比 2022 小清新了许多。
卡牌游戏
首先可以知道的是按照 \(a\) 升序排序，肯定有一段区间的 \(a\) 全保留，然后剩下的全翻面。
那么我们需要求出最长的这段区间是什么。 首先要双指针求区间，然后直接判断剩下的牌 \(b\) 面符不符合就行。
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=2000030;
int a[maxn],b[maxn];int pre_mn[maxn],pre_mx[maxn],suf_mx[maxn],suf_mn[maxn];
int solve(int mid)
{
int rx=0;int ret=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
while(a[rx+1]-a[i]<=mid&&rx<n)
{
rx++;
if(max({a[rx],pre_mx[i-1],suf_mx[rx+1]})-min({a[i],pre_mn[i-1],suf_mn[rx+1]})<=mid)
ret=min(ret,n-(rx-i+1));
}
if(max({a[rx],pre_mx[i-1],suf_mx[rx+1]})-min({a[i],pre_mn[i-1],suf_mn[rx+1]})<=mid)
ret=min(ret,n-(rx-i+1));
}
return ret;
}
int main()
{
//freopen("p.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
pre_mn[0]=0x3f3f3f3f; pre_mx[0]=0;
for(int i=1;i<=n;i++) pre_mx[i]=max(pre_mx[i-1],b[i]),pre_mn[i]=min(pre_mn[i-1],b[i]);
suf_mn[n+1]=0x3f3f3f3f; suf_mx[n+1]=0;
for(int i=n;i>=1;i--) suf_mx[i]=max(suf_mx[i+1],b[i]),suf_mn[i]=min(suf_mn[i+1],b[i]);
int l=1,r=1e9,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(solve(mid)<=m) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
}
矩阵游戏
我们可以随便给 \(a\) 的一行和一列赋值，然后得到一个 \(a\) 数组，不过这里面的 \(a\) 可能不合法。
需要发现一个性质就是 \(a\) 的一整行的第一个数加 \(c\) ，第二个数减 \(c\)，第三个数再加 \(c\) ......以此类推，之后得到的 \(b\) 数组不会发生改变。因为第一个 \(a\) 产生的变化量被第二个抵消掉了。
那么我们可以构造出这么个东西：
\(\begin{matrix} a_{1,1}+r_1+c_1 & a_{1,2}-r_1+c_2 & a_{1,3}+r_1+c_3 &\dots \\ a_{2,1}+r_2-c_1 & a_{2,2}-r_2-c_2 & a_{2,3}+r_2-c_3 &\dots \\ \dots \\ \end{matrix} \)
此时的矩阵应当所有元素都是大于等于零，不大于 \(10^6\)。
这样我们或许可以联想到差分约束。
但是一个问题在于 \(a_{1,1}+r_1+c_1\geq 0\) 这样的东西不好约束。所以我们可以稍微改变一下符号。
\(\begin{matrix} a_{1,1}-r_1+c_1 & a_{1,2}+r_1-c_2 & a_{1,3}-r_1+c_3 &\dots \\ a_{2,1}+r_2-c_1 & a_{2,2}-r_2+c_2 & a_{2,3}+r_2-c_3 &\dots \\ \dots \\ \end{matrix} \)
这样根据奇偶性找到初始符号的规律，使得每一个位置的两个数符号相反。这样就能直接差分约束了。
忘了差分约束的话这边走。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200008;
const int maxm=600044;
int to[maxm],nxt[maxm],head[maxn],num;int val[maxn];
void add(int x,int y,ll z)
{
num++;to[num]=y;val[num]=z;nxt[num]=head[x];head[x]=num;
}
int b[305][305];int a[305][305];
int n,m;
int dis[maxn];bool vis[maxn];int cnt[maxn];
void spfa()
{
queue<int> Q;
memset(dis,0xc0,sizeof(dis)); dis[0]=0;
Q.push(0);
while(Q.size())
{
int p=Q.front(); Q.pop(); vis[p]=0;
for(int i=head[p];i;i=nxt[i])
{
if(dis[to[i]]<dis[p]+val[i])
{
dis[to[i]]=dis[p]+val[i];
cnt[to[i]]++;
if(cnt[to[i]]>=n+1){ printf("NO\n");return; }
if(!vis[to[i]])
{
vis[to[i]]=1; Q.push(to[i]);
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if((i+j)%2==0) a[i][j]+=dis[i]-dis[n+j];
else a[i][j]+=dis[n+j]-dis[i];
if(a[i][j]>2000002||a[i][j]<0) { printf("NO\n");return; }
}
}
printf("YES\n");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
}
void mian()
{
memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt));
memset(head,0,sizeof(head)); num=0;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++) scanf("%d",&b[i][j]);
}
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
{
a[i+1][j+1]=b[i][j]-a[i+1][j]-a[i][j+1]-a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if((i+j)%2==0) add(j+n,i,-a[i][j]),add(i,j+n,-1000000+a[i][j]);
else add(i,j+n,-a[i][j]),add(j+n,i,-1000000+a[i][j]);
}
}
for(int i=1;i<=n;i++) add(0,i,0);
for(int j=1;j<=m;j++) add(0,j+n,0);
spfa();
}
int main()
{
//freopen("p.in","r",stdin);
//freopen("p.out","w",stdout);
int T; scanf("%d",&T); while(T--){mian();}
}
图函数
今天不写了，明天再补（（
宝石
自己想到的做法，但是离复杂度正确只差一点。
首先这玩应肯定具有单调性，所以无脑来个二分答案。
二分之后考虑验证在链上判断能否选出一个子序列使得颜色递增而且从 \(1\) 开始。
我们考虑选出点之后的样子，一定是在上行的部分从下到上有 \(1\) 到一个颜色，下行部分从下到上有 \(mid\) 到一个颜色。所以我们考虑上行能到的最远颜色 \(x\) 和下行从下到上能到的最小颜色 \(y\)，如果 \(x+1<y\)，那么说明这样的路径一定不存在，就一定不行。
我们可以找到每个点在他的祖先里面最近的颜色的前驱和后继。如果是上行，那就从 \(u\) 上找到最近的 \(1\) \(op\)，然后从 \(op\) 往上倍增地跳前驱，跳到最远的不超过 \(lca\) 的点 \(x\)，然后从 \(v\) 向上跳找到最近的 \(mid\) 的点 \(ed\)，从 \(ed\) 倍增的向上跳后继，直到最远的不超过 \(lca\) 的 \(y\)。然后判断 \(x,y\) 能否接上即可。
然后考虑怎样求一个点的前驱。我在极其呆滞的情况下直接倍增套主席树。事实上只需要 \(dfs\) 一次即可....就是实时维护一个桶，桶里面是每种颜色最近的祖先的位置。而且每个点向上的最近的 \(1\) 也能预处理出来。
然后考虑如何给出一个 \(mid\) ，快速地求出来一个点上面最近的 \(mid\)。我直接倍增加主席树然后复杂度 \(O(n\log^3)\)直接升天。我们考虑把询问挂在 \(v\) 上，\(dfs\) 的时候仍然是用那个桶，直接做到一个点就在那里求出答案，这样能直接访问 \(v\) 到任何一个颜色的距离。
最终复杂度 \(O(n\log^2)\)
然后是我脑瘫写的倍增套主席树的又臭又长的 4k 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200002;
const int maxm=400020;
int n,m;
int to[maxm],nxt[maxm],head[maxn],num;
void add(int x,int y){num++;to[num]=y;nxt[num]=head[x];head[x]=num;}
int P[50002],W[50002];int w[maxn];int C;
namespace SGT
{
const int N=maxn*16;
int c[N],lson[N],rson[N],tot;
int newnode(int p){tot++;c[tot]=c[p];lson[tot]=lson[p];rson[tot]=rson[p];return tot;}
void insert(int l,int r,int x,int &p)
{
if(!p) p=++tot;
else p=newnode(p);
if(l==r) {c[p]++;return;}
int mid=(l+r)>>1;
if(x<=mid) insert(l,mid,x,lson[p]);
else insert(mid+1,r,x,rson[p]);
c[p]=c[lson[p]]+c[rson[p]];
}
int query(int l,int r,int x,int p)
{
if(!p) return 0;
if(l==r) return c[p];
int mid=(l+r)>>1;
if(x<=mid) return query(l,mid,x,lson[p]);
else return query(mid+1,r,x,rson[p]);
}
}
int fa[20][maxn],fro[20][maxn],bac[20][maxn]; int FA[maxn];int rt[maxn],dep[maxn];
int ST[maxn];
int siz[maxn],top[maxn],son[maxn];
int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<=dep[top[y]]) swap(x,y);
x=fa[0][top[x]];
}
return dep[x]<dep[y]?x:y;
}
int jump(int p,int c)
{
if(SGT::query(1,C,c,rt[p])-SGT::query(1,C,c,rt[FA[p]])) return p;
for(int i=17;i>=0;i--)
{
if(SGT::query(1,C,c,rt[p])-SGT::query(1,C,c,rt[FA[fa[i][p]]])==0) p=fa[i][p];
}
return FA[p];
}
void dfs(int p,int F)
{
fa[0][p]=F; FA[p]=F; rt[p]=rt[F];SGT::insert(1,C,w[p],rt[p]);
if(p==1) FA[p]=0;
dep[p]=dep[F]+1;
siz[p]=1;
for(int i=head[p];i;i=nxt[i])
{
if(to[i]==F) continue;
dfs(to[i],p);
siz[p]+=siz[to[i]];
if(siz[to[i]]>siz[son[p]]) son[p]=to[i];
}
}
void dfs_build(int p,int tp)
{
top[p]=tp;
if(son[p]) dfs_build(son[p],tp);
for(int i=head[p];i;i=nxt[i])
{
if(to[i]==FA[p]||to[i]==son[p]) continue;
dfs_build(to[i],to[i]);
}
}
bool check(int c,int s,int t,int l,int x,int ed)
{
int y=c+1;
if(ed&&dep[ed]>dep[l])
{
for(int i=15;i>=0;i--)
{
if(bac[i][ed]&&dep[bac[i][ed]]>dep[l]) ed=bac[i][ed];
}
y=w[ed];
}
return x+1>=y;
}
int tt[maxn];vector<int> q[maxn];
int S[maxn],T[maxn],l[maxn],X[maxn],ans[maxn];
void solve(int p)
{
int tmp=tt[w[p]];
tt[w[p]]=p;
for(auto i:q[p])
{
int lx=1,rx=C-1;
while(lx<=rx)
{
int mid=(lx+rx)>>1;
if(check(mid,S[i],T[i],l[i],X[i],tt[mid])) ans[i]=mid,lx=mid+1;
else rx=mid-1;
}
}
for(int i=head[p];i;i=nxt[i])
{
if(to[i]==fa[0][p]) continue;
solve(to[i]);
}
tt[w[p]]=tmp;
}
int main()
{
//freopen("p.in","r",stdin);
//freopen("p.out","w",stdout);
n=IO::read(); m=IO::read(); C=IO::read();
for(int i=1;i<=C;i++) P[i]=IO::read(),W[P[i]]=i;
for(int i=1;i<=n;i++)
{
int xx; xx=IO::read();
if(W[xx])w[i]=W[xx];else w[i]=C+1;
}
C++;
for(int i=1;i<n;i++)
{
int u,v; u=IO::read();v=IO::read();
add(u,v); add(v,u);
}
dfs(1,1); dfs_build(1,1);
for(int i=1;i<=17;i++)
{
for(int j=1;j<=n;j++) fa[i][j]=fa[i-1][fa[i-1][j]];
}
for(int i=1;i<=n;i++) fro[0][i]=jump(i,w[i]+1),bac[0][i]=jump(i,w[i]-1);
for(int i=1;i<=n;i++) ST[i]=jump(i,1);
for(int j=1;j<=15;j++)
{
for(int i=1;i<=n;i++)
fro[j][i]=fro[j-1][fro[j-1][i]],bac[j][i]=bac[j-1][bac[j-1][i]];
}
int Q; Q=IO::read();
for(int i=1;i<=Q;i++)
{
S[i]=IO::read(); T[i]=IO::read();
q[T[i]].push_back(i);
l[i]=LCA(S[i],T[i]);
int st=ST[S[i]];int x=0;
if(st&&dep[st]>=dep[l[i]])
{
for(int j=15;j>=0;j--)
{
if(fro[j][st]&&dep[fro[j][st]]>=dep[l[i]]) st=fro[j][st];
}
x=w[st];
}
X[i]=x;
}
solve(1);
for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
}
滚榜
ACM赛制这玩意也太刺激了吧
首先考虑 \(40\) 分做法。直接枚举全排列，然后 DP 验证可行性。
然后我们发现其实如果上一个是 \(j\)，当前为 \(i\)，那么 \(b_j+a_j\leq a_i+b_i\)，假如我们贴着所有的下界分配权值，那么最后剩下的数量随便分分就行。所以我们只需要关注最优的分配策略。这样 \(b_i=\max\{a_j-a_i+[j<i],0\}+b_j\)。然后枚举全排列验证就是 \(60\) 分。
然后我们会发现一个性质就是 \(\sum b=\sum \max(a_{j}-a_i+[j,i],0)\times(n-i+1)\)。这就是我们可以把 \(\max(a_{j}-a_i+[j,i],0)\) 看作差分数组，然后总的和需要乘上贡献次数。
然后我们考虑状压 DP。设 \(f[S][i][j]\) 表示已经选了的集合为 \(S\)，最后一个选的是 \(i\)，总的 \(b\) 的和是 \(j\)。然后我们可以枚举选 \(i\) 之前选的数字。直到这些就可以知道 \(i\) 加进到集合里之后对全局的贡献（只和位置和上一个出现的数字有关）
然后就能直接转移辣。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int a[20];
ll f[8200][14][505];
int main()
{
scanf("%d%d",&n,&m);
int mxval=0,mxp=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(mxval<a[i]) mxval=a[i],mxp=i;
}
for(int i=1;i<=n;i++)
{
int tmp=max((mxval-a[i])+(mxp<i),0)*(n);
if(tmp<=m) f[(1<<(i-1))][i][tmp]=1;
}
for(int i=1;i<(1<<n);i++)
{
int len=__builtin_popcount(i)+1;
for(int j=1;j<=n;j++)
{
if(!(i&(1<<(j-1)))) continue;
for(int k=0;k<=m;k++)
{
if(!f[i][j][k]) continue;
for(int l=1;l<=n;l++)
{
if(i&(1<<(l-1))) continue;
int tmp=max((a[j]-a[l])+(j<l),0)*(n-len+1);
int tt=i|(1<<(l-1));
if(k+tmp<=m)
f[tt][l][k+tmp]+=f[i][j][k];
}
}
}
}
int bak=(1<<n)-1;ll ans=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
ans+=f[bak][i][j];
}
printf("%lld\n",ans);
}
支配
没时间写了，等会写。
6bit：考试前不要学新算法了。
我：支配树好好玩
标签：head,省选,题解,mid,int,num,maxn,2021,ed From： https://www.cnblogs.com/cc0000/p/17161905.html