A. Captain Flint and Crew Recruitment
题目链接
题目原文
题目大意
如果一个数 x 能够表示成两个不同质数的乘积，那我们就称 x 为nearly prime。现给出 n ，求 n 能不能分解成 4 个不同数的和，其中 3 个是nearly prime？
解题思路
先考虑要求的3个nearly prime，因为要3个不同的数，所以我们需要所有的数尽量小，否则和会超出n。最开始我的想法是直接取6、10、14、n-30，过样例就能发现n-30与前面三个数可能会重复，不满足题意。那直接考虑枚举哪三个质数，只要有不重复的并且和小于n，那就能满足题意。
解法
处理出一部分两两质数的积，枚举取哪三个质数，看n-三个质数是否大于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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T,n;
int num[10]={0,2,3,5,7,11,13},a[maxn],tot=0;
int main()
{
#ifdef lemon
freopen("a.txt","r",stdin);
#endif
scanf("%d",&T);
for(int i=1;i<=6;i++)
for(int j=i+1;j<=6;j++)
a[++tot]=num[i]*num[j];
sort(a+1,a+tot+1);
while(T--)
{
scanf("%d",&n);
bool flag=false;
for(int i=1;i<=tot;i++)
{
for(int j=i+1;j<=tot;j++)
{
for(int k=j+1;k<=tot;k++)
{
if(flag) break;
int temp=n-a[i]-a[j]-a[k];
if(temp<=0) break;
if(temp==a[i]||temp==a[j]||temp==a[k]) break;
flag=true;
printf("YES\n%d %d %d %d\n",a[i],a[j],a[k],temp);
}
}
}
if(!flag) printf("NO\n");
}
return 0;
}
|
B. Captain Flint and a Long Voyage
题目链接
题目原文
题目大意
给出一个 n ，你需要确定一个n位的十进制数x，将x每一位写成二进制形式（要去掉前导零），再删去二进制的后n位，使得最后剩下的二进制最大。求x的最小可能值。
解题思路
根据样例以及初步分析，因为不能有前导零，并且二进制数必须要长。一位十进制数最多能表示成4位二进制数，分别是9(1001)和8(1000)。这样就很显然了，二进制前面n*3位全部是1001，后面n位全部是1000。
解法
确定一下多少个9，剩下补8。
代码
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T,n;
int main()
{
#ifdef lemon
freopen("B.txt","r",stdin);
#endif
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int res=n%4;
int t=n-n/4;
if(res) t--;
for(int i=1;i<=t;i++) printf("9");
for(int i=t+1;i<=n;i++) printf("8");
printf("\n");
}
return 0;
}
|
C. Uncle Bogdan and Country Happiness
题目链接
题目原文
题目大意
给出一棵树，每个节点给出人数、不一定准确的心情值。每个人从1号节点出发，在路上可能有些人心情会从good变成bad。每个人沿着最短路径回到自己的节点，求每个节点给出的心情值是否可能都是准确的。（心情值=good人数-bad人数）
解题思路
直接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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
struct node
{
int to,next;
} edge[maxn<<1];
int head[maxn],k=0;
void add(int u,int v)
{
edge[++k].to=v;
edge[k].next=head[u];
head[u]=k;
}
int n,T;
long long m,p[maxn],h[maxn],good[maxn],bad[maxn],size[maxn];
bool flag=false;
void dfs(int x,int fa)
{
size[x]=p[x];
for(int i=head[x];i;i=edge[i].next)
{
if(edge[i].to==fa) continue;
dfs(edge[i].to,x);
size[x]+=size[edge[i].to];
}
good[x]=size[x]+h[x];
if((good[x]&1)||good[x]<0) flag=true;
good[x]>>=1;
bad[x]=size[x]-good[x];
if(bad[x]<0) flag=true;
int total_good=0;
for(int i=head[x];i;i=edge[i].next)
{
if(edge[i].to==fa) continue;
total_good+=good[edge[i].to];
}
if(good[x]<total_good) flag=true;
}
int main()
{
#ifdef lemon
freopen("C.txt","r",stdin);
#endif
memset(head,0,sizeof(head));
memset(good,0,sizeof(good));
memset(bad,0,sizeof(bad));
memset(size,0,sizeof(size));
scanf("%d",&T);
while(T--)
{
k=0;flag=false;
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
for(int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs(1,1);
if(flag) printf("NO\n");
else printf("YES\n");
for(int i=1;i<=n;i++) head[i]=good[i]=bad[i]=size[i]=0;
}
return 0;
}
|
D. Captain Flint and Treasure
题目链接
题目原文
题目大意
给出长度为n的a数组和b数组，一共操作n次（每个位置必须操作一次），若第i次选定位置i，则ans+=a[i]，并且a[b[i]]+=a[i]，确定一个操作顺序使得取出的ans最大，并输出操作顺序。
解题思路
题目中保证了不会出现环，并且a[b[i]]+=a[i]是单向操作，自然而然地就想到了有向图的拓扑排序，直接做DAG dp就好。
解法
从度数为0的点开始，如果当前值大于0，那么加到下一个点上就可以使下一个点更优（意义为先选这个点）；如果当前值小于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
48
49
50
51
52
53
54
55
56
57
58
59
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=200005;
struct node
{
int to,next;
} edge[maxn<<1];
int k=0,head[maxn];
void add(int u,int v)
{
edge[++k].to=v;
edge[k].next=head[u];
head[u]=k;
}
int n,a[maxn],degree[maxn],rd[maxn],p[maxn],tot=0;
long long ans=0,f[maxn];
void toposort()
{
queue<int> q;
for(int i=1;i<=n;i++)
if(!rd[i]) q.push(i);
while(!q.empty())
{
int x=q.front();q.pop();
p[++tot]=x;
ans+=f[x];
for(int i=head[x];i;i=edge[i].next)
{
f[edge[i].to]+=max(0ll,f[x]);
rd[edge[i].to]--;
if(!rd[edge[i].to]) q.push(edge[i].to);
}
}
}
int main()
{
memset(f,0,sizeof(f));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1,b;i<=n;i++)
{
scanf("%d",&b);
if(b==-1) continue;
add(i,b);
rd[b]++;
degree[i]++;
degree[b]++;
}
for(int i=1;i<=n;i++) f[i]=(long long)a[i];
toposort();
printf("%lld\n",ans);
for(int i=1;i<=n;i++) if(f[p[i]]>=0) printf("%d ",p[i]);
for(int i=n;i;i--) if(f[p[i]]<0) printf("%d ",p[i]);
return 0;
}
|
