停课集训模拟测试-第N+1场考试分析Day1

发表于 | 阅读次数:
字数统计: 837 字

今天是又一套题， 感觉好像难度偏难一些 . . . （可能我还是比较弱吧）自我感觉好像打的还可以。

分数：70 + 0 + 10 = 80分

考试开始：

今天考试开始之后，先看了下T1。第一眼好像是差分， 第二眼感觉不对啊，好像并不是区间修改， 也不是变成一样的数字， 是都变成0。 所以好像不是差分。再看一眼之后发现好像每一个数都是独立的， 与前后的无关， 所以这个数所消耗的 a 和 b 的个数就只由这个数所决定。于是就列了一个方程， 发现这不就是裸的Exgcd吗，然后很兴奋的开始打了一个Exgcd出来。但是又发现这个解就是在限制ax+by=c中|x|+|y|最小。想起来拓展欧几里得的一个性质， 这个解出来的一组解可以保证|x|+|y|最小。 但是好像如果c不是gcd(a, b)的情况下，使用裴蜀定理 可以发现当且仅当c|gcd(a, b)的时候，这个不定方程有解。于是我们知道了输出-1的情况，所以我们现在只需要找出满足ax+by=c的一组解，使得|x|+|y|最小。然后问题就来了，我们可以用一组特解来推出满足这个不定方程的一组通解， 但是我们还需要保证|x|+|y|最小。 搞了差不多20分钟左右才把这个调好， 然后开始看后面题。 发现好像T2不可做， T3可以打15分的暴力。 于是剩下的时间草草打完暴力就结束了上午的比赛。预计得分：100+15 = 115分。

考试结束：

等到考试结束后， 看了下成绩发现好像T1没有A掉的， 在场最高80分，我拿了70分左右。 T3少了5分， 好像是因为p==n的数据出了一些问题。导致5分的送分又挂了. . . 总体感觉还好吧， 明天的比赛加油！

失误总结

  1. 之后比赛有一个时间分配，规定如果是比较重要的比赛的话， 尽量1道正解，1道高分暴力， 1道小暴力分。大概这样打题的话如果不打挂题的话， 差不多两天300+是没有太大问题的。

题解

有一道考验性质的题， 贴一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h> 
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const ll INF = 1e9;
ll a, b, c;
void Exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
	if (!b) {
		x = 1;
		y = 0;
		d = a;
		return;
	}
	ll tx, ty;
	Exgcd(b, a % b, d, tx, ty);
	x = ty;
	y = tx - (a / b) * ty;
}
inline ll abs(ll a) {return a < 0 ? -a : a;}
int main() {
	while(cin>>a>>b>>c,a|b|c) {
		bool flag = 0;
		ll min_x, min_y;
		if (a < b) swap(a, b), flag = 1;
		ll d, x0, y0;
		Exgcd(a, b, d, x0, y0);
		x0 *= c/d;
		y0 *= c/d;
		ll t = y0 / (a / d); ll minn = INF;
		for (int i=t-5;i<=t+5;++i)	{
			ll x = x0 + b/d * i;
			ll y = y0 - a/d * i;
			if (abs(x) + abs(y) < minn) {
				minn = abs(x) + abs(y);
				min_x = abs(x);
				min_y = abs(y);
			}
		}
		if (flag) printf("%lld %lld\n", min_y, min_x);
		else printf("%lld %lld\n", min_x, min_y);
	}
	return 0;
}