[SHOI2008]Debt 循环的债务

[SHOI2008]Debt 循环的债务

Time Limit:1000MS  Memory Limit:165536K
Total Submit:22 Accepted:8
Case Time Limit:100MS

Description

Alice、Bob和Cynthia总是为他们之间混乱的债务而烦恼,终于有一天,他们决定坐下来一起解决这个问题。不过,鉴别钞票的真伪是一件很麻烦的 事情,于是他们决定要在清还债务的时候尽可能少的交换现金。
比如说,Alice欠Bob 10元,而Cynthia和他俩互不相欠。现在假设Alice只有一张50元,Bob有3张10元和10张1元,Cynthia有3张20元。一种比较直 接的做法是:Alice将50元交给Bob,而Bob将他身上的钱找给Alice,这样一共就会有14张钞票被交换。但这不是最好的做法,最好的做法 是:Alice把50块给Cynthia,Cynthia再把两张20给Alice,另一张20给Bob,而Bob把一张10块给C,此时只有5张钞票被 交换过。
没过多久他们就发现这是一个很棘手的问题,于是他们找到了精通数学的你为他们解决这个难题。

Input

输入的第一行包括三个整数:x1、x2、x3(-1,000≤x1,x2,x3≤1,000),其中
x1代表Alice欠Bob的钱(如果x1是负数,说明Bob欠了Alice的钱)
x2代表Bob欠Cynthia的钱(如果x2是负数,说明Cynthia欠了Bob的钱)
x3代表Cynthia欠Alice的钱(如果x3是负数,说明Alice欠了Cynthia的钱)
接下来有三行,每行包括6个自然数:
a100,a50,a20,a10,a5,a1
b100,b50,b20,b10,b5,b1
c100,c50,c20,c10,c5,c1
a100表示Alice拥有的100元钞票张数,b50表示Bob拥有的50元钞票张数,以此类推。另外,我们保证有 a10+a5+a1≤30,b10+b5+b1≤30,c10+c5+c1≤30,而且三人总共拥有的钞票面值总额不会超过1,000。

Output

如果债务可以还清,则输出需要交换钞票的最少张数;如果不能还清,则输出“impossible”(注意单词全部小写,输出到文件时不要加引号)。
输入一
10 0 0
0 1 0 0 0 0
0 0 0 3 0 10
0 0 3 0 0 0
输入二
-10 -10 -10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
【数据规模】
对于30%的数据,x1、x2、x3 ≤ |50|。
对于100%的数据,x1、x2、x3 ≤ |1,000|。

Sample Input

输出一
5

输出二
0

Sample Output

Source

这个题目非常BT囧。。。
我被它搞死了。。。
恩。。办法是这个样子的。。搜索估计要悲剧。直接想Dp。
可以把题目转化成从一个状态A,B分别的钱数到另一个状态。。
然后发现状态可以是pos,a,b表示当前考虑到第pos种钱币,Alice现在的钱,Bob现在的钱。。
然后可以发现对同一种硬币来说,把多余的操作删掉,比如A给B给C。。可以发现要么是A给B,A给C
要么是B给A,C给A。。枚举哪个人被给之类的
由于。。a10+a5+a1≤30,b10+b5+b1≤30,c10+c5+c1≤30。。
这个对于10,5,1还是比较快的。。。
然后可以发现从小到大考虑到话,如果对于后面的数的最大公约数mod的值与目标状态不同
那么说什么也不行了。。
所以可以果断忽略。。
然后再考虑100,50,20.。
他们。。好像都是10的倍数囧。。
所以直接除以10之后再考虑。。就可以快N多从而避免TLE了囧。。
两个部分分别Dp。。。
最后组合一下。。。
就OK了。。

[JSOI2007]麻将

[JSOI2007]麻将

Time Limit:1000MS  Memory Limit:165536K
Total Submit:31 Accepted:10

Description

麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌(共有东、南、西、北、中、发、白七种)和序数牌(分为条子、饼子、万子三种花色,每种花色各有一 到九的九种牌),每种牌各四张。在麻将中,通常情况下一组和了的牌(即完成的牌)由十四张牌组成。十四张牌中的两张组成对子(即完全相同的两张牌),剩余 的十二张组成三张一组的四组,每一组须为顺子(即同花色且序数相连的序数牌,例如条子的三、四、五)或者是刻子(即完全相同的三张牌)。一组听牌的牌是指 一组十三张牌,且再加上某一张牌就可以组成和牌。那一张加上的牌可以称为等待牌。

在这里,我们考虑一种特殊的麻将。在这种特殊的麻将里,没有字牌,花色也只有一种。但是,序数不被限制在一到九的范围内,而是在1到n的范围内。 同时,也没有每一种牌四张的限制。一组和了的牌由3m + 2张牌组成,其中两张组成对子,其余3m张组成三张一组的m组,每组须为顺子或刻子。现给出一组3m + 1张的牌,要求判断该组牌是否为听牌(即还差一张就可以和牌)。如果是的话,输出所有可能的等待牌。

Input

包含两行。
第一行包含两个由空格隔开整数n, m (9<=n<=400, 4<=m<=1000)。第二行包含3m + 1个由空格隔开整数,每个数均在范围1到n之内。这些数代表要求判断听牌的牌的序数。

Output

输出为一行。
如果该组牌为听牌,则输出所有的可能的等待牌的序数,数字之间用一个空格隔开。所有的序数必须按从小到大的顺序输出。如果该组牌不是听牌,则输 出"NO"。

Sample Input

9 4
1 1 2 2 3 3 5 5 5 7 8 8 8

Sample Output

6 7 9

Source

我真是吐血啊。。两个麻将题完全不一样的瀑布汗。。。我顺着上一题的办法拼命搞。。
各种TLE+WA+MLE大囧。。。
最后发现TMD这题分明是贪心题啊。。我真是个沙茶。。。
首先枚举等的牌,
然后枚举哪个是一对,
然后从小到大扫描过去。。
可以发现当前的如果用3次或以上的顺子是沙茶的,所以用的顺子正好是除3的余数。。
然后扫描过去就OK了。。
复杂度是O(N^3)。。。
实际上Hash+Dp也能过很多点的样子。。
Code:
#include <cstdio>
#include <map>
#include <iostream>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=400;
using namespace std;
typedef unsigned long long ull;
int A[maxn]={},B[maxn]={},n,m;
bool Check()
{
rep(cur,n)
if(A[cur]>=2)
{
A[cur]-=2;
rep(i,n)B[i]=A[i];
bool ok=true;
for(int i=0;i<n;)
{
B[i]%=3;
if(!B[i])i++;
else
{
if(i+2<n)
{
if(B[i+1]<B[i]){ok=false;break;}
B[i+1]-=B[i];
if(B[i+2]<B[i]){ok=false;break;}
B[i+2]-=B[i];
i++;
}
else
{
ok=false;
break;
}
}
}
A[cur]+=2;
if(ok)return true;
}
return false;
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
cin>>n>>m;int x;
rep(i,m*3+1)
{
scanf("%d",&x);
A[–x]++;
}
int s=0;
rep(i,n)
{
A[i]++;
if(Check())
{
s++;
printf("%d ",i+1);
}
A[i]–;
}
if(!s)puts("NO");
}

[Zjoi2006]Mahjong麻将

[Zjoi2006]Mahjong麻将

Time Limit:1000MS  Memory Limit:65536K
Total Submit:3 Accepted:3

Description

Input

第一行一个整数N(N<=100),表示玩了N次超级麻将。
接下来N行,每行100个数a1..a100,描述每次玩牌手中各种牌的数量。ai表示数字为i的牌有ai张。(0<=ai& lt;=100)

Output

输出N行,若胡了则输出Yes,否则输出No,注意区分Yes,No的大小写!

Sample Input

