8.12 京东笔试（后端）

3a

第一题：字符串（操作1：字符串的第一位移到最后一位，操作2：某个位置的字母为任意字母）求最少操作使字符串变成回文串

#include <iostream>
using namespace std;
int n;
string s;
int solve(int pos){
    int ans=0;
    for(int i=pos;i<(pos+n +pos)/2;i++){
        if(s[i]!=s[pos+n-i-1+pos]){
            ans++;
        }
    }
    return pos+ans;
}
int main() {
    cin>>n>>s;
    s+=s;
    int ans=1e9;
    for(int pos=0;pos<n;pos++){
        ans=min(ans,solve(pos));
    }    
    cout<<ans<<endl;
}
// 64 位输出请用 printf("%lld")

第二题，对数组最后两个数可以执行两个操作，操作1：(x+y)%10, 操作2：（x*y)%10，操作完后将最后两位删除，操作1或操作2的值加入数组最后一位，共执行n-1次操作，求数组剩下的数分别为0，1，2，..., 9的方案数

#include <iostream>
using namespace std;
#define int long long
const int maxn=2e5+100;
const int mod=1e9+7;
int a[maxn];
int n;
int dp[maxn][10];
signed main() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n==1&&a[n]>=10){
        for(int i=0;i<10;i++){
            cout<<"0 ";
        }
        return 0;
    }
    dp[0][a[n]%10ll]=1;
    for(int i=1;i<=n-1;i++){
        int pos=n-i;
        
        for(int num=0;num<10;num++){
            //操作1
            dp[i][(num+a[pos])%10ll]+=dp[i-1][num];
            dp[i][(num+a[pos])%10ll]%=mod;  
            //操作2
            dp[i][(num*a[pos])%10ll]+=dp[i-1][num];
            dp[i][(num*a[pos])%10ll]%=mod;
        }
    }
    for(int i=0;i<10;i++){
        cout<<dp[n-1][i]<<" ";
    }
    puts("");
}
// 64 位输出请用 printf("%lld")

第三题 求图上所有的4个点组成正方形的总方案数，最多2500个点

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

string s[55];
int n,m;
bool cmp(pair<int,int> &a,pair<int,int> &b){
    return a.first<b.first&&a.second<b.second;
}
vector<pair<int,int> >node;
map<pair<int,int>,int> mp;

pair<int,int> del(pair<int,int> &a,pair<int,int> &b){
    return {(a.first-b.first),(a.second-b.second)};
}
pair<int,int> add(pair<int,int> &a,pair<int,int> &b){
    return {{a.first+b.first},{a.second+b.second}};
}
bool check(pair<int,int> dir1,pair<int,int> dir2,pair<int,int> be){
    pair<int,int> p1=add(be,dir1);
    pair<int,int> p2=add(be,dir2);
    pair<int,int> p3=add(p2,dir1);
    if(mp[p1]==1&&mp[p2]==1&&mp[p3]==1) {
		
		//printf("(%d,%d),(%d,%d),(%d,%d),(%d,%d)\n",be.first+1,be.second+1,p1.first+1,p1.second+1,p2.first+1,p2.second+1,p3.first+1,p3.second+1);
		return 1;
	}
    else return 0;
    
}
int main() {
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='X'){
                node.push_back({i,j});
                mp[{i,j}]=1;
            }
        }
    }
    int ans=0;
    for(int i=0;i<node.size();i++){
        pair<int,int> be=node[i];
        for(int j=i+1;j<node.size();j++){
            pair<int,int> next=node[j];
            pair<int,int> dir1=del(next,be);
            pair<int,int> dir2={-dir1.second,dir1.first};

        	if(check(dir1,dir2,be)){
        		ans++;
			}

        }
    }
    cout<<ans/2<<endl;
}
/*
4 4
XX..
XXX.
.X.X
..X.
*/