Updated:B(括号)的数据已经加强,大家可以再次提交试试(不影响rating和排名)
Level 0 对答案一时爽
对标cf难度:900
知识点:贪心
签到题。最小值显然是0。最大值只需要找到有多少答案牛妹和牛牛是一样的,用题目总数加上这个数即可。
#include <string> #include <iostream> #include <algorithm> using namespace std; #define ll long long int n; int main(){ int i,j; string a,b; cin>>n; cin.get(); getline(cin, a, '\n'); getline(cin, b, '\n'); a.erase(remove_if(a.begin(), a.end(), ::isspace), a.end()); b.erase(remove_if(b.begin(), b.end(), ::isspace), b.end()); int cnt=0; for(i=0;i<n;i++)if(a[i]==b[i])cnt++; cout<<n+cnt<<" "<<0; }
level 1 括号
对标cf难度:1300
知识点:构造、贪心
注意到题目要求字符串长度不超过,而大概是三万多不到4万,所以可以在8万以内完成构造。
一种简单的构造方式是这样:找到一个数,求出 的商和余数,那么则有 。所以先用个左括号,再用个右括号,构成的字符串有个括号对。之后在第个左括号的后面插入一个右括号,就正好增加了个括号对,符合题目要求。
大概长这个样子:
(((....((()((((...((())))....)))))
注意要特判k=0的情况,不要输出空串。
#include<bits/stdc++.h> using namespace std; int main(){ int n,i; cin>>n; if (n == 0) { cout << ")(" << endl; } else { int p=sqrt(n); int c=n/p,y=n%p; for(i=0;i<y;i++)printf("("); printf(")"); for(;i<p;i++)printf("("); for(i=0;i<c;i++)printf(")"); } }
level 2 限制不互素对的排列
对标cf难度:1500
知识点:构造、数学
观察到不超过的一半,那么就简单了。
由于不大于的所有正整数***有个偶数(向下取整),那么如果k<n/2的话,直接取出k+1个偶数依次排列,再从开始从小到大即可。可以证明,后面的部分一定是相邻两两互素的。
如果k=n/2,那么有一个方法是,先取出所有的偶数,除了6以外依次排列,然后6后面接一个3(6和3显然不互素),然后3后面接1、5、7...依次从小到大。
举个例子,当n=10,k=5时,构造的结果是这样的:
2 4 8 10 6 3 1 5 7 9
要注意特判的情况,因为n=5,k=2的时候无法在6后面接一个3了(不存在正整数6),所以无解。
ps:如果 的时候怎么构造?
#include<bits/stdc++.h> using namespace std; int tong[100010]; int main(){ // freopen("13.in","r",stdin); // freopen("13.out","w",stdout); int n,k,i; cin>>n>>k; if(n<6){ if(k==n/2)cout<<-1; else{ cout<<2; tong[2]=1; int i=4; while(k--)cout<<" "<<i,tong[i]=1,i+=2; for(i=1;i<=n;i++)if(!tong[i])cout<<" "<<i; } } else{ if(k==n/2){ for(i=2;i<=n;i+=2){ if(i!=6)cout<<i<<" ",tong[i]=1; } cout<<6<<" "<<3<<" "; tong[6]=tong[3]=1; for(i=1;i<=n;i+=2){ if(!tong[i])cout<<i<<" ",tong[i]=1; } } else{ cout<<2; tong[2]=1; int i=4; while(k--)cout<<" "<<i,tong[i]=1,i+=2; for(i=1;i<=n;i++)if(!tong[i])cout<<" "<<i; } } }
level 2 一群小青蛙呱蹦呱蹦呱
对标cf难度:1500
知识点:数论
我们可以发现,到最后剩余的数一定是不能表示为素数幂形式的数。
因此可以对每个素数对最终答案的贡献分别计算。
对于素数2而言,最大的贡献是(后面无法找到有个2的贡献)。
对于大于2的素数p而言,最大的贡献是(后面无法找到有个p的贡献)。
先线性筛出7.5e7以内的所有素数,然后统计每个素数的贡献后相乘即可。
#include<bits/stdc++.h> using namespace std; #define N 80010000 #define ll long long int num[N], prim[5000060]; int pn = 0; void table(){ memset(num, -1, sizeof(num)); for(int i = 2;i < N;i++){ if(num[i]) prim[pn++] = i; for(int j = 0;j < pn && 1LL*i*prim[j] < N;j++){ num[i*prim[j]] = 0; if(i % prim[j] == 0) break; } } } int main(){ table(); int i; int n; ll res=1,mod=1e9+7; cin>>n; if(n<6){cout<<"empty";return 0;} for(i=1;prim[i]<=n/2;i++){ ll p=prim[i],temp=1; while(temp*p<=n/2)temp*=p; res=res*temp%mod; } ll temp2=1; while(temp2*2<=n/3)temp2*=2; res=res*temp2%mod; cout<<res; }
level 3 点一成零
对标cf难度:1700
知识点:并查集
假设连通块数量为n,那么总方案数就是
每次操作有可能增加或减少连通块的数量,并改变连通块的大小,用并查集维护即可。
#include<bits/stdc++.h> using namespace std; #define ll long long int fa[250010]; int kdm[250020]; string a[505]; int n; int mod=1e9+7; ll power(ll a,ll b){ ll res=1; while(b){ if(b&1)res=res*a%mod; b>>=1; a=a*a%mod; } return res; } ll inv(ll x){ return power(x,mod-2); } int f(int x){ if(fa[x]==x)return x; return f(fa[x]); } void uni(int x,int y){ int p=f(x),q=f(y); if(p==q)return; if(kdm[p]<kdm[q]){ fa[p]=q; kdm[q]+=kdm[p]+1; } else { fa[q]=p; kdm[p]+=kdm[q]+1; } } int visited[505][505]; void dfs(int x,int y){ visited[x][y]=1; if(x>0&&!visited[x-1][y]&&a[x-1][y]=='1')dfs(x-1,y); if(x<n-1&&!visited[x+1][y]&&a[x+1][y]=='1')dfs(x+1,y); if(y>0&&!visited[x][y-1]&&a[x][y-1]=='1')dfs(x,y-1); if(y<n-1&&!visited[x][y+1]&&a[x][y+1]=='1')dfs(x,y+1); } int main(){ // freopen("10.in","r",stdin); // freopen("10.out","w",stdout); int i,j; cin>>n; for(i=0;i<n;i++)cin>>a[i]; for(i=0;i<n*n;i++)fa[i]=i; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(j<n-1&&a[i][j]=='1'&&a[i][j+1]=='1'){ uni(i*n+j,i*n+j+1); } if(i<n-1&&a[i][j]=='1'&&a[i+1][j]=='1'){ uni(i*n+j,(i+1)*n+j); } } } int cnt=0; ll res=1; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(a[i][j]=='1'&&!visited[i][j]){ cnt++; // cout<<kdm[f(n*i+j)]+1<<endl; res=res*(kdm[f(n*i+j)]+1)%mod; dfs(i,j); } } } // cout<<cnt<<endl; for(i=1;i<=cnt;i++)res=res*i%mod; // cerr<<"RES:"<<res<<endl; int q; cin>>q; while(q--){ int x,y; cin>>x>>y; if(a[x][y]=='1'){ cout<<res<<endl; } else{ int temp=1; cnt++; res=res*cnt%mod; // cerr<<"RES:"<<res<<endl; a[x][y]='1'; if(x>0&&a[x-1][y]=='1'&&f(n*(x-1)+y)!=f(n*x+y)){ res=res*inv(kdm[f(n*(x-1)+y)]+1)%mod; temp+=kdm[f(n*(x-1)+y)]+1; uni(n*(x-1)+y,n*x+y); res=res*inv(cnt)%mod; cnt--; } // cerr<<"RES:"<<res<<endl; if(x<n-1&&a[x+1][y]=='1'&&f(n*(x+1)+y)!=f(n*x+y)){ res=res*inv(kdm[f(n*(x+1)+y)]+1)%mod; // cout<<kdm[f(n*(x+1)+y)]+1<<endl; temp+=kdm[f(n*(x+1)+y)]+1; uni(n*(x+1)+y,n*x+y); res=res*inv(cnt)%mod; cnt--; } // cerr<<"RES:"<<res<<endl; if(y>0&&a[x][y-1]=='1'&&f(n*x+y-1)!=f(n*x+y)){ res=res*inv(kdm[f(n*x+y-1)]+1)%mod; temp+=kdm[f(n*x+y-1)]+1; uni(n*x+y-1,n*x+y); res=res*inv(cnt)%mod; cnt--; } // cerr<<"RES:"<<res<<endl; if(y<n-1&&a[x][y+1]=='1'&&f(n*x+y+1)!=f(n*x+y)){ res=res*inv(kdm[f(n*x+y+1)]+1)%mod; temp+=kdm[f(n*x+y+1)]+1; uni(n*x+y+1,n*x+y); res=res*inv(cnt)%mod; cnt--; } // cout<<temp<<" "<<kdm[f(x*n+y)]+1<<endl; res=res*temp%mod; cout<<res<<endl; } } }
level 3 红和蓝
对标cf难度:1700
知识点:树、搜索、dp
可以先树形dp预处理出每个节点子树的节点个数。那么当且仅当每个节点满足以下条件有解:
- 若当前节点x与父节点颜色相同,那么它的子节点子树大小必须为偶数,子节点颜色和x不同。
- 若当前节点x与父节点颜色不同,那么它的子节点子树大小一定有且仅有一个奇数、其他的均为偶数。x的“奇数大小子树”的那个子节点颜色和x相同,其他都和x不同。
#include<bits/stdc++.h> using namespace std; vector<int>g[200020]; int dp[200020]; int su(int x,int pr){ int i,sum=1; for(i=0;i<g[x].size();i++){ if(g[x][i]!=pr){ sum+=su(g[x][i],x); } } return dp[x]=sum; } char out[200020]; int jud=0; char f(char c){ if(c=='R')return 'B'; return 'R'; } void dfs(int x,int pr,char c){ if(jud)return; out[x]=c; int cnt=0,i; for(i=0;i<g[x].size();i++){ if(g[x][i]!=pr){ cnt+=dp[g[x][i]]&1; } } if(out[x]==out[pr]){ if(cnt!=0){jud=1;return;} for(i=0;i<g[x].size();i++){ if(g[x][i]!=pr){ dfs(g[x][i],x,f(c)); } } } else { if(cnt!=1){jud=1;return;} for(i=0;i<g[x].size();i++){ if(g[x][i]!=pr){ if(dp[g[x][i]]&1)dfs(g[x][i],x,c); else dfs(g[x][i],x,f(c)); } } } } int main(){ int n,i; cin>>n; for(i=0;i<n-1;i++){ int x,y; cin>>x>>y; g[x].push_back(y); g[y].push_back(x); } dp[1]=su(1,-1); // for(i=1;i<=n;i++)cout<<dp[i]<<endl; out[0]='B'; dfs(1,0,'R'); if(jud)cout<<-1; else for(i=1;i<=n;i++)cout<<out[i]; } /* 6 1 2 2 3 3 4 3 5 5 6 */
level 4 幂塔个位数的计算
对标cf难度:2100
知识点:找规律、欧拉降幂(划掉)
计算a↑↑n
- 当n为1时,直接输出a的个位数即可。
- 当n=2时,如果a的个位数是2、3、7、8,那么需要观察a的十位数是奇数还是偶数。因为,而2、3、7、8的幂的个位数是4个一循环,所以只用观察a模4是2还是0就行。
如果a的个位数是其他的,那么可以直接输出答案:a的个位数是0 1 5 6 9输出本身即可。a个位数是4则输出6。 - 当n大于2时,由于,而如果a是偶数,模4的值是确定的,所以的个位数也是确定的。而如果a是奇数(特指个位数是3和7),那么模4取决于模4的值。如果模4为1,那么模4也是1,此时a的个位数是3和7的话,的个位数也是3和7,否则应为7和3。
a的个位数是{0,1,2,3,4,5,6,7,8,9}时,对应的的个位数为{0,1,6,7,6,5,6,3,6,9}。
不过这道题也可以欧拉降幂直接秒掉,但由于我欧拉降幂不是很熟,所以这里就不讲解了,想学习的同学可以自行百度。
#include<bits/stdc++.h> using namespace std; #define ll long long int out[10]={0,1,6,7,6,5,6,3,6,9}; int main(){ ll a,b; string A,B; cin>>A>>B; if(B.length()==1&&B[B.length()-1]=='1'){ cout<<A[A.length()-1]; return 0; } a=(A[A.length()-1]-'0')%10; if(A[A.length()-1]=='3'||A[A.length()-1]=='7'){ if(A.length()==1||(A[A.length()-2]-'0')%2==0){ cout<<out[a]; } else{ cout<<a; } return 0; } if((a!=2&&a!=8)||(B.length()>1||B[B.length()-1]!='2')){ cout<<out[a]; } else{ if(a==2){ if(A.length()==1||(A[A.length()-2]-'0')%2==0){ cout<<4; } else cout<<6; } else{ if(A.length()==1||(A[A.length()-2]-'0')%2==0){ cout<<6; } else cout<<4; } } }
level 4 串
对标cf难度:2000
知识点:dp
定义dp[i]为长度为i且包含子序列"us"的字符串的数量。
那么对于长度i+1而言,包含子序列"us"的字符串有两类:
①前i个字符已经包含了子序列"us",后面接任意一个字符。数量为dp[i]*26
②前i个字符包含字母u,但不包含子序列"us"。后面再接一个字符's'即可。数量为26^i-25^i-dp[i]。
两者相加即为dp[i+1]
#include<bits/stdc++.h> using namespace std; #define ll long long int mod=1e9+7; ll power(ll a,ll b){ ll res=1; while(b){ if(b&1)res=res*a%mod; b>>=1; a=a*a%mod; } return res; } ll dp[1000100]={0}; int main(){ dp[1]=0; dp[2]=1; int n,i; cin>>n; for(i=3;i<=1e6;i++)dp[i]=(power(26,i-1)-power(25,i-1)+25*dp[i-1]+mod)%mod; ll res=0; for(i=1;i<=n;i++)res=(res+dp[i])%mod; cout<<res; return 0; }
level 4 三棱锥之刻
对标cf难度:2000
知识点:计算几何
根据r和a的关系一共分4类情况:
①染色面积为0
②染色面积为4个圆形
③染色面积为三棱锥的内表面减去12个小三角(不是三角形,而是一个三角形往内刨掉一个弓形)
④染色面积为三棱锥的内表面全体
分类讨论分别计算即可。
#include<bits/stdc++.h> using namespace std; int main(){ double pi=acos(-1); double a,r=1; cin>>a>>r; double ma=sqrt(6)/4*a,mi=ma/3; double allar=sqrt(3)*a*a; double dd=sqrt(2)/4*a; // cout<<"debug:"<<ma<<" "<<mi<<" "<<dd<<endl; if(r<mi)cout<<0<<endl; else if(r<dd){ printf("%.5f\n",4*pi*(r*r-mi*mi)); } else if(r<ma){ //小等边三角形+小等腰三角形-扇形 double temp=sqrt(r*r-mi*mi); double th=pi-asin(sqrt(3)/6*a/temp); double ntr=pi-th-pi/6; // cout<<ntr<<endl; double d=sin(ntr)*temp*2; // double d2=sin(ntr)*sqrt(3)/3*a/sin(th); // cout<<d<<endl; double h=sqrt(temp*temp-d*d/4); double ar=sqrt(3)/4*d*d+d*h/2-ntr*temp*temp; printf("%.5f\n",allar-12*ar); } else{ printf("%.5f\n",allar); } }
level ? 好玩的数字游戏
对标cf难度:?
知识点:模拟
这道题并没有什么算法,模拟就完事了。
考验的是大家的码力和debug能力。
#include<bits/stdc++.h> using namespace std; long long f(long long x,int p){ long long r=(x%p)*(x%p)/10%p; return (r^(1LL<<17)^(1LL<<57))%p; } int a[10][10]; int pp; int cnt=0; void gaow(int x){ //先移动,再合并,最后移动 int i,j; for(i=1;i<4;i++){ for(j=i-1;j>=0;j--){ if(a[j][x]==0&&a[j+1][x])swap(a[j][x],a[j+1][x]),pp=1; else break; } } for(i=0;i<3;i++){ if(a[i][x]==a[i+1][x]&&a[i+1][x]){ pp=1; cnt+=a[i][x]*2; a[i][x]*=2; a[i+1][x]=0; } } for(i=1;i<4;i++){ for(j=i-1;j>=0;j--){ if(a[j][x]==0&&a[j+1][x])swap(a[j][x],a[j+1][x]),pp=1; else break; } } } void gaoa(int x){ //先移动,再合并,最后移动 int i,j; for(i=1;i<4;i++){ for(j=i-1;j>=0;j--){ if(a[x][j]==0&&a[x][j+1])swap(a[x][j],a[x][j+1]),pp=1; else break; } } for(i=0;i<3;i++){ if(a[x][i]==a[x][i+1]&&a[x][i]){ pp=1; cnt+=a[x][i]*2; a[x][i]*=2; a[x][i+1]=0; } } for(i=1;i<4;i++){ for(j=i-1;j>=0;j--){ if(a[x][j]==0&&a[x][j+1])swap(a[x][j],a[x][j+1]),pp=1; else break; } } } void gaos(int x){ //先移动,再合并,最后移动 int i,j; for(i=2;i>=0;i--){ for(j=i+1;j<4;j++){ if(a[j][x]==0&&a[j-1][x])swap(a[j][x],a[j-1][x]),pp=1; else break; } } for(i=2;i>=0;i--){ if(a[i][x]==a[i+1][x]&&a[i][x]){ pp=1; cnt+=a[i][x]*2; a[i+1][x]*=2; a[i][x]=0; } } for(i=2;i>=0;i--){ for(j=i+1;j<4;j++){ if(a[j][x]==0&&a[j-1][x])swap(a[j][x],a[j-1][x]),pp=1; else break; } } } void gaod(int x){ //先移动,再合并,最后移动 int i,j; for(i=2;i>=0;i--){ for(j=i+1;j<4;j++){ if(a[x][j]==0&&a[x][j-1])swap(a[x][j],a[x][j-1]),pp=1; else break; } } for(i=2;i>=0;i--){ if(a[x][i]==a[x][i+1]&&a[x][i]){ pp=1; cnt+=a[x][i]*2; a[x][i+1]*=2; a[x][i]=0; } } for(i=2;i>=0;i--){ for(j=i+1;j<4;j++){ if(a[x][j]==0&&a[x][j-1])swap(a[x][j],a[x][j-1]),pp=1; else break; } } } void out(){ for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ cout<<a[i][j]<<" "; } cout<<endl; } cout<<endl; } int jud(){ for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ if(a[i][j]==0)return 0; if(i<3&&a[i][j]==a[i+1][j])return 0; if(j<3&&a[i][j]==a[i][j+1])return 0; } } return 1; } int main(){ srand(time(0)); int i,j,k,y; int x=10201,p,q; cin>>x>>p>>q; for(i=0;i<4;i++){ for(j=0;j<4;j++){ cin>>a[i][j]; } } string s=""; // cout<<s<<endl; cin>>s; for(i=0;i<q*2;i+=2){ pp=0; s[i+1]--; switch(s[i]){ case 'W':gaow(s[i+1]-'0');break; case 'A':gaoa(s[i+1]-'0');break; case 'S':gaos(s[i+1]-'0');break; case 'D':gaod(s[i+1]-'0');break; } if(pp){ while(1){ // cout<<x%16/4<<" "<<x%4<<endl; if(a[x%16/4][x%4]==0){a[x%16/4][x%4]=2;x=f(x,p);break;} x=f(x,p); } } // out(); if(jud())break; } // out(); cout<<cnt<<endl; if(i==q*2)cout<<"never die!"; else cout<<i/2+1; } /* 10007 1000001 1 0 0 0 0 0 0 0 0 0 0 0 0 8 4 2 2 D4 */
全部评论
(22) 回帖