[Cqoi2010]扑克牌

[Cqoi2010]扑克牌

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

Description

你有n种牌,第i种牌的数目为ci。另外有一种特殊的牌:joker,它的数目是m。你可以用每种牌各一张来组成一套牌,也可以用一张joker和除了某 一种牌以外的其他牌各一张组成1套牌。比如,当n=3时,一共有4种合法的套牌:{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。
给出n, m和ci,你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里(可以有牌不使用)。

Input

第一行包含两个整数n, m,即牌的种数和joker的个数。第二行包含n个整数ci,即每种牌的张数。

Output

输出仅一个整数,即最多组成的套牌数目。

Sample Input

3 4
1 2 3

Sample Output

3

样例解释
输入数据表明:一共有1个1,2个2,3个3,4个joker。最多可以组成三副套牌:{1,J,3}, {J,2,3}, {J,2,3},joker还剩一个,其余牌全部用完。

数据范围
50%的数据满足:2 < = n < = 5, 0 < = m < = 10^ 6, 0< = ci < = 200
100%的数据满足:2 < = n < = 50, 0 < = m, ci < = 500,000,000。

Source
额。。刚刚打了一大堆结果Firefox死掉了。。晕死。。简单的说一下算了。。就是二分判定。。详情见Code。
Code:

#include <algorithm>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=100;
using namespace std;
typedef long long ll;
ll A[maxn];int n;
int main()
{
cin>>n;n++;rep(i,n)cin>>A[i];
sort(A,A+n);ll l=0,r=inf;
while(l+1<r)
{
ll m=l+r>>1,s=0;
rep(i,n)if(A[i]<m)s+=m-A[i];
if(s<=m)l=m;else r=m;
}
cout<<l<<endl;
}

[ZJOI2008]泡泡堂BNB

[ZJOI2008]泡泡堂BNB

Time Limit:10000MS Memory Limit:165536K
Total Submit:110 Accepted:41
Case Time Limit:1000MS

Description

第XXXX届NOI期间,为了加强各省选手之间的交流,组委会决定组织一场省际电子竞技大赛,每一个省的代表队由n名选手组成,比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前,对阵双方的教练向组委会提交一份参赛选手的名单,决定了选手上场的顺序,一经确定,不得修改。比赛中,双方的一号选手,二号选手……,n号选手捉对厮杀,共进行n场比赛。每胜一场比赛得2分,平一场得1分,输一场不得分。最终将双方的单场得分相加得出总分,总分高的队伍晋级(总分相同抽签决定)。
作为浙江队的领队,你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚,并将其用一个实力值来衡量。为简化问题,我们假定选手在游戏中完全不受任何外界因素干扰,即实力强的选手一定可以战胜实力弱的选手,而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序,所以所有的队伍都采取了这样一种策略,就是完全随机决定出场顺序。
当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下,浙江队最终分别能得到多少分。

Input

输入的第一行为一个整数n,表示每支代表队的人数。
接下来n行,每行一个整数,描述了n位浙江队的选手的实力值。
接下来n行,每行一个整数,描述了你的对手的n位选手的实力值。
20%的数据中,1<=n<=10;
40%的数据中,1<=n<=100;
60%的数据中,1<=n<=1000;
100%的数据中,1<=n<=100000,且所有选手的实力值在0到10000000之间。

Output

包括两个用空格隔开的整数,分别表示浙江队在最好与最坏的情况下分别能得多少分。不要在行末输出多余的空白字符。

Sample Input

Sample Output

Source

操。。总算做出来了。。这题目搞得我快疯了。。
首先注意到所有分数的和是一样的,那么自己分最低就是对方分最高。。
算法1:O(n^3)的最优匹配,太暴力了,40分。。
算法2:从小到大考虑我的每个选手,那么每次要么打别人最小的,要么打别人最大的。
。O(n^2)。。60分。。
算法3:O(n)。。这个想了我很久,首先假如我方输掉t轮到话,显然是我方的最小的t个去打对方最大的t个,然后剩下来的直接按顺序配对(可以证明是最优的,反证一下就OK了。。)。。那么假如枚举t,一个个算,还是O(n^2)。。但是注意到每个选手+2输掉的轮数范围,+1输掉的轮数范
围都是连续的,那么用前缀和来维护一下就可以了。。
额。。因为还要排序,所以是O(nLogn)。。
Code:
#include <vector>

#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#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++)
const int inf=~0U>>1,maxn=100000+10,maxs=1000;
using namespace std;
int n,A[maxn],B[maxn],C[maxn],m;
inline void Add(int l,int r,int x)
{
    if(r<0||l>r)return;if(l<0)l=0;
    C[l]+=x;C[r+1]-=x;
}
int Solve(int A[maxn],int B[maxn])
{
    int ans=0;
    memset(C,0,sizeof C);
    rep(i,n)
    {
        int l=lower_bound(B,B+n,A[i])-B;
        int r=upper_bound(B,B+n,A[i])-B;
        Add(i-l+1,i,2);
        Add(i-r+1,i-l,1);
    }
    int ret=0;
    rep(i,n)
    {
        ret+=C[i];
        ans=max(ans,ret);
    }
    return ans;
}
int main()
{
    //freopen("in","r",stdin);
    scanf("%d",&n);
    rep(i,n)scanf("%d",A+i);
    rep(i,n)scanf("%d",B+i);
    sort(A,A+n);sort(B,B+n);
    cout<<Solve(A,B)<<" "<<n*2-Solve(B,A)<<endl;
}

2 0样例说明我们分别称4位选手为A,B,C,D。则可能出现以下4种对战方式,最好情况下可得2分,最坏情况下得0分。 一 二 三 四 浙江 ??? 结果 浙江 ??? 结果 浙江 ??? 结果 浙江 ??? 结果一号选手 A C 负 A D 负 B C 胜 B D 负二号选手 B D 负 B C 胜 A D 负 A C 负总得分 0 2 2 021324

[Cqoi2010]内部白点

[Cqoi2010]内部白点

Time Limit:10000MS Memory Limit:65536K
Total Submit:63 Accepted:32
Case Time Limit:2000MS

Description

无限大正方形网格里有n个黑色的顶点,所有其他顶点都是白色的(网格的顶点即坐标为整数的点,又称整点)。每秒钟,所有内部白点同时变黑,直到不存在内部白点为止。你的任务是统计最后网格中的黑点个数。
内部白点的定义:一个白色的整点P(x,y)是内部白点当且仅当P在水平线的左边和右边各至少有一个黑点(即存在x1 < x < x2使得(x1,y)和(x2,y)都是黑点),且在竖直线的上边和下边各至少有一个黑点(即存在y1 < y < y2使得(x,y1)和(x,y2)都是黑点)。

Input

输入第一行包含一个整数n,即初始黑点个数。以下n行每行包含两个整数(x,y),即一个黑点的坐标。没有两个黑点的坐标相同,坐标的绝对值均不超过 109。

Output

输出仅一行,包含黑点的最终数目。如果变色过程永不终止,输出-1。

Sample Input

Sample Output

Source
注意到每个黑点只要当前不能被染黑以后也不会被染黑。。就OK了。。
只要弄个扫描线搞一下,再用树状数组维护部分和就OK了
详情见代码吧。。
Code:
#include <vector>

#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <map>
#include <cstring>
#include <set>
#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 All(x) x.begin(),x.end()
const int inf=~0U>>1,maxn=100000;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n;
struct Index
{
    int A[maxn],n;
    Index(){n=0;}
    void Add(int x){A[n++]=x;}
    void DoIt()
    {
        sort(A,A+n);
        n=unique(A,A+n)-A;
    }
    int operator[](int v)
    {
        return lower_bound(A,A+n,v)-A;
    }
}IndexY;
struct TreeArray
{
    int A[maxn],n;
    TreeArray()
    {
        memset(A,0,sizeof A);
    }
    void SetN(int _n){n=_n;}
    void Add(int x,int d)
    {
        for(x++;x<=n;x+=x&-x)
            A[x-1]+=d;
    }
    int Sum(int x)
    {
        int ret=0;
        for(x++;x;x-=x&-x)
            ret+=A[x-1];
        return ret;
    }
}TA;
map<int,vector<int> > Ps;
typedef map<int,vector<int> >::iterator mit;
int Left[maxn]={},Right[maxn]={};
void Init()
{
    scanf("%d",&n);int x,y;
    rep(i,n)
    {
        scanf("%d%d",&x,&y);
        Ps[x].pb(y);
        IndexY.Add(y);
    }
    IndexY.DoIt();
    for(mit it=Ps.begin();it!=Ps.end();it++)
    {
        vector<int>&V=it->second;
        rep(i,V.size())V[i]=IndexY[V[i]],Right[V[i]]++;
        sort(All(V));
    }
}
#define OK(x) (Left[x]&&Right[x])
inline void Update(int x,int d)
{
    int s=OK(x);
    if(d==1)Left[x]++;
    else Right[x]–;
    TA.Add(x,OK(x)-s);
}
void Solve()
{
    ll ans=0;
    TA.SetN(IndexY.n);
    for(mit it=Ps.begin();it!=Ps.end();it++)
    {
        vector<int>&V=it->second;
        int n=V.size();
        rep(i,n)Update(V[i],-1);
        ans+=TA.Sum(V[n-1])-TA.Sum(V[0]-1);
        rep(i,n)ans-=OK(V[i]);
        rep(i,n)Update(V[i],1);
    }
    cout<<ans+n<<endl;
}
int main()
{
    //freopen("in","r",stdin);
    Init();
    Solve();
}

5数据范围36%的数据满足:n < = 50064%的数据满足:n < = 30000100%的数据满足:n < = 10000040 22 0-2 00 -2

谷粒

我语文考试时候的作文。
题目是:
秋天,我和别人一样收获。望着我那干瘪的谷粒,
心里有一种又酸又苦的欢乐。但我并不因我的谷粒比别人干瘪便灰心或丧气。
我把它们捧在手里,紧紧地贴近心窝,仿佛那是新诞生的一个自我。
看到这个你一定有XXX、XXX、XXX吧,写写你的感受。。

                      谷粒
    不知道为什么我小说的主人公就叫谷粒,在我对着试卷发呆的时候
他突然跑了出来,既然这样我就来讲讲他吧。
    谷粒看了张洁的《我的四季》,倍感亲切,一方面是他自己也叫谷
粒,另一方面他觉得自己虽然一直过得不怎么样,好歹也是什么“新诞
生的一个自我”,高兴坏了。
    正好期末考试了,谷粒看到作文正好是这篇文章,非常高兴,于是
就吧自己大夸了一番,说自己尽管不怎么样但依然对自己很满意,比如
小时候被别人打哭了正说明自己抗击打能力强等等。
    不幸的是语文老师是鲁迅的粉丝,看到这个家伙这么模仿阿Q,非常
不爽,就给他扣了20分,谷粒本来就全班倒数第一了,现在就全年级倒数
第一了。
    谷粒痛苦万分,就跑到桥边望着水发呆。一发就是几天。谷粒觉得自己
的悲伤凝成了水,一尝,像咖啡一样。谷粒觉得自己是一个悲伤的人,悲伤
的人就是有深度的人。谷粒沉浸在自己的悲伤中无法自拔,我似乎看到他一
种莫名的快乐浮了上来。
    桥边还有一个失恋的年轻人,失恋的痛苦早过了,却还一天到晚在桥头
体会自己的悲伤,谷粒问他他女朋友是谁,他说忘了。悲伤这玩意不像是快
乐,可以分享。这个年轻人可能觉得自己已经悲伤出了名气,谷粒偏偏来抢
他的风头,就把谷粒给赶走了。
    谷粒这下体会到真正的悲伤了,他觉得自己不再悲伤了,悲伤万分。迷
迷糊糊想起张洁的《我的四季》,浮现出他将谷粒捧在手里,紧紧地贴近心
窝的样子,感到一阵阵满足,他长久的发着呆,以至于几乎忘记了要去田野。
    可惜他找不到所谓的田野,他只好回了家,捧起一把米,深深的凝望,
贴进心窝。
    这时候我似乎觉得我小说的主角要死了,我跑去他家,看见一个人把一
把米捧在手里,紧紧地贴近心窝,仿佛那是新诞生的一个自我。
  

Page 4 of 41234