2018.10.30 正睿停课训练 Day12
期望得分：100+?+0
实际得分：100+90+0
A 强军战歌(DP 树状数组 容斥)
长度为\(i\)的不降子序列个数是可以DP求的。
用\(f[i][j]\)表示长度为\(i\)，结尾元素为\(a_j\)的不降子序列个数。转移为\(f[i][j]=\sum f[i-1][k]\)，其中\(k\)满足\(k<j\)且\(a_k\leq a_j\)，可以用树状数组\(O(n^2\log n)\)解决。
那么长度为为\(i\)的不降子序列个数\(sum[i]=\sum_{j=i}^nf[i][j]\)。
比较麻烦的是得到不降序列后会立刻停止操作。如果没有这个限制，答案就是\(\sum_{i=1}^nsum[i]\times (n-i)!\)。
但是很简单的是，如果长为\(i\)的不降序列是由另一个不降序列继续删数得到的（即不合法的方案），那么这个方案数就是\(sum[i+1]\times (i+1)\times (n-i+1)!\)。
对每个\(i\)减掉不合法方案的贡献就可以了，即\(Ans=\sum_{i=1}^nsum[i]\times (n-i)!-sum[i+1]\times (i+1)\times (n-i+1)!\)。
原题：BZOJ4361。
//324ms 29956kb
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define mod 1000000007
#define Mod(x) x>=mod&&(x-=mod)
typedef long long LL;
const int N=2005;
int fac[N],A[N],f[N][N],g[N];
struct Bit
{
int n,t[N];
#define lb(x) (x&-x)
inline void Add(int p,int v)
{
for(; p<=n; p+=lb(p)) t[p]+=v, Mod(t[p]);
}
inline int Query(int p)
{
LL res=0;
for(; p; p^=lb(p)) res+=t[p];
return res%mod;
}
}T[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int n=read(),mx=0;
fac[0]=fac[1]=1;
for(int i=2; i<=n; ++i) fac[i]=1ll*fac[i-1]*i%mod;
for(int i=1; i<=n; ++i) mx=std::max(mx,A[i]=read());
for(int i=1; i<=n; ++i) f[1][i]=1;
for(int i=2; i<=n; ++i)
{
T[i-1].n=mx, T[i-1].Add(A[i-1],f[i-1][i-1]);
for(int j=i; j<=n; ++j)
f[i][j]=T[i-1].Query(A[j]), T[i-1].Add(A[j],f[i-1][j]);
}
for(int i=1; i<=n; ++i)
{
LL sum=0;
for(int j=i; j<=n; ++j) sum+=f[i][j];
g[i]=1ll*sum%mod*fac[n-i]%mod;
}
LL ans=0;
for(int i=1; i<=n; ++i) ans+=g[i]-1ll*g[i+1]*(i+1)%mod;
printf("%lld\n",(ans%mod+mod)%mod);
return 0;
}
B 当那一天来临(思路)
决策的胜负只与汇合点在哪有关。所以可以先预处理出汇合点在每个点时的状态\(A_i\)。
容易发现，当\(n\)为奇数时，后手一定可以使相会点为\(mid\)。因为只要与先手对称移动就可以了。
那么当\(n\)为偶数时，先手走一步使\(n\)变为奇数，且变成了下一轮的后手，那么先手一定可以使汇合点为\(mid\)或\(mid+1\)。也就是\(mid,mid+1\)有一个点是先手必胜点，先手可以必胜。否则，后手一定可以将汇合点限制在\(mid,mid+1\)处。所以此时\(S=\max(A_{mid},A_{mid+1})\)。
当\(n\)为奇数时，先手操作一步会使后手变为先手，且\(n\)变为偶数。那么同理，后手一定可以选择\(mid-1,mid\)或\(mid,mid+1\)（取决于先手第一步）。所以\(S=\max(\min(A_{mid-1},A_{mid}),\min(A_{mid},A_{mid+1}))\)。
//0ms 564kb
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e4+5;
int tmp[N],suf[N],A[N];
inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
int main()
{
for(int T=read(); T--; )
{
int n=read(); suf[n+1]=0;
for(int i=1; i<=n; ++i) A[i]=A[i-1]+(tmp[i]=read());
for(int i=n; i; --i) suf[i]=suf[i+1]+tmp[i], A[i]-=suf[i];
int mid=n+1>>1,ans;
if(n&1) ans=std::max(std::min(A[mid-1],A[mid]),std::min(A[mid],A[mid+1]));//=min(A[mid],max(A[mid-1],A[mid+1]))
else ans=std::max(A[mid],A[mid+1]);
puts(ans>0?"win":(ans<0?"lose":"tie"));
}
return 0;
}
C 假如战争今天爆发(贪心)
假如已经确定了加工顺序，怎么求时间呢。。
容易想到DP或者直接模拟。考虑DP，\(f[i][1/2/3]\)表示当前第\(i\)个物品在\(A/B/C\)机器加工完所需要的时间，那么有\(f[i][j]=\max\{f[i-1][j],f[i][j-1]\}+A[i][j]\)（\(A[i][j]\)表示机器\(j\)加工\(i\)所需时间）。
答案为\(f[n][3]\)。这样可以\(O(n)\)解决。
（把第一维压掉，实际写起来比这还容易）
把\(f\)画成一个\(3\)行\(n\)列的网格图，因为每个位置就是由左边和上边的取\(\max\)，再加上当前位置的权值转移来，所以\(f[n][3]\)实际就是\((1,1)\)到\((3,n)\)的最长路。
那么我们实际就是要最小化这个最长路长度。
注意到题目限制\(C_{min}\geq B_{max}\)，所以可以看做一条最长路一定不会在第二行拐弯。那么最长路的情况只有一种：从\((1,1)\)走到\((1,x)\)，然后向下走到\((3,x)\)再直接走到\((3,n)\)。
这样最长路的权值可以直接表示：\(pre[x-1]+A_x+B_x+C_x+suf[x+1]\)，\(pre,suf\)分别表示前缀和后缀和。
考虑交换相邻两列\(i,j\)对最长路的影响。受影响的只有\(i,j\)两列，变化前为\(\max\{A_i+B_i+C_i+C_j,\ A_i+A_j+B_j+C_j\}\)，变化后为\(\max\{A_j+B_j+C_j+C_i,\ A_j+A_i+B_i+C_i\}\)。
按上面的排序，就可以AC啦。
因为\(\max\{a+c,\ b+c\}=\max\{a,b\}+c\)，化简一下上面：\(\max\{B_i+C_i,\ A_j+B_j\}+A_i+C_j\to\max\{B_j+C_j,\ A_i+B_i\}+A_j+C_i\)。
如果将\(i,j\)交换后不会更优，则有\(\max\{B_i+C_i,\ A_j+B_j\}+A_i-C_i\leq\max\{B_j+C_j,\ A_i+B_i\}+A_j-C_j\)。
令\(x_i=B_i+C_i,y_i=A_i+B_i\)，继续化简：$$\max{x_i,y_j}+y_i-x_i\leq\max{x_j,y_i}+y_j-x_j\\max{-y_j,-x_i}\leq\max{-y_i,-x_j}\\min{y_j,x_i}\geq\min{y_i,x_j}$$
如果有\(\min\{y_j,x_i\}\geq\min\{y_i,x_j\}\)，\(\min\{y_k,x_j\}\geq\min\{y_j,x_k\}\)，那么分情况讨论可以得到\(\min\{y_k,x_i\}\geq\min\{y_i,x_k\}\)，即满足全序关系，所以贪心是对的。
具体怎么分类讨论==。。不想想。
//183ms 1960kb
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e5+5;
char IN[MAXIN],*SS=IN,*TT=IN;
struct Node
{
int a,b,c;
}A[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline bool cmp(const Node &i,const Node &j)
{
return i.a-i.c+std::max(i.b+i.c,j.a+j.b)<=j.a-j.c+std::max(j.b+j.c,i.a+i.b);
}
int main()
{
int n=read();
for(int i=1; i<=n; ++i) A[i]=(Node){read(),read(),read()};
std::sort(A+1,A+1+n,cmp);
LL An=0,Bn=0,Cn=0;
for(int i=1; i<=n; ++i) An+=A[i].a, Bn=std::max(Bn,An)+A[i].b, Cn=std::max(Cn,Bn)+A[i].c;
printf("%lld\n",Cn);
return 0;
}
考试代码
B
这个记忆化实际就是\(O(n^2)\)的区间DP。（但是用不着map啊 傻了）
#include <map>
#include <cstdio>
#include <cctype>
#include <algorithm>
#define mp std::make_pair
#define pr std::pair<int,int>
#define gc() getchar()
typedef long long LL;
const int N=1e4+5,INF=0x7fffffff;
int A[N],sum[N];
std::map<pr,int> vis[11][2];
inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
int DFS(const int T,int l,int r,int now,int vl,int vr)
{
if(l==r) return vl-vr;
if(vis[T][now].count(mp(l,r))) return vis[T][now][mp(l,r)];
return now?vis[T][now][mp(l,r)]=std::max(DFS(T,l+1,r,now^1,vl+A[l+1],vr),DFS(T,l,r-1,now^1,vl,vr+A[r-1]))
:vis[T][now][mp(l,r)]=std::min(DFS(T,l+1,r,now^1,vl+A[l+1],vr),DFS(T,l,r-1,now^1,vl,vr+A[r-1]));
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
for(int T=read(); T--; )
{
int n=read();
for(int i=1; i<=n; ++i) A[i]=read();
if(n<=20||1)
{
int tmp=DFS(T,1,n,1,A[1],A[n]);
puts(tmp>0?"win":(tmp<0?"lose":"tie"));
continue;
}
}
return 0;
}
C
根本没想DP。。模拟也没写出来。。
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e5+5;
int ra[N],rb[N],rc[N];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Node
{
int a,b,c;
}A[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline bool cmp(const Node &x,const Node &y)
{
return x.b-x.a>y.b-y.a;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int n=read();
for(int i=1; i<=n; ++i) A[i]=(Node){read(),read(),read()};
std::sort(A+1,A+1+n,cmp);
// for(int i=1; i<=n; ++i) printf("%d:a:%d b:%d c:%d\n",i,A[i].a,A[i].b,A[i].c); puts("");
int pa=1,hb=0,tb=0,pc=0,now=0,sb=0,sc=0;
while(pa<=n)
{
while(hb<tb&&sb+A[hb+1].b<=now) sb+=A[++hb].b;
while(pc<hb&&sc+A[pc+1].c<=now) sc+=A[++pc].c;
now+=A[pa++].a, ++tb;
// printf("pa:%d now:%d h:%d t:%d sb:%d sc:%d\n",pa,now,hb,tb,sb,sc);
}
// puts("");
A[hb+1].b-=now-A[n].a-sb;
// printf("%d -= %d\n",hb+1,now-A[n].a-sb);
// printf("End A hb:%d now:%d sc:%d\n",hb,now,sc);
while(hb<n)
{
while(pc<hb&&sc+A[pc+1].c<=now) sc+=A[++pc].c;
now+=A[++hb].b;
// printf("hb:%d now:%d sc:%d\n",hb,now,sc);
}
// puts("");
A[pc+1].c-=now-A[n].b-sc;
// printf("%d -= %d\n",pc+1,now-A[n].b-sc);
// printf("pc:%d sc:%d now:%d\n",pc,sc,now);
// while(pc<n&&sc+A[pc+1].c<=now) sc+=A[++pc].c;
// printf("pc:%d sc:%d now:%d\n",pc,sc,now);
while(pc<n) now+=A[++pc].c;
printf("%d\n",now);
return 0;
}