Monthly Archives: October 2014

POJ 1258-Agri-Net

POJ 1258-Agri-Net
Agri-Net
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 40975 Accepted: 16713
Description
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.
Input
The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.
Output
For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.
Sample Input
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
Sample Output
28
Source
USACO 102


这一题相对第2485来说就更是彻头彻尾的最小生成树了。它要求的是最小生成树的总长度,所以对2485稍微修改即可。需要注意的是题目中有这么一句话:

The input includes several cases.

也就是说有多个测试用例,而不是直接告诉你有几个用例或者结束标志是0 0 0之类的,我一开始写成了

while(1)
{
     scanf("%d",&n);
      ...
}

这样就变成了有无穷个测试用例了,根本停不下来,所以Time Limit Exceeded好几次,后来改成这样就好了:

while(scanf("%d",&n)!=EOF)
{
     ...
}

完整的代码如下:

#include<stdio.h>
int a[101][101];
int lowcost[101];
//int closet[101];
const static int MAX_DIS=100001; //最长距离
//prim算法求最小生成树
int prim(int n)
{
     for(int i=0;i<n;i++)
     {
          lowcost[i]=a[0][i];
          //closet[i]=0;//这个数组可以不要
     }
     int total_min_len=0;
     int k,curr_min_len;
     for(int t=0;t<n-1;t++)
     {
          k=0;
          curr_min_len=MAX_DIS;
          for(int i=0;i<n;i++)
          {
               if(lowcost[i]!=0&&lowcost[i]<curr_min_len)
               {
                    curr_min_len=lowcost[i];
                    k=i;
               }
          }
          total_min_len+=curr_min_len;//这题才是求和
          //if(curr_min_len>total_min_len)//注意看题,求最小生成树中的最长路径
          //     total_min_len=curr_min_len;
          lowcost[k]=0;
          for(int i=0;i<n;i++)
          {
               if(a[i][k]!=0&&a[i][k]<lowcost[i])
               {
                    lowcost[i]=a[i][k];
                    //closet[i]=k;
               }
          }
     }
     return total_min_len;
}
int main()
{
     int n;
     //while(1)//The input includes several cases.并不代表case无穷
     while(scanf("%d",&n)!=EOF)
     {
          //scanf("%d",&n);
          for(int i=0;i<n;i++)
               for(int j=0;j<n;j++)
                    scanf("%d",&a[i][j]);
          printf("%d\n",prim(n));
     }
     return 0;
}

本代码提交AC,用时16MS,内存172K。可以看到内存明显比2485题少了,那是因为我把closet数组删了,因为常规的最小生成树不需要这个变量。

POJ 2485-Highways

POJ 2485-Highways
Highways
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 22907 Accepted: 10553
Description
The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They're planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.
Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.
The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.
Input
The first line of input is an integer T, which tells how many test cases followed.
The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case.
Output
For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.
Sample Input
1
3
0 990 692
990 0 179
692 179 0
Sample Output
692
Hint
Huge input,scanf is recommended.
Source
POJ Contest,Author:Mathematica@ZSU


原始的最小生成树算法,但是要注意题目要我们求解的是什么:

which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.

最小生成树中的最长路径,而不是最小生成树!读题一定要仔细。
代码如下:

#include<stdio.h>
int a[501][501];
int lowcost[501];
int closet[501];
//prim算法求最小生成树
int prim(int n)
{
     for(int i=0;i<n;i++)
     {
          lowcost[i]=a[0][i];
          closet[i]=0;//这个数组可以不要
     }
     int total_min_len=0;
     int k,curr_min_len;
     for(int t=0;t<n-1;t++)
     {
          k=0;
          curr_min_len=65537;
          for(int i=0;i<n;i++)
          {
               if(lowcost[i]!=0&&lowcost[i]<curr_min_len)
               {
                    curr_min_len=lowcost[i];
                    k=i;
               }
          }
          //total_min_len+=curr_min_len;
          if(curr_min_len>total_min_len)//注意看题,求最小生成树中的最长路径
               total_min_len=curr_min_len;
          lowcost[k]=0;
          for(int i=0;i<n;i++)
          {
               if(a[i][k]!=0&&a[i][k]<lowcost[i])
               {
                    lowcost[i]=a[i][k];
                    closet[i]=k;
               }
          }
     }
     return total_min_len;
}
int main()
{
     int t,n;
     scanf("%d",&t);
     while(t--)
     {
          scanf("%d",&n);
          for(int i=0;i<n;i++)
               for(int j=0;j<n;j++)
                    scanf("%d",&a[i][j]);
          printf("%d\n",prim(n));
     }
     return 0;
}

本代码提交AC,用时157MS,内存528K。

hihoCoder 1051-补提交卡

hihoCoder 1051-补提交卡
#1051 : 补提交卡
时间限制:2000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho给自己定了一个宏伟的目标:连续100天每天坚持在hihoCoder上提交一个程序。100天过去了,小Ho查看自己的提交记录发现有N天因为贪玩忘记提交了。于是小Ho软磨硬泡、强忍着小Hi鄙视的眼神从小Hi那里要来M张"补提交卡"。每张"补提交卡"都可以补回一天的提交,将原本没有提交程序的一天变成有提交程序的一天。小Ho想知道通过利用这M张补提交卡,可以使自己的"最长连续提交天数"最多变成多少天。
输入
第一行是一个整数T(1 <= T <= 10),代表测试数据的组数。
每个测试数据第一行是2个整数N和M(0 <= N, M <= 100)。第二行包含N个整数a1, a2, ... aN(1 <= a1 < a2 < ... < aN <= 100),表示第a1, a2, ... aN天小Ho没有提交程序。
输出
对于每组数据,输出通过使用补提交卡小Ho的最长连续提交天数最多变成多少。
样例输入
3
5 1
34 77 82 83 84
5 2
10 30 55 56 90
5 10
10 30 55 56 90
样例输出
76
59
100


