codeforces#395

2019-11-10 20:52:09

字體：大中小

來(lái)源：轉(zhuǎn)載

供稿：網(wǎng)友

A：

題意：

沒(méi)a分鐘來(lái)個(gè)人，每b分鐘一個(gè)liza打電話，在c時(shí)間內(nèi)，最少多少個(gè)人不能來(lái)使得沒(méi)人接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; } } B題：

題意：

把整個(gè)字符串調(diào)換，每次調(diào)換完，被調(diào)換部分最外面的左右兩個(gè)不再動(dòng)，直到?jīng)]得調(diào)換，問(wèn)最后的樣子，

tip：

奇數(shù)換，偶數(shù)不換

#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：

題意：

給一棵樹(shù)，每個(gè)節(jié)點(diǎn)有一個(gè)顏色，除了根以為，這個(gè)樹(shù)，所有子樹(shù)各自滿足：所有節(jié)點(diǎn)顏色都相同就是合法的，問(wèn)是否能找到一個(gè)節(jié)點(diǎn)作為跟，滿足上述條件

tip：

當(dāng)一條邊連接的兩個(gè)節(jié)點(diǎn)顏色不同時(shí)，那兩個(gè)節(jié)點(diǎn)必定有一個(gè)要作為跟，不然一定不滿足條件，于是分別檢查這兩個(gè)點(diǎn)作為跟是否合法就好了，dfs時(shí)候，一個(gè)節(jié)點(diǎn)的子樹(shù)不符合就return 0，否則除了根以外，每個(gè)節(jié)點(diǎn)的所有子樹(shù)顏色也要相同（檢查直接兒子就可以了）且和自己節(jié)點(diǎn)顏色相同。

#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個(gè)長(zhǎng)方形，每個(gè)長(zhǎng)方形給左下和右上坐標(biāo)，且每個(gè)矩形的長(zhǎng)寬都是奇數(shù)。問(wèn)是否能用四種顏色使得相連的矩形顏色不同

tip：

一定是可以的，因?yàn)檫呴L(zhǎng)是奇數(shù)，那么就不存在5個(gè)相連，在考慮，如果一個(gè)矩形左下角的點(diǎn)x是奇數(shù)，那么和她左右相切的矩形x一定是偶數(shù)，如果y是偶數(shù)，那么和她上下相切的矩形y一定是奇數(shù)，有了這個(gè)關(guān)系，一個(gè)矩形最多和四個(gè)相切，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;}