20210815 图论模拟赛

一次运气很好的模拟赛。

赛前

是有点开心也有点紧张的,一方面因为图论专题本人比较简单,另一方面其实这方面一向debug起来很费劲……

赛时

开题便觉得自己完了。四道题都没看懂可怎么做啊?
再度遍历后,“总算”读懂了\(T2\)和\(T3\)。\(T4\)因为“题面引起歧义”(出题人亲承)一直没有搞出样例。

眼看着过了近\(1h\),想着必须要开始写题了,就开了\(T4\)。感觉像是签到题,但是自己理解的题意总是和样例相差1,于是只好输出ans-1(ans表示经过点的数量,ans-1表示经过边的数量)。

大概20分钟敲完\(T4\)并调试完,开的\(T2\)。一眼望去是种类并查集,再次基础上思考发现种类并查集可能性很大。故写上后用着并不太正确的数学方法调出了样例和自己造的数据。

赛后:这里是数学方法确实不正确,另外此题考查也完全不是并查集……

约用了一个小时。

然后看着\(T3\),一道暴力可以稳拿\(60\)的题,还是想了近半个小时的正解,一直都是很接近,但是还差那么一点……

剩余约\(1h20\min\)放弃,开敲暴力。

剩余\(40\min\),还是没太舍得放下\(T1\)。连想带敲了\(30\min\)后发现题面理解错了……无解只能准备文件后提交……

赛时结束还是很慌的,感觉自己爆了。

赛后

期望得分:\(0+[0,50]+60+[0,100]=[0,210]\)

实际得分:\(0+30+60+10=190\).

说实话,看到这个分数还是非常惊喜的。认真想的题没有挂分,还得到了一些意外的分数。

​ T1是确实想错了,加上题目本身知识点比较综合,丢分不是很可惜。

​ T2想错了还能拿到\(30pts\),确实幸运。

​ T3(完全没调试)就稳拿了60的暴力分,还是很满意的。

​ T4在题目理解歧义的情况下还是AC了。

嗯。很满意的分数。

T1

从给定的每个长度为3的子串中构造出原串。

思路很奇妙的一道题。

对于每个串,可以看做前两位与某个串的后两位相同,同理后两位可以与某个的前两位相同。

由此想到:可以从自己前两位向自己后两位建一条边。

比如abc,则是ab\(\to\)bc.

特殊地,aaa视为建一条aa到自己的边。

如此下来,可以用一系列边和点确定这个序列。

剩下的问题,则是如何走完这些边。

通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。

通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。

具有欧拉回路的无向图或有向图称为欧拉图。

于是,考虑在构造出的图上判断是否可以找出欧拉路径即可。输出答案即为根据欧拉路径构造原串。

理论如上。实际还有一个细节:如何建图?

显然,用aa这种表示节点肯定不合适。

于是,用类似于处理hash的思想,将其构造出对应的节点,离散化后使用。最后注意还原的细节即可。

#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 4e5+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
	ll ret = 0 ; char ch = ' ' , c = getchar();
	while(!(c >= '0' && c <= '9')) ch = c , c = getchar();
	while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
	return ch == '-' ? -ret : ret;
}
int n,m;
int ecnt = -1,head[N],ind[N],oud[N];

int f[N];
int find(int x){return f[x] == x ? x : find(f[x]);}
inline void merge(int x,int y){f[find(x)] = find(y);}
struct Edge{int to,nxt;}e[N];
inline void add_edge(int u,int v){
//	printf("   add (%d->%d)\n",u,v);
	e[++ecnt] = (Edge){v,head[u]};
	head[u] = ecnt;
	ind[v] ++ , oud[u] ++;
	merge(u,v);
}
inline int getint(char c){return c >= '0' && c <= '9' ? c-'0'+1 : c >= 'a' && c <= 'z' ? c-'a'+11 : c-'A'+37;}
inline char getch(int x){ return x >= 1 && x <= 10 ? x+'0'-1 : x >= 11 && x <= 36 ? x+'a'-11 : x+'A'-37;}

