《LGJOJ 8.25》 测试总结
纯菜了，属于是。
中间还咕了很多场总结。。。
\(T1\) 简单游戏
输入：
输出：
\(\color{red}analysis:\)
考试的时候看错题了，寄。
正常做就是直接暴力区间 \(dp\) 就好了
就是正常的博弈论 \(dp\)
其他没什么好说的了，时间复杂度 \(O(n^2)\)
\(PS:\) 挂成了 \(30pts\)
\(PS:\) 没加记忆化都过了， \(gj\) 的数据不做评价。
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=2010;
int T,n;
int f[MAXN][MAXN];
char st[MAXN];
int pd(int x,int y) {
if(x<y) return 1;
if(x==y) return 0;
if(x>y) return 2;
}
void dfs(int opt,int l,int r,int cc) {
if(l>r) return ;
if(f[l][r]!=-1) return ;
if(!opt) {
dfs(opt^1,l+1,r,st[l]);
int u=f[l+1][r];
dfs(opt^1,l,r-1,st[r]);
int v=f[l][r-1];
if(u==1||v==1) f[l][r]=1;
else if(!u||!v) f[l][r]=0;
else f[l][r]=2;
}
else {
if(st[l]<cc||st[r]<cc) {
f[l][r]=2;
return ;
}
else if(st[l]==cc||st[r]==cc) {
if(l==r) {
f[l][r]=0;
return ;
}
int u=1,v=1;
if(st[l]==cc) {
dfs(opt^1,l+1,r,cc);
u=f[l+1][r];
}
if(st[r]==cc) {
dfs(opt^1,l,r-1,cc);
v=f[l][r-1];
}
if(u==2||v==2) f[l][r]=2;
else if(!u||!v) f[l][r]=0;
else f[l][r]=1;
}
else {
f[l][r]=1;
}
}
}
int main () {
scanf("%d",&T);
while(T--) {
scanf("%s",st+1);
n=strlen(st+1);
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
f[i][j]=-1;
}
}
dfs(0,1,n,0);
if(f[1][n]==0) puts("Draw");
if(f[1][n]==1) puts("Alice");
if(f[1][n]==2) puts("Bob");
}
return 0;
}
\(T2\) 内鬼
输入：
输出：
2
\(\color{blue}analysis:\)
首先我们考虑暴力 \(f_{i,j,S}\) 表示两个内鬼分别在 \(i,j\) 位置，抓到 \(S\) 这个集合里人所耗费的最少时间，然后我们可以获得一个 \(O(en^22^8)\) 的优秀解法，可以获得 \(30pts\)
\(if(dis[i][t]\le e[i].time-f_{i,j,S})\) 如果满足这个条件，我们的 \(dp\) 就可以转移，所以我们需要预处理
但是这样还不够，由于 \(t3\) 便秘时间过长，耗费了将近 \(1h\) 没想到怎么做，于是就回来写这题，突然想到两个内鬼可以拆开计算，然后枚举两个内鬼分别抓捕的人的集合，分别拆成 \(f_{x,S'},f_{y,S''}\) 。
然后具体能不能做到 \(50pts\) 那一档部分分呢，我觉得应该是可以搞到 \(en2^8\) 的,然后拿 \(50pts\)。
然后由于如果我们想拿 \(100pts\) ，我们就绝对不能预处理 \(dis\) 数组，我们考虑有没有一种方法，不用预处理 \(dis\) 数组。
这时候宋哥跑过来和我说分层图，然后就恍然大悟了属于是，我们既然不能直接预处理，那么我们就考虑直接跑最短路，然后对于每个不同的集合 \(S\) ，分成一层，至多分成 \(256\) 层，然后对于每层跑一下最短路，对于那些跨越层之间的路径也是照样跑就行了。
时间复杂度 \(O((2^km+2^ke)\log (2^kn))\) 空间复杂度也比较大，一种比较好的优化方法就是先对每层跑好在去跑分层图的边，这样就不用存那么多边的信息。
\(T3\) 序列统计
\(analysis:\)
考试便秘想不出来。
首先对于 \(mex\) 有一个比较经典的操作，就是将每种数都分开来处理，从 \(1\sim m\) 来进行处理。
然后题目问最小的包含 \(1\sim m\) 的最小长度是多少，其实就是问 \(mex=i(i\in(2\sim m+1))\) 的最小的长度
\(dp\ +\) 主席树
\(\%\%\% sktn0089\ wzr\) 大神
由于我们的暴力是枚举一个左端点一直向右扫，我们考虑优化。
记 \(f_{i,0/1}\) 表示以 \(i\) 为左端点或右端点使得一段序列包含 \(1\sim a_i\) 的最小的序列长度是多少。
然后我们考虑从 \(a_i=1\) 的 \(i\) 开始枚举。
我们只对 \(f_{i,0}\) 讨论，也就是 \(i\) 为左端点进行讨论，因为为右端点也是同理即可。
我们查询 \(mex(a_i,a_{i+1}...a_{i+f_{i,0}-1})\) ，记为 \(v\) ，然后这个区间就可以贡献给 \(ans_{v}\) ，记 \(ans_v\) 为，\(mex\) 为 \(v\) 的最小序列长度。
对于如何求区间 \(mex\) 我们只需要用主席树查询 \(i+f_{i,0}-1\) 这个版本中最小的最后一次被染色的节点在 \(l\) 左边的即可，具体代码会解释。
然后我们找到这段区间右边第一个 \(a[j]=v\) 的，记为 \(R\) ，左边同理，记为 \(L\)
然后我们就更新这些对应的 \(f\) 即可。
不过注意最后的 \(ans\) 要做一个后缀最小值。
因为对于 \(1\ 3\ 2\) ，实际上找不到 \(mex=2\) 的序列，只找得到 \(mex=3\) 的序列，所以 \(ans_3\) 要贡献给 \(ans_2\) ，也就是后缀最小值。
时间复杂度 \(O(n\log n)\) 空间复杂度 \(n\log n\)
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=5e5+10,inf=1e9;
int n,m;
int a[MAXN],f[MAXN][2],ans[MAXN];
vector<int> e[MAXN];
int T[MAXN],tot;
struct daduoli {
int v,l,r;
}tr[MAXN*20];
int update(int pre,int l,int r,int x,int i) {
int nw=++tot;
tr[nw]=tr[pre];
if(l<r) {
int mid=(l+r)/2;
if(x<=mid) tr[nw].l=update(tr[pre].l,l,mid,x,i);
else tr[nw].r=update(tr[pre].r,mid+1,r,x,i);
tr[nw].v=min(tr[tr[nw].l].v,tr[tr[nw].r].v);//对于区间中最后出现位置的数找到一个最小值
}
else {
tr[nw].v=i;//更新x最后出现位置
}
return nw;
}
int query(int nw,int pre,int l,int r) {
if(tr[nw].v>=pre) return r+1;
if(l==r) return l;
int mid=(l+r)/2;
if(tr[tr[nw].l].v>=pre) return query(tr[nw].r,pre,mid+1,r);//如果左区间中所有数最后出现位置都在左端点右边，那就找右区间，因为左区间全都合法
return query(tr[nw].l,pre,l,mid);
}
int main () {
scanf("%d%d",&n,&m);
for(int i=1;i<=m+1;++i) ans[i]=inf;
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
e[a[i]].push_back(i);
if(a[i]==1) f[i][0]=f[i][1]=1;
else f[i][0]=f[i][1]=inf;
T[i]=update(T[i-1],1,m,a[i],i);
}
for(int i=1;i<=m;++i) {
for(auto t:e[i]) {
if(f[t][0]<inf) {
int l=t,r=t+f[t][0]-1;
int v=query(T[r],l,1,m);
ans[v]=min(ans[v],f[t][0]);
auto it=lower_bound(e[v].begin(),e[v].end(),l)-e[v].begin();
if(it<e[v].size()) f[e[v][it]][1]=min(f[e[v][it]][1],e[v][it]-l+1);
--it;
if(it>=0) f[e[v][it]][0]=min(f[e[v][it]][0],r-e[v][it]+1);
}
if(f[t][1]<inf) {
int l=t-f[t][1]+1,r=t;
int v=query(T[r],l,1,m);
ans[v]=min(ans[v],f[t][1]);
auto it=lower_bound(e[v].begin(),e[v].end(),l)-e[v].begin();
if(it<e[v].size()) f[e[v][it]][1]=min(f[e[v][it]][1],e[v][it]-l+1);
--it;
if(it>=0) f[e[v][it]][0]=min(f[e[v][it]][0],r-e[v][it]+1);
}
}
}
for(int i=m;i>=2;--i) {
ans[i]=min(ans[i],ans[i+1]);//记得取一下后缀最小值
}
for(int i=2;i<=m+1;++i) {
printf("%d\n",ans[i]);
}
return 0;
}
线段树
听 \(forgiven\) 讲了一下。
大概是我们记录一个数组 \(f_{i,j}\) 表示从 \(i\) 开始，要使得区间 \(mex\) 为 \(j\) 的最小长度是多少，我们记下一个与 \(a[i]\) 相同的位置在 \(q\) ，满足 \(a[i]=j-1\) 。
然后我们考虑更新 \(i+1\) ,倘若把 \(i\) 删除掉，那么 \(i+1\sim (q-1)\) 里面想要凑出 \(mex=j\) 的序列，就必须要遍历到 \(q\) ，所以对 \((i+1)\sim (q-1)\) 里面的值进行一个区间取 \(max\) ,但是如果直接区间取 \(max\) ，