首页 > 代码库 > Codeforces Round #381 (Div. 2)

Codeforces Round #381 (Div. 2)

  A题,虽然是水题,但是也需要仔细。代码如下:

技术分享
 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <vector>
 5 #include <iostream>
 6 using namespace std;
 7 const int N = 10000 + 5;
 8 typedef long long ll;
 9 
10 ll n,a,b,c;
11 
12 int main()
13 {
14     cin >> n >> a >> b >> c;
15     ll ans = 0;
16     if(n % 4 == 0) return 0*puts("0");
17     n %= 4;
18     //cout << n << endl;
19     if(n == 1) ans = min({3*a, a+b, c});
20     else if(n == 2) ans = min({2*a, b, 2*c});
21     else ans = min({a, 3*c, b+c});
22     cout << ans << endl;
23     return 0;
24 }
A

 

  B题,暴力计算每一段的贡献,如果大于0那么就选择这段即可。

  C题,构造题,显然答案是根据最短的那一段的长度来决定的,如果最短区间长度为len,答案就为len。然后就是构造了。其实很简单只要按照0~len-1依次一直摆放下去即可,因为这样的话就能够保证任意一个区间里面必定会有这len个数字。

  D题,之前做过一个一模一样的,假设dis[u]表示u这点到根节点的距离,那么u能控制v就需要满足:dis[v]-dis[u]<=a[v],整理得,dis[v]-a[v]<=dis[u]。然后具体算法参照下面的代码好了:

技术分享
 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <vector>
 5 using namespace std;
 6 const int N = 200000 + 100;
 7 typedef long long ll;
 8 
 9 int T,x[N],n;
10 vector<int> p;
11 vector<ll> v;
12 int num[N],ed[N];
13 struct edge
14 {
15     int v,w;
16 };
17 vector<edge> G[N];
18 
19 void init()
20 {
21     for(int i=1;i<=n;i++) G[i].clear();
22     v.clear();
23     p.clear();
24 }
25 
26 void dfs(int u,int fa,int w)
27 {
28     ll temp = 0;
29     if(v.size()) temp = *v.rbegin();
30 
31     v.push_back(temp + w);
32     p.push_back(u);
33 
34     num[u] = ed[u] = 0;
35     for(int i=0;i<G[u].size();i++)
36     {
37         edge e = G[u][i];
38         int v = e.v;
39         if(v == fa) continue;
40         dfs(v,u,e.w);
41         num[u] += num[v] + 1 - ed[v]; // 1表示加上本身,-ed[v]表示减去到v这里就停止的点
42         // 如果是到v的子节点停止的话,num[v]会减少的,因此不会遗漏
43     }
44 
45     int t = lower_bound(v.begin(),v.end(),temp+w-x[u]) - v.begin();
46     ed[p[t]]++;
47 
48     v.pop_back();
49     p.pop_back();
50 }
51 
52 int main()
53 {
54     //freopen("car.in","r",stdin);
55     //scanf("%d",&T);
56     //while(T--)
57     {
58         scanf("%d",&n);
59         init();
60         for(int i=1;i<=n;i++) scanf("%d",x+i);
61         for(int i=2;i<=n;i++)
62         {
63             int v = i;
64             int u,w;
65             scanf("%d%d",&u,&w);
66             //int u,v,w;
67             //scanf("%d%d%d",&u,&v,&w);
68             G[u].push_back((edge){v,w});
69             G[v].push_back((edge){u,w});
70         }
71         dfs(1,-1,0);
72         for(int i=1;i<=n;i++) printf("%d%c",num[i],i==n?\n: );
73     }
74     return 0;
75 }
D

总觉得自己这种dfs然后乱搞的题目不是很会做- -。

Codeforces Round #381 (Div. 2)