对于上周的总结
上周的训练断了，可能也为 ICPC 爆炸埋下种子。
毕竟这东西一两周的积累远远不够
这周末打完西安赛后，应该会空出很多时间，准备开始机器学习的学习以及部分生信的学习。
11月7日
写了下 CF 1750 的 C D
CF1750 C. Complementary XOR
题目大意，给你 a,b 两个 01 串，询问是否能通过以下操作 f(l,r) 将 a,b 变成两个全为 0 的序列
f(l,r) 操作把 i∈[l,r] 中的 ai 变为 i−ai ，将i∈/[l,r] 的 bi 变为 1−bi
首先我们考虑 a=b,a=¬b 这两个都有一个很显然的结论，如果 ai=bi=1 那么我们可以进行 f(1,r),f(1,r−1) 之后ai=bi=0
我们前面的都相等，到 n 不满足，此时我们无论是改 an,bn 都不可以，这种情况不可能成立。
实际上题目给了保证能在 n+5 步得到答案，所以这里更可能是个小范围打表找规律，然后做。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=100100;
int n;
char a[maxn],b[maxn];
int T,cnt;
struct sol{
int l,r;
}q[maxn];
void solve()
{
int lk1=0,lk2=0; cnt=0;
for(int i=1;i<=n;i++)
{
lk1+=(a[i]!=b[i]);
lk2+=a[i]==b[i];
}
if(lk1==n)
{
q[++cnt].l=1;
q[cnt].r=n;
for(int i=1;i<=n;i++) a[i]=b[i];
}
if(lk1==n||lk2==n)
{
cout<<"Yes\n";
}
else
{
cout<<"No\n";
return ;
}
if(a[1]=='1')
{
q[++cnt].l=1;
q[cnt].r=n;
q[++cnt].l=2;
q[cnt].r=n;
}
int las=1;
for(int i=2;i<=n;i++)
{
if(a[i]=='0')
{
las=i;
continue;
}
while(a[i]==a[i+1]&&i+1<=n) i++;
q[++cnt].l=1;
q[cnt].r=i;
q[++cnt].l=1;
q[cnt].r=las;
}
cout<<cnt<<endl;
for(int i=1;i<=cnt;i++)
{
cout<<q[i].l<<" "<<q[i].r<<endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
solve();
}
return 0;
}
|
CF1750 D. Count GCD
题目大意，给你一个序列，满足 gcd(b1,b2,...,bi)=ai ，并且 bi<=m 询问有多少个 bn 满足。
首先第一个数是确定的，为a1，考虑第二个位置的数字
如果 a1<a2 说明无解
如果 a1=a2 说明 b2=⌊a1m⌋
如果 a1>a2
如果 a2∣a1 我们要求的即为 (1,m) 中 gcd(a1,x)=a2 的 x 个数，这就是一个很显然的容斥。
其他情况下，解不存在。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=200200;
const int modp=998244353;
int n,m,a[maxn];
int T;
int p[maxn*10],cnt,inp[maxn*10];
void getprime(int n)
{
inp[1]=1;
for(int i=2;i<=n;i++)
{
if(!inp[i]) p[++cnt]=i;
for(int j=1;j<=cnt&&i*p[j]<=n;j++)
{
inp[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
}
void solve()
{
int ans=1;
int tmp=a[1];
for(int i=2;i<=n;i++)
{
if(a[i]==tmp) ans=(1ll*ans*(m/tmp)%modp);
if(a[i]>tmp)
{
ans=0;
break;
}
if(a[i]<tmp)
{
int mmp=0;
if(tmp%a[i]==0)
{
mmp=tmp/a[i];
tmp=a[i];
int sz=0,d[30]={0};
for(int j=1;p[j]*p[j]<=mmp;j++)
{
if(mmp%p[j]==0)
{
d[++sz]=p[j],mmp/=p[j];
while(mmp%p[j]==0) mmp/=p[j];
}
}
if(mmp>1) d[++sz]=mmp;
int aans=0;
for(int s=1;s<=(1<<sz)-1;s++)
{
int lk=1;
int cc=0;
for(int j=1;j<=sz;j++)
{
if(1<<(j-1)&s) lk*=d[j],cc++;
}
aans+=((m/a[i])-(m/a[i])/lk)*((cc&1)?1:-1);
}
ans=(1ll*ans*aans)%modp;
}
else
{
cout<<"0\n";
return ;
}
}
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin>>T;
getprime(1000000);
while(T--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
solve();
}
}
|
11月8日
今天过了俩板子，一个st表一个线段树2
CF1747D. Yet Another Problem
题目大意，给你一个 01 序列，询问 (l,r) 区间最少操作多少次可以把这个区间变为全 0 ，不能的话输出 -1 ，每次询问互不影响。注意，每次只能操作长度为奇数的区间
我们先考虑无解的情况:
这个区间所有数字异或和不为 0
这个区间形如 2 2 4 4 此时只能对偶数长度区间操作，也不可以
考虑答案为0 的情况
这个区间全为 0
考虑答案为1
区间长度为奇数
长度为偶数的区间有一个端点是 0
考虑答案为 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=200100;
int n,m;
int a[maxn],s[maxn],b[maxn],cnt;
int sx[maxn];
int v1[maxn],v2[maxn],f1[maxn],f2[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int las=0;
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]^a[i];
sx[i]=sx[i-1]+(!a[i]);
b[++cnt]=s[i];
}
b[++cnt]=0;
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
for(int i=0;i<=n;i++)
{
s[i]=lower_bound(b+1,b+cnt+1,s[i])-b;
}
memset(f1,0x3f,sizeof(f1));
memset(f2,0x3f,sizeof(f2));
for(int i=n;i>=0;i--)
{
if(i&1)
{
if(v1[s[i]]) f1[i]=v1[s[i]];
if(v2[s[i]]) f2[i]=v2[s[i]];
v1[s[i]]=i;
}
else
{
if(v1[s[i]]) f1[i]=v1[s[i]];
if(v2[s[i]]) f2[i]=v2[s[i]];
v2[s[i]]=i;
}
}
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
if((r-l+1)&1)
{
if(s[r]^s[l-1]) cout<<-1<<endl;
else if(sx[r]-sx[l-1]==r-l+1) cout<<0<<endl;
else cout<<1<<endl;
}
else
{
if(s[r]^s[l-1]) cout<<-1<<endl;
else
{
if(r-l+1==2)
{
if(a[l]==a[r]&&a[l]==0) cout<<0<<endl;
else if(a[l]==a[r]) cout<<-1<<endl;
else cout<<-1<<endl;
}
else if(sx[r]-sx[l-1]==r-l+1) cout<<0<<endl;
else if(((l-1)%2==1&&f2[l-1]>=r)||((l-1)%2==0&&f1[l-1]>=r)) cout<<-1<<endl;
else
{
if(!a[l]||!a[r]) cout<<1<<endl;
else cout<<2<<endl;
}
}
}
}
return 0;
}
|
还学了下kruskal 重构树，写道另一篇博客里面了
11月9日
今天主要是在偷懒，过了威海的I
I. Dragon Bloodline
题目大意，生产某种物品有 n 种资源需求，每种资源需求 ai ,同时你可以以 2i−1 速率生产，并且最多有 bi 个，询问最多能生产多少个。
很显然的，最多能生产多少可以用一个二分，于是此题难点在于怎么把数字分成 n 组，满足每组能生长 ≥ai
考虑到取等的时候，此题变为 np 所以肯定不是分组背包。
那么我们可以贪心让大的数字尽可能发挥作用，令现在我们二分的答案是 k ，当2i−1≤ai∗k 说明这个数字完全发挥作用，可以放进去。
按照这个道理放数字就可以了，还需要注意二分的边界判断。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=50050;
int n,m,a[maxn],b[maxn],T;
int c[maxn];
bool cmp(const int x,const int y)
{
return x>y;
}
int fd(int x)
{
int l=1,r=n,ans=0,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(c[mid]>=x) l=mid+1,ans=mid;
else r=mid-1;
}
return ans;
}
int check(int x)
{
for(int i=1;i<=n;i++) c[i]=a[i]*x;
for(int i=m;i;i--)
{
sort(c+1,c+n+1,cmp);
int tmp=b[i];
int lk=1<<(i-1);
int k=fd(lk);
if(tmp<=k)
{
for(int j=1;j<=tmp;j++) c[j]-=lk;
continue;
}
for(int j=1;j<=n&&tmp>=1;j++)
{
if(c[j]<=0)
{
break;
}
else if(tmp<c[j]/lk)
{
c[j]-=lk*tmp;
tmp=0;
}
else tmp-=c[j]/lk,c[j]%=lk;
}
sort(c+1,c+n+1,cmp);
for(int j=1;j<=min(tmp,n);j++) c[j]-=lk;
}
sort(c+1,c+n+1,cmp);
if(c[1]<=0) return 1;
return 0;
}
int solve()
{
cin>>n>>m;
int mx=0;
for(int i=1;i<=n;i++) cin>>a[i],mx=max(mx,a[i]);
for(int i=1;i<=m;i++) cin>>b[i];
int l=1,r=2e15/mx,mid,ans=0;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--)
{
solve();
}
return 0;
}
|
十一月十日
过了威海的 G
题目大意，给定 l,r，求 ∑k=lr[gcd(kx⊕x,x)=1]
我们有个猜想，假设 2k 是第一个比 x 大的数字，那么就有一个 2k 的循环节。
然后打表就把这题过了(
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2002000;
int s[maxn],x,n;
int gcd(int x,int y)
{
if(!y) return x;
return gcd(y,x%y);
}
signed main()
{
ios::sync_with_stdio(false);
cin>>x>>n;
int lk=1;
while(lk<x) lk<<=1;
for(int i=1;i<=lk;i++)
{
s[i]=s[i-1]+(gcd(x*i^x,x)==1);
}
int l,r,rl,rr;
for(int i=1;i<=n;i++)
{
cin>>l>>r;
int ans=0;
if(l%lk==0&&r%lk==0) cout<<s[lk]*((r-l+1)/lk)<<endl;
else if(l%lk==0)
{
ans+=s[lk]*((r-l)/lk);
ans+=s[r%lk];
cout<<ans<<endl;
}
else if(r%lk==0)
{
ans+=s[lk]*((r-l)/lk);
ans+=s[lk]-s[l%lk-1];
cout<<ans<<endl;
}
else
{
rl=(l-1)/lk+1; rl*=lk;
rr=(r)/lk; rr*=lk;
if(rr-rl>=0)
{
ans+=(rr-rl)/lk*s[lk];
ans+=s[lk]-s[l%lk-1];
ans+=s[r%lk];
cout<<ans<<endl;
}
else
{
ans+=s[r%lk]-s[l%lk-1];
cout<<ans<<endl;
}
}
}
}
|
