求gcd，遍历下p/w向下w个值即可，复杂度O(w)
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 1e3+7;
5 const ll mod = 1e9 + 9;
6 #define afdafafafdafaf y1;
7 int ar[maxn], n;
8
9
10 void e_gcd(ll a, ll b, ll &gcd, ll &x, ll &y)
11 {
12 if (b==0){
13 x=1;
14 y=0;
15 gcd=a;
16 }else{
17 e_gcd(b, a%b, gcd, y, x);//注意要交换x和y
18 y=y-x*(a/b);//有上面推导出来的公式
19 //x1 = y2（等式两边a的系数相同）
20 //y1 = x2 - (a / b) * y2 （等式两边b的系数相同）
21 }
22 }
23 int main()
24 {
25 ll n,p,w,d;
26 scanf("%lld%lld", &n, &p);
27 scanf("%lld%lld", &w, &d);
28 if(n * w < p){
29 printf("-1\n");
30 return 0;
31 }
32 ll gcd, x, y;
33 e_gcd(w, d, gcd, x, y);
34 if(p % gcd != 0){
35 printf("-1\n");
36 return 0;
37 }
38 w /= gcd;
39 d /= gcd;
40 p /= gcd;
41 ll ins = p / w;
42 for(int i=0;i<=min(w, ins);i++){
43 if((p - (ins - i) * w) % d == 0){
44 x = ins - i;
45 y = (p - (ins - i) * w) / d;
46 break;
47 }
48 }
49 if(x >= 0 && y >= 0 && n - x - y >= 0){
50 printf("%lld %lld %lld\n", x, y, n - x - y);
51 }
52 else printf("-1\n");
53 return 0;
54 }
View Code
初步分析如果出现度大于等于3的点，没有配色方案，那么树一定是一条链，从链的一头开始遍历，dp即可
no[u].a[i][j]值得是u节点涂第i种颜色，他的子节点涂第j种颜色需要的最小花费，dp即可，过程略微繁琐
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 1e5+7;
5 const ll mod = 1e9 + 9;
6 #define afdafafafdafaf y1;
7 int ar[maxn], n;
8
9 struct node{
10 ll a[4][4];
11 }no[maxn];
12 int arr[4][maxn];
13 vector<int> g[maxn];
14 node dfs(int u, int pre){
15 node nou;
16 memset(nou.a, 0, sizeof(nou.a));
17 for(int v : g[u]){
18 if(v == pre)continue;
19 node mid = dfs(v, u);
20 for(int i=1;i<=3;i++){
21 for(int j=1;j<=3;j++){
22 if(i != j)nou.a[i][j] += mid.a[i][j];
23 }
24 }
25 }
26 memset(no[u].a, 0, sizeof(no[u].a));
27 no[u].a[1][2] = arr[1][u] + nou.a[2][3];
28 no[u].a[1][3] = arr[1][u] + nou.a[3][2];
29 no[u].a[2][1] = arr[2][u] + nou.a[1][3];
30 no[u].a[2][3] = arr[2][u] + nou.a[3][1];
31 no[u].a[3][1] = arr[3][u] + nou.a[1][2];
32 no[u].a[3][2] = arr[3][u] + nou.a[2][1];
33 return no[u];
34 }
35 int in[maxn], av[maxn];
36 void dfs2(int u, int pre, int col, ll val, int pre_col){
37 av[u] = col;
38 if(in[u] == 1 && pre != 0){
39 //assert(val == arr[col][u]);
40 }
41 for(int v : g[u]){
42 if(v==pre)continue;
43 ll mn = 1e18;
44 int ins = 0;
45 for(int j=1;j<=3;j++){
46 if(col != j){
47 if(mn > no[u].a[col][j] && j != pre_col){
48 mn = no[u].a[col][j];
49 ins = j;
50 }
51 }
52 }
53 //assert(val == mn);
54 dfs2(v, u, ins, val - arr[col][u], col);
55 }
56 }
57 int main()
58 {
59 scanf("%d", &n);
60 for(int i=1;i<=3;i++){
61 for(int j=1;j<=n;j++)scanf("%d", &arr[i][j]);
62 }
63 for(int i=1;i<n;i++){
64 int a,b;scanf("%d%d", &a, &b);
65 g[a].push_back(b);
66 g[b].push_back(a);
67 in[a]++;
68 in[b]++;
69 }
70 for(int i=1;i<=n;i++){
71 if(in[i] >= 3){
72 printf("-1\n");
73 return 0;
74 }
75 }
76 int be = 0;
77 int xx = 0;
78 for(int i=1;i<=n;i++){
79 if(in[i] == 1){
80 be = i;
81 xx++;
82 }
83 else{
84 assert(in[i] == 2);
85 }
86 }
87 assert(xx == 2);
88 node mid = dfs(be, 0);
89 ll ans = 1e18, ins = 0;
90 for(int i=1;i<=3;i++){
91 for(int j=1;j<=3;j++){
92 if(i != j){
93 if(ans >= mid.a[i][j]){
94 ans = mid.a[i][j];
95 ins = i;
96 }
97 }
98 }
99 }
100 dfs2(be, 0, ins, ans, -1);
101 printf("%lld\n", ans);
102 for(int i=1;i<=n;i++)printf("%d%c", av[i], i==n ? '\n' : ' ');
103
104 return 0;
105 }
View Code
看这个有序列里两个最值的数量，以此更新更小长度的最值即可，利用multiset来写，代码简洁很多
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 1e5+7;
5 const ll mod = 1e9 + 9;
6 #define afdafafafdafaf y1;
7 int ar[maxn], n;
8
9 ll k;
10 int main()
11 {
12 scanf("%d%lld", &n, &k);
13 multiset<ll> s;
14 for(int i = 1; i <= n; i++){
15 scanf("%d", ar + i);
16 s.insert(ar[i]);
17 }
18 ll be = * s.begin();
19 auto it = s.end();
20 it--;
21 ll en = *it;
22 ll be_ins = s.count(be), en_ins = s.count(en);
23 ll ans = 0;
24 s.erase(be);
25 s.erase(en);
26 while(be < en){
27 if(s.size() == 0){
28 be = min(en, be + k / min(be_ins, en_ins));
29 break;
30 }
31 it = s.begin();
32 ll new_be = *it;
33 it = s.end();
34 it--;
35 ll new_en = *it;
36 if(be_ins < en_ins){
37 if(k > be_ins * (new_be - be)){
38 k -= be_ins * (new_be - be);
39 be = new_be;
40 be_ins += s.count(be);
41 s.erase(be);
42 }
43 else{
44 be = min(en, be + k / be_ins);
45 break;
46 }
47 }
48 else{
49 if(k > en_ins * (en - new_en)){
50 k -= en_ins * (en - new_en);
51 en = new_en;
52 en_ins += s.count(en);
53 s.erase(en);
54 }
55 else{
56 en = max(be, en - k / en_ins);
57 break;
58 }
59 }
60 }
61 ans = en - be;
62 printf("%lld\n", max(0LL, ans));
63 return 0;
64 }
View Code