暑假集训题解系列（一）

题目1

Alice and Bob

image-20210721092035987

题解

打表暴力题目（比赛时高估了时间复杂度，QAQ）

代码

#include <bits/stdc++.h>
using namespace std;
bool a[5050][5050] = {0}; ///用bool，int会超时
int main()
{
    for (int i = 0; i <= 5000; i++)
        for (int j = 0; j <= 5000; j++)
        {
            if (!a[i][j])
            {
                for (int k = 1; i + k <= 5000; k++)
                    for (int x = 0; x * k + j <= 5000; x++)
                        a[i + k][x * k + j] = 1;
                for (int k = 1; j + k <= 5000; k++)
                    for (int x = 0; x * k + i <= 5000; x++)
                        a[i + x * k][k + j] = 1;
            }
        }
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        if (a[n][m])
            puts("Alice");
        else
            puts("Bob");
    }
}

题目2

Hash Function

image-20210721110814173

题解

两个for循环遍历，寻找最优答案，如果答案不符合，则退回调整答案。

另该题目可以用NTT来完成，可参考博客：

https://blog.nowcoder.net/n/9e67ea84ea1f4b8fa1046762f6e41210

https://blog.nowcoder.net/n/97fe1e13d21141349751df63315eaa97

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
int a[500500] = {0};
int num[500500] = {0};
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for (int i = 1; i <= n; i++)
        cin>>a[i], num[a[i]] = 1;
    sort(a + 1, a + n + 1);
    int idx=1,jdx=1,ans=n,ndx=1;
    while(idx<=n)
    {
        int jdx=a[idx]%ans;
        int flag=1;
        for(;jdx<=a[n];jdx+=ans)
        {
            if(num[jdx])
            {
                if(flag==2) ///有两个数同余，跳出循环
                {
                    flag=0;
                    break;
                }
                flag++;
            }
        }
        if(flag==0)
            idx=ndx,ans++; ///回退
        if(a[idx]<=ans)
            ndx=idx;     
            ///记录上一个符合条件的答案（由于已排序且当前值小于取模的值，所以前面的肯定符合。
        idx++;
    }
    cout<<ans<<endl;
}