洛谷100题DAY7

ゝ一世哀愁。 2024-02-24 08:13 9阅读 0赞

### 31.P1636 Einstein学画画 ###

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

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

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

eg.

![e0d19928d73a46e1acebd41c6d480f98.jpeg][]

![c275d42878fa4599858638fa35a39bb2.jpeg][]

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

#include<bits/stdc++.h>
    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

![cdc9022eeccd4dc788655cfddf55acb1.jpeg][]

#include<bits/stdc++.h>
    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<bits/stdc++.h>
    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的数的下标先预处理出来

![a9ec923964b04f11a7601ef4fd040731.jpeg][]

#include<bits/stdc++.h>
    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<bits/stdc++.h>
    using namespace std;
    const int N = 2e3 + 10;
    vector<pair<int, 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;
    }

[e0d19928d73a46e1acebd41c6d480f98.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/8caa845beee3470b932d73bafbd9430b.png
[c275d42878fa4599858638fa35a39bb2.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/ece46c436341446fbfd69180a28e12b2.png
[cdc9022eeccd4dc788655cfddf55acb1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/24d7b2a7fa4247edb9af4fd1dc149c5f.png
[a9ec923964b04f11a7601ef4fd040731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/50e0882e1871494f90df542611deb105.png