大一下第四周学习笔记周一 3.22（杂题）周二 3.23 （杂题 + 欧拉回路）周三 3.24 （欧拉回路）周四 3.25 （欧拉回路）周五 3.26 （欧拉回路）周六 3.27 （欧拉回路）周日 3.28 （欧拉回路）

71 阅读 0 评论 47 点赞

我是靠谱客的博主瘦瘦钢笔，最近开发中收集的这篇文章主要介绍大一下第四周学习笔记周一 3.22（杂题）周二 3.23 （杂题 + 欧拉回路）周三 3.24 （欧拉回路）周四 3.25 （欧拉回路）周五 3.26 （欧拉回路）周六 3.27 （欧拉回路）周日 3.28 （欧拉回路），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

周一 3.22（杂题）

Hongcow Builds A Nation (并查集 + 思维)

其实这道题并不难

只是在比赛中为了快点做出，乱猜是贪心，然后思路错误浪费了大量时间，依然WA

所以比赛中静下心和平时一样想题目才是发挥地最好的

这题就是用并查集处理出几个联通分量，没有被标记的联通分量看作一个大联通分量

然后联通分量内部连边，然后未被标记的大联通分量和被标记联通分量里面个数最多的连边

最后减去原来的边就ok了

其实蛮简单的

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 1e3 + 10;
int f[N], a[N], cnt[N], n, m, k;

int find(int x)
{
	if(f[x] == x) return x;
	return f[x] = find(f[x]);
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	_for(i, 1, n) f[i] = i;
	while(k--)
	{
		int x; scanf("%d", &x);
		a[x] = 1;	
	} 
	_for(i, 1, m)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		f[find(u)] = find(v);
	}
	
	int sum = 0, mx = 0, t = 0;
	_for(i, 1, n)
	{
		if(a[i]) a[find(i)] = 1;
		cnt[find(i)]++;
	}
	_for(i, 1, n)
		if(f[i] == i && a[i])
		{
			sum += cnt[i] * (cnt[i] - 1) / 2;
			if(a[i]) mx = max(mx, cnt[i]);
		}	
	_for(i, 1, n)
		if(!a[find(i)])
			t++;
	sum += mx * t + t * (t - 1) / 2;
	printf("%dn", sum - m);

	return 0;
}

Stairs and Elevators（二分查找）

这道题考试的时候都没读题，其实蛮简单的，二分一下就完事了

注意到这道题给的范围很大到1e8

所以给的坐标直接二分一下找到相邻的位置就好了

找到相邻的位置无非就四种可能，四种可能里面取最优就好了

注意可能并不需要走楼梯和电梯，当x相同的时候，要特判一下，我因为这个WA了一次

还有总是重复的量可以用变成存一下，代码会简洁很多，也容易调试

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 1e5 + 10;
int n, m, l[N], e[N], cl, ce, v;

int main()
{
	scanf("%d%d%d%d%d", &n, &m, &cl, &ce, &v);
	_for(i, 1, cl) scanf("%d", &l[i]);
	_for(i, 1, ce) scanf("%d", &e[i]);
	
	int q; scanf("%d", &q);
	while(q--)
	{
		int ans = 1e9, x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		if(y1 > y2) swap(x1, x2), swap(y1, y2);
		
		if(x1 == x2)
		{
			printf("%dn", abs(y1 - y2));
			continue;
		}
		
		int dx = abs(x1 - x2), dy = abs(y1 - y2);
		int now = lower_bound(l + 1, l + cl + 1, y1) - l;
		if(now != cl + 1) ans = min(ans, dx + dy + 2 * max(l[now] - y2, 0));
		if(now - 1 >= 1) ans = min(ans, dx + dy +  2 * abs(y1 - l[now - 1]));
		
		now = lower_bound(e + 1, e + ce + 1, y1) - e;
		dx = (dx + v - 1) / v;
		if(now != ce + 1) ans = min(ans, dx + dy + 2 * max(e[now] - y2, 0));
		if(now - 1 >= 1) ans = min(ans, dx + dy + 2 * abs(y1 - e[now - 1]));
		
		printf("%dn", ans);
	}

	return 0;
}

