A.拆地毯
题目：http://www.contesthunter.org/contest/CH%20Round%20%2352%20-%20Thinking%20Bear%20%231%20(NOIP模拟赛)/拆地毯
题解：按最大生成树顺序加k条边即可
代码：
1 const maxn=100000+1000; 2 var c:array[0..maxn] of int64; 3 fa,a,b:array[0..maxn] of longint; 4 i,j,n,m,k:longint; 5 ans:int64; 6 function find(x:longint):longint; 7 begin 8 if fa[x]<>x then fa[x]:=find(fa[x]); 9 exit(fa[x]); 10 end; 11 12 procedure sort(l,r:longint); 13 var i,j:longint;x,y:int64; 14 begin 15 i:=l;j:=r;x:=c[(i+j)>>1]; 16 repeat 17 while c[i]>x do inc(i); 18 while c[j]<x do dec(j); 19 if i<=j then 20 begin 21 y:=a[i];a[i]:=a[j];a[j]:=y; 22 y:=b[i];b[i]:=b[j];b[j]:=y; 23 y:=c[i];c[i]:=c[j];c[j]:=y; 24 inc(i);dec(j); 25 end; 26 until i>j; 27 if i<r then sort(i,r); 28 if j>l then sort(l,j); 29 end; 30 procedure init; 31 begin 32 readln(n,m,k); 33 for i:=1 to m do readln(a[i],b[i],c[i]); 34 end; 35 procedure main; 36 begin 37 sort(1,m); 38 for i:=1 to n do fa[i]:=i; 39 j:=1; 40 ans:=0; 41 for i:=1 to k do 42 begin 43 while (find(a[j])=find(b[j])) do inc(j); 44 fa[find(a[j])]:=find(b[j]); 45 inc(ans,c[j]); 46 end; 47 writeln(ans); 48 end; 49 50 begin 51 init; 52 main; 53 end.
B.还教室
题目：http://www.contesthunter.org/contest/CH%20Round%20%2352%20-%20Thinking%20Bear%20%231%20(NOIP模拟赛)/还教室
题解：前两个操作都是线段树基础操作，第三个操作需要一点变形
首先我们要知道：方差s=sigma（xi-x0）^2 (i=1..n) /n =sigma（xi^2）-x0^2 x0表示平均数
这手推一下就知道了，我们只需要指导一段区间内的平方和即可，线段树也是可以维护的
（ms贴吧里有人说 只要是具有加和性？就能用线段树来维护？
我理解的是 加上1个值x1 又加了1个值x2，不管第一次加的值，直接把需要加的值更改为x1+x2在维护的时候可以正确就是对的。。。）
代码：
1 const maxn=100000+1000; 2 type node=record 3 l,r,mid,lch,rch:longint; 4 sum,pf,tag:int64; 5 end; 6 var t:array[0..4*maxn] of node; 7 a:array[0..maxn] of longint; 8 i,j,n,m,ch,x,y:longint; 9 xx,yy,z:int64; 10 procedure pushup(k:longint); 11 begin 12 with t[k] do 13 begin 14 sum:=t[lch].sum+t[rch].sum; 15 pf:=t[lch].pf+t[rch].pf; 16 end; 17 end; 18 procedure update(k:longint;val:int64); 19 begin 20 with t[k] do 21 begin 22 inc(tag,val); 23 inc(pf,2*val*sum+(r-l+1)*val*val); 24 inc(sum,(r-l+1)*val); 25 end; 26 end; 27 procedure pushdown(k:longint); 28 begin 29 with t[k] do 30 begin 31 if tag=0 then exit; 32 update(lch,tag);update(rch,tag); 33 tag:=0; 34 end; 35 end; 36 37 procedure build(k,x,y:longint); 38 begin 39 with t[k] do 40 begin 41 l:=x;r:=y;mid:=(l+r)>>1;lch:=k<<1;rch:=k<<1+1;tag:=0; 42 if l=r then begin sum:=a[l];pf:=a[l]*a[l];exit;end; 43 build(lch,l,mid);build(rch,mid+1,r); 44 pushup(k); 45 end; 46 end; 47 procedure change(k,x,y,z:longint); 48 begin 49 with t[k] do 50 begin 51 if (l=x) and (r=y) then begin update(k,z);exit;end; 52 pushdown(k); 53 if y<=mid then change(lch,x,y,z) 54 else if x>mid then change(rch,x,y,z) 55 else 56 begin 57 change(lch,x,mid,z);change(rch,mid+1,y,z); 58 end; 59 pushup(k); 60 end; 61 end; 62 function getsum(k,x,y:longint):int64; 63 begin 64 with t[k] do 65 begin 66 if (l=x) and (r=y) then exit(sum); 67 pushdown(k); 68 if y<=mid then exit(getsum(lch,x,y)) 69 else if x>mid then exit(getsum(rch,x,y)) 70 else exit(getsum(lch,x,mid)+getsum(rch,mid+1,y)); 71 end; 72 end; 73 function getsqr(k,x,y:longint):int64; 74 begin 75 with t[k] do 76 begin 77 if (l=x) and (r=y) then exit(pf); 78 pushdown(k); 79 if y<=mid then exit(getsqr(lch,x,y)) 80 else if x>mid then exit(getsqr(rch,x,y)) 81 else exit(getsqr(lch,x,mid)+getsqr(rch,mid+1,y)); 82 end; 83 end; 84 85 procedure init; 86 begin 87 readln(n,m); 88 for i:=1 to n do read(a[i]);readln; 89 build(1,1,n); 90 end; 91 procedure solvechange; 92 begin 93 readln(x,y,z); 94 change(1,x,y,z); 95 end; 96 function gcd(x,y:int64):int64; 97 begin 98 if y=0 then exit(x) else exit(gcd(y,x mod y)); 99 end; 100 procedure solveaverage; 101 begin 102 readln(x,y); 103 xx:=getsum(1,x,y);yy:=y-x+1; 104 z:=gcd(xx,yy); 105 if xx=0 then writeln('0/1') 106 else writeln(xx div z,'/',yy div z); 107 end; 108 procedure solvefangcha; 109 begin 110 readln(x,y); 111 yy:=y-x+1; 112 xx:=yy*getsqr(1,x,y)-sqr(getsum(1,x,y)); 113 yy:=yy*yy; 114 z:=gcd(xx,yy); 115 if xx=0 then writeln('0/1') 116 else writeln(xx div z,'/',yy div z); 117 end; 118 119 procedure main; 120 begin 121 for i:=1 to m do 122 begin 123 read(ch); 124 case ch of 125 1:solvechange; 126 2:solveaverage; 127 3:solvefangcha; 128 end; 129 end; 130 end; 131 132 begin 133 init; 134 main; 135 end.
C.皇后游戏
题目：http://www.contesthunter.org/contest/CH%20Round%20%2352%20-%20Thinking%20Bear%20%231%20(NOIP模拟赛)/皇后游戏
题解：不会捉。。。按a排序，骗了30分。。。
代码：
1.我的
1 const maxn=100000+1000; 2 var a,b,c:array[0..maxn] of int64; 3 ans,sum:int64; 4 i,j,n,cs:longint; 5 function max(x,y:int64):int64; 6 begin 7 if x>y then exit(x) else exit(y); 8 end; 9 10 procedure sort(l,r:longint); 11 var i,j:longint;x,y:int64; 12 begin 13 i:=l;j:=r;x:=c[(i+j)>>1]; 14 repeat 15 while c[i]<x do inc(i); 16 while c[j]>x do dec(j); 17 if i<=j then 18 begin 19 y:=a[i];a[i]:=a[j];a[j]:=y; 20 y:=b[i];b[i]:=b[j];b[j]:=y; 21 y:=c[i];c[i]:=c[j];c[j]:=y; 22 inc(i);dec(j); 23 end; 24 until i>j; 25 if i<r then sort(i,r); 26 if j>l then sort(l,j); 27 end; 28 procedure init; 29 begin 30 readln(n); 31 for i:=1 to n do readln(a[i],b[i]); 32 for i:=1 to n do c[i]:=a[i]; 33 end; 34 procedure main; 35 begin 36 sort(1,n);sum:=0;ans:=0; 37 for i:=1 to n do 38 begin 39 sum:=sum+a[i]; 40 ans:=max(ans,sum)+b[i]; 41 end; 42 writeln(ans); 43 end; 44 45 begin 46 readln(cs); 47 while cs>0 do 48 begin 49 dec(cs); 50 init; 51 main; 52 end; 53 end.
2.标程 也是排序，不过好高大上啊。。。
1 //#include <cmath> 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <string> 6 #include <cstdlib> 7 #include <vector> 8 #include <set> 9 #include <algorithm> 10 #define mp make_pair 11 #define fi first 12 #define se second 13 14 using namespace std; 15 16 typedef long long int64; 17 typedef pair<int,int> PII; 18 const int MAXN=200005; 19 20 int n; 21 PII a[MAXN]; 22 int64 dp[MAXN]; 23 24 inline bool cmp(const PII &x,const PII &y) 25 { 26 return min(x.fi,y.se)<min(x.se,y.fi); 27 } 28 29 int main() 30 { 31 int testCase; 32 for (scanf("%d",&testCase);testCase;testCase--) 33 { 34 scanf("%d",&n); 35 for (int i=1;i<=n;i++) scanf("%d%d",&a[i].fi,&a[i].se); 36 sort(a+1,a+n+1,cmp); 37 int64 s=0; 38 for (int i=1;i<=n;i++) 39 { 40 s+=a[i].fi; 41 dp[i]=max(s,dp[i-1])+a[i].se; 42 } 43 cout<<dp[n]<<endl; 44 } 45 return 0; 46 }