R49 A-D D图有向有环图

A. Palindromic Twist

给一个字符串（小写字母）   每个字符+1，-1；变成其他字符  a只能变b  z只能变y 看能否变成回文字符串

#include<bits/stdc++.h>
using namespace std;
int32_t main()
{
     int T; cin>>T;
     while(T--)
     {
         int n; cin>>n;
         string ss; cin>>ss;
         int t=1;
         for(int i=0;i<n/2;i++)
         {
             if(ss[i]-ss[n-1-i]==0||fabs(ss[i]-ss[n-1-i])==2)
                continue;
             else t=0;
         }
          if(t==0) cout<<"NO"<<endl;
          else cout<<"YES"<<endl;
     }
}

B. Numbers on the Chessboard

分类讨论下就ok了

#include<bits/stdc++.h>
#define int long long
#define MAX(a,b,c) max(a,max(b,c))
#define MIN(a,b,c) min(a,min(b,c))
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned long long uLL;
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
int32_t main()
{
     int n,q; cin>>n>>q;
     if(n%2==0)
     {
         int ans1=0;
         int ans2=n*n/2;
         while(q--)
         {
             int a,b;cin>>a>>b;
             if( (a+b)%2==0 ) cout<<ans1+(a-1)*n/2+(b+1)/2<<endl;
             else   cout<<ans2+(a-1)*n/2+(b+1)/2<<endl;
         }
     }
     else if(n%2==1)
     {
         int ans1=0;
         int ans2=n*n/2+1;
         while(q--)
         {
             int a,b;cin>>a>>b;
             if( (a+b)%2==0 )
             {
                 if(a%2==1) cout<<(a-1)/2*n+(b+1)/2<<endl;
                 else if(a%2==0) cout<<(a-2)/2*n+(n+1)/2+(b+1)/2<<endl;
             }
             else
             {
                 if(a%2==1) cout<<ans2+(a-1)/2*n+(b+1)/2<<endl;
                 else if(a%2==0) cout<<ans2+(a-2)/2*n+(n-1)/2+(b+1)/2<<endl;
             }
         }
     }
}

C. Minimum Value Rectangle

  要使    4*（a+b）（a+b）/a*b  （a<b） 即使  b/a 最小  排序后暴力也可以   直接找b/a 最小也行。

#include<bits/stdc++.h>
#define int long long
#define MAX(a,b,c) max(a,max(b,c))
#define MIN(a,b,c) min(a,min(b,c))
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned long long uLL;
using namespace std;
const int maxn=3e6+10;
const int INF=0x3f3f3f3f;
int a[maxn];
int b[maxn];
int32_t main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int T;cin>>T;
     while(T--)
     {
         
         int n; cin>>n;
         for(int i=1;i<=n;i++)  cin>>a[i];
         sort(a+1,a+1+n);
         int t=0;
         for(int i=1;i<n;i++)
         {
             if(a[i]!=a[i+1])  continue;
             else { b[++t]=a[i]; i++;}
         }
         double ans=1e18;
         int x,y;
         for(int i=1;i<t;i++)
         {
             double c=(b[i]*1.000000000000/b[i+1])+b[i+1]*1.000000000000/b[i];
             if(c<ans)
             {
                 ans=c;
                 x=b[i]; y=b[i+1];
             }
         }
         cout<<x<<" "<<x<<" "<<y<<" "<<y<<endl;
     }
}

D. Mouse Hunt

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
int c[maxn];
int a[maxn];
int x[maxn];
int sst[maxn];
int ffind(int x)
{
    if(x==sst[x]) return x;
    return sst[x]=ffind(sst[x]);
}
int dfs(int x, int y){
    if(x == y) return c[x];
    return min(dfs(a[x], y), c[x]);
}
int main()
{
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) sst[i]=i ;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        if(ffind(a[i])==ffind(i))
        {
            x[i]=1;
          //  continue;
        }
        else
        {
            sst[ffind(a[i])]=ffind(i);
        }
       /* for(int i=1;i<=n;i++)
        {
            cout<<i<<"=="<<sst[i]<<"  ";
        }cout<<endl;
        for(int i=1;i<=n;i++)
        {
            cout<<x[i]<<"----  ";
        }cout<<endl;*/
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        //cout<<i<<endl;
        if(x[i]) ans += dfs(a[i], i);
        //cout<<ans<<endl;
    }
    printf("%d
", ans);
    return 0;
}