头部背景图片
Alisa |
Alisa |

CCCC训练题

由于上一次写的寒假题解被自己rm掉了…因此决定开一个新坑

CCCC,全称xxxx天梯赛,IOI赛制

公费旅游机会++

CCCC据说是一个手速场,全称xxxx天梯赛

我这种CF A题写10min的是不是药丸?

题目均来自 : https://www.patest.cn/contests/gplt

然后是训练进度

已完成(7/懒得数)

最后完成了大概20多道,并不想写上来了,CCCC已经结束了(3.31

故事区

3.2
L1的题竟然做不出来

3.3
鉴于L1太简单去做L3,然后001的DP就不知道怎么记方案,002树状数组还写炸了,003莫名WA,我好菜啊.jpg

3.4
003WA竟然是因为…有句调试语句没删…竟然过了一组数据,垃圾CCCC

代码区

L1-001

1
2
3
4
5
#include<cstdio>

int main(){
printf("Hello World!");
}

L1-002

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
int num[50];
char s[5];
int main(){
int n;
scanf("%d",&n);
scanf("%s",s);
num[1]=1;
for(int i = 2;i<=30;i++) num[i]=num[i-1]+(i*2-1)*2;
//for(int i = 1;i<=30;i++) printf("%d ",num[i]);
int tmp=0;
for(int i = 1;i<=30;i++) if(n>=num[i]) tmp=i;
for(int i = tmp;i>=1;i--){
for(int j = 1;j<=(tmp-i);j++) printf(" ");
for(int j=1;j<=2*(i-1)+1;j++) printf("%c",s[0]);
printf("\n");
}
for(int i = 2;i<=tmp;i++){
for(int j = 1;j<=(tmp-i);j++) printf(" ");
for(int j=1;j<=2*(i-1)+1;j++) printf("%c",s[0]);
printf("\n");
}
printf("%d\n",n-num[tmp]);
}

L1-003

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
#include<cstring>
using namespace std;
int num[15];
char str[1005];

int main(){
scanf("%s",str);
int len=strlen(str);
for(int i = 0;i<len;i++) num[str[i]-'0']++;
for(int i = 0;i<=9;i++){
if(num[i]!=0){
printf("%d:%d\n",i,num[i]);
}
}
}

L1-004

1
2
3
4
5
6
7
#include<cstdio>

int main(){
int F;
scanf("%d",&F);
printf("Celsius = %d\n",5*(F-32)/9);
}

L1-005

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
char str[1010][20];
int n,m,num1[1010],num2[1010];
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%s%d%d",str[i],&num1[i],&num2[i]);
}
scanf("%d",&m);
for(int i = 1;i<=m;i++){
int x;
scanf("%d",&x);
for(int j = 1;j<=n;j++){
if(num1[j]==x){
printf("%s %d\n",str[j],num2[j]);
break;
}
}
}
}

L1-006

WA了4发,这种题不1A丢人

L3-002

题解:树状数组维护区间和,二分查找check答案

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
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
#include<cstdio>
const int N=1e5+7;
int c[N],stack[N];
int n;
int top;
int lowbit(int x){
return x&(-x);
}

int calc(int x){
int sum=0;
while(x){
sum+=c[x];
x-=lowbit(x);
}
return sum;
}


void updata(int x,int y){
while(x<=1e5){
c[x]+=y;
x+=lowbit(x);
}
}

void findMid(int x){
int L=1,R=1e5;
int ans=0;
while(L<R){
int mid=(L+R)>>1;
//printf("%d\n",mid);
//printf("%d\n",calc(mid));
if(calc(mid)>=x){
ans=mid;
R=mid;
}else L=mid+1;
}
printf("%d\n",ans);
}

int main(){
//int n;
char str[20];
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%s",str);
if(str[1]=='o'){
if(top==0){
printf("Invalid\n");
}else{
printf("%d\n",stack[top]);
updata(stack[top],-1);
top--;
}
}
if(str[1]=='e'){
if(top==0){
printf("Invalid\n");
}else findMid((top+1)/2);
}
if(str[1]=='u'){
int x;
scanf("%d",&x);
updata(x,1);
stack[++top]=x;
}
}
}

L3-003

随便建个图跑一跑,调试语句没注释WA了也是简直了,还有行末没空格mmp

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
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
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1005;
struct ee{
int to,next;
}e[N*N];
int num[N][N];
int pd[N],vis[N],head[N],sz[N];
int n,cnt;
void ins(int u,int v){
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}

bool cmp(int a,int b){
return a>b;
}

int dfs(int x){
//printf("%d\n",x);
int sum=1;
vis[x]=1;
for(int i = head[x];i;i=e[i].next){
int v=e[i].to;
if(!vis[v]) sum+=dfs(v);
}
return sum;
}

int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d:",&num[i][0]);
for(int j=1;j<= num[i][0];j++){
scanf("%d",&num[i][j]);
}
//sort(num[i]+1,num[i]+num[i][0]+1);
}
for(int i = 1;i<=n;i++){
memset(pd,0,sizeof(pd));
for(int j = 1;j<=num[i][0];j++){
pd[num[i][j]]=1;
}
for(int j = i+1;j<=n;j++){
for(int k =1;k<=num[j][0];k++){
if(pd[num[j][k]]){
//printf("%d %d\n",i,j);
ins(i,j);
ins(j,i);
break;
}
}
}
}

int ans=0;
for(int i = 1;i<=n;i++){
if(!vis[i]){
//printf("%d\n",i);
ans++;
sz[ans]=dfs(i);
}
}
printf("%d\n",ans);
sort(sz+1,sz+ans+1,cmp);
for(int i = 1;i<ans;i++) printf("%d ",sz[i]);
printf("%d",sz[ans]);
}