3
2 4 0 0 0 0 0 …… 0(一共98个0)
2 4 2 0 0 0 0 …… 0(一共97个0)
2 3 2 0 0 0 0 …… 0(一共97个0)

Sample Output

Yes
Yes
No

Source

Day2

一开始我看AC人数这么少。。以为是BT的难题。。不敢做。。
不过刚刚仔细看了下怎么好像仿佛。。是水题?
注意到从左往右消去每个麻将,首先当前的只能影响3个。。
所以记录当前3个的个数就足够了囧。。同时还要知道那一对有没有被用过。。
所以状态就是 (pos,Apos,Apos+1,Apos+2,have_pair_used)
应该说Dp就可以了。。不过我有点懒。。。所以用了Hash+set。。速度很快啊囧。。
Code:
#include <cstdio>
#include <set>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define Debug(x) cout<<#x<<"="<<x<<endl;
const int inf=~0U>>1,seed=131,maxn=100;
using namespace std;
typedef unsigned long long ull;
ull P[maxn+1];
set<ull> S;
int A[maxn];
bool ok;
void dfs(int p,bool can,ull code)
{
if(!S.insert(code).second)return;
while(p<maxn&&A[p]==0)p++;
if(p==maxn){if(!can)ok=true;return;}
//three consecutive
if(p+2<maxn&&A[p]&&A[p+1]&&A[p+2])
{
A[p]–;A[p+1]–;A[p+2]–;
ull ncode=code-P[p]-P[p+1]-P[p+2];
dfs(p,can,ncode);if(ok)return;
A[p]++;A[p+1]++;A[p+2]++;
}
//three same
if(A[p]>=3)
{
A[p]-=3;
ull ncode=code-P[p]*3;
dfs(p,can,ncode);if(ok)return;
A[p]+=3;
}
//four same
if(A[p]>=4)
{
A[p]-=4;
ull ncode=code-P[p]*4;
dfs(p,can,ncode);if(ok)return;
A[p]+=4;
}
//use pair
if(A[p]>=2&&can)
{
A[p]-=2;
ull ncode=code-P[p]*2-P[maxn];
dfs(p,!can,ncode);if(ok)return;
A[p]+=2;
}
}
void Solve()
{
ull ret=0;
rep(i,maxn)
{
scanf("%d",A+i);
ret*=seed;ret+=A[i];
}
ret*=seed;ret+=1;
S.clear();
ok=false;
dfs(0,true,ret);
if(ok)puts("Yes");
else puts("No");
}
int main()
{
//freopen("in","r",stdin);
P[0]=1;rep(i,maxn)P[i+1]=P[i]*seed;
int t;cin>>t;rep(i,t)Solve();
}

士兵占领

士兵占领

Time Limit:10000MS  Memory Limit:65536K
Total Submit:48 Accepted:32
Case Time Limit:1000MS

Description

有一个M * N的棋盘,有的格子是障碍。现在你要选择一些格子来放置一些士兵,一个格子里最多可以放置一个士兵,障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘 当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。

Input

第一行两个数M, N, K分别表示棋盘的行数,列数以及士兵的个数。
第二行有M个数表示Li。
第三行有N个数表示Ci。
接下来有K行,每行两个数X, Y表示(X, Y)这个格子是障碍。

Output

输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘,输出”JIONG!” (不含引号)

Sample Input

4 4 4
1 1 1 1
0 1 0 3
1 4
2 2
3 3
4 3

Sample Output

4
数据范围
M, N <= 100, 0 <= K <= M * N

Source

