[HAOI2008]圆上的整点

Time Limit:10000MS  Memory Limit:165536K
Total Submit:68 Accepted:22
Case Time Limit:1000MS

Description

求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。

Input

r

Output

整点个数

Sample Input

4

Sample Output

4

Hint

n<=2000 000 000

Source
额，我去查了查勾股数的生成方法，发现是这个样子的，
（n，m）=1,(n^2-m^2)^2+(2mn)^2=(n^2+m^2)^2。。同时三项全部乘个啥就可以推到所有数，所以首先枚举r/（n,m），再枚举n和m，再用个set去重就OK了。。
Code：

#include<iostream>
#include<set>
#include<utility>
using namespace std;
long long r,n,m;
typedef pair<int,int> ii;
set<ii> S;
int Cal(int d)
{
long long r=::r/d;
n=1,m=1;while(m*m<r)m++;
while(n<m)
{
while(n<m&&n*n+m*m>r)m–;
if(n>=m)break;
if(n*n+m*m==r){int a=m*m-n*n,b=2*m*n;S.insert(ii(a*d,b*d));S.insert(ii(b*d,a*d));}
n++;
}
}
int main()
{
cin>>r;int d;
for(d=1;d*d<r;d++)if(r%d==0) Cal(r/d)+Cal(d);
if(d*d==r)Cal(d);
cout<<S.size()*4+4<<endl;
}

[HAOI2008]玩具取名

Time Limit:10000MS  Memory Limit:165536K
Total Submit:45 Accepted:34
Case Time Limit:1000MS

Description

某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个 字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。
现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。

Input

第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。
接下来W行，每行两个字母,表示W可以用这两个字母替代。
接下来I行，每行两个字母,表示I可以用这两个字母替代。
接下来N行，每行两个字母,表示N可以用这两个字母替代。
接下来G行，每行两个字母,表示G可以用这两个字母替代。
最后一行一个长度不超过Len的字符串。表示这个玩具的名字。

Output

一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出）
如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”

Sample Input

1 1 1 1
II
WW
WW
IG
IIII

Sample Output

IN

Hint

W可以变成II所以IIII可以缩成WW
IN均能变成WW所以WW又可以缩成I或者N
所以最终答案应该按照“WING”的顺序输出IN

[数据范围]
30%数据满足Len<=20，W、I、N、G<=6
100%数据满足Len<=200，W、I、N、G<=16

Source
水题啊。。直接Dp就可以了，Check（l，r，a）表示第l个到第r能否用第a个字母扩充出来
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,maxl=200+1;
int Map[256],D[4],L[4][16],R[4][16];
char Name[10]="WING";
char str[maxl];
bool S[maxl][maxl][4]={0};
bool Dp[maxl][maxl][4];
bool Check(int l,int r,int a)
{
bool&x=Dp[l][r][a];
if(S[l][r][a]) return x;
S[l][r][a]=true;
if(l==r) return x=(str[l]==Name[a]);
for(int k=l;k<r;k++)
rep(i,D[a]) if(Check(l,k,L[a][i])&&Check(k+1,r,R[a][i])) return x=true;
return x=false;
}
int main()
{
//freopen("in","r",stdin);
Map[‘W’]=0;Map[‘I’]=1;Map[‘N’]=2;Map[‘G’]=3;
rep(i,4)cin>>D[i];char l,r;
rep(i,4)rep(j,D[i]) cin>>l>>r,L[i][j]=Map[l],R[i][j]=Map[r];
cin>>str;int len=strlen(str);bool c=false;
rep(i,4)if(Check(0,len-1,i))cout<<Name[i],c=true;
if(!c)cout<<"The name is wrong!";
}

SCOI2007]蜥蜴

Time Limit:1000MS  Memory Limit:165536K
Total Submit:44 Accepted:29

Description

在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。
每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开 的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只 蜥蜴在同一个石柱上。

Input

输入第一行为三个整数r，c，d，即地图的规模与最大跳跃距离。以下r行为石竹的初始状态，0表示没有石柱，1~3表示石柱的初始高度。以下r行为蜥蜴位 置，“L”表示蜥蜴，“.”表示没有蜥蜴。

