首页 > 代码库 > Codeforces Round #419
Codeforces Round #419
A
Karen and Morning
找最近的回文时间
模拟 往后推 判判就行
//By SiriusRen#include <bits/stdc++.h>using namespace std;int tx,ty,T;bool check(){ int rx=tx/10,ry=tx%10; return ry*10+rx==ty;}int main(){ scanf("%d:%d",&tx,&ty); while(1){ if(check()){printf("%d\n",T);return 0;} T++,ty++; if(ty==60)tx++,ty=0; if(tx==24)tx=0; }}
B
Karen and Coffee
差分前缀和推一发完事~
//By SiriusRen#include <bits/stdc++.h>using namespace std;const int N=400050;int n,k,q,xx,yy,a[N],s[N];int main(){ scanf("%d%d%d",&n,&k,&q); for(int i=1;i<=n;i++)scanf("%d%d",&xx,&yy),a[xx]++,a[yy+1]--; for(int i=1;i<N;i++)a[i]+=a[i-1]; for(int i=1;i<N;i++)s[i]=s[i-1]+(a[i]>=k); for(int i=1;i<=q;i++)scanf("%d%d",&xx,&yy),printf("%d\n",s[yy]-s[xx-1]);}
C
Karen and Game
贪心
先把整张图能删的都删了 再枚举行、列
输出比较烦
//By SiriusRen#include <bits/stdc++.h>using namespace std;const int N=505;int n,m,a[N][N],minn=N,rec[N],recl[N],T;int main(){ scanf("%d%d",&n,&m);memset(rec,0x3f,sizeof(rec));memset(recl,0x3f,sizeof(recl)); for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]),minn=min(minn,a[i][j]); for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]-=minn; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++)rec[i]=min(rec[i],a[i][j]); for(int j=1;j<=m;j++)a[i][j]-=rec[i]; } for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]!=a[1][j]){puts("-1");return 0;}else recl[j]=min(recl[j],a[i][j]); for(int i=1;i<=n;i++)for(int j=1;j<=rec[i];j++)T++; for(int i=1;i<=m;i++)for(int j=1;j<=recl[i];j++)T++; if(n<m)for(int i=1;i<=minn;i++)for(int j=1;j<=n;j++)T++; else for(int i=1;i<=minn;i++)for(int j=1;j<=m;j++)T++; printf("%d\n",T); for(int i=1;i<=n;i++)for(int j=1;j<=rec[i];j++)printf("row %d\n",i); for(int i=1;i<=m;i++)for(int j=1;j<=recl[i];j++)printf("col %d\n",i); if(n<m)for(int i=1;i<=minn;i++)for(int j=1;j<=n;j++)printf("row %d\n",j); else for(int i=1;i<=minn;i++)for(int j=1;j<=m;j++)printf("col %d\n",j);}
D
Karen and Test
这题好难啊...
把奇数列盖住
(观察?)可得
偶数列 一个数 等于它上一列左边的加上它上一列右边的
别问我怎么观察出来的 我没有观察出来
推到偶数列
杨辉三角
最后判一判剩的是加号还是减号
搞一起就行了..
//By SiriusRen#include <bits/stdc++.h>using namespace std;const int N=200050,mod=1000000007;int n,a[N],ans1,ans2,tot,fac[N],inv[N];int C(int x,int y){return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}int pow(int x,int y){ int r=1; while(y){ if(y&1)r=1ll*r*x%mod; x=1ll*x*x%mod,y>>=1; }return r;}int main(){ scanf("%d",&n),fac[0]=1; for(int i=1;i<=n;i++)scanf("%d",&a[i]),tot+=i-1; for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod; for(int i=0;i<=n;i++)inv[i]=pow(fac[i],mod-2); if(n==1){printf("%d\n",a[1]);return 0;} if(n&1){ for(int i=0;i<n;i++)a[i]=i&1?(a[i]+a[i+1]):(a[i]-a[i+1]);n--; } for(int i=1;i<=n;i+=2)ans1=(ans1+1ll*a[i]*C(n/2-1,i/2))%mod; for(int i=2;i<=n;i+=2)ans2=(ans2+1ll*a[i]*C(n/2-1,i/2-1))%mod; printf("%d\n",((tot&1?(ans1+ans2)%mod:ans1-ans2)+mod)%mod);}
E
Karen and Supermarket
树形DP
f[x][j] x子树必须用优惠券 选了j个
g[x][j] x子树必须不用优惠券 选了j个
g[x]->g[x]
f[x]&g[x]->f[x]
//By SiriusRen#include <bits/stdc++.h>using namespace std;const int N=5050;int first[N],nxt[N],v[N],tot,c[N],d[N],fa[N],n,k,f[N][N],g[N][N],size[N],ans;void add(int x,int y){v[tot]=y,nxt[tot]=first[x],first[x]=tot++;}void dfs(int x){ f[x][0]=g[x][0]=0,size[x]=1;g[x][1]=c[x]; for(int i=first[x];~i;i=nxt[i]){ dfs(v[i]); for(int j=size[x];~j;j--){ for(int k=size[v[i]];~k;k--){ f[x][j+k]=min(f[x][j+k],f[x][j]+f[v[i]][k]); } } for(int j=size[x];~j;j--){ for(int k=size[v[i]];~k;k--){ g[x][j+k]=min(g[x][j+k],g[x][j]+g[v[i]][k]); } } size[x]+=size[v[i]]; } for(int i=size[x];i;i--)f[x][i]=min(g[x][i],f[x][i-1]+c[x]-d[x]);}int main(){ memset(first,-1,sizeof(first)); memset(f,0x3f,sizeof(f)); memset(g,0x3f,sizeof(g)); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d%d",&c[i],&d[i]); if(i!=1)scanf("%d",&fa[i]),add(fa[i],i); }dfs(1); for(int i=1;i<=n;i++)if(f[1][i]<=k)ans=i; printf("%d\n",ans);}
Div1 D
Karen and Cards
线段树 区间覆盖 区间求和...
按照a排序 那么从大到小 nowb>b[i]||nowc>c[i]
用总方案数减去不合法的
就是all-左下角的一块矩形
a变小的时候 就会有nowb>b[i]&&nowc>c[i]
就把一块都覆盖住就好了
x轴是b y轴是c 单调递减
//By SiriusRen#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=500050;typedef long long ll;int n,a,b,c,minn[N*8],maxx[N*8],lazy[N*8];ll sum[N*8],ans;struct Node{int x,y,z;}node[N];void setlazy(int num,int pos,int wei){sum[pos]=1ll*num*wei;maxx[pos]=minn[pos]=lazy[pos]=wei;}void push_down(int l,int r,int pos){ int mid=(l+r)>>1,lson=pos<<1,rson=lson|1; setlazy(mid-l+1,lson,lazy[pos]),setlazy(r-mid,rson,lazy[pos]); lazy[pos]=0;}void push_up(int pos){ int lson=pos<<1,rson=lson|1; sum[pos]=sum[lson]+sum[rson],minn[pos]=min(minn[lson],minn[rson]),maxx[pos]=max(maxx[lson],maxx[rson]);}void insert(int l,int r,int pos,int L,int R,int wei){ if(wei<=minn[pos])return; if(lazy[pos])push_down(l,r,pos); if(l>=L&&r<=R&&maxx[pos]<=wei){setlazy(r-l+1,pos,wei);return;} int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1; if(mid<L)insert(mid+1,r,rson,L,R,wei); else if(mid>=R)insert(l,mid,lson,L,R,wei); else insert(l,mid,lson,L,R,wei),insert(mid+1,r,rson,L,R,wei); push_up(pos);}bool cmp(Node a,Node b){return a.x>b.x;}int main(){ scanf("%d%d%d%d",&n,&a,&b,&c); for(int i=1;i<=n;i++){ scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].z); insert(1,b,1,1,node[i].y,node[i].z); }sort(node+1,node+1+n,cmp); for(int i=a,j=1;i;i--){ for(;j<=n&&node[j].x==i;j++)insert(1,b,1,1,node[j].y,c),insert(1,b,1,1,b,node[j].z); ans+=1ll*b*c-sum[1]; }printf("%I64d\n",ans);}
Div1 E 不会-> ->
Codeforces Round #419
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。