比赛传送门:第 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; }
Comments 1 条评论
wwwwwwwE神