Output

输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。

Sample Input

5 8 2
00000000
02000000
00321100
02000000
00000000
……..
……..
..LLLL..
……..
……..

Sample Output

1

Hint

100%的数据满足：1<=r, c<=20, 1<=d<=3

Source

Pku 2711 Leapin’ Lizards
有点水的网络流，直接拆点构图就可以了。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
const int inf=~0U>>1,maxn=20,maxv=maxn*maxn*2+2;
int n,m;
inline int In(int i,int j){return (i*m+j)*2;}
inline int Out(int i,int j){return In(i,j)+1;}
struct Edge
{
int t,c;
Edge*next,*op;
Edge(int _t,int _c,Edge*_next):t(_t),c(_c),next(_next){}
}*E[maxv]={0};
int h[maxv],vh[maxv],vs,vt,v;
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];
}
int aug(int no,int m)
{
if(no==vt) return m;
int l=m;
for(Edge*i=E[no];i;i=i->next)if(i->c&&h[no]==h[i->t]+1)
{
int d=aug(i->t,min(i->c,l));
l-=d,i->c-=d,i->op->c+=d;
if(l==0||h[vs]>=v)return m-l;
}
int minh=v;
for(Edge*i=E[no];i;i=i->next)if(i->c&&h[i->t]+1<minh)
minh=h[i->t]+1;
if(–vh[h[no]]==0) 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;
}
inline int Dist(ii a,ii b){return abs(a.first-b.first)+abs(a.second-b.second);}
inline int DistToExit(int x,int y){return min(x+1,min(n-x,min(y+1,m-y)));}
int main()
{
//freopen("in","r",stdin);
int x,d,a=0;char c;cin>>n>>m>>d;v=n*m*2+2;vs=v-1;vt=vs-1;
rep(i,n)rep(j,m){cin>>c;x=c-‘0’;if(x)InsEdge(In(i,j),Out(i,j),x);}
rep(i,n)rep(j,m){cin>>c;if(c==’L’) InsEdge(vs,In(i,j),1),a++;}
rep(i,n)rep(j,m)rep(a,n)rep(b,m)if(Dist(ii(i,j),ii(a,b))<=d) InsEdge(Out(i,j),In(a,b),inf);
rep(i,n)rep(j,m)if(DistToExit(i,j)<=d) InsEdge(Out(i,j),vt,inf);
cout<<a-CalFlow()<<endl;
}

[SCOI2008]着色方案

Time Limit:10000MS  Memory Limit:165536K
Total Submit:20 Accepted:16
Case Time Limit:1000MS

Description

有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。所有油漆刚好足够涂满所有木块，即 c1+c2+…+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。

Input

第一行为一个正整数k，第二行包含k个整数c1, c2, … , ck。

Output

输出一个整数，即方案总数模1,000,000,007的结果。

Sample Input

3
1 2 3

Sample Output

10

Hint

【样例2】
Input
5
2 2 2 2 2
Output
39480
【样例3】
Input
10
1 1 2 2 3 3 4 4 5 5
Output
85937576
数据规模】
50%的数据满足：1 <= k <= 5, 1 <= ci <= 3
100%的数据满足：1 <= k <= 15, 1 <= ci <= 5

