2018 ACM-ICPC, Asia Shenyang Regional

字数统计: 3.1k字   |   阅读时长: 16分
训练题解
solved A B C D E F G H I J K L M
4 / 13 · · Ø · · · O · · O · Ø ·
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

REPLY: 不知道是多少次不开llll导致wawa题了 --Tryna

比赛链接

C. Insertion Sort

solved by Sstee1XD. (-)

题意： 给你三个正整数nn，kk，qq(1≤n,k≤50,108≤q≤109)(1 \leq n, k \leq 50, 10^8 \leq q \leq 10^9)，其中qq为素数。。现在我们我们约定11到nn的一种排列是几乎已排序的定义如下：其最长上升子序列的长度至少为n−1n - 1。现在我们可以将排列的前kk个数按序排列，问有多少种序列能成为几乎已排序的，将答案modmod qq输出。

思路： 首先将序列变成11~nn的顺序排列，然后考虑对这个排列进行变形。

我们考虑前kk个是11~kk的全排列 ，那么后面数字都会比前面大，我们只要保证其最长上升子序列的长度至少为n−k+1n-k+1即可。这一步我们可以选择后面任意一个数字进行插排即可，但是这一步会重复计数。我们先算出(1n−k)∗(1n−k)\dbinom{1}{n-k}*\dbinom{1}{n-k}，然后考虑重复的情况。首先每个数都会进行一次顺序排列，所以要减去n−k−1n - k - 1。然后只有一组相邻逆序对的情况也是会重复计数的。例如435435，我们取出3和4的时候都能达到这种情况，其余情况皆不重复。共有n−k−1n-k-1个这种序列，所以也要减去。

接下来考虑前面并不是1k的全排列的情况，我们发现可以用$k+1$去代替其中任意一个数字，然后把这个被替代的数字在后面进行插排，都是合法的。$k+2$nn之间的数字只能和kk进行替换，并且只能放在k这个位置上。这样子的方案数是(1k)∗(1n−k)+n−k−1\dbinom{1}{k}*\dbinom{1}{n-k} + n - k - 1。

最后注意要乘以k!k!。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;

const int N = 50 + 7;

typedef long long ll;

ll n, k, mod;
int cas;

ll calc(ll n, ll k) {
    ll ak = 1;
    for (ll i = 2; i <= min(k, n); ++i) {
        ak = ak * i % mod;
    }
    if (n - k == 1) ak = ak * n % mod;
    if (n - k <= 1) return ak;
    ll ans = 0;
    ans = ans + ak * ((n - k) * (n - k) - 2 * (n - k) + 2) % mod;
    ans = ans + (ak * (k * (n - k) + (n - k - 1))) % mod;
    ans %= mod;
    return ans;
}

void solve() {
    cin >> n >> k >> mod;
    cout << "Case #" << ++cas << ": ";
    cout << calc(n, k) << endl;
}


int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

G. Best ACMer Solves the Hardest Problem

solved by all.3:49(+1)

题意 给出二维平面上的nn个点, 每个点都有权值ww。然后给出mm次操作，一共有四种操作:加入一个权值为ww的新点、删除一个点、将到(x,y)(x,y)点距离为k\sqrt{k}的点权值加ww、求到(x,y)(x,y)点距离为k\sqrt{k}的点的权值和，记录为lastanslastans并且输出它。以后每次输入的x,yx,y都要对lastanslastans取模加11。

题解： 按题意模拟即可，但暴力模拟会TLETLE,看了看kk的范围，所以我们预处理一下，将a2+b2=ka^2 + b^2 = k的值存下来。

AC代码 
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
const int maxn = 1e7 + 10;
vector<pii>v[maxn];
map<pii, int>mp;
int n, m, cnt;
void init() {
	for(ll i = 0; i <= 4000; i++) {
		for(ll j = 0; j <= 4000; j++) {
			if(i * i + j * j > 10000000) break;
			v[i * i + j * j].pb({i, j});
		}
	}
}

