2021牛客暑假多校联赛第一场
声明：题意就不细说了，我这功底说的也语句不通，尽量写好题解，大家由疑问可以私信我，我会及时回复的，此篇题解是作者在看了网上众多题解之后，自己的一些感受。
A. Alice and Bob
说实话，这题比赛的时候是真的不会，和队友讨论了一下，感觉就情况很多，然后很复杂
思路
题目中给出了一些必败态，那么由此可知，每一个必败态（x,y)，那么由此推出的（x + k, y + s * k), (x + s * k, y + k)就一定是必胜态。
由此我们使用dp[x][y[来表示状态, dp[x][y] = 1, 先手胜，dp[x][y] = 0, 后手胜
那么我们对于每一个后手胜的状态，枚举k，然后枚举s，那么看起来我们同时需要枚举x, y, k, s，那么就是一个O(n ^ 3logn)的方法(s的和是一个调和级数）
那么事实上有一个推论（这谁想得到啊），必败状态不会很多，对于一个x, 只会有一个y与之对应为一个必败态，因为(x, yy（yy > y))可以通过变化得到（x,y), 那么总的时间复杂度就是O(n ^ 2logn)。
上代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 1;
int t, n, m;
bitset<N> dp[N];
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
for (int i = 0; i < N; i ++ ) {
for (int j = 0; j < N; j ++ ) {
if (!dp[i][j]) {
for (int k = 1; i + k < N; k ++ ) {
for (int s = 0; j + s * k < N; s ++ ) {
dp[i + k][j + s * k] = 1;
}
}
for (int k = 1; j + k < N; k ++ ) {
for (int s = 0; i + s * k < N; s ++ ) {
dp[i + s * k][j + k] = 1;
}
}
}
}
}
cin >> t;
while (t -- ) {
cin >> n >> m;
if (dp[n][m]) {
puts("Alice"); }
else {
puts("Bob"); }
}
return 0;
}
B. Ball Dropping
签到题，队友过的，我太菜了
D. Determine the Photo Position
签到题， 队友过的，我菜死了
E. Escape along Water Pipe
就是个BFS大模拟，我还没写，同类型的大家可以做一下推箱子和华容道
F. Find 3-friendly Integers
这题其实我乍一看是个数位dp，但是大家都过得飞快，于是我推了好久的规律，没找到，心想大家的数位dp都写得那么6嘛，不由得暗自惭愧，于是我打了个表，大于100的数，用这个数减去24就是答案，小于100的数没啥规律那就暴力，于是我脑残在牛客的在线编辑器里写起代码来了，深感代码功底不行，然后就过了。
正解：小于100的数没啥规律，那就暴力，对于一个三位及以上的数，假设是三位数，那么如果每一位上的数加起来的和为3的倍数，那么就肯定是满足要求的，那么不是上一种情况的3位数，我们对其每一位求一个前缀和，那么由抽屉原理，必然存在两个相等的数（在模3的情况下），那么这两个数相同的数之间肯定是加了一个数且这个数是3的倍数啊，那么4位数同样可以由抽屉原理得知满足条件，那么就很显然了。
上才艺
//比赛时写的代码
#include <bits/stdc++.h>
using namespace std;
int a[110] = {
0,0,0,1,1,1,2,2,2,3,4,4,5,6,6,7,8,8,9,10,11,12,12,13,14,14,15,16,16,17,18,19,20,21,22,23,24,25,26,27,28,28,29,30,30,31,32,32,33,34,35,36,36,37,38,38,39,40,40,41,42,43,44,45,46,47,48,49,50,51,52,52,53,54,54,55,56,56,57,58,59,60,60,61,62,62,63,64,64,65,66,67,68,69,70,71,72,73,74,75,76,76};
int main(void) {
int t;
long long l, r;
long long cnt1, cnt2;
scanf("%d", &t);
while (t -- ) {
scanf("%lld%lld", &l, &r);
l--;
if (l <= 100) cnt1 = a[l];
else cnt1 = l - 24;
if (r <= 100) cnt2 = a[r];
else {
cnt2 = r - 24;
}
cout << cnt2 - cnt1 << '\n';
}
return 0;
}
G. Game of Swapping Numbers
思路
这道题的难点在于恰好交换k次，同时要是的结果最大。对于每一对ai, bi来说，我们可以根据其相对大小在其前面分别加上”+"和“-”，那么我们假如没有交换k次这个条件，我们可以交换任意次，那么答案就是用最大的n个数减去剩余的n个数。
通过画图。
我们可以很容易的发现，当(ai, bi)与（aj,bj)没有交集的时候，我们交换他们，那么我们就可以是答案变优，在有交集的情况下如果ai - bi与aj - bj的符号相同的话，答案不变，否则答案减小，《答案变优的时候，增加 2 ∗ m i n ( a i , b i j ) − 2 ∗ m a x ( a j , b j ) 2 * min(ai, bij ) - 2 * max(aj, bj) 2∗min(ai,bij)−2∗max(aj,bj), 观察这个柿子，我们可以发现，当 m i n ( a i , b i ) < m a x ( a j , b j ) min(ai, bi) <max(aj, bj) min(ai,bi)<max(aj,bj)的时候我们就可以不交换他们。一开始，我们必然是选择没有交集的区间进行交换，那么我们交换完之后不够k次怎么办，此时由抽屉原题，当(n >= 3)的时候，必然存在两对及以上的ai - bi > 0 或者ai - bi < 0, 那么我们不断地交换他们，答案就一i定不会变差。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) ((int)x.size())
#define rep(i, a, n) for (int i = a; i <= n; i ++ )
#define per(i, a, n) for (int i = n; i >= a; i -- )
int n, k;
signed main(void) {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
vector<int> a(n), b(n);
int ans = 0;
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) cin >> b[i];
rep(i, 0, n - 1) {
if (a[i] > b[i]) {
swap(a[i], b[i]);
}
ans += b[i] - a[i];
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int cnt = 0;
while (cnt < k && cnt < n && a[n - cnt - 1] > b[cnt]) {
ans += 2 * (a[n - cnt - 1] - b[cnt]);
cnt ++;
}
cout << ans << '\n';
return 0;
}
H. Hash Function
因为所有数均不同，那么假设 a i < a j ai < aj ai<aj, 那么 a j = a i + ∣ a j − a i ∣ aj = ai + | aj - ai| aj=ai+∣aj−ai∣
要满足ai % seed != aj % seed, 则只需要满足|aj - ai| % seed != 0, 那么我们只需要处理出来所有的|aj - ai|, 然后seed不是其因子即可， 那么我们需要做的是快速的求出所有的|aj - ai|, 暴力是肯定不行的，因此我们需要使用FFT来加速这个过程（暂时不是很懂原理，就先当成板子使用吧）， 然后我们就可以求出这些数的因子，因为ai <= 1e5， 那么|ai - aj|也必然只有1e5量级的一个取值，然后那个没有出现过的最小的数，就是seed
先放个思路，代码慢慢更…咕咕咕
I. Increasing Subsequence
期望dp，别问怎么想到的，不会，就是中间过程很像dp罢了
我们用dp[x][y]来表示当前回合选择了x， 上一回合选择y的距离结束的步数期望
那么我们假设下一回合选择k，一共以有cnt个选择，那么dp[x][y] = 1 + 1 / / / cnt ∗ * ∗ ∑ \sum ∑dp[k][x], 我们发现并不是很好写代码，因为x一会在第一维，一会儿在第二维，那么我们试着更改一下dp数组的定义，那么我们将dp[x][y]定义为前两步选择了x, y距离结束的步数期望。
那么如果Px > > > Py，dp[x][y] = 1+ 1 / / / cnt * ∑ \sum ∑dp[x][k](Pk > Px, k > y)
如果Px < < < Py, dp[x][y] = 1 + 1 / / / cnt * ∑ \sum ∑dp[k][y](Pk > Py, k > x)
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 5005;
constexpr int mod = 998244353;
int n, f[N][N], ans, inv[N], a[N];
int main(void) {
scanf("%d", &n);
inv[1] = 1;
for (int i = 2; i <= n; i ++ )
inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for(int i = n; i >= 0; i --) {
int sum = 0, cnt = 0;
for(int j = n; j >= 0; j --) {
if(a[j] < i) f[a[j]][i] = (1ll * sum * inv[cnt] + 1) % mod;
if( i < a[j]) {
sum = (sum + f[i][a[j]])%mod;
cnt++;
}
}
}
for(int i = 1; i <= n; i ++)
ans = (ans + f[0][i]) % mod;
printf("%d\n", 1ll * ans * inv[n] % mod);
return 0;
}
K. Knowledge Test about Match
k题是个瞎搞题，看代码吧，反正很玄学, 等我再体会体会回来更新吧
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(X) ((int)(X).size())
#define rep(i, a, n) for (int i = a; i <= n; i ++ )
#define per(i, a, n) for (int i = n; i >= a; i -- )
#define endl '\n'
const int N = 1010;
double w[N];
int n;
int b[N];
void init() {
rep(i, 0, 1000) w[i] = sqrt(i);
return;
}
void solve() {
cin >> n;
rep(i, 0, n - 1) cin >> b[i];
sort(b, b + n);
rep(k, 0, 4) {
rep(i, 0, n - 1) {
rep(j, i + 1, n - 1) {
if (w[abs(b[i] - j)] + w[abs(b[j] - i)] < w[abs(b[i] - i)] + w[abs(b[j] - j)]) {
swap(b[i], b[j]);
}
}
}
}
rep(i, 0, n - 1) cout << b[i] << ' ';
cout << '\n';
}
signed main(void) {
init();
int t;
cin >> t;
//t = 1;
while (t -- ) {
solve();
}
return 0;
}