D. Timetable（分组背包 + 暴力）

这道题真的一言难尽

考试的时候一读完题就知道是分组背包

要预处理一下每一天翘i节课最多能少掉多少时间

结果我没怎么想清楚，感觉是贪心，然后就写了贪心

比赛时一定要和平时一样想清楚，静下心。不要随便贪心，这道题的贪心是错误的

赛后发现贪心是错误的，如果暴力求这个，复杂度理论上是500的三次方，会超时

然后我就想什么方法优化，然后一直想不出

然而最后发现不会超时，可能是因为1.25e8比较极限，没超得太远，而且数据也没那么强

我在这浪费了很多时间，一直以为会超时。有时候到1e8比较极限的时候也可以试一下，说不定数据水

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 500 + 10;
struct node{ int w, v; };
vector<node> ve[N];
int f[N], L[N], R[N];
int n, m, k, sum;

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	_for(j, 1, n)
	{
		int t = 0, cnt = 0, l; 
		_for(i, 1, m) 
		{
			int x; scanf("%1d", &x);
			if(!x) continue;
			if(!t) l = i;
			else L[++cnt] = i - t;	
			t = i;
		}	
		if(!t) continue;
		sum += t - l + 1;
		
		_for(i, 1, cnt) R[i] = L[cnt - i + 1];
		_for(i, 1, cnt) L[i] += L[i - 1], R[i] += R[i - 1];	 

		int w = 0, mx = 0;
		_for(p, 1, min(cnt, k))
		{
			mx = 0;
			_for(i, 0, p)
				mx = max(mx, L[i] + R[p - i]);
			ve[j].push_back(node{++w, mx});
		}
		ve[j].push_back(node{++w, mx + 1});
	}

	_for(i, 1, n) 
		for(int j = k; j >= 0; j--)
			REP(t, 0, ve[i].size())
			{
				int w = ve[i][t].w, v = ve[i][t].v;
				if(j >= w) f[j] = max(f[j], f[j - w] + v);
			}
	printf("%dn", sum - f[k]);
	
	return 0;
}

A. Zebras（思维 + set）

比赛时有两种思路，一种是推出规律，找1的个数和0的个数的关系，结果没推出来

第二种就是for很多遍，每一遍都得出一个序列

其实2e5的数据，尽管会删除数据，for很多遍肯定超时的，我当时就是太着急了，有一个思路还没想正确性就开始写，浪费时间又WA

那么正解肯定是for一遍，O（n）或者O（nlogn）

我想了挺久，发现可以边for就边加入各个序列当中，一个1就要找到末尾为0的序列，一个0就要找到末尾为1的序列

一开始遍历一遍末尾符合的序列结果超时

后来反应到可以用两个set来维护末尾为1的序列和末尾为0的序列的集合，每次都是logn

然后就AC了

还是挺有趣的，这个思维我还是过了很久才想到，还是做题太少，继续加油

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 2e5 + 10;
vector<int> ans[N];
set<int> s1, s2; //s1末尾为1 s2末尾为0 
int cnt;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	string s;
	cin >> s;
	int len = s.size();
	
	int flag = 1;
	REP(k, 0, len)
	{
		if(s[k] == '0')
		{
			if(s1.empty())
			{
				ans[++cnt].push_back(k + 1);
				s2.insert(cnt);
			}
			else
			{
				int t = *s1.begin();  //begin()是迭代器，看作指针 
				ans[t].push_back(k + 1);
				s1.erase(t); s2.insert(t);
			}
		}
		else
		{
			if(s2.empty()) { flag = 0; break; }
			else
			{
				int t = *s2.begin(); 
				ans[t].push_back(k + 1);
				s2.erase(t); s1.insert(t);
			}
		}
	}
	_for(i, 1, cnt)
		if(ans[i].size() % 2 == 0)
		{
			flag = 0;
			break;
		}
	
	if(!flag) puts("-1");
	else
	{
		printf("%dn", cnt);
		_for(i, 1, cnt)
		{
			printf("%d ", ans[i].size());
			for(auto x: ans[i])
				printf("%d ", x);
			puts("");
		}
	}
	
	return 0;
}

