Codeforces Round #345 (Div. 2)

2019-04-14 20:00发布

站内文章 / 模拟电子
14039 0 904

链接：http://codeforces.com/contest/651

A. Joysticks

题意：两个游戏手柄一个充电器，每次只能冲一个手柄，再冲电的每分钟涨1%，没冲的掉2%，两个都到%1以下游戏结束，问什么时候结束。
分析：哪个的电量低哪个就冲电。 代码： #include #include #include #include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f #define Mn 50010 #define Mm 2000005 #define mod 1000000007 #define CLR(a,b) memset((a),(b),sizeof((a))) #define CPY(a,b) memcpy ((a), (b), sizeof((a))) #pragma comment(linker, "/STACK:102400000,102400000") #define ul u<<1 #define ur (u<<1)|1 using namespace std; typedef long long ll; int read() { char c=getchar(); int re=0,f=1; while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {re=re*10+c-'0';c=getchar();} return re; } int main() { int n=read(),m=read(); int a,b; int num=0; while(1) { if(n>m) { n-=2; if(n<0||m==0) break; m++; } else { m-=2; if(m<0||n==0) break; n++; } num++; } cout< B. Beautiful Paintings

题意：一个序列中的元素前一个小于后一个，答案加1，求随意摆放后答案最大。。
分析：记录每个数的个数，然后离散化，这时计算每个数对后面的贡献。

#include #include #include #include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f #define Mn 1010 #define Mm 2000005 #define mod 1000000007 #define CLR(a,b) memset((a),(b),sizeof((a))) #define CPY(a,b) memcpy ((a), (b), sizeof((a))) #pragma comment(linker, "/STACK:102400000,102400000") #define ul u<<1 #define ur (u<<1)|1 using namespace std; typedef long long ll; int read() { char c=getchar(); int re=0,f=1; while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {re=re*10+c-'0';c=getchar();} return re; } int num[Mn]; int a[Mn]; int main() { int n=read(); for(int i=0;i=a[j]) { sum+=a[j]; a[j]=0; } else sum+=a[i],a[j]-=a[i]; } } cout<
C. Watchmen
题意：求二维坐标中满足 |xi - xj| + |yi - yj|=.的点对个数。
分析：用map分别记录在同一横坐标，同一纵坐标，重点个数，用组合数求出在减去重复的。 #include #include #include #include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f #define Mn 1010 #define Mm 2000005 #define mod 1000000007 #define CLR(a,b) memset((a),(b),sizeof((a))) #define CPY(a,b) memcpy ((a), (b), sizeof((a))) #pragma comment(linker, "/STACK:102400000,102400000") #define ul u<<1 #define ur (u<<1)|1 using namespace std; typedef long long ll; int read() { char c=getchar(); int re=0,f=1; while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {re=re*10+c-'0';c=getchar();} return re*f; } map mp1,mp2; map,int>mp3; int main() { int n=read(); for(int i=0;i
D. Image Preview
题意：手机看照片，w为横放，h为竖放，对于没看过的照片要先用1秒看是w还是h，如果是w，就必须花费b秒变成h，照片切换要花费a秒。看过的照片不需要看的时间个转换时间。不能跳过没看的照片。 分析：先预处理出从一边开始到极限经过的每张照片花费时间。然后每次回退这一边的点，将多出来的时间用到另一边，因为回退过程中，多出来时将总是增加的，是所以另一边可以在上次回退的基础上继续走。时间复杂度o(n). #include #include #include #include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f #define Mn 500005 #define Mm 2000005 #define mod 1000000007 #define CLR(a,b) memset((a),(b),sizeof((a))) #define CPY(a,b) memcpy ((a), (b), sizeof((a))) #pragma comment(linker, "/STACK:102400000,102400000") #define ul u<<1 #define ur (u<<1)|1 using namespace std; typedef long long ll; int read() { char c=getchar(); int re=0,f=1; while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {re=re*10+c-'0';c=getchar();} return re*f; } int th[Mn]; int n,a,b,t; int get(string &s) { int lnum=0,lnt=0,rnum=0,rnt=0; for(int i=0;it) break; lnum++;th[i]=lnt;lnt+=a; } int nowpos=n-1,maxx=lnum; for(int i=lnum-1;i>=0;i--) { int rt=t-th[i]-(i+1)*a; while(1) { int tmp=rnt; if(s[nowpos]=='h') rnt+=1; else rnt+=b+1; if(rnt>rt) {rnt=tmp;break;} rnum++; rnt+=a;nowpos--; if(nowpos==0) break; } maxx=max(maxx,lnum+rnum); if(maxx>=n) { maxx=n; break; } lnum--; } return maxx; } int main() { n=read(),a=read(),b=read(),t=read(); string s,x; cin>>s; x=s; reverse(x.begin(), x.end()); x=s[0]+x; int ans=max(get(s),get(x)); cout<

E. Table Compression 题意：将a矩阵转换成另一个矩阵b。要求每行每列不改变相对大小顺序，且每行每列相等的转换后还是相等。 分析：将每行每列相等的点连边，将原值排序后，从小到大求出这些点可在各自的行列可行的最大值，然后得到答案，更新行列值。 代码： #include #include #include #include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f #define Mn 1000010 #define Mm 2000005 #define mod 1000000007 #define CLR(a,b) memset((a),(b),sizeof((a))) #define CPY(a,b) memcpy ((a), (b), sizeof((a))) #pragma comment(linker, "/STACK:102400000,102400000") #define ul u<<1 #define ur (u<<1)|1 using namespace std; typedef long long ll; int read() { char c=getchar(); int re=0,f=1; while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {re=re*10+c-'0';c=getchar();} return re*f; } int h[Mn],w[Mn],vis[Mn],ans[Mn]; struct edge { int next,v; }e[4*Mn]; struct node{ int pos,va; }a[Mn],b[Mn],c[Mn]; bool cmp(node x,node y) { return x.va vt; void dfs(int u) { vt.push_back(u);vis[u]=1; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(vis[v]) continue; dfs(v); } } int main() { int n=read(),m=read(); CLR(head,-1); for(int i=0;i



热门文章