Cool J has recently become a businessman Mr. Jackson, and he has to make a lot of phone calls now. Today he has n calls planned. For each call we know the moment ti (in seconds since the start of the day) when it is scheduled to start and its duration di (in seconds). All ti are different. Mr. Jackson is a very important person, so he never dials anybody himself, all calls will be incoming.
Mr. Jackson isn't Caesar and he can't do several things at once. If somebody calls him while he hasn't finished the previous conversation, Mr. Jackson puts the new call on hold in the queue. In this case immediately after the end of the current call Mr. Jackson takes the earliest incoming call from the queue and starts the conversation. If Mr. Jackson started the call at the second t, and the call continues for d seconds, then Mr. Jackson is busy at seconds t, t + 1, ..., t + d - 1, and he can start a new call at second t + d. Note that if Mr. Jackson is not busy talking when somebody calls, he can't put this call on hold.
Mr. Jackson isn't Napoleon either, he likes to sleep. So sometimes he allows himself the luxury of ignoring a call, as if it never was scheduled. He can ignore at most k calls. Note that a call which comes while he is busy talking can be ignored as well.
What is the maximum number of seconds Mr. Jackson can sleep today, assuming that he can choose an arbitrary continuous time segment from the current day (that is, with seconds from the 1-st to the 86400-th, inclusive) when he is not busy talking?
Note that some calls can be continued or postponed to the next day or even later. However, the interval for sleep should be completely within the current day.
Output
Print a number from 0 to 86400, inclusive — the maximally possible number of seconds for Mr. Jackson to sleep today.
Note
In the first sample the most convenient way is to ignore the first two calls.
In the second sample it is best to ignore the third call. In this case Mr. Jackson will have been speaking:
- first call: from 1-st to 20000-th second,
- second call: from 20001-st to 30000-th second,
- fourth call: from 30001-st to 40000-th second (the third call is ignored),
- fifth call: from 80000-th to 139999-th second.
Thus, the longest period of free time is from the 40001-th to the 79999-th second.
DP；；；
#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
int dp[4005][4005];
struct node
{
int s,d;
};
node a[4005];
int main()
{
int i,j,n,k,ans;
while(scanf("%d%d",&n,&k)!=EOF)
{
for(i=0;i<n;++i)
{
scanf("%d%d",&a[i].s,&a[i].d);
}
ans=0;
for(i=0;i<=n;++i)
{
for(j=0;j<=k;++j)
{
dp[i][j]=86401;
}
}
dp[0][0]=1;
for(i=0;i<n;++i)
{
for(j=0;j<=k;++j)
{
if(j!=k)
dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);
if(dp[i][j]<a[i].s)
{
ans=max(ans,a[i].s-dp[i][j]);
dp[i+1][j]=min(dp[i+1][j],a[i].s+a[i].d);
}
else
{
dp[i+1][j]=min(dp[i+1][j],dp[i][j]+a[i].d);
}
}
}
for(j=0;j<=k;++j)
{
ans=max(ans,86401-dp[n][j]);
}
printf("%d\n",ans);
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2012/03/05/2380629.html
The Berland University is preparing to celebrate the 256-th anniversary of its founding! A specially appointed Vice Rector for the celebration prepares to decorate the campus. In the center of the campus n ice sculptures were erected. The sculptures are arranged in a circle at equal distances from each other, so they form a regular n-gon. They are numbered in clockwise order with numbers from 1 to n.
The site of the University has already conducted a voting that estimated each sculpture's characteristic of ti — the degree of the sculpture's attractiveness. The values of ti can be positive, negative or zero.
When the university rector came to evaluate the work, he said that this might be not the perfect arrangement. He suggested to melt some of the sculptures so that:
- the remaining sculptures form a regular polygon (the number of vertices should be between 3 and n),
- the sum of the ti values of the remaining sculptures is maximized.
Help the Vice Rector to analyze the criticism — find the maximum value of ti sum which can be obtained in this way. It is allowed not to melt any sculptures at all. The sculptures can not be moved.
Output
Print the required maximum sum of the sculptures' attractiveness.
Note
In the first sample it is best to leave every second sculpture, that is, leave sculptures with attractivenesses: 2, 4, 5 и 3.
暴力求解的。。。
就是等间隔取数，求其和最大值！！！
#include<stdio.h>
int aa[20110];
int main()
{
int n;
int res;
int sum;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&aa[i]);
res=-200000000;
for(int i=1;i<=n/3;i++)
{
if(n%i!=0)continue;
if(n/i<3)continue;
for(int j=1;j<=i;j++)
{
sum=0;
for(int k=j;k<=n;k+=i)
sum+=aa[k];
if(sum>res) res=sum;
}
}
printf("%d\n",res);
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2012/03/05/2380627.html
After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of si friends (1 ≤ si ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?
Output
Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.
Note
In the first test we can sort the children into four cars like this:
- the third group (consisting of four children),
- the fourth group (consisting of three children),
- the fifth group (consisting of three children),
- the first and the second group (consisting of one and two children, correspondingly).
There are other ways to sort the groups into four cars.
水题，4个人的单独。
3和1搭配，
2和2搭配。
3有多的话只能单独了。
2可以加入1个的
#include<stdio.h>
int aa[5];
int main()
{
int n;
int t;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<5;i++)aa[i]=0;
while(n--)
{
scanf("%d",&t);
aa[t]++;
}
int res=0;
res+=aa[4];
if(aa[1]==aa[3])
{
res+=aa[1];
aa[1]=0;
aa[3]=0;
if(aa[2]%2==0)
{
res+=aa[2]/2;
}
else
{
res=res+aa[2]/2+1;
}
}
else if(aa[1]<aa[3])
{
res+=aa[1];
aa[3]-=aa[1];
aa[1]=0;
res+=aa[3];
if(aa[2]%2==0)
{
res+=aa[2]/2;
}
else
{
res=res+aa[2]/2+1;
}
}
else
{
res+=aa[3];
aa[1]-=aa[3];
aa[3]=0;
if(aa[2]%2==0)
{
res+=aa[2]/2;
}
else
{
res=res+aa[2]/2+1;
aa[1]-=2;
}
if(aa[1]>=1)
{
if(aa[1]%4==0) res+=aa[1]/4;
else
res=res+aa[1]/4+1;
}
}
printf("%d\n",res);
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2012/03/05/2380624.html
"Contestant who earns a score equal to or greater than the k-th place finisher's score will advance to the next round, as long as the contestant earns a positive score..." — an excerpt from contest rules.
A total of n participants took part in the contest (n ≥ k), and you already know their scores. Calculate how many participants will advance to the next round.
Output
Output the number of participants who advance to the next round.
Note
In the first example the participant on the 5th place earned 7 points. As the participant on the 6th place also earned 7 points, there are 6 advancers.
In the second example nobody got a positive score.
很简单的题目~~~~~
#include<stdio.h>
int mm[120];
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&mm[i]);
int res=k;
if(mm[k]>0)
{
for(int i=k+1;i<=n;i++)
{
if(mm[i]<mm[k])break;
res++;
}
}
else
{
res--;
for(int i=k-1;i>=1;i--)
{
if(mm[i]>0) break;
res--;
}
}
printf("%d\n",res);
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2012/03/05/2380621.html
Problem E
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
Aunt Lizzie takes half a pill of a certain medicine every day. She starts with a bottle that contains N pills.
On the first day, she removes a random pill, breaks it in two halves, takes one half and puts the other half back into the bottle.
On subsequent days, she removes a random piece (which can be either a whole pill or half a pill) from the bottle. If it is half a pill, she takes it. If it is a whole pill, she takes one half and puts the other half back into the bottle.
In how many ways can she empty the bottle? We represent the sequence of pills removed from the bottle in the course of 2N days as a string, where the i-th character is W if a whole pill was chosen on the i-th day, and H if a half pill was chosen (0 <= i < 2N). How many different valid strings are there that empty the bottle?
Input
The input will contain data for at most 1000 problem instances. For each problem instance there will be one line of input: a positive integer N <= 30, the number of pills initially in the bottle. End of input will be indicated by 0.
Output
For each problem instance, the output will be a single number, displayed at the beginning of a new line. It will be the number of different ways the bottle can be emptied.
Sample Input
Sample Output
132 1 14 2 5 3814986502092304
相当于求N个W，和N个H的排列数，而且要求前面任意个中必需H的个数不大于W的个数~~~~
不知道哪些大神是怎么样做出来的，好快的速度就做出来了~~~~
我想了好久都没有想到DP的方法，
最后想出来了，感觉方法比较笨~~~~
转化成了图，W表示往下走，H表是往右走，
则必须在左下角中。
N个W和H的时候就是到N-1行的路径数
如N=1时，为dp[0,0]
N=2时为dp[1,0]+dp[1,1]
N=3时为dp[2,0]+dp[2,1]+dp[2,2]
应该会有更好的方法的~~~~~
我的思路有点蹉了~~~~但幸好做出来了！
代码如下：
#include<stdio.h>
long long dp[31][31];
void init()
{
dp[0][0]=1;
for(int i=1;i<31;i++)
{
dp[i][0]=1;
for(int j=1;j<i;j++)
dp[i][j]=dp[i-1][j]+dp[i][j-1];
dp[i][i]=dp[i][i-1];
}
}
int main()
{
int N;
init();
while(scanf("%d",&N),N)
{
printf("%I64d\n",dp[N][N]);
}
return 0;
}
要求的其实就是从（0，0）到(N,N)的路径数，只能往下或者往右走，而且不能走到右上部分去。 文章来源: http://www.cnblogs.com/kuangbin/archive/2012/03/03/2378248.html
Problem A
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
You are given a list of N non-negative integers a(1), a(2), ... , a(N). You replace the given list by a new list: the k-th entry of the new list is the absolute value of a(k) - a(k+1), wrapping around at the end of the list (the k-th entry of the new list is the absolute value of a(N) - a(1)). How many iterations of this replacement are needed to arrive at a list in which every entry is the same integer?
For example, let N = 4 and start with the list (0 2 5 11). The successive iterations are:
2 3 6 11
1 3 5 9
2 2 4 8
0 2 4 6
2 2 2 6
0 0 4 4
0 4 0 4
4 4 4 4
Thus, 8 iterations are needed in this example.
Input
The input will contain data for a number of test cases. For each case, there will be two lines of input. The first line will contain the integer N (2 <= N <= 20), the number of entries in the list. The second line will contain the list of integers, separated by one blank space. End of input will be indicated by N = 0.
Output
For each case, there will be one line of output, specifying the case number and the number of iterations, in the format shown in the sample output. If the list does not attain the desired form after 1000 iterations, print 'not attained'.
Sample Input
4 0 2 5 11 5 0 2 5 11 3 4 300 8600 9000 4000 16 12 20 3 7 8 10 44 50 12 200 300 7 8 10 44 50 3 1 1 1 4 0 4 0 4 0
Sample Output
Case 1: 8 iterations Case 2: not attained Case 3: 3 iterations Case 4: 50 iterations Case 5: 0 iterations Case 6: 1 iterations
水题~~~~~
迭代就可以了！
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int a[50];
int main()
{
int N,res,j;
int iCase=0;
while(scanf("%d",&N),N)
{
iCase++;
for(int i=0;i<N;i++)
{
scanf("%d",&a[i]);
}
for(j=0;j<N-1;j++)
{
if(a[j]!=a[j+1])break;
}
if(j>=N-1)
{
printf("Case %d: 0 iterations\n",iCase);
continue;
}
for(res=1;res<=1000;res++)
{
a[N]=a[0];
for(int i=0;i<N;i++)
{
a[i]=abs(a[i]-a[i+1]);
}
for(j=0;j<N-1;j++)
{
if(a[j]!=a[j+1])break;
}
if(j>=N-1)break;
}
if(res<=1000)printf("Case %d: %d iterations\n",iCase,res);
else printf("Case %d: not attained\n",iCase);
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2012/03/03/2378235.html
| 店长推荐Ⅱ |
| Time Limit: 1000 MS |
Memory Limit: 65536 K |
| Total Submit: 97(31 users) |
Total Accepted: 28(24 users) |
Special Judge: No |
|
| Description |
|
想必大家已经领略了店长的调皮,自从店长知道了vagaa之后就一直沉迷期中不能自拔,教主看到后很是伤心，玩物丧志啊!于是教主教店长了一个vagaa的新用法,资源搜索功能。输入一些关键词后可以搜索出相关共享的好资源，店长得知后又是欣喜若狂。同时,教主又发明一个游戏，是上次的升级版,这次给出一些由字母和数字的玩具的同时，关键字不再是vagaa了，需要自己给出.看最后能组成多少个关键字。
|
| Input |
|
每行输入一个字符串由小写字母和数字组成，每个字符代表一个玩具, 紧接着输入一个关键字，同样由字母和数字组组成，字符串长度0<n<=10000，关键字长度0<m<=200
处理到文件结束
|
| Output |
|
输出能够组成关键字的数量
按照样例输出格式输出并换行.
|
| Sample Input |
|
vagaadsfaagav ga
asgvasdfzxcades dea
|
| Sample Output |
|
Case 1: 2
Case 2: 1
|
| Author |
| void |
#include<stdio.h>
#include<string.h>
int tt[40],count[40];
char str[10010];
int main()
{
int len,m;
int iCase=0;
while(scanf("%s",&str)!=EOF)
{
iCase++;
len=strlen(str);
memset(tt,0,sizeof(tt));
memset(count,0,sizeof(count));
for(int i=0;i<len;i++)
{
if(str[i]>='0'&&str[i]<='9')
{
m=str[i]-'0'+0;
tt[m]++;
}
else
{
m=str[i]-'a'+10;
tt[m]++;
}
}
scanf("%s",&str);
len=strlen(str);
for(int i=0;i<len;i++)
{
if(str[i]>='0'&&str[i]<='9')
{
m=str[i]-'0'+0;
count[m]++;
}
else
{
m=str[i]-'a'+10;
count[m]++;
}
}
int res=10000;
for(int i=0;i<=9+26;i++)
{
if(count[i]>0)
{
int tmp=tt[i]/count[i];
if(tmp<res) res=tmp;
}
}
printf("Case %d: %d\n",iCase,res);
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2012/02/27/2370325.html
| 青蛙过河 |
| Time Limit: 1000 MS |
Memory Limit: 65535 K |
| Total Submit: 29(11 users) |
Total Accepted: 9(9 users) |
Special Judge: No |
|
| Description |
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是s到t之间的任意正整数（包括s,t）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围s,t，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 |
| Input |
有多组测试数据。
对于每组测试数据，第一行四个正整数L, s, t, n（1 <= L <= 10^5, 1 <= s <= t <= 10，1 <= n <= 100），分别表示独木桥的长度，青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数。第二行有n个不同的正整数分别表示这n个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。 |
| Output |
| 每组测试数据仅输出一行，包括一个整数，表示青蛙过河最少需要踩到的石子数。 |
| Sample Input |
10 2 3 5
2 3 5 6 7 |
| Sample Output |
|
2
#include<stdio.h>
#include<string.h>
const int MAXN=100020;
int flag[MAXN];
int dp[MAXN];
int main()
{
int L,s,t,n;
int a;
while(scanf("%d%d%d%d",&L,&s,&t,&n)!=EOF)
{
memset(flag,0,sizeof(flag));
memset(dp,-1,sizeof(dp));//初始化，-1为不能到达的
//dp[i]表示到底 i 点需要经过的最少石子数，-1表示不能到达
for(int i=0;i<n;i++)
{
scanf("%d",&a);
flag[a]=1;//有石子为1，否则为0
}
dp[0]=0;
for(int i=s;i<=L+t-1;i++)
{
for(int j=i-t;j<=i-s;j++)// j 点跳到 i 点
{
if(j>=0&&dp[j]!=-1)//j 点能够跳到
{
if(dp[i]==-1)dp[i]=dp[j]+flag[i]; //第一次 直 接 给 值
else if(dp[i]>dp[j]+flag[i]) dp[i]=dp[j]+flag[i];//找小的值
}
}
}
int res=10000;
for(int i=L;i<=L+t-1;i++)//L 到 L+t-1 中最小的非 -1 值
{
if(dp[i]!=-1&&dp[i]<res) res=dp[i];
}
printf("%d\n",res);
}
return 0;
}
|
文章来源: http://www.cnblogs.com/kuangbin/archive/2012/02/27/2369901.html
2011已经逝去，2012已经到来~~~~
2011年，总感觉自己得到了很多，也失去了很多，也留下不尽的遗憾。仍记得2011年到来的时候，我自己对自己说这一年将会是我关键的一年，给自己定下了很多目标~~~~这些目标只能说是大致实现了吧，也很多遗憾！
为了迎接2012年，总感觉自己应该写点东西，来总结自己的2011，规划下2012.但是一直抽不出时间来写。等有时间了再写一篇来总结2011吧！
人生应该处于不断的奋斗当中！2012年，我要取得成功！2012年，我一定会做得更好！
加油！
————————————————————————————————————by kuangbin 文章来源: http://www.cnblogs.com/kuangbin/archive/2012/01/03/2310575.html
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1006
这题做了好久了，学习了网上的解法后自己写出来了。
就是枚举12*60分钟，看一分钟内有多少秒是happytime，一分钟内解三个不等式得到区间。
具体看代码。
代码有注释很详细的。
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct qujian
{
double l,r;
};
double D;
qujian solve(double a,double b)//解方程 D<=a*x+b<=360-D ,并且和 [0,60] 取交集
{
qujian p;
if(a>0)
{
p.l=(D-b)/a;
p.r=(360-D-b)/a;
}
else
{
p.l=(360-D-b)/a;
p.r=(D-b)/a;
}
if(p.l<0)p.l=0;
if(p.r>60)p.r=60;
if(p.l>=p.r) p.l=p.r=0;
return p;
}
qujian jiao(qujian a,qujian b)
{
qujian p;
p.l=max(a.l,b.l);
p.r=min(a.r,b.r);
if(p.l>=p.r) p.l=p.r=0;
return p;
}
/*
hh=30*h+m/2+s/120;
mm=6*m+s/10;
ss=6*s;
D<=|hh-mm|<=360-D;
D<=|hh-ss|<=360-D;
D<=|mm-ss|<=360-D;
hh-mm=
*/
double happytime(int h,int m)//计算 h 时，m 分 满足题意的秒数
{
double a,b;
qujian s[3][2];
qujian s1;
//解方程 D<=|hh-mm|<=360-D
//hh=30*h+m/2+s/120;
//mm=6*m+s/10;
a=1.0/120-0.1;
b=30*h+m/2.0-6*m;
s[0][0]=solve(a,b);
s[0][1]=solve(-a,-b);
//解方程 D<=|hh-ss|<=360-D
//hh=30*h+m/2+s/120;
//ss=6*s;
a=1.0/120-6.0;
b=30*h+m/2.0;
s[1][0]=solve(a,b);
s[1][1]=solve(-a,-b);
//解方程 D<=|mm-ss|<=360-D
//mm=6*m+s/10;
//ss=6*s;
a=0.1-6;
b=6*m;
s[2][0]=solve(a,b);
s[2][1]=solve(-a,-b);
double res=0;
//六个区间，选三个取交集。
//因为绝对值的式子得到的两个区间要并，而三个不同表达式的区间要交，故这样做。
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
{
s1=jiao(jiao(s[0][i],s[1][j]),s[2][k]);
res+=s1.r-s1.l;
}
return res;
}
int main()
{
while(scanf("%lf",&D))
{
if(D==-1) break;
double res=0;
int h,m;
for(h=0;h<12;h++)
{
for(m=0;m<60;m++)
{
res+=happytime(h,m);
}
}
printf("%.3lf\n",res*100.0/(60*60*12));
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2011/12/04/2275470.html
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 27 | 28 | 29 | 30 | 31 | 1 | 2 | | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | 10 | 11 | 12 | 13 | 14 | 15 | 16 | | 17 | 18 | 19 | 20 | 21 | 22 | 23 | | 24 | 25 | 26 | 27 | 28 | 29 | 30 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
公告
导航
统计
- 随笔： 100
- 文章： 0
- 评论： 2
- 引用： 0
常用链接
留言簿
随笔分类
随笔档案
博客
搜索
最新评论
阅读排行榜
评论排行榜
|
|