https://codeforces.com/contest/1933

Codeforces Round 929 div 3

A. Turtle Puzzle: Rearrange and Negate

绝对值求和即可，一眼题

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
#include<iostream>
#include<algorithm>
#include<math.h>
//#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 100;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		ll ans=0;
		while (n--)
		{
			int x;
			cin >> x;
			ans += abs(x);
		}
		cout << ans << '\n';
	}

	return 0;
}



B. Turtle Math: Fast Three Task

你可以进行下列两个操作无限次。

1、选择一个数，删掉他，数组总长度-1（没数的时候不能用）

2、选择一个数，加1

问最少多少次操作，可以让数组的和是3的倍数（或者是0，有特殊情况）

本题有两个操作，一个是加1，一个是删除数字，问什么时候可以整除

求个和，如果是3的倍数就不用了，直接输出0

如果是取余为1，记录一下

2也记录一下

如果这个时候和取余为1，很显然我们找到一个取余1的删除即可

如果为2，永远+1，永远1次

剩下的都是2次

总结一下：

如果是0：那么不需要操作就可以得到答案，输出0。

如果是1：最少需要2步，即让某个数加两次1。考虑能不能有更优解，即1步。找到一个数，对3余数为1，存在的话就只需要1步。

如果是2：最少需要1步，操作1和操作2不用想了，反正都是1步。输出1就行

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<iostream>
#include<algorithm>
#include<math.h>
//#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 100;
int a[N];
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int sum = 0;
		int cnt1 = 0;
		int cnt2 = 0;
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			sum += a[i];
			if (a[i] % 3 == 1)
			{
				cnt1++;
			}
			else
			{
				cnt2++;
			}

		}
		int x = sum % 3;
		if (sum % 3 == 0)
		{
			cout << 0<<'\n';
		}
		else if (x == 1 && cnt1)
		{
			cout << 1 << '\n';
		}
		else if (x == 2)
		{
			cout << 1 << '\n';
		}
		else 
		{
			cout << 2 << '\n';
		}


	}

	return 0;
}

C. Turtle Fingers: Count the Values of k

（太久没打cf脑子退化了，wa了不知道多少次，才知道是没开longlong)

本题可以暴力

但是折磨我的点是去重

于是用set

将能整除a的倍数都放进去

b也是

然后暴力枚举，再放进去一个集合

并输出最后的大小

从头到尾都保证了本题的正确性

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
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
//#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//取消同步流
	int t;
	cin >> t;
	while (t--)
	{
		ll a, b, c;
		cin >> a >> b >> c;
		if (c == 1)
		{
			cout << 1 << '\n';
		}
		else
		{
			ll x = a;
			ll y = b;
			set<ll>q;
			set<ll>p;
			set<ll>w;
			q.insert(1ll);
			p.insert(1ll);
			while (x <= c)
			{
				if(c%x==0)
				q.insert(x);
				x *= a;
			}
			while (y <= c)
			{
				if(c%y==0)
				p.insert(y);
				y *= b;
			}
			for (set<long long>::iterator i = q.begin(); i != q.end(); i++)
			{
				for (set<long long>::iterator j = p.begin(); j != p.end(); j++)
				{
					ll sum = (*i) * (*j);
					if (c % sum == 0)
					{
						w.insert(c /sum);
					}
				}
			}
			cout << w.size() << '\n';
		}
	}
	return 0;
}



D. Turtle Tenacity: Continual Mods

给你一个序列A，选出任意一个排列，要求这个序列连续取模过去最终不等于0。

本题考虑贪心算法

由于是任意的，不需要找到该序列，因此只需要判断是否存在即可

有一条性质：

小的数字对大的数字取模会得到小的数字，因此我们考虑排序

既然是贪心，有时候避免不了会用到排序算法

从小到大排序即可

如果最小值只有一个直接输出Yes，我们已经在123456知道了这样的正确性

否则，如果最小值有多个，康康能不能变出一个更小的数字，

用最后的数字对最小数字取模即可，接下来看代码：

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
#include<iostream>
#include<map>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
map<int, int>a;//记录次数
int b[N];//记录数组
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		int minn = 1e9;
		int flag = 0;
		for (int i = 1; i <= n; i++)
		{
			int x;
			cin >> x;
			a[x]++;
			if (x < minn)
			{
				minn = x;
			}
			b[i] = x;
		}
		sort(b + 1, b + 1 + n);
		if (a[minn] == 1)
		{
			cout << "yes" << '\n';
		}
        //1次跳出
		else
		{
			for (int i = n; b[i] != minn; i--)
			{
				int x = b[i] % minn;
				if (x != 0 &&x < minn)
				{
					cout << "YES" << '\n';//遍历找更小
					flag = 1;
					break;
				}
			}
		}
		if (!flag && a[minn] != 1)//都没有就NO
		{
			cout << "NO" << '\n';
		}
		a.clear();//多测记得清零
		memset(b, 0, sizeof(b));
	}
}


E. Turtle vs. Rabbit Race: Optimal Trainings

lsaac喜欢跑步。

他跑过第一个阶段会得到u的表现分。

他跑过第二个阶段会得到u-1的表现分。

他跑过第三个阶段会得到u-2的表现分。

......

他跑过第k个阶段会得到u+1-k的表现分。

现在有数组a[n]，数组中包含阶段数量，如跑过a[1]，若a[1]=3，则直接获得3个阶段。

给你数组起始点L，和表现分开头u，问你总表现分最大的情况下，数组结束点R最小是多少。

本题知识点三分

这是一个图，就是本题的图罢

因为本题的单调性是这样的

因为随着我们越来越多，他肯定是先增加后减少的

不像二分，是一直增加，一直减少

我们的目的是找到那个中间的节点

具体我们需要3个判断

l,mid,mid-1

如果mid大于l，但究竟是左边的那种大还是右边的那种大呢，看Mid-1,如果mid-1比mid小，就是左边的大

l要变大

如果是右边就r变小，就这样，可以写代码了

img 
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
#include<iostream>
#include<map>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 100;
ll a[N];
ll sum[N];
ll  h, u;
ll qiuhe(int k) 
{
	return ((u + (u + 1 - k)) )*k / 2;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			sum[i] = sum[i - 1] + a[i];
		}
		//前缀和优化
		int q;
		cin >> q;
		while (q--)
		{
			cin >> h >> u;
			int l = h;
			int r = n;
			while (l  < r)
			{
				int mid = (l + r) / 2;
				ll ans_mid = qiuhe(sum[mid] - sum[h - 1]);
				ll ans_l = qiuhe(sum[l] - sum[h - 1]);
				ll ans_hmid=qiuhe(sum[mid - 1] - sum[h - 1]);
				if (ans_mid > ans_hmid && ans_mid > ans_l)
				{
					l = mid;
				}
				else
				{
					r = mid;
				}
			}
			if (qiuhe(sum[l + 2] - sum[h - 1]) > qiuhe(sum[l] - sum[h - 1])&&l+2<=n)
			{
				l += 2;
			}
			else if (qiuhe(sum[l + 1] - sum[h - 1]) > qiuhe(sum[l] - sum[h - 1])&&l+1<=n)
			{
				l += 1;
			}
			cout << l << ' ';
		}
		cout << '\n';
		memset(sum, 0, sizeof sum);
	}
}