首页 > 代码库 > Codeforces Round #419 (Div. 2) A-E
Codeforces Round #419 (Div. 2) A-E
上紫啦！
E题1:59压哨提交成功翻盘
（1:00就做完了调了一个小时，还好意思说出来？ （逃））
题面太长就不复制了，但是配图很可爱所以要贴过来
九条可怜酱好可爱呀
A - Karen and Morning
询问从当前时刻过多久，时间会形成回文串的形式。
暴力呀暴力
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 int read(){ 8 int x=0,f=1;char ch=getchar(); 9 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}10 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}11 return x*f;12 }13 int a,b;14 int test(){15 if(a/10 == b%10 && a%10==b/10)return 1;16 return 0;17 }18 int main(){19 a=read();b=read();20 for(int i=0;i>=0;i++){21 if(test()){22 printf("%d\n",i);23 return 0;24 }25 b++;26 if(b>59)b=0,a++;27 if(a>23)a=0;28 }29 return 0;30 }
B - Karen and Coffee
扫描 前缀和
询问区间内有多少数出现次数超过K次
显然可以差分+前缀和
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 const int mxn=210005; 8 int read(){ 9 int x=0,f=1;char ch=getchar();10 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}11 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}12 return x*f;13 }14 int smm[mxn];15 int f[mxn];16 int n,K,Q;17 int main(){18 int i,j,a,b;19 n=read();K=read();Q=read();20 for(i=1;i<=n;i++){21 a=read();b=read();22 smm[a]++;23 smm[b+1]--;24 }25 for(i=1;i<=200000;i++){26 f[i]=f[i-1];27 smm[i]+=smm[i-1];28 if(smm[i]>=K)f[i]++;29 }30 while(Q--){31 a=read();b=read();32 int ans=f[b]-f[a-1];33 printf("%d\n",ans);34 }35 return 0;36 }
C - Karen and Game
贪心
可以贪心删。如果行更长就先删行再删列，否则先删列再删行。
如果删不光就是无解。
好多人没有判删顺序，全部先删行，hack了四个，233
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 const int mxn=5000050; 8 int read(){ 9 int x=0,f=1;char ch=getchar();10 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}11 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}12 return x*f;13 }14 int stH[mxn],top1=0,stL[mxn],top2=0;15 int mp[201][201];16 int n,m;17 void getH(){18 int i,j;19 for(i=1;i<=n;i++){20 int tmp=0x3f3f3f3f;21 for(j=1;j<=m;j++){22 tmp=min(tmp,mp[i][j]);23 }24 for(j=1;j<=m;j++){25 mp[i][j]-=tmp;26 }27 while(tmp){28 stH[++top1]=i;tmp--;29 }30 }31 return;32 }33 void getL(){34 int i,j;35 for(i=1;i<=m;i++){36 int tmp=0x3f3f3f3f;37 for(j=1;j<=n;j++){38 tmp=min(tmp,mp[j][i]);39 }40 for(j=1;j<=n;j++){41 mp[j][i]-=tmp;42 }43 while(tmp){44 stL[++top2]=i;tmp--;45 }46 }47 return;48 }49 void check(){50 for(int i=1;i<=n;i++){51 for(int j=1;j<=m;j++){52 if(mp[i][j]>0){53 printf("-1\n");54 exit(0);55 }56 }57 }58 return;59 }60 int main(){61 int i,j;62 n=read();m=read();63 for(i=1;i<=n;i++){64 for(j=1;j<=m;j++){65 mp[i][j]=read();66 }67 }68 if(n<=m){69 getH();getL();70 }71 else{72 getL();getH();73 }74 check();75 printf("%d\n",top1+top2);76 while(top1){77 printf("row %d\n",stH[top1--]);78 }79 while(top2){80 printf("col %d\n",stL[top2--]);81 }82 return 0;83 }
D - Karen and Test
数学问题 找规律 组合数
手列一个表看一下，可以发现神奇的规律。
倒数第二行肯定是$k_1*a_1+k_3*a_3+k_5*a_5+..$ 和 $ k_2*a_2 + k_4 * a_4 + k_6 * a_6+..$ 的形式。
k的值和二项式系数有关
如果n%4==2，答案是前者加后者，如果n%4==0，答案是前者减后者，如果n是奇数，就先算一行，把n变成偶数。
比赛的时候没做出来，时候补题因为阶乘没加LL，WA得飞起
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mxn=200010; 9 const int mod=1e9+7;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14 return x*f;15 }16 int n;17 int a[mxn];18 int fac[mxn],inv[mxn];19 void init(){20 fac[0]=fac[1]=inv[0]=inv[1]=1;21 for(int i=2;i<mxn;i++){22 fac[i]=(LL)fac[i-1]*i%mod;23 inv[i]=((-mod/i*(LL)inv[mod%i]%mod)+mod)%mod;24 }25 for(int i=2;i<mxn;i++)26 inv[i]=(LL)inv[i-1]*inv[i]%mod;27 return;28 }29 int C(int n,int m){30 if(n<m)return 0;31 return (LL)fac[n]*inv[m]%mod*inv[n-m]%mod;32 }33 int main(){34 int i,j;35 init();36 n=read();37 for(i=1;i<=n;i++)a[i]=read();38 if(n<=2){39 printf("%d\n",(a[1]+a[2])%mod);return 0;40 }41 if(n&1){42 for(i=1;i<n;i++){43 if(i&1)a[i]=(a[i]+a[i+1])%mod;44 else a[i]=(a[i]-a[i+1]+mod)%mod;45 }46 n--;47 }48 int tmp1=0,tmp2=0;49 int ed=n>>1;50 for(i=1;i<=ed;i++){51 tmp1=((LL)tmp1+(LL)C(ed-1,i-1)*a[i*2-1])%mod;52 tmp2=((LL)tmp2+(LL)C(ed-1,i-1)*a[i*2])%mod;53 }54 // printf("%d %d\n",tmp1,tmp2);55 if(n%4==0)tmp1=((LL)(tmp1-tmp2)%mod+mod)%mod;56 else tmp1=((LL)tmp1+tmp2)%mod;57 printf("%d\n",tmp1);58 return 0;59 }
E - Karen and Supermarket
动态规划 树形DP
$f[u][j]$表示在u结点，子树中共选了j件物品，有打折商品的最小花费
$g[u][j]$表示在u结点，子树中共选了j件物品，没有打折商品的最小花费
转移的时候，f可以加g，g不能加f，分别计算一下就可以了。
不到一个小时的时候就写完了，自信提交发现TLE。
原因是DP的时候，先加上了子树size再O(n^2)转移。
↑然而这样复杂度并不是O(n^2)的，在链数据上会被卡得超慢
↑然而一直以为是常数大，尝试了各种优化，提交了一串，无限TLE
↑在最后十几分钟冷静下来思考，终于察觉到了问题，改成先转移再加子树size，在1:59压哨提交PP
↑真™刺激
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #include<vector> 7 #define LL long long 8 using namespace std; 9 const int mxn=100010;10 const int INF=0x3f3f3f3f;11 int read(){12 int x=0,f=1;char ch=getchar();13 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}14 while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();}15 return x*f;16 }17 struct edge{18 int v,nxt;19 }e[mxn<<1];20 int hd[mxn],mct=0;21 void add_edge(int u,int v){22 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return;23 }24 int n,B;25 int w[mxn],c[mxn],fa[mxn],sz[mxn];26 int f[5005][5005];27 int g[5005][5005];28 vector<int>ve[5005];29 int cmp(int a,int b){30 return sz[a]<sz[b];31 }32 void DFS(int u){33 f[u][0]=g[u][0]=0;34 f[u][1]=w[u]-c[u];g[u][1]=w[u];35 sz[u]=1;int tmp=1;36 for(int i=hd[u];i;i=e[i].nxt){37 DFS(e[i].v);38 ve[u].push_back(e[i].v);39 tmp+=sz[e[i].v];40 }41 sort(ve[u].begin(),ve[u].end(),cmp);42 for(register int i=2;i<=tmp;i++)f[u][i]=g[u][i]=INF;43 for(int i=0;i<ve[u].size();i++){44 int v=ve[u][i];45 // sz[u]+=sz[v];46 for(int j=sz[u];j>=0;j--){47 // int ed=min(sz[v],j);48 if(j>0){49 for(int k=1;k<=sz[v];k++){50 if(f[v][k]>B && g[v][k]>B)break;51 if(f[v][k]<=B)f[u][j+k]=min(f[u][j+k],f[u][j]+f[v][k]);52 if(g[v][k]<=B)f[u][j+k]=min(f[u][j+k],f[u][j]+g[v][k]);53 }54 }55 for(int k=0;k<=sz[v];k++){56 if(g[v][k]>B)break;57 g[u][j+k]=min(g[u][j+k],g[u][j]+g[v][k]);58 }59 // ed=min(sz[v],j-1);60 61 }62 sz[u]+=sz[v];63 }64 return;65 }66 int main(){67 int i,j;68 n=read();B=read();69 for(i=1;i<=n;i++){70 w[i]=read();c[i]=read();71 if(i>1){72 fa[i]=read();73 add_edge(fa[i],i);74 }75 }76 // memset(f,0x3f,sizeof f);77 // memset(g,0x3f,sizeof g);78 DFS(1);79 int mx=0;80 for(i=1;i<=n;i++){81 if(f[1][i]<=B || g[1][i]<=B)mx=i;82 else break;83 }84 printf("%d\n",mx);85 /* for(i=1;i<=sz[1];i++){86 printf("%d %d\n",f[1][i],g[1][i]);87 }*/88 return 0;89 }
Codeforces Round #419 (Div. 2) A-E
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。