A.Alive Fossils
纯模拟没啥好说的
map<string,int>mp;
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
int t;cin>>t;
while(t--)
{
string s;cin>>s;
mp[s]++;
}
}
int res=0;
set<string>st;
for(auto it:mp)
{
if(it.second==n)
{
res++;
st.insert(it.first);
}
}
cout<<res<<"\n";
for(auto it:st)
{
cout<<it<<"\n";
}
}
H.Insert 1, Insert 2, Insert 3, ...
题意：给定长度为\(n\)的序列，问有多少个连续子区间满足这个子区间可以通过若干次依次按顺序插入\(1,2,3,...,k\)的子序列构成
Solution
对于一个右端点，它的合法左端点肯定是1，必须是1开头
我们可以用栈来找到对于\(x\)的最近的\(x-1\)的位置，则其中的1一定不合法
所以如果遇到整个都不合法的区间，则清空所有的1
void solve()
{
int n;
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
if (x == 1)
{
s.push_back(i);
e[x].push_back(i);
ans += s.size();
}
else if (e[x - 1].empty())
{
s.clear();
}
else
{
int pos = e[x - 1].back();
e[x - 1].pop_back();
e[x].push_back(i);
while (s.size() && s.back() > pos)
s.pop_back();
ans += s.size();
}
}
cout << ans << "\n";
}
I.Make It Square
题意：有一个串\(n\)，由两个回文串\(s,t\)和两个相同的未知串\(p,q\)组成，其中\(n,p,q\)是\(AA\)型的串，求满足条件的\(p,q\)对于其长度分别为\(1,2,...,k\)的个数
Solution
首先\(p+q\)一定是偶数，不是偶数则\(s\)也不能是偶数
\(|p|=|q|\)时，判断\(p,q\)是否完全一致，如果一致，则答案为\(26^i\)
令\(|p|=n,|q|=m\)
\(|p|>|q|\)时，分情况讨论
当\(i\leq(n-m)/2\)时，则有
发现，此时，\(p,q\)已经固定了，如果\(s,t\)在图中位置匹配，并且\(s\)有长度为\((n-m)/2-i\)的前后缀相同，答案为1，反之为0
当\(i>(n-m)/2\)时，则有
此时有\(i-(n-m)/2\)的是未确定的，如果s,t匹配的话，则答案为\(26^{i-\frac{n-m}{2}}\)（题解的图有点问题）
对于\(|p|<|q|\)的情况同理
void getkmp(string b, int kmp[])
{
int j = 0;
int lenb = b.length();
b = "#" + b;
for (int i = 2; i <= lenb; i++)
{
while (j && b[i] != b[j + 1])
j = kmp[j];
if (b[j + 1] == b[i])
j++;
kmp[i] = j;
}
}
set<int> getBorder(string p, int nx[])
{
set<int> s;
int cur = nx[p.length()];
while (cur)
{
s.insert(cur);
cur = nx[cur];
}
s.insert(0);
return s;
}
void solve()
{
int m;
cin >> m;
string p, q;
cin >> p >> q;
getkmp(p, kmp1);
getkmp(q, kmp2);
set<int> b1, b2;
b1 = getBorder(p, kmp1);
b2 = getBorder(q, kmp2);
// cout << kmp1[p.length()] << " " << kmp2[q.length()] << "\n";
int x = p.length(), y = q.length();
if (x == y)
{
int flag = 1;
for (int i = 0; i < x; i++)
{
if (p[i] != q[i])
{
flag = 0;
break;
}
}
if (flag)
{
int res = 1;
for (int i = 1; i <= m; i++)
{
res = (res * 26) % mod;
cout << res << " ";
}
}
else
{
for (int i = 1; i <= m; i++)
{
cout << "0 ";
}
}
}
else if ((x + y) & 1)
{
for (int i = 1; i <= m; i++)
{
cout << "0 ";
}
}
else if (x > y)
{
int pos = (x - y) / 2;
int flag = 1;
for (int i = 0; i < y; i++)
{
if (p[pos] != q[i])
{
flag = 0;
break;
}
pos++;
}
int res = 1;
for (int i = 1; i <= m; i++)
{
if (!flag)
{
cout << "0 ";
continue;
}
if (i <= (x - y) / 2)
{
if (b1.count((x - y) / 2 - i))
{
cout << "1 ";
}
else
{
cout << "0 ";
}
}
else
{
res = (res * 26) % mod;
cout << res << " ";
}
}
}
else if (x < y)
{
int pos = (y - x) / 2;
int flag = 1;
for (int i = 0; i < x; i++)
{
if (p[i] != q[pos])
{
flag = 0;
break;
}
pos++;
}
int res = 1;
for (int i = 1; i <= m; i++)
{
if (!flag)
{
cout << "0 ";
continue;
}
if (i <= (y - x) / 2)
{
if (b2.count((y - x) / 2 - i))
{
cout << "1 ";
}
else
{
cout << "0 ";
}
}
else
{
res = (res * 26) % mod;
cout << res << " ";
}
}
}
}
J.Permutation and Primes
题意：构造一个排列，使得相邻的数的和或者差是大于2的素数
Solution
看到别人有8循环的，我写个10循环的构造
令初始值为\(x\)，则可以构造出\(\textcolor{red}{x,x+7,x+4,x+1,x+8,x+5,x+2,x+9,x+6,x+3},x+10\)，红色的部分即为一个循环，我们可以打表找到长度从1到9的，这样就可以涵盖到全部的情况
int n;
int a[N];
int mov[10] = {7, -3, -3, 7, -3, -3, 7, -3, -3, 7};
void solve()
{
cin >> n;
if (n % 10 <= 4)
{
for (int i = 1; i <= n % 10; i++)
a[i] = i;
}
else if (n % 10 == 5)
{
a[1] = 1, a[2] = 4, a[3] = 3, a[4] = 2, a[5] = 5;
}
else if (n % 10 == 6)
{
a[1] = 1, a[2] = 4, a[3] = 3, a[4] = 2, a[5] = 5, a[6] = 6;
}
else if (n % 10 == 7)
{
a[1] = 1, a[2] = 2, a[3] = 5, a[4] = 6, a[5] = 3, a[6] = 4, a[7] = 7;
}
else if (n % 10 == 8)
{
a[1] = 1, a[2] = 2, a[3] = 3, a[4] = 4, a[5] = 7, a[6] = 6, a[7] = 5, a[8] = 8;
}
else if (n % 10 == 9)
{
a[1] = 1, a[2] = 2, a[3] = 3, a[4] = 4, a[5] = 7, a[6] = 6, a[7] = 5, a[8] = 8, a[9] = 9;
}
int cnt = 0;
for (int i = n % 10 + 1; i <= n; i++)
{
a[i] = a[i - 1] + mov[cnt % 10];
cnt++;
}
for (int i = 1; i <= n; i++)
cout << a[i] << " \n"[i == n];
}
K.Scheming Furry
题意：给出一个矩阵，狐狸每次操作可以交换两行，猫每次操作可以交换两列，狐狸先操作，谁先把数组变得有序（即按行优先顺序放置数字的顺序）谁获胜，如果谁知道自己无法获胜，则会尽可能不让另一个人获胜。
Solution
先考虑对于\(n>=3,m>=3\)的情况，容易发现如果狐狸不能一步完成，则猫永远也无法完成
\(n=2,m=2\)时，如果进行一次行操作和一次列操作能完成，则猫获胜，如果进行一次行操作能完成，则狐狸获胜
\(n=2,m>=3\)时，如果行操作次数与列操作次数奇偶性相同则猫获胜，反之平局
\(n>=3,n=2\)时，如果行操作次数与列操作次数奇偶性相反时狐狸获胜，反之平局
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
for (int i = 1; i <= m; i++)
{
for (int j = 2; j <= n; j++)
{
if (a[j][i] % m != a[j - 1][i] % m)
{
cout << "NSFW\n";
return;
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 2; j <= m; j++)
{
if ((a[i][j] + m - 1) / m != (a[i][j - 1] + m - 1) / m)
{
cout << "NSFW\n";
return;
}
}
}
int ans1 = 0, ans2 = 0;
memset(vis1, 0, sizeof(vis1));
memset(vis2, 0, sizeof(vis2));
for (int i = 1; i <= n; i++)
{
if (!vis1[i])
{
int pos = i;
while (!vis1[pos])
{
vis1[pos] = 1;
int nxt = (a[pos][1] + m - 1) / m;
pos = nxt;
ans1++;
}
ans1--;
}
}
for (int i = 1; i <= m; i++)
{
if (!vis2[i])
{
int pos = i;
while (!vis2[pos])
{
vis2[pos] = 1;
int nxt = (a[1][pos]) % m;
if (nxt == 0)
nxt = m;
pos = nxt;
ans2++;
}
ans2--;
}
}
if (ans1 == 1 && ans2 == 0)
{
cout << "FOX\n";
return;
}
if (n >= 3 && m >= 3)
{
cout << "NSFW\n";
return;
}
if (n == 2 && m == 2)
{
if (ans1 == 1 && ans2 == 1)
{
cout << "CAT\n";
}
else
{
cout << "FOX\n";
}
return;
}
else if (n == 2)
{
if ((ans1 & 1) == (ans2 & 1))
{
cout << "CAT\n";
return;
}
else
{
cout << "NSFW\n";
return;
}
}
else if (m == 2)
{
if ((ans1 & 1) != (ans2 & 1))
{
cout << "FOX\n";
return;
}
else
{
cout << "NSFW\n";
return;
}
}
else
assert(0);
}