比赛链接：第 63 场周赛 - AcWing
这场打得很烂hh，也没有认真打，题目还可以，写一下总结吧。B是一个栈就可以，我用上次惯性思维用链表去做也写错了，还是栈比较好，后面在一场的多校里面也是出现过，就一下做出来了。C是一个卡我常数，这里需要手写哈希（Hash）
A.数对数量
题意：请计算，共有多少个整数数对 $(x,y)$ 同时满足：
- 1.$0≤x≤a$
- 2.$0≤y≤b$
- 3.$x+y=n$
思路：枚举即可。
代码：
inline void Case_Test()
{
cin>>a>>b>>n;
for (int i=0;i<=a;i++)
for (int j=0;j<=b;j++)
if (i+j==n) ans++;
cout<<ans;
}
B.字符串消除（栈）
题意：李华和张红正在玩字符串消除游戏。
游戏规则如下：
给定一个由小写字母构成的字符串 s。
两人轮流进行消除操作，当轮到一人时，其任务是在当前 s 中找到两个连续且相同的字母，并将它们从 s 中消除。例如，当 s 为 abba 时，可以消除 bb，使 s 变为 aa。
第一个无法进行消除操作的选手视为失败。
已知，游戏由李华执先手，且两人都采取最优策略。
请问，李华是否可以获胜。
思路：
拿栈模拟，每次对于一个新的数与栈顶比较，如果相等就可以pop出，这样就模拟了相邻的消除的，如果不相等那么就压入栈中。
后面出的牛客多校7F题有个题也是这样的，不过这个是环形链表，首尾相接的，所以我这里用双端队列(deque)
2022牛客多校·第七场（J.DP,K.博弈+莫队） - CarryNotKarry
代码：
inline void Case_Test()
{
cin>>s;
n = s.size();
stack<int> st;
for (auto c:s)
{
if (!st.empty()&&st.top()==c) st.pop();
else st.push(c);
}
if ((n-st.size())%4==0) No;
else Yes;
}
C.最大子集(手写Hash)
题意：
给定一个包含 $n$ 个元素的整数集合。
集合中的元素两两不同。
请你找到一个该集合的最大子集，要求子集内的元素满足任意两元素之差的绝对值都是 $2$ 的整数幂。
注意，只包含 $1$ 个元素的子集一定满足条件。
注意：本题数据范围较大，慎用cin/cout、unordered_set、unordered_map等操作。
思路：
主要注意，这个答案最多三种，不会集合有四个的情况，而且三个的情况是相差一样的情况，例如$2,6,10$每个相差$4$，如果两个都不是相差四那么一定不满足条件。
y总有句话写在上面，我也尝试过都tle，所以需要手写hash
const int M=1999997;
const int inf=0x3f3f3f3f;
int h[M];
int find(int x) // 手写hash
{
int t = (x % M + M) % M;
while (h[t] != inf && h[t] != x)
if (++ t == M)
t = 0;
return t;
}
一般这个M需要是数组的四到五倍。
其实就是给x一个位置，一开始需要全部赋值为inf，也就是memset(h,0x3f,sizeof(h));。
返回的是位置，一开始给a[i]分配位置的时候需要h[find(a[i])]=a[i]，也就是找到个位置放进去。
那如何判断有没有呢？
if (h[find(a[i]+d)]!=inf)
这样即可，当前位置没有放东西说明还是inf。
至此，只需要枚举所有的，枚举j=0...30，判断2^j有没有即可。
代码：
const int M=1999997;
int h[M];
int find(int x) // 手写hash
{
int t = (x % M + M) % M;
while (h[t] != inf && h[t] != x)
if (++ t == M)
t = 0;
return t;
}
inline void Case_Test()
{
n=read();
memset(h, 0x3f, sizeof h);
for (int i=1;i<=n;i++) a[i] = read(), h[find(a[i])] = a[i];
sort(a+1,a+n+1);
for (int i=1;i<=n;i++)
{
for (int j=0;j<=30;j++)
{
int d = 1<<j;
int t = 0;
p[t++] = a[i];
if (h[find(a[i]+d)]!=inf)
{
p[t++] = a[i]+d;
if (h[find(a[i]+2*d)]!=inf)
p[t++] = a[i]+2*d;
}
if (t>cnt) cnt = t, memcpy(ans, p, sizeof p);
}
}
writeln(cnt);
for (int i=0;i<cnt;i++) writesp(ans[i]);
}