2022“杭电杯”中国大学生算法设计超级联赛（2）补题
签到题，输出(，数字)即可
区间合并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
#define int long long
const int maxn = 1e5 + 10;
using namespace std;
struct node {
int l, r;
bool operator < (const node &x) const {
if (l == x.l) return r < x.r;
return l < x.l;
}
}a[maxn];
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].l >> a[i].r;
}
a[n + 1].l = 1e9 + 10;
sort(a + 1, a + 1 + n);
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (a[i].r >= a[i + 1].l) {
break;
}
cnt++;
}
cout << cnt << endl;
}
}
|
不难得出p q-1=k m,则要求的m是一个比p和q都大的质因子，据说可以证明出最多只有一个这样的质因子，所以枚举p*q-1的质因子就行了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const LL mod = 1e9+7;
const LL maxn = 3e6+10;
bool isprime(LL n){
if(n<2)return false;
for(LL i = 2; i <= n/i; i++){
if(n%i==0)return false;
}
return true;
}
int main(){
IOS;
int T;
cin>>T;
while(T--){
LL p, q, en;
cin>>p>>q>>en;
LL mm = p*q-1, mmd = -1;
LL sqm = sqrt(mm);
for(LL i = 1; i <= sqm+1; i++){
if(mm%i==0){
if(isprime(i) && i>en && i>q && i>p){
mmd = i; break;
}
if(mm>en*i && mm>q*i && mm>p*i && isprime(mm/i)){
mmd = mm/i; break;
}
}
}
if(mmd==-1){
cout<<"shuanQ\n";
}else{
cout<<q*en%mmd<<"\n";
}
}
return 0;
}
|
对于小于1e6的情况，就是个硬币问题，可以直接类似于背包的做法O(n)去dp；对于大于1e6的情况，可以直接用365把他们减到1e6以下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const LL maxn = 2e6+10;
const LL inf = 2e18+10;
LL c[] = {7, 31, 365};
LL f[maxn] = {0};
int main(){
IOS;
for(LL i = 1; i < maxn; i++)f[i] = inf;
LL m = 3;
for (LL j = 1; j < maxn; j++){
for (LL i = 0; i < m; i++)
if (j - c[i] >= 0)
f[j] = min(f[j], f[j - c[i]] + 1);
}
LL T; cin>>T;
while(T--){
LL x; cin>>x;
LL sum = 0;
if(x > (LL)1e6){
sum = (x-1e6)/365+1, x -= sum*365;
}
if(f[x]!=inf)cout<<f[x]+sum<<"\n";
else cout<<"-1\n";
}
return 0;
}
|
