AcWing周赛63（C.思维+手写Hash）

这场打得很烂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]);
}