T1 White and Black
原题 ARC148C Lights Out on Tree
最小和无解都不用管,不能下改上,所以从上往下,遇到就反转。
一定的观察后发现,当这个点的颜色与父亲不同时,会有贡献,然后直接就做完了。
点击查看代码
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10;
int n,q,s[N],f[N],son[N],head[N],tot;
bool vis[N];
struct EDGE{int v,next;}e[N<<1];
inline void add(int u,int v){
e[++tot]={v,head[u]};head[u]=tot;
}
inline void dfs(int u,int fa){
f[u]=fa;
for(int i=head[u];i;i=e[i].next){
dfs(e[i].v,u);
}
}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read(),q=read();
for(int i=2;i<=n;++i){
int x=read();
add(x,i);
son[x]++;
}
dfs(1,0);
for(int i=1;i<=q;++i){
int num=read();
int res=0;
for(int j=1;j<=num;++j){
s[j]=read();
res+=son[s[j]];
vis[s[j]]=1;
}
for(int j=1;j<=num;++j){
if(vis[f[s[j]]])res--;
else res++;
}
for(int j=1;j<=num;++j){
vis[s[j]]=0;
}
std::cout<<res<<'\n';
}
}
T2 White and White
原题 CF958C3 Encryption(hard)
有个无脑 \(\mathcal{O}(nk\log p)\) 做法,然后给卡了。
设 \(f_{i,k}\) 表示到 \(i\) 分成 \(k\) 段的最小价值。
\(f_{i,k}=min\{f_{j,k-1}+(s_i-s_j)\bmod p\}\) 瓶颈在转移,是 \(\mathcal{O}(n)\) 的。
考虑两个决策点的转移
他们的结果在模 \(p\) 意义下是同余的,所以当 \(f_{j,k-1}\le f_{w,k-1}\) 时,总有 \(f_{j,k-1}+(s_i-s_j)\bmod p\le f_{w,k-1}+(s_i-s_w)\bmod p\),因为它们的增加量是小于 \(p\) 的,不足以反超。
所以对于每个 \(k\) 转移点就是之前的最小值,每个 \(k\) 记一下就可以 \(\mathcal{O}(1)\) 转移了。
点击查看代码
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=5e5+10;
int n,f[N][105],k,mod,a[N];
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
// std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read(),k=read(),mod=read();
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;++i)a[i]=(read()+a[i-1])%mod,f[i][1]=a[i];
for(int j=2;j<=k;++j){
int min=2e9,minpos=0;
for(int i=1;i<=n;++i){
f[i][j]=f[minpos][j-1]+(a[i]-a[minpos]+mod)%mod;
if(min>f[i][j-1]){
min=f[i][j-1];minpos=i;
}
}
}
std::cout<<f[n][k];
}
T3 Black and Black
原题 ARC153C ± Increasing Sequence
套路的构造,先赋好满足递增初值后考虑调整,调整过程满足递增,所以考虑前后缀加减,直接看看前后缀和有没有 \(\pm 1\) 即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10;
int a[N],n,pre[N],suf[N],ans,w[N];
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();
for(int i=1;i<=n;++i){
a[i]=read();pre[i]=pre[i-1]+a[i];
ans+=a[i]*i;
w[i]=i;
}
for(int i=n;i;--i){suf[i]=suf[i+1]+a[i];}
if(ans==0){
std::cout<<"Yes\n";
for(int i=1;i<=n;++i)std::cout<<i<<' ';std::cout<<'\n';
exit(0);
}
if(ans<0){
for(int i=1;i<=n;++i){
if(pre[i]==-1){
std::cout<<"Yes\n";
int k=-ans;
for(int j=1;j<=i;++j)w[j]-=k;
for(int i=1;i<=n;++i)std::cout<<w[i]<<' ';
exit(0);
}
}
for(int i=n;i;--i){
if(suf[i]==1){
std::cout<<"Yes\n";
int k=-ans;
for(int j=i;j<=n;++j)w[j]+=k;
for(int i=1;i<=n;++i)std::cout<<w[i]<<' ';
exit(0);
}
}
std::cout<<"No\n"<<'\n';exit(0);
}
for(int i=1;i<=n;++i){
if(pre[i]==1){
std::cout<<"Yes\n";
int k=ans;
for(int j=1;j<=i;++j)w[j]-=k;
for(int i=1;i<=n;++i)std::cout<<w[i]<<' ';
exit(0);
}
}
for(int i=n;i;--i){
if(suf[i]==-1){
std::cout<<"Yes\n";
int k=ans;
for(int j=i;j<=n;++j)w[j]+=k;
for(int i=1;i<=n;++i)std::cout<<w[i]<<' ';
exit(0);
}
}
std::cout<<"No\n";
}
T4 Black and White
原题 P2056 [ZJOI2007] 捉迷藏
点分树板子,写的线段树上暴力合并。
直径有一个性质,两个点集合并后的直径端点一定是两个点集直径端点组成的。
然后线段树上维护端点和最大距离后直接暴力枚举情况合并即可。时间复杂度 \(\mathcal{O}(n\log n)\)
点击查看代码
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10;
int n,st[20][N],sum[N],dfn[N],dfncnt,dep[N],sm;
std::vector<int> e[N];
struct Tree{int l,r,len,vis;}t[N<<2];
inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
inline void dfs(int u,int fa){
st[0][dfn[u]=++dfncnt]=fa;
for(int v:e[u])if(v!=fa)dep[v]=dep[u]+1,dfs(v,u);
}
inline int get_dis(int u,int v){
int x=u,y=v;
if(u==v)return u;
if((u=dfn[u])>(v=dfn[v]))std::swap(u,v);
int d=std::__lg(v-u++);
int lca=get(st[d][u],st[d][v-(1<<d)+1]);
return dep[x]+dep[y]-2*dep[lca];
}
inline void update(int p){
int ls=p<<1,rs=p<<1|1;
if(t[ls].vis&&t[rs].vis){t[p]={0,0,0,1};return;}
if(t[ls].vis){t[p]=t[rs];return;}
if(t[rs].vis){t[p]=t[ls];return;}
int max=0;
if(max<t[ls].len){t[p]=t[ls];max=t[ls].len;max=t[ls].len;}
if(max<t[rs].len){t[p]=t[rs];max=t[rs].len;max=t[rs].len;}
int w=get_dis(t[ls].l,t[rs].l);
if(max<w){t[p]={t[ls].l,t[rs].l,w,0};max=w;}
w=get_dis(t[ls].l,t[rs].r);
if(max<w)t[p]={t[ls].l,t[rs].r,w,0},max=w;
w=get_dis(t[ls].r,t[rs].l);
if(max<w)t[p]={t[ls].r,t[rs].l,w,0},max=w;
w=get_dis(t[ls].r,t[rs].r);
if(max<w)t[p]={t[ls].r,t[rs].r,w,0},max=w;
}
inline void build(int p,int l,int r){
if(l==r){t[p]={l,r,0,0};return;}
int mid=l+r>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
update(p);
}
inline void change(int p,int l,int r,int pos){
if(l==r){t[p].vis^=1;if(t[p].vis)sm--;else sm++;return;}
int mid=l+r>>1;
if(pos<=mid)change(p<<1,l,mid,pos);
else change(p<<1|1,mid+1,r,pos);
update(p);
}
inline void ask(){
if(sm==1){std::cout<<0<<'\n';return;}
if(sm==0){std::cout<<-1<<'\n';return;}
std::cout<<t[1].len<<'\n';
}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
sm=n=read();
for(int i=2;i<=n;++i){
int u=read(),v=read();
e[u].push_back(v);e[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=std::__lg(n);++i)
for(int j=1;j+(1<<i)-1<=n;++j)
st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-1)]);
build(1,1,n);
int q=read();
for(int i=1;i<=q;++i){
char ch=getchar();
while(ch!='C'&&ch!='G')ch=getchar();
if(ch=='G')ask();
else change(1,1,n,read());
}
}
点击查看
T1
感觉像树剖维护。
等会冲一下
T2
简单分讨后,开值域线段树维护即可。
male,这题这么 \(O(nk\log p)\) 跑不动,白忙活。
T3
只会 30
一定有值域不是很大的方案,