首页 > 其他分享 >练习1题目记录

练习1题目记录

时间：2025-01-23 15:11:31浏览次数：1  
标签：题目 记录 int 练习 cin num return id define

A.Round Dance

Problem

一张图中有 \(n\) 个点，每个点都有两条边，现在给出每个点两条边中任意一条，请求出整张图中可能的环的最大数和最小数。

Solution

首先我们将点 \(i\) 和点 \(a_i\) 之间连一条双向边。

  1. 求环最大数量：要环数最大，就要环的长度最小。因为相联通的点一定在同一个环内，每一个联通块内的点相互联通，所以我们直接求出联通块的数量即可。
  2. 求环最小数量：要环数最小，就要环的长度最大，所以我们想办法将部分联通块连起来。部分联通块是长度大于 2 的环，无法和别的联通块拼接，所以我们先求出这些环的数量；然后我们可以将剩下的所有不是长度大与 2 的环的联通块拼成一个环。两者相加即为答案（注意判断是否有不是长度大与 2 的环的联通块）。

Code

#include<bits/stdc++.h>
#define N 200005 
using namespace std;
int T,n,a[N],vis[N],ansx,ansn,f,sum;
set<int>g[N];
void dfs(int);
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)g[i].clear();
		ansx=0,ansn=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			g[i].insert(a[i]);
			g[a[i]].insert(i);
		}
		memset(vis,0,sizeof vis);
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				++ansx;
				vis[i]=1;
				f=1,sum=0;
				dfs(i);
				if(f&&sum>2)++ansn;
			}
		}
		cout<<ansn+(ansx-ansn>0)<<" "<<ansx<<"\n";
	} 
}

void dfs(int x){
	++sum;
	if(g[x].size()==1)f=0;
	for(int y:g[x]){
		if(vis[y])continue;
		vis[y]=1;
		dfs(y);
	}
}

B.Path Queries

Problem

给你一棵 \(n\) 个点的树，每条边都有权值。问你 \(m\) 次问题，每次给你一个 \(p\)，请求出最大权值不大于 \(p\) 的简单路径数量。

Solution

首先我们需要知道一点，在一棵大小为 \(n\) 的树中，简单路径数量为 \(\frac{n\times (n-1)}{2}\)。

做法就是将 \(m\) 个询问按从小到大排序，再将 \(n-1\) 条边按边权从小到大排序，然后遍历这 \(m\) 个查询，将不大于这个查询的边建起来（这时候排序边就起作用了），同时维护一下每个联通块的大小，再将两个联通块加到一起时再重新计算一下最短路径的数量即可。

Code

#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n,m,q,lst,f[N],num[N],ans[N],sum;
struct edge{int u,v,w;}e[N];
struct node{int x,id;}a[N];
int cmp(node a,node b){return a.x<b.x;}
int tmp(edge a,edge b){return a.w<b.w;}
int findf(int x){
	if(x==f[x])return x;
	return f[x]=findf(f[x]);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)f[i]=i,num[i]=1;
	for(int i=1;i<n;i++)cin>>e[i].u>>e[i].v>>e[i].w;
	for(int i=1;i<=m;i++)cin>>a[i].x,a[i].id=i;
	sort(a+1,a+1+m,cmp);
	sort(e+1,e+n,tmp);
	for(int d=1;d<=m;d++){
		int i;
		for(i=lst+1;i<n&&e[i].w<=a[d].x;i++){
			int x=findf(e[i].u),y=findf(e[i].v);
			if(x!=y){
				sum-=(num[x]*(num[x]-1)/2+num[y]*(num[y]-1)/2);
				num[x]+=num[y];
				sum+=(num[x]*(num[x]-1))/2;
				f[y]=x;
			}
		}
		lst=i-1;
		ans[a[d].id]=sum;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<" ";
	return 0;
}

C.Vlad and the Mountains

Problem

给你一张图，点 \(i\) 有相应的点权 \(h_i\)，从 \(i\) 到 \(j\) 需要花费 \(h_j-h_i\) 的能量（如果为负即为补充相应绝对值），共 \(q\) 次询问，每次询问从 \(s\) 到 \(t\)，初始能量值为 \(e\)，能否保证有一条路线，使得能量值始终不低于 0。

Solution

首先我们能需要想到一点：从 \(i\) 到 \(j\) 需要花费 \(h_j-h_i\) 的能量值，从 \(j\) 到 \(k\) 需要花费 \(h_k-h_j\) 的能量值，也就是从 \(i\) 到 \(j\) 到 \(k\) 需要花费 \(h_j-h_i-h_j+h_k=h_k-h_i\) 的能量值，也就是说，从点 \(a\) 到点 \(b\)需要花费 \(h_b-h_a\) 的能量值而与路途无关。