哎。。我太SB了。。这题我问了glassices神牛才知道怎么做。。神牛真是太强大了!!
Orz!!!!!
恩。。我一看到这个题目。。第一反应就是网络流。。然后立马感觉到Li和Ci就是所谓的下届,
然后想到上下界网络最小流囧。。。
感觉非常繁琐啊。。然后神牛告诉我说要转化一下。。
先把棋盘放满,如果不能满足就囧了。。
然后可以发现每个行和列能拿掉的最大值就知道了。。
然后最少数=全部数-最多能拿掉几个。。
就成最大流了囧。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxv=200+10,maxn=100;
using namespace std;
int vs,vt,n,m,k,v,ans=0;
struct Edge
{
int t,c;
Edge*next,*op;
Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}
}*E[maxv]={};
void AddEdge(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];
}
bool M[maxn][maxn]={};
int L[maxn],C[maxn];
void Fail()
{
puts("JIONG!");
exit(0);
}
void Init()
{
cin>>n>>m>>k;v=n+m;vs=v++;vt=v++;
rep(i,n)cin>>L[i];
rep(i,m)cin>>C[i];
int x,y;
rep(i,k)
{
scanf("%d%d",&x,&y);–x;–y;
M[x][y]=true;
}
rep(i,n)rep(j,m)if(!M[i][j])L[i]–,C[j]–,ans++;
rep(i,n)if(L[i]>0)Fail();
rep(i,m)if(C[i]>0)Fail();
}
void BuildGraph()
{
rep(i,n)AddEdge(vs,i,-L[i]);
rep(j,m)AddEdge(j+n,vt,-C[j]);
rep(i,n)rep(j,m)if(!M[i][j])
AddEdge(i,j+n,1);
}
bool vis[maxv]={};
int dfs(int no,int m)
{
if(no==vt)return m;
vis[no]=true;
for(Edge*e=E[no];e;e=e->next)if(!vis[e->t]&&e->c)
if(int d=dfs(e->t,min(m,e->c)))
return e->c-=d,e->op->c+=d,d;
return 0;
}
int CalFlow()
{
int flow=0;
do
{
memset(vis,0,sizeof vis);
int d=dfs(vs,inf);
if(d)flow+=d;
else break;
}while(1);
return flow;
}
int main()
{
//freopen("in","r",stdin);
Init();
BuildGraph();
cout<<ans-CalFlow()<<endl;
}

C++中如何实现函数任意长参数。。。

额。。这是一篇有点无聊+SB的文章。。神牛可以无视囧。。。
恩。。比如说你在Dp或者XX的时候。。需要一些个数的最大值,
手动比较和用max都很麻烦的话。。可以考虑用这个可变长形参。。
inline int max(int n,…)
{
va_list ap;
va_start(ap,n);
int ret=-inf,i,x;
rep(i,n){x=va_arg(ap,int);if(x>ret)ret=x;}
va_end(ap);
return ret;
}
然后就可以这么调用了。。
max(3,1,9,8);看上去远没有Java的爽囧。。不过凑合凑合吧。。
va_list是一个预先定义的数据结构,用来储存参数列表的。
va_start就是把参数放到va_list里面去,后面还要跟个n表示参数的个数。。
va_arg(ap,int)每次取出下一个参数,还要指定类型。。
最后一个va_end(ap)表示清空这个,回收内存。。。

还有在#define里面也有这样的用法类似的。。
#define rep(i,n) for(i=0;i<n;i++)
#define SC(…) scanf(__VA_ARGS__)
#define PR(…) printf(__VA_ARGS__)
int main()
{
int x;
SC("%d",&x);
PR("%d",x);
}

快速IO in C++

作为一个使用C++的童鞋。。。龟速的IO往往令人蛋疼。。所以要手动加速。。
(1):cin : scanf = 10 : 1
cin的龟速是闻名的。。。只要输入超过1W个数我就不敢用了。。
(2):
看看下面这个函数:
inline int nextInt()
{
char c;c=getchar();
while(c!=’-‘&&(c<‘0’||c>’9′))c=getchar();
int n=0,s=1;if(c==’-‘)s=-1,c=getchar();
while(c>=’0’&&c<=’9′)n*=10,n+=c-‘0′,c=getchar();
return n*s;
}很显然这是一个很SB的读入数字的函数。。。
但是这个的速度是scanf的4倍瀑布汗。。
(3):Pascal的读入之所以快速是因为里面有读入到缓冲区。。
C++只好手动了。。
#define BUFSIZE 1000000
char buf[BUFSIZE], *pt = buf + BUFSIZE, *pend = buf + BUFSIZE;
int sign;
#define read()
do{
if (pt >= pend)
{
pt = buf;
fread(buf, 1, BUFSIZE, stdin);
}
} while(0)

