巢穴

題解

Problem 1 : leader
誰是組長

問題描述
    八中信息組需要選一個組長。信息組一共有n個人，分別用1到n編號，其中m個人參與了投票。得票數過半（票數大于m div 2）的人將被選為組長。
    輸入數據將告知這m個人分別將票投給了誰，請統計出誰將擔任八中信息組的組長。

輸入數據
    第一行兩個數n和m。
    第二行有m個數，這些數都是不超過n的正整數，表明這m個人的選擇。

輸出數據
    輸出將被選為組長的人。如果沒有人的票數過半，請輸出-1。

輸入樣例
7 4
7 7 2 7

輸出樣例
7

時間限制
    各測試點1秒

內存限制
    你的程序將被分配10MB的運行空間

數據規模
    1<=n<=maxlongint
    1<=m<=10000

題解: matrix67給出的方法是快排。然后一個O(m)的掃描即可。不過我沒有用這種方法。正巧前幾天看書看到了一道跟這題一模一樣的題。據說曾經是ms的測試題。好了，回歸正題，這題題意無非就是m個數，范圍都在1-n中間，其實n是無用的。然后會有一個數出現的次數>m div 2。我們假設這個數的值是s,那么每次從這組數里去掉兩個不同的數，因為是不同的數，則至多只可從這些數中去掉一個s,那么如此一直進行下去。去到找不到兩個不同的數為止，則至少還會剩下一個s。當然，這是極端情況，大多數情況下應該會剩下不少s。復雜度為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
最小花費

問題描述
    在n個人中，某些人的銀行賬號之間可以互相轉賬。這些人之間轉賬的手續費各不相同。給定這些人之間轉賬時需要從轉賬金額里扣除百分之幾的手續費，請問A最少需要多少錢使得轉賬后B收到100元。

輸入數據
    第一行輸入兩個正整數n,m，分別表示總人數和可以互相轉賬的人的對數。
    以下m行每行輸入三個正整數x,y,z，表示標號為x的人和標號為y的人之間互相轉賬需要扣除z%的手續費 (z<100)。
    最后一行輸入兩個正整數A,B。數據保證A與B之間可以直接或間接地轉賬。

輸出數據
    輸出A使得B到賬100元最少需要的總費用。精確到小數點后8位。

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

輸出樣例
103.07153164

時間限制
    各測試點1秒

內存限制
    你的程序將被分配40MB的運行空間

數據規模
    1<=n<=2000

題解: 比較明顯的最短路徑模型。不過剛轉c++,我竟然不知道如何保留小數點后面的精度，所以這題就沒有寫精度。

#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
最小傷害

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

輸入數據
    第一行輸入一個正整數n。
    以下n行描述該矩陣。矩陣中的數保證是不超過1000的正整數。

輸出數據
    輸出最小傷害值。

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

樣例輸出
8

數據規模
    n<=1000

題解：這題是更加明顯的動態規劃。直接上代碼……

#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
尋找代表

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

輸入數據
    第一行輸入兩個數n和m。
    以下n行每行若干個數，這些數都是不超過m的正整數。其中第i行的數表示社團i的全部成員。每行用一個0結束。

輸出數據
    輸出最多的能夠成為代表的人數。

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

樣例輸出
3

數據范圍
    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;
}