2021年第19届浙江省程序设计竞赛题解&比赛心得
这篇是和队友一起出的一份题解,这次省赛打的算是成功,但是也有遗憾,最后的I题有一种特况没考虑到,主要是没有实物不好模拟,全靠想象也不好搞(还是我们太菜了)。最后Cu首收尾。希望下次省赛冲波Ag吧。
队友在写题解了,会慢慢更新的。
计划是除了EHK都试着补一下。
进入正题F. Fair Distribution
题意:T组数据,每组数据有a,b两个数,其中a只能减,b只能加,每次加一或者减一的代价是1,问使最后b % a == 0的代价最小是多少。
方法:暴力, 数学
两种情况
1、$a\ge b$时显然答案是$a - b$
2、$a < b$时,最后的$a$一定是在$[1, \sqrt b]$或者$\frac{b}{a}$在$[1, \sqrt b]$内,所以对$b$开根号然后暴力验证就行
做一个简单的说明吧,其实很容易看的出来,假设b不变的时候,我们刚刚的想法肯定是没问题的。当b要增加的时候,最坏情况下就是a = b - 1, b要增加两倍,但是最后的$\frac {b}{a}$还是在$\sqrt{b}$内。(不严谨,但是应该能理解其正确性)
接下来给出代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
inline int lc(int u) {return u << 1;}
inline int rc(int u) {return u << 1 | 1;}
inline void solve() {
LL a, b; cin >> a >> b;
if (a >= b) cout << a - b << endl;
else {
LL res = 1e9 + 10;
LL k = (LL)sqrt(b);
for (int i = 1; i <= k; i ++ ) {
if (b % i) {
if (a >= i)
res = min(res, a - i + abs((b + i - 1) / i * i - b));
if (a >= (b + i - 1) / i) {
LL now = (b + i - 1) / i;
res = min(res, abs(a - now) + abs((b + now - 1) / now * now - b));
}
} else {
if (a >= i)
res = min(res, a - i);
if (a >= b / i)
res = min(res, abs(a - b / i));
}
}
cout << res << endl;
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int t; cin >> t;
while (t -- )
solve();
return 0;
}
队友写的题解
题意:给你一张图,每个点上面都有无穷个宝石,每个宝石都有自己的价值,同一个点上的宝石价值一样。边权为1,每次可以从点1出发去某个点拿走一个宝石然后回到1号点, 当且仅当你去那个点拿到一个宝石并且回到起点才算得到这个宝石的价值, 手上最多只能有一个宝石。每次经过一条边的耗时是1,问在时间T内的每个时间点可以得到的价值最多是多少。
方法:BFS,完全背包
稍微想一下容易得出是一个完全背包,设$d[u]$表示u点到1的距离,于是就变成了一个完全背包的问题。n个物品,每个物品有无限个,你有一个总体积为T的背包,每类物品的代价是$2 \times d[u]$,价值是$a[u]$。就是一个板子题了。先BFS预处理出d数组,然后套板子即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x7f7f7f7f, N = 1e5 + 10;
inline int lc(int u) {return u << 1;}
inline int rc(int u) {return u << 1 | 1;}
int a[N], d[N];
int n, m, t;
int h[N], val[N * 2], nex[N * 2], idx;
LL dp[N];
void bfs() {
memset(d, 0x7f, sizeof d);
queue<int> q;
q.push(1);
d[1] = 0;
while (!q.empty()) {
int tt = q.front();
q.pop();
for (int i = h[tt]; ~i; i = nex[i]) {
int j = val[i];
if (d[j] != INF) continue;
d[j] = d[tt] + 2;
q.push(j);
}
}
}
inline void add(int x, int y) {
val[idx] = y, nex[idx] = h[x], h[x] = idx ++;
}
inline void solve() {
memset(h, -1, sizeof h);
cin >> n >> m >> t;
for (int i = 2; i <= n; i ++ ) cin >> a[i];
while (m -- ) {
int x, y; cin >> x >> y;
add(x, y), add(y, x);
}
bfs();
for (int i = 1; i <= n; i ++ ) {
for (int j = d[i]; j <= t; j ++ )
dp[j] = max(dp[j], dp[j - d[i]] + a[i]);
}
for (int i = 1; i <= t; i ++ ) cout << dp[i] << ' ';
cout << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
// int t; cin >> t;
// while (t -- )
solve();
return 0;
}
题意:有一个憨憨写了一个KMP的假算法,然后给你一个模式串,问你能不能出一个匹配串把这个代码卡WA掉。
方法:KMP
其实还是比较好理解的,看代码就知道这里和标准的KMP代码有一个不一样,就是KMP是如果不匹配就跳到nex数组中,而给出的代码是直接跳到起点,所以如果我们的nex数组中有一个nex值不是跳到起点的,就可以构造出这样的字符串把他hack掉。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
inline int lc(int u) {return u << 1;}
inline int rc(int u) {return u << 1 | 1;}
char s[N];
int nex[N];
inline void solve() {
int n; cin >> n;
scanf("%s", s + 1);
for (int i = 2, j = 0; i <= n; i ++ ) {
while (j && s[i] != s[j + 1]) j = nex[j];
if (s[i] == s[j + 1]) j ++ ;
nex[i] = j;
}
for (int i = 1; i <= n; i ++ ) {
if (nex[i] != 0) {
puts("Wrong Answer");
return ;
}
}
puts("Correct");
}
int main() {
// ios::sync_with_stdio(false), cin.tie(nullptr);
// int t; cin >> t;
// while (t -- )
solve();
return 0;
}
题意:老师和学生各出一个数字,范围在$[1, 20]$,假设老师出了x,学生出了y,就有接下来几步。
1、老师给学生x分
2、学生给老师y分
3、如果$x > y$学生多给老师10分
4、如果$y > x$老师多给学生10分
5、如果平局,双方均不用多给对方分。
注意,这里的给分数是从自己这边扣一些然后给对面的。
问:如果老师随机出值,每个学生可以自己选择值,问面对n个学生的情况下(对每个学生都是独立情况,也就是对上一个学生老师出的值和对这一个学生出的值是相互独立事件)老师的期望得分是多少。
赛场上第一眼看到数学期望直接爬了,结果一看通过率不少,就回头仔细研究了一下,列了下公式就出来了,下面是过程
我们容易看出,分数不会无故产生,都是老师和学生之间的流通,因此老师的期望得分就是学生的期望得分的负数。
对任意一轮,设老师出的值是x,学生是y,站在角度讲,得分的情况是
老师赢:$-x + y + 10$ $x \in [y + 1, 20]$
老师负:$-x + y - 10$ $x \in [1, y - 1]$
平局:$-x + y = 0$ $x = y$
再用我们小学二年级就学过的知识求期望(其实就是平均值)
$E = (y -x + 10) \frac{20 - y}{20} + (y - x - 10) \frac{y - 1}{20}$
化简得
$E = \frac{210 - 19x - y}{20}$
这是老师的得分期望,这里似乎还看不出啥,但是学生的期望就是$-E$啊
$-E = \frac{y + 19x - 210}{20}$
这里其实就看的出来了,学生可以自己决定y的大小,于是y一定是出最大为最优
那么就简单了,因为老师是等概率出数字的,于是出的x的期望一定是10,带入
$E = 0$
输出0即可
//我都讲的这么清楚了还要看代码么QAQ