「一家人杯」程序设计大赛 标准程序

/*
ID:LXYXYNT
PROB:1
LANG:C++
*/
#include <iostream>
using namespace std;
 
const int maxn=50001;
int n,ans;
int a[maxn],b[maxn],c[maxn][2],d[maxn];
 
void sort(int l,int r)
{
    int temp,s=l,t=r,k=c[(l+r)>>1][0];
    do{
        while (c[s][0]<k) ++s;
        while (c[t][0]>k) --t;
        if (s<=t)
        {
            temp=c[s][0];c[s][0]=c[t][0];c[t][0]=temp;
            temp=c[s][1];c[s][1]=c[t][1];c[t][1]=temp;
            ++s;--t;
        }
    }while (s<=t);
    if (l<t) sort(l,t);
    if (s<r) sort(s,r);
    return;
}            
 
int main()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    cin >> n;
    for (int i=1;i<=n;++i) 
    {
        cin >> a[i] >> b[i];
        c[i][0]=a[i]+b[i];
        c[i][1]=i;
    }
    sort(1,n);
    c[0][0]=0;
    c[0][1]=0;
    b[0]=0;a[0]=0;
    ans=-9999999;
    for (int i=1;i<=n;++i) 
    {
        d[i]=a[c[i-1][1]]+d[i-1];
        if (d[i]>b[c[i][1]]+ans) ans=(d[i]-b[c[i][1]]);
    }
    cout << ans << endl;
    return 0;
}

/*
ID:LXYXYNT
PROB:2
LANG:C++
*/
#include <iostream>
using namespace std;
const int maxn=10002;
 
int p1,p2,n,s,dp[maxn],sumf[maxn],sumt[maxn],d[maxn];
 
double cal(int i,int j)
{
    return((dp[i]-dp[j])/(sumt[i]-sumt[j]));
}
 
int main()
{
    freopen("2.in","r",stdin);
    freopen("2.out","w",stdout);
 
    cin >> n >> s;
    sumt[n+1]=0;sumf[n+1]=0;
    for (int i=1;i<=n;++i) cin >> sumt[i] >> sumf[i];
    for (int i=n;i>=1;--i) 
    {
        sumf[i]+=sumf[i+1];
        sumt[i]+=sumt[i+1];
    }
 
    dp[n+1]=0;
    p1=1;p2=1;d[1]=n+1;
    for (int i=n;i>=1;--i)
    {
        dp[i]=dp[d[p1]]+(s+sumt[i]-sumt[d[p1]])*sumf[i];
        while ((p2>p1)&&(cal(d[p2],d[p2-1])>cal(i,d[p2]))) --p2;
        d[++p2]=i;
        while ((p2>p1)&&(cal(d[p1+1],d[p1])<sumf[i-1])) ++p1;        
    }
    cout << dp[1] << endl;
    return 0;
}

/* ID: ceeji
   PROG: 3
   Key Point: 位運算
   http://ceeji.net/
 */
#include <iostream>
#include <string>
#include <string.h>
#include <iomanip>
using namespace std;
 
int main()
{
    freopen("3.in","r",stdin);
    freopen("3.out","w",stdout);
    unsigned long num,p,byte1,byte2;
    scanf("%u",&num);
    for (int i = 0; i < num; ++i)
    {
	scanf("%u",&p); 
        byte1 = p>>16;
        byte2 = p<<16;
        printf("%u\n",byte1|byte2);
    }
    fflush(stdout);
    return 0;
}

/* ID: ceeji
   PROG: 4
   Key Point: Tree DP; Sort
   http://ceeji.net/
 */
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <string.h>
 
#define getmin(x,y,z) ((x <= y)&&(x <= z)?x:((y <= z)&&(y <= x)?y:z))
#define min(x,y) (x <= y?x:y)
 
using namespace std;
const int maxn = 5010, len = 10010;
const char* inf = "4.in";
const char* outf = "4.out";
 
int edge[len], next[len], first[len], res[maxn];  
int dp[maxn][3]; 
bool done[maxn];
int edge_count = 0;
 
// 添加邊。
void addedge(int i, int j)
{
     int tmp = first[i];
     first[i] = ++edge_count;
     edge[edge_count] = j;
     next[edge_count] = tmp;
}
 
int comp(const void* c1, const void* c2) 
{
    return *(static_cast<const int*>(c1)) - *(static_cast<const int*>(c2));
}
 
void treedp(int p)
{
     if (done[p]) 
         return;
     done[p] = true;
     dp[p][0] = 1;
     int minc = 60000,s,zg = 0;
     for (int i = first[p], x = edge[i]; i != 0; i = next[i], x = edge[i])
     {
         if (!done[x])
         {
             treedp(x);
	     zg++;
             dp[p][0] += getmin(dp[x][0],dp[x][1],dp[x][2]);
             s = min(dp[x][0],dp[x][1]);
             dp[p][1] += s;
             if ((s == dp[x][1]) && (dp[x][1] != dp[x][0]))
                 minc = min(minc,dp[x][0]-dp[x][1]);
             else
                 minc = -1;
             dp[p][2] += dp[x][1];
         }
     } 
	 if (zg == 0)
	 {
         dp[p][0] = 1;
         dp[p][1] = 50000;
         dp[p][2] = 0;
         return;
	 }
     if (minc != -1)
         dp[p][1] += minc;
}
 
int main()
{
    //init.
    ifstream fin(inf); ofstream fout(outf);
    memset(first,0,sizeof(first));
    memset(done,0,sizeof(done));
    //read data.
    int n, m, tmp, e, tmp2;
    fin >> n >> m >> e;
    for (int i = 1; i <= e; ++i)
    {
            fin >> tmp >> tmp2;
            addedge(tmp,tmp2);
            addedge(tmp2,tmp);
    }
    int z = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (!done[i])
        {
            treedp(i);
            res[z++] = min(dp[i][0],dp[i][1]);
        }
    }
    qsort(res,z,sizeof(res[0]),comp);
    for (int i = 0; i < z; ++i)
    {
        m -= res[i];
        if (m < 0)
        {
              fout << i << endl << flush;
              return 0;
        }
    }
    fout << z << endl << flush;
    return 0;
}