PKUSC 2014 #1
A:unix纪元
模拟
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 20101009 #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll n,cnt; int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int a1,a2,a3,a4,a5,a6,day=3600*24; void solve() { a3++; if(a2==2) { if(a3>d[a2]+(a1%4==0))a2++,a3=1; } else if(a3>d[a2])a2++,a3=1; if(a2==13)a1++,a2=1; } int main() { while(scanf("%lld",&n)!=EOF) { cnt=1; a1=1970;a2=1;a3=1;a4=a5=a6=0; while(n>=day)n-=day,solve(); a6=n%60;n/=60; a5=n%60;n/=60; a4=n%24; printf("%4d-%.2d-%.2d %.2d:%.2d:%.2d\n",a1,a2,a3,a4,a5,a6); } return 0; } |
B:连环锁
真心不会格雷码QAQ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n; int a[150],b[150]; struct data{ int l,v[105]; data(){ l=1;memset(v,0,sizeof(v)); } friend data operator+(data a,data b){ data c; c.l=max(a.l,b.l); for(int i=1;i<=c.l;i++) c.v[i]=a.v[i]+b.v[i]; for(int i=1;i<=c.l;i++) if(c.v[i]>=10) { c.v[i+1]+=c.v[i]/10,c.v[i]%=10; if(i==c.l)c.l++; } return c; } friend data operator-(data a,data b){ data c;c.l=a.l; for(int i=1;i<=c.l;i++) { c.v[i]+=a.v[i]-b.v[i]; if(c.v[i]<0)c.v[i]+=10,c.v[i+1]--; } while(c.l>1&&c.v[c.l]==0)c.l--; return c; } }bin[150]; void print(data a) { for(int i=a.l;i;i--) printf("%d",a.v[i]); } bool check() { for(int i=1;i<=n;i++) if(a[i]!=b[i])return a[i]<b[i]; return 0; } int main() { bin[0].v[1]=1; for(int i=1;i<=128;i++)bin[i]=bin[i-1]+bin[i-1]; T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)b[i]=read(); data ans1,ans2; for(int i=2;i<=n;i++)a[i]=a[i-1]^a[i]; for(int i=2;i<=n;i++)b[i]=b[i-1]^b[i]; if(check())swap(a,b); for(int i=1;i<=n;i++) { if(a[i])ans1=ans1+bin[n-i]; if(b[i])ans2=ans2+bin[n-i]; } print(ans1-ans2); puts(""); } return 0; } |
C:Zhu’s multiset
二分答案，得出每个数的增长开始时间
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 20101009 #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int a[5000005],b[5000005]; bool jud(int x) { for(int i=1;i<=n;i++)b[i]=x-a[i]; int l=1,r=0,tot=1,now=1; for(int T=0;T<=x;T++) { while(b[l]==T&&l<=n) { if(l>tot)return 0; l++,now--; } tot+=now; now+=now;if(tot>n)tot=n+1,now=n+1; } return 1; } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); sort(a+1,a+n+1,greater<int>()); int l=1,r=2000000; while(l<=r) { int mid=(l+r)>>1; if(jud(mid))r=mid-1; else l=mid+1; } printf("%d\n",l); return 0; } |
D:Team Them Up!
二分图染色+dp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 20101009 #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int cnt,n,top; int last[105],c[105],num[2]; int f[105][205],g[105][205]; bool mark[105]; pair<int,int> q[105]; vector<int> id[105][2]; struct edge{ int to,next; }e[20005]; vector<int> ans[2]; void print(int k,int x) { if(k==0)return ; int t=g[k][x]; for(int i=0;i<2;i++) for(int j=0;j<id[k][i].size();j++) ans[i^t].push_back(id[k][i][j]); print(k-1,x+id[k][t].size()-id[k][t^1].size()); } bool dfs(int x,int f) { num[f]++;c[x]=f; id[top][f].push_back(x); for(int i=last[x];i;i=e[i].next) if(c[e[i].to]==f)return 0; else if(c[e[i].to]==-1) { if(!dfs(e[i].to,f^1))return 0; } return 1; } void insert(int u,int v) { e[++cnt]=(edge){v,last[u]};last[u]=cnt; e[++cnt]=(edge){u,last[v]};last[v]=cnt; } int main() { n=read(); memset(c,-1,sizeof(c)); for(int i=1;i<=n;i++) { memset(mark,0,sizeof(mark)); int x=read(); while(x!=0) { mark[x]=1; x=read(); } for(int j=1;j<=n;j++) if(i!=j&&!mark[j])insert(i,j); } for(int i=1;i<=n;i++) if(c[i]==-1) { num[0]=num[1]=0; top++; if(!dfs(i,0)){puts("No solution");return 0;} q[top]=make_pair(num[0],num[1]); } f[0][100]=1; for(int i=0;i<top;i++) for(int j=0;j<=200;j++) if(f[i][j]) { int t1=q[i+1].first,t2=q[i+1].second; f[i+1][j+t1-t2]=1; f[i+1][j+t2-t1]=1; g[i+1][j+t1-t2]=1; g[i+1][j+t2-t1]=0; } for(int i=0;i<=100;i++) if(f[top][100-i]){print(top,i+100);break;} printf("%lu ",ans[0].size());for(int i=0;i<ans[0].size();i++)printf("%d ",ans[0][i]);puts(""); printf("%lu ",ans[1].size());for(int i=0;i<ans[1].size();i++)printf("%d ",ans[1][i]); return 0; } |
F.Boatherds
傻逼点分治
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt,sum,rt; int last[10005],size[10005],d[10005],f[10005],q[105]; bool vis[10005],mark[105]; struct edge{ int to,next,v; }e[20005]; vector<int>tmp; set<int>st; void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],w};last[v]=cnt; } void getrt(int x,int fa) { size[x]=1;f[x]=0; for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]&&e[i].to!=fa) { getrt(e[i].to,x); size[x]+=size[e[i].to]; f[x]=max(f[x],size[e[i].to]); } f[x]=max(f[x],sum-size[x]); if(f[x]<f[rt])rt=x; } void getdp(int x,int fa) { tmp.push_back(d[x]); for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]&&e[i].to!=fa) { d[e[i].to]=d[x]+e[i].v; getdp(e[i].to,x); } } void solve(int x) { vis[x]=1; st.clear(); for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { tmp.clear(); d[e[i].to]=e[i].v; getdp(e[i].to,x); for(int j=0;j<tmp.size();j++) for(int k=1;k<=m;k++) if(!mark[k]&&q[k]>=tmp[j]) { if(q[k]==tmp[j])mark[k]=1; else mark[k]=st.find(q[k]-tmp[j])!=st.end(); } for(int j=0;j<tmp.size();j++) st.insert(tmp[j]); } for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { sum=size[e[i].to];rt=0; getrt(e[i].to,x); solve(rt); } } int main() { while(1) { n=read(); if(n==0)return 0; cnt=0;memset(last,0,sizeof(last)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { int x=read(),v; while(x!=0) { v=read(); insert(i,x,v); x=read(); } } m=0; int x=read(); while(x!=0) { q[++m]=x; x=read(); } memset(mark,0,sizeof(mark)); rt=0;sum=n;f[0]=inf; getrt(1,0); solve(rt); for(int i=1;i<=m;i++) if(mark[i])puts("AYE"); else puts("NAY"); puts("."); } return 0; } |
计数器 9854486
OI 课件=>
OI 课件=>
貌似百练那个并不能交题啊。。而且搜题号也不对。。
同求+1
http://bailian.openjudge.cn/contests/past
黄学长，pkusc的题去哪测