C题：
比赛结束1500+pp，结果出分900+fst，我就是fst的睿智Orz。
题意为给出$n,p,w,d$,求满足下列式子的任意$x,y,z$
$x*w+y*d=p\&\& x+y+z=n\&\&x\geq 0\&\&y\geq 0\&\&z\geq 0$
如果不看$z$，式子的前半段就是扩展欧几里得，所以先求出式子$x*w+y*d=p$的一种解$(x,y)$，然后再判断解的合法性，并将解转化成合法的。
由于求解时会爆longlong，所以用的java。
1 import java.math.BigInteger; 2 import java.util.*; 3 public class Main { 4 public static BigInteger x,y; 5 public static void main(String[] args) { 6 Scanner in = new Scanner(System.in); 7 BigInteger n,p,w,d,gcd,xx,yy; 8 n = in.nextBigInteger(); 9 p = in.nextBigInteger(); 10 w = in.nextBigInteger(); 11 d = in.nextBigInteger(); 12 gcd = exgcd(w,d); 13 if(p.mod(gcd)!=BigInteger.ZERO) { 14 System.out.printf("-1\n"); 15 return ; 16 } 17 x=x.multiply(p.divide(gcd)); 18 y=y.multiply(p.divide(gcd)); 19 BigInteger lcm = w.divide(gcd).multiply(d); 20 xx = lcm.divide(w); 21 yy = lcm.divide(d); 22 if (x.compareTo(BigInteger.ZERO)==-1 &&y.compareTo(BigInteger.ZERO)==-1) { 23 System.out.printf("-1\n"); 24 return ; 25 } 26 if (x.compareTo(BigInteger.ZERO)==-1) { 27 x=x.add (y.divide(yy).multiply(xx)); 28 y=y.mod(yy); 29 } 30 else if (y.compareTo(BigInteger.ZERO)==-1) { 31 y=y.add (x.divide(xx).multiply(yy)); 32 x=x.mod(xx); 33 } 34 if (x.add(y).compareTo(n)!=1 && x.compareTo(BigInteger.ZERO)!=-1 && y .compareTo(BigInteger.ZERO)!=-1) { 35 System.out.print(x); 36 System.out.print(" "); 37 System.out.print(y); 38 System.out.print(" "); 39 System.out.print(n.subtract(x.add(y))); 40 return ; 41 } 42 x=x.add (y.divide(yy).multiply(xx)); 43 y=y.mod(yy); 44 if (x.add(y).compareTo(n)!=1 && x.compareTo(BigInteger.ZERO)!=-1 && y.compareTo(BigInteger.ZERO)!=-1&&x.multiply(w).add(y.multiply(d)).compareTo(p)==0) { 45 System.out.print(x); 46 System.out.print(" "); 47 System.out.print(y); 48 System.out.print(" "); 49 System.out.print(n.subtract(x.add(y))); 50 return ; 51 } 52 else { 53 System.out.printf("-1\n"); 54 return ; 55 } 56 } 57 public static BigInteger exgcd(BigInteger a,BigInteger b) { 58 if (b == BigInteger.ZERO) { 59 x = BigInteger.ONE; 60 y = BigInteger.ZERO; 61 return a; 62 } 63 BigInteger g = exgcd(b, a.mod(b)); 64 BigInteger t = x; 65 x = y; 66 y =t.subtract((a.divide(b)).multiply(y)); 67 return g; 68 } 69 }
D题：
题意是给一棵树每个点染色，一共三种颜色，求染色花费最少并且相邻的三个点颜色不能重复。
因为相邻的三个点颜色不能一样，所以树上每个点的度都要$\leq 2$，即只有链才能染色。而链上染色只有$6$种方法，所以枚举$6$次即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 2e5 + 10; 5 const ll inf = 1e18; 6 ll a[maxn][5], ans[maxn]; 7 vector<int>p[maxn]; 8 int cnt[10][3] = { {1,2,3},{2,1,3},{3,1,2},{1,3,2},{2,3,1},{3,2,1} }; 9 ll dfs(int x, int fa, int w, int t) { 10 ll ans = a[x][cnt[w][t]]; 11 for (int i = 0; i < p[x].size(); i++) { 12 int y = p[x][i]; 13 if (y == fa)continue; 14 ans += dfs(y, x, w, (t + 1) % 3); 15 } 16 return ans; 17 } 18 void dfs1(int x, int fa, int w, int t) { 19 ans[x] = cnt[w][t]; 20 for (int i = 0; i < p[x].size(); i++) { 21 int y = p[x][i]; 22 if (y == fa)continue; 23 dfs1(y, x, w, (t + 1) % 3); 24 } 25 } 26 int main() { 27 int n; 28 scanf("%d", &n); 29 for (int j = 1; j <= 3; j++) 30 for (int i = 1; i <= n; i++) 31 scanf("%lld", &a[i][j]); 32 int f = 0, root = 1; 33 for (int i = 1, x, y; i < n; i++) { 34 scanf("%d%d", &x, &y); 35 p[x].push_back(y); 36 p[y].push_back(x); 37 if (p[x].size() > 2 || p[y].size() > 2) 38 f = 1; 39 } 40 for (int i = 1; i <= n; i++) 41 if (p[i].size() == 1) 42 root = i; 43 if (f == 1) 44 printf("-1\n"); 45 else { 46 ll Min = inf, ansi = 0; 47 for (int i = 0; i < 6; i++) { 48 ll t = dfs(root, 0, i, 0); 49 if (Min > t) 50 Min = t, ansi = i; 51 } 52 printf("%lld\n", Min); 53 dfs1(root, 0, ansi, 0); 54 for (int i = 1; i <= n; i++) 55 printf("%lld%c", ans[i], i == n ? '\n' : ' '); 56 } 57 }
E题：
题意说有n个数，有一种操作可以让一个数+1或-1，问最多k次操作后$min(max(a_{i})-min(a_{i}))$的值。