一个上午都在思考人生（实际上是为不会写而发愁），想着不会写倒是没关系，下午改就可以了。
然后就很煎熬。
没交所以没有成绩。
2908. 矩阵乘法(mat) (Standard IO)
Time Limits: 2000 ms Memory Limits: 262144 KB Detailed Limits Goto ProblemSet
这道题，文不对题（kusa）。
方法是 整体二分+二维树状数组。
没写过整体二分，大致讲一下：
整体二分类似于一些决策单调性分治，可以用来解决诸多区间第k小/大问题。
solve(l,r,L,R)表示答案在[l,r]中，操作与[L,R] 有关。
就是对询问区间和值域二分，然后分别讨论对答案的贡献，也是用树状数组求前缀和来解决。
搞不过洛谷的究极卡常，最后吸氧气快了1s多
具体看代码吧。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int inf=1e9;
4 const int N=510;
5 const int N2=250010;
6 const int Q=6e4+10;
7 int n,qq,cnt;
8 int ma[N][N],ans[Q];
9 struct node{
10 int x1,y1,x2,y2,k,id;
11 }q[Q+N2],q1[Q+N2],q2[Q+N2];
12 int a[N][N];
13 inline int lb(int x){return x&(-x);}
14 inline void add(int x,int y,int z){
15 for(register int i=x;i<=n;i+=lb(i)){
16 for(register int j=y;j<=n;j+=lb(j)){
17 a[i][j]+=z;
18 }
19 }
20 }
21 inline int query(int x,int y){
22 if(!x||!y) return 0;
23 int ans=0;
24 for(register int i=x;i;i-=lb(i)){
25 for(register int j=y;j;j-=lb(j)){
26 ans+=a[i][j];
27 }
28 }
29 return ans;
30 }
31 inline int get_sum(int x1,int y1,int x2,int y2){
32 return query(x2,y2)+query(x1-1,y1-1)-query(x1-1,y2)-query(x2,y1-1);
33 }
34 void solve(int l,int r,int L,int R){
35 if(L>R) return;
36 if(l==r){
37 for(register int i=L;i<=R;i++){
38 if(q[i].id){
39 ans[q[i].id]=l;
40 }
41 }
42 return;
43 }
44 int mid=(l+r)>>1,cnt1=0,cnt2=0;
45 for(register int i=L;i<=R;i++){
46 if(q[i].id==0){//change
47 if(q[i].k<=mid){
48 add(q[i].x1,q[i].y1,1);//如果在答案区间左边，会对后面做出1点贡献
49 q1[++cnt1]=q[i];
50 }
51 else{
52 q2[++cnt2]=q[i];
53 }
54 }
55 else{//query
56 int tmp=get_sum(q[i].x1,q[i].y1,q[i].x2,q[i].y2);
57 if(tmp>=q[i].k){
58 q1[++cnt1]=q[i];
59 }
60 else{
61 q[i].k-=tmp;//在另一个区间查区间第k-tmp小
62 q2[++cnt2]=q[i];
63 }
64 }
65 }
66 for(register int i=1;i<=cnt1;i++){
67 if(!q1[i].id){
68 add(q1[i].x1,q1[i].y1,-1);
69 }
70 }
71 for(register int i=L;i<=L+cnt1-1;i++){
72 q[i]=q1[i-L+1];
73 }
74 for(register int i=L+cnt1;i<=R;i++){
75 q[i]=q2[i-L-cnt1+1];
76 }
77 solve(l,mid,L,L+cnt1-1);
78 solve(mid+1,r,L+cnt1,R);
79 }
80 int read(){
81 int x=0,f=1;
82 char c=getchar();
83 while(!isdigit(c)){
84 if(c=='-') f=-1;
85 c=getchar();
86 }
87 while(isdigit(c)){
88 x=x*10+c-'0';
89 c=getchar();
90 }
91 return x*f;
92 }
93 int main(){
94 n=read(),qq=read();
95 for(register int i=1;i<=n;i++){
96 for(register int j=1;j<=n;j++){
97 ma[i][j]=read();
98 q[++cnt]=(node){i,j,0,0,ma[i][j],0};
99 }
100 }
101 for(register int i=1;i<=qq;i++){
102 cnt++;
103 q[cnt].x1=read(),q[cnt].y1=read(),q[cnt].x2=read(),q[cnt].y2=read(),q[cnt].k=read();
104 q[cnt].id=i;
105 }
106 solve(0,inf,1,cnt);
107 for(register int i=1;i<=qq;i++){
108 printf("%d\n",ans[i]);
109 }
110 return 0;
111 }
3410. 【GDOI2014模拟】Tree (Standard IO)
Time Limits: 2000 ms Memory Limits: 262144 KB Detailed Limits看到这题以为是LCT，实际上没有那么难。
这道题的思想很巧妙，以0.25为一个单位来确定一个伪平均数，让所有边权值减去这个值并平方，以此建最小生成树，这样可以近似的减小差值，使当前答案贴近最终答案，再根据确定好的最小生成树重新算出真正的平均值，更新答案即可。
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,m;
4 double minans=1e9;
5 double maxc=0;
6 const int N=2e3+10;
7 struct edge{
8 int x,y,id;
9 double w;
10 }a[N],b[N];
11 int f[N];
12 bool cmp(edge t1,edge t2){
13 return t1.w<t2.w;
14 }
15 int findf(int x){
16 return f[x]==x?x:f[x]=findf(f[x]);
17 }
18 queue<double> k;
19 int main(){
20 scanf("%d%d",&n,&m);
21 for(int i=1;i<=m;i++){
22 cin>>a[i].x>>a[i].y>>a[i].w;
23 a[i].id=i;
24 maxc=max(maxc,a[i].w);
25 }
26 for(double i=0;i<=maxc;i+=0.25){
27 double ans=0;
28 double num=0;
29 for(int j=1;j<=n;j++) f[j]=j;
30 for(int j=1;j<=m;j++){
31 b[j]=a[j];
32 b[j].w=(a[j].w-i)*(a[j].w-i);
33 }
34 sort(b+1,b+m+1,cmp);
35 for(int j=1;j<=m;j++){
36 if(findf(b[j].x)!=findf(b[j].y)){
37 num+=a[b[j].id].w;
38 k.push(a[b[j].id].w);
39 f[findf(b[j].x)]=findf(b[j].y);
40 }
41 }
42 num/=(n-1);
43 while(!k.empty()){
44 ans+=(k.front()-num)*(k.front()-num);
45 k.pop();
46 }
47 minans=min(minans,sqrt((double)ans/(n-1)));
48 }
49 printf("%.4f",minans);
50 return 0;
51 }
Points and Segments (Standard IO)
Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits Special Judge Time Remaining: 00:00:00第一眼以为是网络流或者差分约束之类的，结果居然是欧拉回路……
表示并没有学过，开始学一学。
引用内容来源于OIWIKI
定义
通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。
通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。
具有欧拉回路的图称为欧拉图。
具有欧拉通路的图称为半欧拉图。
有向图的时候可以类似地定义。
性质
欧拉图中所有顶点的度数都是偶数。
若G是欧拉图，则它若干个边不重的圈的并。
判别法
G是欧拉图当且仅当G是连通的且没有奇度定点。
G是半欧拉图当且仅当G中恰有两个奇度定点。
对于这道题，我们将数据离散化，由线段端点从小到大连接无向边，最后将所有奇点（度数为奇数的点）从小到大排序，一共有偶数个，由1到2,3到4连边，最后跑一遍欧拉回路就能得到一组可行解。这个做法可以证明一定是正确的：
我们将欧拉图上的点放到坐标轴上，因为欧拉图的每一个点度数均为偶数，因此：
1.对于一个点，以它为端点的边一定有偶数条（两条以它为端点的线段可以看做一条跨过它的边，虽然要计算两次），跨过它的边一定有偶数条，否则无法构成欧拉回路。
2.对于任意一个奇点，增加连边后不会让它超出答案范围（感性理解下）
以上两点都是瞎说的，yy一下即可。
不写了。
总结：明天要不要听计算几何呢？感觉很有意思，但是又想打比赛。