这一题想到那个点上就不难了,题目要求将补提交卡插入空缺的某天中,使连续提交天数最长。要使连续提交天数最长,补提交卡插入的位置也一定要是连续的,而且很方便的是,题目中给出的空缺天数都是递增的,所以不需要重新排序了。
既然需要满足插入的位置也要连续,那么总的方案数就没有那么多了。比如n=5,m=2,有如下几种方案:

左边的红色数字表示不同方案标号,这个标号也正好是该方案中数组a中的第一个插空位置的下标。很容易得到总的方案数有n-m+1个,所以我们只需将i从0到n-m+1循环枚举每一种方案,求最长的连续提交天数。
对于某一种方案,如上所述,其插空的开始下标正好为i,因为要插m个空,所以结束下标为m+i-1。那么这两者之间总的连续提交天数怎么算呢?比如上图中的方案2,如果把第55和56天填上,那么实际的连续提交天数应该是从31~89.也就是要从i-1对应的那天的后一天(31)算起,到m+i-1-1对应的那天的前一天(89)结束,总共就是89-31+1,也就是a[m+i-1+1]-a[i-1]-1;如果遇到最后一个空,因为m+i-1+1可能超过数组a的范围,所以我们添加一个a[n]=101,俗称哨兵;如果i==0的话,没有i-1,所以分开讨论。
最终的代码如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
     int t;
     cin>>t;
     int n,m;
     while(t--)
     {
          cin>>n>>m;
          vector<int> a(n+1);
          for(int i=0;i<n;i++)
               cin>>a[i];
          a[n]=101;//哨兵
          if(m>=n)
               cout<<100<<endl;
          else
          {
               int max_days=0;//最长连续提交天数
               int case_num=n-m+1;//总的枚举情况数
               for(int i=0;i<case_num;i++)
               {
                    int last_index=m+i-1;//该方案下最后一个下标
                    if(i==0)
                    {
                         if(a[last_index+1]-1>max_days)
                              max_days=a[last_index+1]-1;
                    }
                    else
                    {
                         if(a[last_index+1]-a[i-1]-1>max_days)
                              max_days=a[last_index+1]-a[i-1]-1;
                    }
               }
               cout<<max_days<<endl;
          }
     }
     return 0;
}

本代码提交AC,用时0MS,内存0MB。

POJ 1019-Number Sequence

POJ 1019-Number Sequence
Number Sequence
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 34278 Accepted: 9835
Description
A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2...Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another.
For example, the first 80 digits of the sequence are as follows:
11212312341234512345612345671234567812345678912345678910123456789101112345678910
Input
The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)
Output
There should be one output line per test case containing the digit located in the position i.
Sample Input
2
8
3
Sample Output
2
2
Source
Tehran 2002, First Iran Nationwide Internet Programming Contest


做这一题需要细心,我们先分析一下题意。给出一串数字,问你这个数字串中第i个位置的数字是什么。其中数字串是形如112123123412345123456123456712345678123456789123456789101234567891011123456789101112这样的。
仔细分析一下就是1、12、123、1234,...,123456789、12345678910、1234567891011,... 串联起来的。我们定义单个数字串1234...i的长度为single_len[i],总的数字串1,12,123,...,123...i.的长度为total_len[i]。因为1,12,123,...,123...i.=1,12,123,...,123...(i-1).+123...i.所以我们可以得出一个等式:total_len[i]=total_len[i-1]+single_len[i]。那么怎么来求解single_len[i]呢?
single_len[0]=0; single_len[1]=1; single_len[2]=2; single_len[10]=11. 因为single_len[i]为123...(i-1)i的长度,single_len[i-1]为123...(i-1)的长度。很显然,single_len[i]=single_len[i-1]+数字i的长度。这有点类似动态规划的状态转移方程。求数字i的长度可以用下面的函数求解:

//求数字i的位数
int get_digits_num(int i)
{
     int rs=1;
     while(i>=10)
     {
          rs++;
          i/=10;
     }
     return rs;
}

当然也可以用stringstream先将int转换为string再求string.size(),但是这种方法更慢。
当我们求到了single_len和total_len,就可以分两步求解总的数字串中第i个位置的数字了。首先在total_len中找到位置i在哪一个内部串中,然后再在内部串中找到位置i的确切位置。这就有点像信号调节中的粗调和微调,首先找到大致的位置,然后在某个局部找细节的位置。
比如给定数字串112123123412345123456123456712345678123456789123456789101234567891011123456789101112。问i=18位置处的数字是什么。我们已经求到total_len[0]=0; total_len[1]=1; total_len[2]=3; total_len[3]=6; total_len[4]=10; total_len[5]=15; total_len[6]=21; 。18正好在total_len[5]和total_len[6]之间。因为total_len[5]=15表示以5结束的总的数字串的长度为15<18,所以我们取total_len[6],也就是i=18必定在以6结尾的总的数字串中,即在112123123412345123456中,且在以6结尾的单个数字串中的第i-total_len[6-1]=18-15=3个位置,也就是在123456的第3个位置即3,所以最终结果就是3。
所以总结一下求解的步骤就是:
1. 计算single_len和total_len。
2. 在total_len中二分查找位置i在以last_num为末尾数字的总的串中。
3. 计算出在以last_num为末尾数字的单个内部串中位置i所在的相对位置inner_index。
4. 在以last_num为末尾数字的单个内部串中二分查找出相对位置为inner_index的数字。
其中要数第4步最难,其二分搜索函数如下:

