[HNOI2005]狡猾的商人

Time Limit:10000MS  Memory Limit:165536K
Total Submit:44 Accepted:26
Case Time Limit:1000MS

Description

刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。账本上记录了n个月以来的收入情况，其中第i 个月的收入额为Ai(i=1,2,3…n-1,n)， 。当 Ai大于0时表示这个月盈利Ai 元，当 Ai小于0时表示这个月亏损Ai 元。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。
刁姹的任务是秘密进行的，为了调查商人的账本，她只好跑到商人那里打工。她趁商人不在时去偷看账本，可是她无法将账本偷出来，每次偷看账本时她都 只能看某段时间内账本上记录的收入情况，并且她只能记住这段时间内的总收入。
现在，刁姹总共偷看了m次账本，当然也就记住了m段时间内的总收入，你的任务是根据记住的这些信息来判断账本是不是假的。

Input

第一行为一个正整数w，其中w < 100，表示有w组数据，即w个账本，需要你判断。每组数据的第一行为两个正整数n和m，其中n < 100，m < 1000，分别表示对应的账本记录了多少个月的收入情况以及偷看了多少次账本。接下来的m行表示刁姹偷看m次账本后记住的m条信息，每条信息占一行，有三 个整数s，t和v，表示从第s个月到第t个月（包含第t个月）的总收入为v，这里假设s总是小于等于t。

Output

包含w行,每行是true或false,其中第i行为true当且仅当第i组数据，即第i个账本不是假的；第i行为false当且仅当第i组数据，即第i 个账本是假的。

Sample Input

2
3 3
1 2 10
1 3 -5
3 3 -15
5 3
1 5 100
3 5 50
1 2 51

Sample Output

true
false

Source

这道题的话dfs和并查集都可以，dfs是首先dfs一下把所有的值推出来，在遇到反向边的时候再判断一下就可以了。不过这样还要构图，还是直接并查集爽，
并查集关键就是信息，为此考虑部分和序列，告诉你s到t的和实际上就是Sum(t)-Sum(s-1)=v。那么这两个的信息就关联起来了，那么并在一起并保存相对信息就可以了。。
Code:
#include<cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100;
int n,m,F[maxn],G[maxn];
int Find(int x)
{
if(x==F[x])return x;
Find(F[x]);G[x]+=G[F[x]];return F[x]=F[F[x]];
}
void solve()
{
int s,t,v;
scanf("%d %d",&n,&m);
rep(i,n+1)F[i]=i,G[i]=0;
bool Right=1;
while(m–)
{
scanf("%d %d %d",&s,&t,&v);–s;
int i=Find(s),j=Find(t),a=G[s],b=G[t];
if(i!=j)
{
F[i]=j;
G[i]=b-a-v;
}
else if(b-a!=v)Right=false;
}
Right?puts("true"):puts("false");
}
int main()
{
int t;scanf("%d",&t);while(t–)solve();
}

[HNOI2007]紧急疏散evacuate

Time Limit:10000MS  Memory Limit:165536K
Total Submit:57 Accepted:19
Case Time Limit:1000MS

Description

发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是’.’，那么表示这是一块空地；如果是’X’，那么表示这是一面墙，如果是’D’，那么表示这是一扇门，人们可以从这儿撤出 房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格， 当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到 门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。

Input

输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符’.’、’X’和’D’，且字符间无空格。

Output

只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出’impossible’（不包括引号）。

Sample Input

5 5
XXXXX
X…D
XX.XX
X..XX
XXDXX

Sample Output

3

Source

61.187.179.132:8080/JudgeOnline/showproblem
写了半天的代码，累死了。不过SAP还真是快啊。。
首先我的第一感觉是最优性改判定性，那么如何判断能否在限定时间T内将所有人转移走呢？很显然先特判一下无解的情况，首先从每个门BFS出它到每个节点的最短路，那么它最多能配上T个点且这T个点到他的最短路长度要小于T。那么就可以转化成网络流问题，从源向每个门连一条容量为T的边，从每个空地向汇连一条容量为1的边，然后不断增加T就可以了。。
就这么A掉了。可为什么这样是可以的？我感觉如果配上的T个点离的比较远的话在门上会卡住的囧，也就不可能完全利用T的时间了甚至好像可以找出反例（我没找出来）。。
也许是因为一个距离为d的点之前必然有一个距离为d-1的点之类的性质？迷茫了。。
Code(超过最大长度发不上来囧。。):
放在ideone上吧：
www.ideone.com/OdFo4hbA#

[Baltic2001]Mars Maps

Time Limit:5000MS  Memory Limit:65536K
Total Submit:19 Accepted:7
Case Time Limit:1000MS

Description

给出N个矩形,N<=10000.其坐标不超过10^9.求其面积并

Input

先给出一个数字N,代表有N个矩形.
接下来N行,每行四个数,代表矩形的坐标.

Output

输出面积并

Sample Input

2
10 10 20 20
15 15 25 30

Sample Output

225

Source

这是很经典的题目了。离散化之后用扫描线扫过去，用线段树维护当前与扫描线相交的矩形的长度并。就可以降维了。。
不过我悲剧了。数组开小了囧。。WA了好几次。。
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=10000;
int n;
int Y[maxn*2];
struct Event
{
int x,l,r,d;
Event(){}
Event(int _x,int _l,int _r,int _d):x(_x),l(_l),r(_r),d(_d){}
bool operator<(const Event&o)const
{
return x<o.x;
}
}E[maxn*2];
void Init()
{
scanf("%d",&n);
int x[2],y[2],cnt=0;
rep(i,n)
{
rep(j,2)scanf("%d %d",x+j,y+j),Y[cnt++]=y[j];
E[2*i]=Event(x[0],y[0],y[1],1);
E[2*i+1]=Event(x[1],y[0],y[1],-1);
}
}
int Cover[8*maxn]={0},Sum[8*maxn]={0};
void change(int t,int l,int r,int a,int b,int d)
{
if(a>=r||b<=l) return;
if(a<=l&&b>=r)Cover[t]+=d;
else change(t*2,l,(l+r)/2,a,b,d),change(t*2+1,(l+r)/2,r,a,b,d);
if(Cover[t]>0)
Sum[t]=Y[r]-Y[l];
else
Sum[t]=(l+1==r)?0:(Sum[t*2]+Sum[t*2+1]);
}
void Work()
{
n<<=1;
sort(Y,Y+n);
rep(i,n)
{
E[i].l=lower_bound(Y,Y+n,E[i].l)-Y;
E[i].r=lower_bound(Y,Y+n,E[i].r)-Y;
}
sort(E,E+n);int last=E[0].x;long long Ans=0;
rep(i,n)
{
Event now=E[i];
if(now.x!=last)
{
Ans+=(long long)(Sum[1])*(now.x-last);
last=now.x;
}
change(1,0,n-1,now.l,now.r,now.d);
}
cout<<Ans<<endl;
}
int main()
{
//freopen("in","r",stdin);
Init();
Work();
}

[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

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

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