[JSOI2009]Count

Time Limit:10000MS  Memory Limit:65536K
Total Submit:16 Accepted:15
Case Time Limit:1000MS

Description

Input

Output

Sample Input

Sample Output

1
2

Hint

Source

JSOI2009Day1
61.187.179.132:8080/JudgeOnline/showproblem

我已经菜到只会做水题了。。又看了两道题。。都不会囧。。只好把题目按通过人数排序了一下囧。。
这道题不知道有没有什么更好的办法。我不管三七二十一直接上二维树状数组了。二维树状数组本质上跟一维的也差不多。。就是对每个颜色都维护一个树状数组，然后其他就好说了。。
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=301,maxc=100;
int n,m;
struct Board
{
int C[maxn][maxn];
Board(){memset(C,0,sizeof(C));}
void change(int i,int j,int d)
{
for(int x=i;x<=n;x+=x&-x)
for(int y=j;y<=n;y+=y&-y)
C[x][y]+=d;
}
int sum(int i,int j)
{
int Ans=0;
for(int x=i;x>0;x-=x&-x)
for(int y=j;y>0;y-=y&-y)
Ans+=C[x][y];
return Ans;
}
int sum(int x0,int y0,int x1,int y1)
{
return sum(x1,y1)-sum(x1,y0-1)-sum(x0-1,y1)+sum(x0-1,y0-1);
}
}C[maxc];
int M[maxn][maxn];
void Change(int x,int y,int c)
{
int o=M[x][y];
C[o].change(x,y,-1);
C.change(x,y,1);
M[x][y]=c;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;int c;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&c);–c;
C.change(i,j,1);
M[i][j]=c;
}
int p,t,x,y,x0,y0,x1,y1;cin>>p;
while(p–)
{
scanf("%d",&t);
if(t==1)
scanf("%d %d %d",&x,&y,&c),Change(x,y,c-1);
else
scanf("%d %d %d %d %d",&x0,&x1,&y0,&y1,&c),printf("%dn",C[c-1].sum(x0,y0,x1,y1));
}
}

[SCOI2005]互不侵犯King

Time Limit:10000MS  Memory Limit:165536K
Total Submit:13 Accepted:9
Case Time Limit:1000MS

Description

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个 格子。

Input

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

Output

方案数。

Sample Input

3 2

Sample Output

16

Source

今天早上我一直在被题虐。。看了7、8道没一道会的，我真是太菜了55555
好不容易看到道会的还这么水。。囧死了。。
61.187.179.132:8080/JudgeOnline/showproblem
额。这道题目首先dfs出所有可能的状态（不能有连续的1）。。然后预处理出所有数中1的个数。然后直接DP就OK了。。
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=9,maxk=maxn*maxn;
typedef long long ll;
ll dp[2][maxk+1][1<<maxn]={0};
int state[1<<maxn],cnt=0,N,K,C[1<<maxn];
void dfs(int p,int s)
{
if(p==N){state[cnt++]=s;return;}
dfs(p+1,s*2);
if(!(s&1))dfs(p+1,s*2+1);
}
inline bool Legal(int a,int b)
{
a=state[a];b=state[b];
return !(a&b)&&!((a<<1)&b)&&!((a>>1)&b);
}
inline int Count(int a)
{
a=state[a];
return C[a];
}
int main()
{
//freopen("in","r",stdin);
cin>>N>>K;
int now=0,old=1;
dp[now][0][0]=1;dfs(0,0);
C[0]=0;
for(int i=1;i<(1<<N);i++)
C[i]=C[i/2]+(i&1);
rep(n,N)
{
swap(now,old);memset(dp[now],0,sizeof(dp[now]));
rep(k,K+1)rep(ps,cnt)rep(ns,cnt)
if(k-Count(ns)>=0&&Legal(ns,ps))
{
dp[now][k][ns]+=dp[old][k-Count(ns)];
}
}
ll ans=0;
rep(s,cnt) ans+=dp[now][K][s];
cout<<ans<<endl;
}

61.187.179.132:8080/JudgeOnline/showproblem

Vijos1083 小白逛公园　

