Codeforces Round #660 (Div. 2)
A. Captain Flint and Crew Recruitment（签到）
题意：定义可以分解成两个不同素数相乘的数为nearly prime，将一个数分解为4个不同的数，其中至少有三个nearly prime
开始没注意到4个不同的数，wa了
最小的四个nearly prime：6 10 14 15，<= 30的数无法分解，特别地 36 = 6 + 10 + 15 + 5，40 = 6 + 10 + 15 + 9，44 = 6 + 10 + 15 + 13，其他的都是6 + 10 + 14 + (n - 30)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int main()
{
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
if(n <= 30)
cout<<"NO"<<'\n';
else {
cout<<"YES"<<'\n';
if(n == 36)
cout<<"6 10 15 5"<<'\n';
else if(n == 40)
cout<<"6 10 15 9"<<'\n';
else if(n == 44)
cout<<"6 10 15 13"<<'\n';
else
cout<<"6 10 14 "<<n - 30<<'\n';
}
}
return 0;
}
B. Captain Flint and a Long Voyage（找规律）
题意： 找到使r取最大值的最小的x。r = 将x按位写成二进制的形式，擦掉后x位形成的数（当作10进制看）
打表发现的。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 75;
int main()
{
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int b = (n + 3) / 4;
int a = n - b;
for(int i = 1; i <= a; ++i) cout<<'9';
for(int i = 1; i <= b; ++i) cout<<'8';
cout<<'\n';
}
return 0;
}
C. Uncle Bogdan and Country Happiness（树 + dfs）
题意：
有n个城市，共m个人，给出每个城市的居民数，起初所有人都在城市1工作，都是开心的，在回家的过程中可能变得不开心，每个城市的快乐值 = 经过该点快乐的人数 - 经过该点不快乐的人数。
思路：
来自https://blog.csdn.net/ljw_study_in_CSDN/article/details/107711221
设sum[i]表示经过i点的总人数，good[i]表示经过i点是好心情的人数，bad[i]表示经过i点是坏心情的人数。
那么有：sum[i]=good[i]+bad[i], h[i]=good[i]-bad[i]。
消去bad[i]得到：good[i]=(sum[i]+h[i])/2。
其中，h[i]已知，sum[i]实际上就是家在 i 的子树节点(包括i)的人数，在dfs回溯的时候即可求出。那么good[i]也可求出了。
然后，考虑good[i]的限制条件：
- good[i]必须为整数，那么 sum[i]+h[i] 为偶数。
- 0<=good[i]<=sum[i]。
- good[v1]+good[v2]+…+good[vk]<=good[i]，其中v1,v2,…,vk为 i 的子树节点(不包括i)。因为从 i 点往下走其子树节点的过程中，好心情的总人数会降低或者不变，所以经过 i 的子树节点的好心情总人数小于等于经过 i 的好心情人数。
只要满足上述三条限制条件则存在可能性。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
vector<int>g[N];
int h[N], p[N], sum[N], good[N];
bool flag;
void dfs(int u, int fa) {
if(!flag) return ;
sum[u] = p[u];
int s = 0;
for(int v : g[u]) {
if(v == fa) continue;
dfs(v, u);
if(!flag)
return ;
sum[u] += sum[v];
s += good[v];
}
int tmp = h[u] + sum[u];
if(tmp & 1) {
flag = 0;
return ;
}
good[u] = tmp / 2;
if(good[u] < 0 || good[u] > sum[u] || s > good[u]) {
flag = 0;
return ;
}
}
int main()
{
int t, n, m, u, v;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%d", &p[i]);
for(int i = 1; i <= n; ++i)
scanf("%d", &h[i]);
for(int i = 1; i <= n; ++i)
g[i].clear();
for(int i = 1; i < n; ++i) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
flag = 1;
dfs(1, 0);
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}
D. Captain Flint and Treasure（思维 + 拓扑排序）
题意：每次选择包括两个步骤：ans += a[i]，a[b[i]] += a[i]，构造一个选择顺序使ans最大
思路：a[b[i]] += a[i]可以看作一条从a[i]到a[b[i]]的有向边，如果a[i] > 0，这条边会使a[b[i]]变大，是有利的，这时a[i]应尽早取，否则是不利的，a[i]应靠后取。跑一边拓扑排序，按拓扑序列把正值和负值分开存储，正值正序输出，负值逆序输出（靠前的会导致后面更多的数变小）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll a[N], b[N], in[N], n, ans;
vector<int>x, y;
void topo() {
x.clear();
y.clear();
queue<int>q;
for(int i = 1; i <= n; ++i) {
if(in[i] == 0)
q.push(i);
}
while(q.size()) {
int tmp = q.front();
q.pop();
int v = b[tmp];
if(v != -1) {
in[v]--;
if(in[v] == 0) q.push(v);
if(a[tmp] > 0) a[v] += a[tmp];
}
ans += a[tmp];
if(a[tmp] >= 0) x.push_back(tmp);
else y.push_back(tmp);
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i) in[i] = 0;
for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
for(int i = 1; i <= n; ++i) {
scanf("%lld", &b[i]);
if(b[i] != -1) in[b[i]]++;
}
ans = 0;
topo();
printf("%lld\n", ans);
int xs = x.size(), ys = y.size();
for(int i = 0; i < xs; ++i) {
if(i > 0) printf(" ");
printf("%d", x[i]);
}
for(int i = ys - 1; i >= 0; --i)
printf(" %d", y[i]);
printf("\n");
return 0;
}
美的集团公司福利 136人发布