//(单组数字串)内部二分搜索
char bin_search_inner(int i)
{
     int s=1,t=MAX_N,mid;
     while(s<t)
     {
          mid=(s+t)/2;
          if(single_len[mid]<i)
               s=mid+1;
          else if(single_len[mid]==i)
          {
               string s=int2string(mid);
               return s[s.size()-1];
          }
          else
               t=mid-1;
     }
     if(single_len[t]<i)
          t++;
     string rs=int2string(t);
     return rs[rs.size()-(single_len[t]-i)-1];
}

其中的single_len[mid]==i分支:比如single_len[12]=15; single_len[13]=17;如果mid==12; i==15.结果是多少呢?single_len[12]=15表示以12结尾的数字串的长度为15,而i正好为15,所以结果应该为123456789101112的最后一个数字2。
假设single_len[1234]=9843; i=9841; 这时t=1234,结果又是多少呢?假设我们到了rs[rs.size()-(single_len[t]-i)-1];这一步。通过直观观察,i=9841的位置是2,因为single_len[1234]=9843表示1234末尾的数字4的i=9843,往前推自然得到i=9841时数字为2;怎样写成一个公式呢?single_len[t]-i=2表示位置i离末尾数字的距离为2,那么它离开头的距离为多少呢?很显然用t(也就是rs=int2string(t))的总长度减去离末尾的距离再减1就行了。也就是rs[rs.size()-(single_len[t]-i)-1];,所以我们是从这个数字的末尾往前推的。
还要注意一下i最大为2147483647,2147483647刚好是int的正整数最大极限值,所以total_len要用unsigned int。其他的就没有太多要解释的了。具体看代码:

#include<iostream>
#include<string>
#include<sstream>
#include<cstdlib>
using namespace std;
const static int MAX_N=31269;//数字串中最大的数
int single_len[MAX_N]={0};//single_len[i]表示1,2,3,...,i.这个数字串中总的数字位数
unsigned int total_len[MAX_N]={0};//total_len[i]表示1,12,123,...,123...i.这个数字串中总的数字位数
//将int转换为string
string int2string(int i)
{
     stringstream ss;
     string s;
     ss<<i;
     ss>>s;
     return s;
}
//求数字i的位数
int get_digits_num(int i)
{
     int rs=1;
     while(i>=10)
     {
          rs++;
          i/=10;
     }
     return rs;
}
//初始化单组数字串
void init_single_len()
{
     for(int i=1;i<MAX_N;i++)
     {
          single_len[i]=single_len[i-1]+get_digits_num(i);
     }
}
//初始化总体数字串
void init_total_len()
{
     for(int i=1;i<MAX_N;i++)
     {
          total_len[i]=total_len[i-1]+single_len[i];
     }
}
//外部(总体)二分搜索
int bin_search_outer(int i)
{
     int s=1,t=MAX_N-1,mid;
     while(s<t)
     {
          mid=(s+t)/2;
          if(total_len[mid]<i)
               s=mid+1;
          else if(total_len[mid]==i)
               return mid;
          else
               t=mid-1;
     }
     if(total_len[t]<i)
          return t+1;
     else
          return t;
}
//(单组数字串)内部二分搜索
char bin_search_inner(int i)
{
     int s=1,t=MAX_N,mid;
     while(s<t)
     {
          mid=(s+t)/2;
          if(single_len[mid]<i)
               s=mid+1;
          else if(single_len[mid]==i)
          {
               string s=int2string(mid);
               return s[s.size()-1];
          }
          else
               t=mid-1;
     }
     if(single_len[t]<i)
          t++;
     string rs=int2string(t);
     return rs[rs.size()-(single_len[t]-i)-1];
}
int main()
{
     int t,i;
     cin>>t;
     init_single_len();
     init_total_len();
     //cout<<total_len[31268]<<endl;
     while(t--)
     {
          cin>>i;
          int last_num=bin_search_outer(i);
          int inner_index=i-total_len[last_num-1];
          cout<<bin_search_inner(inner_index)<<endl;
     }
     return 0;
}

本代码提交AC,用时16MS,内存464K。

hihoCoder 1043-完全背包

hihoCoder 1043-完全背包
#1043 : 完全背包
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
且说之前的故事里,小Hi和小Ho费劲心思终于拿到了茫茫多的奖券!而现在,终于到了小Ho领取奖励的时刻了!
等等,这段故事为何似曾相识?这就要从平行宇宙理论说起了………总而言之,在另一个宇宙中,小Ho面临的问题发生了细微的变化!
小Ho现在手上有M张奖券,而奖品区有N种奖品,分别标号为1到N,其中第i种奖品需要need(i)张奖券进行兑换,并且可以兑换无数次,为了使得辛苦得到的奖券不白白浪费,小Ho给每件奖品都评了分,其中第i件奖品的评分值为value(i),表示他对这件奖品的喜好值。现在他想知道,凭借他手上的这些奖券,可以换到哪些奖品,使得这些奖品的喜好值之和能够最大。
提示一: 切,不就是0~1变成了0~K么
提示二:强迫症患者总是会将状态转移方程优化一遍又一遍
提示三:同样不要忘了优化空间哦!
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第一行为两个正整数N和M,表示奖品的种数,以及小Ho手中的奖券数。
接下来的n行描述每一行描述一种奖品,其中第i行为两个整数need(i)和value(i),意义如前文所述。
测试数据保证
对于100%的数据,N的值不超过500,M的值不超过10^5
对于100%的数据,need(i)不超过2*10^5, value(i)不超过10^3
输出
对于每组测试数据,输出一个整数Ans,表示小Ho可以获得的总喜好值。
样例输入
5 1000
144 990
487 436
210 673
567 58
1056 897
样例输出
5940


