Codeforces Round 895 (Div. 3)

╰+攻爆jí腚メ 2024-03-04 01:04 53阅读 0赞

[https://codeforces.com/contest/1872][https_codeforces.com_contest_1872]

### B. The Corridor or There and Back Again ###

如果还有s秒出发开关，那么就会最多走(s - 1) / 2个房间，在所有可以到的房间个数中选择最小的那个则为最大。首先我们可以发现，陷阱之间是独立的，只有我们到达陷阱之后，陷阱才会启动，而且每个陷阱的触发时间决定了我们应该什么时候回到这个位置，所以我们可以算出来每个陷阱最远可以到达哪里，然后再选择最近的那个点，因为不能跑更远。

#include<bits/stdc++.h>
    using namespace std;
    int t, n, d, s, ans;
    int main()
    {
    	cin >> t;
    	while(t --)
    	{
    		ans = 2e5 + 10; 
    		cin >> n;
    		for(int i = 1; i <= n; i ++)
    		{
    			cin >> d >> s;
    			ans = min(ans, d + (s - 1) / 2);
    		}
    		cout << ans << '\n';
    	}
    	return 0;
    }

### C. Non-coprime Split ###

可以分为奇数和偶数两种情况讨论，应为如果是偶数就一定可以被2整数，如果是奇数就观察是否是素数，如果不是素数则可以使用辗转相减法求**gcd(a,b)=gcd(b,a−b)**

eg.gcd(12, 3) = gcd(3, 12 - 3)

#include<bits/stdc++.h>
    using namespace std;
    int t;
    void solve()
    {
    	int l, r;
    	cin >> l >> r;
    	for(int i = r; i >= l; i --)
    	{
    		if(i % 2 == 0 && i > 2)
    		{
    			cout << i - 2 << ' ' << 2 << '\n';
    			return;
    		}
    		else if(i % 2 != 0 && i > 3)
    		{
    			for(int j = 3; j <= i / j; j ++)
    			{
    				if(i % j == 0)
    				{
    					cout << j << ' ' << i - j << '\n';
    					return;
    				}
    			}
    		}
    	}
    	cout << -1 << '\n';
    	return;
    }
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	cin >> t;
    	while(t --)
    	{
    		solve();
    	}
    	return 0;
    }

### D. Plus Minus Permutation ###

要求得最大值需要减数最大，被减数最小，对于下方结论3而言，同是x, y的倍数会使两个数相抵消，加之后会被减去。

利用等差数列公式算出每部分的和再相减即可![fb12460a4d094eb680782cc2de45ffcc.png][]

#include<bits/stdc++.h>
    using namespace std;
    long long gcd(long long a, long long b)
    {
    	return b == 0 ? a : gcd(b, a % b);
    }
    long long lcm(long long a, long long b)
    {
    	return a * b / gcd(a, b);
    }
    long long f(long long a, long long b, long long cnt)
    {
    	return (a + b) * cnt / 2;
    }
    void solve()
    {
    	long long n, x, y;
    	cin >> n >> x >> y;
    	long long cnt1 = n / x;
    	long long cnt2 = n / y;
    	long long cnt3 = n / lcm(x, y);
    	cnt1 -= cnt3;
    	cnt2 -= cnt3;
    	cout << f(n,n - cnt1 + 1, cnt1) - f(1, cnt2, cnt2) << '\n';
    }
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	long long t;
    	cin >> t;
    	while(t --)
    	{
    		solve();
    	}
    	return 0;
    }

### E. Data Structures Fan ###

使用异或和进行优化

![b3addfbfdd82467497eae8825f9f685d.png][]

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	int t;
    	cin >> t;
    	while(t --)
    	{
    		int n, q, a[100000], su[100000];
    		char s[100000];
    		cin >> n;
    		for(int i = 1; i <= n; i ++)cin >> a[i]; 
    		cin >> s + 1;
    		for(int i = 1; i <= n; i ++)
    		{
    			su[i] = su[i - 1] ^ a[i];
    		}
    		int sum1 = 0, sum0 = 0;
    		for(int i = 1; i <= n; i ++)
    		{
    			if(s[i] == '1')sum1 ^= a[i];
    			if(s[i] == '0')sum0 ^= a[i];
    		}
    		cin >> q;
    		while(q --)
    		{
    			int tp;
    			cin >> tp;
    			if(tp == 1)
    			{
    				int l, r;
    				cin >> l >> r;
    				sum1 ^= (su[r] ^ su[l - 1]);
    				sum0 ^= (su[r] ^ su[l - 1]);
    			}
    			else if(tp == 2)
    			{
    				int x;
    				cin >> x;
    				if(x == 0)cout << sum0 << ' ';
    				else cout << sum1 << ' ';
    			}
    		}
    		cout << '\n';
    	}
    	return 0;
    }

### F. Selling a Menagerie ###

（拓扑排序）

注：F单独发布题解

[https_codeforces.com_contest_1872]: https://codeforces.com/contest/1872
[fb12460a4d094eb680782cc2de45ffcc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/da8d770d96d94adfaef91969012d0e86.png
[b3addfbfdd82467497eae8825f9f685d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/a90080c9acc843f799d6afb620589352.png