Time Limit:10000MS  Memory Limit:65536K
Total Submit:58 Accepted:16
Case Time Limit:1000MS

Description

小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪 些公园玩了。
一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公 园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分 也可能会有一些变化。
那么，就请你来帮小白选择公园吧。

Input

第一行，两个整数N和M，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。
接下来N行，每行一个整数，依次给出小白 开始时对公园的打分。
接下来M行，每行三个整数。第一个整数K，1或2。K=1表示，小新要带小白出去玩，接下来的两个整数a和b给出了选择公园的范围 （1≤a,b≤N）；K=2表示，小白改变了对某个公园的打分，接下来的两个整数p和s，表示小白对第p个公园的打分变成了s（1≤p≤N）。
其中，1≤N≤500 000，1≤M≤100 000，所有打分都是绝对值不超过1000的整数。

Output

小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。

Sample Input

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

Sample Output

2
-1

Source

这是一道水题啊水题啊。我实验了一下我最近想出来的线段树新写法。就是合并用一个失效值来代替不存在的节点。。然后不是在父节点处判断范围，而是直接在子节点处判断范围，写起来超爽，代码也超短，具体看Code吧。
Code：
#include<cstdio>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>1,maxn=500000;
int A[maxn];
struct info
{
int L,R,M,S;
info(int x=0):L(x),R(x),M(x),S(x){}
}none;
info operator+(const info&l,const info&r)
{
info f;if(l.M==-inf)return r;
if(r.M==-inf)return l;
f.L=max(l.L,l.S+r.L);
f.R=max(r.R,r.S+l.R);
f.S=l.S+r.S;
f.M=max(l.M,r.M);
f.M=max(f.M,l.R+r.L);
return f;
}
info T[maxn*3];
inline void set(int t,int x)
{
T[t]=info(x);
}
void build(int t,int l,int r)
{
if(l+1==r) {set(t,A[l]);return;}
build(t*2,l,(l+r)/2);
build(t*2+1,(l+r)/2,r);
T[t]=T[t*2]+T[t*2+1];
}
void change(int t,int l,int r,int p,int s)
{
if(l+1==r){set(t,s);return;}
if(p<(l+r)/2) change(t*2,l,(l+r)/2,p,s);
else change(t*2+1,(l+r)/2,r,p,s);
T[t]=T[t*2]+T[t*2+1];
}
info ask(int t,int l,int r,int a,int b)
{
if(b<=l||a>=r) return none;
if(l>=a&&r<=b) return T[t];
return ask(t*2,l,(l+r)/2,a,b)+ask(t*2+1,(l+r)/2,r,a,b);
}
int main()
{
//freopen("in","r",stdin);
none.M=-inf;
int n,m,a,b,c;scanf("%d %d",&n,&m);
rep(i,n)scanf("%d",A+i);
build(1,0,n);
while(m–)
{
scanf("%d %d %d",&a,&b,&c);
if(a==1) {if(b>c)swap(b,c);printf("%dn",ask(1,0,n,b-1,c).M);}
else change(1,0,n,b-1,c);
}
}

61.187.179.132:8080/JudgeOnline/showproblem

[ZJOI2006]物流运输trans

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

Description

物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输 路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目 的地。但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。

Input

第一行是四个整数n（1<=n<=100）、m（1<=m<=20）、K和e。n表示货物运输所需天数，m表示码头总数，K表示 每次修改运输路线所需成本。接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度（>0）。其中码头A编号 为1，码头B编号为m。单位长度的运输费用为1。航线是双向的。
再接下来一行是一个整数d，后面的d行每行是三个整数P（ 1 < P < m）、a、b（1 < = a < = b < = n）。表示编号为P的码头从第a天到第b天无法装卸货物（含头尾）。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头A到码头B的 运输路线。

Output

包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。

Sample Input

5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5

Sample Output

Sample Output
32

Hint

前三天走1-4-5，后两天走1-3-5，这样总成本为(2+2)*3+(3+2)*2+10=32

Source