今天一口气补了四道题，都是独立做出，很爽

其实还是有实力做出来cf 1500到2000的题目的，但是考试时发挥不出来。

考试时应该静下心想题，想清楚，像平时一样，这是我要改进的

周二 3.23 （杂题 + 欧拉回路）

AtCoder - agc006_b（构造题）

说实话这道题我是一点思路都没有

感觉挺复杂，因为每三个数都要取一遍

最后看了题解

发现很巧妙，只要中间放上x - 1 x x + 1就可以了

可以推出来这样一直往上，x会一直在中间

没想到这么简单

这种构造题真的挺巧妙的，看似很复杂，却能用一种很简单的方式解决

构造题不要想太复杂，往往解法很简单。不要有心理障碍

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 2e5 + 10;
int ans[N];

int main()
{
	int n, x;
	scanf("%d%d", &n, &x);
	if(x == 1 || x == 2 * n - 1) 
	{
		puts("No");
		return 0;
	}
	
	ans[n - 1] = x - 1;
	ans[n] = x;
	ans[n + 1] = x + 1;
	
	int now = 0;
	_for(i, 1, 2 * n - 1)
	{
		if(ans[i]) continue;
		now++;
		if(now == x - 1) now = x + 2;
		ans[i] = now;
	}
	
	puts("Yes");
	_for(i, 1, 2 * n - 1) printf("%dn", ans[i]);
	
	return 0;
}

P2731 [USACO3.3]骑马修栅栏 Riding the Fences(欧拉回路模板题)

欧拉回路可以很形象地理解为一笔画问题

一笔画就是一条路径，每条边经过且仅经过一次

这样的路叫做欧拉路

如果是一条回路，就交欧拉回路

理解了这个定义，那么一些性质就很容易理解

无向图中，欧拉回路度数都为偶数，欧拉路仅有两个度数为奇数的点

有向图中，欧拉回路入度=出度，欧拉路中一个点入度多1，一个点出度多1，其他入度等于出度

那么这么求呢？

算法的思路是这样的，找到一个环，删除，继续找一个环，然后把两个环拼接成一个环，一直重复下去

看起来复杂，思路很简单，dfs的时候每走过一条边就删除掉

关键点在于在这个点的出边遍历完之后加入栈记录答案，这个过程恰好完成了两个环拼接的过程

注意这里不能边搜边记录答案，要遍历完出边，把这个点加入栈

最后倒序输出

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 500 + 10;
int g[N][N], d[N], m, mx, mi = 1e9;
stack<int> ans;

void dfs(int u)
{
	_for(v, mi, mx)
		if(g[u][v])
		{
			g[u][v]--;
			g[v][u]--;
			dfs(v);
		}
	ans.push(u);
}

int main()
{
	scanf("%d", &m);
	while(m--)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		g[u][v]++; g[v][u]++;
		d[u]++; d[v]++;
		mi = min(mi, min(u, v));
		mx = max(mx, max(u, v));
	}
	
	int st = mi;
	_for(i, mi, mx)
		if(d[i] & 1)
		{
			st = i;
			break;
		}
	
	dfs(st);
	while(!ans.empty())
	{
		printf("%dn", ans.top());
		ans.pop();
	}

	return 0;
}

周三 3.24 （欧拉回路）

先再明确一下定义

欧拉路是每条边只经过一次且经过所有顶点，即一笔画经过所有点

是否存在欧拉路或欧拉回路的判定：

有两个条件

一个是图是联通的，有向边则视为无向边（称为基图），可以用并查集维护，最后为一个联通分量

一个是度数的关系，这个是很容易推出来的

如果要求具体的路径才dfs

「一本通 3.7 例 2」单词游戏（建模 + 欧拉路判定）

这道题搞了我好久

建模真的太骚了

第一反应可以是单词为点，然后去连边，找一条路径使得每个点只经过一次

第一连边会超时，第二这种路径是哈密尔顿路，求这个路很麻烦

然后我就灵光一闪，把26个字母看作点，单词看作边

这样每条边只经过一次，这样建模不就刚好是欧拉路的定义吗

然后我又卡住了，单词看作边要怎么连呢

