[HAOI2007]反素数ant

Time Limit:10000MS  Memory Limit:165536K
Total Submit:54 Accepted:33
Case Time Limit:1000MS

Description

反质数（ant）
对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足：g(x)>g(i) 0

Input

一个数N（1<=N<=2,000,000,000）。

Output

不超过N的最大的反质数。

Sample Input

1000

Sample Output

840

Source
只能搜呗。。首先素因子最多是前10个，同时各个因子的幂肯定递减。。然后就随便搜了。。实际上还可以加一些剪枝的，比如估价函数之类的，设当前搜到素数p，上限为N，那么显然最多还能将素因子*2^Log（p,N）倍。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxp=1000;
int Ps[maxp],pnt=0,N;
typedef long long ll;
bool IsPrime(int p)
{
if(p==2)return true;
if(p%2==0) return false;
for(int i=3;i*i<=p;i+=2)if(p%i==0) return false;
return true;
}
struct Answer
{
int ans,num;
Answer(){ans=1;num=1;}
void Update(const Answer&a)
{
if(a.ans>ans||(a.ans==ans&&a.num<num)) *this=a;
}
Answer Mul(int x,int c)
{
Answer ret;
ret.ans=ans*(c+1);
ret.num=num*x;
return ret;
}
}Ans;
void GetPrime()
{
for(int i=2;i<maxp&&pnt<9;i++) if(IsPrime(i)) Ps[pnt++]=i;
}
void dfs(int now,int pre,ll N,Answer a)
{
if(N<Ps[now]||now>=pnt||!pre){Ans.Update(a);return;}
ll s=1;rep(i,pre) s*=Ps[now];
for(int i=pre;i>=0;–i)
{
if(s<=N)dfs(now+1,i,N/s,a.Mul(s,i));
s/=Ps[now];
}
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
cin>>N;
GetPrime();
dfs(0,15,N,Answer());
long long k=1;
cout<<Ans.num<<endl;
}

[JSOI2008]Blue Mary的战役地图

Time Limit:10000MS  Memory Limit:165536K
Total Submit:13 Accepted:10
Case Time Limit:1500MS

Description

Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。
由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿 这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。
具体来说，Blue Mary已经将战役地图编码为n*n的矩阵，矩阵的每个格子里面是一个32位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形 矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。

Input

第一行包含一个正整数n。
以下n行，每行包含n个正整数，表示第一张战役地图的代表矩阵。
再以下n行，每行包含n个正整数，表示第二张战役地图的代表矩阵。

Output

仅包含一行。这一行仅有一个正整数，表示这两个矩阵的相似程度。

Sample Input

3
1 2 3
4 5 6
7 8 9
5 6 7
8 9 1
2 3 4

Sample Output

2

Hint

样例解释：

子矩阵：
5 6
8 9
为两个地图的最大公共矩阵

约定：
n<=50

Source

Hash直接秒杀之额。。不过看别人的代码量莫非枚举也能过囧。。
就是玩二维Hash，注意两个seed不要一样就可以了。。
Code 发不上来囧。。说是超过最大长度。。韩度怎么这么LJ囧。。

Current Contest
Past Contests
Scheduled Contests Welcome
WJMZBMR Log Out
Mail:0(0)

[Usaco2009 Dec]Dizzy 头晕的奶牛

Time Limit:10000MS  Memory Limit:65536K
Total Submit:10 Accepted:0
Case Time Limit:1000MS

Description

Input

* 第1行: 三个由空格隔开的正数: N, M1和M2

* 第2到1+M1行: 第i+1行表示第i条单向道路，包含两个由空格隔开的整数: A_i和B_i

* 第2+M1到第1+M1+M2行: 第i+M1+1行表示第i条单向道路，包含两个由空格隔开的整数
X_i和Y_i

Output

* 第1到M2行: 第i行应该包含两个由空格隔开的整数: 根据你给第i条双向道路定义的的方
向，可能是X_i, Y_i，也可能是Y_i, X_i。这些双向道路必须按照输入的顺序
输出。如果无解，在单独的一行内输出"-1"。