那么问题就可以转化为：找一条从 \(s\) 到 \(t\) 的路径，使得路上的每个点 \(i\) 都保证 \(e-(h_i-h_s)\ge 0\)，也就是保证 \(e+h_s\ge h_i\)，再转化一步，就是让这条路径上的 \(h\) 的最大值保证 \(e+h_s\ge h_{max}\)。

熟悉吗？太熟悉了！这不就是上一题吗！同样，我们进行排序后建边的操作，同时用并查集来判断连通性即可。

Code

#include<bits/stdc++.h>
#define Pr pair<int,int>
#define N 200005
#define M 200005
#define int long long
using namespace std;
int T,n,m,q,f[N],x[N];
vector<int>g[N];
string ans[N];
int findf(int x){
	if(x==f[x])return x;
	return f[x]=findf(f[x]);
}
struct node{
	int st,ed,e,id;
}a[N];
struct Nd{
	int x,id;
}p[N];
int cmp(node a,node b){
	return x[a.st]+a.e<x[b.st]+b.e;
}
int tmp(Nd a,Nd b){
	return a.x<b.x;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			f[i]=p[i].id=i;
			cin>>p[i].x;
			g[i].clear();
			x[i]=p[i].x;
		}
		for(int i=1;i<=m;i++){
			int a,b;
			cin>>a>>b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		cin>>q;
		for(int i=1;i<=q;i++){
			cin>>a[i].st>>a[i].ed>>a[i].e;
			a[i].id=i;
		}
		sort(a+1,a+1+q,cmp);
		sort(p+1,p+1+n,tmp);
		int lst=0;
		for(int d=1;d<=q;d++){
			int i,num=x[a[d].st]+a[d].e;
			for(i=lst+1;i<=n&&p[i].x<=num;i++){
				int fx=findf(p[i].id);
				for(int y:g[p[i].id]){
					if(x[y]<=num){
						int fy=findf(y);
						if(fx!=fy)f[fy]=fx;
					}
				}
			}
			lst=i-1;
			if(findf(a[d].st)==findf(a[d].ed))ans[a[d].id]="YES\n";
			else ans[a[d].id]="NO\n";
		}
		for(int i=1;i<=q;i++)cout<<ans[i];
		cout<<"\n";
	}
	return 0;
}

D.Information Graph

Problem

给你 \(n\) 个点，在将其连城一棵树的过程中对 \(x\) 到 \(x\) 目前的祖宗打上一个标记，同时查询某个标记是否存在于某个节点上。

Solution

非常板的一道树上差分+线段树合并。在输入时记录一下修改操作的当前节点和祖宗节点，然后离线修改，将节点 \(x\) 的 \(y\) 标记加一，给他当时祖宗节点的父亲节点 \(y\) 标记减一，最后跑一遍 dfs 进行线段树合并操作，合并时顺便统计一下答案即可。

Code

#include<bits/stdc++.h>
#define Pr pair<int,int>
#define N 100005
using namespace std;
int n,m,op,fa[N],f[N],cnt,a[N],b[N],num,rt[N],vis[N],id[N];
vector<int>g[N];
vector<Pr>v[N];
string ans[N];
struct node{
	int ls,rs,sum;
}t[N<<4];
struct s_tree{
	int idcnt=0;
	void add(int &id,int l,int r,int x,int val){
		if(!id)id=++idcnt;
		if(l==r){
			t[id].sum+=val;
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid)add(t[id].ls,l,mid,x,val);
		else add(t[id].rs,mid+1,r,x,val);
		t[id].sum=t[t[id].ls].sum+t[t[id].rs].sum;
	}
	int query(int id,int l,int r,int x){
		if(!id||!t[id].sum)return 0;
		if(l==r)return t[id].sum;
		int mid=(l+r)>>1;
		if(x<=mid)return query(t[id].ls,l,mid,x);
		else return query(t[id].rs,mid+1,r,x);
	}
	int merge(int a,int b,int l,int r){
		if(!a||!b)return a|b;
		if(l==r){
			t[a].sum+=t[b].sum;
			return a;
		}
		int mid=(l+r)>>1;
		t[a].ls=merge(t[a].ls,t[b].ls,l,mid);
		t[a].rs=merge(t[a].rs,t[b].rs,mid+1,r);
		t[a].sum+=t[b].sum;
		return a;
	}
}tr;
void dfs(int x){
	for(int y:g[x]){
		if(vis[y])continue;
		vis[y]=1;
		dfs(y);
		rt[x]=tr.merge(rt[x],rt[y],1,cnt);
	}
	for(auto y:v[x]){
		if(tr.query(rt[x],1,cnt,y.first))ans[y.second]="YES\n";
		else ans[y.second]="NO\n";
	}
}
int findf(int x){
	if(x==f[x])return x;
	return f[x]=findf(f[x]);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		cin>>op;
		if(op==1){
			int x,y;
			cin>>x>>y;
			f[x]=y;
			fa[x]=y;
			g[y].push_back(x);
		}
		if(op==2){
			cin>>a[++cnt];
			b[cnt]=findf(a[cnt]);
		}
		if(op==3){
			int x,y;
			cin>>x>>y;
			v[x].push_back({y,++num});
		}
	}
	for(int i=1;i<=cnt;i++){
		tr.add(rt[a[i]],1,cnt,i,1);
		tr.add(rt[fa[b[i]]],1,cnt,i,-1);
	}
	for(int i=1;i<=n;i++){
		int x=f[i];
		if(vis[x])continue;
		vis[x]=1;
		dfs(x);
	}
	for(int i=1;i<=num;i++)cout<<ans[i];
	return 0;
}