我开始是想末字母有一条出边，首字母有一条入边，然后看度数的关系

可是判顶的时候还要看联通，所以不能光看度数的关系

最后我看了题解，竟然是一个单词首字母向末字母连一条边

太秀了

这样子没那么直接，但是分析一波是对的，这样保留了这个单词的信息

因此根据前面说的那两个条件判定欧拉图就好了

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 1e3 + 10;
int in[30], out[30], f[30], vis[30], n, cnt;
char s[N];

int find(int x)
{
	if(f[x] == x) return x;
	return f[x] = find(f[x]);
}

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		memset(in, 0, sizeof(in));
		memset(out, 0, sizeof(out));
		memset(vis, 0, sizeof(vis));
		_for(i, 0, 25) f[i] = i;
		cnt = 0;
		
		scanf("%d", &n);
		_for(i, 1, n)
		{
			scanf("%s", s);
			int len = strlen(s);
			int u = s[0] - 'a', v = s[len - 1] - 'a';
			out[u]++; in[v]++; 
			if(!vis[u]) vis[u] = 1, cnt++;
			if(!vis[v]) vis[v] = 1, cnt++;
			if(find(u) != find(v)) cnt--;
			f[find(u)] = find(v);
		}
	
		int cnt1 = 0, cnt2 = 0, flag = 1;
		_for(i, 0, 25)
		{
			if(in[i] == out[i]) continue;
			if(in[i] - out[i] == 1) cnt1++;
			else if(out[i] - in[i] == 1) cnt2++;
			else { flag = 0; break; }
		}
		
		if(cnt != 1 || !flag || !( (!cnt1 && !cnt2) || (cnt1 == 1 && cnt2 ==1))) puts("The door cannot be opened.");
		else puts("Ordering is possible.");
	}
	
	return 0;
}

也可以度数+dfs，看能否经过所有边

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 1e3 + 10;
int in[30], out[30], n, sum;
struct node{ int v, vis; };
vector<node> g[N];
char s[N];

void dfs(int u)
{
	for(auto& x: g[u]) //如果要修改边的值的话，这里要引用 
		if(!x.vis)
		{
			x.vis = 1;
			dfs(x.v);
			sum++;
		}
}

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		memset(in, 0, sizeof(in));
		memset(out, 0, sizeof(out));
		_for(i, 0, 25) g[i].clear();
		
		scanf("%d", &n);
		_for(i, 1, n)
		{
			scanf("%s", s);
			int len = strlen(s);
			int u = s[0] - 'a', v = s[len - 1] - 'a';
			g[u].push_back(node{v, 0});
			out[u]++; in[v]++; 
		}
	
		int cnt1 = 0, cnt2 = 0, flag = 1, st = -1;
		_for(i, 0, 25)
		{
			if(in[i] == out[i]) continue;
			if(in[i] - out[i] == 1) cnt1++;
			else if(out[i] - in[i] == 1) cnt2++, st = i;
			else { flag = 0; break; }
		}
		
		if(!flag || !( (!cnt1 && !cnt2) || (cnt1 == 1 && cnt2 ==1))) 
		{
			puts("The door cannot be opened.");
			continue;
		}
		
		if(st == -1)
			_for(i, 0, 25)
				if(out[i])
				{
					st = i;
					break;
				}
		sum = 0;
		dfs(st);
		if(sum == n) puts("Ordering is possible.");
		else puts("The door cannot be opened.");
	}
	
	return 0;
}

hdu 1878 (判定欧拉图模板题)

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 1e3 + 10;
int deg[N], f[N], n, m; 

int find(int x)
{
	if(f[x] == x) return x;
	return f[x] = find(f[x]);
}

int main()
{
	while(scanf("%d", &n) && n)
	{
		memset(deg, 0, sizeof(deg));
		_for(i, 1, n) f[i] = i;
		int cnt = n;
		
		scanf("%d", &m);
		while(m--)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			deg[u]++; deg[v]++;
			if(find(u) != find(v)) cnt--;
			f[find(u)] = find(v);
		}
		
		int flag = 1;
		_for(i, 1, n)
			if(deg[i] & 1)
			{
				flag = 0;
				break;
			}
		if(flag && cnt == 1) puts("1");
		else puts("0");
	}
	
	return 0;
}

