| Solved | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|
| 7/9 | O | O | O | O | O | O | Ø | . | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
问一个字符串是不是$2050$拼成的。
解题思路
签到题，暴力求解。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
char a[10000010];
int main(){
int i,t;
scanf("%d",&t);
while(t--){
scanf("%s",a);
int flag=0;
for(i=0;a[i];i+=4){
if(a[i]=='2'&&a[i+1]=='0'&&a[i+2]=='5'&&a[i+3]=='0');
else {
flag=1;
break;
}
}
if(flag)printf("No\n");
else printf("Yes\n");
}
return 0;
}
B
题目描述
给一个年月日时分秒，求这个时间点和$2050$年$1$月$1$日$0$时$0$分$0$秒差多少秒，答案对$100$取模。
解题思路
刚开始一边写判断闰年一边暗骂出题者毒瘤，写到一半突然发现答案竟然是对$100$取模？？
（脏话）
直接计算这是该天的第几秒，判断一下这个时间在给定日期之前还是之后即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
int main(){
int t,y,m,d,h,min,s;
scanf("%d",&t);
while(t--){
int ans=0;
scanf("%d-%d-%d",&y,&m,&d);
scanf("%d:%d:%d",&h,&min,&s);
ans=h*3600+min*60+s;
if(y<2050)ans=86400-ans;
printf("%d\n",ans%100);
}
return 0;
}
C
题目描述
有一堆人，$n+k$个男生，$m+k$个女生，其中$k$对情侣。有双人间$a$、三人间$b$、情侣间$c$，其中情侣间只能住情侣，双人三人间只能住同性且可以不住满。三种房间分别有不同价格，求把他们安排下住宿的最小花费。
解题思路
刚开始想的是取情侣全住$c$和全不住$c$的最小值，然后兴高采烈交了个$WA$。
后来才发现，情侣可以部分住$c$，枚举即可。
$f$表示的是$x$个人分配到$a$或$b$间的最小花费，分三种情况（除三的余数）讨论即可。
然后递推就可以了。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef long long ll;
int t,n,m,k;
ll a,b,c;
ll min(ll a,ll b){return a>b?b:a;}
ll f(int x){
ll ans=0;
if(x<3)return min(a,b);
if(x%3==1)ans=min((x/3+1)*b,(x/3-1)*b+2*a);
else if(x%3==2)ans=min((x/3+1)*b,x/3*b+a);
else ans=x/3*b;
return min((x/2+(x%2!=0))*a,ans);
}
int main(){
scanf("%d",&t);
int i;
while(t--){
scanf("%d%d%d%lld%lld%lld",&n,&m,&k,&a,&b,&c);
ll ans=f(n+k)+f(m+k);
for(i=0;i<k;i++)ans=min(ans,f(n+i)+f(m+i)+(k-i)*c);
printf("%lld\n",ans);
}
return 0;
}
D
题目描述
给一个计分规则，求最终奖品个数。
给定一个$01$串，求每一个前缀包含的所有本质不同的字母串个数。
解题思路
纯模拟，没啥好说的。
显然需要离线处理枚举前缀的结尾。
第一思路是，从前缀的结尾$i$往前递推，$num$记录最多能向后延伸几位，$dp[j]$表示$j$之后的字母串种类个数。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int a[10010],num[10010];
int peo[10010];
int main(){
int i;
int t,n,m,k;
scanf("%d",&t);
while(t--){
memset(num,0,sizeof(num));
memset(peo,0,sizeof(peo));
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
num[a[i]]++;
}
for(i=0;i<=m;i++)peo[i]=num[i]-num[i]/k;
int ans=0;
for(i=0;i<n/2;i++)if(num[a[i]]>peo[a[i]])num[a[i]]--,ans++;
printf("%d\n",ans);
}
return 0;
}
E
题目描述
两个人打乒乓球。给一个球赛的计分榜，其中有$A$得分、$B$得分、未知得分三种情况，问最多进行了多少场比赛。
解题思路
这题的$DP$挺麻烦的。
可以设一个$f[i][j][k]$表示在第$k$个计分之后，$A$和$B$比分为$i:j$的时候，最多可能的比赛轮数，其中$-1$表示不可能到达这种局面。其中，$10:10$之后某方得分可以化为$10:9$，特判即可。
AC代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
using namespace std;
int f[12][12][10010];
char a[10010];
int main(){
int i,j,k,t;
scanf("%d",&t);
while(t--){
scanf("%s",a+1);
int l=strlen(a+1);
memset(f,-1,sizeof(f));
f[0][0][0]=0;
for(i=1;a[i];i++){
if(a[i]=='A'){
for(j=1;j<=10;j++)
for(k=0;k<=10;k++)
if(~f[j-1][k][i-1])f[j][k][i]=f[j-1][k][i-1];
for(j=0;j<10;j++)
if(~f[10][j][i-1])f[0][0][i]=max(f[0][0][i],f[10][j][i-1]+1);
f[10][9][i]=max(f[10][10][i-1],f[10][9][i]);
}else if(a[i]=='B'){
for(j=0;j<=10;j++)
for(k=1;k<=10;k++)
if(~f[j][k-1][i-1])f[j][k][i]=f[j][k-1][i-1];
for(j=0;j<10;j++)
if(~f[j][10][i-1])f[0][0][i]=max(f[0][0][i],f[j][10][i-1]+1);
f[9][10][i]=max(f[10][10][i-1],f[9][10][i]);
}else{
for(j=0;j<=10;j++)
for(k=0;k<=10;k++){
if(j&&~f[j-1][k][i-1])f[j][k][i]=f[j-1][k][i-1];
if(k&&~f[j][k-1][i-1])f[j][k][i]=f[j][k-1][i-1];
}
for(j=0;j<10;j++){
if(~f[j][10][i-1])
f[0][0][i]=max(f[0][0][i],f[j][10][i-1]+1);
if(~f[10][j][i-1])
f[0][0][i]=max(f[0][0][i],f[10][j][i-1]+1);
}
f[9][10][i]=max(f[10][10][i-1],f[9][10][i]);
f[10][9][i]=max(f[10][10][i-1],f[10][9][i]);
}
/*printf("%d %c\n",i,a[i]);
for(j=0;j<12;j++){
for(k=0;k<12;k++)printf("%d ",f[j][k][i]);
puts("");
}
puts("");*/
}
int ans=0;
for(i=0;i<=10;i++)for(j=0;j<=10;j++)
ans=max(ans,f[i][j][l]);
printf("%d\n",ans);
}
return 0;
}
F
题目描述
现在，我们要依次面对$n$个冰水挑战，每个挑战你都可以选择接受或不接受。接受第$i$个挑战会让你丧失$a_i$点体力，因为每个挑战所处的环境不同，如果你要挑战它，在挑战它之前你的体力$x$会变成 $min(x,b_i)$，当你完成这个挑战的时候，你的体力会变成$x−a_i$，体力任何时候不允许小于等于$0$，无论你是否接受第$i$个挑战，在这个挑战结束以后你的体力都会增加$c_i$。
解题思路
$f[i][j]$表示进行到第$i$个挑战，已经完成了$j$ 个挑战之后，最大的体力值。然后$dp$即可。
AC代码
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
using namespace std;
int t,n;
long long p,a[1010],b[1010],c[1010];
long long f[1010][1010];
int main(){
int i,j;
scanf("%d",&t);
while(t--){
memset(f,0,sizeof(f));
scanf("%d%lld",&n,&p);
for(i=1;i<=n;i++)scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
f[0][0]=p;
for(i=1;i<=n;i++){
for(j=0;j<=i;j++){
if(f[i-1][j])f[i][j]=f[i-1][j]+c[i];
if(j&&min(f[i-1][j-1],b[i])-a[i]>0)
f[i][j]=max(f[i][j],min(f[i-1][j-1],b[i])-a[i]+c[i]);
}
}
int ans=0;
for(i=1;i<=n;i++)if(f[n][i])ans=i;
printf("%d\n",ans);
}
return 0;
}
G
题目描述
我们看到了一栋高楼大厦，大厦的墙面可以看做一个$W×H$的矩形，我们把它的左下角当成$(0,0)$，右上角当成$(W,H)$。上面分布着一些$LED$灯，这些$LED$灯与地面呈$45$度倾斜，并且从矩形的边界延伸到另一边界，把大厦分成了若干个区域。我们想数一下这个图里面存在多少个与地面成$45$度角的矩形，其中四条边都是$LED$灯的一部分。
解题思路
比赛并没有过这个题，但是想到了一种扫描线算法，出奇的麻烦，结果听学长说用$bitset$简单可过……
AC代码
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
31
32
33
34
using namespace std;
int w,h,n,m,a[N],b[N];
long long W=1000000007;
bitset<N> B[N];
void solve(){
long long ans=0;
scanf("%d%d%d%d",&w,&h,&n,&m);
int i,j;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
for(j=0;j<N;j++)B[i][j]=0;
}
for(i=1;i<=m;i++){
scanf("%d",&b[i]);
for(j=1;j<=n;j++)if(a[j]+b[i]>=0&&a[j]+b[i]<=2*w&&a[j]>=b[i]&&a[j]-b[i]<=2*h)B[j][i]=1;
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++){
long long sum=(B[i]&B[j]).count();
(ans+=sum*(sum-1)/2)%=W;
}
printf("%lld\n",ans);
}
int main(){
int T;
scanf("%d",&T);
while(T--)solve();
return 0;
}
后面的题还没看……