2023 ICPC Jinan
ICPC Jinan
G
考虑找矛盾。首先对于同一行，翻转和不翻是一个矛盾，对于相异的行，若一行的翻转或不反转会使同一列产生多余的 1，则又是一个矛盾。将每一行拆成两个点，一个点代表不翻转该行，一个点代表翻转该行，然后将所有的矛盾作为边连起来，会得到一个图，对于图中的连通块，若是二分图，则这个连通会对答案产生乘 2 的贡献，否则，乘 0。
在建图之前，先要初步判断一下合法性，否则会因为建的边太多而导致 TLE。
std::string g[N + 5];
std::vector<int> adj[N + 5 << 1], col[N + 5];
int cnt[N + 5];
int color[N + 5 << 1];void init(int n, int m) {for (int i = 0; i < n + n; ++i) {adj[i].clear();color[i] = 0;}for (int i = 0; i <= m; ++i) {col[i].clear();cnt[i] = 0;}
}bool dfs(int cur, int c) {if (color[cur] != 0) {return color[cur] == c;}color[cur] = c;for (auto &to : adj[cur]) {if (!dfs(to, 3 - c)) {return false;}}return true;
}void solve() {int n = 0, m = 0;std::cin >> n >> m;init(n, m);for (int i = 0; i < n; ++i) {std::cin >> g[i];for (int j = 0; j < m; ++j) {cnt[j] += (g[i][j] - '0') + (g[i][m - 1 - j] - '0');}}i64 ans = 1ll;int mid = (m + 1) >> 1;for (int i = 0; i < mid; ++i) {if (cnt[i] > 2) {ans = 0ll;break;}}for (int i = 0; i < n && ans != 0; ++i) {// 建边adj[i].push_back(i + n);adj[i + n].push_back(i);for (int j = 0; j < m; ++j) {// 不翻转if (g[i][j] == '1') {for (auto &t : col[j]) {adj[i].push_back(t);adj[t].push_back(i);}}// 翻转int k = m - 1 - j;if (g[i][k] == '1') {for (auto &t : col[j]) {adj[i + n].push_back(t);adj[t].push_back(i + n);}}}// 统计for (int j = 0; j < m; ++j) {if (g[i][j] == '1') {col[j].push_back(i);}if (g[i][m - 1 - j] == '1') {col[j].push_back(i + n);}}}for (int i = 0; i < n && ans != 0; ++i) {if (color[i] != 0) {continue;}if (dfs(i, 1)) {ans <<= 1;if (ans >= Mod) {ans -= Mod;}}else {ans = 0;}}std::cout << ans << '\n';
}
K
一个关键的 trick 是，我们令 \(a_i \leftarrow a_i - i\)，这样做的能够使一段公差为 1 的 等差序列变成相等的数，于是问题就变成了可以在规定的操作次数内，能操作出的最长的段使得段内所有的数都相等。双指针 加上 堆顶堆动态维护中位数 容易解出。
M
首先求凸包，标记凸包上的点，然后枚举每个不在凸包上的点，以该点为中心对所有点进行极角排序，排完序后相邻的且同时时凸包上的点会对答案产生一的贡献。