T1

这题有点绕 其实可以直接枚举操作1的次数，然后计算经过操作1之后翻转后的字符串的操作2的次数 求最小值

int f(string &s){
    int l=0,r=s.size()-1,cnt=0;
    while(l<r){
        if(s[l]!=s[r]){
            cnt++;
        }
        l++;r--;
    }
    return cnt;
}
void solve(int u) {
    cin>>n>>s;
    int res=1e9;
    for(int i=0;i<n;i++){
        string t=s.substr(i)+s.substr(0,i);
        res=min(res,f(t)+i);
    }
    cout<<res<<endl;
}

T2

线性dp 定义f[i][j]为操作到第i个数的时候 以j结尾的方案数

初始化f[n][w[n]%10]=1

注意：如果本题n=1且w[1]>=10 则其他方案数均为0(这个样例比较狗，当时卡了很久，不写的话只能过96%)

状态转移方程

int a=(w[i]+j)%10,b=(w[i]*j)%10;

f[i][a]+=f[i+1][j]

f[i][b]+=f[i+1][j]

void solve(int u){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    if(n==1){
        if(w[1]>=10){
            for(int i=0;i<10;i++)cout<<0<<" "; 
            return;
        }
    }
    f[n][w[n]%10]=1;
    for(int i=n-1;i>=1;i--){
        for(int j=0;j<10;j++){
            int a=(j+w[i])%10,b=(1ll*j*w[i])%10;
            f[i][a]=(f[i][a]+f[i+1][j])%mod;
            f[i][b]=(f[i][b]+f[i+1][j])%mod;
        }
    }
    for(int i=0;i<10;i++)cout<<f[1][i]<<" ";
}

T3

问题转换为给定n个点，求可以组成正方形的方案数（n<=2500）

可以使用n^2的方式暴力枚举

选两个点找两个方向是否有对应的点，（找的过程可以使用哈希表优化搜索）因为每个边都算了一次，所以答案除以4

unordered_map<int, vector<int>>mp;
bool check(int x, int y) {
    if (mp.count(x)) {
        for (auto& t : mp[x]) {
            if (t == y)return true;
        }
    }
    return false;
}
void solve(int u) {
    cin >> n >> m;
    vector<PII>v;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if (g[i][j] == 'X') {
                v.push_back({i, j});
                mp[i].push_back(j);
            }
        }
    }
    n = v.size();
    ll res = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int x1 = v[i].x, y1 = v[i].y, x2 = v[j].x, y2 = v[j].y;
            int x31 = x1 - (y1 - y2), y31 = y1 + (x1 - x2);
            int x41 = x2 - (y1 - y2),y41 = y2 + (x1 - x2);
            if (check(x31, y31) && check(x41, y41)) {
                res++;
            }
            int x32 = x1 + (y1 - y2), y32 = y1 - (x1 - x2);
            int x42 = x2 + (y1 - y2), y42 = y2 - (x1 - x2);
            if(check(x32,y32)&&check(x42,y42)){
                res++;
            }

        }
    }
    res /= 4;
    cout << res << endl;
}