xtuoj-0x06

个人图片

Index

A

模拟题，具体看怎么实现删除

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
#include<stdio.h>
#include<string.h>

char ball[31];

void delete(char *ball,int index){
    int left=index,right=index;
    int len=strlen(ball);
    while(left>0&&ball[left-1]==ball[index]) left--;
    while(right<len-1&&ball[index]==ball[right+1]) right++;
    if(right-left+1>=3){
        for(int i=left;i<=right;i++) ball[i]='0';
    }
}

void update(char *ball){
    char temp[31];
    int len=strlen(ball),index=0;
    for(int i=0;i<len;i++){
        if(ball[i]!='0') temp[index++]=ball[i];
    }
    temp[index]='\0';
    strcpy(ball,temp);
}

void swap(char *a,char *b){
    char temp=*a;
    *a=*b;
    *b=temp;
}
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--){
        scanf("%s%d",ball,&n);
        while(n--){
            scanf("%d",&m);
            swap(&ball[m],&ball[m-1]);
            delete(ball,m-1);
            delete(ball,m);
            update(ball);
            if(strlen(ball)==0) printf("Over\n");
            else printf("%s\n",ball);
        }
        puts("");
    }
    return 0;
}

B

这是错误代码，原因在于字符串处理无法处理n>9的情况，一开始没想到，直到疯狂RE时，写对拍才发现，但是思路是没问题的，重新写一遍就过了

false code 
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
#include<stdio.h>
#include<string.h>

char num[1010]; 
int time[1010];

void gen_time(int n){
    for(int i=2;i<n;i++){
        time[i]=(time[i-1]+time[i-2])%n+1;
    }
    for(int i=0;i<n-1;i++){
        time[i]--;
    }
}

void Delete(char *num,int start){
    int len=strlen(num);
    memmove(&num[start],&num[start+1],len-start);
    num[len-1]='\0';
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,index=0;
        scanf("%d%d%d",&n,&time[0],&time[1]);
        for(int i=0;i<n;i++) num[i]=('0'+i+1);
        num[n]='\0';
        gen_time(n);
        for(int i=0;i<n-1;i++){
            int len=strlen(num);
            index=(index+time[i])%len;
            Delete(num,index);
        }
        printf("%s\n",num);
    }
    return 0;
}

AC Code:

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
#include<stdio.h>
#include<string.h>

int num[1010]; 
int time[1010];

void gen_time(int n){
    for(int i=2;i<n;i++){
        time[i]=(time[i-1]+time[i-2])%n+1;
    }
    for(int i=0;i<n-1;i++){
        time[i]--;
    }
}

void Remove(int *num,int start,int len){
    for(int i=start;i<len;i++){
        num[i]=num[i+1];
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,index=0;
        scanf("%d%d%d",&n,&time[0],&time[1]);
        for(int i=0;i<n;i++) num[i]=i+1;
        gen_time(n);
        int len=n;
        for(int i=0;i<n-1;i++){
            index=(index+time[i])%len;
            Remove(num,index,len);
            len--;
        }//32~33 核心代码
        for(int i=0;i<len;i++){
            if(num[i]) printf("%d",num[i]);
        }
        puts("");
    }
    return 0;
}

C

  • 数码串
    又RE了，数组越界，我还开了两倍长的数据，没想到三倍长的数据长度都不够，应该估计一下最差情况可能需求的数组长度的
    以后RE先检查数组，QAQ
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
#include<stdio.h>
#include<string.h>

char num[400000];/* 用足够大的空间来换取模拟循环队列 */

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s",num);
        int len=strlen(num);
        for(int i=0;i<len-1;i++){
            if(num[i]>num[i+1]){
                num[len++]=(num[i]+1)>'9'?'9':(num[i]+1);
                num[i]='a';
            }
        }
        for(int i=0;i<len;i++){
            if(num[i]!='a') printf("%c",num[i]);
        }
        puts("");
    }
    return 0;
}

D

这玩意就是个关系矩阵的幂，模拟关系的复合运算就行了，估计以后不会遇到这样的题了

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
#include<stdio.h>
#include<string.h>

int matrix[101][101];
int effect[101];
int temp[101][101];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        memset(matrix,0,sizeof(matrix));
        for(int i=0;i<n;i++) scanf("%d",&effect[i]);
        for(int i=0;i<n;i++){
            int k=effect[i]-1;
            matrix[i][k]=1;
            if(k>0) matrix[i][k-1]=1;
        }/* 初始矩阵 */
        for(int layer=1;layer<m-1;layer++){
            memset(temp,0,sizeof(temp));
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(matrix[i][j]){
                        int k=effect[j]-1;
                        temp[i][k]=1;
                        if(k>0) temp[i][k-1]=1;/* 每次循环后的temp矩阵就是matrix相乘一次的矩阵 */
                    }
                }
            }
            memcpy(matrix,temp,sizeof(matrix));
        }
        for(int j=0;j<n;j++){
            for(int i=0;i<n;i++){
                printf("%d",matrix[i][j]);
            }
            puts("");
        }
        puts("");

    }
    return 0;
}

E

  • 最大可变字符串
    我觉得这个代码很巧妙，变量用的恰到好处，我自己思路不对，这是别人的代码
    我目前已知这个题有两种思路
    1.排序对比是否相同
    2.统计字符出现次数是否相同
    这是第一种，我觉得第二种的实现太过麻烦，就懒得去思考了
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
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char str[115][15];
char copy[115][15];
int cnt[115];

