#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int n,m;
int w[N][N];
int f[N*2][N][N];
int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin>>w[i][j];
    for(int k = 2 ; k <= n + m ; k ++)
        for(int x1 = max(1,k - m); x1 <= min(k - 1,n) ; x1 ++)
            for(int x2 = max(1,k - m); x2 <= min(k - 1, n); x2 ++)
            {
                int t = w[x1][k - x1];
                if(x2 != x1) t += w[x2][k - x2];
                for(int a = 0; a <= 1; a ++)
                    for(int b = 0; b <= 1; b ++)
                        f[k][x1][x2] = max(f[k][x1][x2],f[k - 1][x1 -a][x2 - b] + t) ;
            }
    cout<<f[n + m][n][n]<<endl;        
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
int k;
int main()
{
    cin>>k;
    while(k --)
    {
     LL n,d,e;
     scanf("%lld%lld%lld",&n,&d,&e);
     LL m = n - e*d + 2;
     LL dt = m * m - 4 * n;
     LL r = sqrt(dt);
     if(dt < 0 || r * r != dt || (m - r) % 2)puts("NO");
     else cout<<(m - r)/2<<" "<<(m + r) / 2<<endl;
    }
    return 0;
}

快速幂

#include<iostream>
using namespace std;
typedef long long LL;
const int INF = 1e9;
LL qmi(int a,int k)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res =(LL)res * a;
        k >>= 1;
        a = (LL)a * a;
    }
    return res;
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    LL t = qmi(a,b);
    if(abs(t) <= INF)cout<<t;
    else cout<<-1;
    return 0;
}

