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 }
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?' ':' '); 73 } 74 return 0; 75 }
总觉得自己这种dfs然后乱搞的题目不是很会做- -。