题目
codeforces round 376 Div2
题解
D
题意：给一些字符串，每次可以将所有字符序数+1，字符可以循环，问如何变幻使得其按字典序排列。
题解：枚举相邻两个字符串，求出如果这两个满足字典序要求，转动次数的范围，用差分，最后看一下有没有被覆盖n-1次的点。
//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=500000+10;
const int maxv=1e6+10;
inline int read()
{int ret=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';return ret;
}int L,R,n,c;
int *s[maxn],len[maxn],D[maxv];inline void ADD(int l,int r){
if(l>r) return ;D[l]++;D[r+1]--;}int main()
{cin>>n>>c;for(int i=1;i<=n;i++){len[i]=read();s[i]=new int [len[i]+10];for(int j=1;j<=len[i];j++) s[i][j]=read();}for(int i=1;i<n;i++){for(int p=1;;p++){if(p==len[i]+1) //这两个判断是判断前缀关系{ADD(0,c-1);break;}if(p==len[i+1]+1) //如果后面是前面的前缀则无解，否则均可{
printf("-1\n");return 0;}if(s[i][p] < s[i+1][p]) //分两种计算范围，注意:即使已经满足要求也可以将两个均‘爆掉’，不要漏掉第二个ADD{ADD(0,c-s[i+1][p]);ADD(c-s[i][p]+1,c-1);break;}if(s[i][p] > s[i+1][p]) {ADD(c-s[i][p]+1,c-s[i+1][p]);break;}}}int sum=0;for(int i=0;i<=c-1;i++) if((sum+=D[i]) >= n-1) {
printf("%d\n",i);return 0;}printf("-1");return 0;
}
E
题意：有一个游戏，有一排纸片，上面写了一些数字，两人轮流操作，可以从左边拿走2~m（m为剩下纸片个数）片，然后将总和计入自己得分。每次操作完后会在最左边放上一张新纸片，上面的数字为取走数字的总和。策略：使得自己与别人得分分差最大，问先手与后手的分差。
题解：算是比较简单的线段树优化DP。发现用一个数字i就能够表示状态，因为最左边那块纸片总是之前的纸片的总和。当第i个纸片变为新纸片时称为状态i，用dp（i）表示i状态下的max{先手得分（下称为A）-后手得分（下称为B）}，那就要决策这一步选什么，发现当前这步的先手是下个状态的后手，假如我取到j，那么A-B=-（dp（j）-sum（j）），注意要加’-‘，然后发现要取max{dp(j)-sum(j)},i+1<=j<=n 是个裸的线段树优化DP。
//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF=-1*(1ll<<60);
const int maxn=200000+10;
inline int read()
{int ret=0,ok=1;char ch=getchar();while(ch<'0'||ch>'9') {
if(ch=='-')ok=-1;ch=getchar();}for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';return ret*ok;
}int a[maxn];
ll dp[maxn],sum[maxn];
//dp[i]表示i状态下的 max{先手-后手} struct Node{ll m;Node *lc,*rc;Node(){m=INF,lc=rc=NULL;}inline void UP(){m=max(lc->m,rc->m);}
}*root;#define mid ((l+r)>>1)
void build(Node* &p,int l,int r)
{p=new Node();if(l==r) return ;build(p->lc,l,mid);build(p->rc,mid+1,r);p->UP();
}void updata(Node* &p,const int &pos,const ll& val,int l,int r)
{if(l==r) {p->m=val;return ;}if(pos<=mid) updata(p->lc,pos,val,l,mid);else updata(p->rc,pos,val,mid+1,r);p->UP();
}ll query(Node* &p,int l,int r,const int &L,const int &R)
{if(L<=l&&r<=R) return p->m;ll ret=INF;if(L<=mid) ret=max(ret,query(p->lc,l,mid,L,R));if(mid<R ) ret=max(ret,query(p->rc,mid+1,r,L,R));return ret;
}int main()
{int n=read();build(root,1,n);for(int i=1;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i];updata(root,n,sum[n],1,n);for(int i=n-1;i>=1;i--){dp[i]=query(root,i+1,n,1,n);updata(root,i,-dp[i]+sum[i],1,n);}cout<<dp[1];return 0;;
}
F
题意：给一堆游戏卡片以及它们的分值，选一张当主卡（称为A），将剩下所有卡（称为B）进行如下处理，如果B%A==0,将B加入总答案，否则将B/A*A加入总答案（整除），问答案最大值。
题解：（1000+AC人数的F题。。）不难发现按升序排序后，枚举选的主卡，最优方案一定是把右边的全选了。也不难发现，如果存在i< j&&a[j]%a[i]==0, 那么选i当主卡肯定更优。所以采取如下策略，枚举i，如果当前的a[i]没有被标记，那就从2*a[i]，3 * a[i]一直枚举到最大值，把这些数都打上标记（像极了筛素数？）。可以证明这一步的复杂度不超过nlogn,其实计算答案只要搞一点事情就行了，用sum[i]表示不超过i的数有多少个，注意到a[i]~2 * a[i]-1范围内的数对答案贡献是一样的，所以在枚举k *a[i]时顺便计算答案，总复杂度O(nlogn)
//QWsin
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=2000000+10;
inline int read()
{int ret=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';return ret;
}int done[maxn],a[maxn],sum[maxn];int query(int l,int r){return sum[r]-sum[l-1];
}int main()
{int n=read(),maxnum=0;for(int i=1;i<=n;i++) {a[i]=read(),sum[a[i]]++;maxnum=max(maxnum,a[i]);}for(int i=1;i<=maxnum*2;i++) sum[i]+=sum[i-1];sort(a+1,a+n+1);ll ans=0;for(int i=1;i<=n;i++)if(!done[a[i]]){ll tmp=0;done[a[i]]=1;for(int j=2;(j-1)*a[i]<=maxnum;j++)done[(j-1)*a[i]]=1,tmp+=(ll)query((j-1)*a[i],j*a[i]-1)*(j-1)*a[i];ans=max(ans,tmp);}printf("%lld",ans);return 0;
}