问题 A: 正确答案
题目描述
小 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.
- #include
- #include
- #include
- #include
- #include
- #include
- using namespace std;
- int n,m,p,q;
- char fuck[501];
- string a[30010],ans;
- map<string,int> mp;
- bool flag;
- bool cmp(string a,string b)
- {
- return a<b;
- }
- bool check(string s)
- {
- string ss;
- for(int i=0;i<m;i++)
- {
- if(s[i]=='N') ss+='Y';
- else ss+='N';
- }
- if(mp.find(ss)==mp.end()) return 1;
- return 0;
- }
- void dfs(string s,int dep)
- {
- if(flag) return;
- if(dep==m)
- {
- if(!mp[s]&&check(s))
- {
- flag=1;
- ans=s;
- }
- return;
- }
- dfs(s+'N',dep+1);
- dfs(s+'Y',dep+1);
- }
- int main()
- {
- scanf("%d%d%d%d",&n,&m,&p,&q);
- for(int i=1;i<=n;i++)
- {
- scanf("%s",fuck);
- a[i]=string(fuck);
- mp[a[i]]++;
- }
- if(p==0&&q==0)
- {
- dfs("N",1);
- if(!flag) dfs("Y",1);
- if(!flag)
- {
- puts("-1");
- }
- else cout<<ans;
- }
- else
- {
- bool ff=0;
- if(p==0)
- {
- swap(p,q);ff=1;
- }
- sort(a+1,a+1+n,cmp);
- for(int i=1;i<=n;i++)
- {
- string s;
- if(mp[a[i]]==p)
- {
- for(int j=0;j<m;j++)
- {
- if(a[i][j]=='N') s+='Y';
- else s+='N';
- }
- if(mp[s]==q)
- {
- if(ff)
- {
- for(int j=0;j<m;j++)
- {
- if(a[i][j]=='N') cout<<'Y';
- else cout<<'N';
- }
- }
- else ans=a[i];
- flag=1;break;
- }
- }
- }
- if(!flag) puts("-1");
- else cout<<ans;
- }
- }
问题 B: 无名
题目描述
题意很简单, 给你一个串, 求他有多少个不同的子串, 满足前缀为 A, 后缀为 B. 需要注意的是, 串中所有的字母都是小写字母. 友情提示: 如果你过不了样例, 请注意是 不同 的子串.
输入
第一行母串 S; 第二行串 A; 第三行串 B.
输出
一个数, 即有多少不同的子串.
样例输入
abababab a b
样例输出
4
提示
100%: length(S)<=2000; length(A)<=2000; length(B)<=2000; 30%: 都少个 0.
- #include<bits/stdc++.h>
- using namespace std;
- const int sed=131;
- unsigned long long ha[2002],q[2002]={1};
- int len,lena,lenb,tot1,tot2,ans;
- int aa[2002],bb[2002];
- string s,a,b,fff[2002];
- set<unsigned long long> S;
- int main()
- {
- cin>>s>>a>>b;
- len=s.size();lena=a.size();lenb=b.size();
- for(int i=0;i<len-lena+1;i++)
- {
- bool flag=0;
- for(int j=0;j<lena;j++)
- {
- if(s[i+j]!=a[j]) {flag=1;break;}
- }
- if(!flag) aa[++tot1]=i+lena-1;
- }
- for(int i=0;i<len-lenb+1;i++)
- {
- bool flag=0;
- for(int j=0;j<lenb;j++)
- {
- if(s[i+j]!=b[j]) {flag=1;break;}
- }
- if(!flag) bb[++tot2]=i;
- }
- ha[0]=s[0]-'0';
- for(int i=1;i<len;i++)
- {
- ha[i]=ha[i-1]*sed+s[i]-'0';
- q[i]=q[i-1]*sed;
- }
- for(int i=1;i<=tot1;i++)
- for(int j=1;j<=tot2;j++)
- {
- if(aa[i]>bb[j]+lenb-1||aa[i]-lena+1>bb[j]) continue;
- else
- {
- unsigned long long k1=ha[aa[i]-lena]*q[bb[j]+lenb-1-aa[i]+lena]-ha[bb[j]+lenb-1];
- unsigned long long k2=ha[bb[j]+lenb-1]-ha[aa[i]-lena]*q[bb[j]+lenb-1-aa[i]+lena];
- S.insert(max(k1,k2));
- }
- }
- ans=S.size();
- printf("%d",ans);
- }
问题 C: Friends
题目描述
有三个好朋友喜欢在一起玩游戏, A 君写下一个字符串 S,B 君将其复制一遍得到 T,C 君在 T 的任意位置 (包括首尾) 插入一个字符得到 U. 现在你得到了 U, 请你找出 S.
输入
第一行一个数 N, 表示 U 的长度. 第二行一个字符串 U, 保证 U 由大写字母组成.
输出
若 S 不存在, 输出 "NOT POSSIBLE". 若 S 不唯一, 输出 "NOT UNIQUE". 否则输出 S.
样例输入
7 ABXCABC
样例输出
ABC
提示
- Sample Input2: 6 ABCDEF Sample Input3: 9 ABABABABA
- Sample Output2: NOT POSSIBLE Sample Output3: NOT UNIQUE
对于 100% 的数据 2<=N<=2000001
- #include<bits/stdc++.h>
- using namespace std;
- int n,ans,sum;
- char s[2000010];
- unsigned long long ha[2000010],q[2000010]={1},k1,k2;
- const int sed=131;
- set<unsigned long long> S;
- int main()
- {
- scanf("%d%s",&n,s+1);
- for(int i=1;i<=n;i++)
- {
- ha[i]=ha[i-1]*sed+s[i]-'0';
- q[i]=q[i-1]*sed;
- }
- int mid=(n-1)/2;
- for(int i=1;i<=n;i++)
- {
- if(i<=mid)
- {
- k1=ha[i-1]*q[mid+1-i]+(ha[mid+1]-ha[i]*q[mid+1-i]);
- k2=ha[n]-ha[mid+1]*q[mid];
- }
- if(i>mid)
- {
- k1=ha[mid];
- k2=(ha[i-1]-ha[mid]*q[i-mid-1])*q[n-i]+ha[n]-ha[i]*q[n-i];
- }
- if(k1==k2) ans=i,S.insert(k1);
- }
- sum=S.size();
- if(sum==0) puts("NOT POSSIBLE");
- else if(sum>1) puts("NOT UNIQUE");
- else
- {
- string ss;
- if(ans<=mid)
- {
- for(int i=1;i<=mid+1;i++)
- if(i!=ans) ss+=s[i];
- cout<<ss<<endl;
- }
- else
- {
- for(int i=mid+1;i<=n;i++)
- if(i!=ans) ss+=s[i];
- cout<<ss<<endl;
- }
- }
- return 0;
- }
问题 D: Antisymmetry
题目描述
对于一个 01 字符串, 如果将这个字符串 0 和 1 取反后, 再将整个串反过来和原串一样, 就称作 "反对称" 字符串. 比如 00001111 和 010101 就是反对称的, 1001 就不是. 现在给出一个长度为 N 的 01 字符串, 求它有多少个子串是反对称的.
输入
第一行一个正整数 N (N 500,000). 第二行一个长度为 N 的 01 字符串.
输出
一个正整数, 表示反对称子串的个数.
样例输入
8 11001011
样例输出
- 7
- #include<bits/stdc++.h>
- using namespace std;
- const int sed=131;
- int n,ans;
- unsigned long long ha1[500010],ha2[500010],q[500010]={1};
- char s[500010];
- bool check(int len,int x)
- {
- unsigned long long k1,k2;
- k1=ha1[x]-ha1[x-len]*q[len];
- k2=ha2[x+1]-ha2[x+len+1]*q[len];
- return k1==k2;
- }
- int main()
- {
- scanf("%d%s",&n,s+1);
- for(int i=1;i<=n;i++)
- {
- ha1[i]=ha1[i-1]*sed+s[i]-'0';
- q[i]=q[i-1]*sed;
- }
- for(int i=n;i>=1;i--)
- {
- ha2[i]=ha2[i+1]*sed+((s[i]-'0')^1);
- }
- for(int i=1;i<=n;i++)
- {
- int l=1,r=min(i,n-i),mid,tot=0;
- while(l<=r)
- {
- mid=(l+r)>>1;
- if(check(mid,i)) l=mid+1,tot=mid;
- else r=mid-1;
- }
- ans+=tot;
- }
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2746343.html