| # | Name | ||
|---|---|---|---|
| A | Computer Game 2 s, 256 MB |   |
 |
| B | Groups 4 s, 256 MB | |
|
| C | Delete Two Elements 2 s, 256 MB | |
|
| D | Training Session 2 s, 256 MB | |
|
| E | Staircases 2 s, 256 MB | |
|
| F | RBS3 s, 512 MB | |
|
| G | The Sum of Good Numbers 2 s, 256 MB | |
|
C. Delete Two Elements（思维）
题意
给你 $n$ 个数，让你删去两个数，使得删去前后平均值不变，问你最多有多少种选择方式（值相同的不同数字算不同的方案）。
思路
显而易见，设平均数为 $k$，选取的两个数 $x$ $y$ 满足 $x + y = 2k$ 时，删去前后平均值不变，先计算出平均数，然后用map统计一下每个数出现的次数，然后遍历所有数值，方案数就是当前这个数字 $x$ 出现的次数乘上 $k-x$ 出现的次数。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 2e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
LL a[maxn];
map<long long,LL> mp;
void solve() {
int n;
cin >> n;
mp.clear();
LL sum = 0;
for (int i = 0; i < n; i++) scanf("%lld", a + i), mp[a[i]]++, sum+=a[i];
if(sum*2ll % n != 0) puts("0");
else {
LL key = sum * 2ll / n;
LL m = key / 2ll;
LL ans = 0ll;
for(auto num : mp) {
if(num.first > m) break;
if(num.first == m && key - m == m) {
ans += num.second * (num.second - 1) / 2;
break;
}
if(mp.find(key - num.first) != mp.end())
ans += num.second * mp[key - num.first];
}
printf("%lld\n",ans);
}
}
int main(int argc, char const *argv[]) {
int t = 1;
cin >> t;
while(t--) {
solve();
}
return 0;
}
D. Training Session（思维）
题意
有 $n$ 个问题，告诉你每个问题的难度和类型，保证没有难度和类型都相同的两个问题，让你找出3个问题，使得满足一下两个条件之一：
- 三个问题的类型都不同。
- 三个问题的难度都不同。
问你一共有几种选择方案。
思路
直接计算有点困难，我们可以用容斥的思想转换问题。不考虑限制条件，我们可以得到，一共有 $\frac{n(n-1)(n-2)}{6}$ 种选择方案，考虑将不符合要求的删去，剩下的就是符合条件的。即三个问题中有至少两个问题的类型且难度相同的就是非法方案。假设 $x_i$ 表示难度，$y_i$表示类型，则非法情况可以这样表示：$(x_1,y_1),(x_1,y_2)(x_2,y_1)$，即可以选择一个问题当做基准，让第二个问题的难度和第一个问题相同， 让第三个问题的类型和第一个问题相同，其他任意。于是，我们可以将每一个问题当做基准，然后看有多少个问题和基准相同（除去自己），记作$cnt_1$， 看有多少问题的类型和基准相同（除去自己），记作$cnt_2$ ，则$cnt_1*cnt_2$ 就是以该问题为基准的所有非法方案了，由于题目保证没有两个问题的难度和类型都相同，所以不会重复计算。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
LL a[maxn], b[maxn];
PII p[maxn];
void solve() {
LL n, m;
cin >> n;
LL ans = n * (n - 1) * (n - 2) / 6;
for (int i = 1; i <= n; i++) a[i] = b[i] = 0;
for (int i = 1; i <= n; i++) {
scanf("%d %d", &p[i].first, &p[i].second);
a[p[i].first]++;
b[p[i].second]++;
}
for (int i = 1; i <= n; i++) {
ans -= (a[p[i].first] - 1) * (b[p[i].second] - 1);
}
printf("%lld\n", ans);
}
int main(int argc, char const *argv[]) {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
E. Staircases(DP+思维)
题意
给你一个 $n*m$ 的格子图，每个格子有两个状态墙或者空地，初始都为空地，有 $q$ 次操作，每次翻转一个格子的状态，问你操作完后，整张图有多少个梯子图形，梯子图形如下：
即先右再下，或者先下再右，特殊规定一个格子也算梯子图形。
分析
首先先算出初始有多少个梯子图形，可以用DP，令dp[i][j][0/1] 表示，结尾为 (i,j) 且结尾为横着（用1表示），或者为竖着（用0表示） 的方案数，可以得到转移：
dp[i][j][0] = dp[i][j - 1][1] + 1;
dp[i][j][1] = dp[i - 1][j][0] + 1;
跑一个$O(nm)$ 即可计算出初始方案数。
然后计算由于某个格子改变状态影响的梯子图形个数，即有多少个梯子图形经过这个格子。我们可以从这个点分别向上和向下走到边界（撞墙或者超出格子图），记录长度为 $len_1$ 和 $len_2$ ，则影响的梯子图形数量为 $len_1*len_2-1$，每次判断是增加还是减少，维护答案即可。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
int dp[1111][1111][2];
int mx[2] = {0, 1};
int my[2] = {1, 0};
struct node {
int x, y, step, dir, type;
};
int n, m, q;
int mp[1111][1111];
int bfs(int x, int y, int type, int dir) {
int step = 1;
while (1) {
if (type)
y += dir;
else
x += dir;
if (x >= 1 && x <= n && y >= 1 && y <= m && !mp[x][y])
step++, type ^= 1;
else
return step;
}
}
void solve() {
cin >> n >> m >> q;
LL ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j][0] = dp[i][j - 1][1] + 1;
dp[i][j][1] = dp[i - 1][j][0] + 1;
ans += dp[i][j][0] + dp[i][j][1] - 1;
}
}
while (q--) {
int x, y;
scanf("%d %d", &x, &y);
int cnt1 = bfs(x, y, 1, 1), cnt2 = bfs(x, y, 0, -1);
int cnt3 = bfs(x, y, 0, 1), cnt4 = bfs(x, y, 1, -1);
// printf("%d %d %d %d \n", cnt1, cnt2, cnt3, cnt4);
mp[x][y] ^= 1;
int now = cnt1 * cnt2 + cnt3 * cnt4 - 1;
if (mp[x][y])
ans -= now;
else
ans += now;
printf("%lld\n", ans);
}
}
int main(int argc, char const *argv[]) {
int t = 1;
while (t--) {
solve();
}
return 0;
}
