[Usaco2009 Dec]Toll 过路费

[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]建造栅栏

[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

[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 冷冻波

[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 快递服务

[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

[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();
}

[JSOI2010]满汉全席

[JSOI2010]满汉全席

Time Limit:10000MS  Memory Limit:65536K
Total Submit:34 Accepted:21
Case Time Limit:1000MS

Description

满汉全席是中国最丰盛的宴客菜肴,有许多种不同的材料透过满族或是汉族的料理方式,呈现在數量繁多的菜色之中。由于菜色众多而繁杂,只有极少數博学多闻技 艺高超的厨师能够做出满汉全席,而能够烹饪出经过专家认证的满汉全席,也是中国厨师最大的荣誉之一。
世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成,而他们之间还细分为许多不同等级的厨师。为了招收新进的厨师进入世界满汉全席协会,将 于近日举办满汉全席大赛,协会派遣许多会员当作评审员,为的就是要在參赛的厨师之中,找到满汉料理界的明日之星。
大会的规则如下:每位參赛的选手可以得到n 种材料,选手可以自由选择用满式或是汉式料理将材料当成菜肴。大会的评审制度是:共有m 位评审员分别把关。每一位评审员对于满汉全席有各自独特的見解,但基本见解是,要有兩样菜色作为满汉全席的标志。如某评审认为,如果没有汉式东坡肉跟满式 的涮羊肉锅,就不能算是满汉全席。但避免过于有主見的审核,大会规定一个评审员除非是在认为必备的两样菜色都没有做出來的狀况下,才能淘汰一位选手,否则 不能淘汰一位參赛者。换句话說,只要參赛者能在这兩种材料的做法中,其中一个符合评审的喜好即可通过该评审的审查。如材料有猪肉,羊肉和牛肉时,有四位评 审员的喜好如下表:
评审一 评审二 评审三 评审四
满式牛肉 满式猪肉 汉式牛肉 汉式牛肉
汉式猪肉 满式羊肉 汉式猪肉 满式羊肉
如參赛者甲做出满式猪肉,满式羊肉和满式牛肉料理,他将无法满足评审三的要求,无法通过评审。而參赛者乙做出汉式猪肉,满式羊肉和满式牛肉料理, 就可以满足所有评审的要求。
但大会后來发现,在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话,所有的參赛者最多只能通过部分评审员的审查而不是全部,所以可能 会发生没有人通过考核的情形。如有四个评审员喜好如下表时,则不論參赛者采取什么样的做法,都不可能通过所有评审的考核:
评审一 评审二 评审三 评审四
满式羊肉 满式猪肉 汉式羊肉 汉式羊肉
汉式猪肉 满式羊肉 汉式猪肉 满式猪肉
所以大会希望有人能写一个程序來判断,所选出的m 位评审,会不会发生 没有人能通过考核的窘境,以便协会组织合适的评审团。

Input

第一行包含一个数字 K,代表测试文件包含了K 组资料。每一组测试资料的第一行包含兩个数字n 跟m(n≤100,m≤1000),代表有n 种材料,m 位评审员。为方便起見,材料舍弃中文名称而给予编号,编号分别从1 到n。接下來的m 行,每行都代表对应的评审员所拥有的兩个喜好,每个喜好由一个英文字母跟一个数字代表,如m1 代表这个评审喜欢第1 个材料透过满式料理做出來的菜,而h2 代表这个评审员喜欢第2 个材料透过汉式料理做出來的菜。每个测试文件不会有超过50 组测试资料,而每笔测试资料中材料的种类数跟评审员的个数均不超过15。

Output

每笔测试资料输出一行,如果不会发生没有人能通过考核的窘境,输出GOOD;否则输出BAD(大写字母)。

Sample Input

2
3 4
m3 h1
m1 m2
h1 h3
h3 m2
2 4
h1 m2
m2 m1
h1 h2
m1 h2

Sample Output

GOOD
BAD

Source

JSOI2010第二轮Contest2
水题啊。。一眼就看出是2-sat,而且还不需要方案囧。。直接构图然后Tarjan就可以了。。
具体说就是对每个菜建两个节点,一个节点连向另一节点表示选了这个就一定要选那个,比如一个人要求一个汉一个满,如果第一个选了满那么第二个只能是汉了(*^__^*) 。。然后看看有没有两个矛盾的量在一个强联通分量里的就可以了囧。。
Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<stack>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100*2;
struct Edge
{
int t;Edge*next;
Edge(int _t,Edge* _next):t(_t),next(_next){}
}*E[maxn]={0};
void AddEdge(int s,int t){E[s]=new Edge(t,E[s]);}
int n,m;
inline int node(int i,bool j){return i*2+j;}
int low[maxn],ord[maxn],id[maxn],cnt,snt;bool instack[maxn];
stack<int> S;
int dfs(int x)
{
low[x]=ord[x]=++cnt;
S.push(x);instack[x]=true;
for(Edge*e=E[x];e;e=e->next)
if(!ord[e->t]) low[x]=min(low[x],dfs(e->t));
else if(instack[e->t]) low[x]=min(low[x],ord[e->t]);
if(low[x]==ord[x])
{
int u;
do{u=S.top();S.pop();id[u]=snt;instack[u]=false;}while(u!=x);
snt++;
}
return low[x];
}
void Tarjan()
{
memset(ord,0,sizeof(ord));
memset(instack,0,sizeof(instack));
cnt=snt=0;
rep(i,2*n)if(!ord[i])dfs(i);
}
bool Judge()
{
rep(i,n) if(id[2*i]==id[2*i+1])return false;
return true;
}
void solve()
{
scanf("%d %dn",&n,&m);bool c[2];int x[2];char t;
memset(E,0,sizeof(E));
while(m–)
{
rep(i,2)scanf("%c%dn",&t,x+i),–x[i],c[i]=t==’h';
rep(i,2) AddEdge(node(x[i],!c[i]),node(x[1-i],c[1-i]));
}
Tarjan();
if(Judge())cout<<"GOOD"<<endl;
else cout<<"BAD"<<endl;
}
int main()
{
//freopen("in","r",stdin);
int t;cin>>t;while(t–)solve();
}

Vijos 1350 C数列

www.vijos.cn/Problem_Show.asp
话说Vijos的很多题目都有点问题,这个明显有多解的但连解的要求的没有说囧。。
这是经典剪枝问题了。。我欺负题的数据比较小,随便写了几个剪枝就过了(*^__^*)
首先是所有数一定要递增,如果不递增的话更改操作顺序是可以改成递增的,那就没必要重复搜索了。替代性剪枝
其次如果当前最大数超过需要的数了,最优性剪枝。
使用DFSID,如果还能迭代d次,当前最大数*2^d次方小于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,maxn=100;
int n;
int A[maxn];
bool dfs(int p,int d)
{
if(!d)return false;
if(A[p-1]>n||(A[p-1]<<d)<n)return false;
if(A[p-1]==n)return true;
for(int i=p-1;i>=0;–i)
for(int j=i;j>=0;–j)
{
int x=A[i]+A[j];
if(x<=A[p-1])break;
A[p]=x;
if(dfs(p+1,d-1))return true;
}
return false;
}
int main()
{
//freopen("in","r",stdin);
cin>>n;A[0]=1;
for(int i=1;;i++)
if(dfs(1,i))
{
cout<<i<<endl;
rep(j,i)cout<<A[j]<<" ";
cout<<endl;
break;
}
}

[NOI2006]最大获利

[NOI2006]最大获利

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

Description

新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜,需要 做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。
在前期市场调查和站址勘测之后,公司得到了一共N个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需 要投入的成本也是不一样的,所幸在前期调查之后这些都是已知数据:建立第i个通讯中转站需要的成本为Pi(1≤i≤N)。
另外公司调查得出了所有期望中的用户群,一共M个。关于第i个用户群的信息概括为Ai, Bi和Ci:这些用户会使用中转站Ai和中转站Bi进行通讯,公司可以获益Ci。(1≤i≤M, 1≤Ai, Bi≤N)
THU集团的CS&T公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的 中转站才能让公司的净获利最大呢?(净获利 = 获益之和 – 投入成本之和)

Input

输入文件中第一行有两个正整数N和M 。
第二行中有N个整数描述每一个通讯中转站的建立成本,依次为P1, P2, …, PN 。
以下M行,第(i + 2)行的三个数Ai, Bi和Ci描述第i个用户群的信息。
所有变量的含义可以参见题目描述。

Output

你的程序只要向输出文件输出一个整数,表示公司可以得到的最大净获利。

Sample Input

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

Sample Output

4

Hint

【样例说明】
选择建立1、2、3号中转站,则需要投入成本6,获利为10,因此得到最大收益4。
【评分方法】
本题没有部分分,你的程序的输出只有和我们的答案完全一致才能获得满分,否则不得分。
【数据规模和约定】
80%的数据中:N≤200,M≤1 000。
100%的数据中:N≤5 000,M≤50 000,0≤Ci≤100,0≤Pi≤100。

Source

我晕。。我以前的SAP写法都是错的?zkw的程序居然是错的囧。。不过悲剧的是以前的所有题目怎么都能过囧。。NOI的数据果然是NB额。。
即使增广过了边容量已经是0了还要更新高度?我觉得没道理啊。。不过不这样就不能AC。真是活见鬼囧。。
Code:
#include<cstdio>
#include<algorithm>
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=60000,inf=~0U>>1;
struct Edge
{
int t,c;
Edge(int _t,int _c,Edge* _next):
t(_t),next(_next),c(_c){}
Edge*next,*op;
}*E[maxn]={0};
int n,m,vs,vt,v,Ans=0;
void InsEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,0,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
inline int T(int i){return i;}
inline int C(int i){return n+i;}
void Init()
{
scanf("%d%d",&n,&m);int s,t,c;
v=n+m+2;vs=v-1;vt=v-2;
rep(i,n)scanf("%d",&c),InsEdge(T(i),vt,c);
rep(i,m)
{
scanf("%d%d%d",&s,&t,&c);–s;–t;
InsEdge(C(i),T(s),inf);
InsEdge(C(i),T(t),inf);
InsEdge(vs,C(i),c);
Ans+=c;
}
}
int h[maxn],vh[maxn];
int aug(int no,int m)
{
if(no==vt) return m;
int l=m,minh=v;
for(Edge*i=E[no];i;i=i->next)if(i->c)
{
if(h[no]==h[i->t]+1)
{
int d=aug(i->t,min(l,i->c));
i->c-=d,i->op->c+=d,l-=d;
if(!l||h[vs]>=v) return m-l;
}
minh=min(minh,h[i->t]+1);
}
if(!–vh[h[no]]) h[vs]=v;
vh[h[no]=minh]++;
return m-l;
}
int CalFlow()
{
memset(h,0,sizeof(h));
memset(vh,0,sizeof(vh));
vh[0]=v;int flow=0;
while(h[vs]<v) flow+=aug(vs,inf);
return flow;
}
int main()
{
//freopen("in","r",stdin);
Init();
cout<<Ans-CalFlow()<<endl;
}

Page 1 of 712345...Last »