P73
竞赛时间：????年??月??日??:??-??:??
|
题目名称 |
第二题 |
死亡 |
凝视 |
|
名称 |
two |
death |
eyesight |
|
输入 |
two.in |
death.in |
eyesight.in |
|
输出 |
two.out |
death.out |
eyesight.out |
|
每个测试点时限 |
1秒 |
1秒 |
1秒 |
|
内存限制 |
512MB |
512MB |
512MB |
|
测试点数目 |
10 |
10 |
10 |
|
每个测试点分值 |
10 |
10 |
10 |
|
是否有部分分 |
无 |
无 |
无 |
|
题目类型 |
传统 |
传统 |
传统 |
注意事项（请务必仔细阅读）：
第二题
【题目描述】
给你两个日期，问这两个日期差了多少毫秒。
【输入格式】
两行，每行一个日期，日期格式保证为“YYYY-MM-DD hh:mm:ss”这种形式。第二个日期时间一定比第一个日期时间要大两个日期的年份一定都是21世纪的年份。
【输出格式】
一行一个整数代表毫秒数。
【样例输入1】
2000-01-01 00:00:00
2000-01-01 00:00:01
【样例输出1】
1000
【样例输入2】
2000-01-01 00:00:00
2000-11-11 00:00:00
【样例输出2】
27216000000
【样例解释】
从前有座山。
【数据范围与规定】
对于的数据，两个日期相同。
对于的数据，两个日期只有秒数可能不同。
对于的数据，两个日期只有秒数、分钟数可能不同。
对于的数据，两个日期的年月日一定相同。
对于的数据，两个日期的年月一定相同。
对于的数据，两个日期的年份一定相同。
对于的数据，两个日期一定都是21世纪的某一天，且第二个日期一定大于等于第一个日期。
/* 60分少了个= */ #include<iostream> #include<cstdio> #include<cstring> #define LL long long using namespace std; LL n1,y1,r1,s1,f1,m1; LL n2,y2,r2,s2,f2,m2; LL ans; LL month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; LL init() { LL x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } LL judge(LL x) { if((x%4==0&&x%100!=0)||x%400==0) return 1; return 0; } void Deal() { if(m1==60)m1==0,f1++; if(f1==60)f1=0,s1++; if(s1==24)s1=0,r1++; if(judge(n1))month[2]=29; else month[2]=28; if(r1==month[y1]+1)r1=1,y1++; if(y1==13)y1=1,n1++; } int main() { //freopen("two.in","r",stdin); //freopen("two.out","w",stdout); n1=init(),y1=init(),r1=init(),s1=init(),f1=init(),m1=init(); n2=init(),y2=init(),r2=init(),s2=init(),f2=init(),m2=init(); if(m1!=m2) { if(m1<m2)ans+=m2-m1,m1=m2; else if(m1>m2)ans+60-m1+m2,m1=m2,f1++; Deal(); } if(f1!=f2) { if(f1<f2)ans+=(f2-f1)*60,f1=f2; else if(f1>f2)ans+=(60-f1+f2)*60,f1=f2,s1++; Deal(); } if(s1!=s2) { if(s1<s2)ans+=(s2-s1)*60*60,s1=s2; else if(s1>s2)ans+=(24-s1+s2)*60*60,s1=s2,r1++; Deal(); } while(r1!=r2||y1!=y2||n1!=n2) { r1++;Deal(); ans+=60*60*24; } cout<<ans*1000<<endl; return 0; }
/* 刚开始少打了个等号 60分 QAQ...... */ #include<iostream> #include<cstdio> #include<cstring> #define LL long long using namespace std; LL n1,y1,r1,s1,f1,m1; LL n2,y2,r2,s2,f2,m2; LL ans; LL month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; LL init() { LL x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } LL judge(LL x) { if((x%4==0&&x%100!=0)||x%400==0) return 1; return 0; } void Deal() { if(m1==60)m1=0,f1++; if(f1==60)f1=0,s1++; if(s1==24)s1=0,r1++; if(judge(n1))month[2]=29; else month[2]=28; if(r1==month[y1]+1)r1=1,y1++; if(y1==13)y1=1,n1++; } int main() { freopen("two.in","r",stdin); freopen("two.out","w",stdout); n1=init(),y1=init(),r1=init(),s1=init(),f1=init(),m1=init(); n2=init(),y2=init(),r2=init(),s2=init(),f2=init(),m2=init(); if(m1!=m2) { if(m1<m2)ans+=m2-m1,m1=m2; else if(m1>m2)ans+=60-m1+m2,m1=m2,f1++;//+=打成了+ Deal(); } if(f1!=f2) { if(f1<f2)ans+=(f2-f1)*60,f1=f2; else if(f1>f2)ans+=(60-f1+f2)*60,f1=f2,s1++; Deal(); } if(s1!=s2) { if(s1<s2)ans+=(s2-s1)*60*60,s1=s2; else if(s1>s2)ans+=(24-s1+s2)*60*60,s1=s2,r1++; Deal(); } while(r1!=r2||y1!=y2||n1!=n2) { r1++;Deal(); ans+=60*60*24; } cout<<ans*1000<<endl; return 0; }
死亡
【问题描述】
现在有个位置可以打sif，有个人在排队等着打sif。现在告诉你前个人每个人需要多长的时间打sif，问你第个人什么时候才能打sif。（前个人必须按照顺序来）
【输入格式】
第一行两个整数如上所述。
接下来行每行一个整数代表每个人所需要用的时间。
【输出格式】
一行一个整数表示答案。
【样例输入】
3 2
1
1
1
【样例输出】
1
【样例解释】
山里有座庙。
【数据规模与约定】
对于的数据，每个人所需用的时间不超过。
|
测试点 |
|
|
测试点 |
|
|
|
1 |
10 |
10 |
1 |
5000 |
500 |
|
2 |
20 |
10 |
2 |
100000 |
5000 |
|
3 |
50 |
10 |
3 |
100000 |
10000 |
|
4 |
1000 |
500 |
4 |
100000 |
20000 |
|
5 |
2000 |
500 |
5 |
100000 |
50000 |
/* 贪心 每个人都去时间最少的地方 */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #define LL long long #define maxn 100010 using namespace std; LL n,m; LL t[maxn]; struct node { LL t; bool operator < (node a)const { return t>a.t; } }; priority_queue<node>q; LL init() { LL x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int main() { freopen("death.in","r",stdin); freopen("death.out","w",stdout); n=init();m=init(); for(LL i=1;i<=n;i++) t[i]=init(); for(LL i=1;i<=m;i++) q.push((node){0}); for(LL i=1;i<=n;i++) { node now=q.top(); q.pop(); now.t+=t[i]; q.push(now); } node now=q.top(); cout<<now.t<<endl; return 0; }
凝视
【问题描述】
背包是个好东西，希望我也有。
给你一个二维的背包，它的体积是。现在你有一些大小为和的物品，每个物品有自己的价值。你希望往背包里面装一些物品，使得它们的价值和最大，问最大的价值和是多少。
【输入格式】
第一行一个整数代表该测试点的数据组数。
对于每组数据，第一行有四个整数，其中分别代表大小为和大小为的物品个数。
接下来一行有个数代表每个物品的价值。
接下来一行有个数代表每个物品的价值。
【输出格式】
对于每组询问，输出能够达到的价值最大值。
【样例输入】
1
2 3 2 2
1 2
1 2
【样例输出】
4
【样例解释】
庙里有座山。
【数据规模与约定】
对于的数据，。
对于的数据，。
对于的数据，。
/* 以为只能竖着放 打的dp */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 20010 #define maxx 510 using namespace std; int T,n,m,p,q; int w[maxn],v[maxn]; int f[maxx][maxx]; int init() { int x=0,f=1;char c=getchar(); while(c<'0'&&c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int main() { freopen("eyesight.in","r",stdin); freopen("eyesight.out","w",stdout); T=init(); while(T--) { n=init();m=init();p=init();q=init(); for(int i=1;i<=p;i++) { w[i]=2; v[i]=init(); } for(int i=p+1;i<=p+q;i++) { w[i]=3; v[i]=init(); } for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) f[i][j]=0; for(int i=1;i<=p+q;i++) { for(int j=n;j>=1;j--) { for(int k=m;k>=w[i];k--) { f[j][k]=max(f[j][k],f[j][k-w[i]]+v[i]); f[j][k]=max(f[j][k],f[j-1][m]+v[i]); } } } printf("%d ",f[n][m]); } return 0; }
正解
/* 这道题竟然不是dp 贪心... 对于一个n*m的网格 放1*2和1*3的块 若是枚举放多少1*2的和多少1*3的 比如放x个1*2的和y个1*3的 判断是否能放下 若能 肯定是取最大的那几个来填 有如下结论: 对于n*m的网格用足够1*3和1*2的块填能剩下1个或0个 只需要枚举1*3放少个就行只要数*3<=格子就能放下 (长或宽为2时除外单独讨论) */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define maxn 20010 using namespace std; LL T,n,m,p,q,ans,sum,tot; LL a[maxn],b[maxn]; LL s[maxn],t[maxn]; LL init() { LL x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } LL cmp(LL x,LL y) { return x>y; } LL min(LL x,LL y) { return x<=y?x:y; } int main() { freopen("eyesight.in","r",stdin); freopen("eyesight.out","w",stdout); T=init(); while(T--) { n=init();m=init();p=init();q=init(); for(LL i=1;i<=p;i++) a[i]=init(); for(LL i=1;i<=q;i++) b[i]=init(); sort(a+1,a+p+1,cmp); sort(b+1,b+q+1,cmp); for(LL i=1;i<=p;i++) s[i]=s[i-1]+a[i]; for(LL i=1;i<=q;i++) t[i]=t[i-1]+b[i]; if(n==2||m==2) { if(m==2)swap(n,m);ans=0; int l=m-m%3;l=l/3*2; for(LL i=0;i<=min(q,l);i++) { tot=n*m-i*3; ans=max(ans,t[i]+s[min(p,tot/2)]); } cout<<ans<<endl; continue; } ans=0; for(LL i=0;i<=q;i++) { if(n*m>=i*3) { tot=n*m-i*3; ans=max(ans,t[i]+s[min(p,tot/2)]); } else break; } cout<<ans<<endl; } return 0; }