洛谷100题DAY7

31.P1636 Einstein学画画

此题为欧拉通路，必须要满足奇点的个数为0或2个

奇点：度数（入度出度）为奇数的点

如果奇点为2个或者0个就可以直接一笔化成

eg.

 

 我们发现奇数点个数每增加2个就多一笔

#include
using namespace std;
const int N = 2e5 + 10;
int n, m, a, b, du[N], ans;
int main()
{ 
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		cin >> a >> b;
		du[a] ++, du[b] ++;
	}
	for(int i = 1; i <= n; i ++)
	{
		if(du[i] & 1)ans ++;
	}
	cout << max(1, ans / 2);//最少也得画一笔 
	return 0;
}

32. P1652 圆

我们枚举每一个圆，判断这个圆包含1和2哪个点，如果如果都包含说明这个线不会穿过这个圆，否则就将这个圆的穿线个数+1

#include
using namespace std;
const int N = 2e5 + 10;
int n, x[N], y[N], r[N], xx1, yy1, xx2, yy2, ans;
int dist(int xx, int yy, int xxx, int yyy)
{
	return (xxx - xx) * (xxx - xx) + (yyy - yy) * (yyy - yy);
}
int main()
{
	
	cin >> n;
	for(int i = 1; i <= n; i ++)cin >> x[i];
	for(int i = 1; i <= n; i ++)cin >> y[i];
	for(int i = 1; i <= n; i ++)cin >> r[i];
	cin >> xx1 >> yy1 >> xx2 >> yy2;
	for(int i = 1; i <= n; i ++)
	{
		bool d1 = dist(xx1, yy1, x[i], y[i]) <= r[i] * r[i];
		bool d2 = dist(xx2, yy2, x[i], y[i]) <= r[i] * r[i];
		if(d1 ^ d2)ans ++;
	}
	cout << ans;
	return 0;
}

33.P1657 选书

对书进行dfs，看是选a还是选b

#include
using namespace std;
const int N = 2e5 + 10;
int x, ans, a[N], b[N];
bool v[N];
void dfs(int dep)
{
	if(dep == x + 1)
	{
		ans ++;
		return;
	}
	if(!v[a[dep]])
	{
		v[a[dep]] = 1;
		dfs(dep + 1);
		v[a[dep]] = 0;
	}
	if(!v[b[dep]])
	{
		v[b[dep]] = 1;
		dfs(dep + 1);
		v[b[dep]] = 0;
	}
}
int main()
{
	cin >> x;
	for(int i = 1; i <= x; i ++)
	{
		cin >> a[i] >> b[i];
	}
	dfs(1);
	cout << ans << '\n';
	return 0;
}

34.P1795 无穷的序列

找规律，将为1的数的下标先预处理出来

#include
using namespace std;
vector<int> v;
int n, x;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	for(int i = 1, j = 0; i <= 1e9; i += j ++)v.push_back(i);
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> x;
		auto it = lower_bound(v.begin(), v.end(), x);
		bool flag = (it != v.end() && *it == x);
		if(flag)cout << 1 << '\n';
		else cout << 0 << '\n';
	}
	return 0;
}

 35.P1757 通天之分组背包

我们可以将分出的组别用v[N]来记录，将同一组存入同一个v[N]中去，从而转化为背包问题

dp[i][j]表示到i组为止，总重量为j的最大价值

#include
using namespace std;
const int N = 2e3 + 10;
vectorint, int>> v[N];
int n, m, a, b, c, dp[N][N];
int main()
{
	cin >> m >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> a >> b >> c;
		v[c].push_back({a, b});
	}
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 0; j <= m; j ++)
		{
			dp[i][j] = dp[i - 1][j];
			for(auto k : v[i])
			if(j >= k.first)dp[i][j] = max(dp[i][j], dp[i - 1][j - k.first] + k.second);
		}
	}
	cout << dp[n][m];
	return 0;
}