这一题和之前的0-1背包很类似,只需要稍微修改一下就可以了。
我们先来复习一下之前的0-1背包。0-1背包对于一件物品,要么兑换,要么不兑换,只有两种可能。假设V[i,j]表示用j张奖券兑换前i个物品,则对于第i个物品,我们只有两种选择:1.兑换;2.不兑换。如果不兑换,则V[i,j]=V[i-1,j],也就是不要第i件物品,用j张奖券兑换前i-1个物品;如果兑换,则V[i,j]=V[i-1,j-need[i]]+value[i],也就是一定要第i件物品,所以+value[i],然后再看兑换完第i件物品后剩余的奖券兑换前i-1个物品能得到多少价值。最后就是求这两种情况的最大值。用数学公式表示就是:

V[i,j] = \begin{cases}0 & \text{if i=0 or j=0} \\V[i-1,j] & \text{if j < need[i]} \\max \{ V[i-1,j],V[i-1,j-need[i]]+value[i] \} & \text{if i>0 and j$\geq$ need[i]}\\\end{cases}


上面是0-1背包的动态规划状态转换方程,详细的代码可以参考上面的链接。对于完全背包,只需稍微修改即可。
我们首先要理解完全背包的含义,完全背包不限制物品的个数,也就是只要奖券够多,可以兑换多个同一种物品但是对于某一个物品,也只有两种情况,要么兑换,要么不兑换,不可以将某一件物品拆分成小部分,只兑换其中的0.x。这个地方容易和分数背包混淆。分数背包和0-1类似,每一种物品也只有一个,你可以完整的兑换这一个物品,也可以只兑换这个物品的一部分,但是一种物品只有一个。分数背包可以用贪心算法快速求解,可以参考《算法导论第三版》中文版P243关于0-1背包和分数背包的讨论。
理解了完全背包的含义,我们再来推导其状态转换方程。这个时候对于第i个物品,我们有多种选择:1.不兑换;2.兑换1个;3.多换多个。同样的,我们要从中选一个能使价值最大的方案。如果不兑换,和0-1背包一样,有V[i,j]=V[i-1,j];但是如果兑换,是不是得一一尝试兑换1个、2个...的所有方案呢?可以这样做,但是还有一个更巧妙的方法,我们先给出公式再解释:

V[i,j] = \begin{cases}0 & \text{if i=0 or j=0} \\V[i-1,j] & \text{if j<need[i]} \\max \{ V[i-1,j],V[i,j-need[i]]+value[i] \} & \text{if i>0 and j$\geq$ need[i]}\\\end{cases}


大家仔细对比0-1背包和完全背包的状态转换方程,只改动了一个微小的地方。对于第i个物品,我们如果兑换,则肯定要+value[i],这是剩下j-need[i]张奖券,因为第i个物品可以兑换多个,所以我们还是用j-need[i]张奖券兑换前i个物品,而不是只兑换前i-1个物品,即V[i,j]=V[i,j-need[i]]+value[i]这样的话,程序自然还会考虑选择第i个物品,也就是兑换多个第i个物品。这就是0-1背包和完全背包的重要区别。
理解了这一点,我们很快就可以写出程序了。代码如下:

#include <iostream>
#include<vector>
using namespace std;
int main()
{
     int n,m;
     cin>>n>>m;
     vector<int> need_vi(n),value_vi(n);
     for(int i=0;i<n;i++)
          cin>>need_vi[i]>>value_vi[i];
     vector<int> V(m+1,0);//V[j]表示有j张奖券,装前i个奖品获得的最大评分
     for(int i=0;i<n;i++)//V[j]表示有j张奖券,装前i个奖品获得的最大评分,每个奖品可以装多个
     {
          for(int j=need_vi[i];j<=m;j++)//从前往后填表,因为这是完全背包
          {
               V[j]=(V[j-need_vi[i]]+value_vi[i]>V[j])?(V[j-need_vi[i]]+value_vi[i]):V[j];
          }
     }
     cout<<V[m];
     return 0;
}

具体到写代码时,因为我们正是要利用兑换第i个物品时j=j-need[i]时的值,所以我们从左往右填(从前往后填),这样后面就能利用前面已经修改过的值了。大家可以自己画个表格填一下就知道了,同时请参考联系我之前关于0-1背包的博客。
本代码提交AC,用时148MS,内存0MB。

POJ 2586-Y2K Accounting Bug

POJ 2586-Y2K Accounting Bug
Y2K Accounting Bug
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 10647 Accepted: 5328
Description
Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc.
All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite.
Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post.
Input
Input is a sequence of lines, each containing two positive integers s and d.
Output
For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible.
Sample Input
59 237
375 743
200000 849694
2500000 8000000
Sample Output
116
28
300612
Deficit
Source
Waterloo local 2000.01.29


这个题首先要读懂题意,其中的

ACM knows that each of these 8 postings reported a deficit

