题面:http://codeforces.com/contest/1118/problems
打了一场不是很顺的div.3 就A了3题 掉了15分
C调了太久了，可能有一个半小时
赛后10分钟过了F1，今天发现D也是水题随便写写就过了update: E也是水题
啊又掉分了。我 想 上 蓝 ！
A. Water Buying
题意
签到1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
pii a[2000];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int q;
cin >> q;
while(q--)
{
ll n, a, b;
cin >> n >> a >> b;
cout << min(n * a, (n / 2) * b + (n % 2) * a) << endl;
}
return 0;
}
B. Tanya and Candies
题意
有n个数字，要求从中删除一个使得偶数位的和等于奇数位的和的数字个数
解法
记录前后缀 扫一遍即可 删除当前数后 该数的前一个和后一个必然具有不同的奇偶性位置
要注意处理好首尾的情况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
using namespace std;
const int maxn = 2e5 + 10;
ll a[maxn];
ll pre[maxn], suf[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++)
{
if(i == 0 || i == 1)
pre[i] = a[i];
else
pre[i] = a[i] + pre[i - 2];
}
for(int i = n - 1; i >= 0; i--)
{
if(i == n - 1 || i == n - 2)
suf[i] = a[i];
else
suf[i] = suf[i + 2] + a[i];
}
int cnt = 0;
for(int i = 0; i < n; i++)
{
ll aa = pre[i] - a[i] + suf[i + 1], bb;
if(i == 0)
bb = suf[i] - a[i];
else
bb = pre[i - 1] + suf[i] - a[i];
if(aa == bb)
cnt++;
}
cout << cnt << endl;
return 0;
}
C. Palindromic Matrix
题意
给定$n$及$n^2$个数，要求你构造出一个$n \times n$的矩阵。
使得行交换和列交换后的矩阵和原矩阵相同
解法
这题是真的烦。有大量的细节要考虑。
偶数的情况较容易
观察可以发现，所有数必须是4的倍数，将矩阵分为上下左右4个子矩阵，是关于中心对称的
处理计算所有数的个数是否位4的倍数即可。
奇数情况才是真的魔鬼。
可以发现，除了中间一列和中间一行，上下左右4个子矩阵是关于中心对称的。
但是对于中间行列来说，只需要关于轴对称即可。且中间的数可以单独存在。
所以扫一遍所有数判断奇数的个数是否超过2 超过2则一定不可能
奇数个数的那个数就是中间的数
然后判断2的个数够不够用 如果超过了中间行列需要的数$(n - 1)$也是NO
如果不够 并且缺偶数个 那么可以用4个的补 如果是奇数 则输出NO
要注意的点 在处理的时候 要注意前面可能已经删过了 所以不光只是整除4 还要是否判断大于0
然后补2的时候是尽可能能补则补 不要4个的只补一双 如果有8个 就补8个 以防后面不够
处理个数的话我用了一个set存所有数字，同时tim数组记录每个数字出现次数
这场就崩在这题上了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
using namespace std;
const int maxn = 2e3 + 10;
int tim[maxn];
int ans[30][30];
set<int> q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n * n; i++)
{
int t;
cin >> t;
q.insert(t);
tim[t]++;
}
if(n % 2 == 0)
{
for(auto idx: q)
if(tim[idx] % 4)
{
cout << "NO" << endl;
return 0;
}
vector<int> p;
for(auto idx: q)
{
for(int i = 0; i < tim[idx] / 4; i++)
p.push_back(idx);
}
int idx = 0;
for(int i = 0; i < n / 2; i++)
for(int j = 0; j < n / 2; j++)
ans[i][j] = ans[i][n - 1 - j] = ans[n - 1 - i][j] = ans[n - 1 - i][n - 1 - j] = p[idx++];
cout << "YES" << endl;
for(int i = 0; i < n; i++, cout << endl)
for(int j = 0; j < n; j++)
cout << ans[i][j] << ' ';
}
else
{
int odd = 0;
vector<int> two;
for(auto idx: q)
if(tim[idx] % 2)
odd++;
if(odd > 1)
{
cout << "NO" << endl;
return 0;
}
for(auto idx: q)
{
if(tim[idx] % 2)
{
ans[n / 2][n / 2] = idx;
tim[idx]--;
}
if(tim[idx] % 4)
{
two.push_back(idx);
tim[idx] -= 2;
}
}
if(two.size() > n - 1 || (n - 1 - two.size()) % 2)//Èç¹ûÊÇ2µÄ±¶Êý³¬¹ýn-1»òÕß»¹²îÆæÊý¸ö
{
cout << "NO" << endl;
return 0;
}
if(two.size() < n - 1)//ÓÃ4µÄÕûÊý±¶µÄÈ¥²¹
for(auto idx: q)
{
if(tim[idx] > 0 && tim[idx] % 4 == 0)
{
int qt = tim[idx];
for(int i = 0; i < qt / 2 && two.size() < n - 1; i++)
{
two.push_back(idx);
tim[idx] -= 2;
}
if(two.size() == n - 1)
break;
}
}
vector<int> p;
for(auto idx: q)
{
if(tim[idx] % 4 == 0 && tim[idx] > 0)
for(int i = 0; i < tim[idx] / 4; i++)
p.push_back(idx);
}
int idx = 0;
for(int i = 0; i < n / 2; i++)
for(int j = 0; j < n / 2; j++)
ans[i][j] = ans[i][n - 1 - j] = ans[n - 1 - i][j] = ans[n - 1 - i][n - 1 - j] = p[idx++];
idx = 0;
for(int i = 0; i < n / 2; i++)
{
ans[n / 2][i] = ans[n / 2][n - 1 - i] = two[idx++];
ans[i][n / 2] = ans[n - 1 - i][n / 2] = two[idx++];
}
cout << "YES" << endl;
for(int i = 0; i < n; i++, cout << endl)
for(int j = 0; j < n; j++)
cout << ans[i][j] << ' ';
}
return 0;
}
D. Coffee and Coursework
题意
有$n$杯咖啡，每杯咖啡有一个咖啡因值$a_i$。每天喝第1杯咖啡时可以得到能量$a_i$，可以做$a_i$张试卷。当天接下来喝的第$k$杯咖啡，只能得到$a_i-k$的能量。问要做完m张试卷，最少需要多少天。
解法
二分。由于喝的咖啡可以随意选择，所以先将咖啡按咖啡因从大到小进行排序。
很显然，每天分到的咖啡杯数一定是越少越好。因为分到的咖啡杯数越多，咖啡因的削弱会越多。所以如果存在$i$满足要求，则对于$j(j>i)$一定也满足要求，存在单调性。
1 |
|
E. Yet Another Ball Problem
题意
要求构造出n个二元组满足
- 每个元组各不相同
- 相邻的两个元组的第一个数和第二个数不能相同
- 每个元组的第一个数和第二个数必须不同
- 可以使用$1-k$之间的数
解法
又是一个构造题。有很多种构造的方法。
比如说$(1, 2)(2,1)(1,3)(3,1)(1,4)(4,1)(2,3)(3,2)(2,4)(4,2)(3,4)(4,3)$
再比如说Let man’s costumes colors be in the following order: $1,2,…,𝑘;1,2,…,𝑘;1,2,…,𝑘$ and so on. Now we have to set some colors to woman’s costumes. The first thing comes to mind is to use some cyclic shift of $1,2,…,𝑘$. And it is the best thing we can do! So let women’s costumes colors be in the following order: $2,3,…,𝑘,1;3,4,…,𝑘,1,2;4,5,…,𝑘,1,2,3$ ans so on.
最多能构造的数量为$(1 + 2+3+…k-1) \cdot 2 = k \cdot (k - 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
using namespace std;
int main()
{
ll n, k;
scanf("%lld%lld", &n, &k);
ll mmax = k - 1 + (k - 2) * (k - 1) / 2;
mmax *= 2;
if(n > mmax)
puts("NO");
else
{
puts("YES");
int counter = 0;
for(int i = 1; i < k && counter < n; i++)
{
for(int j = i + 1; j <= k && counter < n; j++)
{
printf("%d %d\n", i, j);
counter++;
if(counter == n) break;
printf("%d %d\n", j, i);
counter++;
}
}
}
return 0;
}
F1. Tree Cutting (Easy Version)
题意
给定$n$个节点的树，树上节点可能是蓝色、红色或是没有颜色。保证至少有一个节点是蓝色和红色。删除一条边使得割裂后的两棵子树
解法
算出蓝色和红色的节点总个数。统计子树中的蓝色节点和红色节点个数。每次遍历完该节点的子树后进行判断即可。一遍DFS。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
using namespace std;
const int maxn = 3e5 + 10;
vector<int> tree[maxn];
int color[maxn];
int blue, red, res;
int cnt[maxn][2];//0为红 1为蓝
void dfs(int node, int pre)
{
for(auto idx: tree[node])
{
if(idx == pre)
continue;
dfs(idx, node);
cnt[node][0] += cnt[idx][0];
cnt[node][1] += cnt[idx][1];
}
if((cnt[node][0] == red && cnt[node][1] == 0) || (cnt[node][1] == blue && cnt[node][0] == 0))
res++;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> color[i];
if(color[i] == 1)
{
red++;
cnt[i][0]++;
}
if(color[i] == 2)
{
blue++;
cnt[i][1]++;
}
}
for(int i = 1; i < n; i++)
{
int a, b; cin >> a >> b;
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs(1, 0);
cout << res << endl;
return 0;
}