首页 > 代码库 > Codeforces Round #395 (Div. 2)（未完）
Codeforces Round #395 (Div. 2)（未完）
2.2.2017 9:35~11:35
A - Taymyr is calling you
直接模拟
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=1e4+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,m,z,ans;int vis[N];int main(int argc, const char * argv[]) { n=read();m=read();z=read(); for(int i=n;i<=z;i+=n) vis[i]=1; for(int i=m;i<=z;i+=m) ans+=vis[i]; printf("%d",ans); return 0;}
B - Timofey and cubes
奇数位置反转，偶数位置不变
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=2e5+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,a[N];int main(int argc, const char * argv[]) { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n/2;i++) if(i&1) swap(a[i],a[n-i+1]); for(int i=1;i<=n;i++) printf("%d ",a[i]); return 0;}
C - Timofey and a tree
题意：选一个根使得所有子树同色(每个子树中节点同色 不同子树可以不同色)
比赛时先打了个傻逼树形DP发现不对 然后就用对于一个点i它的子树用树形DP，它的上面的树用DFS序+线段树/ST表询问颜色相同......反正A掉了
//// main.cpp// C//// Created by Candy on 2017/2/2.// Copyright © 2017年 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;#define mid ((l+r)>>1)#define lson x<<1,l,mid#define rson x<<1|1,mid+1,r#define lc x<<1#define rc x<<1|1typedef long long ll;const int N=2e5+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,u,v,c[N],a[N];struct edge{ int v,ne;}e[N<<1];int h[N],cnt=0;inline void ins(int u,int v){ cnt++; e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;}struct node{ int same;}t[N<<2];void build(int x,int l,int r){ if(l==r) t[x].same=a[l]; else{ build(lson); build(rson); if(t[lc].same==0||t[rc].same==0||t[lc].same!=t[rc].same) t[x].same=0; else t[x].same=t[lc].same; }}int segSame(int x,int l,int r,int ql,int qr){ if(ql>qr) return -1; if(t[x].same) return t[x].same; if(ql<=l&&r<=qr) return t[x].same; else{ int same=-1; if(ql<=mid) same=segSame(lson,ql,qr); if(mid<qr){ int _=segSame(rson,ql,qr); if(same==-1||same==_) same=_; else same=0; } return same; }}int d[N],L[N],R[N],dfc;void dfs(int u,int fa){ L[u]=++dfc; a[dfc]=c[u]; d[u]=c[u]; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(v==fa) continue; dfs(v,u); if(d[u]!=0&&d[v]!=d[u]) d[u]=0; } R[u]=dfc;}int ans;void dfsSol(int u,int fa){//printf("dfsSol %d %d\n",u,fa); if(ans) return; int flag=1; for(int i=h[u];i;i=e[i].ne) if(e[i].v!=fa) if(d[e[i].v]==0) {flag=0;break;} if(flag){ int s1=segSame(1,1,n,1,L[u]-1),s2=segSame(1,1,n,R[u]+1,n); flag=0; if(s1!=0&&s2!=0&&(s1==-1||s2==-1||s1==s2)) flag=1;// printf("hi %d %d %d %d %d %d\n",u,L[u],R[u],s1,s2,flag); if(flag) {ans=u;return;} } for(int i=h[u];i;i=e[i].ne) if(e[i].v!=fa) dfsSol(e[i].v,u);}int main(int argc, const char * argv[]) { n=read(); for(int i=1;i<=n-1;i++) u=read(),v=read(),ins(u,v); for(int i=1;i<=n;i++) c[i]=read(); dfs(1,0); build(1,1,n);// for(int i=1;i<=n;i++) printf("hi %d %d %d %d\n",i,d[i],L[i],R[i]);// for(int i=1;i<=n;i++) printf("a %d %d\n",i,a[i]); dfsSol(1,0); if(ans) printf("YES\n%d",ans); else puts("NO"); return 0;}
实际上可以发现如果一条边两边节点的颜色不对一定是这两个节点中的一个做根，三遍DFS就行了....好简单
dfsD - Timofey and rectangles
题意：一些不相交矩形边长都是奇数 4种颜色染色 判断可行及一种方案
....最后才看到洛谷群有这道题题解然后最后10s提交失败呜呜呜
超简单 边长奇数，所以横边相邻的矩形y坐标奇偶性不同 x同理 所以按左下角奇偶性染色就行了
//// main.cpp// C//// Created by Candy on 2017/2/2.// Copyright © 2017年 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,x,y;int main(int argc, const char * argv[]) { n=read(); puts("YES"); for(int i=1;i<=n;i++){ x=read();y=read(); x=min(x,read());y=min(y,read()); x+=1e9;y+=1e9; if(x&1){ if(y&1) puts("1"); else puts("2"); }else{ if(y&1) puts("3"); else puts("4"); } }}
未完
Codeforces Round #395 (Div. 2)（未完）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。