第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(沈阳)G F K I

发布于 2022-10-23  1035 次阅读


比赛传送门:第 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;
}