#define scan(t)
{
t = 0;sign=1;
read();
while ((*pt<‘0’||*pt>’9′)&&*pt!=’-‘) {pt ++; read();}
if(*pt==’-‘)sign=-1,pt++;
while (((*pt) >= ‘0’ && (*pt) <= ‘9’)) {t = t * 10 + (*(pt ++)) – ‘0’; read();}
t*=sign;
}
#define scan_str(s)
{
int p = 0;
read();
while ((*pt) == ‘ ‘ || (*pt) == ‘n’ || (*pt) == ‘r’) {pt ++; read();}
while (!((*pt) == ‘ ‘ || (*pt) == ‘n’ || (*pt) == ‘n’)) {s[p ++] = (*(pt ++)); read();}
s[p] = 0;
}fread就是直接读一大块数据。。速度自然很快。。然后手动模拟缓冲区。。
速度又提高一倍。。跟Pascal差不多了。。
(5):输出也有悲剧的地方。。
int A[20],k;
inline void print_int(int x)
{
if(x<0)putchar(‘-‘),x=-x;
k=0;while(x)A[k++]=x%10,x/=10;
for(int i=k-1;i>=0;i–)putchar(‘0’+A[i]);
putchar(‘n’);
}这么一个函数往往比纯printf快N多。。。
(6):或者干脆输出也用一个缓冲区。。
用一个大数组s存储要输出的字符。。然后一口气输出。。。

【转】追MM算法(转)

动态规划
你追一个MM的时候,需要对该MM身边的各闺中密友都好,这样你追MM这个问题就分解为对其MM朋友的问题,只有把这些问题都解决了,最终你才能追到MM。

该方法适用于聪明的MM,懂得“看一个人,不是看他如何对你,而是看他如何对他人。”的道理,并且对付这样的MM总能得到最优解。

该方法的缺点是开销较大,因为每个子问题都要好好对待。。。。
——————————————————————–

贪心法
你追一个MM的时候,从相识到相知,每次都采用最aggressive的方式,进攻进攻再进攻!从不采用迂回战术或是欲擒故纵之法!目标是以最快的速度确立两人关系。
该法优点是代价小,速度快,但缺点是不是每次都能得到最优解。。。。。
——————————————————————–

回溯算法
追一个MM,但也许你还是情窦初开的新手,不知道如何才能讨得MM的欢心,于是你只好一条路一条路的试,MM不开心了,你就回溯回去换另一种方式。当然其 间你也许会从某些途径得到一些经验,能够判断哪些路径不好,会剪枝(这就是分支估界了)。你也可以随机选择一些路径来实施,说不定能立杆见影(这就是回溯 的优化了)但总的来说,你都需要一场持久战。。。。
该算法一般也能得到最优解,因为大多数MM会感动滴!!但其缺点是开销大!除非你是非要谈一场恋爱不可,否则不推荐使用。特别是你可能还有许多其他的事情要做,比如学习,比如事业。。。。
——————————————————————–

NP完全问题
呵呵,那你为什么那么贱,非要去追呢?记住:“天涯何处无芳草!” 不过如果你“非如此不可”的话,建议升级你的硬件,好好学习,好好工作,加强实力,人到中年的时候也许你能解开NP难。。。。

补充NP:在你追了若干美女都失败告终后,你发现有一批美女追起来是一样困难的,如果你能追到其中任何一个就能追到其他所有的美女,你把这样的女人叫作NP-Complete。
P=NP:这是一个美好的猜想,追美女和恐龙的难度其实一样。
APX与Random:NP的美女难追,你无法完全占有她。你只好随机的去靠近她,装作若无其事;或者用一种策略,追到她的一个approximation ratio,例如50%。
APX-hard:这样的女人,连一个固定的百分比都不给你,还是另谋高就吧。
////////////////////////////////////////////////////////////////////

