11.24模拟赛

11.24模拟赛

全国信息学奥林匹克联赛( N O I P 2014 NOIP2014 NOIP2014)复赛

模拟题 D a y 1 Day1 Day1

长乐一中

题目名称	正确答案	序列问题	长途旅行
英文名称	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 H H 与小 Y Y Y 刚刚参加完 U O I P UOIP UOIP 外卡组的初赛，就迫不及待的跑出考场对答案。

“吔，我的答案和你都不一样！”，小 Y Y Y 说道，”我们去找神犇们问答案吧”。

外卡组试卷中共有 m m m 道判断题，小 H H H 与小 Y Y Y 一共从其他 n n n 个神犇那问了答案。之后又从小 G G G 那里得知，这 n n n 个神犇中有 p p p 个考了满分， q q q 个考了零分，其他神犇不为满分或零分。

这可让小 Y Y Y 与小 H H H 犯了难。你能帮助他们还原出标准答案吗？如有多解则输出字典序最小的那个。无解输出 − 1 -1 −1。

【输入格式】

第一行四个整数 n n n, m m m, p p p, q q q，意义如上描述。

接下来 n n n 行，每一行 m m m 个字符 ’ N ’ ’N’ ’N’或 ’ Y ’ ’Y’ ’Y’，表示这题这个神犇的答案。

【输出格式】

仅一行，一个长度为 m m m 的字符串或是 − 1 -1 −1。

【样例输入】

2 2 2 0
YY
YY

【样例输出】

YY

【数据范围】

30 30 30% : n < = 100. n <= 100. n<=100.

60 60 60% : n < = 5000 , m < = 100. n <= 5000 , m <= 100. n<=5000,m<=100.

100 100 100% : 1 < = n < = 30000 , 1 < = m < = 500.0 < = p , q 且 p + q < = n . 1 <= n <= 30000 , 1 <= m <= 500. 0 <= p , q 且 p + q <= n. 1<=n<=30000,1<=m<=500.0<=p,q且p+q<=n.

2.序列问题

【题目描述】

小 H H H 是个善于思考的学生，她正在思考一个有关序列的问题。

她的面前浮现出了一个长度为 n n n 的序列 a i {ai} ai，她想找出两个非空的集合 S 、 T S、T S、T。

这两个集合要满足以下的条件：

1. 两个集合中的元素都为整数，且都在 [ 1 , n ] [1, n] [1,n] 里，即 S i ， T i ∈ [ 1 , n ] Si，Ti ∈ [1, n] Si，Ti∈[1,n]。

2. 对于集合 S S S 中任意一个元素 x x x，集合 T T T 中任意一个元素 y y y，满足 x < y x < y x<y。

3. 对于大小分别为 p p p, q q q 的集合 S S S 与 T T T，满足

a [ s 1 ] a[s1] a[s1] x o r xor xor a [ s 2 ] a[s2] a[s2] x o r xor xor a [ s 3 ] . . . a[s3] ... a[s3]... x o r xor xor a [ s p ] = a [ t 1 ] a[sp] = a[t1] a[sp]=a[t1] a n d and and a [ t 2 ] a[t2] a[t2] a n d and and a [ t 3 ] . . . a[t3] ... a[t3]... a n d and and a [ t q ] . a[tq]. a[tq].

小 H H H 想知道一共有多少对这样的集合 ( S , T ) (S,T) (S,T)，你能帮助她吗？

【输入格式】

第一行，一个整数 n n n

第二行， n n n 个整数，代表 a i ai 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 30 30%: 1 < = n < = 10 1 <= n <= 10 1<=n<=10

60 60 60%: 1 < = n < = 100 1 <= n <= 100 1<=n<=100

100 100 100%: 1 < = n < = 1000 , 0 < = a i < 1024 1 <= n <= 1000, 0 <= ai < 1024 1<=n<=1000,0<=ai<1024

3.长途旅行

【题目描述】

J Y JY JY 是一个爱旅游的探险家，也是一名强迫症患者。现在 J Y JY JY 想要在 C C C 国进行一次长途旅行， C C C 国拥有 n n n 个城市(编号为 0 , 1 , 2... , n − 1 0,,n - 1 0,,n−1)，城市之间有 m m m 条道路，可能某个城市到自己有一条道路，也有可能两个城市之间有多条道路，通过每条道路都要花费一些时间。 J Y JY JY 从 0 0 0 号城市开始出发，目的地为 n – 1 n – 1 n–1 号城市。由于 J Y JY JY 想要好好参观一下 C C C 国，所以 J Y JY JY 想要旅行恰好 T T T 小时。为了让自己的旅行更有意思， J Y JY JY 决定不在任何一个时刻停留(走一条到城市自己的路并不算停留)。 J Y JY JY 想知道是否能够花恰好 T T T 小时到达 n – 1 n – 1 n–1 号城市（每个城市可经过多次）。现在这个问题交给了你。

若可以恰好到达输出 “ P o s s i b l e ” “Possible” “Possible”否则输出 “ I m p o s s i b l e ” “Impossible” “Impossible”。(不含引号)。

【输入格式】

第一行一个正整数 C a s e Case Case，表示数据组数。

每组数据第一行 3 3 3 个整数，分别为 n , m , T n, m, T n,m,T。

接下来 m m m 行，每行 3 3 3 个整数 x , y , z , x, y, z, x,y,z,代表城市 x x x 和城市 y y y 之间有一条耗时为 z z z 的双向边。

【输出格式】

对于每组数据输出 ” P o s s i b l e ” ”Possible” ”Possible”或者 ” I m p o s s i b l e ” ”Impossible” ”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 0 -> 1 -> 2 :11 0−>1−>2:11

第二组：显然偶数时间都是不可能的。

【数据范围】

30 30 30%: T < = 10000 T <= 10000 T<=10000

另有 30 30 30%: n < = 5 , m < = 10. n <= 5 , m <= 10. n<=5,m<=10.

100 100 100%: 2 < = n < = 50 , 1 < = m < = 100 , 1 < = z < = 10000 , 1 < = T < = 1 0 18 , C a s e < = 5. 2 <= n <= 50 , 1 <= m <= 100 , 1 <= z <= 10000 , 1 <= T <= 10^{18 }, Case <= 5. 2<=n<=50,1<=m<=100,1<=z<=10000,1<=T<=1018,Case<=5.

---

题解

转自博客园-一入OI深似海，转载地址：.html

---

T1

/*
自己还是太弱~没看出来要用hash 只是觉得自己的作法慢~
QAQ
50分暴力 先排序 一样的缩成一种 然后枚举正确答案是哪个
q==0 p==0的情况没考虑到~ 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 30010
#define maxm 510
using 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("-1n");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 119
using 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("%sn",a[ans].s);else printf("-1n");
}
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("-1n");
}
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("%sn",r);else printf("-1n");
}
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;
}

T2

/*
30分暴力枚举集合不说了
其实这题需要高精的....
维护i到n &值为j的方案数 
维护1到i ^值为j的方案数 
然后枚举断点 乘起来 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 2050
#define ll long long
using 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;
}

T3

暴力dp30：

/*
暴力dp 30
状态f[i][j]表示到了i号节点走了j的状态是否存在
可以水过T比较小的数据 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1000010
using 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("Possiblen");else printf("Impossiblen");}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 long
using 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("Impossiblen");continue;}mxx*=2;SPFA();if(dis[n][t%mxx]<=t)printf("Possiblen");else printf("Impossiblen");}return 0;
}