周四 3.25 （欧拉回路）

「一本通 3.7 练习 2」Ant Trip（欧拉回路 + 找规律猜结论）

一开始想暴力，就是不断跑欧拉路不断删边，看能跑多少次

然后超时了

后来想到可以通过度数来判定，不用真的去跑欧拉回路，要具体路径才跑

那么有欧拉路或者欧拉回路前提是联通，所以用并查集维护多个联通分量

然后我就任意画图看要几笔才能画完，感觉和奇点个数有关

然后我一直画不出奇点个数为奇数的图，一直是0 2 4 6

我还发现，0 和 2的时候是一次（也即欧拉路判定条件），而4个奇点要2笔，6个奇点要3笔

发现每画一笔会少两个奇点。那么就可以按照这个算个数了

交上去WA了一发，发现忽略了孤立点的情况。

孤立点要删掉，因为其根本没有边，欧拉路是经过每个边有且仅有一次。

因此统计答案时忽略孤立点就好了

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 1e5 + 10;
int deg[N], f[N], cnt[N], n, m; 

int find(int x)
{
	if(f[x] == x) return x;
	return f[x] = find(f[x]);
}

int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		memset(deg, 0, sizeof(deg));
		memset(cnt, 0, sizeof(cnt));
		_for(i, 1, n) f[i] = i;
		
		while(m--)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			deg[u]++; deg[v]++;
			f[find(u)] = find(v);
		}
		
		_for(i, 1, n)
			if(deg[i] & 1)
				cnt[find(i)]++;
		
		int ans = 0;
		_for(i, 1, n)
			if(deg[i] && find(i) == i)
			{
				if(cnt[i] <= 2) ans++;
				else ans += cnt[i] / 2;
			}
		printf("%dn", ans);
	}
	
	return 0;
}

「一本通 3.7 练习 3」John's Trip（欧拉回路模板题）

输出边的顺序就好了

注意两个点

1.dfs之前要先判断一下度数，度数正确是前提。如果度数不对，即使dfs可以得到一个路径，也是不行的

2.如果题目要求输出边的编号，那么删边的时候用一个vis数组来保存是否访问过就好。

3.注意重边和自环。删边用边的编号删去，不要用map<pair<int, int>, bool> 这个无法处理重边的情况

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 50;
const int M = 2000;
struct node{ int v, id; };
vector<node> g[N];
stack<int> ans;
int deg[N], vis[M], n, m, st, cnt;

void dfs(int u)
{
	for(node x: g[u])
	{
		int v = x.v, id = x.id;
		if(!vis[id])
		{
			vis[id] = 1;
			dfs(v);
			ans.push(id);
		}
	}
}

int main()
{
	int x, y, z;
	while(scanf("%d%d", &x, &y) && x && y)
	{
		cnt = 1;
		REP(i, 0, N) g[i].clear();
		memset(deg, 0, sizeof(deg));
		memset(vis, 0, sizeof(vis));
		st = min(x, y);
		
		scanf("%d", &z);
		g[x].push_back(node{y, z});
		g[y].push_back(node{x, z});
		deg[x]++; deg[y]++;
		
		while(scanf("%d%d", &x, &y) && x && y)
		{
			scanf("%d", &z);
			g[x].push_back(node{y, z});
			g[y].push_back(node{x, z});	
			deg[x]++; deg[y]++;
			cnt++;
		}
		
		int flag = 1;
		REP(i, 0, N) //一定先判度数 
			if(deg[i] & 1)
			{
				puts("Round trip does not exist.");
				flag = 0;
				break;
			}
		if(!flag) continue;
		
		while(!ans.empty()) ans.pop();
		dfs(st);
		if(ans.size() != cnt) puts("Round trip does not exist.");
		else
		{
			while(!ans.empty())
			{
				printf("%d", ans.top());
				if(ans.size() == 1) puts("");
				else printf(" ");
				ans.pop();
			}
		}
	}
	
	return 0;
}

周五 3.26 （欧拉回路）

「一本通 3.7 练习 4」太鼓达人（欧拉回路 + 建模）