深度优先和广度优先:
深度优先就是追一个mm追到底,直到失败然后换个mm继续追……
广度优先就是同时追多个mm,一起发展……
////////////////////////////////////////////////////////////////////

二叉树的前序、中序和后序遍历:
前序就是直接搞定MM,然后搞定她爸妈(左)和你自己爸妈(右)
中序就是先搞定未来岳父岳父,然后搞定她,最后告诉你爸妈
后续就是,让未来的岳父岳母和自己爸妈都觉得你们合适之后,才对MM下手,这个时候就没有障碍了啊
////////////////////////////////////////////////////////////////////

网络流
追MM的时候总避免不了送礼物,但是你老是直接送礼物就会给MM造成很大的压力,于是你就想到了通过朋友来转送的方法。你希望送给MM尽可能多的礼 物,所以就是需要找到一中配送方案,就是最大流了。然而你请别人帮忙并不是不要开销的,你让A同学拿去给B同学可能需要一些花费,自然你不是一个大款,想 最小化这个花费,那么就是最小费用最大流了……

SGU 311. Ice-cream Tycoon

311. Ice-cream TycoonTime limit per test: 3 second(s)
Memory limit: 65536 kilobytesinput: standard
output: standard

You’ve recently started an ice-cream business in a local school. During a day you have many suppliers delivering the ice-cream for you, and many students buying it from you. You are not allowed to set the prices, as you are told the price for each piece of ice-cream by the suppliers.

The day is described with a sequence of queries. Each query can be eitherARRIVE n c, meaning that a supplier has delivered n pieces of ice-cream pricedc each to you, or BUY n t, meaning that a student wants to buy n pieces of ice-cream, having a total of t money. The latter is processed as follows: in casen cheapest pieces of ice-cream you have cost no more than t (together), you sell those n cheapest pieces to the student; in case they cost more, she gets nothing. You start the day with no ice-cream.

For each student, output HAPPY if she gets her ice-cream, and UNHAPPYif she doesn’t.

InputThe input file contains between 1 and 105 queries (inclusive), each on a separate line. The queries are formatted as described above, either ARRIVE n cor BUY n t, 1 ≤ nc ≤ 106, 1 ≤ t ≤ 1012.

OutputFor each BUY-query output one line, containing either the word HAPPY or the word UNHAPPY (answers should be in the same order as the corresponding queries).

Example(s) sample input sample output ARRIVE 1 1
ARRIVE 10 200
BUY 5 900
BUY 5 900
BUY 5 1000 HAPPY
UNHAPPY
HAPPY
这个题目一看就是裸的线段树囧。。就是老TLE瀑布汗。。。这次我火了。。写了个带标记的非递归
线段树终于A了内流满面囧。。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxc=1<<20;
using namespace std;
typedef long long ll;
char cmd[100];
#define scan(t)
{
char pt;
while(pt=getchar(),pt<‘0’||pt>’9′);
t=pt-‘0′;
while(pt=getchar(),pt>=’0’&&pt<=’9′)t=t*10+pt-‘0′;
}
bool Mark[1<<21];
ll sum[1<<21]={},num[1<<21]={};
void set(int t)
{
sum[t]=sum[t*2]+sum[t*2+1];
num[t]=num[t*2]+num[t*2+1];
}
void MarkIt(int t)
{
sum[t]=num[t]=0;
Mark[t]=true;
}
void PushDown(int t)
{
if(Mark[t])
MarkIt(t*2),MarkIt(t*2+1);
Mark[t]=false;
}
void Update(int t,ll c)
{
int i,l,r;
for(i=1,l=0,r=maxc;i<maxc;)
{
PushDown(i);i<<=1;
int m=l+r>>1;
if(t>=m)i++,l=m;
else r=m;
}
i=t+maxc;sum[i]+=t*c;num[i]+=c;
for(i>>=1;i;i>>=1)set(i);
}
ll get(int n)
{
if(num[1]<n)return -1;
ll ret=0;int i;
for(i=1;i<maxc;)
{
PushDown(i);i<<=1;
if(num[i]>=n)continue;
ret+=sum[i];n-=num[i];i++;
}
return ll(n)*(i-maxc)+ret;
}
void clear(int n)
{
int i;
for(i=1;i<maxc;)
{
PushDown(i);i<<=1;
if(num[i]>=n)continue;
n-=num[i];MarkIt(i);i++;
}
Update(i-maxc,-n);
}
int main()
{
//freopen("in","r",stdin);
int n;ll c;
while(scanf("%s",cmd)==1)
{
scan(n);scan(c);
if(cmd[0]==’A’)Update(c,n);
else
{
ll tmp=get(n);
if(tmp==-1||tmp>c)
puts("UNHAPPY");
else
puts("HAPPY"),clear(n);
}
}
}

