Atcoder题集

E - Lucky 7 Battle

博弈论，对抗性搜索，记忆化搜索

#include<bits/stdc++.h>
using namespace std;
string t,x;
int n;
int f[200010][7];
int dfs(int i,int r)
{
    if(f[i][r]!=-1) return f[i][r];
    if(i==n+1) return r==0;
    if(x[i]=='T') return f[i][r]=dfs(i+1,r*10%7)|dfs(i+1,(r*10+t[i]-'0')%7);
    else return f[i][r]=dfs(i+1,r*10%7)&dfs(i+1,(r*10+t[i]-'0')%7);
}
int main()
{
    memset(f,-1,sizeof(f));
    cin>>n;
    cin>>t;
    cin>>x;
    t=" "+t;
    x=" "+x;
    int k=dfs(1,0);
    if(!k) cout<<"Aoki";
    else cout<<"Takahashi";
}

D - Hanjo (atcoder.jp)

暴搜，比较难写

#include <cstdio>
#define maxn 20
using namespace std;
​
bool mat[maxn][maxn];
int h, w, a, b, ans;
​
inline bool valid(int x, int y)
{
    return !mat[x][y] && x >= 0 && x < h && y >= 0 && y < w;
}
​
void dfs(int i, int j, int usedA, int usedB)
{
    if((usedA << 1) + usedB == h * w)
    {
        ans ++;
        return;
    }
    if(i == h) return;
    int ni, nj;
    if(j == w - 1) ni = i + 1, nj = 0;
    else ni = i, nj = j + 1;
    if(mat[i][j])
    {
        dfs(ni, nj, usedA, usedB);
        return;
    }
    mat[i][j] = true;
    // Rectangle (A)
    if(usedA < a)
    {
        if(valid(i, j + 1))
        {
            mat[i][j + 1] = true;
            dfs(ni, nj, usedA + 1, usedB);
            mat[i][j + 1] = false;
        }
        if(valid(i + 1, j))
        {
            mat[i + 1][j] = true;
            dfs(ni, nj, usedA + 1, usedB);
            mat[i + 1][j] = false;
        }
    }
    // Square (B)
    if(usedB < b) dfs(ni, nj, usedA, usedB + 1);
    mat[i][j] = false;
}
​
int main()
{
    scanf("%d%d%d%d", &h, &w, &a, &b);
    dfs(0, 0, 0, 0);
    printf("%d\n", ans);
    return 0;
}
​