2016-11-14试题解题报告
By shenben
T1：
30%: O(n ^ 2 * m)暴力判断。
100%: 很显然答案的可能性最多只有n种，所以我们将所有人的答案按字典序排序后枚举。将每个人的答案作为正确答案来进行判断。
由于是判断题，若当前人的答案为正确答案则零分者的答案也就确定了，那么只需统计出这两种答案的人数判断是否满足题意，即可。这一步使用字符串哈希即可解决。
T2:
30%：枚举每个数所在的集合或者不选，然后判定即可。复杂度O(n*3^n)。
60%： Dp，两个数相等就相当于两个数的xor为0。设 f[i][j][k=0..2]代表 处理到第 I 个数， 如果 k = 1代表and值为j,如果k = 2代表xor 值为 j,如果k = 0则代表一个元素都没 取。所以很容易得到方程：
f[i][j][0] = f[i + 1][j][0]
f[i][j & ai][1] = f[i + 1][j][1] + f[i + 1][j][0] + f[i + 1][j & ai][1]
f[i][j ^ ai][2] = f[i + 1][j][1] + f[i + 1][j][2] + f[i + 1][j ^ ai][2];
最后f[1][0][2]就是答案, 复杂度为O(n * 1024 * 3)
DP还可以分开用f[i][j]和g[i][j]表示前i个xor值为j，后i个and值为j的方案数， 随后枚举分界点k来求总方案数。复杂度O(n * 1024 * 3)。
100%：满分数据需要高精，答案位数较大，需要进行压位来防止TLE，因为不知道答案的 位数究竟多大，压位后高精数组仍需要开的较大一些，所以原DP的数组滚动即可。
T3：
30%：
当T<= 10000的时候，可以设 vis[i][j] 代表到达第i个点时间为j是否合法。 这样是O(T*m)，可以拿到小数据。
另外的那30%：各种奇怪的骗分方法。选手自行考虑。
100%：
当T很大的时候，我们考虑 如果0 -> x -> n - 1路径时间为T，且 从x出发有一个时间为d的环，则 一定存在一个K满足 K + p*d = T（至少T满足条件），这样我们就能绕着环走p次就能构成一条时间为T的路径。
显然要求的路径一定经过 0，而且在合法情况下从0号点出发一定存在一条边，否则0号点和n - 1号就是不联通的。随便取一条边时间为d, 则能构成从0号点出发的一个时间为2d的环。这样原题就化为最短路问题了，dis[i][j] 代表到达i号点，时间为 j + p * 2d，最小的 j+p*2d，
最后判断dis[n -1][T % 2d] 是否小于等于T即可。
实际上就是在30%的基础上缩减状态。
时间复杂度为O(m*d)。
T1代码：
#include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<ctime> #include<algorithm> #include<iostream> #include<vector> #include<stack> #include<queue> #include<map> using namespace std; #define ll long long #define R register #define debug(x) cout<<x<<"---"<<endl inline int read(){ R int x=0;bool f=1; R char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return f?x:-x; } const int N=30000+5; const int M=3000+5; string s[N]; map<string,int>ys; string s1,t; int n,m,p,q; int cnt,ans; char ss[M]; int judge(string &std,string &now){ int res=0; for(int i=0;i<m;i++) if(std[i]!=now[i]) res++; return res; } void fanzhuan(){ for(int slen=s1.length(),i=0;i<slen;i++){ s1[i]=(s1[i]=='N'?'Y':'N'); } printf("%s",s1.c_str()); } void sp(int x){ if(x==m){ int j,t; for(j=1;j<=cnt;j++){ if(s[j]==s1) break; t=judge(s1,s[j]); if(t==m) break; } if(j>cnt){for(int i=0;i<m;i++) putchar(s1[i]);exit(0);} return ; } for(int i=0;i<2;i++){ s1[x]=(!i?'N':'Y'); sp(x+1); } } void in(){ char ch;int l=0; for(ch=getchar();l<m;ch=getchar()){ if(ch!='\n') ss[l++]=ch; else break; } ss[l]='\0'; } void work(){ int flag=0; for(int i=0;i<m;i++) t+='N'; for(int i=1;i<=n;i++){ for(int j=0;j<m;j++){ if(s[i][j]=='Y')t[j]='N'; if(s[i][j]=='N')t[j]='Y'; } int sum=ys[s[i]],tot=ys[t]; if(sum==p&&tot==q){ flag=i; break; } } if(flag) printf("%s",s[flag].c_str()); else puts("-1"); } #define name "answer" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); n=read();m=read();p=read();q=read(); for(int i=1;i<=n;i++){ in(); for(int j=0;j<m;j++) s[i]+=ss[j]; ys[s[i]]++; } sort(s+1,s+n+1); cnt=unique(s+1,s+n+1)-(s+1); if(!p&&!q){ sp(0); return 0; } if(p){work();return 0;} /*if(p!=0){ for(int i=1;i<=cnt;i++){ if(ys[s[i]]!=p) continue; ans=0; for(int j=1,t;j<=cnt;j++){ if(i==j) continue; t=judge(s[i],s[j]); if(t==m) ans+=ys[s[j]]; } if(ans==q){ printf("%s",s[i].c_str()); return 0; } } }*/ else if(q){ for(int i=1;i<=cnt;i++){ if(ys[s[i]]!=q) continue; ans=0; for(int j=1,t;j<=cnt;j++){ if(i==j) continue; t=judge(s[i],s[j]); if(t==m) ans+=ys[s[j]]; } if(ans==p){ s1=s[i]; fanzhuan(); return 0; } } } else puts("-1"); fclose(stdin); fclose(stdout); return 0; } /*50分代码存档 #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<ctime> #include<algorithm> #include<iostream> #include<vector> #include<stack> #include<queue> #include<map> using namespace std; #define ll long long #define R register #define debug(x) cout<<x<<"---"<<endl inline int read(){ R int x=0;bool f=1; R char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return f?x:-x; } inline char in(){ for(R char ch=getchar();;ch=getchar()) if((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')) return ch; } const int N=30000+5; string s[N]; map<string,int>ys; string s1; int n,m,p,q,num,nt,nf; bool f1; void fanzhuan(){ for(int slen=s1.length(),i=0;i<slen;i++){ s1[i]=(s1[i]=='N'?'Y':'N'); } printf("%s",s1.c_str()); } #define name "answer" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); n=read();m=read();p=read();q=read(); for(int i=1;i<=n;i++){ getline(cin,s[i]); ys[s[i]]++; } sort(s+1,s+n+1); int cnt=unique(s+1,s+n+1)-(s+1); if(p==q){puts("-1");return 0;} if(p<2&&q<2&&p+q<n){puts("-1");return 0;} int zmx=0; for(int i=1;i<=cnt;i++){ if(zmx<ys[s[i]]){ zmx=ys[s[i]]; s1=s[i]; } } for(int i=1;i<=cnt;i++){ if(zmx==ys[s[i]]){ if(s1!=s[i]){f1=1;break;} } } if(zmx==p&&f1){ num=0; for(int i=1;i<=cnt;i++){ if(ys[s[i]]==q){ num++; s1=s[i]; } } if(num!=1){puts("-1");return 0;} else{fanzhuan();return 0;} } if(zmx==q&&f1){ num=0; for(int i=1;i<=cnt;i++){ if(ys[s[i]]==p){ num++; s1=s[i]; } } if(num!=1){puts("-1");return 0;} else{printf("%s",s1.c_str());return 0;} } for(int i=1;i<=cnt;i++){ if(ys[s[i]]==p){ nt++; s1=s[i]; } } if(nt==1){printf("%s",s1.c_str());return 0;} for(int i=1;i<=cnt;i++){ if(ys[s[i]]==q){ nf++; s1=s[i]; } } if(nf==1){fanzhuan();return 0;} else{puts("-1");return 0;} if(zmx!=p&&zmx!=q){puts("-1");return 0;} if(p>q) printf("%s",s1.c_str()); else fanzhuan(); fclose(stdin); fclose(stdout); return 0; } */
T2代码：
来自std
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; const int N = 1001, M = 1024, W = 1e9; int n, cur, nxt, va, vx, p[N]; struct huge_int { int len, a[40]; huge_int(): len(1) { memset(a, 0, sizeof(a)); } inline void operator += (const huge_int &b) { b.len > len ? len = b.len : 0; for (int i = 1; i <= len; ++i) { a[i] += b.a[i]; if (a[i] >= W) ++a[i + 1], a[i] -= W; } if (a[len + 1]) ++len; return ; } inline void print() { printf("%d", a[len]); for (int i = len - 1; i; --i) printf("%09d", a[i]); puts(""); return ; } } f[2][M][3]; char ch; int read() { while (ch = getchar(), ch < '0' || ch > '9'); int res = ch - 48; while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48; return res; } int main() { freopen("sequence.in", "r", stdin); freopen("sequence.out", "w", stdout); n = read(); for (int i = n; i; --i) p[i] = read(); f[0][1023][0].a[1] = 1; for (int i = 0; i < n; ++i) { nxt = cur ^ 1; for (int j = 0; j < M; ++j) for (int k = 0; k <= 2; ++k) f[nxt][j][k] = f[cur][j][k]; for (int j = 0; j < M; ++j) { va = p[i + 1] & j, vx = p[i + 1] ^ j; f[nxt][va][1] += f[cur][j][0]; f[nxt][va][1] += f[cur][j][1]; f[nxt][vx][2] += f[cur][j][1]; f[nxt][vx][2] += f[cur][j][2]; } cur ^= 1; } f[cur][0][2].print(); fclose(stdin); fclose(stdout); return 0; }
/*30分暴力 来自sjt #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define R register using namespace std; const int N=1010; int n,a[N],x[N],y[N],ans=0; inline int read(){ R int x=0;bool f=1; R char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return f?x:-x; } void panduan(int l1,int l2){ int ss=a[x[1]],sss=a[y[1]]; for(int i=2;i<=l1;i++) ss^=a[x[i]]; for(int i=2;i<=l2;i++) sss&=a[y[i]]; if(ss==sss) ans++; } void dfs_j(int d[],int k,int l,int r,int l1,int l2){ if(k>l2){panduan(l1,l2);return;} for(int i=l;i<=r;i++){ d[k]=i; dfs_j(d,k+1,i+1,r,l1,l2); } } void dfs_i(int d[],int k,int l,int r,int l1,int l2){ if(k>l1){//搜索S数组完成，搜索J数组 dfs_j(y,1,l,r,l1,l2); return; } for(int i=l;i<=r;i++){ d[k]=i; dfs_i(d,k+1,i+1,r,l1,l2); } } int main(){ freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++){ for(int j=1;j<=n-i;j++){ dfs_i(x,1,1,n,i,j); } } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; } */
T3代码：
#include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<ctime> #include<algorithm> #include<iostream> #include<vector> #include<stack> #include<queue> #include<map> using namespace std; #define ll long long #define R register #define pir pair<int,int> #define debug(x) cout<<x<<"---"<<endl inline int read(){ R int x=0;bool f=1; R char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return f?x:-x; } inline ll Read(){ R ll x=0;bool f=1; R char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return f?x:-x; } inline char in(){ for(R char ch=getchar();;ch=getchar()) if((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')) return ch; } const int N=51; const int M=201; const int K=20001; struct node{ int u,v,w,next; }e[M<<1]; int n,m,cas,len,tot,head[M]; ll T,dis1[N][K]; bool vis[N][K]; void add(int x,int y,int z){ e[++tot].u=x; e[tot].v=y; e[tot].w=z; e[tot].next=head[x]; head[x]=tot; } void spfa(int S){ memset(dis1,127/3,sizeof dis1); memset(vis,0,sizeof vis); dis1[S][0]=0; vis[S][0]=1; queue<pir>q; q.push(make_pair(S,0)); while(!q.empty()){ pir t=q.front();q.pop(); int x=t.first; int p=t.second; vis[x][p]=0; for(int i=head[x];i;i=e[i].next){ int v=e[i].v; ll w=dis1[x][p]+e[i].w; int c=w%len; if(dis1[v][c]>w){ dis1[v][c]=w; if(!vis[v][c]){ vis[v][c]=1; q.push(make_pair(v,c)); } } } } } void Cl(){ tot=0; memset(head,0,sizeof head); } void work(){ Cl(); n=read();m=read();T=Read(); for(int i=1,x,y,z;i<=m;i++){ x=read();y=read();z=read(); add(x,y,z);add(y,x,z); } if(!head[0]) puts("Impossible"); else{ len=10001; for(int i=head[0];i;i=e[i].next){ len=min(len,e[i].w); } len<<=1; spfa(0); if(dis1[n-1][T%len]<=T) puts("Possible"); else puts("Impossible"); } } #define name "travel" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); cas=read(); while(cas--) work(); fclose(stdin); fclose(stdout); return 0; }