E.白雪皑皑

Problem

给你一个全部为 0 的长为 \(n\) 的序列，操作 \(m\) 次，第 \(i\) 次将 \(i\times p+q\mod n\) 到 \(i\times q+p\mod n\) 区间内的值修改为 \(i\)，求最后的状态。

Solution

F1：

直接线段树区间修改即可。同时，因为求操作的边界时系数不变，且进行去摸操作，所以一定有循环节，直接找到最后一个循环节进行修改即可。

F2:

用并查集判断连通性。选择从后往前操作，因为后面的会把前面的覆盖。用 \(f_i\) 表示 \(i\) 和 \(i\) 前面中最近一个可以修改的，也就是还没有被修改的。在修改的同时维护 \(f\) 即可。

Code

F1：

#include<bits/stdc++.h>
#define N 1000005
#define int long long
using namespace std;
int n,m,p,q;
struct node{
	int num,l,r,lazy;
}t[N<<2];
struct s_tree{
	#define ls id<<1
	#define rs id<<1|1
	void addtag(int id,int val){t[id].lazy=t[id].num=val;}
	void pushdown(int id){
		if(t[id].lazy){
			addtag(ls,t[id].lazy);
			addtag(rs,t[id].lazy);
			t[id].lazy=0;
		}
	}
	void build(int id,int l,int r){
		t[id].l=l,t[id].r=r,t[id].num=t[id].lazy=0;
		if(l==r)return;
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
	void add(int id,int l,int r,int x){
		if(l<=t[id].l&&t[id].r<=r){
			addtag(id,x);
			return;
		}
		pushdown(id);
		int mid=(t[id].l+t[id].r)>>1;
		if(l<=mid)add(ls,l,r,x);
		if(r>mid)add(rs,l,r,x);
		if(t[ls].num==t[rs].num)t[id].num=t[ls].num;
		else t[id].num=0;
	}
	int query(int id,int x){
		if(t[id].num||t[id].l==t[id].r)return t[id].num;
		pushdown(id);
		int mid=(t[id].l+t[id].r)>>1;
		if(x<=mid)return query(ls,x);
		else return query(rs,x);
	}
}tr;
signed main(){
	cin>>n>>m>>p>>q;
	tr.build(1,1,n);
	int a=(m*p+q)%n+1,b=(m*q+p)%n+1;
	int k=1;
	for(int i=m-1;i;i--){
		if((i*p+q)%n+1==a&&(i*q+p)%n+1==b){
			k=i+1;
			break;
		}
	}
	for(int i=k;i<=m;i++){
		int l=(i*p+q)%n+1,r=(i*q+p)%n+1;
		if(l>r)swap(l,r);
		tr.add(1,l,r,i);
	}
	for(int i=1;i<=n;i++)cout<<tr.query(1,i)<<"\n";
	return 0;
}

F2：

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,m,p,q,f[N],c[N];
int findf(int x){
	if(x==f[x])return x;
	return f[x]=findf(f[x]);
}
signed main(){
	cin>>n>>m>>p>>q;
	int a=(m*p+q)%n+1,b=(m*q+p)%n+1;
	int k=1;
	for(int i=m-1;i;i--){
		if((i*p+q)%n+1==a&&(i*q+p)%n+1==b){
			k=i+1;
			break;
		}
	}
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=m;i>=k;i--){
		int l=(i*p+q)%n+1,r=(i*q+p)%n+1;
		if(l>r)swap(l,r);
		for(int j=r;j>=l;j=f[j]){
			int t=findf(j);
			if(t==j)c[j]=i,f[j]=findf(j-1);
		}
	}
	for(int i=1;i<=n;i++)cout<<c[i]<<"\n";
	return 0;
}

