11月做题记录
2021/11/1 23:10:36
本文主要是介绍11月做题记录，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
不知道为什么就开了这个坑。
争取在 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);
}
这篇关于11月做题记录的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门：从零开始的编程之旅
- 2024-11-23Java创业入门：新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门：初学者的简单教程
- 2024-11-23JAVA副业入门：初学者的实战指南