stack<int>stk;
void dfs(int u){
	for(int i = head[u] ; ~i ; i = head[u]){
		int v = e[i].to;
		head[u] = e[i].nxt;
//		printf("  dfs(%d,%d)\n",u,v);
		dfs(v);
	}
	stk.push(u);
}
int a[N][2],p[N];
void init(){
	for(int i = 1 ; i <= m ; i ++)
		head[i] = -1 , ind[i] = oud[i] = 0 , f[i] = i;
	ecnt = -1;
}
void work(){
	char ch[4];
	n = read();
	for(int i = 1 ; i <= n ; i ++)
		scanf("%s",ch+1),
		p[(i-1)*2+1] = a[i][0] = getint(ch[1])*65+getint(ch[2]) , p[(i-1)*2+2] = a[i][1] = getint(ch[2])*65+getint(ch[3]);
	
	sort(p+1,p+n+n+1);
	m = unique(p+1,p+n+n+1)-p-1;
	init();
	for(int i = 1 ; i <= n ; i ++){
		int u = lower_bound(p+1,p+m+1,a[i][0])-p,
			v = lower_bound(p+1,p+m+1,a[i][1])-p;
//		printf("  pre: add[%d] -> [%d]\n",a[i][0],a[i][1]);
		add_edge(u,v);
	}
	int s = 1 , sum = 0;
	for(int i = 1 ; i <= m ; i ++){
		if(abs(ind[i]-oud[i]) > 1){puts("NO");return;}
		if(oud[i]-ind[i] == 1) s = i;
		sum += oud[i] != ind[i];
		if(i != 1 && find(i) != find(i-1)){puts("NO");return;}
	}
//	printf("sum = %d , m = %d\n",sum,m);
	if(sum != 0 && sum != 2){puts("NO");return;}
	
	puts("YES");
	dfs(s);
	if(!stk.empty())
		putchar(getch(p[stk.top()]/65));
	while(!stk.empty())
		putchar(getch(p[stk.top()]%65)),stk.pop();
	puts("");
}
signed main(){
//	fo("recover");
	int T = read();
	while(T--)
		work();
}
/*
1
5
ACA
ABA
ABA
CAB
BAC
*/

T2

一道很好的题啊。

对于每个有敌对关系的节点,我们标记为二分图染成不同颜色。对于跟他敌对的点敌对的点(有点拗口hhh),通过递归的方式也标记上(此时就要强制与它是同色了。)若染色冲突则不可行。

否则,通过以上方式,可以将节点分割为多个联通块。

问题转化:在每组两个的多组联通块中各选取其中一个,使得选取总值最接近\(\dfrac n2\)。

此过程使用分组背包来实现。

#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e2+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
	ll ret = 0 ; char ch = ' ' , c = getchar();
	while(!(c >= '0' && c <= '9')) ch = c , c = getchar();
	while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
	return ch == '-' ? -ret : ret;
}
int n;
int a[N][N];
bool vis[N],col[N];
int siz[N][2],tot; 
int dp[N][N]; 

bool dfs(int u,int co,int bel){
	if(vis[u]) return col[u] == co;
//	printf("  color [%d]->%d :%d\n",u,co,bel);
	vis[u] = 1, col[u] = co;
	siz[bel][co] ++;
	for(int v = 1 ; v <= n ; v ++)
		if(!a[u][v])
			if(!dfs(v,!co,bel))
				return 0;
	return 1;
}
void init(){
	tot = 0;
	memset(siz,0,sizeof(siz));
	memset(dp,0,sizeof(dp));
	memset(vis,0,sizeof(vis));
}
void work(){
	n = read();
	init();
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= n ; j ++)
			a[i][j] = read();
	if(n == 1){puts("No solution");return;}
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1; j <= n ; j ++)
			a[i][j] = a[j][i] = a[i][j] & a[j][i];
			
	for(int i = 1 ; i <= n ; i ++)
		if(!vis[i]){
			tot ++;
			if(!dfs(i,0,tot)){puts("No solution");return;}
		}
	
	dp[0][0] = 1;
	int ans = INF;
	for(int i = 1 ; i <= tot ; i ++)
		for(int j = n ; j ; j --)
			for(int k = 0 ; k <= 1 ; k ++)
				if(j >= siz[i][k])
					dp[i][j] |= dp[i-1][j-siz[i][k]];
//	for(int i = 0 ; i <= n ; i ++)
//		printf("%d:%d\n",i,dp[i]);
	for(int i = 0 ; i <= n ; i ++)
		if(dp[tot][i])
			ans = min(ans,abs(n-i*2));
	printf("%d\n",ans);
}
signed main(){
//	fo("team");
	int T = read();
	while(T--)
		work();
	return 0;
}

T3

瓶颈就在,经过的边必须是在\([L,R]\)区间内建好的。

考虑进行离线,边权为建设时间。

将多个询问按左端点降序排序,这样处理起来,只有加边操作

