[ZJOI2007]仓库建设

[ZJOI2007]仓库建设

Time Limit:10000MS  Memory Limit:165536K
Total Submit:51 Accepted:28
Case Time Limit:3000MS

Description

L公司有N个工厂,由高到底分布在一座山上。如图所示,工厂1在山顶,工厂N在山脚。

由于这座山处于高原内陆地区(干燥少雨),L公司一般把产品直接堆放在露天,以节省费用。突然有一天,L公司的总裁L先生接到气象部门的电话,被 告知三天之后将有一场暴雨,于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。
由于地形的不同,在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件,在第i个工厂位置建立仓库的费用是Ci。对于没有建立仓 库的工厂,其产品应被运往其他的仓库进行储藏,而由于L公司产品的对外销售处设置在山脚的工厂N,故产品只能往山下运(即只能运往编号更大的工厂的仓 库),当然运送产品也是需要费用的,假设一件产品运送1个单位距离的费用是1。假设建立的仓库容量都都是足够大的,可以容下所有的产品。
你将得到以下数据:
 工厂i距离工厂1的距离Xi(其中X1=0);
 工厂i目前已有成品数量Pi;
 在工厂i建立仓库的费用Ci;

请你帮助L公司寻找一个仓库建设的方案,使得总的费用(建造费用+运输费用)最小。

Input

第一行包含一个整数N,表示工厂的个数。接下来N行每行包含两个整数Xi, Pi, Ci, 意义如题中所述。

Output

仅包含一个整数,为可以找到最优方案的费用。

Sample Input

3
0 5 10
5 3 100
9 6 10

Sample Output

32

Hint

在工厂1和工厂3建立仓库,建立费用为10+10=20,运输费用为(9-5)*3 = 12,总费用32。
如果仅在工厂3建立仓库,建立费用为10,运输费用为(9-0)*5+(9-5)*3=57,总费用67,不如前者优。
【数据规模】
对于20%的数据, N ≤500;
对于40%的数据, N ≤10000;
对于100%的数据, N ≤1000000。
所有的Xi, Pi, Ci均在32位带符号整数以内,保证中间计算结果不超过64位带符号整数。

Source

这道题目很明显还是决策单调性。。跟toy一摸一样一样的做法就可以了。。不过longlong上面纠结了半天囧。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<deque>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=1000000+1;
struct node
{
int l,r,ch;
node(){}
node(int _l,int _r,int _ch):l(_l),r(_r),ch(_ch){}
};
typedef long long ll;
int C[maxn],X[maxn],n;
ll SP[maxn]={0},SXP[maxn]={0},Dp[maxn];
ll Cost(int l,int r)
{
return (SP[r]-SP[l-1])*X[r]-(SXP[r]-SXP[l-1])+C[r];
}
ll Get(int i,int j)
{
return Dp[j]+Cost(j+1,i);
}
int binary(node t,int i)
{
int l=t.l,r=t.r;
#define check(m) (Get(m,t.ch)<Get(m,i))
if(check(r)) return r;
while(l+1<r)
{
int m=(l+r)/2;
if(check(m)) l=m;
else r=m;
}
#undef check
return l;
}
void Init()
{
int x,p;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d %d %d",&x,&p,C+i);
SP[i]=SP[i-1]+p;SXP[i]=SXP[i-1]+ll(x)*p;X[i]=x;
}
}
void Work()
{
deque<node> D;
Dp[0]=0;D.pb(node(1,n,0));
for(int i=1;i<=n;i++)
{
Dp[i]=Get(i,D.front().ch);
if(D.front().l<D.front().r)
D.front().l++;
else
D.pop_front();
int e;node t;
while(D.size())
{
t=D.back();
if(Get(t.l,i)<=Get(t.l,t.ch))
D.pop_back();
else
{
e=binary(t,i);
D.back().r=e;
break;
}
}
if(D.size()==0) D.pb(node(i+1,n,i));
else if(e<n) D.pb(node(e+1,n,i));
}
cout<<Dp[n]<<endl;
}
int main()
{
//freopen("in","r",stdin);
Init();
Work();
}

[HNOI2008]玩具装箱toy

[HNOI2008]玩具装箱toy

Time Limit:1000MS  Memory Limit:165536K
Total Submit:204 Accepted:76

Description

P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一 维容器中。P教授有编号为1…N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P教授要求在一个一维容器中的玩具编号是连续 的。同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物,形式地说如果将第i件玩具到第j个玩具放到一个容器中,那么容器的 长度将为
x=j-i+Sigma(Ck) i<=K<=j
制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为x,其制作费用为(X-L)^2.其中L是一个
常量。P教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过L。但他希望费用最小.

Input

第一行输入两个整数N,L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

Output

输出最小费用

Sample Input

5 4
3
4
2
1
4

Sample Output

1

Source

额。。看了决策单调性之后决定A个一题,结果搞了半天,我太菜了555。。。
这是很基本的决策单调性,也可以用斜率优化来搞,不过单调性感觉比较直观,而且也能AC(*^__^*)
就是用一个双端队列来保存当前的决策区间,用二分查找寻分界点。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<deque>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
const int maxn=50000+1;
typedef long long ll;
struct node
{
int l,r,ch;
node(){}
node(int _l,int _r,int _ch):l(_l),r(_r),ch(_ch){}
};
ll Sum[maxn]={0},Dp[maxn];
int top=0;
int L,n;
ll Cost(int l,int r)
{
ll x=Sum[r]-Sum[l-1]+r-l;
x-=L;
return x*x;
}
ll Get(int New,int Old)
{
if(Old>=New)return inf;
return Dp[Old]+Cost(Old+1,New);
}
int binary(node t,int i)
{
int l=t.l,r=t.r;
#define check(m) (Get(m,t.ch)<Get(m,i))
if(check(r)) return r;
while(l+1<r)
{
int m=(l+r)/2;
if(check(m)) l=m;
else r=m;
}
return l;
#undef check
}
void Init()
{
scanf("%d %d",&n,&L);
rep(i,n)scanf("%lld",Sum+i+1);
for(int i=1;i<=n;i++) Sum[i]+=Sum[i-1];
}
void Work()
{
Dp[0]=0;deque<node> D;
D.pb(node(1,n,0));
for(int i=1;i<=n;i++)
{
Dp[i]=Get(i,D.front().ch);
if(D.front().l<D.front().r)
D.front().l++;
else
D.pop_front();
node t;int e;
while(D.size())
{
t=D.back();
if(Get(t.l,i)<=Get(t.l,t.ch))
{
D.pop_back();
}
else
{
e=binary(t,i);
D.back().r=e;
break;
}
}
if(D.size()==0)
D.pb(node(i+1,n,i));
else if(e<n) D.pb(node(e+1,n,i));
}
cout<<Dp[n]<<endl;
}
int main()
{
//freopen("in","r",stdin);
Init();
Work();
}

[JSOI2009]Count

[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

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

Vijos1083 小白逛公园

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

[ZJOI2006]物流运输trans

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

[HNOI2004]宠物收养所

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

[SCOI2005]繁忙的都市

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

[JSOI2008]星球大战starwar

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]最长距离

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

Page 4 of 7« First...23456...Last »