Sample Input

4 2 3
1 2
4 3
1 3
4 2
3 2

Sample Output

1 3
2 4
2 3

Source

Gold
囧。。有意思的题目。。我一开始想的是随便找个点dfs，然后按深度连边，明显错的囧。。然后想对每个点dfs一遍求出能通过有向边到达哪些点，那么这些点与这个点连的无向边肯定要正向，结果很明显TLE囧。。要是比赛的话只能按这个骗点分了。。
当我苦思无果头痛万分的时候。。我感觉似乎应该是找某种规则来连边的，什么规则才能没有圈呢？DAG。。拓扑排序！囧。。我们学校春游的时候我就在想这个，春游都没玩好囧。。
Code：

/*
ID: Tom Chen
LANG: C++
TASK: dizzy
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100000;
vector<int> E[maxn];
int In[maxn]={0},ord[maxn],n,m1,m2;
int main()
{
freopen("dizzy.in","r",stdin);
freopen("dizzy.out","w",stdout);
cin>>n>>m1>>m2;int s,t,cnt=0;
rep(i,m1)scanf("%d %d",&s,&t),–s,–t,E[s].pb(t),In[t]++;
queue<int> Q;rep(i,n)if(!In[i]) Q.push(i);
while(Q.size())
{
int t=Q.front();Q.pop();ord[t]=cnt++;
for(vector<int>::iterator i=E[t].begin();i!=E[t].end();i++)
if(!–In[*i]) Q.push(*i);
}
rep(i,m2)
{
scanf("%d %d",&s,&t),–s,–t;
if(ord[s]>ord[t])swap(s,t);
printf("%d %dn",s+1,t+1);
}
}

[Usaco2009 Dec]Toll 过路费

Time Limit:10000MS Memory Limit:65536K
Total Submit:14 Accepted:10
Case Time Limit:1000MS

Description

跟所有人一样，农夫约翰以着宁教我负天下牛，休叫天下牛负我的伟大精神，日日夜夜苦思生
财之道。为了发财，他设置了一系列的规章制度，使得任何一只奶牛在农场中的道路行走，都
要向农夫约翰上交过路费。

农场中由N（1 <= N <= 250）片草地（标号为1到N），并且有M（1 <= M <= 10000）条
双向道路连接草地A_j和B_j（1 <= A_j <= N; 1 <= B_j <= N）。奶牛们从任意一片草
地出发可以抵达任意一片的草地。FJ已经在连接A_j和B_j的双向道路上设置一个过路费L_j
（1 <= L_j <= 100,000）。

可能有多条道路连接相同的两片草地，但是不存在一条道路连接一片草地和这片草地本身。最
值得庆幸的是，奶牛从任意一篇草地出发，经过一系列的路径，总是可以抵达其它的任意一片
草地。

除了贪得无厌，叫兽都不知道该说什么好。FJ竟然在每片草地上面也设置了一个过路费C_i
（1 <= C_i <= 100000）。从一片草地到另外一片草地的费用，是经过的所有道路的过路
费之和，加上经过的所有的草地（包括起点和终点）的过路费的最大值。

任劳任怨的牛们希望去调查一下她们应该选择那一条路径。她们要你写一个程序，接受K（1
<= K <= 10,000）个问题并且输出每个询问对应的最小花费。第i个问题包含两个数字s_i
和t_i（1 <= s_i <= N; 1 <= t_i <= N; s_i != t_i），表示起点和终点的草地。

考虑下面这个包含5片草地的样例图像:

从草地1到草地3的道路的“边过路费”为3，草地2的“点过路费”为5。

要从草地1走到草地4，可以从草地1走到草地3再走到草地5最后抵达草地4。如果这么走的话，
需要的“边过路费”为2+1+1=4，需要的点过路费为4（草地5的点过路费最大），所以总的花
费为4+4=8。

而从草地2到草地3的最佳路径是从草地2出发，抵达草地5，最后到达草地3。这么走的话，边
过路费为3+1=4，点过路费为5，总花费为4+5=9。

Input

* 第1行: 三个空格隔开的整数: N, M和K

* 第2到第N+1行: 第i+1行包含一个单独的整数: C_i

* 第N+2到第N+M+1行: 第j+N+1行包含3个由空格隔开的整数: A_j, B_j和L_j

* 第N+M+2倒第N+M+K+1行: 第i+N+M+1行表示第i个问题，包含两个由空格隔开的整数s_i
和t_i

Output

* 第1到第K行: 第i行包含一个单独的整数，表示从s_i到t_i的最小花费。

Sample Input

Sample Output

Source

Gold

饿。。悲剧。当时的比赛因为要中考没参加囧。。这道题目还是挺有意思的，首先n很小，询问很多只好预处理，预处理不能不想到floyd，不过floyd如果直接按原来的顺序枚举k是搞不出来的囧。。实际上只要按C的顺序枚举k就可以了囧。。
Code：

#include<iostream>#include<cstdio>#include<algorithm>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int inf=~0U>>3,maxn=250;int D[maxn][maxn],Ans[maxn][maxn],n,m,q,C[maxn],P[maxn];void Init(){ cin>>n>>m>>q;rep(i,n)scanf("%d",C+i),P[i]=i;int s,t,c; rep(i,n)rep(j,n)D[i][j]=Ans[i][j]=inf; rep(i,n)D[i][i]=0; rep(i,m)scanf("%d %d %d",&s,&t,&c),–s,–t,D[s][t]=D[t][s]=min(D[s][t],c);}bool cmp(int a,int b){return C[a]<C[b];}inline void Renew(int&x,int c){x=min(x,c);}void Work(){ sort(P,P+n,cmp); rep(t,n) { int k=P[t]; rep(i,n)rep(j,n)if(C[i]<=C[k]&&C[j]<=C[k])Renew(Ans[i][j],D[i][k]+D[k][j]+C[k]); rep(i,n)rep(j,n)Renew(D[i][j],D[i][k]+D[k][j]); } int s,t; rep(i,q)scanf("%d %d",&s,&t),–s,–t,printf("%dn",Ans[s][t]);}int main(){ //freopen("in","r",stdin); Init(); Work();}895 7 2253341 2 31 3 22 5 35 3 15 4 12 4 33 4 41 42 3

[Usaco2008 Oct]建造栅栏

Time Limit:5000MS Memory Limit:65536K
Total Submit:6 Accepted:6
Case Time Limit:1000MS

Description

勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n（4<=n<=2500）的木板，他想把这块本板切成4块。
这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。
注意：

*只要大木板的切割点不同就当成是不同的方案（像全排列那样），不要担心另外的特殊情况，go ahead。

*栅栏的面积要大于0.

*输出保证答案在longint范围内。

*整块木板都要用完。

Input

*第一行：一个数n

Output

*第一行：合理的方案总数

Sample Input

Sample Output

Source

资格赛
饿。。这个本来是要用Dp的。。但我容斥用爽了。。直接上容斥原理(*^__^*)
Code：

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=2600;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;int n,dp[5][maxn]={0};typedef long long ll;ll WaySumTo(int a,int b){ if(a<0)return 0; ll ret=1;a+=–b; rep(i,b) ret*=a-i; rep(i,b) ret/=i+1; return ret;}int main(){ //freopen("in","r",stdin); cin>>n;int a=n/2;if(a*2==n)–a; n-=4; cout<<WaySumTo(n,4)-4*WaySumTo(n-a,4)+6*WaySumTo(n-2*a,4)-4*WaySumTo(n-3*a,4)+WaySumTo(n-4*a,4)<<endl;}

6输出详解：Farmer John能够切出所有的情况为: (1, 1, 1,3); (1, 1, 2, 2); (1, 1, 3, 1); (1, 2, 1, 2); (1, 2, 2, 1); (1, 3,1, 1);(2, 1, 1, 2); (2, 1, 2, 1); (2, 2, 1, 1); or (3, 1, 1, 1).下面四种 — (1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), and (3,1, 1, 1) – 不能够组成一个四边形.6

[Ahoi2009]Seq 维护序列seq

Time Limit:30000MS  Memory Limit:65536K
Total Submit:27 Accepted:13
Case Time Limit:3000MS

Description

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。
有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式：
(1)把数列中的一段数全部乘一个值;
(2)把数列中的一段数全部加一个值;
(3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。

Input

第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式：
操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。
操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。
操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值
(1≤t≤g≤N)。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

Output

对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

Sample Input

7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

Sample Output

2
35
8

Hint

【样例说明】

初始时数列为(1,2,3,4,5,6,7)。
经过第1次操作后，数列为(1,10,15,20,25,6,7)。
对第2次操作，和为10+15+20=45，模43的结果是2。
经过第3次操作后，数列为(1,10,24,29,34,15,16}
对第4次操作，和为1+10+24=35，模43的结果是35。
对第5次操作，和为29+34+15+16=94,模43的结果是8。

测试数据规模如下表所示

数据编号 1 2 3 4 5 6 7 8 9 10
N= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000
M= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000

Source

Day1
这道题一眼就看出是线段树的题目囧。。但是信息很难维护啊囧。。
我一开始想的办法是标记最后一次操作的种类，如果一样的话就标上去，否则就先传递在标上去。但这样肯定是要TLE的囧。。
然后我就想是不是要多维护一点东西，然后我发现好像维护“先乘a，再加b”这样的信息是可以传递的囧。。程序慢的跟鬼一样囧。
PS。。最近最后一次刷题目了。要去参加数学竞赛了囧。。4月中旬再回来吧。。
原来我是很鄙视宏的，觉得影响可读性，现在才理解用宏的人的心情，真是。TMD太爽了囧。。

Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100000;
typedef long long ll;
ll sum[maxn*3],A[maxn],mod;
int n;
struct Mark
{
ll mul,plus;
bool operator==(const Mark&o)const
{return mul==o.mul&&plus==o.plus;}
Mark(ll _mul=1,ll _plus=0):mul(_mul),plus(_plus){}
}none,mark[maxn*3];
void Plus(ll&a,ll b){a+=b;a%=mod;}
void Mul(ll&a,ll b){a*=b;a%=mod;}
#define Tree int t,int l,int r
#define This t,l,r
#define Left t*2,l,(l+r)/2
#define Right t*2+1,(l+r)/2,r
void MarkIt(Tree,Mark m)
{
Mul(sum[t],m.mul);Plus(sum[t],(r-l)*m.plus);
Mul(mark[t].mul,m.mul);Mul(mark[t].plus,m.mul);Plus(mark[t].plus,m.plus);
}
void PushDown(Tree)
{
if(mark[t]==none)return;
MarkIt(Left,mark[t]),MarkIt(Right,mark[t]),mark[t]=none;
}
void Build(Tree)
{
mark[t]=none;
if(l+1==r){sum[t]=A[l];return;}
Build(Left);Build(Right);
sum[t]=(sum[t*2]+sum[t*2+1])%mod;
}
void Change(Tree,int a,int b,Mark m)
{
if(l>=b||r<=a)return;
if(l>=a&&r<=b){MarkIt(This,m);return;}
PushDown(This);
Change(Left,a,b,m);Change(Right,a,b,m);
sum[t]=sum[t*2]+sum[t*2+1];sum[t]%=mod;
}
ll Ask(Tree,int a,int b)
{
if(l>=b||r<=a)return 0;
if(l>=a&&r<=b) return sum[t];
PushDown(This);
return (Ask(Left,a,b)+Ask(Right,a,b))%mod;
}
int main()
{
//freopen("in","r",stdin);
scanf("%d %d",&n,&mod);
rep(i,n) scanf("%d",A+i);
Build(1,0,n);
int m,l,r,c,x;scanf("%d",&m);
rep(i,m)
{
scanf("%d %d %d",&x,&l,&r);
switch(x)
{
case 1:scanf("%d",&c),Change(1,0,n,l-1,r,Mark(c,0));break;
case 2:scanf("%d",&c),Change(1,0,n,l-1,r,Mark(1,c));break;
case 3:printf("%dn",Ask(1,0,n,l-1,r));break;
}
}
}

[JSOI2010]Frozen Nova 冷冻波

Time Limit:10000MS  Memory Limit:65536K
Total Submit:77 Accepted:22
Case Time Limit:1000MS

Description

WJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能Frozen Nova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。
当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫 妖就可以瞬间杀灭一个小精灵。
在森林里有N个巫妖，每个巫妖释放Frozen Nova之后，都需要等待一段时间，才能再次施放。不同的巫妖有不同的等待时间和施法范围，但相同的是，每次施放都可以杀死一个小精灵。
现在巫妖的头目想知道，若从0时刻开始计算，至少需要花费多少时间，可以杀死所有的小精灵？

Input

输入文件第一行包含三个整数N、M、K(N,M,K<=200)，分别代表巫妖的数量、小精灵的数量和树木的数量。
接下来N行，每行包含四个整数x, y, r, t，分别代表了每个巫妖的坐标、攻击范围和施法间隔（单位为秒）。
再接下来M行，每行两个整数x, y，分别代表了每个小精灵的坐标。
再接下来K行，每行三个整数x, y, r，分别代表了每个树木的坐标。
输入数据中所有坐标范围绝对值不超过10000，半径和施法间隔不超过20000。

Output

输出一行，为消灭所有小精灵的最短时间（以秒计算）。如果永远无法消灭所有的小精灵，则输出-1。

Sample Input

2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10

Sample Output

5

Source

JSOI2010第二轮Contest1

JSOI2010第二轮Contest161.187.179.132:8080/JudgeOnline/showproblem
由于文章过长就不贴题目了囧。。变态题。。JSOI2010 Contest1中最难的了囧。写的半死囧还WA几次。
题意太恶心了啊，就是目光与树相交也算看到囧。。
我的代码慢的跟鬼一样囧。。
很显然要二分答案然后判断，判断的话网络流随便建个图就可以了。。
关键是计算几何部分，太恶心了囧。。
关键是一条线与不与一个圆相交，首先算出圆心到这个线的距离，然后跟半径比较一下，
点到线段的距离怎么求呢？就是这个点跟线段两端点组成三角形的面积除以底边长，面积用叉积算就可以了。。
Code：百度太垃圾了，长点的代码就发不了囧。。
只好放ideone上了囧。。
www.ideone.com/erv1eoAI

水平太懒了。。做的都是水题囧。。。。
今天再整理一点。。。
ZJ
[ZJOI2006]
[ZJOI2006]物流运输trans
dp+spfa
[ZJOI2007]
[ZJOI2007]最大半连通子图
强联通+dp
[ZJOI2007]棋盘制作
变相的最大空子矩阵问题。。
[ZJOI2007]仓库建设
dp优化，决策单调性或斜率优化。。
[ZJOI2007]报表统计
数据结构模拟，set+heap
[ZJOI2008]
[ZJOI2008]骑士
tree dp
[ZJOI2008]生日聚会Party
dp..感觉当时我是想维护这个信息的线段树想到的dp。。dp的关键在于可以转移啊，不能转移的状态只能撞死囧。。
[ZJOI2010]
[ZJOI2010]count 数字计数
还算简单的数位统计问题。。
SC
[SCOI2009]迷路
状态打包的矩阵乘法，很巧妙额。。
[SCOI2003]字符串折叠
关于压缩的Dp。。Easy。
[SCOI2007]压缩
关于压缩的Dp。。Hard。
[Scoi2010]传送带
这道太水了，怎么做都行，模拟退火吧
[Scoi2010]序列操作
有点恶心的线段树经典题。。代码我最短嘻嘻。。
[SCOI2009]生日快乐
直接爆搜。。。
[SCOI2007]蜥蜴
相当水的网络流。。。
[SCOI2008]着色方案
状态压缩DP
[SCOI2005]最大子矩阵
DP….
[SCOI2009]游戏
比较巧妙的DP。。。
[SCOI2009]生日礼物
熟练使用Heap。。。
[SCOI2009]最长距离
01权图的最短路径问题。。。

[JSOI2010]Express Service 快递服务

Time Limit:10000MS  Memory Limit:65536K
Total Submit:84 Accepted:20
Case Time Limit:1000MS

Description

「飞奔」快递公司成立之后，已经分别与市内许多中小企业公司签订邮件收送服务契约。由于有些公司是在同一栋大楼内，所以「飞奔」公司收件的地点（收件点） 最多只有m点 (1, 2, …, m)，因此「飞奔」仅先行采购了三辆货車并聘用了三名司机，每天早上分别从收件地点 「1」, 「2」 及 「3」出发。而在与客户的服务契约中有明确订约：「飞奔」必须在客户提出邮件寄送要求的隔天派人至该公司（地点）收件。
为了能更有效率的服务客户并节省收件时间，该公司设立了收件服务登记网站，客户如有邮件需要寄送，必须在需要收件的前一天就先上网登记。为了节省 油量，「飞奔」就利用晚上先行安排三位司机隔天的收件路线。每位司机至各地点收件的顺序应与各公司上网登记的顺序相符且必须能在最省油的情况下完成当天所 有的收件服务。因此每位司机有可能需要在不同时间重复到同一地点收件，或不同的司机有可能需在不同的时间点前往同一地点收件。
如下面范例二(收件公司地点依序为： 4 2 4 1 5 4 3 2 1)所示，虽然司机1一开始就已经在收件地点「1」了，但是他却不能先把后面第四个登记的公司（地点「1」）邮件先收了再前往第一、第二、或第三个登记收 件地点（地点「4」,「2」,「4」）收件。但是如果前三个登记收件的服务是由司机2或3來负责，则司机1就可以在地点「1」收了第四个登记的邮件后再前 往后面所登记的地点收件。此外，在某些情况下，不一定每辆车都要收到货，也就是說，最佳收件方式也有可能是只需出动一或兩辆车去收货。请写一个程序來帮 「飞奔」公司计算每天依预约顺序至各收件地点收件的最少总耗油量。

Input

输入文件第一行有一个整数 m（3 < = m < = 200），代表「飞奔」公司收件的地点数，以1至m之间的整数代号來表示每个地点。
接下來的m行（第2到第m+1行），每行有m个整数，代表一个矩阵D。第 i +1行的第 j 个整数是D(i, j)，D(i, j) 代表司机开车从收件点 i 到收件点 j 所需耗油量。最后有一行数串，数串之数字依序为前一天上网登记要求收件的公司地点代号，最多会有1000个收件请求。输入文件中任兩个相邻的整数都以一个 空白隔开。 //D(i,j)<=maxint
注意：油量矩阵D满足三角不等式，也就是說 D(i, j) < = D(i, k) + D(k, j)，1 < = i, j, k < = m。因此，每辆车前往下一个收件地点时一定是直接前往，不必先绕道至其它地点再抵达下个收件地点。

Output

输出一个整数，代表收件所需最少总耗油量。

Sample Input

4
0 5 0 6
6 0 5 6
1 6 0 6
1 1 1 0
1 1 1 1 4 4 2 2 2 3

Sample Output

6

样例说明：到每个请求收件地点的司机分别为1 1 1 1 3 3 2 2 2 1，因此司机1只需从起使点1移动到地点3，司机2只需停留在地点2，司机3从起始点3移动到地点4。

Source

JSOI2010第二轮Contest1
这题肯定是要Dp的，关键是状态，记录Dp(i,j,k)表示前i个订单，一个车在第i个订单的位置，另一个在第j个位置，另一个在第k个位置时的最小收入，那么直接Dp就OK了。。
一开始我看到那个D(i,j)<=maxint以为要用long long，结果TLE，其实这个maxint就是max integer的意思囧。。所以int就可以了。。
实际上还能再快1倍的，因为另外两辆的顺序是无所谓的，所以状态数还可以减少一半，不过懒得了囧。。

Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=200+10,maxp=1000+10;
const int inf=~0U>>1;
int Dist[maxn][maxn];
int Dp[2][maxn][maxn];
int A[maxp],n,p=0;
void Init()
{
scanf("%d",&n);
rep(i,n) rep(j,n)scanf("%d",&Dist[i][j]);
A[p++]=0;
while(scanf("%d",A+p)==1)–A[p++];
}
inline void Update(int&x,int c){x=min(x,c);}
void Work()
{
int now=0,next=1;int cost;
rep(j,n) rep(k,n) Dp[next][j][k]=inf;
Dp[next][1][2]=0;
rep(i,p-1)
{
swap(now,next);
rep(j,n) rep(k,n) Dp[next][j][k]=inf;
rep(j,n) rep(k,n) if((cost=Dp[now][j][k])!=inf)
{
//use the car in previous place
Update(Dp[next][j][k],cost+Dist[A[i]][A[i+1]]);
//use other two car
Update(Dp[next][A[i]][j],cost+Dist[k][A[i+1]]);
Update(Dp[next][A[i]][k],cost+Dist[j][A[i+1]]);
}
}
int Ans=inf;
rep(j,n) rep(k,n) Update(Ans,Dp[next][j][k]);
cout<<Ans<<endl;
}
int main()
{
//freopen("in","r",stdin);
Init();
Work();
}

[JSOI2010]Group 部落划分 Group

Time Limit:10000MS  Memory Limit:65536K
Total Submit:85 Accepted:33
Case Time Limit:1000MS

Description

聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间 则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。

不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了N个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附 近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了K个部落！这真是个好消 息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法：

对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。
例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。

Input

第一行包含两个整数N和K(1<=N<=1000,1

Output

输出一行，为最优划分时，最近的两个部落的距离，精确到小数点后两位。

Sample Input

4 2
0 0
0 1
1 1
1 0

Sample Output

1.00

Source

JSOI2010第二轮Contest1
被ZJOI的题目虐死了囧。。那个Risk计算几何太变态了
这题好水啊囧。。把所有距离排个序。用并查集维护连通性就可以了囧。。
顺便Orz一下中国脑筋神牛，神牛切题真是太神速了
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<utility>
#include<cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=1000+10;
typedef pair<int,int> ii;
typedef pair<int,ii> Edge;
Edge Es[maxn*maxn/2];
ii P[maxn];
int F[maxn];
int find(int x){return x==F[x]?x:(F[x]=find(F[x]));}
int n,k,cnt=0;
int Dist(ii a,ii b)
{
int x=a.first-b.first,y=a.second-b.second;
return x*x+y*y;
}
void Init()
{
scanf("%d %d",&n,&k);
rep(i,n) scanf("%d %d",&P[i].first,&P[i].second),F[i]=i;
rep(i,n) rep(j,i) Es[cnt++]=Edge(Dist(P[i],P[j]),ii(i,j));
}
void Work()
{
sort(Es,Es+cnt);Edge*i=Es;
while(true)
{
int a=i->second.first,b=i->second.second;
a=find(a),b=find(b);
if(a!=b)
{
if(n>k) F[a]=b,–n;
else{printf("%0.2lfn",sqrt(i->first));break;}
}
++i;
}
}
int main()
{
//freopen("in","r",stdin);
Init();
Work();
}