codeforces#395

2019-11-10 20:28:30

字体：大中小

来源：转载

供稿：网友

A：

题意：

没a分钟来个人，每b分钟一个liza打电话，在c时间内，最少多少个人不能来使得没人接liza电话

tip：

暴力

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;int a[10010];void init(){ int n,m,p,cnt=0,ans = 0; scanf("%d%d%d",&n,&m,&p); for(int i = 1; ;i++){ if(n*i>p) break; a[++cnt] = n*i; } int now = 1; for(int i = 1 ;;i++){ int mm = m*i; if(m*i >p ) break; for(int j = 1; j <= cnt ;j++) if(a[j] == mm){ ans++; break; } } PRintf("%d/n",ans);}int main(){ init(); return 0;

B题：

题意：

把整个字符串调换，每次调换完，被调换部分最外面的左右两个不再动，直到没得调换，问最后的样子，

tip：

奇数换，偶数不换

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;int n;int a[200010];void init(){ scanf("%d",&n); for(int i = 1 ; i <= n ; i++) scanf("%d",&a[i]); for(int i = 1; i <= n/2;i++){ if(i %2 == 1) swap(a[i],a[n-i+1]); } for(int i = 1 ;i <= n ; i++) printf("%d%c",a[i],i == n?'/n':' ');}int main(){ init(); return 0;}

C：

题意：

给一棵树，每个节点有一个颜色，除了根以为，这个树，所有子树各自满足：所有节点颜色都相同就是合法的，问是否能找到一个节点作为跟，满足上述条件

tip：

当一条边连接的两个节点颜色不同时，那两个节点必定有一个要作为跟，不然一定不满足条件，于是分别检查这两个点作为跟是否合法就好了，dfs时候，一个节点的子树不符合就return 0，否则除了根以外，每个节点的所有子树颜色也要相同（检查直接儿子就可以了）且和自己节点颜色相同。

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>const int maxn = 1e6+10;int ans,c[maxn],head[maxn],tot,n,cnt;using namespace std;struct node{ int u,v,next;}edges[maxn];void add(int u,int v){ edges[tot].v = v;edges[tot].u = u;edges[tot].next = head[u];head[u] = tot++; edges[tot].v = u;edges[tot].u = v;edges[tot].next = head[v];head[v] = tot++;}int dfs(int hea,int now ,int fa){ bool flag = false,ff = false; int pre; for(int k = head[now] ; k!= -1 ; k = edges[k].next){ if(edges[k].v == fa) continue; flag = true; if(!dfs(hea,edges[k].v,now)){ // cout << " "<<edges[k].v<<endl; return 0; } if(!ff){ ff = true; pre = c[edges[k].v]; } else if(c[edges[k].v]!=pre&&now !=hea) return 0; } //cout <<"now = "<<now<<"flag = "<<flag<<endl; if(!flag) return 1; if(now !=hea && c[now]!=pre) return 0; return 1;}void init(){ scanf("%d",&n); tot=cnt = 0; memset(head,-1,sizeof(head)); for(int i = 1; i < n ; i++){ int u,v; scanf("%d%d",&u,&v); add(u,v); } for(int i = 1; i <= n ; i++){ scanf("%d",&c[i]); } for(int i = 0; i < tot ;i++){ if(c[edges[i].u]!=c[edges[i].v]){ int an1 = dfs(edges[i].u,edges[i].u,0); int an2 = dfs(edges[i].v,edges[i].v,0); if(an1 != 1 && an2 != 1){ printf("NO/n");return ; } else if(an1 ==1){ printf("YES/n%d/n",edges[i].u); return; } else{ printf("YES/n%d/n",edges[i].v); return; } } } printf("YES/n1/n");}int main(){ init(); return 0;}

D题：

题意：

给n个长方形，每个长方形给左下和右上坐标，且每个矩形的长宽都是奇数。问是否能用四种颜色使得相连的矩形颜色不同

tip：

一定是可以的，因为边长是奇数，那么就不存在5个相连，在考虑，如果一个矩形左下角的点x是奇数，那么和她左右相切的矩形x一定是偶数，如果y是偶数，那么和她上下相切的矩形y一定是奇数，有了这个关系，一个矩形最多和四个相切，x奇偶性相反或者y相反或者都相反的分别用4种颜色就好了

#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;int x,y,a,b,n;void init(){ scanf("%d",&n); puts("YES"); for(int i=1;i<=n;i++){ scanf("%d%d%d%d",&x,&y,&a,&b); printf("%d/n",2*abs(x%2)+abs(y%2)+1); }}int main(){ init(); return 0;}

上一篇：@Param注解的用法解析

下一篇：Leetcode 191. Number of 1 Bits