[Zjoi2004]Lunch 午餐

[Zjoi2004]Lunch 午餐

Time Limit:3000MS  Memory Limit:65536K
Total Submit:13 Accepted:9
Case Time Limit:1000MS

Description

上午的训练结束了,THU ACM小组集体去吃午餐,他们一行N人来到了著名的十食堂。这里有两个打饭的窗口,每个窗口同一时刻只能给一个人打饭。由于每个人的口味(以及胃口)不 同,所以他们要吃的菜各有不同,打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同,所以吃饭花费的时间也是可能有所不同的。
THU ACM小组的吃饭计划是这样的:先把所有的人分成两队,并安排好每队中各人的排列顺序,然后一号队伍到一号窗口去排队打饭,二号队伍到二号窗口去排队打 饭。每个人打完饭后立刻开始吃,所有人都吃完饭后立刻集合去六教地下室进行下午的训练。
现在给定了每个人的打饭时间和吃饭时间,要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。
假设THU ACM小组在时刻0到达十食堂,而且食堂里面没有其他吃饭的同学(只有打饭的师傅)。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响 的,而且每个人打饭的时间是和窗口无关的,打完饭之后立刻就开始吃饭,中间没有延迟。
现在给定N个人各自的打饭时间和吃饭时间,要求输出最佳方案下所有人吃完饭的时刻。

Input

第一行一个整数N,代表总共有N个人。
以下N行,每行两个整数 Ai,Bi。依次代表第i个人的打饭时间和吃饭时间。

Output

一个整数T,代表所有人吃完饭的最早时刻。

Sample Input

5
2 2
7 7
1 3
6 4
8 5

Sample Output

17

Hint

方案如下:

窗口1: 窗口2:
7 7 1 3
6 4 8 5
2 2

【限制】
所有输入数据均为不超过200的正整数。

Source

额。这个题目还不错。。挺有意思的。。
首先一看到这经典的模型,可以B大的要在前面。。
然后就可以动归了。。
先按B降序排序。。
用Dp[i][j]表示前i个,第一个队的吃饭时间和为j的最优值。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=201;
using namespace std;
int A[maxn],B[maxn],P[maxn],n;
bool cmp(int i,int j)
{
return B[i]>B[j];
}
int Dp[2][maxn*maxn];
inline void Update(int&t,int c)
{
if(t==-1||t>c)t=c;
}
int main()
{
//freopen("in","r",stdin);
cin>>n;
rep(i,n)
{
cin>>A[i]>>B[i];
P[i]=i;
}
sort(P,P+n,cmp);
int now=0,next=1,sum=0;
memset(Dp[next],-1,sizeof Dp[next]);
Dp[next][0]=0;
for(int i=0;i<n;i++)
{
int t=P[i],c,first,second,nc;
swap(now,next);
memset(Dp[next],-1,sizeof Dp[next]);
rep(j,sum+1)
if((c=Dp[now][j])!=-1)
{
first=j;
second=sum-j;
//Put it In First Queue
nc=max(first+A[t]+B[t],c);
Update(Dp[next][j+A[t]],nc);
//Put it In Second Queue
nc=max(second+A[t]+B[t],c);
Update(Dp[next][j],nc);
}
sum+=A[t];
}
int ans=inf;
rep(i,sum+1)if(Dp[next][i]!=-1)ans=min(ans,Dp[next][i]);
cout<<ans<<endl;
}

