CodeForces 1650

A - Deletions of Two Adjacent Letters

思路：给定一个字符串，进行任意次以下操作：选择字符串中的任意两个相邻字母 s并将它们从字符串中删除，使过程以长度为 1、由字母 c 组成的字符串结束。只需要判断字符串中是否存在这个字符，并且该字符的下表是偶数即可

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
#include<iostream>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int flag = 0;
		string s;
		cin >> s;
		char c;
		cin >> c;
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == c&&i%2==0)
			{
				flag = 1;
				break;
			}
		}
		if (flag)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}

B - DIV + MOD

思路：给定一个区间，输出区段上函数的最大值。比较r- r % a - 1和r带入函数的结果，输出较大值即可，注意r- r % a - 1的值不能小于l。

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
#include<iostream>
using namespace std;

int fun(int x, int p)
{
	return x / p + x % p;
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int l, r, a;
		cin >> l >> r >> a;

		int e1 = fun(r, a);
		int f = r- r % a - 1;
		int e2 = 0;
		if(f>=l)
			e2 = fun(f, a);

		cout << max(e1, e2) << endl;
	}
	return 0;
}

C - Weight of the System of Nested Segments**

思路：使用结构体存放一个点的信息，包括下标，索引，权值；对权值升序排序，找到权值最小的几个。使用pair数组存放最小的几个的下标和索引，对下标再进行排序，输出对应索引即可

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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2e5 + 10;

struct trip{
    int _a,_b,_idx;//表示下标，权值，索引
    //对权值排序
    bool operator<(const trip&w)const{
        return _b<w._b;
    }
}trip[N];

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n, m;
		cin >> n >> m;
		for(int i=0;i<m;i++)
		{
			int a, b;
			cin >> a >> b;
			trip[i]={a,b,i+1};
		}
		sort(trip, trip + m);
		long long ans = 0;
		for (int i = 0; i < 2*n; i++)
		{
			ans += trip[i]._b;
		}
		
		cout<<ans<<endl;
		vector<pair<int,int>>ma;
		for (int i = 0; i < 2 * n; i++)
		{
			ma.push_back({trip[i]._a,trip[i]._idx});
		}
		sort(ma.begin(),ma.end());
		for(int i=0;i<n;i++)
		    cout<<ma[i].second<<" "<<ma[2*n-i-1].second<<endl;
		   
	}
	return 0;
}

D - Twist the Permutation

思路：将数字向左移动，回到1，2，3，4……的状态就可，可以看出，将第i个数向左移动时，前i个数都要跟着移动，i之后的数就不会移动。所以我们从大到小枚举，模拟即可

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<iostream>
using namespace std;
const int N = 2e3 + 10;
int a[N];
int f[N];

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			int x; cin >> x;
			a[x] = i;
		}
		for (int i = n; i >= 1; i--)
		{
			int tt = a[i];
			int yy = a[i] % i;
			f[i] = yy;
			for (int j = 1; j <= i; j++)
			{
				if (a[j] - yy >= 0)
					a[j] = a[j] - yy;
				else
					a[j] = ( a[j] - yy + i) % n;
			}
		}
		for (int i = 1; i <= n; i++)
			cout << f[i] << " ";
		cout << endl;
	}

	return 0;
}

谢谢观看