巢穴

题解

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;
}