Source
这题一看就知道是要Dp的，而且状态很麻烦，好在c最大只有5，所以可以用一个6维数组表示
，就是第i个表示当前还有i个的颜色还有几个，还要一个Last表示最后一个是哪个颜色。然后用
Hash表存储状态就可以了。。unsigned long long中的-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;
const int inf=~0U>>1,c=6,seed=17,mod=1000000007,size=17771;
typedef unsigned long long ull;
int n;
struct State
{
int Num,Last;
State(){memset(Num,0,sizeof(Num));}
ull HashCode() const
{
ull ret=0;
rep(i,c) ret*=seed,ret+=Num[i];
ret*=seed;return ret+=Last;
}
State Next()
{
State s=*this;
s.Num[Last]–;s.Num[Last-1]++;return s;
}
bool Legal(){return Num[Last]>0&&Last>0;}
void operator=(const State&o)
{
memcpy(Num,o.Num,sizeof(Num));
Last=o.Last;
}
};
struct Hash
{
struct Node
{
ull key,Count;
Node*next;
Node(ull _key,Node*_next):key(_key),next(_next),Count(-1){}
}*H[size];
Hash(){memset(H,0,sizeof(H));}
ull& Find(const State&a)
{
ull code=a.HashCode(),h=code%size;
for(Node*i=H[h];i;i=i->next)if(i->key==code) return i->Count;
return H[h]=new Node(code,H[h]),H[h]->Count;
}
}H;
ull dfs(State S,int Left)
{
ull&x=H.Find(S);if(x!=-1) return x;
if(!S.Legal()) return x=0;
if(Left==1) return x=1;
x=0;
State NewS=S.Next();
for(int i=1;i<c;i++)
{
NewS.Last=i;
if(i!=S.Last&&S.Num[i])
{
x+=S.Num[i]*dfs(NewS,Left-1);
x%=mod;
}
if(i==S.Last&&S.Num[i]>1)
{
x+=(S.Num[i]-1)*dfs(NewS,Left-1);
x%=mod;
}
}
return x;
}
int main()
{
//freopen("in","r",stdin);
State now;ull ans=0;
int n,x,s=0;cin>>n;rep(i,n) cin>>x,now.Num[x]++,s+=x;
rep(i,c) now.Last=i,ans+=now.Num[i]*dfs(now,s),ans%=mod;
cout<<ans<<endl;
}

       好吧我开学一个月了才写开学感言确实有点晕。。
OK，开学一个月了，感觉跟鬼一样，话说我们这里已经中考考完了，然后我这个CLJ进了LJ班晕，实际上也没什么，男女比例3：1也没什么，班里帅哥还真是多，我这样下去要变BL了天哪。。。开学了还是无聊，有时候还能见到原来的同学，好吧我觉得也就这样了，我越来越觉得人生来就孤独了，没什么要紧的，没心没肺啊没心没肺。
文化节我们班MS悲剧了，不过压根就没人鸟这事，文化节越来越像作秀，不是跳脱衣舞就是抛绣球还有拜堂成亲的，好吧附近两个班欺负我们班没有女生都在抛绣球晕，我受捕鸟了就溜掉了。换票？居然有人问我要不要换票，我特蔑视地看了她一眼囧。。
还有什么辩论赛，初中辩论的时候我就觉得很火，辩论经典文学通俗化利大于弊否？这件事有什么利弊的，不过是分个档次而已，通俗了说白了实际上就叫儿童文学了，不过没人逼你去看儿童文学，给儿童看看也是好事。我当时想去骂的，不过有点懒得，就去机房上机了。。
那个整个下午的什么狗屁京剧我都想吐了，京剧都成什么样子了，天哪，杂技+武功？看不下去。。看了一下午的电子书。。晚上的节目倒不错，尤其是那个雷雨，雷到我了。。曹禺老先生一定有恋母情节。。
昨天就去春游了晕，春游？好古老。青春青春，青年人发春？我太老了发不了春了，只能发疯，在西溪湿地逛了一圈特无聊，玩了玩沼泽探险小游戏晕。中午之后还有人风筝DIY的小游戏，我弄了半天最后火了把耳机线放在后面结果居然飞起来了真强。。。其他也没什么好玩的，东西死贵也就罢了，连个卖风筝，卖水枪的都没有晕。。
额，谈恋爱？说到底就是看人家长的漂亮晕，我早就不相信爱情了。。
最后说说编程什么的，我愈发感觉我原来的风格都可以去死了，程序说白了就是不要错，错了就0分，时间空间关系都不大，所以写起来也就是要方便调试，方便修正，我原来华丽花哨的编法真是垃圾，现在我init之类的函数都懒得写了，没意义。最近在刻苦钻间gdb，调试真的很重要，很多时候可以节省大量的时间。我NOIP就是栽在这上面了。

[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