每添加一条边\(u\to v\)时,都只有dis[u]和可dis[v]能改变。

这样,令dis[u][k] = dis[v][k] = min(dis[u][k],ans[v][k]),直接维护即可。

#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e3+5 , M = 1e5+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
	ll ret = 0 ; char ch = ' ' , c = getchar();
	while(!(c >= '0' && c <= '9')) ch = c , c = getchar();
	while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
	return ch == '-' ? -ret : ret;
}
int n,m,k;
struct Edge{int u,v;}e[M];
struct Ask{int l,r,s,t,id;}q[M]; 
inline bool operator < (const Ask a,const Ask b){return a.l > b.l;}
int dis[N][N],ans[M];
signed main(){
//	fo("plan");
	memset(dis,0x3f,sizeof(dis)) ;
	n = read() , m = read() , k = read();
	for(int i = 1 ; i <= m ; i ++){
		e[i].u = read() , e[i].v = read();
 	}
//	printf(" %d -> %d\n",st,ed);
	for(int i = 1 ; i <= k ; i ++){
		int l = read() , r = read() , s = read() , t = read();
		q[i] = (Ask){l,r,s,t,i};
	}
	sort(q+1,q+k+1);
	q[0].l = m+1;
	for(int i = 1 ; i <= k ; i ++) {
		int s = q[i].s , t = q[i].t;
//		printf("  ask[%d -> %d],(%d,%d)\n",s,t,q[i].l,q[i].r);
		for(int j = q[i-1].l-1 ; j >= q[i].l ; j --){
			int u = e[j].u , v = e[j].v;
//			printf(" add[%d][%d]\n",u,v);
			dis[u][v] = dis[v][u] = j;
			for(int j = 1 ; j <= n ; j ++)
				dis[u][j] = dis[v][j] = min(dis[u][j],dis[v][j]);
		}
//		printf("dis = %d\n",dis[s][t]);
		ans[q[i].id] = dis[s][t] <= q[i].r;
	}
	for(int i = 1 ; i <= k ; i ++)
		puts(ans[i] ? "Yes" : "No");
	return 0;
}

T4

很水的签到题,这里就不再赘述了吧……

只需要判断新建边和序列的关系,给无向边定向即可。

#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 5e4+5 , M = 2e5+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
	ll ret = 0 ; char ch = ' ' , c = getchar();
	while(!(c >= '0' && c <= '9')) ch = c , c = getchar();
	while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
	return ch == '-' ? -ret : ret;
}
int n,m,k;
int ecnt,head[N];
struct Edge{int to,nxt;}e[M<<1];
inline void add_edge(int u,int v){
//	printf("add (%d,%d)\n",u,v);
	e[++ecnt] = (Edge){v,head[u]};
	head[u] = ecnt;
}
int buc[N];
queue<int>q;
int st,ed;
int dis[N];bool vis[N];
inline void init(){
	memset(head,-1,sizeof(head));ecnt = -1;
	for(int i = 1 ; i <= n ; i ++)buc[i] = 0,vis[i] = 0;
}
void bfs(){
	while(!q.empty())q.pop();
	vis[st] = 1 , dis[st] = 0;
	q.push(st);
	while(!q.empty()){
		int u = q.front();q.pop();
		if(u == ed)return;
		for(int i = head[u] ; ~i ; i = e[i].nxt){
			int v = e[i].to;
//			printf("bfs(%d %d)\n",u,v);
			if(!vis[v])
				dis[v] = dis[u] + 1,
				vis[v] = 1,
				q.push(v);
		}
	}
}
void work(){
	n = read() , m = read() , k = read();
	init();
	int u = read(),v;
	buc[u] = 1;st = u;
	for(int i = 1 ; i <= k ; i ++){
		v = read();
		buc[v] = i + 1;
		add_edge(u,v);
		u = v;
	}
	ed = v;
//	printf(" %d -> %d\n",st,ed);
	for(int i = 1 ; i <= m - k ; i ++){
		u = read() , v = read();
		if(!buc[u] || !buc[v])continue;
		if(buc[u] < buc[v])add_edge(u,v);
		else add_edge(v,u);
	}
	bfs();
	printf("%d\n",dis[ed]);
}
signed main(){
//	fo("seqpath");
	int T = read();
	while(T--)
		work();
	return 0;
}

明天接种疫苗第二针。早睡早睡。

上一篇:《Codeforces Round #737 (Div. 2)》


下一篇:【HarmonyOS鸿蒙应用开发】ListContainer简单新闻案例模拟