安全等级保护每个网站必须做吗,蛋糕烘焙wordpress主题,服务中心网站建设方案,wordpress友情链接函数传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你个nnn和三个长度为n∗2n*2n∗2的串#xff0c;让你构造一个长度≤n∗3\le n*3≤n∗3的串#xff0c;使其子序列包含至少两个给定串。
思路#xff1a;
先考虑如果没有长度限制#xff0c;那么我们…传送门
文章目录题意思路题意
给你个nnn和三个长度为n∗2n*2n∗2的串让你构造一个长度≤n∗3\le n*3≤n∗3的串使其子序列包含至少两个给定串。
思路
先考虑如果没有长度限制那么我们肯定就是把两个串链接在一起就行了这样长度就是n∗4n*4n∗4的考虑怎么优化成n∗3n*3n∗3的串。我们要减少长度nnn所以可以考虑两个串共用nnn个字符这样两个串长度减去公用的字符就变成了nnn而我们构造的串长度目前也是nnn所以我们直接将两个串剩余的字符都插入我们目前构造的长度为nnn的串里面就好了。 下面证明为什么一定能找两个公共字符≥n\ge n≥n的串。 由于只有0,10,10,1两种字符所以这个串一定是cnt1≥ncnt_1 \ge ncnt1≥n或者cnt0≥ncnt_0 \ge ncnt0≥n所以由抽屉原理可知三个串的时候至少有两个cnt1≥ncnt_1 \ge ncnt1≥n或者cnt0≥ncnt_0 \ge ncnt0≥n,所以我们直接找就好啦。 做的时候想到了尽可能多的找的公用的但是没想到直接选一个字符来判断。
//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N2010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
string a[4];string solve(string a,string b,char c)
{int l,r; lr0;string ans;for(int in;i;i--){while(ln*2a[l]!c) ansa[l];while(rn*2b[r]!c) ansb[r];l; r;ansc;}while(ln*2) ansa[l];while(rn*2) ansb[r];return ans;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int _; cin_;while(_--){cinna[0]a[1]a[2];vectorstringv1,v2;for(int i0;i3;i){int cnt0;for(int j0;jn*2;j) cnta[i][j]0;if(cntn) v1.pb(a[i]);else v2.pb(a[i]);}string ans;if(v1.size()1) anssolve(v1[0],v1[1],0);else anssolve(v2[0],v2[1],1);coutansendl;}return 0;
}
/*
1
3
000010
111010
111111
*/
