巢穴

題解

Problem 1 : leader
誰(shuí)是組長(zhǎng)

問(wèn)題描述
    八中信息組需要選一個(gè)組長(zhǎng)。信息組一共有n個(gè)人，分別用1到n編號(hào)，其中m個(gè)人參與了投票。得票數(shù)過(guò)半（票數(shù)大于m div 2）的人將被選為組長(zhǎng)。
    輸入數(shù)據(jù)將告知這m個(gè)人分別將票投給了誰(shuí)，請(qǐng)統(tǒng)計(jì)出誰(shuí)將擔(dān)任八中信息組的組長(zhǎng)。

輸入數(shù)據(jù)
    第一行兩個(gè)數(shù)n和m。
    第二行有m個(gè)數(shù)，這些數(shù)都是不超過(guò)n的正整數(shù)，表明這m個(gè)人的選擇。

輸出數(shù)據(jù)
    輸出將被選為組長(zhǎng)的人。如果沒(méi)有人的票數(shù)過(guò)半，請(qǐng)輸出-1。

輸入樣例
7 4
7 7 2 7

輸出樣例
7

時(shí)間限制
    各測(cè)試點(diǎn)1秒

內(nèi)存限制
    你的程序?qū)⒈环峙?0MB的運(yùn)行空間

數(shù)據(jù)規(guī)模
    1<=n<=maxlongint
    1<=m<=10000

題解: matrix67給出的方法是快排。然后一個(gè)O(m)的掃描即可。不過(guò)我沒(méi)有用這種方法。正巧前幾天看書(shū)看到了一道跟這題一模一樣的題。據(jù)說(shuō)曾經(jīng)是ms的測(cè)試題。好了，回歸正題，這題題意無(wú)非就是m個(gè)數(shù)，范圍都在1-n中間，其實(shí)n是無(wú)用的。然后會(huì)有一個(gè)數(shù)出現(xiàn)的次數(shù)>m div 2。我們假設(shè)這個(gè)數(shù)的值是s,那么每次從這組數(shù)里去掉兩個(gè)不同的數(shù)，因?yàn)槭遣煌臄?shù)，則至多只可從這些數(shù)中去掉一個(gè)s,那么如此一直進(jìn)行下去。去到找不到兩個(gè)不同的數(shù)為止，則至少還會(huì)剩下一個(gè)s。當(dāng)然，這是極端情況，大多數(shù)情況下應(yīng)該會(huì)剩下不少s。復(fù)雜度為O(m)

#include <iostream>
#include <fstream>
#include <memory.h>
using namespace std;

ifstream fin("leader.in");
ofstream fout("leader.out");

const int maxm=10000;

int n,m;
long f[maxm];
bool h[maxm];
void init()
{
     fin>>n>>m;
     for (int i=0;i<m;i++)
     {
         fin>>f[i];
     }
}
void solve()
{
     memset(h,false,sizeof(h));
     for (int i=0;i<m;i++)
     {
         if (h[i]) continue;
         int u=i+1;
         while (u<m)
         {
               if (f[i]!=f[u])
               {
                  h[i]=true;
                  h[u]=true;
                  break;
               }
               u++;
         }
     }
     for (int i=0;i<m;i++)
     {
        
         if (!h[i])
         {
            fout<<f[i]<<endl;
            exit(0);
         }
     }
}
int main()
{
    init();
    solve();

    return 0;
}

Problem 2 : money
最小花費(fèi)

問(wèn)題描述
    在n個(gè)人中，某些人的銀行賬號(hào)之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬的手續(xù)費(fèi)各不相同。給定這些人之間轉(zhuǎn)賬時(shí)需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費(fèi)，請(qǐng)問(wèn)A最少需要多少錢(qián)使得轉(zhuǎn)賬后B收到100元。

輸入數(shù)據(jù)
    第一行輸入兩個(gè)正整數(shù)n,m，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對(duì)數(shù)。
    以下m行每行輸入三個(gè)正整數(shù)x,y,z，表示標(biāo)號(hào)為x的人和標(biāo)號(hào)為y的人之間互相轉(zhuǎn)賬需要扣除z%的手續(xù)費(fèi) (z<100)。
    最后一行輸入兩個(gè)正整數(shù)A,B。數(shù)據(jù)保證A與B之間可以直接或間接地轉(zhuǎn)賬。

輸出數(shù)據(jù)
    輸出A使得B到賬100元最少需要的總費(fèi)用。精確到小數(shù)點(diǎn)后8位。

輸入樣例
3 3
1 2 1
2 3 2
1 3 3
1 3

輸出樣例
103.07153164

時(shí)間限制
    各測(cè)試點(diǎn)1秒

內(nèi)存限制
    你的程序?qū)⒈环峙?0MB的運(yùn)行空間

數(shù)據(jù)規(guī)模
    1<=n<=2000

題解: 比較明顯的最短路徑模型。不過(guò)剛轉(zhuǎn)c++,我竟然不知道如何保留小數(shù)點(diǎn)后面的精度，所以這題就沒(méi)有寫(xiě)精度。

#include <iostream>
#include <fstream>
#include <memory.h>
using namespace std;

ifstream fin("money.in");
ofstream fout("money.out");


