不知道为什么就开了这个坑。

争取在 NOIP 之前每日更新（

11.1

*1442C

考虑分层图。在第 \(19\) 层的时候换方向的代价已经超过了走一遍图的代价，所以如果能在 \(19\) 层之前到达 \(n\) 的话一定不会再往下走。如果翻转 \(19\) 次还无法到达 \(n\)，就需要走的层尽量少，最短路时将换层代价设为极大即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
void write(int n)
{
	if(n<0){putchar('-');n=-n;}
	if(n>9)write(n/10);
	putchar(n%10^48);
}
const int N=2e5+10,M=4e5+10,inf=0x3f3f3f3f3f3f3f3fll,mod=998244353;
int head[N],ver[M],nxt[M],tot=0,edge[M];
void add(int x,int y,int z){ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;}
int dis[N][21];bool vis[N][21];
void dij(int s)
{
	priority_queue<pair<int,pii> > que;
	que.push(mp(0,mp(s,0)));
	memset(dis,0x3f,sizeof(dis));
	dis[s][0]=0;
	while(!que.empty())
	{
		pii x=que.top().se;que.pop();
		if(vis[x.fi][x.se])continue;
		for(int i=head[x.fi];i;i=nxt[i])
		{
			int y=ver[i],z=edge[i];
			if(z==(x.se&1ll))
			{
				if(dis[x.fi][x.se]+1<dis[y][x.se])
				{
					dis[y][x.se]=dis[x.fi][x.se]+1;
					que.push(mp(-dis[y][x.se],mp(y,x.se)));
				}
			}
			else if(x.se<19)
			{
				if(dis[x.fi][x.se]+(1ll<<x.se)+1<dis[y][x.se+1])
				{
					dis[y][x.se+1]=dis[x.fi][x.se]+(1<<x.se)+1;
					que.push(mp(-dis[y][x.se+1],mp(y,x.se+1)));
				}
			}
		}
	}
}
void dij1(int s)
{
	memset(dis,0x3f,sizeof(dis));
	dis[s][0]=0;
	memset(vis,0,sizeof(vis));
	priority_queue<pair<int,pii> > que;
	que.push(mp(0,mp(s,0)));
	while(!que.empty())
	{
		pii x=que.top().se;que.pop();
		if(vis[x.fi][x.se])continue;
		vis[x.fi][x.se]=1;
		for(int i=head[x.fi];i;i=nxt[i])
		{
			int y=ver[i],z=edge[i];
			if(x.se==z)
			{
				if(dis[x.fi][x.se]+1<dis[y][x.se])
				{
					dis[y][x.se]=dis[x.fi][x.se]+1;
					que.push(mp(-dis[y][x.se],mp(y,x.se)));
				}
			}
			else
			{
				if(dis[x.fi][x.se]+1e7+1<dis[y][x.se^1])
				{
					dis[y][x.se^1]=dis[x.fi][x.se]+1e7+1;
					que.push(mp(-dis[y][x.se^1],mp(y,x.se^1)));
				}
			}
		}
	}
}
int qpow(int a,int n)
{
	a%=mod;
	int ans=1;
	while(n)
	{
		if(n&1)ans=ans*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return ans;
}
signed main()
{
	int n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		add(u,v,0),add(v,u,1);
	}
	dij(1);int ans=inf;
	for(int i=0;i<=19;i++)ans=min(ans,dis[n][i]);
	if(ans==27)puts("HELLO!");
	if(ans<inf)return printf("%lld",ans),0;
	dij1(1);ans=min(ans,min(dis[n][0],dis[n][1]));
	printf("%lld",((qpow(2,ans/10000000)-1)+ans%10000000)%mod);
}

1473E

\(\sum_{i=1}^{k}{w_{e_i}} - \max_{i=1}^{k}{w_{e_i}} + \min_{i=1}^{k}{w_{e_i}}\) 这玩意等价于路径上随便加一条边的权值再减一条边的权值，根据贪心加的一定会选最小的减的一定会选最大的，所以 \(dis(x,0/1/2/3)\) 表示到 \(x\) 点，没有加过也没有减过/只加了/只减了/都用过了 四种状态的最小代价，最短路即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
void write(int n)
{
	if(n<0){putchar('-');n=-n;}
	if(n>9)write(n/10);
	putchar(n%10^48);
}
const int N=2e5+10,M=4e5+10;
int head[N],ver[M],nxt[M],edge[M],tot=0;
void add(int x,int y,int z)
{
	ver[++tot]=y;
	edge[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
}
int dis[N][4];bool vis[N][4];
//0:no
//1:+
//2:-
//3:+ - 
void dij(int s)
{
	priority_queue<pair<int,pii> > que;
	memset(dis,0x3f,sizeof(dis));
	dis[s][0]=0;
	que.push(mp(0,mp(s,0)));
	while(!que.empty())
	{
		pii x=que.top().se;que.pop();
		if(vis[x.fi][x.se])continue;
		vis[x.fi][x.se]=1;
		for(int i=head[x.fi];i;i=nxt[i])
		{
			int y=ver[i],z=edge[i];
			if(x.se==0)
			{
				if(dis[x.fi][0]+z<dis[y][0])
				{
					dis[y][0]=dis[x.fi][0]+z;
					que.push(mp(-dis[y][0],mp(y,0)));
				}
				if(dis[x.fi][0]+2*z<dis[y][1])
				{
					dis[y][1]=dis[x.fi][0]+2*z;
					que.push(mp(-dis[y][1],mp(y,1)));
				}
				if(dis[x.fi][0]<dis[y][2])
				{
					dis[y][2]=dis[x.fi][0];
					que.push(mp(-dis[y][2],mp(y,2)));
				}
				if(dis[x.fi][0]+z<dis[y][3])
				{
					dis[y][3]=dis[x.fi][0]+z;
					que.push(mp(-dis[y][3],mp(y,3)));
				}
			}
			else if(x.se==1)
			{
				if(dis[x.fi][1]+z<dis[y][1])
				{
					dis[y][1]=dis[x.fi][1]+z;
					que.push(mp(-dis[y][1],mp(y,1)));
				}
				if(dis[x.fi][1]<dis[y][3])
				{
					dis[y][3]=dis[x.fi][1];
					que.push(mp(-dis[y][3],mp(y,3)));
				}
			}
			else if(x.se==2)
			{
				if(dis[x.fi][2]+z<dis[y][2])
				{
					dis[y][2]=dis[x.fi][2]+z;
					que.push(mp(-dis[y][2],mp(y,2)));
				}
				if(dis[x.fi][2]+2*z<dis[y][3])
				{
					dis[y][3]=dis[x.fi][2]+2*z;
					que.push(mp(-dis[y][3],mp(y,3)));
				}
			}
			else if(x.se==3)
			{
				if(dis[x.fi][3]+z<dis[y][3])
				{
					dis[y][3]=dis[x.fi][3]+z;
					que.push(mp(-dis[y][3],mp(y,3)));
				}
			}
		}
	}
}
signed main()
{
	int n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read();
		add(u,v,w),add(v,u,w);
	}dij(1);
	for(int i=2;i<=n;i++)printf("%lld ",dis[i][3]);
	return 0;
}

