解题报告_ NOIp2017 提高组 [exgcd, GG]

有的时候应该坚持自己的想法

即使并非最优

首先为南京大屠杀默哀

先留个坑….

懵逼的 题目

传送至 Luogu

扯淡的 题解

D1T1

我终于证明了我的方法是对的…

设一个能达到的数为maxz
而且ans = maxz - 1
那么这个maxz有什么性质呢…
首先maxz == ax + by(他本身必须能被凑出, 要不然他自己就是答案了)

然后观察一个能凑出数(以下称为合法的数, 注意这里的合法是指能够通过a, b凑出) 如何凑出比他小1的数: 减掉几个a, 加上几个b; 或者加上几个a, 减掉几个b;
而这”几个”是怎么得出的呢?
显然是这个样的…
ax1 - by1 = 1: 减去x1a, 加上y1b, 可以让一个合法的数z变为z - 1;
bx2 - ay2 = 1: 减去x2b, 加上x2a, 可以让一个合法的数z变为z - 1;

所以如果我们能求出x1, y1, x2, y2就能让所有的合法的数z变成z - 1辣…………吗?
显然如果一个数z = ax + by, 如果他的a的个数x小于x1, 不能通过减掉几个a, 再加上几个b来让z变成z - 1, 并且他的b的个数y也小于x2, 不能通过减掉几个b, 再加上几个a来让z变成z - 1
他就是maxz, 为什么呢, 因为maxz - 1不能凑出嘛
但是如何保证maxz最大呢?
显然就是让maxz = ax + by, x = x1 - 1, y = x2 - 1就行了….因为一旦又加了一个x或者y, 就都可以让maxz - 1被凑出: 因为可以减掉x1a或者减掉x2b
证毕….?

所以算法就是求ax1 - by1 = 1bx1 - ay1 = 1x1, x2, 答案就是x1 * a + x2 * b - 1

不得不说用exgcd做出D1T1对我意义挺大的…这表明了…我是对的! 我在考场上托腮思考的1.5h没有浪费! 我还是那个宽嫂! 那个不一般的宽嫂!

D1T2

SB模拟…注意几个细节就好了…
考场上输出”ERR”之后没有把这个程序剩下的部分都读完…导致下一次循环从上次”ERR”的地方开始读的…我说怎么当时单个的测样例没问题…一旦多组数据就GG…看了好几遍初始化原来是这个问题….
还有就是x < y的情况比较蛋疼…多注意一下…不要把unused加多了…注意unused一旦不为0就没必要操作了….

D1T3

未完待续…

沙茶的 代码

D1T1

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
46
47
48
49
50
51
52
53
54
/*
ax + by = 1
x0, y0 -> x', y"
a * (x' - 1) + b * (y" - 1)
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#define pll pair<LL, LL>
#define LL long long
using namespace std;

LL solve(LL, LL, LL);
LL exgcd(LL, LL, LL&, LL&);
int main()
{
LL a, b;
scanf("%lld%lld", &a, &b);
LL maxb = solve(a, b, 1);
LL maxa = solve(b, a, 1);
printf("%lld", (a * (maxb - 1) + b * (maxa - 1) - 1));
return 0;
}
LL solve(LL a, LL b, LL c)
{
LL x, y;
LL gcd = exgcd(a, b, x, y);
y = -y;
LL tb = b / gcd;
while (x < 0)
x += tb;
return x;
}
LL exgcd(LL a, LL b, LL& x, LL& y)
{
if (!b)
{
x = 1;
y = 0;
return a;
}
else
{
LL re = exgcd(b, a % b, y, x);
y -= a / b * x;
return re;
}
}

/*
3 5
7
*/

D1T2

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <stack>
#define MAXN (100 + 5)
#define MAXT (10 + 5)
#define MAXC (26 + 5)

#define PUTSERR cout << "ERR\n"

#define CTI(a) ((a) - '0')
#define CTC(a) ((a) - 'a')

// #define GG
using namespace std;

bool used[MAXC];

void init();
void solve();
int STI(string&, int);
void qp(int, int);
int main()
{
#ifdef GG
freopen("in.in", "r", stdin);
#endif
int t;
cin >> t;
while (t--)
{
init();
solve();
}
return 0;
}
void init()
{
memset(used, false, sizeof(used));
}
void solve()
{
int len;
string fzd;
int inw;
cin >> len >> fzd;
if (fzd[2] == '1')
inw = 0;
else
inw = STI(fzd, 4);
int totf = 0;
int tw = 0;
int noww = 0;
int unused = 0;
string dq;
stack <char> s;
stack <int> ins;
for (int i = 1; i <= len; i++)
{
cin >> dq;
if (dq == "E")
{
--totf;
if (unused > 0)
--unused;
if (totf < 0)
{
qp(i, len);
PUTSERR;
return ;
}
if (!s.empty())
{
used[CTC(s.top())] = false;
s.pop();
}
if (!unused && !ins.empty())
{
noww -= ins.top();
ins.pop();
}
}
else if (dq == "F")
{
++totf;
if (unused)
++unused;
cin >> dq;
if (used[CTC(dq[0])])
{
qp(i, len);
PUTSERR;
return ;
}
s.push(dq[0]);
used[CTC(dq[0])] = true;
string dqxs, dqys;
cin >> dqxs >> dqys;
int dqx = STI(dqxs, 0);
int dqy = STI(dqys, 0);
if (dqxs == "n" && dqys != "n" && !unused)
{
++unused;
}
else if (dqxs != "n" && dqys == "n" && !unused)
{
++noww;
ins.push(1);
tw = max(tw, noww);
}
else if (dqy < dqx && !unused)// 就是这个地方...n被转成了数字...结果导致unused被多加了几遍...
{
++unused;
}
else if (dqy > dqx && !unused)
{
ins.push(0);
}
}
}
if (totf)
{
PUTSERR;
return ;
}
if (tw == inw)
{
cout << "Yes\n";
}
else
{
cout << "No\n";
}
}
int STI(string& x, int be)
{
int re = 0;
int xn = x.length();
for (int i = be; i < xn; i++)
{
if (x[i] > '9' || x[i] < '0')
break;
re = (re << 1) + (re << 3);
re += CTI(x[i]);
}
return re;
}
void qp(int from, int to)
{
char a[1000];
for (int i = from; i <= to; i++)
{
cin.getline(a, 1000, '\n');
}
}

/*
1
4 O(n^2)
F x 5 n
F y 10 n
E
E
*/

By 一个中二病晚期 Cansult