# | Name | ||
|---|---|---|---|
A | Computer Game 2 s, 256 MB | x8894 | |
B | Groups 4 s, 256 MB | x5935 | |
C | Delete Two Elements 2 s, 256 MB | x4419 | |
D | Training Session 2 s, 256 MB | x1583 | |
E | Staircases 2 s, 256 MB | x442 | |
F | RBS3 s, 512 MB | x159 | |
G | The Sum of Good Numbers 2 s, 256 MB | x2 |
C. Delete Two Elements（思维）
题意
给你 n 个数，让你删去两个数，使得删去前后平均值不变，问你最多有多少种选择方式（值相同的不同数字算不同的方案）。
思路
显而易见，设平均数为 k，选取的两个数 x y 满足 x y=2k 时，删去前后平均值不变，先计算出平均数，然后用map统计一下每个数出现的次数，然后遍历所有数值，方案数就是当前这个数字 x 出现的次数乘上 k−x 出现的次数。
代码
代码语言：javascript复制#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("%lldn",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 就是以该问题为基准的所有非法方案了，由于题目保证没有两个问题的难度和类型都相同，所以不会重复计算。 代码
代码语言：javascript复制#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("%lldn", 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，每次判断是增加还是减少，维护答案即可。 代码
代码语言：javascript复制#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("%lldn", ans);
}
}
int main(int argc, char const *argv[]) {
int t = 1;
while (t--) {
solve();
}
return 0;
}