void run () {
	scanf("%d %d", &n, &m);
	cnt++;
	printf("Case #%d:\n", cnt);
	mp.clear();
	ll lastans = 0;
	for(int i = 1; i <= n; i++) {
		int x, y, w;
		scanf("%d %d %d", &x, &y, &w);
		mp[{x, y}] = w;
	}
	while(m--) {
		int q, x, y, w, k;
		scanf("%d", &q);
		if(q == 1) {
			scanf("%d %d %d", &x, &y, &w);
			x = (x + lastans) % 6000 + 1;
			y = (y + lastans) % 6000 + 1;
			mp[{x, y}] = w;
		}
		if(q == 2) {
			scanf("%d %d", &x, &y);
			x = (x + lastans) % 6000 + 1;
			y = (y + lastans) % 6000 + 1;
			mp[{x, y}] = 0;
		}
		if(q == 3) {
			scanf("%d %d %d %d", &x, &y, &k, &w);
			x = (x + lastans) % 6000 + 1;
			y = (y + lastans) % 6000 + 1;
			for(auto g : v[k]) {
				if(g.fi == 0 && g.se == 0) {
					if(mp[{x, y}] != 0)
						mp[{x, y}] += w;
				}
				else if(g.fi == 0) {
					if(mp[{x, y + g.se}] != 0)
						mp[{x, y + g.se}] += w;
					if(mp[{x, y - g.se}] != 0)
						mp[{x, y - g.se}] += w;
				}
				else if(g.se == 0) {
					if(mp[{x + g.fi, y}] != 0)
						mp[{x + g.fi, y}] += w;
					if(mp[{x - g.fi, y}] != 0)
						mp[{x - g.fi, y}] += w;
				}				
				else {
					if(mp[{x + g.fi, y + g.se}] != 0)
						mp[{x + g.fi, y + g.se}] += w;
					if(mp[{x - g.fi, y - g.se}] != 0)
						mp[{x - g.fi, y - g.se}] += w;	
					if(mp[{x + g.fi, y - g.se}] != 0)
						mp[{x + g.fi, y - g.se}] += w;
					if(mp[{x - g.fi, y + g.se}] != 0)
						mp[{x - g.fi, y + g.se}] += w;				
				}
			}
		}
		if(q == 4) {
			scanf("%d %d %d", &x, &y, &k);
			x = (x + lastans) % 6000 + 1;
			y = (y + lastans) % 6000 + 1;
			ll sum = 0;
			for(auto g : v[k]) {
				if(g.fi == 0 && g.se == 0) {
					if(mp[{x, y}] != 0)
						sum += mp[{x, y}];
				}
				else if(g.fi == 0) {
					if(mp[{x, y + g.se}] != 0)
						sum += mp[{x, y + g.se}];
					if(mp[{x, y - g.se}] != 0)
						sum += mp[{x, y - g.se}];
				}
				else if(g.se == 0) {
					if(mp[{x + g.fi, y}] != 0)
						sum += mp[{x + g.fi, y}];
					if(mp[{x - g.fi, y}] != 0)
						sum += mp[{x - g.fi, y}];
				}				
				else {
					if(mp[{x + g.fi, y + g.se}] != 0)
						sum += mp[{x + g.fi, y + g.se}];
					if(mp[{x - g.fi, y - g.se}] != 0)
						sum += mp[{x - g.fi, y - g.se}];	
					if(mp[{x + g.fi, y - g.se}] != 0)
						sum += mp[{x + g.fi, y - g.se}];
					if(mp[{x - g.fi, y + g.se}] != 0)
						sum += mp[{x - g.fi, y + g.se}];				
				}
			}
			printf("%lld\n", sum);
			lastans = sum;
		}
	}
}

int main () {
	init();
	int t;
	scanf("%d", &t);
	while(t--)
		run();
	return 0;
}

J. How Much Memory Your Code Is Using?