我一开始看不懂,不知道这个8代表什么意思,是怎么来的,看过别人的解释才知道,原来前面说每连续5个月会发布一次盈亏报告,而一年又12个月,总共可以发布8次,即:1-5,2-6,3-7,4-8,5-9,6-10,7-11,8-12。注意每次报告的月份和前后的报告的月份是有重叠的。
题目告诉我们这8次报告都是亏损,但是求这一年是否可以盈利,总的盈利最多是多少。这道题有点最优化的感觉,已知约束是8次报告都是亏损,求最优化总的盈利。
这道题可以有两种解法。
贪心
因为要求盈利最大化,所以可以先设12个月都是盈利的,然后再慢慢调整满足8次报告都是亏损的。一次报告是连续的5个月的总和,要保证一次报告是亏损,5个月里至少一个月是亏损的,亏损的月份放在5个月里的最后月份是最好的,因为这样可以和下一个报告重叠,使总的盈利最大。比如1-5使第5月份亏损,就能保证这个报告亏损,则2-6已经包含5月份了,当然这个报告肯定也亏损。这样1-5和2-6实际只有5月份是亏损的。但是如果1-5使第1月份亏损,虽然第一个报告是亏损的,但是2-6还是盈利的,又使第2月份亏损,则1-5和2-6实际有1月份和2月份是亏损的,这就亏损了两个月。
所以每次我们要亏损时,都从该报告的最后月份开始试探,一直往前试探,直到这个报告亏损。一直循环8个报告。最后求这一年总的盈亏。代码如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
     int s,d;
     while(cin>>s>>d)
     {
          int surplus_num;//盈余的月份数
          vector<int> month(12,1);//初始的时候每个月都是surplus,1为surplus,0为deficit
          for(int i=0;i<8;i++)//8个‘连续5个月’
          {
               surplus_num=0;
               for(int j=0;j<5;j++)
                    surplus_num+=month[i+j];
               int k=0;
               while(surplus_num*s>=(5-surplus_num)*d)
               {
                    month[i+4-k]=0;//亏损的月份尽量放到后面,因为可以和下一个周期重叠,这样总的surplus会大一些
                    surplus_num=0;
                    for(int j=0;j<5;j++)
                         surplus_num+=month[i+j];
                    k++;
               }
          }
          surplus_num=0;
          for(int i=0;i<12;i++)
               surplus_num+=month[i];
          int rs=surplus_num*s-(12-surplus_num)*d;//这一年总的盈亏
          if(rs<0)
               cout<<"Deficit"<<endl;
          else
               cout<<rs<<endl;
     }
     return 0;
}

这个版本提交AC,用时32MS,内存216K。
枚举
因为这题只有12月份,每个报告只是连续5个月,要是每个报告都亏损,则可以在5个月里有1个月份亏损、2个月份亏损、3个月份亏损、4个月份亏损、5个月份亏损。前4种情况依次求解,直到既满足每个报告亏损,又使12个月总的是盈利。如果前4种都不行,那总的肯定是亏损。
这4种情况可以这样来表示,由于每5个月的报账都为亏损,所有连续的5个月里至少有1个月为亏损,则可能产生最优解的情况为如下4种

1 2 3 4 5 6 7 8 9 10 11 12
s s s s d s s s s d s s //每5个月里只有1个月亏损
s s s d d s s s d d s s //每5个月里只有2个月亏损
s s d d d s s d d d s s //每5个月里只有3个月亏损
s d d d d s d d d d s d //每5个月里只有4个月亏损

从上到下一次枚举四种情况,如果满足条件(每次报账都为亏损),则算出ans = (盈利的月数)*s - (亏损的月数)*d,若ans>0 则输出 否则输出Deficit;若上述4种情况都不满足,则直接输出Deficit.
代码如下:

#include<iostream>
using namespace std;
int main()
{
     int a,b;
     while(cin>>a>>b)
     {
          int ans = 0;
          if(4*a-b<0)
          {
               ans = 10*a-2*b;
          }
          else if(3*a-2*b<0)
          {
               ans = 8*a-4*b;
          }
          else if(2*a-3*b<0)
          {
               ans = 6*a-6*b;
          }
          else if(a-4*b<0)
          {
               ans = 3*a-9*b;
          }
          else
          {
               ans = -1;
          }
          if(ans>0)
               cout<<ans<<endl;
          else
               cout<<"Deficit"<<endl;
     }
     return 0;
}

这个版本提交AC,用时0MS,内存216K。
很显然,枚举速度更快,但是如果总共有1000个月份,每个报告20个月,共50个报告,或者数字更大时,枚举就很麻烦了,所以掌握第一种贪心的方法还是很有必要的。

POJ 1012-Joseph

POJ 1012-Joseph
Joseph
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 48397 Accepted: 18267
Description
The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.
Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.
Input
The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.
Output
The output file will consist of separate lines containing m corresponding to k in the input file.
Sample Input
3
4
Sample Output
5
30
Source
Central Europe 1995


这个题目挺有趣的。有k个好人和k个坏人,依次编号为1~k~2k,其中前k个为好人,后k个为坏人。然后从1开始循环报数,报到m的被杀掉,杀掉之后,从被杀掉的下一个人开始又从1开始循环报数。求最小的m使得在杀好人之前,所有的坏人都已经被杀掉了。
看到这个题很快能得出两个约束条件:
1. 因为坏人的编号大于k,所以m的取值肯定要大于k,要不然第一个杀的肯定是好人。
2. 对于某个m,最多只需要循环杀k个人,我们就能判断这个m是不是所求,杀人的过程中杀到某个人的编号小于等于k,则肯定杀到好人了,但此时还没有杀完所有坏人,所以这个m不是所求,跳出,m++;如果这k个人都成功杀完,则所有坏人都杀完,m是所求。
以上思路都很简单,但是有一个关键问题没有解决:已知第i次杀人的编号是a[i],那么杀完a[i]后,下一个杀的人的编号是多少呢?如果是环形不杀人,只是报数的话,易知是(a[i]+m-1)%n,但是杀完某个人后下一轮报数时这个人已经不在了,要跳过他,所以编号是(a[i]+m-1)%(n-i),这就是著名的Joseph环。
有了Joseph环这个结论就很好办了,加上之前的两点结论,我们可以很快的写出代码,如下:

