深圳中心网站建设,网站header设计,科技进步法,达州做网站登录—专业IT笔试面试备考平台_牛客网
题目大意#xff1a;给出一字符串t#xff0c;求一个长为n的字符串#xff0c;使tst中包含且仅包含两个t
1n1000;测试样例组数1000
思路#xff1a;一开始很容易想到如果t里有1#xff0c;s就全0#xff0c;否则s就全…登录—专业IT笔试面试备考平台_牛客网
题目大意给出一字符串t求一个长为n的字符串使tst中包含且仅包含两个t
1n1000;测试样例组数1000
思路一开始很容易想到如果t里有1s就全0否则s就全1但当tan*0/n*1a这样时例如001000001,110111110,n3这时s就对应的不能等于全0/全1但至少有一种可以也就是对于前者我们可以选111对于后者选000所以我们全0或全1都试一下用kmp分别检验是否合法都不合法就输出-1但经测试其实没有-1的情况
#includebits/stdc.h
#define P pairint,char
using namespace std;
const int N 1e3 5;
char str[N], pattern[N];
int fail[N];
int a[N];
int n;
string t,s;
void getfail(string p, int plen)
{//取得p的失配指针fail[0] 0, fail[1] 0;for (int i 1; i plen; i){int j fail[i];while (j p[i] ! p[j]){j fail[j];}fail[i 1] p[i] p[j] ? j 1 : 0;}
}
int kmp(string s, string p)
{//求s的子串中有多少个pint cnt 0;//记录答案int last -1;//记录上一次匹配的位置int slen s.size(), plen p.size();getfail(p, plen);int j 0;for (int i 0; i slen; i){while (j s[i] ! p[j]){j fail[j];}if (s[i] p[j]){j;}if (j plen){cnt;last i;}}return cnt;
}
bool check()
{string temp t s t;if(kmp(temp,t)2){return false;}return true;
}
int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);int T;cinT;while(T--){cinn;cint;s;for(int i0;in;i){s0;}if(check()){//全0试试coutsendl;continue;}s;for(int i0;in;i){s1;}if(check()){//全1试试coutsendl;continue;}//cout-1endl;}return 0;
}
