greedy

贪心的题目比较杂，主要是要明确贪心什么，要什么越大越好，要什么越小越好。

做得算是比之前的轻松一些，但是容易陷阱去，对一个问题写着写着发现有细节没考虑到，就急了，直接加进去，最后发现代码一团糟，思路也不清楚，还是应该想好框架，考虑完细节处理再动手。

  • 素数数列构造
  • 大数模板
  • 二分
  • 二次分配
  • 因数分解
  • 树形dp

A. Prefix Sum Primes

 

Day2的原题，有其它做法。

一个数列[2,1,2,2,2,······,2,1,1,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
#include<iostream>
#include<map>
using namespace std;
map<int,int>mp;
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		mp[a]++;
	}
	if (n == 1) {
		if (mp[1] != 0)cout << 1;
		else cout << 2;
	}
	else if (n == 2) {
		if (mp[2] != 0)cout << 2<<' ',mp[2]--;
		if (mp[1] != 0)cout << 1<<' ',mp[1]--;
		if (mp[2] != 0)cout << 2<<' ',mp[2]--;
		if(mp[1]!=0)  cout << 1<<' ',mp[1]--;
	}
	else {
		if (mp[2] != 0) {
			cout << 2<<' ';
			mp[2]--;
		}
		if (mp[1] != 0) {
			cout << 1<<' ';
			mp[1]--;
		}
		while (mp[2] > 0) {
			cout << 2<<' ';
			mp[2]--;
		}
		while (mp[1] > 0) {
			cout << 1<<' ';
			mp[1]--;
		}
	}
	return 0;
}

 

B. Number Circle

 

先从小到大排序，一个隔一个地挑出来，分到左右两边半圆，靠近起点的小，靠近终点的大。

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
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
int b[maxn];
int c[maxn];
bool check(int i)
{
	if (a[i] < a[i - 1] + a[i + 1]) return true;
	else return false;
}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	int b1 = 0, c1 = 0;
	for (int i = 0; i < n; i++)
	{
		if (i % 2 == 0) c[c1++] = a[i];
		else b[b1++] = a[i];
	}
	for (int i = 0; i < c1; i++)
	{
		a[i] = c[i];
	}
	for (int i = c1; i < n; i++)
	{
		a[i] = b[--b1];
	}
	bool flag = true;
	for (int i = 1; i < n - 1; i++)
	{
		if (!check(i)) flag = false;
	}
	if (!flag || a[n - 1] >= a[0] + a[n - 2] || a[0] >= a[n - 1] + a[1]) cout << "NO";
	else
	{
		cout << "YES" << endl;
		for (int i = 0; i < n; i++)
		{
			cout << a[i] << " ";
		}
	}
	return 0;
}

 

C. Split a Number

 

用大数模板就过了，分奇偶讨论，偶数时从中间找到两边不为零的位置，作为后半部分的开头数字，比较两种的大小；奇数时分中间是否为零，不为零则mid和mid+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
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include <bits/stdc++.h>
using namespace std;
 
struct BigInteger
{
	static const int BASE = 100000000; 
	static const int WIDTH = 8;       
	bool sign;                       
	size_t length;                   
	vector<int> num;                 

	BigInteger(long long x = 0) { *this = x; }
	BigInteger(const string &x) { *this = x; }
	BigInteger(const BigInteger &x) { *this = x; }
	BigInteger &operator=(long long x)
	{
		num.clear();
		if (x >= 0)
		{
			sign = true;
		}
		else
		{
			sign = false;
			x = -x;
		}
		do
		{
			num.push_back(x % BASE);
			x /= BASE;
		} while (x > 0);
		cutLeadingZero();
		return *this;
	}
	BigInteger &operator=(const string &str)
	{
		num.clear();
		sign = (str[0] != '-');
		int x, len = (str.size() - 1 - (!sign)) / WIDTH + 1;
		for (int i = 0; i < len; i++)
		{
			int End = str.size() - i * WIDTH;
			int start = max((int)(!sign), End - WIDTH);
			sscanf(str.substr(start, End - start).c_str(), "%d", &x);
			num.push_back(x);
		}
		cutLeadingZero();
		return *this;
	}
	BigInteger &operator=(const BigInteger &tmp)
	{
		num = tmp.num;
		sign = tmp.sign;
		length = tmp.length;
		return *this;
	}
	const BigInteger &operator+() const { return *this; }
	BigInteger operator+(const BigInteger &b) const
	{
		if (!b.sign)
		{
			return *this - (-b);
		}
		if (!sign)
		{
			return b - (-*this);
		}
		BigInteger ans;
		ans.num.clear();
		for (int i = 0, g = 0;; i++)
		{
			if (g == 0 && i >= num.size() && i >= b.num.size())
				break;
			int x = g;
			if (i < num.size())
				x += num[i];
			if (i < b.num.size())
				x += b.num[i];
			ans.num.push_back(x % BASE);
			g = x / BASE;
		}
		ans.cutLeadingZero();
		return ans;
	}
	