好像是老题目了。。以前在VJ上看到过。不过我是第一次做。。还有就是我刚刚实在太无聊了。。把自己以前在PKU上过的USACO月赛题目交题库了。。结果刷了不少Rank。。其实都是USACO的水题囧。。PKU居然有代码打包的功能的，真是太强了了Orz。。
这道题目的话设Dp(i)表示1到i天最小费用，那么Dp(i)=Min(Dp(j)+Cost(j+1,i)*(i-j)+k)..Cost(l,r)表示l到r期间都可用的最短路线长度。。每次都spfa一次就可以了。。反正数据这么小想怎么做都可以囧。。
最后再-个k就OK了。。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#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 all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int inf=~0U>>2,maxT=100+1,maxn=20,maxm=1000;
int T,n,k,m;
struct Edge
{
int t,c;
Edge*next;
Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}
}*E[maxn]={0};
struct Vertex
{
int D[maxT];
Vertex(){memset(D,0,sizeof(D));}
void Ins(int l,int r)
{
For(i,l,r) D[i]=1;
}
void Set()
{
For(i,1,T) D[i]+=D[i-1];
}
bool ok(int l,int r)
{
return D[r]==D[l-1];
}
}V[maxn];
void InsEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,c,E[t]);
}
void Init()
{
cin>>T>>n>>k>>m;int s,t,c;
while(m–)
{
scanf("%d %d %d",&s,&t,&c);
InsEdge(s-1,t-1,c);
}
int p,a,l,r;cin>>p;
while(p–)
{
scanf("%d %d %d",&a,&l,&r);
V[a-1].Ins(l,r);
}
rep(i,n)V[i].Set();
}
int Cost(int l,int r)
{
static int dist[maxn];
static bool inq[maxn];
rep(i,n) dist[i]=inf,inq[i]=false;
queue<int> Q;
Q.push(0);inq[0]=true;dist[0]=0;
while(Q.size())
{
int t=Q.front();Q.pop();inq[t]=false;int cost=dist[t];
for(Edge*e=E[t];e;e=e->next)
{
int ncost=cost+e->c,v=e->t;
if(!V[v].ok(l,r))continue;
if(dist[v]>ncost)
{
dist[v]=ncost;
if(!inq[v]) Q.push(v),inq[v]=true;
}
}
}
return dist[n-1];
}
int dp[maxT];
void Work()
{
dp[0]=0;
For(i,1,T)
{
dp[i]=inf;
for(int j=i-1;j>=0;–j)
{
int c=Cost(j+1,i);
if(c==inf)break;
dp[i]=min(dp[i],dp[j]+c*(i-j)+k);
}
}
cout<<dp[T]-k<<endl;
}
int main()
{
//freopen("in","r",stdin);
Init();
Work();
}

61.187.179.132:8080/JudgeOnline/showproblem

[HNOI2004]宠物收养所

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

Description

最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。
每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个 正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发 生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。
1． 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠 物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的 特点值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。
2． 收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养 者，如果该宠物的特点值为a，存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b，那么特点值为a-b的那个领养者将成功领养该宠物。

一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。
【任务描述】
你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有 宠物，也没有领养者。

Input

第一行为一个正整数n，n<=80000，表示一年当中来到收养所的宠物和领养者的总数。接下来的n行，按到来时间的先后顺序描述了一年当中来到收 养所的宠物和领养者的情况。每行有两个正整数a, b，其中a=0表示宠物，a=1表示领养者，b表示宠物的特点值或是领养者希望领养宠物的特点值。（同一时间呆在收养所中的，要么全是宠物，要么全是领养 者，这些宠物和领养者的个数不会超过10000个）

Output

仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。

Sample Input

5
0 2
0 4
1 3
1 2
1 5

Sample Output

3
(abs(3-2) + abs(2-4)=3，最后一个领养者没有宠物可以领养)

Source

在set存在的情况下这是一个大水题为了方便插入两个无穷节点..长度最短(*^__^*)
Code:
#include<cstdio>
#include<set>
using namespace std;
const int inf=~0U>>2;
typedef set<int>::iterator sit;
set<int> S;
int main()
{
int n,a,b,ans=0,type;
scanf("%d",&n);S.insert(inf);S.insert(-inf);
while(n–)
{
scanf("%d %d",&a,&b);
if(S.size()==2) type=a,S.insert(b);
else if(type==a) S.insert(b);
else
{
sit i=S.lower_bound(b);
int r=*i-b,l=b-*(–i);
if(l<=r) ans+=l,S.erase(i);
else ans+=r,S.erase(++i);
ans%=1000000;
}
}
printf("%dn",ans);
}

