The 2020 ICPC 沈阳 DFIK

Nannan Lv5
  2023-09-12 11:28 2023-09-12 11:28 Created   2024-09-30 16:58:15 2024-09-30 16:58:15 Updated      

Dashboard - The 2020 ICPC Asia Shenyang Regional Programming Contest - Codeforces DFIK

D. Journey to Un’Goro

思路：思维+搜索

一开始以为是构造，好吧但是是搜索。

我们先考虑什么时候是最大值？

首先考虑，题目要求我们从且红色的数量是奇数被认为是好的。那么我们考虑记录表示前个里面红色的数量。那么从的红色的数量就可以表示为：。又因为要求红色的数量是奇数，那么对于从红色的数量是奇数那么：和的奇偶性应该不一样。那么我们考虑对于里面有个奇数和个是偶数，那么最终的答案对数就是。那么如果要求最大的，两个数的和为且乘积的值最大，肯定是两个越接近的数的乘积。那么答案就是。

接下来输出方案数。原本以为答案只输出前种只是为了不要输出太多，其实是为了方便我们剪枝。之后我们只要考虑去搜就啦。

剪枝的话:记录前步，前缀是偶数出现次数，前缀是奇数出现次数，当前的奇偶性，表示偶数，表示奇数。如果当或者其中一个大于一半以上就直接了，因为肯定不满足。如果方案数已经有了，那么也直接。

注意：

  1. 只有红色能改变奇偶性
  2. 要求字典序最小，那先考虑放。
  3. 为什么要记录?因为如果当前是奇数那么加上一个还是奇数，否则如果是偶数加上一个数还是偶数，我需要知道前缀是奇数还是偶数来确定当前加的这个使得奇数前缀增加还是偶数前缀增加。
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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll n,hav;
char a[N];
void dfs(int step,int cnt0,int cnt1,int st)
{
    if(hav>=100)exit(0);
    if(cnt0>(ll)ceil(1.0*(n+1)/2)||cnt1>(ll)ceil(1.0*(n+1)/2))return;
    if(step>n)
    {
        for(int i = 1;i <= n; i++)
            cout<<a[i];
        cout<<"\n";
        hav++;
        return;
    }
    a[step] = 'b';
    dfs(step+1, cnt0 + (st^1), cnt1 + st, st);
    
    a[step] = 'r';
    st ^= 1;
    dfs(step+1, cnt0 + (st^1), cnt1 + st, st);
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n;
    cout<<(n+1)/2*(ll)ceil((n+1)*1.0/2)<<"\n";
    dfs(1,1,0,0);
    return 0;
}

F. Kobolds and Catacombs

思路：思维

我们先对原数组排序得到最终数组。我们去求这两个数组的前缀和，当且仅当前缀和一样的时候可以被分成一段，那么我们只需要判断有几个前缀和一样就可以了。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
ll a[N],b[N],sa[N],sb[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    for(int i = 1;i <= n; i++)
        cin>>a[i],b[i] = a[i];
    sort(b+1,b+1+n);
    for(int i = 1;i <= n; i++)
        sa[i] = sa[i-1]+a[i],sb[i] = sb[i-1]+b[i];
    int cnt = 0;
    for(int i = 1;i <= n; i++)
        if(sa[i]==sb[i])cnt++;
    cout<<cnt<<"\n";
    return 0;
}

I. Rise of Shadows

思路：数论，追击问题，我们以时针作为参照物(静止不动),相对运动速度针对分针分析。

绝对绝对

相对绝对绝对绝对

相当于分针相对于时针以每分钟的速度运动。

绝对绝对

其中

那么柿子转化为：绝对绝对

即：

根据剩余定理：如果是模的一个完全剩余系，且有,那么也是模的一个完全剩余系。更一般地，也是完全剩余系。

为满足互质条件，同除，那么

那么：

同时

接下来只需求解出的整数解的个数。