	BigInteger &operator+=(const BigInteger &b)
	{
		*this = *this + b;
		return *this;
	}
	
	bool operator<(const BigInteger &b) const
	{
		if (sign != b.sign)
		{
			return !sign;
		}
		else if (!sign && !b.sign)
		{
			return -b < -*this;
		}
		if (num.size() != b.num.size())
			return num.size() < b.num.size();
		for (int i = num.size() - 1; i >= 0; i--)
			if (num[i] != b.num[i])
				return num[i] < b.num[i];
		return false;
	}
	bool operator>(const BigInteger &b) const { return b < *this; } 
	bool operator<=(const BigInteger &b) const { return !(b < *this); }
	bool operator>=(const BigInteger &b) const { return !(*this < b); } 
	bool operator!=(const BigInteger &b) const { return b < *this || *this < b; } 
	bool operator==(const BigInteger &b) const { return !(b < *this) && !(*this < b); }
	friend ostream &operator<<(ostream &out, const BigInteger &x)
	{
		if (!x.sign)
			out << '-';
		out << x.num.back();
		for (int i = x.num.size() - 2; i >= 0; i--)
		{
			char buf[10];
			sprintf(buf, "%08d", x.num[i]);
			for (int j = 0; j < strlen(buf); j++)
				out << buf[j];
		}
		return out;
	}
	friend istream &operator>>(istream &in, BigInteger &x)
	{
		string str;
		in >> str;
		size_t len = str.size();
		int start = 0;
		if (str[0] == '-')
			start = 1;
		if (str[start] == '\0')
			return in;
		for (int i = start; i < len; i++)
		{
			if (str[i] < '0' || str[i] > '9')
				return in;
		}
		x.sign = !start;
		x = str.c_str();
		return in;
	}
};
 
int main()
{	
	int l;
	cin >> l;
	string s;
	cin >> s;
	if (l % 2 == 0) {
		int md = l / 2;
		int md1 = md, md2 = md;
		while (s[md1] == '0'&&md1 > 0) {
			md1--;
		}
		while (s[md2] == '0'&&md2 < l - 1) {
			md2++;
		}
		if (md1 == 0) {
			BigInteger ans2 = BigInteger{ s.substr(0,md2) }+BigInteger{ s.substr(md2) };
			cout << ans2;
		}
		else if (md2 == l - 1) {
			BigInteger ans1 = BigInteger{ s.substr(0,md1) }+BigInteger{ s.substr(md1) };
			cout << ans1;
		}
		else {
			BigInteger ans1 = BigInteger{ s.substr(0,md1) }+BigInteger{ s.substr(md1) };
			BigInteger ans2 = BigInteger{ s.substr(0,md2) }+BigInteger{ s.substr(md2) };
			cout << min(ans1, ans2);
		}
	}
	else {
		int md = l / 2;
		if (s[md] != '0') {
			BigInteger ans1 = BigInteger{ s.substr(0,md) }+BigInteger{ s.substr(md) };
			if (s[md + 1] != 0) {
				ans1 = min(ans1, BigInteger{ s.substr(0,md + 1) }+BigInteger{ s.substr(md + 1) });
			}
			cout << ans1;
		}
		else {
			int md1 = md, md2 = md;
			while (s[md1] == '0'&&md1 > 0) {
				md1--;
			}
			while (s[md2] == '0'&&md2 < l - 1) {
				md2++;
			}
			if (md1 == 0) {
				BigInteger ans2 = BigInteger{ s.substr(0,md2) }+BigInteger{ s.substr(md2) };
				cout << ans2;
			}
			else if (md2 == l - 1) {
				BigInteger ans1 = BigInteger{ s.substr(0,md1) }+BigInteger{ s.substr(md1) };
				cout << ans1;
			}
			else {
				BigInteger ans1 = BigInteger{ s.substr(0,md1) }+BigInteger{ s.substr(md1) };
				BigInteger ans2 = BigInteger{ s.substr(0,md2) }+BigInteger{ s.substr(md2) };
				cout << min(ans1, ans2);
			}
		}
	}
	return 0;
}

 

D. Color the Fence

 