*1408E

考虑每个点向集合连边，边权为 \(a_i+b_j\)，那么有彩虹当且仅当有环。要删的最少，即保留的最多并且无环，就是最大生成树了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
const int N=2e5+10;
struct dsu{
	int fa[N];
	void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
	int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
	void mg(int x,int y){fa[getf(y)]=getf(x);}
}B;
int a[N],b[N];
struct Edge{int u,v,w;}e[N];
bool cmp(Edge x,Edge y){return x.w>y.w;}
int main()
{
	int m=read(),n=read();ll ans=0;
	for(int i=1;i<=m;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	//set:n+i   number:i
	B.init(n+m);int cnt=0;
	for(int i=1;i<=m;i++)
	{
		int s=read();
		for(int j=1;j<=s;j++)
		{
			int x=read();
			e[++cnt]=Edge{i+n,x,a[i]+b[x]};
			ans+=a[i]+b[x];
		}
	}
	sort(e+1,e+cnt+1,cmp);
	for(int i=1;i<=cnt;i++)
	{
		if(B.getf(e[i].u)==B.getf(e[i].v))continue;
		B.mg(e[i].u,e[i].v);
		ans-=e[i].w;
	}
	printf("%lld",ans);
	return 0;
}

915F

首先把 \(\sum I(i,j)\) 拆成 \(\sum \operatorname{Max}(i,j)-\sum\operatorname{Min}(i,j)\)，\(\operatorname{Max}\) 表示路径上点权最大值，\(\operatorname{Min}\) 同理。根据某场 ABC 的套路，按照边权排序后并查集维护 \(sz\) 加边算贡献是可以分别计算两者的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
void write(int n)
{
	if(n<0){putchar('-');n=-n;}
	if(n>9)write(n/10);
	putchar(n%10^48);
}
const int N=1e6+10,M=2e6+10;
int head[N],ver[M],nxt[M],tot=0;
void add(int x,int y)
{
	ver[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
struct Node{
	int w,pos;
}a[N];
bool cmp(Node x,Node y){return x.w==y.w?x.pos<y.pos:x.w<y.w;}
bool cmp1(Node x,Node y){return x.w==y.w?x.pos>y.pos:x.w>y.w;}
struct dsu{
	int fa[N],sz[N];
	void init(int n){for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;}
	int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
	void mg(int x,int y){sz[getf(x)]+=sz[getf(y)],fa[getf(y)]=getf(x);}
}B;int w[N]; 
int main()
{
	int n=read();B.init(n);ll ans=0;
	for(int i=1;i<=n;i++)w[i]=a[i].w=read(),a[i].pos=i;
	for(int i=1;i<n;i++){int u=read(),v=read();add(u,v),add(v,u);}
	sort(a+1,a+n+1,cmp1);
//	for(int i=1;i<=n;i++)printf("val=%d, pos=%d\n",a[i].w,a[i].pos);
	for(int xx=1;xx<=n;xx++)
	{
		int i=a[xx].pos;
		for(int x=head[i];x;x=nxt[x])
		{
			int j=ver[x];if(B.getf(i)==B.getf(j))continue;
			if(cmp1(Node{w[i],i},Node{w[j],j}))continue;
//			printf("merge(%d, %d)\n",i,j);
//			printf("ans-=%d * %d\n",B.sz[B.getf(i)],B.sz[B.getf(j)]);
			ans-=1ll*B.sz[B.getf(i)]*B.sz[B.getf(j)]*w[i];
			B.mg(i,j);
		}
	}
//	printf("%lld",ans);
	sort(a+1,a+n+1,cmp);B.init(n);
	for(int xx=1;xx<=n;xx++)
	{
		int i=a[xx].pos;
		for(int x=head[i];x;x=nxt[x])
		{
			int j=ver[x];if(B.getf(i)==B.getf(j))continue;
			if(cmp(Node{w[i],i},Node{w[j],j}))continue;
//			printf("merge(%d, %d)\n",i,j);
//			printf("ans-=%d * %d\n",B.sz[B.getf(i)],B.sz[B.getf(j)]);
			ans+=1ll*B.sz[B.getf(i)]*B.sz[B.getf(j)]*w[i];
			B.mg(i,j);
		}
	}
	printf("%lld",ans);
}