61.187.179.132:8080/JudgeOnline/showproblem

[SCOI2005]繁忙的都市

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

Description

城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口， 有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分 值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
1． 改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
2． 在满足要求1的情况下，改造的道路尽量少。
3． 在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小。
任务：作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。

Input

第一行有两个整数n,m表示城市有n个交叉路口，m条道路。接下来m行是对每条道路的描述，u, v, c表示交叉路口u和v之间有道路相连，分值为c。(1≤n≤300，1≤c≤10000)

Output

两个整数s, max，表示你选出了几条道路，分值最大的那条道路的分值是多少。

Sample Input

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

Sample Output

3 6

Source

水题！边排序之后直接并查集
代码最短速度第二(*^__^*)
Code：
#include<cstdio>
#include<algorithm>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> edge;
vector<edge> E;
vector<int> F;
int find(int x){return F[x]==x?x:(F[x]=find(F[x]));}
int main()
{
int n,m,s,t,c,ans;
scanf("%d %d",&n,&m);
rep(i,n) F.pb(i);
rep(i,m)scanf("%d %d %d",&s,&t,&c),E.pb(edge(c,ii(s-1,t-1)));
sort(all(E));
rep(i,m)
{
int a=find(E[i].second.first),b=find(E[i].second.second);
if(a!=b) F[a]=b,ans=E[i].first;
}
printf("%d %dn",n-1,ans);
}

61.187.179.132:8080/JudgeOnline/showproblem

[JSOI2008]星球大战starwar

Time Limit:3000MS  Memory Limit:165536K
Total Submit:90 Accepted:43
Case Time Limit:1000MS

Description

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星 系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。
但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通 讯通道也开始不可靠起来。现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打 击之后反抗军占据的星球的连通快的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。

Input

输入文件第一行包含两个整数，N (1 <= N <= 2M) 和M (1 <= M <= 200,000)，分别表示星球的数目和以太隧道的数目。星球用0~N-1的整数编号。
接下来的M行，每行包括两个整数X, Y，其中（0<=X<>Y

Output

输出文件的第一行是开始时星球的连通块个数。
接下来的N行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

Sample Input

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7

Sample Output

1
1
1
2
3
3

Source

额。算法鬼都知道(*^__^*) 就是倒过来然后加点然后用并查集。这没话说。。
关键是如果按我一般的方式用vector表示边的话会TLE囧。。
只好用前向星了。惊讶的发现前向星可以写的怎么短！以后遇到这种情况都用前向星了(*^__^*)
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<utility>
#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(vi::iterator i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define divide cout<<"—————"<<endl;
using namespace std;
const int inf=~0U>>1,maxm=400000,maxn=maxm;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
ii E[maxm];
int A[maxn],Ans[maxn],S[maxn+1]={0},T[maxm];
bool inSet[maxn]={0},used[maxn]={0};
int F[maxn],n,m,cnt;
void makeset(int x)
{
F[x]=x;cnt++;inSet[x]=true;
}
int find(int x)
{
if(F[x]==x)return x;
return F[x]=find(F[x]);
}
void Union(int i,int j)
{
if(!inSet[i]||!inSet[j])return;
i=find(i);j=find(j);
if(i!=j) F[i]=j,cnt–;
}
int main()
{
//freopen("in","r",stdin);
scanf("%d %d",&n,&m);int s,t;cnt=0;
rep(i,m)
{
scanf("%d %d",&s,&t);
E[i*2]=ii(s,t);
E[i*2+1]=ii(t,s);
S[s]++;S[t]++;
}
for(int i=1;i<=n;i++) S[i]+=S[i-1];
for(int i=2*m-1;i>=0;–i)
T[–S[E[i].first]]=E[i].second;
int k;scanf("%d",&k);
rep(i,k)scanf("%d",A+i),used[A[i]]=true;
rep(i,n)if(!used[i])makeset(i);
rep(i,n)if(!used[i])for(int e=S[i];e<S[i+1];e++)Union(i,T[e]);
Ans[k]=cnt;
for(int i=k-1;i>=0;–i)
{
int t=A[i];makeset(t);
for(int e=S[t];e<S[t+1];e++)Union(t,T[e]);
Ans[i]=cnt;
}
rep(i,k+1)printf("%dn",Ans[i]);
}