我又一次跳坑，二进制数看作点，去连边

花了一个小时写完后发现错了。

突然意识这道题和单词接龙的非常像，可以说是一道题

同样，一个二进制数就是一条边，头向尾连，这时头是除去最后一个字符，尾是出去第一个字符

欧拉回路建模的核心在于明确什么是边，边经过且只经过一次

然后还有一些细节看代码

#include<bits/stdc++.h>
#define mp make_pair
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 1100;
map<pair<int, int>, bool> vis;
vector<int> g[N];
stack<int> ans;
int k;

int num(string s)
{
	int res = 0, len = s.size();
	REP(i, 0, len)
	{
		res <<= 1; //乘2写上面，不然最后多乘一次 
		res += s[i] - '0';
	}
	return res;
}

void dfs(int u)
{
	for(int v: g[u])
		if(!vis[mp(u, v)]) //没有重边可以用map删边. 
		{
			vis[mp(u, v)] = 1;
			dfs(v);
		}
	ans.push(u); //点在循环结束后加入 
}

int main()
{
	cin >> k;
	REP(i, 0, 1 << k)
	{
		string t = "", t1 = "", t2 = ""; //初始化，类似int x = 0 
		REP(j, 0, k)
		{
			if(i & (1 << j)) t += "1";
			else t += "0";
		}
		REP(j, 0, k - 1) t1 += t[j], t2 += t[j + 1]; //注意string用法 是 += 不是 = 
		g[num(t1)].push_back(num(t2)); //注意是有向边 
	}
	
	REP(i, 0, 1 << (k - 1)) sort(g[i].begin(), g[i].end()); //排序保证字典序 
	dfs(0);
	cout << (1 << k) << " ";
	
	while(ans.size() > 1) //最后回到起点不用输出 
	{
		int t = ans.top();
		if(t & (1 << (k - 2))) cout << "1";
		else cout << "0";
		ans.pop();
	}

	return 0;
}

周六 3.27 （欧拉回路）

「一本通 3.7 练习 6」原始生物（欧拉回路 + 建模 + 找规律）

这道题感觉就像是前面几道题的综合

首先建模很套路了，一个遗传密码就是一条边，首向尾连接

然后问题就变成了一个有向图，需要几笔画才能画完

我开始跑欧拉回路，看能跑几次。发现在不存在一笔画完的情况下跑欧拉回路是错误的

这个图存在欧拉回路再去跑才是对的

那么显然就要看每个联通分量的度数了

这里我卡了很久，没什么思路

然后我意识到，一条路径，起点出度-1，终点入度-1，中间的点的出度和入度减去相同的数

也就是除非是作为起点和终点，否则一个点的出度和入度的差值是相同的

那么比如一个点出度比入度大3，那么这个点一定要以它为起点跑3次

所以我们可以统计所有出度大于入度时的差值和（入度大于出度叶可以，一样的），就是要跑的次数

这里有个坑点就是，差值和为0的时候也要跑一次，这时是欧拉回路

知道了跑欧拉路的次数之后，就可以按照题意算出答案了，答案为次数 + 联通分量中边的个数

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 1e3 + 10;
int in[N], out[N], f[N], cnt[N], cnt1[N], n;

int find(int x)
{
	if(f[x] == x) return x;
	return f[x] = find(f[x]);	
} 

int main()
{
	_for(i, 1, 1000) f[i] = i;
	scanf("%d", &n);
	while(n--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		out[l]++; in[r]++;
		
		int x = find(l), y = find(r);
		if(x == y) cnt[x]++;
		else
		{
			f[x] = y;
			cnt[y] += cnt[x] + 1;
		}
	}
	
	_for(i, 1, 1000)
		if(out[i] > in[i]) 
			cnt1[find(i)] += out[i] - in[i];
	
	int ans = 0;
	_for(i, 1, 1000)
		if((in[i] || out[i]) && f[i] == i)
			ans += cnt[i] + max(cnt1[i], 1);
	printf("%dn", ans);

	return 0;
}

周日 3.28 （欧拉回路）

「一本通 3.7 练习 5」相框（欧拉回路）

这题太骚了，我独立做到80分，有一种情况没考虑到

