A.拆地毯
题目：http://www.contesthunter.org/contest/CH%20Round%20%2352%20-%20Thinking%20Bear%20%231%20(NOIP模拟赛)/拆地毯
题解：按最大生成树顺序加k条边即可
代码：
const maxn=+;
var c:array[..maxn] of int64;
fa,a,b:array[..maxn] of longint;
i,j,n,m,k:longint;
ans:int64;
function find(x:longint):longint;
begin
if fa[x]<>x then fa[x]:=find(fa[x]);
exit(fa[x]);
end; procedure sort(l,r:longint);
var i,j:longint;x,y:int64;
begin
i:=l;j:=r;x:=c[(i+j)>>];
repeat
while c[i]>x do inc(i);
while c[j]<x do dec(j);
if i<=j then
begin
y:=a[i];a[i]:=a[j];a[j]:=y;
y:=b[i];b[i]:=b[j];b[j]:=y;
y:=c[i];c[i]:=c[j];c[j]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end;
procedure init;
begin
readln(n,m,k);
for i:= to m do readln(a[i],b[i],c[i]);
end;
procedure main;
begin
sort(,m);
for i:= to n do fa[i]:=i;
j:=;
ans:=;
for i:= to k do
begin
while (find(a[j])=find(b[j])) do inc(j);
fa[find(a[j])]:=find(b[j]);
inc(ans,c[j]);
end;
writeln(ans);
end; begin
init;
main;
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在维护的时候可以正确就是对的。。。）
代码：
const maxn=+;
type node=record
l,r,mid,lch,rch:longint;
sum,pf,tag:int64;
end;
var t:array[..*maxn] of node;
a:array[..maxn] of longint;
i,j,n,m,ch,x,y:longint;
xx,yy,z:int64;
procedure pushup(k:longint);
begin
with t[k] do
begin
sum:=t[lch].sum+t[rch].sum;
pf:=t[lch].pf+t[rch].pf;
end;
end;
procedure update(k:longint;val:int64);
begin
with t[k] do
begin
inc(tag,val);
inc(pf,*val*sum+(r-l+)*val*val);
inc(sum,(r-l+)*val);
end;
end;
procedure pushdown(k:longint);
begin
with t[k] do
begin
if tag= then exit;
update(lch,tag);update(rch,tag);
tag:=;
end;
end; procedure build(k,x,y:longint);
begin
with t[k] do
begin
l:=x;r:=y;mid:=(l+r)>>;lch:=k<<;rch:=k<<+;tag:=;
if l=r then begin sum:=a[l];pf:=a[l]*a[l];exit;end;
build(lch,l,mid);build(rch,mid+,r);
pushup(k);
end;
end;
procedure change(k,x,y,z:longint);
begin
with t[k] do
begin
if (l=x) and (r=y) then begin update(k,z);exit;end;
pushdown(k);
if y<=mid then change(lch,x,y,z)
else if x>mid then change(rch,x,y,z)
else
begin
change(lch,x,mid,z);change(rch,mid+,y,z);
end;
pushup(k);
end;
end;
function getsum(k,x,y:longint):int64;
begin
with t[k] do
begin
if (l=x) and (r=y) then exit(sum);
pushdown(k);
if y<=mid then exit(getsum(lch,x,y))
else if x>mid then exit(getsum(rch,x,y))
else exit(getsum(lch,x,mid)+getsum(rch,mid+,y));
end;
end;
function getsqr(k,x,y:longint):int64;
begin
with t[k] do
begin
if (l=x) and (r=y) then exit(pf);
pushdown(k);
if y<=mid then exit(getsqr(lch,x,y))
else if x>mid then exit(getsqr(rch,x,y))
else exit(getsqr(lch,x,mid)+getsqr(rch,mid+,y));
end;
end; procedure init;
begin
readln(n,m);
for i:= to n do read(a[i]);readln;
build(,,n);
end;
procedure solvechange;
begin
readln(x,y,z);
change(,x,y,z);
end;
function gcd(x,y:int64):int64;
begin
if y= then exit(x) else exit(gcd(y,x mod y));
end;
procedure solveaverage;
begin
readln(x,y);
xx:=getsum(,x,y);yy:=y-x+;
z:=gcd(xx,yy);
if xx= then writeln('0/1')
else writeln(xx div z,'/',yy div z);
end;
procedure solvefangcha;
begin
readln(x,y);
yy:=y-x+;
xx:=yy*getsqr(,x,y)-sqr(getsum(,x,y));
yy:=yy*yy;
z:=gcd(xx,yy);
if xx= then writeln('0/1')
else writeln(xx div z,'/',yy div z);
end; procedure main;
begin
for i:= to m do
begin
read(ch);
case ch of
:solvechange;
:solveaverage;
:solvefangcha;
end;
end;
end; begin
init;
main;
end.
C.皇后游戏
题目：http://www.contesthunter.org/contest/CH%20Round%20%2352%20-%20Thinking%20Bear%20%231%20(NOIP模拟赛)/皇后游戏
题解：不会捉。。。按a排序，骗了30分。。。
代码：
1.我的
const maxn=+;
var a,b,c:array[..maxn] of int64;
ans,sum:int64;
i,j,n,cs:longint;
function max(x,y:int64):int64;
begin
if x>y then exit(x) else exit(y);
end; procedure sort(l,r:longint);
var i,j:longint;x,y:int64;
begin
i:=l;j:=r;x:=c[(i+j)>>];
repeat
while c[i]<x do inc(i);
while c[j]>x do dec(j);
if i<=j then
begin
y:=a[i];a[i]:=a[j];a[j]:=y;
y:=b[i];b[i]:=b[j];b[j]:=y;
y:=c[i];c[i]:=c[j];c[j]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end;
procedure init;
begin
readln(n);
for i:= to n do readln(a[i],b[i]);
for i:= to n do c[i]:=a[i];
end;
procedure main;
begin
sort(,n);sum:=;ans:=;
for i:= to n do
begin
sum:=sum+a[i];
ans:=max(ans,sum)+b[i];
end;
writeln(ans);
end; begin
readln(cs);
while cs> do
begin
dec(cs);
init;
main;
end;
end.
2.标程 也是排序，不过好高大上啊。。。
//#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <set>
#include <algorithm>
#define mp make_pair
#define fi first
#define se second using namespace std; typedef long long int64;
typedef pair<int,int> PII;
const int MAXN=; int n;
PII a[MAXN];
int64 dp[MAXN]; inline bool cmp(const PII &x,const PII &y)
{
return min(x.fi,y.se)<min(x.se,y.fi);
} int main()
{
int testCase;
for (scanf("%d",&testCase);testCase;testCase--)
{
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d%d",&a[i].fi,&a[i].se);
sort(a+,a+n+,cmp);
int64 s=;
for (int i=;i<=n;i++)
{
s+=a[i].fi;
dp[i]=max(s,dp[i-])+a[i].se;
}
cout<<dp[n]<<endl;
}
return ;
}