首页 > 代码库 > 9.5noip模拟试题
9.5noip模拟试题
题目名称 | 正确答案 | 序列问题 | 长途旅行 |
英文名称 | answer | sequence | travel |
输入文件名 | answer.in | sequence.in | travel.in |
输出文件名 | answer.out | sequence.out | travel.out |
时间限制 | 1s | 1s | 1s |
空间限制 | 256M | 256M | 256M |
测试点数目 | 20 | 20 | 10 |
测试点分值 | 5 | 5 | 10 |
是否有部分分 | 无 | 无 | 无 |
题目类型 | 传统 | 传统 | 传统 |
是否有SPJ | 无 | 无 | 无 |
1.正确答案
【题目描述】
小H与小Y刚刚参加完UOIP外卡组的初赛，就迫不及待的跑出考场对答案。
“吔，我的答案和你都不一样！”，小Y说道，”我们去找神犇们问答案吧”。
外卡组试卷中共有m道判断题，小H与小Y一共从其他n个神犇那问了答案。之后又从小G那里得知，这n个神犇中有p个考了满分，q个考了零分，其他神犇不为满分或零分。这可让小Y与小H犯了难。你能帮助他们还原出标准答案吗？如有多解则输出字典序最小的那个。无解输出-1。
【输入格式】
第一行四个整数n, m, p, q，意义如上描述。
接下来n行，每一行m个字符’N’或’Y’，表示这题这个神犇的答案。
【输出格式】
仅一行，一个长度为m的字符串或是-1。
【样例输入】
2 2 2 0
YY
YY
【样例输出】
YY
【数据范围】
30% : n <= 100.
60% : n <= 5000 , m <= 100.
100% : 1 <= n <= 30000 , 1 <= m<= 500. 0 <= p , q 且 p + q <= n.
暴力50：
/*自己还是太弱~没看出来要用hash 只是觉得自己的作法慢~QAQ50分暴力 先排序 一样的缩成一种 然后枚举正确答案是哪个q==0 p==0的情况没考虑到~ */#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 30010#define maxm 510using namespace std;int n,m,p,q,cnt;string g[maxn];struct node{ int len; string s;}k[maxn];int cmp(int a[maxm],int b[maxm]){ for(int i=1;i<=m;i++){ if(a[i]<b[i])return 1; if(a[i]>b[i])return 0; } return 1;}int main(){ freopen("answer.in","r",stdin); freopen("answer.out","w",stdout); scanf("%d%d%d%d",&n,&m,&p,&q); for(int i=1;i<=n;i++)cin>>g[i]; sort(g+1,g+1+n); int l=1,r; for(r=2;r<=n;r++){ if(g[r]==g[l])continue; k[++cnt].s=g[l]; k[cnt].len=r-l;l=r; } k[++cnt].s=g[l]; k[cnt].len=r-l; int falg=0; for(int i=1;i<=cnt;i++){ if(k[i].len!=p)continue; int sum=0; string x;x.clear(); for(int j=0;j<m;j++) if(k[i].s[j]==‘Y‘)x+=‘N‘; else x+=‘Y‘; for(int j=1;j<=cnt;j++) if(k[j].s==x){ sum+=k[j].len; break; } if(sum==q){ cout<<k[i].s; falg=1;break; } } if(falg==0) for(int i=1;i<=cnt;i++){ if(k[i].len!=q)continue; int sum=0; string x;x.clear(); for(int j=0;j<m;j++) if(k[i].s[j]==‘Y‘)x+=‘N‘; else x+=‘Y‘; for(int j=1;j<=cnt;j++) if(k[j].s==x){ sum+=k[j].len; break; } if(sum==p){ cout<<x; falg=1;break; } } if(!falg)printf("-1\n"); return 0;}
正解hash：
/*正解hash思路和之前的有相似之处先排序 只不过没有类似离散化的处理把每个人的答案放入hash表 这里用链表处理了碰撞的情况然后同样的枚举正确答案 这不过用了hash表加速对于pq==0的情况 枚举答案 按字典序小的来那难道不会T到飞吗 不成了2^500的了吗答案是不会的 这里的枚举是针对pq==0的情况来的结束的条件是 找到与每个人都不一样的（存在一个即可）的就停下所以枚举最多30000次 */#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 100010#define mod 10007#define MOD 23333#define bas 19#define BAS 119using namespace std;int n,m,p,q,hash[maxn],HASH[maxn],ans,falg;int num,head[maxn],cnt[maxn],t,T;struct edge{ int v,pre;}e[maxn*2];struct node{ char s[510]; bool operator < (const node &x) const { return strcmp(s,x.s)<0; }}a[maxn];void Insert(int from,int to){ for(int i=head[from];i;i=e[i].pre) if(e[i].v==to){ cnt[i]++;return; } num++;e[num].v=to; e[num].pre=head[from]; head[from]=num; cnt[num]++;}int Query(int from,int to){ for(int i=head[from];i;i=e[i].pre) if(e[i].v==to)return cnt[i]; return 0;}void Yan(){ for(int i=1;i<=n;i++){ t=0,T=0; for(int j=0;j<m;j++){ t=t*bas+(a[i].s[j]==‘Y‘);t%=mod; T=T*BAS+(a[i].s[j]==‘Y‘);T%=MOD; } hash[i]=t;HASH[i]=T; Insert(t,T); } for(int i=1;i<=n;i++){ if(Query(hash[i],HASH[i])==p){ int t=0,T=0; for(int j=0;j<m;j++){ t=t*bas+(a[i].s[j]==‘N‘);t%=mod; T=T*BAS+(a[i].s[j]==‘N‘);T%=MOD; } if(Query(t,T)==q){ ans=i; falg=1;break; } if(falg)break; } } if(falg)printf("%s\n",a[ans].s); else printf("-1\n");}void Li(){ for(int i=1;i<=n;i++){ int t=0,T=0; for(int j=0;j<m;j++){ t=t*bas+(a[i].s[j]==‘Y‘);t%=mod; T=T*BAS+(a[i].s[j]==‘Y‘);T%=MOD; } hash[i]=t;HASH[i]=T; Insert(t,T); } for(int i=n;i>=1;i--){ if(Query(hash[i],HASH[i])==q){ t=0,T=0; for(int j=0;j<m;j++){ t=t*bas+(a[i].s[j]==‘N‘);t%=mod; T=T*BAS+(a[i].s[j]==‘N‘);T%=MOD; } if(Query(t,T)==p){ ans=i; falg=1;break; } if(falg)break; } } if(falg){ for(int i=0;i<m;i++) if(a[ans].s[i]==‘N‘)printf("Y"); else printf("N"); } else printf("-1\n");}void Feng(){ for(int i=1;i<=n;i++){ t=0,T=0; for(int j=0;j<m;j++){ t=t*bas+(a[i].s[j]==‘Y‘);t%=mod; T=T*BAS+(a[i].s[j]==‘Y‘);T%=MOD; } Insert(t,T); t=0;T=0; for(int j=0;j<m;j++){ t=t*bas+(a[i].s[j]==‘N‘);t%=mod; T=T*BAS+(a[i].s[j]==‘N‘);T%=MOD; } Insert(t,T); } char r[510]; for(int i=0;i<m;i++)r[i]=‘N‘; while(1){ t=0,T=0; for(int i=0;i<m;i++){ t=t*bas+(r[i]==‘Y‘);t%=mod; T=T*BAS+(r[i]==‘Y‘);T%=MOD; } if(Query(t,T)==0){ falg=1;break; } for(int i=m-1;i>=0;i--) if(r[i]==‘Y‘)r[i]=‘N‘; else{ r[i]=‘Y‘;break; } } if(falg)printf("%s\n",r); else printf("-1\n");}int main(){ freopen("answer.in","r",stdin); freopen("answer.out","w",stdout); scanf("%d%d%d%d",&n,&m,&p,&q); for(int i=1;i<=n;i++) scanf("%s",a[i].s); sort(a+1,a+1+n); if(p)Yan(); else if(q)Li(); else Feng(); return 0;}
2.序列问题
【题目描述】
小H是个善于思考的学生，她正在思考一个有关序列的问题。
她的面前浮现出了一个长度为n的序列{ai}，她想找出两个非空的集合S、T。
这两个集合要满足以下的条件：
1. 两个集合中的元素都为整数，且都在 [1, n] 里，即Si，Ti∈ [1, n]。
2. 对于集合S中任意一个元素x，集合T中任意一个元素y，满足x< y。
3. 对于大小分别为p, q的集合S与T，满足
a[s1] xor a[s2] xor a[s3] ... xor a[sp] =a[t1] and a[t2] and a[t3] ... and a[tq].
小H想知道一共有多少对这样的集合(S,T)，你能帮助她吗？
【输入格式】
第一行，一个整数n
第二行，n个整数，代表ai。
【输出格式】
仅一行，表示最后的答案。
【样例输入】
4
1 2 3 3
【样例输出】
4
【样例解释】
S ={1,2}, T = {3}， 1 ^ 2= 3 = 3 (^为异或)
S ={1,2}, T = {4}, 1 ^ 2 = 3 = 3
S = {1,2}， T = {3，4} 1 ^ 2 = 3 & 3 = 3 （&为与运算）
S = {3}， T = {4} 3 = 3 = 3
【数据范围】
30%:1 <= n <= 10
60%:1 <= n <= 100
100%:1 <= n <= 1000, 0 <= ai < 1024
/*30分暴力枚举集合不说了其实这题需要高精的....维护i到n &值为j的方案数 维护1到i ^值为j的方案数 然后枚举断点 乘起来 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 2050#define ll long longusing namespace std;ll n,a[maxn],b[maxn],sum[maxn],f[maxn][maxn+200],g[maxn][maxn+200],ans;int main(){ freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); cin>>n; for(ll i=1;i<=n;i++) cin>>a[i]; for(ll i=1;i<=n;i++) b[i]=a[n-i+1]; for(ll i=1;i<=n;i++){ for(ll j=0;j<=2048;j++) f[i][j]=sum[j^a[i]]; f[i][a[i]]++; for(ll j=0;j<=2048;j++) sum[j]+=f[i][j]; } memset(sum,0,sizeof(sum)); for(ll i=0;i<n;i++){ for(ll j=0;j<=2048;j++) g[i+1][j&b[i+1]]+=sum[j]; g[i+1][b[i+1]]++; for(ll j=0;j<=2048;j++) sum[j]+=g[i+1][j]; } memset(sum,0,sizeof(sum)); for(ll i=1;i<n;i++){ for(ll j=0;j<2048;j++) sum[j]+=f[i][j]; for(ll j=0;j<2048;j++) ans+=sum[j]*g[n-i][j]; } cout<<ans; return 0;}
3.长途旅行
【题目描述】
JY是一个爱旅游的探险家，也是一名强迫症患者。现在JY想要在C国进行一次长途旅行，C国拥有n个城市(编号为0,1,2...,n - 1)，城市之间有m条道路，可能某个城市到自己有一条道路，也有可能两个城市之间有多条道路，通过每条道路都要花费一些时间。JY从0号城市开始出发，目的地为n – 1号城市。由于JY想要好好参观一下C国，所以JY想要旅行恰好T小时。为了让自己的旅行更有意思，JY决定不在任何一个时刻停留(走一条到城市自己的路并不算停留)。JY想知道是否能够花恰好T小时到达n – 1号城市（每个城市可经过多次）。现在这个问题交给了你。
若可以恰好到达输出“Possible”否则输出“Impossible”。(不含引号)。
【输入格式】
第一行一个正整数Case，表示数据组数。
每组数据第一行3个整数，分别为n, m, T。
接下来m行，每行3个整数x, y, z,代表城市x和城市y之间有一条耗时为z的双向边。
【输出格式】
对于每组数据输出”Possible”或者”Impossible”.
【样例输入】
2
3 3 11
0 2 7
0 1 6
1 2 5
2 1 10000
1 0 1
【样例输出】
Possible
Impossible
【样例解释】
第一组：0 -> 1 -> 2 :11
第二组：显然偶数时间都是不可能的。
【数据范围】
30%: T <= 10000
另有30%: n <= 5 , m <= 10.
100%:2 <= n <= 50 , 1 <= m <= 100 , 1 <= z <= 10000 , 1 <= T<= 10^18 , Case <= 5.
暴力dp30：
/*暴力dp 30状态f[i][j]表示到了i号节点走了j的状态是否存在可以水过T比较小的数据 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 1000010using namespace std;int T,t,n,m,f[51][maxn],g[51][51];void Clear(){ memset(f,0,sizeof(f)); memset(g,0,sizeof(g));}int main(){ freopen("travel.in","r",stdin); freopen("travel.out","w",stdout); scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&m,&t); int u,v,s;Clear(); for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&s); u++;v++; g[u][v]=g[v][u]=s; } f[1][0]=1; for(int j=1;j<=t;j++) for(int i=1;i<=n;i++) for(int k=1;k<=n;k++){ if(!g[i][k]||j-g[i][k]<0)continue; f[i][j]=f[i][j]||f[k][j-g[i][k]]; } if(f[n][t])printf("Possible\n"); else printf("Impossible\n"); } return 0;}
正解SFPA：
/*正解是最短路~~~~一开始以为图论 后来认为是dp 没想到最后又回到图论了~~前面dp做法的瓶颈很显然是T太大~ 但是出入的边的权值和要小的多 所以会在某个环了转圈假设有一条路径走一遍的时间为t 中间有一个长度为p的环那这条路可以认为是t+p*k长度的所以我们只需要维护这个多出来的t就好了 先选一个环保险起见 选从零出发的最小的环 长度设为x 定义dis[i][j] 表示到了i 时间为j+k*x 且k最小 这里跑最短路找最小为什么找最小呢 因为只有当dis[n][T%x]<=T 时才可以 所以为了尽量满足条件维护最小的dis */#include<iostream>#include<cstdio>#include<cstring>#include<queue>#define maxn 210#define ll long longusing namespace std;ll T,t,n,m,num,head[maxn],dis[maxn][maxn*100],mxx,f[maxn][maxn];struct node{ ll v,t,pre;}e[maxn*2];struct point{ int v,s;};queue<point>q;void Clear(){ memset(head,0,sizeof(head)); memset(f,0,sizeof(f)); num=0;}ll min(ll a,ll b){ return a<b?a:b;}void Add(ll from,ll to,ll dis){ num++;e[num].v=to; e[num].t=dis; e[num].pre=head[from]; head[from]=num;}void SPFA(){ memset(dis,127/3,sizeof(dis)); q.push((point){1,0}); f[1][0]=1;dis[1][0]=0; while(!q.empty()){ ll x=q.front().v; ll s=q.front().s; q.pop();f[x][s]=0; for(int i=head[x];i;i=e[i].pre){ ll v=e[i].v; ll di=s+e[i].t; di%=mxx;//这里分清谁做下标谁是dis值 if(dis[v][di]>s+e[i].t){ dis[v][di]=s+e[i].t; if(f[v][di]==0){ f[v][di]=1; q.push((point){v,di}); } } } }}int main(){ freopen("travel.in","r",stdin); freopen("travel.out","w",stdout); cin>>T; while(T--){ cin>>n>>m>>t; ll u,v,s;Clear(); mxx=0x7fffffff; for(int i=1;i<=m;i++){ cin>>u>>v>>s; u++;v++; Add(u,v,s);Add(v,u,s); if(u==1||v==1)mxx=min(mxx,s); } if(mxx==0x7fffffff){//不连通 printf("Impossible\n"); continue; } mxx*=2; SPFA(); if(dis[n][t%mxx]<=t)printf("Possible\n"); else printf("Impossible\n"); } return 0;}
9.5noip模拟试题