T1

哈希表记录每个元素对应的位置 最后比较abs(pos[x]-pos[y])==1即可

void solve(int u){
    cin>>n;
    unordered_map<int,int>pos;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        pos[x]=i;
    }
    int x,y;
    cin>>x>>y;
    if(abs(pos[x]-pos[y])==1)puts("Yes");
    else puts("No");
}

T2

把原数组复制一份 即可破环成链 然后使用前缀和计算距离即可(注意分类讨论)

void solve(int u){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        w[i+n]=w[i];
    }
    for(int i=1;i<=n*2;i++){
        sum[i]=sum[i-1]+w[i];
    }
    int x,y;
    cin>>x>>y;
    x--;y--;
    if(x>y)swap(x,y);
    ll res=min(sum[y]-sum[x],sum[x+n]-sum[y]);
    cout<<res<<endl;
}

T3

二维前缀和模板题:注意只能枚举(i,m)和(n,j)的位置的终点

void solve(int u) {
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    ll sum=s[n][m],res=1e18;
    for(int i=1;i<=n;i++){  //枚举切割(i,m)
        ll a=s[i][m],b=sum-a;
        res=min(res,abs(a-b));
    }
    for(int i=1;i<=m;i++){ //枚举切割(n,i)
        ll a=s[n][i],b=sum-a;
        res=min(res,abs(a-b));
    }
    cout<<res<<endl;
}

T4

枚举+DFS求连通块距离

二维坐标映射到一维小技巧:n*m 二维坐标为(i,j)则一维坐标为i*m+j

记得每次开标记数组都需要重新初始化为false

void dfs(int x,int y,vector<vector<bool>>&st){ //dfs将某一个连通块全部标记
    int t=x*m+y;
    st[x][y]=true;
    for(int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i],z=a*m+b;
        if(a<0||a>=n||b<0||b>=m||st[a][b]||s[z]!=s[t])continue;
        dfs(a,b,st);
    }
}
int f(){  //求连通块个数
    vector<vector<bool>>st(n,vector<bool>(m,false));
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!st[i][j]){
                cnt++;
                dfs(i,j,st);
            }
        }
    }
    return cnt;
}
void solve(int u) {
    cin>>k;
    cin>>s;
    int res=k;
    for(int i=1;i<=k;i++){
        if(k%i){  //必须要可以整除
            continue;  
        }
        n=i;m=k/i;
        res=min(res,f());
    }
    cout<<res<<endl;
}

T5

树形dp+数论(数据好像超级弱，应该没有1e9)

check(a,b)乘积是否为完全平方数可以使用质因数分解法：看二者的质因数分解的和的每个质因数的个数是否都是偶数(复杂度logU) U<=1e9

考虑对u节点染色:(u节点和他的子节点x都会被染色)

设f[u][0]表示以u为根节点且u没被染色的最多红色节点个数

f[u][1]表示以u为根节点且u被染色的最多红色节点个数

显然f[u][0]+=max(f[x][1],f[x][0])

对于f[u][1] 只能选择某一个子节点染色 假设选择的子节点为x

f[u][1]=f[u][0]-max(f[x][0],f[x][1])+f[x][0]+2

因此可以遍历子节点 取max即可

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
#define x first
#define y second
typedef long long ll;
const int N=2E5+10,mod=1e9+7;
int T,w[N],n,res;
unordered_set<ll>st;
bool is_st[N];
vector<int>g[N];
int f[N][2];
bool check(int a,int b){
    ll c=sqrt(1ll*a*b);
    return c*c==1ll*a*b;
}
void dfs(int u,int fa){
    if(g[u].size()==1&&g[u][0]==fa)return;
    for(int &x:g[u]){
        if(x==fa)continue;
        dfs(x,u);
        f[u][0]+=max(f[x][0],f[x][1]);
        }
    for(int &x:g[u]){
        if(x==fa)continue;
        int a=w[u],b=w[x];
        if(check(a,b)){
            f[u][1]=max(f[u][1],f[u][0]-max(f[x][0],f[x][1])+2+f[x][0]);
        }
    }

    }
void solve(int u){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0);
    cout<<max(f[1][0],f[1][1])<<endl;

}
int main(){
    T=1;
    for(int i=1;i<=T;i++){
        solve(i);
    }
    return 0;
}