要尽量用完颜料并写出多的数字，则先写用颜料少的，以先占据尽量多的数位，在从开头起，尝试把该数位上的数字变大，若颜料再也不够了，则得到最终答案。

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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
vector<pii>vc;
vector<int>ans;
int a[10];
bool cmp(pii a, pii b) {
	if (a.second == b.second)return a.first > b.first;
	else return a.second < b.second;
}
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= 9; i++) {
		int tp;
		cin >> tp;
		a[i] = tp;
		vc.push_back(pii(i, tp));
	}
	sort(vc.begin(), vc.end(), cmp);
	if (n < vc[0].second) {
		cout << -1;
		return 0;
	}
	int at = 0;
	while (n >= vc[at].second) {
		int t = n / vc[at].second;
		for (int i = 0; i < t; i++) {
			ans.push_back(vc[at].first);
		}
		n = n % (vc[at].second);
		at++;
	}
	int k = 9;
	for (int i = 0; i < ans.size(); i++) {
		for (int j = 9; j >= 1; j--) {
			if (a[j] - a[ans[i]] <= n) {
				n -= (a[j] - a[ans[i]]);
				ans[i] = j;
				break;
			}
		}
	}
	for (auto c : ans)
		cout << c;
	//cout<<endl << n;
	return 0;
}

 

E. Increasing by Modulo

 

我们要尽量使每个数字最小，留给后面数字的空间就越大

若已知要修改k次，则对每个数字有最多k次操作机会（不需要全部用完），在k次中，若始终无法使它更小，则之后数字要大于等于它，否则是最小值最小，这可以确保我们每经过一位数，它之前都已经达到最佳，若有一位数字无论用多少次操作都无法大于记录的最小值，则k次不够用，要增加次数。

本题关键在于贪心，使得在检查每个数时，确保之前已经最佳，即这个数要大于等于的数是k次操作中可以做到的最小值。

接下来就是二分找到最小的k。

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
#include<iostream>
using namespace std;
const int N = 3e5 + 5;
int n, m, a[N];
bool check(int k) {
	int now = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i] > now) {
			if (a[i]+k>=m && (a[i] + k) % m>=now) {
				;
			}
			else
				now = a[i];
		}
		else if (a[i] < now) {
			if (a[i] + k   < now) {
				return false;
			}
		}
	}
	return true;
}
int main() {
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int st = 0, ed = m;
	while (st<=ed) {
		int mid = (st + ed) / 2;
		if (check(mid))
			ed = mid-1;
		else st = mid+1;
	}
	cout << st;
	return 0;
}

 

F. Vus the Cossack and Numbers

 

先对每个数只取整数部分，即正数向下取整，负数向上取整，只需要取int就可做到。同时记录舍去的小数部分，由于所有数的整数部分+小数部分=0，所以小数部分的和一定是整数，讨论该和的正负，由于正数向下取整，因此每个正数都有+1的空间，变为原数向上取整，所以若小数和为正数，则平分到正数上；同理，负数则平分到负数上。

存在精度问题及对0的处理问题。

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
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
int n;
double rest;
double a[100005];
vector<int>vc;
bool cmp(int a, int b) {
	return a > b;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		double tp;
		cin >> tp;
		a[i] = tp;
		int ac = tp;
		vc.push_back(tp);
		rest += (tp - ac);
	}
	if (fabs(rest) < 1e-6)rest = 0;
	if (rest > 0) {
		for (int i = 0; i < n; i++) {
			if (a[i] > 0&&((int)a[i]-a[i]!=0)) {
				vc[i]++;
				rest--;
			}
			if (fabs(rest) < 1e-6)break;
		}
	}
	else if(rest<0){
		for (int i = 0; i < n; i++) {
			if (a[i] < 0&& ((int)a[i] - a[i] != 0)) {
				vc[i]--;
				rest++;
			}
			if (fabs(rest) < 1e-6)break;
		}
	}
	for (auto c : vc) {
		cout << c << endl;
	}
	return 0;
}

 

G. Nick and Array

 

一种特殊的操作，a->-a-1，要使最终所有元素乘积最大，注意到这个操作可以使正数变负数，且绝对值变大，而对负数使用绝对值会变小，因此首先将所有数都经此操作变为负数，若元素个数为奇数，说明不得已要变出一个正数，我们便绝对值最小的那个，使影响最小。

