T1

這題有點繞 其實可以直接枚舉操作1的次數(shù)，然后計算經(jīng)過操作1之后翻轉(zhuǎn)后的字符串的操作2的次數(shù) 求最小值

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個數(shù)的時候 以j結(jié)尾的方案數(shù)

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

注意：如果本題n=1且w[1]>=10 則其他方案數(shù)均為0(這個樣例比較狗，當(dāng)時卡了很久，不寫的話只能過96%)

狀態(tài)轉(zhuǎn)移方程

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

問題轉(zhuǎn)換為給定n個點，求可以組成正方形的方案數(shù)（n<=2500）

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

選兩個點找兩個方向是否有對應(yīng)的點，（找的過程可以使用哈希表優(yōu)化搜索）因為每個邊都算了一次，所以答案除以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;
}