对于上周的总结
上周的训练断了,可能也为 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; } } } }
|