SDUT 2021 Spring Individual Contest(for 20) - 19

题目链接：A - Rooms and Passages

题意：

一条路上有nn个房间，每个相邻房间之间有加密设备，初始时有所有密码，如果a[i]>0a[i]>0，只有拥有房间密码才能通过；如果a[i]<0a[i]<0，可以通过，但密码∣a[i]∣|a[i]|失效。从0−−n−10--n-1个房间出发，计算出能通过的最多房间数。

思路：

通过符号为负的房间后，遇到的第一个对应权值的正号房间会停止，因为密码已经失效。

当满足此条件时，之前所有的起始位置都会在这个点停下，这样就可以算出之前所有点对应的可走的最大房间数。

结束位置nn可能不满足这个条件，但相应的，此时已经没有条件限制，可以直接求出上个满足条件的位置到结束位置之间各点的最大房间数。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include <cstring>
using namespace std;
const int N = 5e5 + 7;
int v[N],a[N];
int main()
{
	int n ;
	cin >> n;
	int idx = 1;
	for (int i = 1; i <= n; i ++ ){
		cin >> a[i];
		if (a[i] < 0) v[-a[i]]++;
		if (a[i] > 0 && v[a[i]]){
			while (v[a[i]]){
				cout << i - idx << ' ';
				if (a[idx] < 0) v[-a[idx]]--;
				idx ++;
			}
		}
	}
	for (int i = idx; i <= n ; i ++) cout << n + 1 -i  <<' ';
}

题目链接：B - Rearrange Columns

题意：

给出一个2∗n2*n的矩阵，询问所有的#是否能通过操作qq联通。

qq：每次可以移动一列。

思路：

三种情况：

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
39
40
41
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,m;
const int N = 1e7 + 7;
void swapp(ll x,ll y){
	ll t = x; x = y; y = t;
}
bool v[N];int L[1000],R[1000],MID[1000];
int main(){
	string s1,s2;
	getline(cin,s1);
	getline(cin,s2);
	
	int l = 0, r = 0 ,mid= 0;
	for ( int i = 0; s1[i]; i ++) {
		if (s1[i] == '#' && s2[i] == '.') L[l++] = i;
		else if (s1[i] == '.' && s2[i] == '#') R[r++] = i;
		else if (s1[i] == '#' && s2[i] == '#') MID[mid++] = i;
	}
	n = s1.size();
	//cout << l << mid << r << endl;
	if (mid > 0 || l == 0 || r == 0 ) {
		puts("YES");
		for  (int i = 0 ; i < l ; i++) cout << s1[L[i]] ;
		for (int i = 0 ; i < mid; i ++) cout << s1[MID[i]];
		for ( int i = 0 ; i < r; i ++) cout << s1[R[i]];
		for (int i = l + mid + r; i < n ;i ++) cout <<'.';
		puts("");
		for  (int i = 0 ; i < l ; i++) cout << s2[L[i]] ;
		for (int i = 0 ; i < mid; i ++) cout << s2[MID[i]];
		for ( int i = 0 ; i < r; i ++) cout << s2[R[i]];
		for (int i = l + mid + r; i < n ;i ++) cout << '.';
		puts("");
	}else puts("NO");
	return 0;

题目链接：C - Jumps on a Circle

题意：

给出一个由pp个点组成的环，编号从0−−n−10--n-1，初始位置为00，此后第ii步会向后跳i(i=1,2,3,4……)i(i = 1 ,2 ,3,4…… )个单位长度，跳的步数为nn，问走过多少个不同的点。

思路：

nn的数据范围为1e181e18，应该是找规律。打表发现当n==pn==p或更小时，答案就不变了。

而nn的范围只有1e71e7，最多遍历到nn即可。

代码：

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
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,m;
const int N = 1e7 + 7;

void swapp(ll x,ll y){
	ll t = x; x = y; y = t;
}
ll minn(ll a,ll b){
	return a < b ? a : b;
}
bool v[N];
int main(){
	cin >> n >> m;
	ll cnt = 1;
	ll ans = 1;
	ll idx = 2;
	memset(v,0,sizeof v);
	v[0] = 1;
	for (ll i = 1; cnt++ <= minn(m,n); ){
		if (i >= n) i %= n;
		if(!v[i]) {
			v[i] = 1;ans++;
		}
		i += idx++;
	}
	cout << ans << '\n';
	return 0;
}

题目链接： L - Inscribed Circle

题意：

给出两个相交的圆，求出在两圆相交之间的且与两圆相切的圆。

思路：

设已知圆半径为r1,r2r1,r2，所求圆为rr

则r=(r1+r2−两圆心之间的距离)/2r=(r1+r2-两圆心之间的距离)/2

所求圆圆心(x,y)(x,y)可以通过所求圆与另外两圆圆心之间的距离比值求出。

代码：

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
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
typedef double ff;
void swapp(ff x,ff y){
	ff t = x; x = y; y = t;
}
ff minn(ff a,ff b){
	return a < b ? a : b;
}
int main(){
	ff x1,y1,r1,x2,y2,r2,x,y,r;
	cin >> x1>>y1>>r1>>x2>>y2>>r2;
	ff L = sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1));
	r =(r1 + r2 - L) / 2;
	ff R1 = fabs(r-r1), R2 = fabs(r-r2);
	if (R1 > R2) swapp(R1,R2);
	ff k = R1 / (R2 + R1);
	if (x1 > x2)x = x1 - fabs(x1-x2) *k;
	else x = x1 + fabs(x1-x2)*k;
	if (y1 > y2)
	y = y1 - fabs(y1-y2)*k;
	else y = y1 + fabs(y1-y2)  *k;
	printf("%.15lf %.15lf %.15lf\n",x,y,r);
	return 0;
}