AtCoder Regular Contest 176（ARC176）A、B

题目：AtCoder Regular Contest 176 - tasks
官方题解：AtCoder Regular Contest 176 - editorial
参考：atcoder regular 176 (ARC176) A、B题解

A - 01 Matrix Again

题意

给一个n×n的方格，给出m个坐标(x,y)×m，在方格中选择一些格子填入1，要求填完后每行有m个1，每列有m个1，并且之前给出的坐标对应方格中也是1，输出一种可能的方案。

思路（依照官方题解）

容易得出一共要选n×m个格子。
当m=1时：
需要选n个格子，每行每列都要一个1，其中有一个格子坐标给定为(x₀, y₀)。如何保证每行每列一个呢？可以让行坐标x+列坐标y（模n）固定，x遍历0~(n - 1)时，y也遍历0~(n - 1)。那x+y的和怎么选呢？显然只能是x₀ + y₀。
于是可以令k = (x₀ + y₀) % n，x遍历0~(n - 1)，y = (k - x + n) % n。
当m!=1时：
既然固定一个x + y = k能选出n个格子，并且保证每行每列一个，那么能不能选出m个不同的k，达到每行每列m个呢？答案是可以的，当k互不相同时，每个k选出的n个点和其他k选出的不会有交集。
现在就只剩怎么选出m个不同的k，使得给定的那些点在我们会选出的点集里了。
如果给定的点里有(x_i, y_i)，显然k = (x_i + y_i) % n是一定要选的。但是一个k也可能对应多个给定的点，所以只要对所有给定点(x_i, y_i)，选上k = (x_i + y_i) % n（就选一次不能重复），剩下的没选过的数中随便挑几个凑够m个即可。

代码

#include <vector>
#include <iostream>
#include <cstdio>
#include <ctime> 
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 1e5 + 5;

int vis[N];
vector<int> setk; 

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		vis[(x + y - 2) % n] = 1;
	}
	for (int i = 0; i < n; i++)
		if (vis[i]) setk.push_back(i);
	for (int i = 0; i < n; i++)
		if (!vis[i] && setk.size() < m) setk.push_back(i);
	cout << n * m << endl; 
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int x = j + 1, y = (setk[i] - j + n) % n + 1;
			cout << x << ' ' << y << endl;
		}
	}  
	return 0;
}

B - Simple Math 4

思路（官方题解）

n >= m时：
（注意一定是n >= m，这样2^n-m才是整数）
这样把n变小
n < m时：
当2ⁿ = 2^m - 2^k时（也就是n = k = m - 1)，答案为0
否则有2ⁿ < 2^m - 2^k，答案就是2ⁿ % 10

代码

容易发现2ⁿ最后一位是2、4、8、6循环的，得到n之后可以直接按周期算出个位数

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
const int N = 2e5 + 5;

int re[4] = {2, 4, 8, 6};

int main()
{
	int T; 
	cin >> T;
	while (T--)
	{
		ll m, n, k;
		cin >> n >> m >> k;
		if (n >= m) n = n - (n - m) / (m - k) * (m - k);
		if (n >= m) n -= m - k;
		if (n == m - 1 && k == m - 1) cout << 0 << endl;
		else cout << re[(n - 1) % 4] << endl;
	}
	return 0;
}