牛客小白月赛70

A.小d和答案修改

收获isupper函数。

B.小d和图片压缩

关键在于找到坐标的对应关系，或者将每个小方格加到左上角。

C.小d和超级泡泡堂

简单dfs。

D.小d和孤独的区间

只包含1个1的区间可以用总区间数减去2端的区间数，也可以直接由左端点的个数乘以右端点的个数得到。

E.小d的博弈

 博弈

1.考虑简单情况或边界情况，能够由此递推出别的情况。

2.考虑可维持的状态，无论一方怎样操作，另一方总是能通过操作(如模仿棋)抵消影响。

3.考虑打表找规律。

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;

const int N=110;
int f[N][N];

int dfs(int x,int y){
    if(x<y)return dfs(y,x);
    if(~f[x][y])return f[x][y];
    //在博弈问题中，状态一定是必胜或必输的
    //如果能到达必输状态就必胜，否则必输
    for(int i=1;i<x;i++){
        if(i>=x-i)break;
        int t=dfs(i,y);
        if(t==0)return f[x][y]=1;
    }
    for(int i=1;i<x;i++){
        if(i>=y-i)break;
        int t=dfs(x,i);
        if(t==0)return f[x][y]=1;
    }
    return f[x][y]=0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(f,-1,sizeof f);
    for(int i=1;i<=50;i++){
        for(int j=1;j<=50;j++){
            cout<<(dfs(i,j)?"O":"X");
        }
        cout<<endl;
    }
    return 0;
}

该题由打表结果可知，如果n+1和m+1的二进制位相等先手必败，否则必胜。

可维持的状态就是这个二进制位想等，如果初始不相等便可经过一次操作相等，而初始相等则怎样都无法逃脱这个局面。

最终无法操作的局面就是二进制位相等。

如果不打表还是很难发现这个的，所以不要蛮干，要有方法。

F.小d和送外卖

树上背包

待补。。。