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