标签：题目,记录,int,练习,cin,num,return,id,define
From： https://www.cnblogs.com/WDY-Hodur/p/18687693

相关文章

  • 记录一些 Windows 下的 UI 自动化测试工具
    1、WinAppDriver正如其名称，算是较为底层的工具，需要在其它测试框架下进行使用貌似可以支持对UWP、WinForm、WPF、Win32窗口程序的识别与测试但看着好几年没更新过了，也许不需要再更新了？项目地址：https://github.com/microsoft/WinAppDriver2、Appium通过抽象驱动层，可以跨平台......
  • 【问题记录】JVM进程崩溃（hs_err_pid.log致命错误日志）
    一个使用kafka的Java项目，在Windows环境启动后不久出现进程崩溃的情况，反复验证偶发的能得到hs_err_pid.log致命错误日志，始终没有生成coredump。通过错误日志确实看到了导致崩溃的线程堆栈跟kafka客户端有关，但栈顶显示当前在执行native本地代码，我们分别替换了kafka-clients的历史版......
  • QSound相关记录
    controlC0-->用于声卡的控制，例如通道选择，混音，麦克风的控制等midiC0D0-->用于播放midi音频pcmC0D0c-->用于录音的pcm设备pcmCoDop-->用于播放的pcm设备seq-->音序器timer-->定时器其中，COD0代表的是声卡0中的设备0，pcmC0D0c最后一个c代表capture，pcmC0D0p最后一个p代表p......
  • 【做题记录】2025提高刷题-dp
    A.Min-FundPrison(Medium)考虑一个边双连通分量一定不可能分为合法的两部分，于是进行缩点。缩完后显然是一个森林。设\(dp_{i,j,0/1}\)表示第一堆有\(i\)个点，第二堆有\(j\)个点，两堆点有没有用一条边连起来的最小花费。对于每棵树，考虑将它加入第一堆/加入第二堆/一部分加......
  • 打靶记录25——darkhole_2
    靶机：https://vulnhub.com/entry/darkhole-2,740/下载（镜像）：https://download.vulnhub.com/darkhole/darkhole_2.zip难度：高目标：获得Root权限+2Flag攻击方法：主机发现端口扫描Git库泄露源码分析SQL注入本地端口转发密码爆破水平提权1、2Root提权1、2主......
  • 如何准确查看和记录网站内容的修改时间以确保数据完整性
    准确查看和记录网站内容的修改时间对于维护数据完整性和追踪历史版本至关重要。以下是详细的步骤和建议：利用CMS系统自带功能：如果使用的是内容管理系统（如WordPress、Joomla），大多数平台都内置了版本控制和日志记录功能。例如，在WordPress中，可以通过“修订历史”查看文章或页面的......
  • 如何记录网站后台的修改内容
    问题描述：如何记录网站后台的修改内容。解决方法：使用日志记录功能：许多网站后台管理系统都提供了日志记录功能，可以记录用户的操作行为和修改内容。启用日志记录功能后，系统会自动记录每次修改的时间、用户、操作类型、修改内容等信息。自定义日志记录：如果网站后台管理系统没有提......
  • 【CodeForces训练记录】Codeforces Round 1000 (Div. 2)
    训练情况赛后反思C题猜了个假结论WA4，每次选择度最多的删掉，在连续三个度都是最大的情况下，删中间的会寄A题有点前缀和的感觉，\([1,l]\)互质个数为\(l\),\([1,r]\)互质个数为\(r\)，所以区间\([l,r]\)的个数就是\(r-l\)，特判一下\(l=1,r=1\)的情况答案是\(1\)点击查看代......
  • 可达鸭J3题目 拦截导弹
    题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所......
  • 【vjudge训练记录】大一寒假专项训练——前缀和/差分
    训练情况A题前缀和模板题，我们输入完\(a_i\)后直接求前缀和\(a_i=a_i+a_{i-1}\)，求区间\([l,r]\)的和就为\(a_r-a_{l-1}\)点击查看代码#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intn,m;c......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99