比赛传送门：第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（沈阳）
G - The Witchwood（签到）
选出最大的K个数字求和即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
int a[maxn];
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int N, K;cin >> N >> K;
for(int i = 1;i <= N; ++ i)cin >> a[i];
sort(a + 1,a + 1 + N, [](const int &a,const int &b)
{
return a > b;
});
int ans = 0;
for(int i = 1;i <= K; ++ i)ans += a[i];
cout << ans << '\n';
return 0;
}
F - Kobolds and Catacombs（排序 + Hash）
给定一个序列，将其划分为若干份，将每一份分别排序后，可以使得整体序列非降序，问怎样划分使得份数最多。
读入a序列，再将b序列作为a序列排序后的序列，从前往后遍历，如果某个区间[l, r]内包含的a中的元素和b中的元素相同，说明这里可以划分为一类，借助Hash来判断两个集合是否相等（没有顺序关系）。
这个Hash十分巧妙，利用三种具有交换律的运算（乘法、加法和异或），只有当参与运算的数字都相同时才会三者都相等，出错概率极低。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
typedef unsigned long long ULL;
int a[maxn], b[maxn];
struct Hash
{
ULL h1, h2, h3;
Hash()
{
clear();
}
void add(int x)
{
h1 = h1 * (x * x + 131);
h2 = h2 + (x * x + 1331);
h3 = h3 ^ (x * x + 13331);
}
void clear()
{
h1 = h2 = h3 = 1;
}
bool operator == (Hash &b)
{
return h1 == b.h1 && h2 == b.h2 && h3 == b.h3;
}
};
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int N;cin >> N;
for(int i = 1;i <= N; ++ i)cin >> a[i], b[i] = a[i];
sort(b + 1,b + 1 + N);
Hash ha, hb;
int ans = 0;
for(int i = 1;i <= N; ++ i)
{
ha.add(a[i]), hb.add(b[i]);
if(ha == hb)
{
ans ++;
ha.clear(), hb.clear();
}
}
cout << ans << '\n';
return 0;
}
K - Scholomance Academy（前缀和）
前缀和搞一搞就出来了。将点作为关键帧，描绘出矩形面积。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
int p0[maxn], p1[maxn];//分别表示正负的个数
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int N;cin >> N;
vector<pair<int, char> > v;
v.push_back({0, '#'});
for(int i = 1;i <= N; ++ i)
{
char ch;cin >> ch;
int x;cin >> x;
v.push_back({x, ch});
}
sort(v.begin(), v.end());
for(int i = 1;i <= N; ++ i)
{
p0[i] = p0[i - 1], p1[i] = p1[i - 1];
if(v[i].second == '-')p0[i] ++;
if(v[i].second == '+')p1[i] ++;
}
double ans = 0.0, lst = 0.0;
for(int i = 0;i <= N; ++ i)
{
//当cita等于v[i].x时，x <= c的认为负，x > c认为正数
//如果前后两个关键帧的值相同，直接向后移动，说明当前点不能作为关键帧
if(i < N && v[i].first == v[i + 1].first)continue;
int tp = p1[N] - p1[i];
int fn = p1[i];
int tn = p0[i];
int fp = p0[N] - p0[i];
double tpr = 1.0 * tp / (tp + fn), fpr = 1.0 * fp / (tn + fp);
//cout << tpr << ' ' << fpr << '\n';
ans += tpr * (fpr - lst);
lst = fpr;
}
cout << fixed << setprecision(10) << 1.0 - ans << '\n';
return 0;
}
I - Rise of Shadows（数论）
分享一篇写的很好的题解：2020 ICPC 沈阳站 I - Rise of Shadows 题解 - olderciyuan - 博客园 (cnblogs.com)
选取“分钟”作为原子单位，时针的位置和分针的位置都可以用分钟来表达，设当前时间为t（分钟），则t的取值为[0, HM - 1]，这个不难理解。
当时间为T时，时针相对0刻度的角度为：
\(w_{1} = \frac{2\pi t}{HM}\)
时针转动一周的时间为HM，而当前时间为T，总角度为\(2\pi\)。
同样地，分针的角度为：
\(w_{2} = \frac{2\pi t}{M}\)
不妨设分针永远在时针前面，得到角度差，注意对2pi取模，因为可能出现负数，取模后会变为一个钝角，表示的意义是下一圈的时针减去当前分针的角度：
\(\theta = (w2 - w1) \% (2\pi) = (2\pi / (HM) * t(1 - H))\%(2\pi)\)
再结合题目给的条件：
\(\theta \le 2\pi A / (HM) 或 \theta \ge 2\pi - 2\pi A / (HM)\)
整理一下得到：
\(ans = \sum_{t=0}^{HM - 1}[t(H - 1) \% (HM) \le A 或 t(H-1)\%(HM)\ge HM-A]\)
我们将其分开来考虑，对于左边这个式子，根据完全剩余系的知识，我们知道若a*x mod m是一个完全剩余系，那么x和m互质，且对于a属于[0, m - 1]，a * x在[0, m - 1]是一个满射。
对于上式中如果\(gcd(H-1,HM) = 1\)，那么答案就是A + 1，相当于T在[0, HM - 1]中参数和值一一对应。
如果H-1和HM不互质，就需要构造一下，令\(g = gcd(H-1, HM)\)，将左右两边同时除以g，得到：
\(t(H-1)/g \%(HM/g) \le A/g\)
此时t的取值范围是[0, HM/g - 1]，但是这只是第一个完全剩余系中的结果，一共有多少个呢？一共有g个，所以算出第一个的再乘g就可了，第一个完全剩余系中有多少是<=A/g的呢？显然是A/g + 1个（加上0）。
综上，左边这个式子求和的答案是\(g * (a/g + 1)\)，a/g是向下取整。
右边这个式子，这样考虑，首先如果g = 1，那么就有A个满足条件的t（从HM - A到HM - 1）。
当g>1的时候需要分类讨论，当HM - A能够整除g时，答案是g * (A / g)，当HM - A不能整除g时，答案是g * ((A - g + 1) / g)。这个动手画一画就出来了。
有些大佬分析第二个式子的时候都是g * (A / g)，俺不知道啥原理。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
int gcd(int a,int b)
{
return b == 0 ? a : gcd(b, a % b);
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int H, M, A;cin >> H >> M >> A;
if(2 * A == H * M)cout << H * M << '\n';
else
{
int g = gcd(H - 1, H * M);
if((H * M - A) % g == 0)cout << 2 * g * (A / g) + g << '\n';
else cout << g * (A / g) + g + g * ((A - g + 1) / g) << '\n';
}
return 0;
}
文章评论
wwwwwwwE神