solved by Tryna & Sstee1XD.0:26(+1)

题意： 给出一系列变量的定义，求占用的多少KBKB的空间。

题解： 签到题，直接按照题意模拟就好了。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n, cnt;
string s;
void run () {
	cin>>n;
	int sum = 0;
	cnt++;
	getchar();
	while(n--) {
		getline(cin, s);
		int base = 16;
		if(s.substr(0, 4) == "char" || s.substr(0, 4) == "bool") 
			base = 1;
		else if(s.substr(0, 3) == "int" || s.substr(0, 5) == "float")
			base = 4;
		else if(s.substr(0, 9) == "long long" || s.substr(0, 6) == "double")
			base = 8;
		int num = 0;
		for(int i = 0; i < s.size(); i++) {
			if(s[i] == '[') {
				i++;
				while(s[i] != ']') {
					num = num * 10 + (s[i] - '0');
					i++;  
				}
				break;
			}
		}
		if(num == 0) num = 1;
		sum += base * num;
	}
	printf("Case #%d: ", cnt);
	printf("%d\n", (sum + 1023) / 1024);
}

int main () {
	int t = 1;
	cin>>t;
	while(t--)
		run();
	return 0;
}

K - Let the Flames Begin

solved by Tryna.(-)

题意 本题是一个约瑟夫环的变形，一般的约瑟夫环是求最后一个出局的人的位置，此题是求第mm个出局的人的位置, 这也很容易由一个递推式得到。如果不了解约瑟夫环，可以先去看看这篇文章：约瑟夫环。

题解： 所以此题的递推式是：$$P[n][m] = (P[n - 1][m - 1] + k)%n$$
但是这题数据范围很大，但又有min(m,k)≤2e6min(m,k)\leq 2e^6，这就意味着mm和kk必定有一个数字不会很大，所以根据这个分类即可。

  • 当mm小时，暴力就可以。
  • 当kk小时，我们可以将加法转化为减法，因为kk很小，所以我们需要加一定的次数才能取模，所以我们需要把那个次数xx求出来，这样就可以大大降低时间复杂度。
AC代码 
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define LL __int128;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define PAUSE system("pause");
const double eps = 1e-8;
const int maxn = 1e4 + 10;
const int mod = 998244353;
ll n, m, k, cas;
void solve() {
	scanf("%lld %lld %lld", &n, &m, &k);
	printf("Case #%lld: ", ++cas);
	if(k == 1)
		printf("%lld\n", m);
	else if(m <= k) {
		ll ans = (k - 1) % (n - m + 1);
		for(ll i = n - m + 2; i <= n; i++) {
			ans = (ans + k) % i;
		}
		printf("%lld\n", ans + 1);
	}
	else{
		ll cnt = (n - m + 1);
		ll ans = (k - 1) % cnt;
		ll now = 1;
		while(now < m) {
			if(ans + k >= cnt + 1) {
				cnt++;
				ans = (ans + k) % cnt;
				now++;
				continue;
			}
			ll x = (cnt - ans - 1) / (k - 1);
			x = min(x, m - now);
			now += x;
			cnt += x;
			ans += k * x;
		}
		printf("%lld\n", ans + 1);
	}
}
int main() {
	int t = 1;
	scanf("%d", &t);
	// cin>>t;
	while(t--)
		solve();
	return 0;
}

L. Machining Disc Rotors

solved by Tryna.(-)

题意： 给出一个大圆，然后再给出若干个小圆，这些小圆切割了大圆，求被切割后的几何图形的直径。

题解： 想法很简单，如果被切割后仍存在大圆直径，那么答案就是大圆直径，否则就是最远的两点距离。
对于如何判断是否存在直径可以枚举每个端点，然后求它关于原点的对称点，如果不在任何一个圆内，那么直径存在。
注意其他圆与大圆无交点时答案就是直径

