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

思路（官方题解）

1. n >= m时：
   （注意一定是n >= m，这样2^n-m才是整数）
   这样把n变小
2. 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;
}