专栏文章

7.12

bbokaro_kyoku_mania
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miowygai
此快照首次捕获于
2025/12/03 02:30
3 个月前
此快照最后确认于
2025/12/03 02:30
3 个月前
查看原文
P1276:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{
		c=getchar();
		if(c=='-'){
			sign=-1;
		}
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline string readstr(){
	string str="";
	char ch=getchar();
	while(ch==' '||ch=='\n'||ch=='\r'){
		ch=getchar();
	}
	while(ch!='\n'&&ch!='\r'){
		str+=ch;
		ch=getchar();
	}
	return str;
}
inline void printstr(string s){
	for(int i=0;s[i]!='\0';i++){
		putchar(s[i]);
	}
}
int n,l,ju,ans1,x,y,ans2;
int p[101010],c[101010],m[101010];
signed main(){
	memset(p,1,sizeof(p)); 
	memset(c,0,sizeof(c)); 
	read(l);
	read(n); 
	for(int i=1;i<=n;i++){
		read(ju);
		read(x);
		read(y);
		if(ju==0){
			for(int j=x;j<=y;j++){
				p[j]=0;
				m[j]=0;
				if(c[j]==1){
					ans2++;
					c[j]=0;
				}
			}
		}
		else{
			for(int j=x;j<=y;j++){
				if(p[j]==0){
					c[j]=1;
					m[j]=1;
				}
				p[j]=1;
			}
		}
	}
	for(int i=0;i<=l;i++){
		if(m[i]==1){
			ans1++; 
		}
	}
	write(ans1);
	putchar('\n');
	write(ans2);
	
	
	
	
	return 0; 
}
P1347:
CPP
#include<bits/stdc++.h>
//#define int long long
using namespace std;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{
		c=getchar();
		if(c=='-'){
			sign=-1;
		}
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline string readstr(){
	string str="";
	char ch=getchar();
	while(ch==' '||ch=='\n'||ch=='\r'){
		ch=getchar();
	}
	while(ch!='\n'&&ch!='\r'){
		str+=ch;
		ch=getchar();
	}
	return str;
}
inline void printstr(string s){
	for(int i=0;s[i]!='\0';i++){
		putchar(s[i]);
	}
}
vector<int>e[30];
int n,m;
queue<int>q;
string s,ans;
int in[30];
int topusort(){
	ans="";
	while(!q.empty()){
		q.pop();
	}
	for(int i=1;i<=n;i++){
		in[i]=0;
	}
	for(int i=1;i<=n;i++){
		for(auto to:e[i]){
			in[to]++;
		}
	}
	for(int i=1;i<=n;i++){
		if(!in[i]){
			q.push(i);
		}
	}
	int k=0;
	while(!q.empty()){
		if(q.size()!=1)k=2;
		int x=q.front();
		q.pop();
		ans+=char(x+'A'-1);
		for(auto to:e[x]){
			--in[to];
			if(!in[to]){
				q.push(to);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(in[i])k=1;
	}
	return k;
}
signed main(){
	read(n);
	read(m);
	for(int i=1;i<=m;i++){
		s=readstr();
		e[s[0]-'A'+1].push_back(s[2]-'A'+1);
		int op=topusort();
		if(op==0){
			printf("Sorted sequence determined after %d relations: ",i);
			printstr(ans);
			putchar('.');
			putchar('\n');
			return 0;
		}
		if(op==1){
			printf("Inconsistency found after %d relations.\n",i);
			return 0;
		}
	}
	string ansss="Sorted sequence cannot be determined.";
	printstr(ansss);
	
	
	
	
	
	
	return 0;
}
P1807:
CPP
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{
		c=getchar();
		if(c=='-'){
			sign=-1;
		}
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline string readstr(){
	string str="";
	char ch=getchar();
	while(ch==' '||ch=='\n'||ch=='\r'){
		ch=getchar();
	}
	while(ch!='\n'&&ch!='\r'){
		str+=ch;
		ch=getchar();
	}
	return str;
}
inline void printstr(string s){
	for(int i=0;s[i]!='\0';i++){
		putchar(s[i]);
	}
}
const int N=1e5+50;
queue<int>q;
vector<pair<int,int> >e[N];
int n,m,f[N];
int in[N];
void topu(){
	memset(f,-0x3f,sizeof(f));
	f[1]=0;
	for(int i=1;i<=n;i++){
		for(auto to:e[i]){
			in[to.first]++;
		}
	}
	for(int i=1;i<=n;i++){
		if(!in[i]){
			q.push(i);
		}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(auto to:e[x]){
			f[to.first]=max(f[to.first],f[x]+to.second);
			in[to.first]--;
			if(!in[to.first])q.push(to.first);
		}
	}
}
signed main(){
	read(n);
	read(m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		read(u);
		read(v);
		read(w);
		e[u].push_back(make_pair(v,w));
	}
	topu();
	if(f[n]<-1e8)write(-1);
	else write(f[n]);
	
	
	
	
	
	return 0;
}
P3379:
(lca模板)
CPP
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{
		c=getchar();
		if(c=='-'){
			sign=-1;
		}
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline string readstr(){
	string str="";
	char ch=getchar();
	while(ch==' '||ch=='\n'||ch=='\r'){
		ch=getchar();
	}
	while(ch!='\n'&&ch!='\r'){
		str+=ch;
		ch=getchar();
	}
	return str;
}
inline void printstr(string s){
	for(int i=0;s[i]!='\0';i++){
		putchar(s[i]);
	}
}
const int N=1e6+50;
int n,m,s;
int head[N],nxt[N<<1],to[N<<1],tot;
int deep[N];
int p[N][21];
void add(int x,int y){
	nxt[tot]=head[x];
	to[tot]=y;
	head[x]=tot++;
}
void dfs(int x){
	for(int i=head[x];~i;i=nxt[i]){
		if(to[i]!=p[x][0]){
			deep[to[i]]=deep[x]+1;
			p[to[i]][0]=x;
			dfs(to[i]);
		}
	}
}
int lca(int x,int y){
	if(deep[x]<deep[y])swap(x,y);
	for(int i=20;i>=0;i--){
		if(deep[x]-deep[y]>=(1<<i)){
			x=p[x][i];
		}
	}
	if(x==y)return x;
	for(int i=20;i>=0;i--){
		if(p[x][i]!=p[y][i]){
			x=p[x][i];
			y=p[y][i];
		}
	}
	return p[x][0];
}
signed main(){
	memset(head,-1,sizeof(head));
	read(n);
	read(m);
	read(s);
	for(int i=1;i<=n-1;i++){
		int u,v;
		read(u);
		read(v);
		add(u,v);
		add(v,u); 
	}
	dfs(s);
	for(int j=1;j<=20;j++){
		for(int i=1;i<=n;i++){
			p[i][j]=p[p[i][j-1]][j-1];
		}
	}
	while(m--){
		int u,v;
		read(u);
		read(v);
		write(lca(u,v));
		putchar('\n');
	}
	
	
	
	return 0;
}
(离线做法)
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{
		c=getchar();
		if(c=='-'){
			sign=-1;
		}
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline string readstr(){
	string str="";
	char ch=getchar();
	while(ch==' '||ch=='\n'||ch=='\r'){
		ch=getchar();
	}
	while(ch!='\n'&&ch!='\r'){
		str+=ch;
		ch=getchar();
	}
	return str;
}
inline void printstr(string s){
	for(int i=0;s[i]!='\0';i++){
		putchar(s[i]);
	}
}
const int N =5e5+50;
int n,m,s,p[N],fa[N],ans[N];
vector<pair<int,int> >q[N];
int head[N],nxt[N<<1],to[N<<1],tot;
void add(int x,int y){
	nxt[tot]=head[x];
	to[tot]=y;
	head[x]=tot++;
}
int get_p(int x){
	return p[x]==x?x:p[x]=get_p(p[x]);
}
bool vis[N];
void dfs(int x){
	vis[x]=1;
	for(auto t:q[x]){
		if(vis[t.first]){
		ans[t.second]=get_p(t.first);
		}
	}
	for(int i=head[x];~i;i=nxt[i]){
		if(to[i]!=fa[x]){
			fa[to[i]]=x;
			dfs(to[i]);
		}
	}
	p[x]=fa[x]; 
}
signed main(){
	memset(head,-1,sizeof(head));
	read(n);
	read(m);
	read(s);
	for(int i=1;i<=n-1;i++){
		int u,v;
		read(u);
		read(v);
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=m;i++){
		int u,v;
		read(u);
		read(v);
		q[u].push_back(make_pair(v,i));
		q[v].push_back(make_pair(u,i)); 
	}
	for(int i=1;i<=n;i++){
		p[i]=i;
	}
	dfs(s);
	for(int i=1;i<=m;i++){
		write(ans[i]);
		putchar('\n');
	}
		
	
	
	
	return 0;
}
(链剖做法)
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{
		c=getchar();
		if(c=='-'){
			sign=-1;
		}
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline string readstr(){
	string str="";
	char ch=getchar();
	while(ch==' '||ch=='\n'||ch=='\r'){
		ch=getchar();
	}
	while(ch!='\n'&&ch!='\r'){
		str+=ch;
		ch=getchar();
	}
	return str;
}
inline void printstr(string s){
	for(int i=0;s[i]!='\0';i++){
		putchar(s[i]);
	}
}
const int N=1e6+50;
int n,m,s;
int head[N],nxt[N<<1],to[N<<1],tot;
int deep[N];
int fa[N],hson[N],sz[N],top[N];
void add(int x,int y){
	nxt[tot]=head[x];
	to[tot]=y;
	head[x]=tot++;
}
void dfs(int x){
	sz[x]=1;
	for(int i=head[x];~i;i=nxt[i]){
		if(to[i]!=fa[x]){
			deep[to[i]]=deep[x]+1;
			fa[to[i]]=x;
			dfs(to[i]);
			sz[x]+=sz[to[i]];
			if(sz[hson[x]]<sz[to[i]]){
				hson[x]=to[i];
			}
		}
	}
}
void dfs2(int x,int t){
	top[x]=t;
	if(hson[x])dfs2(hson[x],t);
	for(int i=head[x];~i;i=nxt[i]){
		if(to[i]!=fa[x]&&to[i]!=hson[x]){
			dfs2(to[i],to[i]);
		}
	}
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]]){
			swap(x,y);
		}
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]){
		swap(x,y);
	}
	return x;
}
signed main(){
	memset(head,-1,sizeof(head));
	read(n);
	read(m);
	read(s);
	for(int i=1;i<=n-1;i++){
		int u,v;
		read(u);
		read(v);
		add(u,v);
		add(v,u); 
	}
	dfs(s);
	dfs2(s,s);
	while(m--){
		int u,v;
		read(u);
		read(v);
		write(lca(u,v));
		putchar('\n');
	}
	
	
	
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...