#include <stdio.h>
int main()
{
     int people[28] = {0}, k, Joseph[14] = {0};//k最多是13,people所有人的编号,Joseph用于打表,不然超时
     while(scanf("%d", &k) != EOF && k != 0)
     {
          if (Joseph[k] != 0)//如果是之前求过的
          {
               printf("%d\n", Joseph[k]);//则直接输出
               continue;
          }
          int n = 2 * k;
          int m = k+1;//m从k+1开始测试
          people[0] = 0;//people[0] = 0表示编号从0开始
          for (int i = 1; i <= k; i++)//最多连续杀k个人
          {
               //每次枚举完毕将剩下的人按从0到n - i编号,只要好人没有杀掉,则前面k - 1个编号是不变的
               people[i] = (people[i - 1] + m - 1) % (n - i + 1);
               if (people[i] < k)//第k个人的编号为k - 1,所以这里是<而不是<=    //杀到好人了
               {
                    i = 0 ;//重新开始    //有点continue的意思
                    m++;  //测试下一个m
               }
          }
          Joseph[k] = m;
          printf("%d\n", m);
     }
     return 0;
}

以上代码参考这个博客,做了微小的调整。代码AC,用时250MS,内存136K。
其实在我不知道Joseph环公式的时候,我用双向链表(其实就是STL里的list)写了一个版本,这个版本很朴实,就是杀一个人之后,把这个节点去掉,然后再循环报数,这样就不需要琢磨下一个被杀的编号到底是多少啊,但是这个版本超时严重。我也把代码贴上来,以供参考。

#include<iostream>
#include<list>
#include<map>
using namespace std;
//测试m是否是所求
bool check_m(int k,int m)
{
     list<int> li;
     for(int i=1;i<=2*k;i++)
          li.push_back(i);//首先初始化链表,人的编号从1开始
     int pos=1,executed_num=0;//pos当前报数,executed_num被杀的人数
     list<int>::iterator it=li.begin(),tmp;
     while(executed_num<k)//最多杀k个人就可以判断m
     {
          if(pos==m)//如果报数到m了。
          {
               //cout<<*it<<endl;
               if(*it<=k)//但是编号小于等于k,则杀到好人了。
                    return false;
               tmp=it;
               tmp++;
               li.erase(it);//否则把这个坏人杀掉并去除这个节点
               it=tmp;
               pos=1;//重新从1开始报数
               executed_num++;
          }
          else//如果还没报到m,则一直报下去,这个地方可能会消耗比较多的时间
          {
               pos++;
               it++;
          }
          if(it==li.end())//如果到链表尾了,则循环到头
               it=li.begin();
     }
     return true;
}
int main()
{
     int k,m;
     map<int,int> mii; //用于打表
     while(cin>>k&&k)
     {
          if(mii.find(k)!=mii.end())//如果之前计算过这个k,则直接输出
          {
               cout<<mii[k]<<endl;
               continue;
          }
          for(m=k+1;;m++)
          {
               if(check_m(k,m))
               {
                    cout<<m<<endl;
                    mii[k]=m;
                    break;
               }
          }
     }
     return 0;
}

hihoCoder 1040-矩形判断

hihoCoder 1040-矩形判断
#1040 : 矩形判断
时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
给出平面上4条线段,判断这4条线段是否恰好围成一个面积大于0的矩形。
输入
输入第一行是一个整数T(1<=T<=100),代表测试数据的数量。
每组数据包含4行,每行包含4个整数x1, y1, x2, y2 (0 <= x1, y1, x2, y2 <= 100000);其中(x1, y1), (x2,y2)代表一条线段的两个端点。
输出
每组数据输出一行YES或者NO,表示输入的4条线段是否恰好围成矩形。
样例输入
3
0 0 0 1
1 0 1 1
0 1 1 1
1 0 0 0
0 1 2 3
1 0 3 2
3 2 2 3
1 0 0 1
0 1 1 0
1 0 2 0
2 0 1 1
1 1 0 1
样例输出
YES
YES
NO


这一题题意很简单,但是要写代码实现还是有很多细节需要考虑。
题目给出了4条线段的8个端点,问是否能由这4条线段构成一个面积大于0的矩形。脑海中立马浮现出一个矩形的形状。要构成一个矩形的首要条件是:
1. 有且只有4个互异的顶点
这个条件是显而易见的,如下图(1)给出的4条线段,虽然延长一下能组成矩形,但是很明显如果只由线段组成的话,不是一个矩形。

要判断给出的点是否只有4个点,第一反应是用set集合,只要把题目给出的8个点都加入到set中,判断集合大小是否是4就可以了。
首先给出点的定义:

//点结构体
typedef struct P
{
     int x,y;//两点坐标
     bool operator<(const P& p)const//如果要加入到set中,需要重载<
     {
          //return this->x<p.x&&this->y<p.y;//注意这样会导致(0,0)<(0,1)且(0,1)<(0,0)的情况
          return (this->x<p.x)||((this->x==p.x)&&(this->y<p.y));
     }
     bool operator==(const P&p)const//重载等于比较
     {
          return (this->x==p.x)&&(this->y==p.y);
     }
};

需要注意一点,因为需要把P加入到set中,而set是通过红黑树来排序的,所以需要重载小于<操作符。我最开始重载函数是这样写的

return this->x<p.x&&this->y<p.y;

但是这样会有问题,如果给出两个点(0,0)和(0,1),会得出(0,0)<(0,1)和(0,1)<(0,0)都不成立的结论,也就是说无法给(0,0)和(0,1)排序,也就无法插入到set中,所以需要修改成

return (this->x<p.x)||((this->x==p.x)&&(this->y<p.y));

