牛客周赛 Round 80
前言
这场比赛是很有意思的，紧跟时事IG杯，大卞"神之举手"，0胜拿下比赛，我当时也是完整的看完三场比赛，在第二次说直接两次罚下的时候我真是直接暴起了，然后第三场当时我正在吃饭，看到又整幺蛾子直接恶心的不行，真就离谱，棋虽小道，品德最尊。因为小时候就学过围棋，这种棋盘上的博弈也正像打acm比赛时的紧张刺激一般令我神迷，而韩国棋手在棋道上还是有很长的路要走
正文
棋盖放子
#include <bits/stdc++.h>
using namespace std;
//#define int long long // 恢复 long long 宏定义
#define N 200005
void solve() {
int x,y;
cin>>x>>y;
if(y>x)
{
cout<<"quit the competition!";
}
else
cout<<x-y;
}
signed main() {
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}比大小输出即可
训练参赛
#include <bits/stdc++.h>
using namespace std;
#define int long long // 恢复 long long 宏定义
#define N 200005
void solve() {
int n;
cin >> n;
vector<int>a(2*n);
for (int &x : a)
cin >> x;
sort(a.begin(), a.end());
int ma = 0;
for (int i = 0; i < 2*n; i+=2)
ma +=a[i+1]-a[i] ;
cout << ma;
}
signed main() {
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}先排序，再进行计算即可
举手赢棋easy
#include <bits/stdc++.h>
using namespace std;
//#define int long long // 恢复 long long 宏定义
#define N 200005
void solve() {
int n;
cin >> n;
string s;
int w = 0;
cin >> s;
int ww = 0, ss = 0;
int ans = 0, st = 0;
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '1')
ww++;
else
ss++;
if (ss > ww) {
if (st == 1) {
cout << 0;
return;
}
ans=ss;
ww++, ss--;
st = 1;
}
}
if (st)
cout << ans << endl;
else
cout << n << endl;
}
signed main() {
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}这个题就开始上难度了，题意是说大卞有机会通过举手将一局由输转赢，而且还要求任何时刻都要保证赢的数大于等于输的数。
这道题需要我们有一些深度的思考
首先如果一直都是赢的大于输的，那么大卞就可以堂堂正正的获胜，这时候答案其实就是n，任何一把都可以举手
然后就是如果有一把输的会导致不再是赢大于等于输了，那么这时候就需要强制举手。但是我们需要认识到，实际上这次举手可以用在这个输的一把之前的任何一把输的场都可以。
最后就是无论如何，用了举手还是输了，也就是在第一次举手之后，后面又出现一次使输大于赢的情况。
举手赢棋hard
#include <bits/stdc++.h>
using namespace std;
#define int long long // 恢复 long long 宏定义
#define N 200005
int c(int x, int q = 2) {
return x * (x - 1) / 2;
}
void solve() {
int n;
cin >> n;
string s;
int w = 0;
cin >> s;
int ww = 0, ss = 0;
int ans1 = 0, ans2, st = 0;
for (int i = 1; i <= n; i++)
w += s[i - 1] - '0';
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '1')
ww++;
else
ss++;
if (ss > ww) {
if (st == 2) {
cout << 0;
return;
}
if (st == 0)
ans1 = ss;
if (st == 1)
ans2 = ss+1;
ww++, ss--;
st ++;
}
}
// cout<<ans1<<ans2;
int aa = 0,su=n-w;
if (st == 2) {
aa += c(ans1, 2);
aa += ans1 * (ans2 - ans1);
} else if (st == 1) {
aa += c(ans1, 2);
aa += ans1 * (su - ans1);
aa += ans1 * w;
} else {
aa = c(n, 2);
}
cout << aa;
}
signed main() {
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}这个题在理解前面easy版本的条件下就很简单了，就是可以举两次手。
1，不需要举手，那就是C(n,2)，随便选两把就好
2，需要在k把举一次手，那么第一次举手是强制在k把之前的，那么我们可以分类讨论，i,两次都在k把前举手，ii,一次在k前一次在k后，iii,还有一次在k前，第二次在所有赢的里面去举手（这里不好将前两种合并成k前*所有输的次数，因为会重叠，不如分开算）
3.需要举两次手，x举一次,y举一次，那么也是分类 i,在x之前举两次 ii，在x之前一次，在x~y举一次，答案就出来了。
公平对局
#include <bits/stdc++.h>
using namespace std;
// #define int long long // 恢复 long long 宏定义
#define N 2005
int q[N][N];
struct qq {
int a, b, x;
};
vector<qq>ans;
int f[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int n, s, num, cnt, xxx, yyy;
int st[N][N], st2[N][N];
void dfs(int x, int y) {
st[x][y] = 1;
num++;
for (int i = 0; i < 4; i++) {
int xx = x + f[i][0], yy = y + f[i][1];
if (xx < 1 || yy < 1 || xx > n || yy > n)
continue;
if (st[xx][yy] == 1)
continue;
if (q[xx][yy] == 2) {
dfs(xx, yy);
} else if (q[xx][yy] == 0) {
if (st2[xx][yy] == cnt)
continue;
st2[xx][yy] = cnt;
s++;
xxx=xx,yyy=yy;
}
}
// cout<<'*'<<x<<' '<<y<<' '<<q[x][y]<<endl;
}
struct xx {
int x, y, v;
};
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
char c;
cin >> c;
if (c == '.')
q[i][j] = 0;
else if (c == '#')
q[i][j] = 1;
else
q[i][j] = 2;
}
}
int ma = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (q[i][j] == 2 && st[i][j] == 0) {
s = 0;
num = 0;
cnt++;
dfs(i, j);
// cout<<i<<j<<' '<<num<<' '<<s<<endl;
if (s == 1) {
ans.push_back({xxx, yyy, num});
}
}
}
}
map<pair<int, int>, int>mp;
for (auto[x, y, z] : ans) {
mp[ {x, y}] += z;
ma = max(mp[ {x, y}], ma);
}
cout << ma;
}
signed main() {
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}这道题我可能写的麻烦了一点，最开始想dfs后来莫名其妙总是错，后来就改成并查集进行操作了。首先通过dfs吧所有连成一块的白子作为一个联通块，然后把那些只剩一口气的联通块进行记录（这里有可能是对于两个白子剩的一口气都在同一个位置，那也算一口气而非两口气），并且把他最后一口气的坐标进行记录，就会有几个可以下黑子的地方，然后注意可能一个黑子会把两个块都吃掉，所以我们需要进行一个记录的操作。这个题虽然操作有点难受，但是思路不难理解。
训练参赛（二）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 998244353
#define int long long
const int N = 1e6 + 5;
void solve(int q) {
int n, k;
cin >> n >> k;
vector<int>a(n + 1), mp(2 * n + 1);
if (k < n || k > n * n) {
cout << "-1" << "\n";
return;
}
if ((k + n + 2 * n * n) % 2) {
cout << "-1" << "\n";
return;
}
int tmp = 2*n-1;
for (int i = 1; i <= n; i++) {
while (k - tmp < (n - i))
tmp -= 2;
a[i] = tmp;
k -= tmp;
if (tmp > 2)
tmp -= 2;
}
int p = 2 * n;
for (int i = 1; i <= n; i++) {
while (mp[p])
p--;
mp[p] = 1, mp[p - a[i]] = 1;
cout << p << ' ' << p - a[i] << "\n";
}
}
signed main() {
int T;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
T = 1;
cin >> T;
for (int i = 1; i <= T; i++) {
solve(i);
}
return 0;
}这个可以说是最难的一波了，因为思维量挺大的，我们先进行一个举例，n=3时
不难看出，前者为最大值，后者为最小值，所以k能触及的范围就在n~n^2，并且对于前者这个底下的数字的变动不会影响答案，而后者则会
我们可以通过拆除12，56组成新的组合，并且使不和谐度增加，而且我们可以发现我们这次拆除增加了8，去掉了2，所以净增加6，而如果换成 12 34进行操作，那么净增加为2，相当于每个增加1或者3，然后列更多的我们可以发现，我们可以通过这个操作进行增加的净增加都是奇数，而且是1 3 5 7等规律递增的相邻的奇数，这就很有意思了，我们可以想到可不可以用类似二进制表示的方法，对这个k进行拆分成多个奇数表示的形状，然后就可以进行排列了，然后我们就可以把k进行拆分成很多个单独的数，然后我们只要进行一个从大到小按顺序的配对，以得到这些差值即可。
不公平对局
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define int long long
#define endl '\n'
const int N = 1e3 + 5;
int P1, P2, P3, P4, dp[N][N], aa;
int ksm(int x, int n, int m) {
int ans = 1;
while (n) {
if (n & 1)
ans = ans * x % m;
x = x * x % m;
n >>= 1;
}
return ans;
}
int dfs(int x, int y) {
if (x == aa)
return dp[x][y] = 0;
else if (y == aa)
return dp[x][y] = 1;
if (dp[x][y] != -1)
return dp[x][y];
return dp[x][y] = (P1 * dfs(x + 1, y + 1)%mod + P2 * dfs(x + 1, y)%mod + P3 * dfs(x, y + 1)%mod) % mod * P4 % mod;
}
void solve() {
int x, a, b, p1, p2;
cin >> aa;
cin >> a >> b;
p1 = a * ksm(b, mod - 2, mod) % mod;
cin >> a >> b;
p2 = a * ksm(b, mod - 2, mod) % mod;
P1 = (p1 * p2 % mod);
P2 = p1 * (1 - p2 + mod) % mod;
P3 = (1 - p1 + mod)* p2 %mod;
P4 = (1 - p1 + mod) % mod * (1 - p2 + mod) % mod;
P4 = ksm(1 - P4 + mod, mod - 2, mod);
for (int i = 0; i <= aa; i++) {
for (int j = 0; j <= aa; j++)
dp[i][j] = -1;
}
cout << dfs(0, 0) << endl;
}
signed main() {
int T;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}这是一个数学问题，我确实是受益匪浅，但直接嘴上讲讲不动了，建议看一下视频题解
【视频题解】牛客周赛80题目讲解
讲的真好，我有机会还要把他说的题也刷一下，学习一下这种题型（补题预告）
后记
这次比赛还是很有意思的，最起码指向性非常针对，而且大快人心，题型也很有意思。然后就是等着我去补最后一个题的类题就好了