T1#include<bits/stdc++.h>using namespace std;using ll=long long;const int maxl=1e6+10;int n,m,tot,ans;int a[maxl];char s[maxl];inline void prework(){ cin>>n; for(int i=1;i<=n;i++) {  int x;cin>>x;  a[x]=i; } int x,y;cin>>x>>y; if(abs(a[x]-a[y])==1)  puts("Yes"); else  puts("No");}inline void mainwork(){ }inline void print(){ }int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); prework(); mainwork(); print(); return 0; }T2#include<bits/stdc++.h>using namespace std;using ll=long long;const int maxl=1e6+10;int n,m,tot;ll ans;ll a[maxl],sum[maxl];char s[maxl];inline void prework(){ cin>>n; for(int i=1;i<=n;i++) {  cin>>a[i],sum[i]=sum[i-1]+a[i];  a[i+n]=a[i]; } for(int i=n+1;i<=2*n;i++)  sum[i]=sum[i-1]+a[i]; int x,y; cin>>x>>y; if(x>y)  swap(x,y); ll ans=min(sum[y-1]-sum[x-1],sum[x+n-1]-sum[y-1]); cout<<ans;}inline void mainwork(){ }inline void print(){ }int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); prework(); mainwork(); print(); return 0; }T3#include<bits/stdc++.h>using namespace std;using ll=long long;const int maxl=1e3+10;int n,m,tot;ll ans;int a[maxl][maxl];ll row[maxl],col[maxl];char s[maxl];inline void prework(){ cin>>n>>m; for(int i=1;i<=n;i++)  for(int j=1;j<=m;j++)  {   cin>>a[i][j];   row[i]+=a[i][j];   col[j]+=a[i][j];  }}inline void mainwork(){ ll you=0,xia=0,zuo=0,shang=0; for(int j=1;j<=m;j++)  you+=col[j]; ans=you;xia=you; for(int j=1;j<m;j++) {  you-=col[j];  zuo+=col[j];  ans=min(ans,abs(you-zuo)); } for(int i=1;i<n;i++) {  shang+=row[i];  xia-=row[i];  ans=min(ans,abs(shang-xia)); }}inline void print(){ cout<<ans;}int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); prework(); mainwork(); print(); return 0; }T4 因为一定要整除，所以枚举所有因数就行了，然后构造完以后bfs或者dfs搞flood fill求连通块个数，O(nsqrt(n))#include<bits/stdc++.h>using namespace std;using ll=long long;const int maxl=1e6+10;int n,m,tot,ans;int a[maxl];string s;int tx[4]={0,1,0,-1};int ty[4]={1,0,-1,0};inline void prework(){ cin>>n; cin>>s;}inline void solv(int c){ vector<string> b;int nowid=0; int r=n/c; for(int i=1;i<=r;i++) {  b.emplace_back(s.substr(nowid,c));  nowid+=c; } vector<vector<int>> vis(r,vector<int>(c,0));  auto bfs=[&](int ix,int iy) ->void {  using pii=pair<int,int>;  queue<pii> q;  q.push({ix,iy});vis[ix][iy]=true;  char ch=b[ix][iy];  while(q.size())  {   pii d=q.front();q.pop();   for(int k=0;k<4;k++)   {    int x=d.first+tx[k],y=d.second+ty[k];    if(x<0 || x>=r || y<0 || y>=c ||      vis[x][y] || ch!=b[x][y])      continue;    vis[x][y]=1;    q.push({x,y});   }  } }; int cnt=0; for(int i=0;i<r;i++)  for(int j=0;j<c;j++)  if(!vis[i][j])  {   cnt++;   bfs(i,j);  } ans=min(ans,cnt);}inline void mainwork(){ ans=n;int up=sqrt(n); for(int i=1;i<=up;i++) if(n%i==0)  solv(i),solv(n/i);}inline void print(){ cout<<ans;}int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); prework(); mainwork(); print(); return 0; }T5 设dp[u][1]表示u为染红点，某个子节点也染红，u子树最多的染色点个数，dp[u][0]则表示u不染色的子树最多个数。可以注意到dp[u][1]如果选择把a[u]和a[v]染红，那么转移的时候v只能选择dp[v][0]，因为要求v之前不被染色#include<bits/stdc++.h>using namespace std;using ll=long long;const int maxl=1e6+10;int n,m,tot,ans;ll a[maxl];int dp[maxl][2];char s[maxl];vector<int> e[maxl];inline void prework(){ cin>>n; for(int i=1;i<=n;i++)  cin>>a[i]; for(int i=1;i<n;i++) {  int u,v;cin>>u>>v;  e[u].emplace_back(v);  e[v].emplace_back(u); }}inline bool x2(ll x,ll y){ ll d=sqrt(x*y); return d*d==x*y;}inline void dfs(int u,int fa){ for(int &v:e[u]) {  if(v==fa) continue;  dfs(v,u);  dp[u][0]+=max(dp[v][1],dp[v][0]); } for(int &v:e[u]) {  if(v==fa || !x2(a[u],a[v])) continue;  dp[u][1]=max(dp[u][1],dp[u][0]-max(dp[v][0],dp[v][1])+2+dp[v][0]); }}inline void mainwork(){ dfs(1,0); ans=max(dp[1][0],dp[1][1]);}inline void print(){ cout<<ans;}int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); prework(); mainwork(); print(); return 0; }