若绝对值最小的是-1，注意所有元素都已经经由操作变为负数，这说明数组中只有-1。而-1是只能由零变来或者本来就是-1，这说明我们不论如何操作，最终乘积只能得到0或-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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
int n;
vector<pii> vc;
bool cmp1(pii a, pii b) {
	return a.first < b.first;
}
bool cmp2(pii a, pii b) {
	return a.second < b.second;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (a >= 0) {
			a = -a - 1;
		}
		vc.push_back(pii(a, i));
	}
	if (n % 2 == 0) {
		for (auto c : vc) {
			cout << c.first << ' ';
		}
	}
	else {
		sort(vc.begin(), vc.end(), cmp1);
		if (vc[0].first != -1) {
			vc[0].first = -vc[0].first - 1;
			sort(vc.begin(), vc.end(), cmp2);
			for (auto c : vc) {
				cout << c.first<<' ';
			}
		}
		else {
			vc[0].first = 0;
			sort(vc.begin(), vc.end(), cmp2);
			for (auto c : vc) {
				cout << c.first<<' ';
			}
		}
	}
}

 

H. Maximal GCD

 

设该公因数为q,则n=q⋅(a1+a2+a3+⋯+ak)n=q\cdot (a_1+a_2+a_3+\cdots +a_k)，其中a1<a2<a3<⋯<aka_1<a_2<a_3<\cdots <a_k，最紧凑的情况是什么？

a1=1,a2=2,a3=3,ak=ka_1=1,a_2=2,a_3=3,a_k=k，则a1+a2+⋯+ak≤(1+k)⋅k2a_1+a_2+\cdots +a_k\leq\frac{(1+k)\cdot k}{2}，也就是说我们要找到两个数它们的乘积=n，并且其中一个数要大于等于(1+k)⋅k2\frac{(1+k)\cdot k}{2}，那么接下来枚举即可，我们要q尽量大，就是要(a1+a2+a3+⋯+ak)(a_1+a_2+a_3+\cdots +a_k)尽量小，因此从1开始枚举，若i是n的因数，且满足(1+k)⋅k2≤i\frac{(1+k)\cdot k}{2}\leq i，则找到答案q，跳出。

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
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
	long long n, k, tp, q;
	cin >> n >> k;
	if (k>141420)
	{
		cout << "-1" << endl;
		return 0;
	}
	tp = (1 + k)*k / 2; 
	q = 0;
	for (long long i = 1; i <= sqrt(n); i++)
	{
		if (n%i == 0)
		{
			if (i >= tp)
			{
				q = n / i; break;
			}
			else if (n / i >= tp)
				q = i;
		}
	}
	if (!q)
	{
		cout << "-1" << endl; return 0;
	}
	long long sum = 0, i;
	for (i = 1; i<k; i++)
	{
		cout << i*q << " "; sum += i;
	}
	cout << q*(n / q - sum) << endl;
	return 0;
}

 

I. Neko and Aki’s Prank

 

树形DP

求树上的最大匹配。

观察发现，对一棵根节点有i个’<‘，j个’>‘的子树A，与同样有i个’<‘，j个’>'的子树B，两者的后续发展是相同的，因而匹配情况也是是相同的。

因此考虑用记忆化搜索以节省时间。

dp[1005] [1005] [2]，设dp[i] [j] [k]表示某一节点已经用了i个’<‘，j个’>'，k表示该结点与其父节点是否可以连边，即连边后是否会与已确定的边集冲突，k=0表示不能与父节点连边，k=1表示可以与父节点连边。

转移方程：

 若当前节点的’<‘数i<n，则可以继续加入’<‘，而当且仅当’<‘个数大于’>‘个数时，可以加入’>'，因此需要分类讨论是否可以包含该节点的两棵子树。

叶子节点的dp值为0，因此推出当k=0时，即当前节点与其父节点不能连边，也就是说当前节点已经与某个子节点连边了，当前节点的最大匹配等于k=1的子节点+1，（因为仅仅是该子节点与当前节点可以连边，但并没有实际已经连边，所以要+1）。

最后(dp[1] [0] [1] +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
#include<iostream>
using namespace std;
const int mod = 1e9 + 7;
int n;
int dp[1005][1005][2];
bool vis[1005][1005][2];
int dfs(int l, int r, int k) {
	if (vis[l][r][k])
		return dp[l][r][k];
	vis[l][r][k] = 1;
	int t = k;
	int ans = 0;
	if (l < n) {
		ans = (ans + dfs(l + 1, r, t ^ 1) + (t ^ 1)) % mod;
		t = 1;
	}
	if (l > r) {
		ans = (ans + dfs(l, r + 1, t ^ 1) + (t ^ 1)) % mod;
	}
	return dp[l][r][k] = ans;
}
int main() {
	cin >> n;
	cout << (1+dfs(1,0,1)) % mod;
	return 0;
}