整棵树的最大高度 = max{子树a的max高度+1，子树b的max高度+2,…}
调换后 = max{子树b的max高度+1,子树a的max高度+2,…}
=> 子树的最大高度 + k = h(x) + k , k是当层结点总数

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int h[N],e[N],ne[N],idx;
void add(int a,int b)
{
    e[idx] = b; 
    ne[idx] = h[a];
    h[a] = idx++;
}
int dfs(int u)
{
    int hmax = 0,cnt = 0;
    for(int i = h[u];~i;i = ne[i]) //~i  => i != -1
    {
        int j = e[i];
        hmax = max(hmax,dfs(j));
        cnt ++;
    }
    return hmax + cnt;
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    //输入的是每个点(2~n)的父节点
    for(int i = 2; i <= n ; i ++)
    {
        int p;
        scanf("%d",&p);
        add(p,i);
    }
    cout<< dfs(1);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 12 , M = 1 << N;//2^N
int n, m ;
LL f[N][M];
vector<int>state[M];//所有合法状态
bool st[M];//某列是否合法，所有连续零的个数是否偶数个
int main()
{
    while(cin>>n>>m ,n || m)
    {
        //预处理st[]数组,枚举所有状态找出合法状态
        for(int i = 0; i < 1<<n ; i ++) // i < 2^n
        {
            int cnt = 0; //零的个数
            bool is_valid = true;//是否合法
            for(int j = 0; j < n; j ++)
                if(i >> j & 1) //当前位数是1
                {
                    //判断前面的零的个数是否为偶数
                    if(cnt & 1) //奇数
                    {
                        is_valid = false;
                        break;
                    }
                    cnt = 0;
                }
                else cnt ++;
            if(cnt & 1)is_valid = false;//最后一位，所有0的个数为奇数，不合法
            st[i] = is_valid;
        }    
        //枚举所有合法状态
        for(int i = 0; i < 1<<n; i ++)
        {
            state[i].clear();//清空
            for(int j =0 ; j < 1<<n ; j ++)
                if((i & j) == 0 && st[i | j])
                    state[i].push_back(j);
        }
        memset(f,0,sizeof f);
        f[0][0] = 1;
        for(int i = 1; i <= m ; i ++)
            for(int j = 0; j < 1 << n; j ++)
                for(auto k : state[j])
                    f[i][j] += f[i - 1][k];
        cout<<f[m][0]<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int>PII;
const int N = 1010,M =60,INF = 1e8;
int n,m,k;
PII tree[N];
int b[M][M];
int main()
{
    cin>>n>>m>>k;
    //绿化带A中树的坐标
    for(int i = 0 ; i < n ; i ++)scanf("%d%d",&tree[i].x,&tree[i].y);

    //藏宝图B中树的个数
    int tc = 0;
    for(int i = k; i >= 0; i --)
        for(int j = 0; j <= k; j ++)
        {
            scanf("%d",&b[i][j]);
            tc += b[i][j];
        }
    int res = 0;
    for(int i = 0; i < n ; i ++)
    {
        //有树的地方扩展后可能对应藏宝图
        int sx = tree[i].x,sy = tree[i].y;
        if(sx + k > m || sy + k > m)continue;
        //绿化带中对应区域多少棵树
        int cnt = 0;
        for(int j = 0; j < n; j ++)
        {
            int x = tree[j].x, y = tree[j].y;
            if(x >= sx && x - sx <= k && y >= sy && y - sy <= k)
            {
                //不匹配，如果直接退出的话cnt可能等于tc，所以用负无穷容错
                if(!b[x - sx][y - sy])cnt = -INF; 
                else cnt ++;
            }
        }
        if(cnt == tc) res ++;
    }
    cout<<res;
    return 0;
}

台阶Nim游戏:
a1 ^ a3 ^ a5 … ^an = x != 0 先手必胜
只要保证奇数台阶始终相等就能胜利
如果对方动的是偶数台阶，只需要下移到下一台

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    int res = 0;
    cin>>n;
    for(int i = 1; i <= n ; i ++)
    {
        int x;
        cin>>x;
        if(i % 2) res ^= x;
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

Nim游戏定理：
a1 ^ a2 ^ … ^an = 0 先手必败
a1 ^ a2 ^ … ^an = x != 0 先手必胜

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int res;
    while(n --)
    {
        int x;
        scanf("%d",&x);
        res ^= x;
    }
    if(res)puts("Yes");
    else puts("No");
    return 0;
}

f[k,i1,i2] : 所有从(1,1),(1,1) 分别到(i1,k - i1) , (i2,k - i2)的最大长度路径
k = i1 + j1 = i2 + j2
状态转移:max(f[k-1][][]) + [重合:w[i1][j1] || 不重合:w[i1][j1] + w[i2][j2] ]
其中max(f[k-1][i1 - 1][i2 -1],f[k-1][i1-1][i2],f[k-1][i1][i2-1],f[k-1][i1][i2]
也就是以下四种转移情况：
第一条：下 下 右 右
第二条：下 右 下 右

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 20;
int n;
int w[N][N];
int f[N*2][N][N];
int main()
{
    int a,b,c;
    cin>>n;
    while(cin>>a>>b>>c,a||b||c) w[a][b] =  c;
    for(int k = 2; k <= n + n; k ++)
        for(int i1 = 1; i1 <= n ; i1 ++)
            for(int i2 = 1 ;i2 <= n ; i2 ++)
            {
                int j1 = k - i1, j2 = k - i2;
                //如果存在
                if(j1 > 0 && j2 > 0 && j1 <= n && j2 <= n)
                {
                    int t = w[i1][j1]; //重合情况
                    int &x =f[k][i1][i2];//用x代替表达
                    if(i1 != i2)t = w[i1][j1] + w[i2][j2]; //不重合情况
                    x = max(x,f[k-1][i1 - 1][i2 -1] + t);
                    x = max(x,f[k-1][i1][i2-1] + t);
                    x = max(x,f[k-1][i1-1][i2] + t);
                    x = max(x,f[k-1][i1][i2] + t);
                }
            }
    cout << f[n + n][n][n];
    return 0;
}

//差分算法
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N =200010;
int n , m , k ;
int b[N];
int main()
{
    cin>>n>>m>>k;
    while(n--)
    {
        int t,c;
        scanf("%d%d",&t,&c);
        int l = t - k - c + 1, r  = t - k;
        if(r > 0)b[max(1,l)] ++,b[r + 1] --;
    }
    for(int i = 1 ; i < N ;i ++)b[i] += b[i-1];
    while(m --)
    {
        int  t;
        scanf("%d",&t);
        cout<<b[t]<<endl;
    }
    return 0;
}