[SCOI2009]最长距离

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

Description

windy有一块矩形土地，被分为 N*M 块 1*1 的小格子。
有的格子含有障碍物。
如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。
如果从格子A不可以走到格子B，就没有距离。
如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。
如果windy可以移走T块障碍物，求所有格子间的最大距离。
保证移走T块障碍物以后，至少有一个格子不含有障碍物。

Input

输入文件maxlength.in第一行包含三个整数，N M T。
接下来有N行，每行一个长度为M的字符串，’0’表示空格子，’1’表示该格子含有障碍物。

Output

输出文件maxlength.out包含一个浮点数，保留6位小数。

Sample Input

【输入样例一】
3 3 0
001
001
110

【输入样例二】
4 3 0
001
001
011
000

【输入样例三】
3 3 1
001
001
001

Sample Output

【输出样例一】
1.414214

【输出样例二】
3.605551

【输出样例三】
2.828427

Hint

20%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 0 。
40%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 2 。
100%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 30 。

Source

Day2
61.187.179.132:8080/JudgeOnline/showproblem
效仿tclsm神牛直接贴题目了。。感觉给我本来就很短的题解凑了点字囧。。
这道题目的感觉是SCOI2009最水的，枚举每个起点，直接BFS，复杂度是O(n^2m^2)的，同时可以规定终点的横坐标大于起点。。减少一半搜索量。。
BFS的时候注意边权可以是1也可以是0，那么用一个deque代替queue，遇到0边就放进对首，否则放进队尾就OK了。。
我从qzc神牛的代码中看到define是可以放在函数中的，而且可以用#undef给取消掉，太orz了。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<deque>
#include<cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define pf push_front
using namespace std;
typedef pair<int,int> ii;
const int inf=~0U>>1,maxn=30;
int n,m,T;
double ans=0;
bool Map[maxn][maxn];
const int di[]={1,0,-1,0},dj[]={0,1,0,-1};
void bfs(int x,int y)
{
static bool vis[maxn][maxn];
static int dist[maxn][maxn];
memset(vis,0,sizeof(vis));
deque<ii> Q;dist[x][y]=Map[x][y];
vis[x][y]=true;Q.pb(ii(x,y));
#define legal(i,j) (i>=x&&i<n&&j>=0&&j<m&&!vis[i][j])
#define A first
#define B second
double tx,ty;
while(Q.size())
{
ii t=Q.front();int cost=dist[t.A][t.B],xx,yy;Q.pop_front();
if(cost>T)break;
tx=t.A-x;ty=t.B-y;
ans=max(ans,tx*tx+ty*ty);
rep(d,4)
{
xx=t.A+di[d];
yy=t.B+dj[d];
if(legal(xx,yy))
{
if(Map[xx][yy])
Q.pb(ii(xx,yy)),dist[xx][yy]=cost+1;
else
Q.pf(ii(xx,yy)),dist[xx][yy]=cost;
vis[xx][yy]=true;
}
}
}
#undef legal
#undef A
#undef B
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m>>T;char x;
rep(i,n)rep(j,m)cin>>x,Map[i][j]=x==’1′;
rep(i,n)rep(j,m)bfs(i,j);
ans=sqrt(ans);
printf("%0.6lf",ans);
}

[SCOI2009]迷路

Time Limit:10000MS  Memory Limit:165536K
Total Submit:40 Accepted:24
Case Time Limit:1000MS

Description

windy在有向图中迷路了。
该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。
现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？
注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

Input

第一行包含两个整数，N T。
接下来有 N 行，每行一个长度为 N 的字符串。
第i行第j列为’0’表示从节点i到节点j没有边。
为’1’到’9’表示从节点i到节点j需要耗费的时间。

Output

