前言
胜不在罚时，在题数也。
组队赛小C一把，很是怡情~
题目：A. Mocha 上小班啦
链接： Mocha 上小班啦
题意：
旭丘幼儿园的小班开设了一门教授数论的课程。Mocha 在研究数论的过程中，发现了一种奇妙的 数——Mocha 数。Mocha 数是一个由几个互不相同的数字构成且不含前导零的正整数。 为了方便研究，Mocha 想知道是否存在一个包含 n 个数位的 Mocha 数，如果存在，其中最小的 Mocha 数是多少。
输入格式
一个整数 n（1 ≤ n ≤ 20），代表询问的位数。
输出格式
如果存在包含 n 个数位的 Mocha 数，输出最小的 n 位 Mocha 数，否则输出 −1。
数据范围
1 ≤ n ≤ 20
输入样例：
1输出样例：
1思路：
- 水题 。由于不能含有前导零，同时要数字尽可能的小，所以0要放在次高位，1放在最高位。剩下的数字从小到大依次放在0后面。
- 提前判断一下n的位数，因为所有数位均不相同，所以n的值最大就是10。如果满足条件就按顺序输出。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long ll;
//提前打表
int a[11]={1,0,2,3,4,5,6,7,8,9};
int main()
{
int n;
cin>>n;
if(n>10)cout<<-1<<endl;
else
{
int i=0;
//从前到后输出a数组中的n位
while(n--)cout<<a[i++];
}
system("pause");
return 0;
}题目：E. Serval 的俳句
链接：Serval 的俳句
题意：
Serval 是加帕里幼儿园的新生。 Serval 在俳句赏析大会上发现了一本神秘书卷，他想从中找出一句俳句。
具体来说，神秘书卷是一个仅包含小写英文字母的字符串 S，你需要找到满足下列条件的 S 的一个 子序列 S′ 作为一句俳句：
- S′ 的长度 |S′| 恰好为 17；
- S′1 , S′2 , S′3 , S′4 , S′5 为同一个字符；
- S′6, S′7, . . . , S′11, S′12 为同一个字符；
- S′13, S′14, S′15, S′16, S′17 为同一个字符。
如果满足条件的子序列存在，则输出这个子序列。若存在多个满足条件的子序列，输出任意一个均可。 如果不存在满足条件的子序列，则输出 none 。 我们称 S′ 是 S 的子序列，当且仅当 S′ 可以从 S 中删去任意数量的字符得到。注意 S′ 的前 5 个字 符、中间 7 个字符以及后 5 个字符可以为同一个字符，例如 aaaaaaaaaaaaaaaaa，bbbbbcccccccbbbbb， dddddeeeeeeeeeeee 都是满足条件的。
输入格式
第一行，一个正整数 |S|（1 ≤ |S| ≤ 106），表示字符串 S 的长度。
第二行，一个长度为 |S| 的仅包含小写字母的字符串 S。
输出格式
共一行，如果满足条件的子序列存在，则输出这个子序列，否则输出 none。
数据范围
1 ≤ |S| ≤ 106
输入样例：
22
aaabaacccdccbcccaadaaa输出样例：
aaaaacccccccaaaaa思路：
- 贪心 。先找第一组5个相同字符，然后找第二组7个相同字符，最后找第三组5个相同字符。
- 为什么？因为我们只能删除，不能增加或者交换字符，所以我们要让满足条件的字符组位置尽可能的靠前。给后面的字符组留出更多的寻找空间。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long ll;
int main()
{
int n;
cin>>n;
string s;
cin>>s;
//绯句最少是17
if(n<17)cout<<"none";
else
{
//cnt记录找到几组，i表示当前走到原串的第几个位置，t[i]表示第i组的字符是什么
int cnt=0,i=0;
char t[3];
//因为要找三组，所以最外层循环三次
for(int j=1;j<=3;++j)
{
unordered_map<char,int>m;
for(;i<n;++i)
{
m[s[i]]++;
if((j!=2&&m[s[i]]==5)||(j==2&&m[s[i]]==7))
{
//s[i]此时已经被用了，不能再用于下一次寻找
t[cnt++]=s[i++];
break;
}
}
}
//如果cnt为3，说明找到了符合条件的绯句
if(cnt==3)
{
for(int i=1;i<=5;++i)cout<<t[0];
for(int i=1;i<=7;++i)cout<<t[1];
for(int i=1;i<=5;++i)cout<<t[2];
}
else cout<<"none";
}
system("pause");
return 0;
}优雅之上の优雅：
我享受我自己的代码，感叹我大师般的手法.jpg
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long ll;
int main()
{
int n;
cin>>n;
string s;
cin>>s;
int i=0;
string ans="";
for(int j=1;j<=3;++j)
{
unordered_map<char,int>m;
for(;i<n;++i)
{
m[s[i]]++;
if((j!=2&&m[s[i]]==5)||(j==2&&m[s[i]]==7))
{
j==2?ans+=string(7,s[i++]):ans+=string(5,s[i++]);
break;
}
}
}
ans.size()==17?cout<<ans:cout<<"none";
system("pause");
return 0;
}题目：F. 集合之和
链接：集合之和
题意：
对于任意有限数集 A, B，定义二者之和 A + B 为：
$$
A + B = {x + y | x ∈ A, y ∈ B}
$$
例如，当 A = {1, 2}, B = {3, 4}，有 A+B = {4, 5, 6}。注意此处并非可重集，因此即使 1+4 = 2+3 = 5， A + B 也仅包含一个 5。
记有限数集 A 中的元素个数为 |A|。
现给定 n，试构造数集 A 满足 |A + A| = n，且 A 中任一元素 x 满足 0 ≤ x ≤ 5 × 105 且 x 为整数。
若有多个可行的 A，输出任意解均可。若 A 不存在，输出 −1。
输入格式
一行，一个正整数 n（1 ≤ n ≤ 5 × 105）。
输出格式
若 A 存在，第一行输出一个整数 |A|，表示集合 A 的元素个数。第二行输出 |A| 个互不相同的非负 整数，表示 A 中的元素。
若 A 不存在，输出 −1。
数据范围
1 ≤ |S| ≤ 106
输入样例：
3输出样例：
2
11 51思路：
- 思维 。本质上还是一道找规律的题。
- 当n = 2和n = 4时无解。
- 否则，若n为奇数，输出 [1, (n+1)/2]。若n为偶数，输出 [1, n/2-1] + n/2+1。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef long long ll;
int main()
{
int n;
cin>>n;
//2和4无解
if(n==2||n==4)cout<<-1<<endl;
//当n为奇数
else if(n%2==1)
{
int t=(n+1)/2;
cout<<t<<endl;
for(int i=1;i<=t;++i)cout<<i<<" ";
}
//当n为偶数
else
{
n=n/2;
cout<<n<<endl;
for(int i=1;i<n;++i)cout<<i<<" ";
cout<<n+1<<endl;
}
system("pause");
return 0;
}题目：G. Mocha 上大班啦
链接：Mocha 上大班啦
题意：
在旭丘幼儿园大班的数学课上，Mocha 学到了位运算和概率。她认为自己已经熟练地掌握了这两个 知识点，于是她找到了同学 Arisa 来出题考考自己。
Arisa 给了 Mocha n 个长度为 m 且只包含 0 和 1 的数字串，Arisa 会对这些数字串操作 q 次。每次 Arisa 会选择两个数字串 si 和 sj，并选择两个位置 l, r，对于所有的 x ∈ [l, r]，将 sj [x] 替换为 sj [x] & si [x]， sj [x] 为第 j 个数字串的第 x 位，其中 & 为位运算中的与运算。但是对于第 i 次操作，只有 pi/100 的概 率成功。Arisa 想让 Mocha 计算出 q 次操作后，n 个数字串按位与运算后得到的数字串中 1 的个数的期 望对 998 244 353 取模的结果。
Mocha 并不能解决这道问题，但是她不想丢面子，于是她想请聪明的你帮她计算出这道题的答案。
输入格式
第一行两个整数 n, m（2 ≤ n ≤ 1000, 1 ≤ m ≤ 4000），代表数字串的个数和长度。
之后 n 行每行一个长度为 m 且只包含 0 和 1 的数字串。
第 n + 2 行包含一个整数 q（1 ≤ q ≤ 2 × 105），代表操作次数。
之后 q 行，每行五个整数 i, j, l, r, p（1 ≤ i, j ≤ n, 1 ≤ l ≤ r ≤ m, 0 ≤ p ≤ 100），代表操作两个数字 串的编号，操作的位置范围以及成功概率。保证 i ≠ j。
输出格式
输出一个整数，代表所求期望对 998 244 353 取模的结果。
令 M = 998 244 353，可以证明所求期望可写作既约分数 p q 的形式，其中 p, q 为整数且 q ̸≡ 0 (mod M)。输出的整数应与 p × q−1 mod M 相等，换言之，输出一个整数 x 满足 0 ≤ x < M 且 x × q ≡ p (mod M)。
数据范围
2 ≤ n ≤ 1000
1 ≤ m ≤ 4000
1 ≤ q ≤ 2 × 105
1 ≤ i, j ≤ n
1 ≤ l ≤ r ≤ m
0 ≤ p ≤ 100
输入样例：
3 3
100
110
111
1
1 2 1 2 0输出样例：
1思路：
- 思维 。翻译题目：给n个长度为m的串，有p次操作，每次操作将 si 串和 sj 串共同的一段进行按位与，并将 sj 对应的一段替换为结果。每次操作有可能失败。最后将n个串依次与一个长度为m且所有数位都为1的串（记为M）按位与操作，问最后M串 可能 还剩下多少位是1。
- 之所以用 可能 这个词是因为题目告诉我们每次操作是有可能失败的。但最后的结果真的是不可控的吗？
- 其实不是。我们会发现，无论操作是否成功与否，只有01这样的组合会改变原来的值，因为00和11进行与操作后还是和原来一样。而01这样的组合即便成功也只是让其中某一位的1变成0，这对最后将M与所有串进行与操作的结果是没有改变的。所以对M串操作完后，M串有多少个数位是1是一个定值：该位上所有串都是1的位数。
- 我们会发现其实题目一直在试图迷惑我们，q和后面的q行都不需要接受输入，甚至也不需要取模，因为最多就4000 × 1000 = 4×106 位。
代码：
#include<bits/ stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long ll;
int main()
{
int n,m;
cin>>n>>m;
string s[N];
for(int i=1;i<=n;++i)cin>>s[i];
int q;
cin>>q;
int a,b,c,d,e;
for(int i=1;i<=q;++i)cin>>a>>b>>c>>d>>e;
//cnt存M串最后有多少数位是1
int cnt=0;
//按列遍历
for(int i=0;i<m;++i)
{
//对于第i列，遍历所有串
for(int j=1;j<=n;++j)
{
//只要遇到一个0，最后M该位就为0，提前让cnt--并退出
if(s[j][i]=='0')
{
cnt--;
break;
}
}
//如果有0，已经让cnt--了，需要加1恢复cnt的值。如果没有0，说明cnt需要加1。
cnt++;
}
cout<<cnt<<endl;
system("pause");
return 0;
}
