| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 7/10 | 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
题目描述
垃圾分类。
解题思路
签到题，模拟即可。
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;
using namespace std;
char a[2010],b[30];
int main(){
int i,j,n;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%s%s",a,b);
printf("Case #%d: ",i);
int l=strlen(a),h=0,d=0,w=0;
for(j=0;j<l;j++){
if(b[a[j]-'a']=='h')h++;
else if(b[a[j]-'a']=='w')w++;
else d++;
}
if(4*h>=l)printf("Harmful");
else if(10*h<=l)printf("Recyclable");
else if(d>=2*w)printf("Dry");
else printf("Wet");
puts("");
}
return 0;
}
B
题目描述
给一个长度为$128$的$01$串，按照规定缩小串长度并输出。
解题思路
模拟，注意处理各个位置缩小的幅度。
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
typedef long long ll;
using namespace std;
char a[200];
int num[200],hexa[200],ipv[200];
void print(int x){
int i,tmp=x;
while(!hexa[x]&&x<tmp+4)x++;
if(x==tmp+4)printf("0");
for(i=x;i<tmp+4;i++){
printf("%x",hexa[i]);
}
}
int main(){
int i,T,Cas=0;
scanf("%d",&T);
while(T--){
scanf("%s",a);
printf("Case #%d: ",++Cas);
for(i=0;a[i];i++)num[i]=a[i]-'0';
for(i=0;i<32;i++){
int j=i*4;
hexa[i]=num[j]*8+num[j+1]*4+num[j+2]*2+num[j+3];
}
for(i=0;i<8;i++){
int j=i*4;
ipv[i]=(hexa[j]||hexa[j+1]||hexa[j+2]||hexa[j+3]);
}
int zero=0,mx=0,temp=0;
for(i=0;i<8;i++){
if(ipv[i]==0){
zero++;
if(zero>mx||(zero==mx&&(i!=7||temp-zero<0))){
mx=zero;
temp=i;
}
}else zero=0;
}
zero=mx;
if(zero<2){
print(0);
for(i=1;i<8;i++)printf(":"),print(i*4);
}else{
if(temp-zero>=0)print(0);
for(i=1;i<=temp-zero;i++)printf(":"),print(i*4);
printf("::");
if(temp+1<8)print((temp+1)*4);
for(i=temp+2;i<8;i++)printf(":"),print(i*4);
}
puts("");
}
return 0;
}
C
题目描述
给一个串$s$，其所有连续子回文串构成集合$S$。问从$S$中能取多少对$(a,b)$，$a$是$b$的真子串。
解题思路
建立一棵回文树，每一个节点当做$b$串时，对答案的贡献为所有它的回文子串。注意到回文树$fail$指针的作用是其最长回文后缀，对答案产生的贡献即为其回文树上的前驱节点的贡献集合与沿$fail$指针不停向上跳路上经过的节点集合的并集。这里考虑用$dfs$计算贡献，$vis$数组记录所有前驱走过的$fail$边上的点的集合去重即可。
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
typedef long long ll;
using namespace std;
ll ans;
struct PT{
int tr[N][P],fail[N],len[N];
int tot,s[N],n,last,i;
int newnode(int l){
for(i=0;i<P;i++)tr[tot][i]=0;
len[tot]=l;
return tot++;
}
void init(){
n=last=tot=0;
newnode(0);newnode(-1);
s[0]=-1;
fail[0]=1;
}
int getfail(int p){
while(s[n-len[p]-1]!=s[n])p=fail[p];
return p;
}
void add(int p){
s[++n]=p;
int cur=getfail(last);
if(!tr[cur][p]){
int now=newnode(len[cur]+2);
int getf=getfail(fail[cur]);
fail[now]=tr[getf][p];
tr[cur][p]=now;
}
last=tr[cur][p];
}
void insert(char a[]){
int i;
for(i=0;a[i];i++)add(a[i]-'a');
}
}p;
char a[N];
queue<int>Q;
int vis[N];
void dfs(int x,int num){
int i,t=x;
int sta[10]={0},top=0;
while(t&&!vis[t]){
vis[t]=1;
sta[++top]=t;
num++;
t=p.fail[t];
}
if(x>=2)ans+=num-1;
for(i=0;i<P;i++)if(p.tr[x][i])dfs(p.tr[x][i],num);
while(top)vis[sta[top--]]=0;
}
ll solve(){
ans=0;
memset(vis,0,sizeof(vis));
vis[0]=vis[1]=1;
dfs(0,0);dfs(1,0);
return ans;
}
int main(){
int T,Cas=0;
scanf("%d",&T);
while(T--){
scanf("%s",a);
p.init();
p.insert(a);
printf("Case #%d: %lld\n",++Cas,solve());
}
return 0;
}
D
题目描述
有$n$个物品，$k$个箱子，每个物品有其重量，按照每次向箱子里放最大可以放的物品的规则，问箱子最小要多大才能够保证所有物品能够放入。
解题思路
开始以为是个二分答案，然后全场都在$WA$，莫名其妙，看来二分是假了。
然后每次二分枚举一下下界调调参就过了
虚假的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
typedef long long ll;
using namespace std;
int n,k,a[1010],vis[1010];
int check(int x){
int i,tot=0;
memset(vis,0,sizeof(vis));
for(i=0;i<k;i++){
int rest=x;
while(1){
int index=upper_bound(a+1,a+n+1,rest)-a-1;
while(index&&vis[index])index--;
if(!index)break;
rest-=a[index];
vis[index]=1;
tot++;
}
}
return tot==n;
}
int main(){
int i,t,Cas=0;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
a[n+1]=1e9;
sort(a+1,a+n+1);
int l=0,r=1000000,ans=1000000;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;
else{
int flag=0;
for(i=mid-1;i>=mid-40&&i>0;i--)if(check(i)){
ans=i;
r=i-1;
flag=1;
}
if(!flag)l=mid+1;
}
}
printf("Case #%d: %d\n",++Cas,ans);
}
return 0;
}
正解：答案没有单调性，上界下界之差的复杂度可以保证，于是从下界暴力枚举即可。
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
typedef long long ll;
using namespace std;
int n,k,a[1010],vis[1010];
int check(int x){
int i,tot=0;
memset(vis,0,sizeof(vis));
for(i=0;i<k;i++){
int rest=x;
while(1){
int index=upper_bound(a+1,a+n+1,rest)-a-1;
while(index&&vis[index])index--;
if(!index)break;
rest-=a[index];
vis[index]=1;
tot++;
}
}
return tot==n;
}
int main(){
int i,t,Cas=0;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
int s=0;
for(i=1;i<=n;i++)scanf("%d",&a[i]),s+=a[i];
sort(a+1,a+n+1);
for(i=max(s/k,a[n]);;i++)if(check(i))break;
printf("Case #%d: %d\n",++Cas,i);
}
return 0;
}
E
题目描述
求构造一个补图和原图同构的图。
解题思路
玄学构造，待补。
AC代码
2
F
题目描述
解题思路
AC代码
2
G
题目描述
给一堆字母表示的日期，按字典序求出字母代表的数字使得日期合法且均为星期五。
解题思路
暴力枚举剪枝，去个重即可$AC$。
蔡勒公式看来需要收藏一下。
$random_shuffle$一下直接从$4000ms$跑到$3400ms$，牛
WA代码
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
typedef long long ll;
using namespace std;
struct Str{
char a[20];
bool operator<(const Str s)const{
return strcmp(a,s.a)<0;
}
bool operator==(const Str s)const{
return strcmp(a,s.a)==0;
}
}a[N];
int n,y[N][10],m[N][10],d[N][10];
int vis[15];
int ans[15];
int day[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int run(int Y){
if(Y%400==0)return 1;
if(Y%100==0)return 0;
if(Y%4==0)return 1;
return 0;
}
int friday(int y,int m,int d){
if(m<3)m+=12,y--;
int c=y/100;y%=100;
return (c/4-2*c+y+y/4+13*(m+1)/5+d-1-5)%7==0;
}
int check(int Y,int M,int D){
if(run(Y))day[2]=29;
else day[2]=28;
if(Y>=1600&&Y<=9999&&M>=1&&M<=12&&D<=day[M]&&D>=1);
else return 0;
if(friday(Y,M,D))return 1;
return 0;
}
int dfs(int x){
int i,j;
for(i=0;i<n;i++){
int Y=ans[y[i][0]]*1000+ans[y[i][1]]*100+ans[y[i][2]]*10+ans[y[i][3]];
int M=ans[m[i][0]]*10+ans[m[i][1]];
int D=ans[d[i][0]]*10+ans[d[i][1]];
if(ans[m[i][0]]>1||M>12)return 0;
if(ans[d[i][0]]>3)return 0;
if(ans[y[i][0]]!=-1&&ans[y[i][1]]!=-1&&ans[y[i][0]]*10+ans[y[i][1]]<16)return 0;
if(ans[d[i][0]]==-1||ans[d[i][1]]==-1)continue;
if(ans[m[i][0]]==-1||ans[m[i][1]]==-1)continue;
if(ans[y[i][0]]==-1||ans[y[i][1]]==-1||ans[y[i][2]]==-1||ans[y[i][3]]==-1)continue;
if(!check(Y,M,D))return 0;
}
if(x==10){
for(i=0;i<10;i++){
if(ans[i]==-1){
for(j=0;j<10;j++){
if(!vis[j]){
vis[j]=1;
ans[i]=j;
break;
}
}
}
printf("%d",ans[i]);
}
return 1;
}
for(i=0;i<10;i++){
if(!vis[i]){
vis[i]=1;
ans[x]=i;
if(dfs(x+1))return 1;
vis[i]=0;
ans[x]=-1;
}
}
return 0;
}
int main(){
int i,j,T,Cas=0;
scanf("%d",&T);
while(T--){
memset(vis,0,sizeof(vis));
memset(ans,-1,sizeof(ans));
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%s",a[i].a);
sort(a,a+n);
n=unique(a,a+n)-a;
for(i=0;i<n;i++){
for(j=0;j<4;j++)y[i][j]=a[i].a[j]-'A';
for(j=5;j<7;j++)m[i][j-5]=a[i].a[j]-'A';
for(j=8;j<10;j++)d[i][j-8]=a[i].a[j]-'A';
}
printf("Case #%d: ",++Cas);
if(!dfs(0))printf("Impossible");
puts("");
}
return 0;
}
H
题目描述
解题思路
AC代码
2
I
题目描述
解题思路
AC代码
2
J
题目描述
有$n$个科技，$m$个等级，第$i$个科技升级到$j$的花费是$c_{ij}$，所有科技都升级到$i$的花费是$d_i$，求最大化收益。
解题思路
枚举所有科技共同升到多少级，其他科技处理成最小值，并记录位置，如果全都在枚举的等级之上，则强制删掉一个最大的（负值），更新答案即可。
AC代码
isha
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
typedef long long ll;
using namespace std;
int n;
ll d[N],a[N][N];
int mn[N][N];
int main(){
int i,j,n,m,T,Cas=0;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%lld",&a[i][j]);
a[i][j]+=a[i][j-1];
}
mn[i][m]=m;
for(j=m-1;j;j--){
if(a[i][j]<a[i][mn[i][j+1]])mn[i][j]=j;
else mn[i][j]=mn[i][j+1];
}
}
ll ans=0;
for(i=1;i<=m;i++)scanf("%lld",&d[i]),d[i]+=d[i-1];
printf("Case #%d: ",++Cas);
for(j=0;j<=m;j++){
ll sum=d[j],mx=0;
int rightend=1e9;
for(i=1;i<=n;i++)sum-=a[i][j];
for(i=1;i<=n;i++){
ll pay=a[i][mn[i][j]]-a[i][j];
sum-=pay;
mx=max(mx,pay);
rightend=min(rightend,mn[i][j]);
}
if(rightend!=j)sum+=mx;
ans=max(ans,sum);
}
printf("%lld\n",ans);
}
return 0;
}