int cmp(const void *a,const void *b){
    return *(char *)a-*(char *)b;
}

void solve(){
    int n,k=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",str[i]);
        strcpy(copy[i],str[i]);
        qsort(copy[i],strlen(copy[i]),sizeof(char),cmp);
    }
    for(int i=1;i<n;i++){
        if(!cnt[i]){/* 只有没被标记的类别可以进入，这个思维有点像埃筛 */
            cnt[i]=1;
            for(int j=i+1;j<=n;j++){
                if(strcmp(copy[i],copy[j])==0){
                    cnt[i]++;
                    cnt[j]=-i;/* 归类，每个相同的字符串为一类 */
                }
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(cnt[i]>cnt[k]) k=i;/* 找出最大出现次数，同时找出类别 */
    }
    printf("%d\n",cnt[k]);
    printf("%s\n",str[k]);
    for(int i=1;i<=n;i++){
        if(cnt[i]==-k){
            printf("%s\n",str[i]);
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        memset(cnt,0,sizeof(cnt));
        solve();
        puts("");
    }
    return 0;
}

F

没什么好说的，剪枝优化，注意负数解就行了

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
#include<stdio.h>
#include<math.h>

typedef long long ll;

int check(int n){
    return sqrt(n)==(int)sqrt(n);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        ll n,m,flag=0;
        scanf("%lld%lld",&n,&m);
        ll edge=(ll)sqrt(m)+1;
        for(ll x=-edge;x<edge;x++){
            ll y=m-x*x;
            if(check(y)){
                y=(ll)sqrt(y);
                if(x*x*x+y*y*y==n){
                    printf("%lld %lld\n",x,y);
                    flag=1;
                    break;
                }else if(x*x*x-y*y*y==n){
                    printf("%lld %lld\n",x,-y);
                    flag=1;
                    break;
                }
            }
        }
        if(!flag) puts("0");
    }
    return 0;
}

G

  • 原根
    用同余的一个性质防止爆long long 和TLE，其他模拟就完了
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
#include<stdio.h>
#include<string.h>

int cnt[100010];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        memset(cnt,0,sizeof(cnt));
        int k=1,flag=1;
        for(int i=1;i<=n-1;i++){
            k*=2;
            k%=n;
            cnt[k]++;
            if(cnt[k]>1){
                printf("No\n");
                flag=0;
                break;
            }
        }
        if(flag) puts("Yes");
    }
    return 0;
}

H

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
70
71
72
73
74
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char str1[5];
char str2[5];

int cmp1(const void *a,const void *b){
    return *(char *)a-*(char *)b;
}

int cmp2(const void *a,const void *b){
    return *(char *)b-*(char *)a;
}

void up(char *str1){
    qsort(str1,strlen(str1),sizeof(char),cmp1);
}

void down(char *str2){
    qsort(str2,strlen(str2),sizeof(char),cmp2);
}

void swap(char *a,char *b){
    char temp=*a;
    *a=*b;
    *b=temp;
}

void plus(char *str1,char *str2){
    char temp[6]={0};
    for(int i=0;i<4;i++){
        if(str1[i]+str2[i]-2*'0'>9){
            temp[i]+=(str1[i]+str2[i]-2*'0')%10+'0';
            str1[i+1]++;
        }else{
            temp[i]=str1[i]+str2[i]-'0';
        }
        
    }
    swap(&temp[0],&temp[3]);
    swap(&temp[1],&temp[2]);
    strcpy(str1,temp);
}

int check(char * str1){
    for(int i=0;i<strlen(str1)-1;i++){
        if(str1[i]!=str1[i+1]) return 0;
    }
    return 1;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s",str1);
        int cnt=0;
        while(1){
            if(check(str1)){
                printf("%d\n",cnt);
                break;
            }else{
                strcpy(str2,str1);
                up(str1);
                down(str2);
                plus(str1,str2);
            }
            cnt++;
        }

    }
    return 0;
}

Code2:

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp1(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int cmp2(const void* a, const void* b) {
    return (*(int*)b - *(int*)a);
}

void getn(int n, int num[4]) {
    for (int i = 0; i < 4; i++) {
        num[3 - i] = n % 10;
        n /= 10;
    }
}

int trans(int num[4]) {
    return num[0] * 1000 + num[1] * 100 + num[2] * 10 + num[3];
}

int check(int *num) {
    return num[0] == num[1] && num[1] == num[2] && num[2] == num[3];
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        int cnt = 0;
        while (1) {
            int num[4];
            getn(n, num);
            if (check(num)) {
                printf("%d\n", cnt);
                break;
            }
            qsort(num, 4, sizeof(int), cmp1);
            qsort(num, 4, sizeof(int), cmp2);
            int a = trans(num);
            int b = trans(num);
            n = (a + b) % 10000;
            cnt++;
            getn(n, num);
            if (check(num)) {
                printf("%d\n", cnt);
                break;
            }
        }
    }
    return 0;
}
cs xtuoj
#oj #cs
xtuoj-0x06
http://example.com/2024/11/25/xtuoj-0x06/
Author
Anfsity
Posted on
November 25, 2024
Licensed under