[Zjoi2006]trouble 皇帝的烦恼

[Zjoi2006]trouble 皇帝的烦恼

Time Limit:1000MS  Memory Limit:65536K
Total Submit:54 Accepted:20

Description

经过多年的杀戮,秦皇终于统一了中国。为了抵御外来的侵略,他准备在国土边境安置n名将军。
不幸的是这n名将军羽翼渐丰,开始展露他们的狼子野心了。他们拒绝述职、拒绝接受皇帝的圣旨。秦皇已经准备好了秘密处决这些无礼的边防大将。不过 为防兵变,他决定先授予这些将军一些勋章,为自己赢得战略时间。
将军们听说他们即将被授予勋章都很开心,他们纷纷上书表示感谢。第i个将军要求得到ai枚不同颜色的勋章。但是这些将军都很傲气,如果两个相邻的 将军拥有颜色相同的勋章他们就会认为皇帝不尊重他们,会立即造反(编号为i的将军和编号为i+1的将军相邻;因为他们驻扎的边境可以类似看成一个圆形,所 以编号1和编号n的将军也相邻)。
皇帝不得不满足每个将军的要求,但对他们的飞扬跋扈感到很气愤。于是皇帝决定铸造尽量少种类的勋章来满足这些狂妄者的要求。请问他至少要铸造多少 种颜色的勋章?

Input

第一行有一个整数n(1<=n<=20000)。
接下来n行每行一个整数ai,表示第i个将军要求得到多少种勋章。(1<=ai<=100000)

输出一个整数,即最少需要多少种勋章。

Output

4
2
2
1
1

Sample Input

4

Sample Output

Source

Day2
靠。。这道破题让我WAN次。。真是悲剧。。看来太不细心了囧。。。
首先这个题目很显然如果扫描的话,由于是环形的,可以把奖章看成两种,
第一种属于第一个人的,第二种是不属于的。
那么如果Dp的话要记录种数,显然要TLE。。
所以要二分答案。。
然后可以发现每个人能拿的第一种奖章数是一个区间。。
假设第i个人的区间是l,r
那么列出一系列条件(这点一定要考虑周全,不然WA)。。
算出第i+1个人的区间,然后看看第N个人的区间是否包含0。。
Code:

#include <cstdio>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
const int maxn=20000,inf=~0U>>1;
using namespace std;
int a[maxn],n,l[maxn],r[maxn];
inline void checkmin(int&x,int c){if(x>c)x=c;}
inline void checkmax(int&x,int c){if(x<c)x=c;}
bool Check(int K)
{
l[0]=r[0]=a[0];
for(int i=1;i<n;i++)
{
l[i]=-inf;r[i]=inf;
if(a[i-1]+a[i]>K)return false;
checkmin(r[i],a[0]-l[i-1]);
checkmin(r[i],a[0]);
checkmin(r[i],a[i]);
checkmax(l[i],a[0]+a[i-1]+a[i]-K-r[i-1]);
checkmax(l[i],a[i]-K+a[0]);
checkmax(l[i],0);
if(l[i]>r[i])return false;
}
return l[n-1]<=0;
}
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);rep(i,n)scanf("%d",a+i);
int l=0,r=500000;
while(l+1<r)
{
int m=l+r>>1;
if(Check(m))r=m;else l=m;
}
printf("%dn",r);
}

Page 20 of 56« First...10...1819202122...304050...Last »