http://2050.acmclub.cn/contests/contest_show.php?cid=3
开场白
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
我们想要用10个题目,大声喊出年青人的声音。我们希望和大家一起用技术创造一个更好的2050。
第一道题目,我们来玩一个数字游戏。
给出一个数字 n
,我们想知道 n
是不是若干个 2050 依次拼接起来的。
表示数据组数。
对于每组数据,一行一个正整数 n (1≤n≤10^100000)
。
是若干个 2050 依次拼接起来的,No 表示不是。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
char ch[];
int main(){
int t;
scanf("%d",&t);
char d[]="";
while(t--){
scanf("%s",ch);
int f=;
int len=strlen(ch);
if(len%)f=;
for(int i=;i<len;i++){
if(ch[i]!=d[i%]){
f=;
}
}
if(f)printf("Yes\n");
else printf("No\n");
}
return ;
}
时间间隔
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7501 Accepted Submission(s): 2735
给出一个时间S,我们想知道S距离2050年1月1日0点0时0分多少秒。
因为答案可能很大,请输出答案模100的值。
表示数据组数。
对于每组数据,一行一个字符串表示时间。
时间格式为:YYYY-MM-DD HH:MM:SS,分别表示年、月、日、时,分、秒。
输入的时间保证都在2019年1月1日以后(包含当天)。
2019-01-01 00:00:00
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
int month[][]={
{,,,,,,,,,,,,},
{,,,,,,,,,,,,}
};
char ch[],ch2[];
int main(){
int t;
scanf("%d",&t);
while(t--){
ll ans=;
//2019-01-01 00:00:00
scanf("%s%s",ch,ch2);
int len=strlen(ch);
int ye=,mon=,day=;
for(int i=;i<;i++){
ye*=;
ye+=ch[i]-'';
}
for(int i=;i<;i++){
mon*=;
mon+=ch[i]-'';
}
for(int i=;i<;i++){
day*=;
day+=ch[i]-'';
}
int len2=strlen(ch2);
int sum=;
for(int i=;i<;i++){
sum*=;
sum+=ch2[i]-'';
}
sum*=;
int sum2=;
for(int i=;i<;i++){
sum2*=;
sum2+=ch2[i]-'';
}
sum2*=;
int sum3=;
for(int i=;i<;i++){
sum3*=;
sum3+=ch2[i]-'';
}
sum3+=sum2+sum;
ans+=*-sum3;
day++;
if((ye%==&&ye%)||(ye%==)){
if(day>month[][mon]){
mon++;
day=;
}
if(mon==){
mon=;
ye++;
}
ll days=month[][mon]-day+;
for(int i=mon+;i<=;i++){
days+=month[][i];
}
days*=*;
ans+=days;
ans%=;
for(int i=ye+;i<;i++){
if((i%==&&i%)||i%==){
ans+=**;
}
else{
ans+=**;
}
ans%=;
}
}
else{
if(day>month[][mon]){
mon++;
day=;
}
if(mon==){
mon=;
ye++;
}
ll days=month[][mon]-day+;
for(int i=mon+;i<=;i++){
days+=month[][i];
}
days*=*;
ans+=days;
ans%=;
for(int i=ye+;i<;i++){
if((i%==&&i%)||i%==){
ans+=**;
}
else{
ans+=**;
}
ans%=;
}
}
printf("%lld\n",ans%);
}
return ;
}
分宿舍
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
那天我说我要来,于是你就来啦。
TA看到了什么?
你又看到了什么?
我看到你们在一起,我是真的很happy:)
太阳在哪里啊?
就在早上七八点。
太阳在哪里啊?
就在云的栖息地!”
——2050主题曲
2050的线下活动吸引了很多心怀梦想的年轻人。
小伙们打算组团去参加。他们一共有 n+m+2k
个人,包括 n+k
个男生,m+k
个女生,其中 k
对男女生为异性情侣,现在他们要找房间住。房间有三种类型,双人间 a
元一间,三人间 b
元一间,这两种只能同性一起住。情侣间能住一对异性情侣,一间 c
元。除了情侣间以外,其他房间都可以不住满。
求最少花多少钱,能让小伙伴们都有地方住。
表示数据组数。
接下来 T
组数据,每组数据一行 6
个整数 n,m,k,a,b,c
,其中 0≤n,m,k≤103,0≤a,b,c≤109
。
3 0 1 1 3 3
3 3 2 1 6 2
6
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll inf=1e15;
ll dp[];
int main(){
int t;
scanf("%d",&t);
while(t--){
ll n,m,k,a,b,c;
scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&k,&a,&b,&c);
int xx=max(n+k,m+k);
for(int i=;i<=xx;i++)dp[i]=inf;
//memset(dp,0x3f3f3f3f,sizeof(dp));
dp[]=;
for(int i=;i<=xx;i++){
if(i>=)dp[i]=min(dp[i],dp[i-]+a);
if(i>=)dp[i]=min(dp[i],dp[i-]+a);
if(i>=)dp[i]=min(dp[i],dp[i-]+b);
if(i>=)dp[i]=min(dp[i],dp[i-]+b);
if(i>=)dp[i]=min(dp[i],dp[i-]+b);
}
ll ans=inf;
//ans=min(ans,dp[m+k]+dp[n+k]);
//ans=min(ans,dp[n]+dp[m]+k*c);
//ans=min(ans,);
for(int i=;i<=k;i++){
ans=min(ans,dp[n+k-i]+dp[m+k-i]+i*c);
}
printf("%lld\n",ans);
}
return ;
}
PASS
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
个选手参加了 2050 编程竞赛,他们属于 m
个学校,学校的编号为 1
到 m
,2050 编程竞赛的 PASS 奖励资格如下:对于一个学校,如果它有 x
个学生参赛,它的参赛学生里成绩最好的 ⌊x/k⌋
人里,每有一个人总排名在前 50%
内(包括50%
),就奖励一个 PASS。
现在给出每个选手所属的学校和它的排名(假设没有平手),请你帮主办方算一下一共发出了几个 PASS。
表示数据组数。
接下来 T
组数据,对于每组数据:
第一行三个正整数 n,m,k (1≤n≤104,1≤m≤103,2≤k≤20)
。
第二行 n
个数,按照成绩从好到差给出 n
个选手所属的学校。
6 2 2
1 1 2 1 2 2
8 2 2
1 1 2 1 2 2 2 2
2
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
int a[],in[],b[];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m,k;
memset(in,,sizeof(in));
memset(b,,sizeof(b));
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
in[a[i]]++;
}
int ans=;
for(int i=;i<=n/;i++){
if(b[a[i]]<in[a[i]]/k){
//b[a[i]]++;
ans++;
}
b[a[i]]++;
}
printf("%d\n",ans);
}
return ;
}
冰水挑战
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
The stage could not be any cooler, and we mean literally:
a hole cut through the ice in the frozen Baltic Sea.
2050有一项很有挑战的活动 —— Polar Bear Pitching 。
体验人跳入冰水中讲述自己的恐惧,改变以及梦想。这是没有时间限制的演讲,就看你能在冰水中呆多久!
现在,我们要依次面对 n
个冰水挑战,每个挑战你都可以选择接受或不接受。接受第 i
个挑战会让你丧失 ai
点体力,因为每个挑战所处的环境不同,如果你要挑战它,在挑战它之前你的体力 x
会变成 min(x,bi)
,当你完成这个挑战的时候,你的体力会变成 x−ai
,体力任何时候不允许小于等于 0
,无论你是否接受第 i
个挑战,在这个挑战结束以后你的体力都会增加 ci
。
现在我们想知道最多可以完成多少个挑战。
表示数据组数。
接下来 T
组数据,每组第一行两个正整数 n,c (1≤n≤10^3,1≤c≤10^9)
,表示挑战的数量和初始体力,接下来 n
行,每行三个非负整数 ai,bi,ci(0≤ai,bi,ci≤109)
。
3 10
1 2 0
4 8 3
6 10 1
2 1
1 1 1
1 1 1
0
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll inf=1e15;
ll dp[][];
ll a[],b[],c[];
int main(){
int t;
scanf("%d",&t);
while(t--){
ll n,C;
scanf("%lld%lld",&n,&C);
for(int i=;i<=n;i++){
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
}
memset(dp,-,sizeof(dp));
dp[][]=C;
for(int i=;i<=n;i++){
for(int j=;j<=i;j++){
if(dp[i-][j]!=-)dp[i][j]=max(dp[i][j],dp[i-][j]+c[i]);
ll xx=-;
if(j)xx=min(dp[i-][j-],b[i]);
if(xx>a[i])dp[i][j]=max(dp[i][j],xx-a[i]+c[i]);
}
}
int ans=;
for(int i=n;i>=;i--){
if(dp[n][i]>){
ans=i;
break;
}
}
printf("%d\n",ans);
}
return ;
}