1、前言
今天是APIO2010的题目，主要目的依旧是练习搜索（当然说是这么说）。感觉总体而言还是可做的，前两道似乎都比较适合骗分。
2、Commando 特别行动队
大概题意：给出一个序列，请划分成若干个子段，要求每一个子段和x变换为ax^2+bx+c后的总和最大。（a,b,c均已知，a<0）
总结：50分的暴力DP还是很好写的，但是由于常数问题可能会被卡成40分，着主要集中在变换值的计算。考试的时候写了个贪心，即根据二次函数的性质，在x=-b/2a存在最大值，故在向前枚举的时候当越过最大值之后可以break掉，而不用枚举到最前面。但是这个正确性明显不足。交到CodeVS上之后我被吓坏了，竟然后6个点全部AC，然而前4个点却WA了。机智的我决定根据数据大小分类讨论，结果评测的时候只有70分，最后3个点全部TLE。后来自己手动测试的时候发现确实T成鬼了，实在膜拜CodeVS的评测速度啊！2.8s的数据跑出了0.4s。
题解：当然这道题是并不存在70分算法的。正解是斜率优化动态规划。【此处待补充！】
代码略。
3、Patrol 巡逻
大概题意：给出一棵树，连k条边（k∈[1,2]），使得从1号节点遍历全图的步数最少。
总结：k=1时固然好写，可以证得求得树上最长链即可（即树的直径），可得30分。而后k=2的情况，考场上没写，但是看其他同学的搞法之后觉得很好，虽然同样是不能保证正确性的贪心，但是分数就好看多了，所以以后还是一样，多想想一些稀奇古怪的得分方式吧。
题解：直接求树的直径（30分）；求出树的直径之后将这条链删除，再次求直径（贪心算法，66分）；树形DP/BFS（100分）。为什么前者只有66分呢？因为选取两个环是要分类讨论的，一种为两个环互不相交，没有重边，也就是贪心所能达到的；还有一种为两个环存在公共边，但是易得这样同样可以转换为一个环的情况，也没有看到什么证明方法，其实画一画就知道了。第二次必须用树形DP。
代码（66分）：
-----------------------------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#define MAXN 100005
int max(int a,int b) { return (a>b)?a:b; }
struct Edge
{
int v,next,flag;
};
Edge edge[MAXN*2];
int h[MAXN],now=1,n,k;
void addEdge(int u,int v)
{
now++;
edge[now].v=v;
edge[now].next=h[u];
h[u]=now;
}
int q[MAXN],vis[MAXN],dep[MAXN],flag[MAXN],nte[MAXN*2],fa[MAXN*2],bye;
void BFS(int now,int c1,int c2)
{
int head=1,tail=2; q[head]=now,vis[now]=1,dep[now]=0;
if (c1) flag[now]=1;
while (head!=tail)
{
for (int x=h[q[head]];x;x=edge[x].next)
{
if (vis[edge[x].v] || edge[x].flag) continue;
nte[edge[x].v]=x,q[tail++]=edge[x].v,vis[edge[x].v]=1;
dep[edge[x].v]=dep[q[head]]+1;
if (c2) fa[x]=nte[q[head]];
if (c1) flag[edge[x].v]=1;
}
head++;
}
}
int s,t,maxDep;
void getDep(int &now)
{
for (int i=1;i<=n;i++) if (maxDep<dep[i]) maxDep=dep[i],now=i;
memset(dep,0,sizeof(dep)),memset(vis,0,sizeof(vis));
}
int work1()
{
BFS(1,0,0),getDep(s),maxDep=0;
BFS(s,0,1),getDep(t);
return n*2-maxDep-1;
}
int work2()
{
int r1=0,r2=0;
BFS(1,0,0),getDep(s),maxDep=0;
BFS(s,0,1),getDep(t);
for (int x=nte[t];x;x=fa[x]) edge[x].flag=edge[x^1].flag=1;
r1=maxDep,maxDep=0;
for (int i=1;i<=n;i++)
if (!flag[i])
{
BFS(i,1,0),getDep(s);
if (!maxDep) continue;
maxDep=0,BFS(s,0,0),getDep(t),r2=max(r2,maxDep),maxDep=0;
if (bye) break;
}
return 2*n-r1-r2;
}
int u,v;
int main()
{
freopen("patrol.in","r",stdin);
freopen("patrol.out","w",stdout);
scanf("%d %d",&n,&k);
for (int i=1;i<=n;i++)
{
scanf("%d %d",&u,&v);
addEdge(u,v),addEdge(v,u);
}
printf("%d",k==1?work1():work2());
return 0;
}
-----------------------------------------------------------------------------------------------------
4、Signaling 信号覆盖
大概题意：给出n个点，每次取其中3个点作外接圆，记录在圆内或圆上的点个数，求所有情况的平均个数。
总结：计算几何，码农题吧。不多去考虑100分情况，直接暴力40分，其实也有差别很大的代码，值得分析一下。其实标准的计算几何代码是需要一大堆预处理的，需要用特殊的形式去表示向量等单位，以及各种操作。但是这道题的话用了可能有点小题大做吧，而我为了熟悉一下还是去用了。那么还是只给出一个比较简洁的代码吧。
题解略。
代码（40分，from z123z123d）：
-----------------------------------------------------------------------------------------------------
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 1510
#define dbl double
using namespace std;
int n, x[M], y[M], s, ans;
dbl ox, oy, r;
void get (int x1, int y1, int x2, int y2, dbl &ux, dbl &uy, dbl &sx, dbl &sy) {
sx = (x1 + x2 + 0.0) / 2, sy = (y1 + y2 + 0.0) / 2;
dbl vx = x2 - x1, vy = y2 - y1;
ux = -vy, uy = vx;
}
int cmp (dbl x, dbl t) {if (t < x + 1e-5 && t > x - 1e-5) return 0; return t - x > 0? -1 : 1;}
dbl dis (dbl x1, dbl y1, dbl x2, dbl y2) {return sqrt ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));}
void sol (dbl a1, dbl b1, dbl c1, dbl a2, dbl b2, dbl c2, dbl &t) {
if (cmp (a1, 0) == 0)
swap (a1, a2), swap (b1, b2), swap (c1, c2);
dbl c = a2 / a1;
b1 *= c, c1 *= c;
t = (c1 - c2) / (b1 - b2);
}
void pre (int a, int b, int c) {
dbl x1, y1, ux, uy, x2, y2, vx, vy, t;
get (x[a], y[a], x[b], y[b], ux, uy, x1, y1);
get (x[b], y[b], x[c], y[c], vx, vy, x2, y2);
sol (ux, -vx, x2 - x1, uy, -vy, y2 - y1, t);
ox = x2 + t * vx, oy = y2 + t * vy, r = dis (x[a], y[a], ox, oy);
}
void check (int k) {
if (cmp (dis (x[k], y[k], ox, oy), r) <= 0) s ++;
}
int main()
{
freopen("signaling.in","r",stdin),freopen("signaling.out","w",stdout);
scanf ("%d", &n);
for (int i = 1; i <= n; i++)
scanf ("%d %d", &x[i], &y[i]);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
for (int k = j + 1; k <= n; k++) {
pre (i, j, k);
s = 0;
for (int t = 1; t <= n; t++)
check (t);
ans += s;
}
printf ("%.3lf", (ans + 0.0) / (n * (n - 1) * (n - 2) / 6));
return 0;
}
-----------------------------------------------------------------------------------------------------