第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（沈阳）（重现赛）
传送门：ICPC沈阳
F - The Witchwood
这重现赛，这数据，我既然被hack了，我写的代码太拉跨了？？？？？
对原来的代码做了亿点点修改：对于每一个小区间，区间内的和与排序后区间内的和是一样的。所以。。。。
#pragma warning(disable:4996)
#include<iostream>
#include<string.h>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<set>
#include<algorithm>
#include<sstream>
#include<vector>
#include<ctype.h>
#include<list>
//#include <unordered_map>
#include<deque>
#include<functional>
using namespace std;
const int maxn = 1e6 + 9;
long long a[maxn], sorted[maxn], le = 0, ri = 0, minn = 0x3f3f3f3f, maxx = 0;
int main()
{
int n, ans = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
sorted[i] = a[i];
}
long long suma = 0, sumb = 0;
sort(sorted, sorted + n);
for (int i = 0; i < n; i++) {
suma += a[i];
sumb += sorted[i];
if (suma == sumb)ans++;
}
cout << ans;
return 0;
}
G - The Witchwood
solved by Micky. 00:32:02(+)
签到。略
#pragma warning(disable:4996)
#include<iostream>
#include<string.h>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<set>
#include<algorithm>
#include<sstream>
#include<vector>
#include<ctype.h>
#include<list>
//#include <unordered_map>
#include<deque>
#include<functional>
using namespace std;
const int maxn = 1e5 + 9;
long long a[maxn], ans, n, k;
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
for (int i = n - 1; i >= n - k; i--) {
ans += a[i];
}
cout << ans;
return 0;
}
I - Rise of Shadows
solved by oye (after).
题意：
给你一个特定的钟，有H小时，每小时有M分钟。问从0:00开始，时钟转完一圈的时间内，分钟和时钟的夹角小于等于
2
π
A
H
M
\frac{2\pi A}{HM}
HM2πA的次数有几次（分针指到格子线才算一次）
一开始，我和我的队友都以为是追及问题，怎么都过不了，一直卡到赛后。也不明白为什么是奇数，后来才发现，最后的那个重合是不用算的，相当于我们现实生活中，实际有效时间其实只有0：00~11:59（我指转一圈）。
因为要分针指到格子线才算一次，追及算时间算路程那个没法用，所以用假设先把题目化成通式。
假设一时间为
t
(
t
∈
[
0
,
H
M
)
，
t
∈
Z
,
单
位
：
分
钟
)
t(t\in[0,HM)，t\in Z,单位：分钟)
t(t∈[0,HM)，t∈Z,单位：分钟)
此时，时针的角度为
2
π
t
H
M
\frac{2\pi t}{HM}
HM2πt，分钟角度为
2
π
t
M
\frac{2\pi t}{M}
M2πt。求满足
∣
2
π
t
H
M
%
2
π
−
2
π
t
M
%
2
π
∣
≤
2
π
A
H
M
|\frac{2\pi t}{HM}\%2\pi-\frac{2\pi t}{M}\%2\pi|\leq\frac{2\pi A}{HM}
∣HM2πt%2π−M2πt%2π∣≤HM2πA的
t
t
t的个数
将该式化简得
t
(
H
−
1
)
m
o
d
H
M
≤
A
t(H-1) \mod HM\leq A
t(H−1)modHM≤A
or
t
(
H
−
1
)
m
o
d
H
M
≥
(
H
M
−
A
)
t(H-1) \mod HM\geq (HM-A)
t(H−1)modHM≥(HM−A)
我们先看
t
(
H
−
1
)
m
o
d
H
M
≤
A
t(H-1) \mod HM\leq A
t(H−1)modHM≤A这个式子。oye我就是卡在这里，完全想不出来要怎么求个数，同余定理和中国剩余定理翻了翻好像都没有什么能解决解的个数问题的。后来还是队友翻到了官方题解，找到了关键的一步——
t
(
H
−
1
)
g
m
o
d
H
M
g
≤
A
g
\frac{t(H-1)}g \mod \frac{HM}g\leq \frac{A}g
gt(H−1)modgHM≤gA（为了方便点设
g
=
gcd
(
H
−
1
,
H
M
)
g=\gcd(H-1,HM)
g=gcd(H−1,HM)，注：此时的
t
∈
[
0
,
H
M
g
)
,
t
∈
Z
t\in[0,\frac{HM}g),t\in Z
t∈[0,gHM),t∈Z）
哦，然后官方就得出了个数是
A
g
+
1
\frac{A}g+1
gA+1（冷漠脸）。可恶，和数学答案里面的易得有什么区别嘛，摔！不过后面证完之后，的确有点易得的感觉，TAT太菜了我。
下面证明：
先不考虑后面的
A
g
\frac A g
gA，单看前面的式子，设
t
a
m
o
d
b
=
r
ta \mod b=r
tamodb=r（方便起见，设
a
=
H
−
1
g
，
b
=
H
M
g
a=\frac{H-1}g，b=\frac{HM}g
a=gH−1，b=gHM）
已知，
r
∈
[
0
,
b
)
,
r
∈
Z
r\in[0,b),r\in Z
r∈[0,b),r∈Z，跟
t
t
t的取值是不是一样，所以大胆假设，
t
t
t和
r
r
r存在一一对应关系。
利用反证法，假设存在
t
1
,
t
2
(
t
1
>
t
2
)
t_1,t_2(t_1>t_2)
t1,t2(t1>t2)使得
t
a
m
o
d
b
=
r
ta \mod b=r
tamodb=r
即，
(
t
1
−
t
2
)
a
m
o
d
b
=
0
(t_1-t_2)a \mod b=0
(t1−t2)amodb=0（同余定理）
已知此时，
a
,
b
a,b
a,b互质，故要使该式有解，一，满足
t
1
=
t
2
t_1=t_2
t1=t2，矛盾；二，满足
t
1
=
x
(
t
2
+
b
)
t_1=x(t_2+b)
t1=x(t2+b)，与
t
∈
[
0
,
b
)
t\in[0,b)
t∈[0,b)矛盾
故，得证。
再来看
t
(
H
−
1
)
g
m
o
d
H
M
g
≤
A
g
\frac{t(H-1)}g \mod \frac{HM}g\leq \frac{A}g
gt(H−1)modgHM≤gA，由上面的证明可得，对于
r
∈
[
0
,
A
g
)
,
r
∈
Z
r\in[0, \frac{A}g),r\in Z
r∈[0,gA),r∈Z，都可以在
t
∈
[
0
,
H
M
g
)
,
t
∈
Z
t\in[0,\frac{HM}g),t\in Z
t∈[0,gHM),t∈Z中找到对应的
t
t
t。故
t
t
t的个数，就是
r
r
r的个数，即
A
g
+
1
\frac{A}g+1
gA+1。
同理操作第二个式子，将两个式子的结果加起来得到
2
∗
A
g
+
1
2*\frac{A}g+1
2∗gA+1，由于先前除以了
g
g
g，所以最后结果还要把
g
g
g乘回去。
故这题的最终解是 g ( 2 ∗ A g + 1 ) g(2*\frac{A}g+1) g(2∗gA+1)
还有一个特判是在 2 A = H M 2A=HM 2A=HM的时候，此时答案为 2 A 2A 2A（因为此时分针相对于时针满足条件的范围为整一圈，在边界处发生了重复）——来自被数学逼疯的oye
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll h,m,a;
int main()
{
scanf("%lld%lld%lld",&h,&m,&a);
ll g=__gcd(h-1,h*m);
if(a==h*m/2) printf("%lld",h*m);
else printf("%lld",g*(2*(a/g)+1));
return 0;
}