Problem D 

题目大意：有n行，每行有ki 个数，你没次能进行一次操作就是将所有数加1，这些数的上限是c，如果大于c则变成1，

问你有没有存在一个操作次数m使得每行的字典序上升。

思路：我们找出每两行之间决定他们字典序大小的两个数，每两个都能求出一次操作数的范围，然后就是看存不存在

一个范围所有区间都覆盖，差分标记一下就好啦。

#include
      
       #define pii pair
       
        #define mk make_pairusing namespace std;const int N=5*1e5+5;const int M=2e6+5;vector
        
          a[M],b[M];vector
         
           c[M],d[M];int vis[M];int n,w,cnt;int main(){    scanf("%d%d",&n,&w); w--;    for(int i=1;i<=n;i++)    {        int k; scanf("%d",&k);        a[i].resize(k);        for(int j=0;j
          
           a[i+1][j])            {                b[a[i][j]].push_back(a[i+1][j]);                flag=true;                break;            }            else if(a[i][j]
           
            a[i+1].size()) { puts("-1"); return 0; } } for(int i=0;i<1e6;i++) { if(!b[i].size()) continue; int mx=-1,mn=1e6+5,mx2=-1,mn2=1e6+5,add=w-i+1; for(int j:b[i]) { mx=max(mx,j); mn=min(mn,j); mx2=max(mx2,(j+add)%(w+1)); mn2=min(mn2,(j+add)%(w+1)); } cnt++; if(mn>i) { c[0].push_back(cnt); d[w-mx].push_back(cnt); c[w-i+1].push_back(cnt); d[2*w-mx].push_back(cnt); } else { c[add].push_back(cnt); d[add+w-mx2].push_back(cnt); } } int ans=0; for(int i=0;i<1e6;i++) { for(int j:c[i]) { if(!vis[j]) ans++; vis[j]++; } if(ans==cnt) { printf("%d\n",i); return 0; } for(int j:d[i]) { if(vis[j]==1) ans--; vis[j]--; } } puts("-1"); return 0;}
           
          
         
        
       
      

 

Problem E

题目大意：给出n个数，有两个人，每次从这些数的最左边拿走k个数，范围为2~m。特别之处在于，拿走后会把

拿走的数的和作为一个新的数放在最左边，要求两个人拿走数之差的最大值。

 

思路：先求一遍前缀和，问题就变成了：一排数，两个人轮流取数，保证取的位置递增（且从第二个数开始取），

每个人要使自己取的数的和尽量大，求在最优策略下取的max(先手和-后手和)。

dp[ i ]表示，将前i个看成一堆，先手的最优答案，又有dp[ n-1 ]=sum[ n ]，那么我们就能从后往前推，导出状态

转移方程，dp[ i ]=max(sum[j] - dp[ j ])  i < j <=n，这个状态转移方程的意思表示，对dp[ i ]来说先手取了第j个sum

然后还要减去第二个人先手的最优值。

1 #include
      
        2 #define ll long long 3 using namespace std; 4 const int N=2*1e5+5; 5 const int inf=1e18; 6 int n; 7 ll a[N],sum[N],dp[N]; 8 int main() 9 {10     scanf("%d",&n);11     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);12     for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];13     ll mx=sum[n];14     for(int i=n-1;i>=1;i--)15     {16         dp[i]=mx;17         mx=max(mx,sum[i]-dp[i]);18     }19     printf("%lld\n",dp[1]);20     return 0;21 }