这样就能判断(0,0)<(0,1)成立了。有关这个问题可以参考这个这个
经过以上的步骤,就把问题转换成已知4个点,问能否由这4个点构成一个矩形的问题了。
此时又可以得出以下两个结论
2. 矩形中某条边和另外3条边的关系是:和其中2条边垂直,和另外1条边平行
3. 且和它平行的那条边不能是重合的边
有的同学可能会说,像上图中的(2)和(3)也是边a和另外2条边垂直、1条边平行啊,但是他们都不是矩形,但是大家别忘了,当我们走到这一步的时候,已经经过了第1个条件的检验,也就是只有4个顶点,你看图(2)和(3)明显不止4个顶点啊。所以结论2成立。
又有同学说,为什么还要结论3呢?因为还可能出现如上图(4)的样子,虽然图中所有边都满足条件2:和2条边垂直、和1条边平行,但是这明显不是一个矩形。因为边a和b重合了。所以结论3还是有必要的。
有了以上3条结论,我们就可以判断给出的4条线段是否能组成一个矩形了。
编程中有一些数学知识需要掌握的是,已知两个线段的4个端点,怎样判断这两条线段的关系:平行?垂直?其他?
很自然想到用斜率,如果k1*k2==-1则垂直,如果k1==k2则平行,否则其他。但是会遇到线段和y轴平行的情况,此时斜率是不存在的,所以需要稍微变一下。
假设线段L1的两个端点分别为(x1,y1)和(x2,y2),线段L2的两个端点分别为(a1,b1)和(a2,b2),则k1*k2==-1可以转换为(y2-y1)*(b2-b1)==-(x2-x1)*(a2-a1)。类似的,k1==k2转换为(y2-y1)*(a2-a1)==(b2-b1)*(x2-x1)。这样就不用担心斜率不存在的问题。
经过以上详细的分析,我们可以写出如下代码:

#include<iostream>
#include<set>
#include <vector>
using namespace std;
//点结构体
typedef struct P
{
     int x,y;//两点坐标
     bool operator<(const P& p)const//如果要加入到set中,需要重载<
     {
          //return this->x<p.x&&this->y<p.y;//注意这样会导致(0,0)<(0,1)且(0,1)<(0,0)的情况
          return (this->x<p.x)||((this->x==p.x)&&(this->y<p.y));
     }
     bool operator==(const P&p)const//重载等于比较
     {
          return (this->x==p.x)&&(this->y==p.y);
     }
};
//线结构体
typedef struct L
{
     P p1,p2;//一条线由两点组成
};
//判断两条线的关系,1:垂直 0:平行 -1:其他
int check_two_line(L l1,L l2)
{
     int x1=l1.p1.x,y1=l1.p1.y,x2=l1.p2.x,y2=l1.p2.y;
     int a1=l2.p1.x,b1=l2.p1.y,a2=l2.p2.x,b2=l2.p2.y;
     if((y2-y1)*(b2-b1)==-(x2-x1)*(a2-a1))//斜率公式的变形
          return 1;
     else if((y2-y1)*(a2-a1)==(b2-b1)*(x2-x1))
          return 0;
     else
          return -1;
}
//判断是否是同一条直线
bool is_same_line(L l1,L l2)
{
     if(((l1.p1==l2.p1)&&(l1.p2==l2.p2))||((l1.p1==l2.p2)&&(l1.p2==l2.p1)))//如果线的两个端点都相同,则是同一条直线
          return true;
     else
          return false;
}
//判断能否组成一个矩形
bool is_rect(vector<L> lines)
{
     int vertical_num,parallel_num;
     for(int i=0;i<4;i++)//每条线都和剩余3条线判断关系
     {
          vertical_num=0;
          parallel_num=0;
          for(int j=0;j<4;j++)
          {
               if(j==i)//不和自己判断
                    continue;
               int rs=check_two_line(lines[i],lines[j]);
               if(rs==-1)
                    return false;
               else if(rs==1)
                    vertical_num++;
               else
               {
                    if(is_same_line(lines[i],lines[j]))//如果是平行线还要判断是否是相同的线
                         return false;
                    parallel_num++;
               }
          }
          if(!(vertical_num==2&&parallel_num==1))//只有当该线和其他2条线垂直,1条线平行时,才能组成矩形
               return false;
     }
     return true;
}
int main()
{
     int T;
     cin>>T;
     while(T--)
     {
          set<P> points;
          vector<L> lines;
          for(int i=0;i<4;i++)
          {
               P p1,p2;
               cin>>p1.x>>p1.y>>p2.x>>p2.y;
               points.insert(p1);
               points.insert(p2);
               L l;
               l.p1=p1;
               l.p2=p2;
               lines.push_back(l);
          }
          if(points.size()!=4)//能组成矩形的必要条件是有且只有4个点,所以用set来判断更方便
               cout<<"NO"<<endl;
          else
          {
               if(is_rect(lines))
                    cout<<"YES"<<endl;
               else
                    cout<<"NO"<<endl;
          }
     }
     return 0;
}

代码提交后AC,用时1MS,内存0MB,还不错。

hihoCoder 1038-01背包

hihoCoder 1038-01背包
#1038 : 01背包
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
且说上一周的故事里,小Hi和小Ho费劲心思终于拿到了茫茫多的奖券!而现在,终于到了小Ho领取奖励的时刻了!
小Ho现在手上有M张奖券,而奖品区有N件奖品,分别标号为1到N,其中第i件奖品需要need(i)张奖券进行兑换,同时也只能兑换一次,为了使得辛苦得到的奖券不白白浪费,小Ho给每件奖品都评了分,其中第i件奖品的评分值为value(i),表示他对这件奖品的喜好值。现在他想知道,凭借他手上的这些奖券,可以换到哪些奖品,使得这些奖品的喜好值之和能够最大。
提示一:合理抽象问题、定义状态是动态规划最关键的一步
提示二:说过了减少时间消耗,我们再来看看如何减少空间消耗
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第一行为两个正整数N和M,表示奖品的个数,以及小Ho手中的奖券数。
接下来的n行描述每一行描述一个奖品,其中第i行为两个整数need(i)和value(i),意义如前文所述。
测试数据保证
对于100%的数据,N的值不超过500,M的值不超过10^5
对于100%的数据,need(i)不超过2*10^5, value(i)不超过10^3
输出
对于每组测试数据,输出一个整数Ans,表示小Ho可以获得的总喜好值。
样例输入
5 1000
144 990
487 436
210 673
567 58
1056 897
样例输出
2099