首先抽象出模型，以度数为核心考虑

烧熔操作可以理解为把度数拆开，例如3拆成1 + 2

那么为了最终成一个环，要分两种情况

如果只有一个联通分量就简单，大于2的全部拆成一堆2，如果为奇数就多留下一个1

为什么要2呢，因为环上每个度数都为2

从度数满足去推为一个环，我手画了一下，发现度数对了一定有其中一种方式可以弄成环。不一定度数对了就是环，但一定有一种方式度数对了就是环

之后合并，把奇数对合并就好

如果有多个联通分量就麻烦

目标是每个联通分量弄成一条链，最后一起合并成一个大环

对于其中的一个联通分量

同样大于2的点拆，最后合并度数为1的点

这里有个特例，就是不存在奇数点的情况

我开始想的是最后再把环拆成链就行了

然后我没想到的是，当烧熔的过程中，如果度数大于2，比如4，是可以拆成2 + 1 + 1的

也就是说，如果有点度数大于2，就不用最后再把环拆为链

就是这个点让我一直80分

此外，如果有一端为0那就新创一个点，把它合并到体系当中。记得相应空间也改一改

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 1e5 + 1e3 + 10;
int deg[N], f[N], num[N], k[N], n, m;

int find(int x)
{
	if(f[x] == x) return x;
	return f[x] = find(f[x]);
}

int main()
{
	REP(i, 1, N) f[i] = i;
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		if(!u) deg[u = ++n]++; else deg[u]++;
		if(!v) deg[v = ++n]++; else deg[v]++;
		f[find(u)] = find(v);
	}
	
	int cnt = 0;
	_for(i, 1, n)
		if(deg[i] && f[i] == i) //联通分量个数 
			cnt++;
	
	int ans = 0;
	if(cnt == 1)
	{
		int t = 0;
		_for(i, 1, n)
		{
			if(deg[i] > 2) ans++;
			if(deg[i] & 1) t++; //奇数个数 
		}
		ans += t / 2;       //合并两端 
	}
	else
	{
		_for(i, 1, n)
		{
			if(deg[i] > 2) ans++, k[find(i)] = 1; 
			if(deg[i] & 1) num[find(i)]++; //奇数个数 
		}
		_for(i, 1, n)
			if(deg[i] && f[i] == i)
			{
				if(num[i] == 0) ans += !k[i]; 
				else ans += num[i] / 2 - 1; 
			}
		ans += cnt;
	}
	printf("%dn", ans);
		
	return 0;
}

现在开始如果队内没有比赛的话，自己弄一套div1 abc，英文要适应

A. Basic Diplomacy（构造）

看似复杂的这种构造题

YES与NO的区分条件往往是很简单，很极端的

这道题只要必须选的人超过m/2就不行，其他时候一定行

行的话，那就把必须选的人先选，然后剩下就选那些选的次数最少的人就行

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

const int N = 1e5 + 10;
vector<int> g[N];
int cnt[N], n, m;
	
int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		memset(cnt, 0, sizeof(cnt));
		scanf("%d%d", &n, &m);
		
		int mx = 0;
		_for(i, 1, m) 
		{
			g[i].clear();
			int k; scanf("%d", &k);
			_for(j, 1, k)
			{
				int x; scanf("%d", &x);
				g[i].push_back(x);
				if(k == 1) mx = max(mx, ++cnt[x]);
			}
		}
		
		if(mx > (m + 1) / 2) puts("NO");
		else
		{
			puts("YES");
			memset(cnt, 0, sizeof(cnt));
			_for(i, 1, m)
				if(g[i].size() == 1)
					cnt[g[i][0]]++;
			_for(i, 1, m)
			{
				if(g[i].size() == 1) printf("%d ", g[i][0]);
				else 
				{
					int ma = 1e9, t;
					for(int j: g[i]) 
						if(ma > cnt[j])
						{
							ma = cnt[j];
							t = j;
						}
					printf("%d ", t);
					cnt[t]++;
				}
		
			}
			puts("");
		}
	}
		
	return 0;
}

晚上做b做着有点疲惫了

明天把bc做了，每周一套div1 abc