#7
电压
题面
JOISC的一道不错的题。
首先如果一条边在偶环上,这条边是不可能成为答案的。因为偶环黑白染色后一定是黑白相间的。反过来对于奇环,则必然有一条边两端颜色相同。因为题目要求有且只存在一条,所以可以为答案的边一定在所有奇环上,求出一棵生成树,对于一条非树边,如果构成奇环,则将树上对应的边和自己的边权加 \(1\),反之减 \(1\)。如果一条边边权等于构成的奇环的个数则可以为答案,反之不行。权值加减可以用树上差分或树剖+线段树。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e5+10,M=1e6+10;
int n,m,flag[M],edge_id[N];
struct edge{
int u,v;
}e[M];
vector<pii>G[N];
namespace build{
int fa[N];
int getfa(int u){
if(fa[u]!=u){
fa[u]=getfa(fa[u]);
}
return fa[u];
}
void solve(){
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
int u=getfa(e[i].u),v=getfa(e[i].v);
if(u!=v){
fa[v]=u;
G[e[i].u].pb(mp(e[i].v,i));
G[e[i].v].pb(mp(e[i].u,i));
flag[i]=1;
}
}
}
}
int fa[N],dep[N],id[N],top[N],idx,siz[N],heavy[N],cnt[N];
void make_tree(int u,int father){
fa[u]=father;
dep[u]=dep[father]+1;
siz[u]=1;
for(auto x:G[u]){
int v=x.first,ID=x.second;
if(v==father){
continue;
}
edge_id[v]=ID;
make_tree(v,u);
siz[u]+=siz[v];
if(siz[heavy[u]]<siz[v]){
heavy[u]=v;
}
}
}
void dfs(int u,int topf){
top[u]=topf;
id[u]=++idx;
if(heavy[u]){
dfs(heavy[u],topf);
}
for(auto x:G[u]){
int v=x.first;
if(v==fa[u]||v==heavy[u]){
continue;
}
dfs(v,v);
}
}
namespace Seg_Tree{
int ans[N<<2],tag[N<<2];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void f(int p,int l,int r,int val){
ans[p]+=(r-l+1)*val;
tag[p]+=val;
}
void push_down(int p,int l,int r){
int mid=(l+r)>>1;
f(ls(p),l,mid,tag[p]);
f(rs(p),mid+1,r,tag[p]);
tag[p]=0;
}
void push_up(int p){
ans[p]=ans[ls(p)]+ans[rs(p)];
}
void update(int p,int l,int r,int q_l,int q_r,int val){
if(q_l>q_r){
return;
}
if(q_l<=l&&r<=q_r){
ans[p]+=val*(r-l+1);
tag[p]+=val;
return;
}
int mid=(l+r)>>1;
push_down(p,l,r);
if(q_l<=mid){
update(ls(p),l,mid,q_l,q_r,val);
}
if(q_r>mid){
update(rs(p),mid+1,r,q_l,q_r,val);
}
push_up(p);
}
int query(int p,int l,int r,int pos){
if(l==r){
return ans[p];
}
push_down(p,l,r);
int mid=(l+r)>>1;
if(pos<=mid){
return query(ls(p),l,mid,pos);
}
else{
return query(rs(p),mid+1,r,pos);
}
}
}
void update(int u,int v,int val){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
Seg_Tree::update(1,1,n,id[top[u]],id[u],val);
u=fa[top[u]];
}
if(dep[u]>dep[v]){
swap(u,v);
}
if(u!=v){
Seg_Tree::update(1,1,n,id[u]+1,id[v],val);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m);
for(int i=1;i<=m;i++){
read(e[i].u),read(e[i].v);
}
build::solve();
for(int i=1;i<=n;i++){
if(!dep[i]){
make_tree(i,0);
dfs(i,i);
}
}
int tot=0;
for(int i=1;i<=m;i++){
if(flag[i]){
continue;
}
int u=e[i].u,v=e[i].v;
if((dep[u]+dep[v])%2==0){
tot++;
update(u,v,1);
cnt[i]++;
}
else{
update(u,v,-1);
cnt[i]--;
}
}
for(int i=1;i<=n;i++){
cnt[edge_id[i]]=Seg_Tree::query(1,1,n,id[i]);
}
int ans=0;
for(int i=1;i<=m;i++){
if(cnt[i]==tot){
ans++;
}
}
write_endl(ans);
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
邮戳拉力赛
题面
非常神秘的dp。
对于一个车站,有 \(4\) 种情况:
- 上行 \(\rightarrow\) 车站 \(\rightarrow\) 下行,贡献为 \(u+e\)。
- 上行 \(\rightarrow\) 车站 \(\rightarrow\) 上行,贡献为 \(u+v\)。
- 下行 \(\rightarrow\) 车站 \(\rightarrow\) 上行,贡献为 \(d+v\)。
- 下行 \(\rightarrow\) 车站 \(\rightarrow\) 下行,贡献为 \(e+d\)。
因为最后一定是往上走,所以 \(1\) 和 \(3\) 一定是以一组的情况出现,且 \(3\) 一定在 \(1\) 下面。将 \(1\) 看作左括号,\(3\) 看作右括号,最后这个序列一定是个合法括号序。令 \(f_{i,j}\) 表示前 \(i\) 个里有 \(j\) 个右括号未匹配的最小代价。
先处理这 \(j\) 个右括号往上再走一层的贡献,这部分为 \(2\times j\times t\)。
上面四种情况分别得到转移方程:
\(f_{i,j}=\min(f_{i-1,j+1}+u_i+e_i,f_{i,j})\)
\(f_{i,j}=\min(f_{i-1,j}+u_i+v_i,f_{i,j})\)
\(f_{i,j}=\min(f_{i-1,j-1}+d_i+v_i,f_{i,j})\)
\(f_{i,j}=\min(f_{i-1,j}+e_i+d_i,f_{i,j})(j>0)\)
因为一个车站可能不止穿过一次,所以可以在同层中再做一遍完全背包,处理穿过多次的情况。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3010;
int t,u[N],v[N],d[N],e[N],f[N][N],n;
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
memset(f,0x3f,sizeof(f));
f[0][0]=0;
read(n),read(t);
for(int i=1;i<=n;i++){
read(u[i]),read(v[i]),read(d[i]),read(e[i]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i-1][j]=f[i-1][j]+j*t*2;
}
for(int j=1;j<=n;j++){
f[i][j]=min(f[i][j],f[i-1][j-1]+d[i]+v[i]);
}
for(int j=0;j<n;j++){
f[i][j]=min(f[i][j],f[i-1][j+1]+u[i]+e[i]);
}
for(int j=1;j<=n;j++){
f[i][j]=min(f[i][j],f[i-1][j]+d[i]+e[i]);
}
for(int j=0;j<=n;j++){
f[i][j]=min(f[i][j],f[i-1][j]+u[i]+v[i]);
}
for(int j=1;j<=n;j++){
f[i][j]=min(f[i][j],f[i][j-1]+d[i]+v[i]);
}
for(int j=n-1;j>=0;j--){
f[i][j]=min(f[i][j],f[i][j+1]+u[i]+e[i]);
}
}
write_endl(f[n][0]+(n+1)*t);
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
Bread First Search
题面
题目中 BFS 顺序会将图划分为若干层,原有的边不能从第 \(i-2\) 层转移到第 \(i\) 层。
设 \(f_{i,j}\) 表示将 \([i,j]\) 划到一个层中,枚举转移 \(f_{k,j-1}\rightarrow f_{j,k}\),得到 \(O(n^3)\) 做法。
令 \(f_i\) 表示前 \(i\) 个点分为若干段的最小权值,可以发现能转移到的 \(j\) 满足是一段后缀。设 \(mx_i\) 表示 \([1,i]\rightarrow v\) 的最大 \(v\),限制变成了 \(j\ge mx_i\),且 \(j\) 每增大 \(1\),权值增大 \(1\),代价连续,所以只向 \(mx_i\) 转移,后继进行 \(f_{i-1}\rightarrow f_i\) 的转移即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int vis[N],mx[N],f[N],n,m,sum;
vector<int>e[N];
void add(int u){
sum+=(!vis[u]);
vis[u]=1;
}
void solve(){
read(n),read(m);
for(int i=1;i<=m;i++){
int u,v;
read(u),read(v);
mx[u]=max(mx[u],v);
mx[v]=max(mx[v],u);
e[min(u,v)].pb(max(u,v));
}
for(int i=1;i<=n;i++){
mx[i]=max(mx[i],mx[i-1]);
}
memset(f,63,sizeof(f));
for(int i=1;i<n;i++){
f[i]=min(f[i],f[i-1]+1);
int nowf=(i==1?0:f[i]);
add(i);
for(auto v:e[i]){
add(v);
}
int nxt=max(mx[i],i+1);
f[nxt]=min(f[nxt],nowf+nxt-sum);
}
write_endl(f[n]);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[POI2011] IMP-Party
题面
对于在团中的两个点,之间必然有边相连,所以对于之间没有边的两个点,必然一个在团内,一个在团外,删掉这两个点,剩下团的大小为 \(\frac{n}{3}\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3010;
int n,m,deg[N],u[N*N],v[N*N],id[N],vis[N],e[N][N],ans_cnt,ans[N];
bool cmp(int x,int y){
return deg[x]>deg[y];
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m);
for(int i=1;i<=m;i++){
read(u[i]),read(v[i]);
e[u[i]][v[i]]=e[v[i]][u[i]]=1;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(vis[i]||vis[j]||e[i][j]){
continue;
}
vis[i]=vis[j]=1;
break;
}
}
int cnt=0;
// write_endl(n/3);
for(int i=1;i<=n;i++){
if(!vis[i]){
write_space(i);
cnt++;
if(cnt==n/3){
break;
}
}
}
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
PermuTree (hard version)
题面
先考虑 \(O(n^2)\) dp 如何实现,对于一个节点,以它为 lca 的贡献为将子树分为两组,子树大小和的最大乘积。即对于每个节点,对所有子树大小做一遍01背包。可以发现不同的子树大小最多有 \(\sqrt{n}\) 种,将同种大小的子树合并,做多重背包,复杂度为 \(O(n\sqrt{n})\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e6+10;
int n,m,fa[N],siz[N],f[N],vis[N];
vector<int>e[N];
ll ans;
void query(int u){
if(!e[u].size()){
return;
}
for(auto v:e[u]){
if(siz[v]>=(siz[u]-1)/2){
ans+=1ll*siz[v]*(siz[u]-1-siz[v]);
return;
}
}
for(int i=0;i<=siz[u];i++){
vis[i]=0;
}
vis[0]=1;
map<int,int>cnt;
for(auto v:e[u]){
cnt[siz[v]]++;
}
for(auto x:cnt){
int w=x.first,c=x.second;
for(int i=0;i<=siz[u];i++){
f[i]=0;
}
for(int i=w;i<=siz[u];i++){
if(!vis[i]&&vis[i-w]&&f[i-w]<c){
vis[i]=1;
f[i]=f[i-w]+1;
}
}
}
ll sum=0;
for(int i=0;i<=siz[u];i++){
if(vis[i]){
sum=max(sum,1ll*i*(siz[u]-1-i));
}
}
ans+=sum;
}
void solve(){
read(n);
for(int i=2;i<=n;i++){
read(fa[i]);
e[fa[i]].pb(i);
}
for(int i=1;i<=n;i++){
siz[i]=1;
}
for(int i=n;i>=2;i--){
siz[fa[i]]+=siz[i];
}
for(int i=1;i<=n;i++){
query(i);
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
Counting Graphs
题面
如果一条新增的边会影响最小生成树,那么这条边会在原图生成树两端点连通前加入最小生成树。我们考虑对于原树,一条边加入到最小生成时,带来的贡献。根据上述分析,这条边的答案为此时两端点所处连通块的大小的乘积减 \(1\)。因为各边独立,所以总答案为各条边答案的乘积。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,mod=998244353;
int n,mx,fa[N],siz[N];
struct edge{
int u,v,w;
}e[N];
bool cmp(edge x,edge y){
return x.w<y.w;
}
int getfa(int u){
if(fa[u]!=u){
fa[u]=getfa(fa[u]);
}
return fa[u];
}
int qpow(int a,int b){
int res=1;
while(b){
if(b&1){
res=res*a%mod;
}
a=a*a%mod;
b>>=1;
}
return res;
}
void solve(){
read(n),read(mx);
for(int i=1;i<n;i++){
read(e[i].u),read(e[i].v),read(e[i].w);
}
sort(e+1,e+n,cmp);
for(int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
}
int ans=1;
for(int i=1;i<n;i++){
int u=getfa(e[i].u),v=getfa(e[i].v);
ans=ans*qpow(mx-e[i].w+1,siz[u]*siz[v]-1)%mod;
fa[v]=u;
siz[u]+=siz[v];
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
Vika and Wiki
题面
令 \(f_{i,j}\) 表示操作 \(i\) 次后,\(j\) 位置答案。显然可能存在于答案中的位置必然在 \([j,j+i]\) 中,一个位置要存在答案中,需要满足这个位置在得到答案的过程中异或了奇数次。我们可以得到 \(f_{i,j}=\oplus_{k=0}^i[\binom{i}{k}\equiv 1 \pmod 2]a_{j+k}\),根据 kummer 定理,我们可以得到 \(\binom{i}{k}\equiv 1\pmod 2\) 要满足在二进制位上,\(k\) 是 \(i\) 的子集。
假定答案为 \(i\),则存在 \(f_{ans,0}=f_{ans,1}=f_{ans,2}=\dots=f_{ans,n-1}=0\),即 \(\forall i\ge ans,j\in[0,n-1],f_{i,j}=0\),我们可以进行一次高维前缀异或和,得到所有的 \(f_{i,0}\)。从后往前找就能找到答案。
因为 \(n\) 为 \(2\) 的若干次方,所以一定有解。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=(1<<20)+10;
int n,a[N];
void solve(){
read(n);
for(int i=0;i<n;i++){
read(a[i]);
}
for(int k=1;k<(1ll<<20);k*=2){
for(int i=0;i<(1ll<<20);i+=k*2){
for(int j=i;j<i+k;j++){
a[j+k]^=a[j];
}
}
}
for(int i=n-1;i>=0;i--){
if(a[i]){
write_endl(i+1);
return;
}
}
write_endl(0);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}