因为一些原因题解迟到了，以后我争取当天或次日就搞定

 

读完发现这题跟牛客练习赛41C题差不多啊，于是想了一下并查集但没什么思路

考虑到存在u->v的边那么u就不需要选择，但是当路径构成环的时候，我们只需

要取环上最小值就可以了。

1 #define IO std::ios::sync_with_stdio(false); 2 #include 
     
       3 using namespace std; 4 typedef long long ll; 5 typedef double db; 6 int n; 7 ll a[200005],g[200005],vis[200005]; 8 ll ans=0; 9 ll mi,id;10 void dfs(int u){11     if(vis[u]){12         id=u;13         mi=a[u];14         return;15     }16     vis[u]=1;17     dfs(g[u]);18     if(id==u)ans+=mi;19     else mi=min(mi,a[u]);20 }21 int main(){22     IO;23     cin>>n;24     for(int i=1;i<=n;i++)cin>>a[i];25     for(int i=1;i<=n;i++)cin>>g[i];26     for(int i=1;i<=n;i++){27         if(!vis[i])dfs(i);28     }29     cout<
      
       <
      
     

 

 

有点恶心的水题，分情况讨论即可

1 #define IO std::ios::sync_with_stdio(false); 2 #include 
      
        3 using namespace std; 4 typedef long long ll; 5 typedef double db; 6 ll n,q,x,y; 7 int main(){ 8     IO; 9     cin>>n>>q;10     while(q--){11         cin>>x>>y;12         ll k=n*n/2;13         if(n%2)k++;14         if(n%2){15             if((x+y)%2){16                 if(x%2){17                     ll h=(x-1)*n/2;18                     h+=y/2;19                     cout<
       
        <
       
      

 

设长为x,宽为y，现在要使p^2/s=4(x+y)^2/(x*y)=4(x/y+y/x)最小

显然当x与y差最小的时候原式最小，当x==y时也就是有一个数的出现了4次以上时

直接输出就好，其余情况我们可以先筛出现2次以上的数然后用double算一下更新答案

1 #define IO std::ios::sync_with_stdio(false); 2 #include 
       
         3 using namespace std; 4 typedef long double ldb; 5 typedef long long ll; 6 typedef double db; 7 int T,n; 8 ll a[1000005],c[10005],b[10005]; 9 int main(){10     IO;11     cin>>T;12     while(T--){13         cin>>n;14         memset(b,0,sizeof(b));15         int v=0;16         for(int i=1;i<=n;i++){17             cin>>a[i];18             b[a[i]]++;19             if(b[a[i]]>=4&&!v){20                 v=a[i];21             }22         }23         if(v){24             for(int i=1;i<=4;i++){25                 cout<
        
         <<" ";26             }27             continue;28         }29         sort(a+1,a+1+n);30         int h=unique(a+1,a+1+n)-a-1;31         ll x,y,id;32         int cnt=0;33         for(int i=1;i<=h;i++){34             if(b[a[i]]>=2)c[++cnt]=a[i];35         }36         db res=1e18;37         for(int i=1;i
        
       

 

 

显然当差为2或0时可以转换，其余都不可以

1 #define IO std::ios::sync_with_stdio(false); 2 #include 
       
         3 using namespace std; 4 typedef long long ll; 5 typedef double db; 6 int T,n; 7 char s[1005]; 8 int main(){ 9     IO;10     cin>>T;11     while(T--){12         cin>>n;13         cin>>s+1;14         int flag=0;15         for(int i=1;i<=n/2;i++){16             int h=abs(s[i]-s[n-i+1]);17             if(h>2||h==1){18                 flag=1;19                 break;20             }21         }22         if(flag)cout<<"NO"<
       

 

送分题，从上到下dp取最大，应该没有比这还简单的dp了。。。代码不写了(随便写都能过)

看到数据n<=100，直接枚举每个点跑最短路就完事了，代码略

这题我当时在纸上博弈发现n=1，3，7时先手必败，

发现当n为2^k-1时必输，其余情况先手必胜。

后来发现好多人都是直接看n的奇偶性。。。

然后还全过了。。。。。

然后就有人发现return 0就可以ac。。。

最后发现E,F也是这样。。。

所以中南oj管理员删库跑路了？

本场最难的题，用到了xls最喜欢的线段树，罗总的题解写得很好，大家可以看一下

仔细读题发现只要当前钱数大于商品价格总和就一定可以满足要求

1 #define IO std::ios::sync_with_stdio(false); 2 #include 
       
         3 using namespace std; 4 typedef long long ll; 5 int T; 6 int n,m; 7 ll x; 8 ll a[100005]; 9 int b[100005];10 int main(){11     IO;12     cin>>T;13     while(T--){14         cin>>n>>m;15         ll res=0;16         for(int i=1;i<=n;i++){17             cin>>x;18             res+=x;19         }20         int cnt=0;21         while(m--){22             cin>>x;23             if(x>res)b[++cnt]=1;24             else b[++cnt]=0;25         }26         for(int i=1;i<=cnt;i++){27             cout<
       

一开始都错题以为拿出数会拿很多轮然后感觉不可做，后来发现只有一轮。。。

那么我们可以单独考虑拿第一个数和最后一个数的期望，

然后预处理出相隔两个数的差的前缀和以及后缀和

最后再取最大值加入到答案里就ok

1 #define IO std::ios::sync_with_stdio(false); 2 #include 
       
         3 using namespace std; 4 typedef long long ll; 5 typedef double db; 6 int T,n; 7 int a[100005],b[100005],c[100005]; 8 int main(){ 9     IO;10     cin>>T;11     while(T--){12         cin>>n;13         for(int i=1;i<=n;i++){14             cin>>a[i];15             b[i]=c[i]=0;16         }17         for(int i=2;i<=n;i++){18             b[i]=max(b[i-1],abs(a[i]-a[i-1]));19         }20         for(int i=n-1;i>=1;i--){21             c[i]=max(c[i+1],abs(a[i]-a[i+1]));22         }23         ll ans=b[n-1]+c[2];24         for(int i=2;i
       

 

首先求出>=m的数的个数的前缀和，然后计算以i为起点的序列的个数

直接枚举会超时，考虑到前缀和肯定是单调递增的，那么我们二分查找刚好有k个数>=m的位置h，

那么以第h到第n之间的数结尾的都是满足条件的序列。

1 #define IO std::ios::sync_with_stdio(false); 2 #include 
       
         3 using namespace std; 4 typedef long long ll; 5 typedef double db; 6 int T,n,m,k; 7 int a[200005],b[200005]; 8 int main(){ 9     IO;10     cin>>T;11     while(T--){12         cin>>n>>m>>k;13         for(int i=1;i<=n;i++){14             cin>>a[i];15             b[i]=b[i-1];16             if(a[i]>=m)b[i]++;17         }18         ll ans=0;19         for(int i=1;i<=n-k+1;i++){20             int x=b[i-1];21             if(x+k>b[n])break;22             int h=lower_bound(b+i,b+1+n,k+x)-b;23             ans+=n-h+1;24         }25         cout<
        
         <
        
       

本场第二难得题，看网上题解才补出来，用到了分段式dp，d[i][j][k][p]表示三个人分别在i,j,k城得时候第p个人准备移动时得方案数

为什么从后往前dp呢?这道题没有初始状态因为题目里说了每个边u->v都有v>=u，那么最后当所有人都在n城就是一个确定的最终状态，

由此我们可以从后往前转移状态，时间复杂度n^4。

1 #define IO std::ios::sync_with_stdio(false); 2 #include 
       
         3 using namespace std; 4 typedef long long ll; 5 typedef double db; 6 const int N=55; 7 ll mod=998244353; 8 ll T,n,m,h,q,x,y,z; 9 ll d[N][N][N][4];10 ll w[N],g[N][N];11 void add(ll &x,ll y){12     x=(x+y)%mod;13 }14 int main(){15     IO;16     cin>>T;17     while(T--){18         memset(g,0,sizeof(g));19         memset(d,0,sizeof(d));20         cin>>n>>m>>h>>q;21         for(int i=1;i<=n;i++)cin>>w[i];22         for(int i=1;i<=m;i++){23             cin>>x>>y;24             g[x][y]=1;25         }26         for(int i=n;i>=1;i--){27             for(int j=n;j>=1;j--){28                 for(int k=n;k>=1;k--){29                     if(abs(w[i]-w[j])<=h&&abs(w[i]-w[k])<=h&&abs(w[j]-w[k])<=h){30                         add(d[i][j][k][1],1);31                     }32                     else d[i][j][k][1]=0;33                     if(d[i][j][k][1]){34                         for(int z=1;z
        
         >x>>y>>z;53             cout<
         
          <