AC代码 
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define LL __int128;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define PAUSE system("pause");
const double eps = 1e-8;
const int maxn = 2e2 + 10;
const int mod = 998244353;
int num;
int sgn(double x) {
	if(fabs(x) < eps) return 0;
	if(x < 0) return -1;
	else return 1;
}
struct Point{
	double x, y;
	Point(){}
	Point(double _x, double _y) {
		x = _x;
		y = _y;
	}
	Point operator -(const Point &b) const{
		return Point(x - b.x, y - b.y);
	}
	Point operator +(const Point &b) const{
		return Point(x + b.x, y + b.y);
	}
	double distance(Point p) {
		return hypot(x - p.x, y - p.y);
	}
	double len() {
		return hypot(x, y);
	}
	Point trunc(double r) {
		double l = len();
		if(!sgn(l)) return *this;
		r /= l;
		return Point(x * r, y * r);
	}
	Point rotleft() {
		return Point(-y, x);
	}
	Point rotright() {
		return Point(y, -x);
	}
}P[maxn];
struct circle{
	Point p;
	double r;
	circle(){}
	circle(Point _p, double _r) {
		p = _p;
		r = _r;
	}
	int relation(Point b) {
		double dst = b.distance(p);
		if(sgn(dst - r) < 0) return 2;
		else if(sgn(dst - r) == 0) return 1;
		return 0;
	}
	int relationcircle(circle v) {
		double d = p.distance(v.p);
		if(sgn(d - r - v.r) > 0) return 5;
		if(sgn(d - r - v.r) == 0) return 4;
		double l = fabs(r - v.r);
		if(sgn(d - r - v.r) < 0 && sgn(d - l) > 0) return 3;
		if(sgn(d - l) == 0) return 2;
		if(sgn(d - l) < 0) return 1;
	}
	void pointcrosscircle(circle v) {
		int rel = relationcircle(v);
		if(rel == 1 || rel == 5) return ;
		double d = p.distance(v.p);
		double l = (d * d + r * r - v.r * v.r) / (2 * d);
		double h = sqrt(r * r - l * l);
		Point tmp = p + (v.p - p).trunc(l);
		if(rel == 2 || rel == 4) return ;
		P[++num] = tmp + ((v.p - p).rotleft().trunc(h));
		P[++num] = tmp + ((v.p - p).rotright().trunc(h));
	}
}C, c[maxn];
int n, cas;
void solve() {
	scanf("%d %lf", &n, &C.r);
	C = circle(Point(0, 0), C.r);
	num = 0;
	for(int i = 1; i <= n; i++) {
		double x, y;
		scanf("%lf %lf %lf", &x, &y, &c[i].r);
		c[i] = circle(Point(x, y), c[i].r);
		C.pointcrosscircle(c[i]);
	}
	printf("Case #%d: ", ++cas);
	// for(int i = 1; i <= num; i++) 
	// 	printf("*%lf %lf\n", P[i].x, P[i].y);
	if(num == 0) {
		printf("%.15f\n", C.r * 2.0);
		return ;
	}
	int flag = 0;
	double ans = 0;
	for(int i = 1; i <= num; i++) {
		flag = 0;
		Point pos = Point(-P[i].x, -P[i].y);
		for(int j = 1; j <= n; j++) {
			if(c[j].relation(pos) == 2) {
				flag = 1;
				break;
			}
		}
		if(flag == 0) {
			printf("%.15f\n", C.r * 2.0);
			return ;
		}
	}
	for(int i = 1; i < num; i++) {
		for(int j = i + 1; j <= num; j++) {
			ans = max(ans, P[i].distance(P[j]));
		}
	}
	printf("%.15f\n", ans);
}
int main() {
	int t = 1;
	scanf("%d", &t);
	// cin>>t;
	while(t--)
		solve();
	return 0;
}
文章目录
  1. C. Insertion Sort
  2. G. Best ACMer Solves the Hardest Problem
  3. J. How Much Memory Your Code Is Using?
  4. K - Let the Flames Begin
  5. L. Machining Disc Rotors
|