2012年3月5日
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
2012年3月3日
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
2012年2月27日
| 店長推薦Ⅱ |
| 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
2012年1月3日
2011已經逝去，2012已經到來~~~~
2011年，總感覺自己得到了很多，也失去了很多，也留下不盡的遺憾。仍記得2011年到來的時候，我自己對自己說這一年將會是我關鍵的一年，給自己定下了很多目標~~~~這些目標只能說是大致實現了吧，也很多遺憾！
為了迎接2012年，總感覺自己應該寫點東西，來總結自己的2011，規劃下2012.但是一直抽不出時間來寫。等有時間了再寫一篇來總結2011吧！
人生應該處于不斷的奮斗當中！2012年，我要取得成功！2012年，我一定會做得更好！
加油！
————————————————————————————————————by kuangbin 文章來源: http://www.cnblogs.com/kuangbin/archive/2012/01/03/2310575.html
2011年12月4日
題目鏈接：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
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 26 | 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 |
|
公告
導航
統計
- 隨筆： 100
- 文章： 0
- 評論： 2
- 引用： 0
常用鏈接
留言簿(2)
隨筆分類
隨筆檔案
博客
搜索
最新評論
閱讀排行榜
評論排行榜
|
|