[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

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]内部白点

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分，谷粒本来就全班倒数第一了，现在就全年级倒数
第一了。
    谷粒痛苦万分，就跑到桥边望着水发呆。一发就是几天。谷粒觉得自己
的悲伤凝成了水，一尝，像咖啡一样。谷粒觉得自己是一个悲伤的人，悲伤
的人就是有深度的人。谷粒沉浸在自己的悲伤中无法自拔，我似乎看到他一
种莫名的快乐浮了上来。
    桥边还有一个失恋的年轻人，失恋的痛苦早过了，却还一天到晚在桥头
体会自己的悲伤，谷粒问他他女朋友是谁，他说忘了。悲伤这玩意不像是快
乐，可以分享。这个年轻人可能觉得自己已经悲伤出了名气，谷粒偏偏来抢
他的风头，就把谷粒给赶走了。
    谷粒这下体会到真正的悲伤了，他觉得自己不再悲伤了，悲伤万分。迷
迷糊糊想起张洁的《我的四季》，浮现出他将谷粒捧在手里，紧紧地贴近心
窝的样子，感到一阵阵满足，他长久的发着呆，以至于几乎忘记了要去田野。
    可惜他找不到所谓的田野，他只好回了家，捧起一把米，深深的凝望，
贴进心窝。
    这时候我似乎觉得我小说的主角要死了，我跑去他家，看见一个人把一
把米捧在手里，紧紧地贴近心窝，仿佛那是新诞生的一个自我。
  

语文69。。。那个批卷老师居然说我作文写得不错。。什么时候发上来。。