很简单的0-1背包问题。重新复习一下算法课本P140就好。注意填表的时候,从右往左填,这样只需要一行的空间。如果从左往右填只用一行空间的话,新的数据会覆盖老的数据,但是后面填表的过程中要用到老的数据,所以不行。代码如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
     int n,m;
     cin>>n>>m;
     vector<int> need_vi(n);//所需奖券
     vector<int> value_vi(n);//评分值
     for(int i=0;i<n;i++)
          cin>>need_vi[i]>>value_vi[i];
     vector<int> V(m+1,0);//V[j]表示有j张奖券,装前i个奖品获得的最大评分
     for(int i=0;i<n;i++)//V[j]表示有j张奖券,装前i个奖品获得的最大评分
     {
          for(int j=m;j>=need_vi[i];j--)//从后往前填表,能减少空间
          {
               V[j]=(V[j-need_vi[i]]+value_vi[i]>V[j])?(V[j-need_vi[i]]+value_vi[i]):V[j];//要这件奖品和不要的对比
          }
     }
     cout<<V[m];
     return 0;
}

代码提交AC,用时148MS,内存0MB。

POJ 1011-Sticks

POJ 1011-Sticks
Sticks
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 121990 Accepted: 28247
Description
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output should contains the smallest possible length of original sticks, one per line.
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
Sample Output
6
5
Source
Central Europe 1995


这个题是个深度搜索的好题目,题目的大意为:将一摞长度相同的棍子随机砍成不同长度的小棍子,问原始棍子的长度是多少。
设要求的原始棍子长度为original_len,砍乱之后,所有小棍子的长度总和为sum,因为原来都是整数根相同长度的棍子,所以sum一定是original_len的整数倍;而且因为棍子是随机砍乱的,所以original_len一定不小于砍乱的小棍子中的最大值。由此可以得出original_len的一个取值范围。然后再利用深度搜索求解。
在做算法题时,搜索题算比较难的了,由于我之前这方面的题练的也比较少,所以dfs的思路不太清晰,后来参考了这篇博文,里面关于剪枝的说明也挺详细的,我理解了他的代码,然后自己重新写了一遍,并在某些细节有所改动。代码如下:

#include <iostream>
#include<algorithm>
using namespace std;
int total_sticks,n,original_len;//分别表示没截断之前有几根棍子,总的截断的数量,没截断之前每根棍子的长度
int sticks[65];//截断之后每部分的长度
int mark[65];//指示每一段是否搜索过了
void init_mark()
{
     for(int i=0;i<65;i++)
          mark[i]=0;
}
bool cmp(int a,int b)
{
     return a>b;
}
//深度搜索,参数分别表示已经拼接好了几根棍子,当前正在拼接的棍子已经拼了多长了,当前测试的下标
bool dfs(int done_sticks,int done_parts,int pos)
{
     if(done_sticks==total_sticks)//如果所有棍子都拼好了,成功
          return true;
     for(int i=pos+1;i<n;i++)//从pos+1开始测试
     {
          if(mark[i]==1)//如果这根小棍子已经拼过了,则开始下一个
               continue;
          if(done_parts+sticks[i]==original_len)//刚好拼成了一个原始的棍子
          {
               mark[i]=1;//标记
               if(dfs(done_sticks+1,0,-1))//继续深度搜索,注意pos=-1,因为之前搜索的时候有些前面的小棍子可能没用上
                    return true;
               mark[i]=0;//如果搜索失败,回溯
               return false;
          }
          else if(done_parts+sticks[i]<original_len)
          {
               mark[i]=1;
               if(dfs(done_sticks,done_parts+sticks[i],i))//继续深度搜索,这时pos=i,因为继续往下搜的过程中,只能越取越小,因为这个时候还没有拼成一个完整的棍子,且之前已经搜过大的了
                    return true;
               mark[i]=0;//如果搜索失败,回溯
               if(done_parts==0)//如果这根小棍子是某次拼接时的第一个棍子,则失败
                    return false;
               while(sticks[i]==sticks[i+1])//否则找下一个小棍子时,跳过数值相同的小棍子,因为肯定失败
                    i++;
          }
     }
     return false;
}
int main()
{
     while(cin>>n&&n)
     {
          int sum=0;
          for(int i=0;i<n;i++)
          {
               cin>>sticks[i];
               sum+=sticks[i];//求和
          }
          sort(sticks,sticks+n,cmp);//按降序排序
          for(original_len=sticks[0];original_len<=sum;original_len++)
          {
               if(sum%original_len==0)//总和肯定能被原始棍子的长度整除
               {
                    total_sticks=sum/original_len;
                    init_mark();//每次都要初始化
                    if(dfs(0,0,-1))//dfs初始值
                    {
                         cout<<original_len<<endl;
                         break;
                    }
               }
          }
     }
     return 0;
}

代码都已经做了详细的注释,应该不难看懂,唯一和参考博客不同的地方是进行dfs时初始值的不同,我的是0,0,-1,不知道为什么原博客是1,0,-1,按理说最开始还没有组成一个完整的棍子啊,为什么done_sticks=1呢?
我的代码提交AC,用时16MS,内存220K。