2022 ICPC网络预选赛1
![在这里插入图片描述](https://img-blog.csdnimg.cn/9e86f103621a4de79533cc5ad410285d.png)
A
最难的一点就是没有处理环形后效性
比如询问L=1R=9 ->111000111应该是长度为6的连续一段1,贡献为6/2=3而不是2+2=4
做法就是预处理L右边最近的0的下标x,预处理R左边最近的0的下标y,然后把一段区间分成三份求解,中间就直接贡献sum[y]-sum[x-1]
然后把左边和右边连续的1加起来除于2
做法1,dp处理前缀和贡献
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> using namespace std; const int N=1e6+10; char s[N]; int n,m,sum[N],L[N],R[N]; int f[N],l,r; signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m>>s+1; int cnt=0; for(int i=1;i<=n;i++){ if(s[i]=='1')cnt++; else cnt=0; f[i]=f[i-cnt-1]+(cnt+1)/2; } L[0]=0; for(int i=1;i<=n;i++){ if(s[i]=='1')L[i]=L[i-1]; else L[i]=i; } R[n+1]=n+1; for(int i=n;i>=1;i--){ if(s[i]=='1')R[i]=R[i+1]; else R[i]=i; } while(m--){ cin>>l>>r; int len=r-l+1; int cnt1=r-L[r]+R[l]-l; int t=f[L[r]]-f[R[l]-1]+(cnt1+1)/2; cout<<max(0,len/3-t)<<'\n'; } }
|
做法2,对一段连续的1采取贡献差分,也就是+1+0+1+0+1+0,然后前缀和
这样可以保证奇数的时候上取整,偶数下取整
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
| #include<bits/stdc++.h> using namespace std; const int N=1e6+10; char s[N]; int n,m,sum[N],L[N],R[N]; int cal(int l,int r){ int ll=R[l]; int rr=L[r]; if(ll>=rr)return (r-l+1)/2; int len1=(r-rr)+(ll-l); return sum[rr]-sum[ll-1]+(len1+1)/2; } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m>>s+1; int last=-1; for(int i = 1; i <= n ; i ++ ) { if(s[i] == '1') { if(last != i - 1) sum[i] = 1, last = i; else last = -1; } sum[i] += sum[i - 1]; } for(int i=1;i<=n;i++){ if(s[i]=='0')L[i]=i; else L[i]=L[i-1]; } R[n+1]=n+1; for(int i=n;i>=1;i--){ if(s[i]=='0')R[i]=i; else R[i]=R[i+1]; } while(m--){ int l,r; cin>>l>>r; int len=r-l+1; int t=cal(l,r); cout<<max(0,len/3-t)<<'\n'; } }
|
B
先预处理我要选x个tower的状态,pushback进vector里面
开一个优先队列对一个个时间片,先拿出来,t=t+a[i],然后放进去
dfs爆搜
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
| #include<bits/stdc++.h> using namespace std; const int N=16,M=(1<<N)+10; int n,a[N],b[N],ans=1e9; vector<int>v[M]; typedef pair<int,int>PII; priority_queue<PII,vector<PII>,greater<PII>>q; #define t first #define u second int cal(int x){ int ans=0; for(int i=0;i<n;i++)ans+=x>>i&1; return ans; } int dfs(int s,int T){ if(s+1==1<<n)return T; int sum=0; T=q.top().t; while(q.size()&&q.top().t==T){ int u=q.top().u; int t=q.top().t; sum+=b[u]; q.pop(); q.push({T+a[u],u}); } if(sum+cal(s)>=n)return T; int ans=1e9; for(auto x:v[sum]){ if(x&s)continue; for(int i=0;i<n;i++){ if(x>>i&1)q.push({a[i]+T,i}); } ans=min(ans,dfs(s|x,T)); } return ans; } signed main(){ cin>>n; for(int i=0;i<1<<n;i++){ v[cal(i)].push_back(i); } for(int i=0;i<n;i++)cin>>a[i]>>b[i]; for(int i=0;i<n;i++){ while(q.size())q.pop(); q.push({a[i],i}); ans=min(ans,dfs(1<<i,0)); } cout<<ans; }
|
C
结论题,去理解题意,感受一下为什么
没有特判n==1wa了一发,没有清空度数数组wa了一发
D
我写的爆搜要剪很多枝才能刚好冲过去,vp的时候一直超时,改完就一发a了
而且代码很丑
说白了就是枚举长度len,枚举后缀零个数x,然后放一个1去挡,然后最前面也是一个1,dfs爆搜放y-2个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 41 42 43 44 45 46 47 48 49
| #include<bits/stdc++.h> using namespace std; set<int>S; int T,l,r,len; int a[31];
void dfs(int l,int r,int y){ if(l>r){ if(y==0){ int x=0; for(int i=0;i<len;i++)x+=a[i]<<i; S.insert(x); return; } else return; } if(y==0){dfs(r+1,r,y);return;} if(y==r-l+1){ for(int i=l;i<=r;i++)a[i]=1; dfs(r+1,r,0); for(int i=l;i<=r;i++)a[i]=0; return; } if(y>r-l+1)return; if(y)a[l]=1,dfs(l+1,r,y-1); a[l]=0,dfs(l+1,r,y); } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); S.insert(2); for(len=4;len<=30;len++){ for(int i=0;i<len;i++)a[i]=0; for(int x=2;x<=len/2;x++){ for(int i=0;i<x;i++)a[i]=0; a[x]=1; a[len-1]=1; int y=x-2; dfs(x+1,len-2,y); } } cin>>T; while(T--){ cin>>l>>r; auto it=S.lower_bound(l); if(it==S.end()||*it>r)cout<<"-1"<<'\n'; else cout<<*it<<'\n'; } }
|
看到有个人写了个很优美的折半搜索
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
| #include<bits/stdc++.h> using namespace std; set<int>S; int T,l,r,len; int a[31]; void dfs(int x,int cnt,int p){ if(cnt==0){ if(x<=1e9)S.insert(x); return; } if(p==30)return; dfs(x|1<<p,cnt-1,p+1); dfs(x,cnt,p+1); } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); for(int i=1;i<=16;i++)dfs(1<<i,i-1,i+1); cin>>T; while(T--){ cin>>l>>r; auto it=S.lower_bound(l); if(it==S.end()||*it>r)cout<<"-1"<<'\n'; else cout<<*it<<'\n'; } }
|
G
没读题
感觉读懂硬搞能写
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
| #include <bits/stdc++.h> #define rep(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std; typedef long long ll; const int N = 110; ll dp[6][55][35][27][22], k[5], x[5], s[N]; int n, T; int main() { scanf("%d%d", &n, &T); _for(i, 1, 4) { scanf("%lld", &x[i]); k[i] = k[i - 1] + x[i]; } _for(i, 1, n) { ll x; scanf("%lld", &x); s[i] = s[i - 1] + x; } ll ans = 0; _for(i, 1, n) _for(p1, 0, n / 2 + 1) _for(p2, 0, n / 3 + 1) _for(p3, 0, n / 4 + 1) _for(p4, 0, n / 5 + 1) { if(p1 * k[1] + p2 * k[2] + p3 * k[3] + p4 * k[4] > T) break; ll res = dp[(i - 1 + 6) % 6][p1][p2][p3][p4]; if(p1 - 1 >= 0 && i - 2 >= -1) res = max(res, dp[(i - 2 + 6) % 6][p1 - 1][p2][p3][p4] + s[i] - s[i - 1]); if(p2 - 1 >= 0 && i - 3 >= -1) res = max(res, dp[(i - 3 + 6) % 6][p1][p2 - 1][p3][p4] + s[i] - s[i - 2]); if(p3 - 1 >= 0 && i - 4 >= -1) res = max(res, dp[(i - 4 + 6) % 6][p1][p2][p3 - 1][p4] + s[i] - s[i - 3]); if(p4 - 1 >= 0 && i - 5 >= -1) res = max(res, dp[(i - 5 + 6) % 6][p1][p2][p3][p4 - 1] + s[i] - s[i - 4]); dp[i % 6][p1][p2][p3][p4] = res; if(i == n) ans = max(ans, dp[i % 6][p1][p2][p3][p4]); } printf("%lld\n", ans); return 0; }
|
H
赛时沛桐过的,写个递归就好了,如果紧张的话很大概率写不好
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
| #include<bits/stdc++.h> using namespace std; #define int long long const int mod=20220911; int ans; int dfs(){ int ans=0; string s; while(cin>>s&&s!="for"){ if(s[0]=='l')ans++; else if(s[0]=='r')ans+=dfs(); } int x; cin>>x; return x*ans%mod; } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); string s; while(cin>>s&&s!="fin"){ if(s[0]=='l')ans++; else if(s[0]=='r')ans+=dfs(); ans%=mod; } cout<<ans; }
|
J
非常好的期望题
根据样例猜构造方式,需要刷题量足够多足够敏感
设第一个为A,然后想到错位相消就很快了
记得特判算出来的A不合法的情况和超出范围的情况
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| #include<bits/stdc++.h> #define int long long using namespace std; int x,y,s,A,a,b,n,m; signed main(){ cin>>x>>y; for(int i=2;i<x;i++)s+=i; for(m=2;;m++){ n=m-x+3; if(n<=1||n>m)continue; a=m*y-n*x+x-s; b=m-s-n*x+x; int d=__gcd(a,b); a/=d; b/=d; if(a*b<=0||a>b)continue; if(a>10000||b>10000)continue; cout<<a<<" "<<b<<'\n'; for(int i=m;i>=n;i--)cout<<1<<" "<<i<<'\n'; cout<<"1 1"<<'\n'; return 0; } }
|
L
赛时无法解决操作的前缀限制关系,即app,ppa会对应不同的方案,然后就不会了
结果发现题解是预处理了一个限制数组
,理解不是特别困难但就是想不到
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> using namespace std; const int N=5e5+10; int f[N][30],vis[30],dont[30][30],n,m; char a[N],b[N]; signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>a+1>>b+1; n=strlen(a+1); m=strlen(b+1); for(int i=1;i<=m;i++){ for(int j=0;j<26;j++){ if(vis[j])dont[j][b[i]-'a']=1; } vis[b[i]-'a']=1; } for(int i=1;i<=n;i++)f[i][a[i]-'a']=1; for(int i=1;i<=n;i++){ int x=a[i]-'a'; if(!vis[x]){ for(int j=0;j<26;j++)f[i][j]=f[i-1][j]+1; } else{ for(int j=0;j<26;j++){ f[i][j]=max(f[i][j],f[i-1][j]); if(dont[j][x])continue; f[i][x]=max(f[i][x],f[i-1][j]+1); } } } int ans=0; for(int j=0;j<26;j++)ans=max(ans,f[n][j]); cout<<ans; }
|
感觉区域赛的dp还是非常考验大抽象级别的思维量,非常的灵活
比较有特点的是去年威海站的打砖块,某div2F题red and black
acwing宝藏和昨晚的cf#281 E题