包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。

Sample Input

【输入样例一】
2 2
11
00

【输入样例二】
5 30
12045
07105
47805
12024
12345

Sample Output

【输出样例一】
1

【样例解释一】
0->0->1

【输出样例二】
852

Hint

30%的数据，满足 2 <= N <= 5 ； 1 <= T <= 30 。
100%的数据，满足 2 <= N <= 10 ； 1 <= T <= 1000000000 。

Source

Day2

我擦啊！61.187.179.132:8080/JudgeOnline/showproblem
我一开始没想出来怎么做，很明显要用矩阵乘法，所以我就想怎么搞。。
我想了半天没有什么头绪，感觉这个长度很麻烦，感觉矩阵乘法就是从一个推出下一个，推不出下面很多个额。。很头疼。
过了一天发现由于长度最长是9。。。所以把每9个打包起来就再递推就OK了。。
可是我：

晕死了。。那几个WA是我故意写return 0查出错点的。。
最后发现原来因为矩阵有点大，导致如果我直接在乘法里写临时变量的话会MLE。。
靠靠靠。。我本来就没什么AC率的。。现在悲剧大发了。。
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 maxt=9,maxv=90,maxn=10,mod=2009;
int n,v;
inline int node(int time,int pos)
{
return time*n+pos;
}
int tmp[maxv][maxv];
struct Mat
{
int M[maxv][maxv];
int&operator()(int i,int j){return M[i][j];}
Mat(){memset(M,0,sizeof(M));}
void operator*=(Mat&o)
{
memset(tmp,0,sizeof(tmp));
rep(i,v)rep(j,v)rep(k,v)
tmp[i][j]+=M[i][k]*o(k,j),tmp[i][j]%=mod;
memcpy(M,tmp,sizeof(M));
}
void operator=(const Mat&o)
{
memcpy(M,o.M,sizeof(M));
}
}orig;
int Map[maxn][maxn];
void Power(int n,Mat&ret)
{
if(n==1){ret=orig;return;}
Power(n/2,ret);
ret*=ret;
if(n&1)ret*=orig;
}
int main()
{
//freopen("in","r",stdin);
//freopen("road.in","r",stdin);
//freopen("road.out","w",stdout);
int T;
scanf("%d %d",&n,&T);char x;v=n*9;
rep(i,n)
{
scanf("n");
rep(j,n)scanf("%c",&x),Map[i][j]=x-‘0’;
}
rep(i,n)for(int t=0;t<8;t++)
orig(node(t,i),node(t+1,i))++;
rep(i,n)rep(j,n)if(Map[j][i])
orig(node(8,i),node(9-Map[j][i],j))++;
Mat Ans;Power(T,Ans);
int dp[maxn][maxt]={0};
dp[0][0]=1;
for(int t=1;t<maxt;t++)
{
rep(i,n)rep(j,n)
if(Map[j][i])
if(t-Map[j][i]>=0)
{
dp[i][t]+=dp[j][t-Map[j][i]];
dp[i][t]%=mod;
}
}
int ans=0;
rep(i,n)rep(t,maxt)
{
ans+=Ans(node(0,n-1),node(t,i))*dp[i][t];
ans%=mod;
}
cout<<ans<<endl;
}

靠。。刚想出这道题Vijos居然奔溃了。。我哭啊。。
题目是说给你n个数，都小于10^5，然后让你求出其中一个子序列（连不连续无所谓，只要顺序是原序列的顺序就OK）。。相邻两个数不互质。。让你求这个序列的最大长度。。n<=100000
很明显暴力DP是会悲剧的，如果你用Dpi表示第i个数结尾的最长长度然后O(n)枚举前一个的话是O(n^2)的。关键是利用题目的性质。
注意到不互质的数一定有一个公共的质因子，就简单了。首先算出10^5一下每个质数，然后开个数组保存每个当前以第i个质数的倍数结尾的数列的最长值，然后对于每个数枚举他的每个质因子计算并更新一下就可以了。。
关键是一个数的质因子数目显然是O(logn)级别的，并且预先处理也可以大大降低枚举量。。程序还是很快的。。
不过VJ挂了。没法测了囧。。