因为是的完全剩余系，又,那么也是构成模意义下的完全剩余系。

由于之后余数，因此一共又，一共个，并且无重复。即于余数值一一对应。在中一共有个。

再把还原到,答案就是个。

注意特判：，此时所有都满足，答案是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll H,M,A;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>H>>M>>A;
    if(2*A==H*M)cout<<H*M<<"\n";
    else
    {
        //(H-1)t mod HM = |A|
        ll g = __gcd(H-1,H*M);
        cout<<(2*(A/g)+1)*g<<"\n";
    }
    return 0;
}

K.Scholomance Academy

思路：小模拟

注意：分界点的处理。考虑，如果去除分界点会怎么样呢？会变成一条斜线，我们考虑把它拉平(emmm，可能有点抽象hh)。

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
#include<bits/stdc++.h>

using namespace std;


typedef long long ll;

const int N = 1e6 + 10;

vector<int> vx;
vector<int> a, b;
vector<pair<double, double>> event;
int n;
void solve()
{
	cin>>n;
	for(int i = 1; i <= n; i++)
	{
		char opt[2];	int x;	
		// cin>>opt>>x;
		scanf("%s%d", opt, &x);
		vx.push_back(x);
		vx.push_back(x - 1);
		vx.push_back(x + 1);
		// mp[x]++;
		if(opt[0] == '+')
			a.push_back(x);
		else
			b.push_back(x);
	}
	sort(vx.begin(), vx.end());
	vx.erase(unique(vx.begin(), vx.end()), vx.end());
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	int sza = a.size(), szb = b.size();
	for(auto x : vx)
	{
		// if(mp[x] >= 2)	continue;
		int TP = 0, FN = 0, FP = 0, TN = 0;
		if(lower_bound(a.begin(), a.end(), x) == a.end())
			TP = 0, FN = sza;
		else
		{
			int sz = lower_bound(a.begin(), a.end(), x) - a.begin() + 1;
			TP = sza - sz + 1;
			FN = sza - TP;
		}
		if(lower_bound(b.begin(), b.end(), x) == b.end())
			TN = szb;
		else	
		{
			int sz = lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
			FP = szb - sz + 1;
			TN = szb - FP;
		}
		double TPR = 1.0 * TP / (1.0 * TP + FN);
		double FPR = 1.0 * FP / (1.0 * TN + FP);
		// cout<<"x : "<<x<<"  FPR : "<<FPR<<"  TPR : "<<TPR<<'\n'; 
		// if(FPR == 0.5 && TPR == 0.5)	continue;

		event.push_back({FPR, TPR});
	}
	event.push_back({0.0, 0.0});
	sort(event.begin(), event.end());
	int m = event.size();
	double res = 0;
	for(int i = 1; i < m; i++)
	{
		double tx = event[i - 1].first, ty = event[i - 1].second;
		double x = event[i].first, y = event[i].second;
		
		if(x == 0.5 && y == 0.5)
			y = 0.25;
		// cout<<"x : "<<x<<"  y : "<<y<<'\n';
		if(x != tx && y != ty)
				y = ty;

		res = res + (x - tx) * y;
	}
	// cout<<res<<'\n';
	printf("%.11lf\n", res);

}
int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);	cout.tie(nullptr);

	solve();

}
  • Title: The 2020 ICPC 沈阳 DFIK
  • Author: Nannan
  • Created at : 2023-09-12 11:28:00
  • Updated at : 2024-09-30 16:58:15
  • Link: https://redefine.ohevan.com/2023/09/12/Dashboard - The 2020 ICPC Asia Shenyang Regional Programming Contest - Codeforces DFIK/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
The 2020 ICPC 沈阳 DFIK
  1. Dashboard - The 2020 ICPC Asia Shenyang Regional Programming Contest - Codeforces DFIK
    1. D. Journey to Un’Goro
    2. F. Kobolds and Catacombs
    3. I. Rise of Shadows
    4. K.Scholomance Academy