const int maxn=2000;
int n,m;
int f[maxn+1][maxn+1];
int s,t;
double dist[maxn+1];
bool hash[maxn+1];
void init()
{
     fin>>n>>m;
     int a,b,c;
     for (int i=0;i<m;i++)
     {
         fin>>a>>b>>c;
         f[a][b]=c;
         f[b][a]=c;
     }
     fin>>s>>t;
}
void solve()
{

     for (int i=1;i<=n;i++)
     {
         if (f[s][i]==0)
         {
          dist[i]=100000.0;
          continue;
         }
         dist[i]=100.0*100/(double)(100-f[s][i]);

     }
     dist[s]=100000.0;hash[s]=true;

     for (int i=1;i<n;i++)
     {
         double min=100000.0;
         int u=0;
         for (int j=1;j<=n;j++)
         {
             if (hash[j]) continue;
             if (min>dist[j]) {min=dist[j];u=j;}
         }
         hash[u]=true;
         for (int j=1;j<=n;j++)
         {
             if (f[u][j]==0) continue;
             if (dist[j]>dist[u]*100/(double)(100-f[u][j]))
                dist[j]=dist[u]*100/(double)(100-f[u][j]);
         }
     }
   //  printf()l;
    // fout.precision(11);
     fout<<dist[t]<<endl;
     
}
int main()
{
    init();
    solve();
    return 0;
}

Problem 3 : harm
最小傷害

問(wèn)題描述
    把兒站在一個(gè)N x N的方陣中最左上角的格子里。他可以從一個(gè)格子走到它右邊和下邊的格子里。每一個(gè)格子都有一個(gè)傷害值。他想在受傷害最小的情況下走到方陣的最右下角。

輸入數(shù)據(jù)
    第一行輸入一個(gè)正整數(shù)n。
    以下n行描述該矩陣。矩陣中的數(shù)保證是不超過(guò)1000的正整數(shù)。

輸出數(shù)據(jù)
    輸出最小傷害值。

樣例輸入
3
1 3 3
2 2 2
3 1 2

樣例輸出
8

數(shù)據(jù)規(guī)模
    n<=1000

題解：這題是更加明顯的動(dòng)態(tài)規(guī)劃。直接上代碼……

#include <iostream>
#include <fstream>
#include <memory.h>
using namespace std;

ifstream fin("harm.in");
ofstream fout("harm.out");

const int maxn=1000;
int n;
int sum[maxn+1][maxn+1];
int dp[maxn+1][maxn+1];
int min(int x,int y)
{
    return x<y?x:y;
}
void init()
{
     fin>>n;
     for (int i=1;i<=n;i++)
     {
         for (int j=1;j<=n;j++)
         {
             fin>>sum[i][j];
         }
     }
}
void solve()
{
     memset(dp,0,sizeof(dp));
     for (int i=1;i<=n;i++)
     {
         for (int j=1;j<=n;j++)
         {
             if (i==1) {dp[i][j]=dp[i][j-1]+sum[i][j];continue;}
             if (j==1) {dp[i][j]=dp[i-1][j]+sum[i][j];continue;}
             dp[i][j]=min(dp[i-1][j],dp[i][j-1])+sum[i][j];
         }
     }
     fout<<dp[n][n]<<endl;
}
int main()
{
    init();
    solve();
    return 0;
}

Problem 4 : unique
尋找代表

問(wèn)題描述
    八中一共有n個(gè)社團(tuán)，分別用1到n編號(hào)。
    八中一共有m個(gè)人，分別用1到m編號(hào)。每個(gè)人可以參加一個(gè)或多個(gè)社團(tuán)，也可以不參加任何社團(tuán)。
    每個(gè)社團(tuán)都需要選一個(gè)代表。我們希望更多的人能夠成為代表。

輸入數(shù)據(jù)
    第一行輸入兩個(gè)數(shù)n和m。
    以下n行每行若干個(gè)數(shù)，這些數(shù)都是不超過(guò)m的正整數(shù)。其中第i行的數(shù)表示社團(tuán)i的全部成員。每行用一個(gè)0結(jié)束。

輸出數(shù)據(jù)
    輸出最多的能夠成為代表的人數(shù)。

樣例輸入
4 4
1 2 0
1 2 0
1 2 0
1 2 3 4 0

樣例輸出
3

數(shù)據(jù)范圍
    n,m<=200

題解：2分圖匹配，匈牙利算法。

#include <iostream>
#include <fstream>
#include <memory.h>

using namespace std;
const int maxn=200;

ifstream  fin("unique.in");
ofstream fout("unqiue.out");
int n,m;
bool connect[maxn+1][maxn+1];
bool used[maxn+1];
int  ms[maxn+1];
void init()
{
     fin>>n>>m;
     for (int i=1;i<=n;i++)
     {
         while (true)
         {
            int c;
            fin>>c;
            if (c==0) break;
            connect[i][c]=true;
         }
     }
     
}
bool check(int x)
{
        for (int i=1;i<=m;i++)
        {
            if ((!used[i])&&(connect[x][i]))
            {
               used[i]=true;
               if ((ms[i]==0)||(check(ms[i])))
               {
                  ms[i]=x;
                  return true;
               }
            }
            
        }
        return false;
}
void solve()
{
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        memset(used,false,sizeof(used));
        if (check(i))
        {
                     ans++;
        }
        
    }
    fout<<ans<<endl;
}
int main()
{
    init();
    solve();
    return 0;
}