xtuoj-part1

  • 记载刷xtuoj遇到的一些题目

xtuoj-part1

maze

  • Maze
    模拟题，第一次写是照着别人的思路写的，这是第二次写的代码，老师说可以更改一下逻辑，直接检查，避免回溯，但是我懒的调了，就这样吧
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
43
44
45
46
47
48
49
50
51
52
53
#include<stdio.h>
#include<string.h>

char map[110][110]={};
int direct_x[4]={-1,0,1,0};
int direct_y[4]={0,1,0,-1};

void foundS(int *x,int *y,int n,int m){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(map[i][j]=='S'){
                *x=i;
                *y=j;
                return ;
            }
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,d,cnt=0,alert=0,flag=1;
        scanf("%d%d%d",&n,&m,&d);
        d--;
        getchar();
        for(int i=0;i<n;i++){
            fgets(map[i],sizeof(map[i]),stdin);//用scanf和fgets都可以，使用fgets时注意上次读入时的换行符
        }
        int x,y;
        foundS(&x,&y,n,m);
        while(map[x][y]!='E'){
            d=d%4;
            x+=direct_x[d];
            y+=direct_y[d];
            if(map[x][y]=='*'||x>n-1||y>m-1||x<0||y<0){
                x-=direct_x[d],y-=direct_y[d];
                d++,alert++;
                cnt--;
            }
            cnt++;
            if(cnt>n*m||alert>n*m*m){//防止死循环
                flag=0;
                puts("Impossible");
                break;
            }
        }
        if(flag) printf("%d\n",cnt);
        memset(map,' ',sizeof(map));
    }
    return 0;
}

最大的数

  • 最大的数
    完完全全的思维题
    我不是完全理解这个思路，也就是说，我不会证明这个为什么可行，只是觉得，啊啊，对啊，就是这样,很有道理
    ······
The Max Number 
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
#include<stdio.h>
#include<string.h>

#define N 10010

int num[N];
int odd[N];
int even[N];
int res[N];

int main()
{
    char a[N];
    while(scanf("%s",a)!=EOF){
        int len = strlen(a);
        for(int i = 0; i < len; i++) num[i] = a[i] - '0';
        int n = 0, m = 0;
        for(int i = 0; i < len; i++){
            if(num[i] % 2 == 1) odd[n++] = num[i];
            else even[m++] = num[i];
        }
        int i = 0, j = 0, k = 0;
        while(i < n && j < m){
            if(odd[i] < even[j]) res[k++] = even[j++];
            else res[k++] = odd[i++];
        }
        while(i<n) res[k++] = odd[i++];
        while(j<m) res[k++] = even[j++];
        for(int i = 0; i < len; i++) printf("%d",res[i]);
        printf("\n");
    }
    return 0;
}

刷油漆

题目大意 n,m,c,t表示行数，列数，颜色数，刷漆次数
谢大以前给研究生出的压轴题，还是具有一定的思维难度的
算法的核心在于构建O(T)的代码
突破点在于将操作顺序和读入顺序倒置
掌握了这点，剩下的就可以顺利突破了
上代码

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
43
44
45
46
47
#include <stdio.h>

int colorCount[1010];       // 记录每种颜色的格子数量
int rowPainted[10010];      // 记录某行是否已被刷过
int colPainted[10010];      // 记录某列是否已被刷过
int paintOps[3][100005];    // 记录所有刷漆操作

void solve() {
    int rows, cols, colors, operations;
    scanf("%d%d%d%d", &rows, &cols, &colors, &operations);
    
    // 读取每个操作
    for(int i = 1; i <= operations; i++) {
        scanf("%d%d%d", &paintOps[0][i], &paintOps[1][i], &paintOps[2][i]);
    }
    
    int paintedRows = 0, paintedCols = 0;  // 记录被刷过的行数和列数
    
    // 从后往前遍历所有操作，保证逆序优先级
    for(int i = operations; i >= 1; i--) {
        if(paintOps[0][i] == 0) {  // 如果是行操作
            if(!rowPainted[paintOps[1][i]]) {  // 如果该行未被刷过
                rowPainted[paintOps[1][i]] = 1;  // 标记该行被刷过
                colorCount[paintOps[2][i]] += cols - paintedCols;  // 该行颜色的格子数增加（总列数 - 被刷过的列数）
                paintedRows++;  // 被刷过的行数加1
            }
        } else {  // 如果是列操作
            if(!colPainted[paintOps[1][i]]) {  // 如果该列未被刷过
                colPainted[paintOps[1][i]] = 1;  // 标记该列被刷过
                colorCount[paintOps[2][i]] += rows - paintedRows;  // 该列颜色的格子数增加（总行数 - 被刷过的行数）
                paintedCols++;  // 被刷过的列数加1
            }
        }
    }
    
    // 按颜色编号从小到大输出每种颜色的格子数
    for(int i = 1; i <= colors; i++) {
        if(colorCount[i]) {  // 只输出数量不为0的颜色
            printf("%d %d\n", i, colorCount[i]);
        }
    }
}

int main() {
    solve();  // 直接调用一次solve函数
    return 0;
}

返回目录

完美回文数

  • perfect palindrome Number
  • 1e5内的完美回文数只有三个{11，1001，1111}
  • 输入T(样例数)，n(数据)
  • 输出：每行输出一个样例的结果，如果n不能由完美回文数累加得到，输出0
  • 思路：动态规划
  • 很正常，如果从n反推由多少个pre_pal组成，思路会很复杂且不清楚，但是我倒过来思考

  • 如果我提前把所有完美回文数可能的组成情况预先计算并储存进入数组，思路就会清楚很多

  • 而且也很容易实现代码，甚至时间复杂度是O(T);

  • 真是优雅啊
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<stdio.h>
#include<limits.h>

#define MAX 100000

int dp[MAX+1]={};
int pre_pal[3]={11,1001,1111};

int main()
{
    
    for(int i=1;i<=MAX;i++)
    {
		dp[i]=INT_MAX;//每个dp赋值为int类型的最大值，而dp[0]是dp的开始
	}
	//核心代码
	for(int i=0;i<=MAX;i++)
	{
		for(int j=0;j<3;j++){
			if(i>=pre_pal[j]&&dp[i-pre_pal[j]!=INT_MAX])//i表示在1e5内可以由三个完美回文数生成的值
            {
				dp[i]=(dp[i]<dp[i-pre_pal[j]]+1)?dp[i]:dp[i-pre_pal[j]]+1;
			}
		}
        //举个例子，首次出现由完美回文数组成的整数是11，就有dp[11]=1
        //dp[22]->dp[11]+1=2,dp[33]->dp[22]+1=3,dp[44]->dp[33]+1=4,dp[55]->dp[44]+1=5直到dp[1001]出现，此时又像dp[11]一样，记为1
        //当第一个特殊的n出现时，1012，这么说吧，1012=1001+11，而循环是从小的pre_pal开始的，第一个检查的值就是1012-11
        //所以，dp[1012]=dp[1001]+dp[11]=(1+1=2)
	}
	
	
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int k;
		scanf("%d",&k);
		if(k<=MAX&&dp[k]!=INT_MAX){//如果k是完美回文数的和，输出结果，处理类似于前缀和
			printf("%d\n",dp[k]);
		}else{
			printf("0\n");
		}
	}
	
	
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int k;
		scanf("%d",&k);
		if(k<=MAX&&dp[k]!=INT_MAX){//如果k是完美回文数的和，输出结果，处理类似于前缀和
			printf("%d\n",dp[k]);
		}else{
			printf("0\n");
		}
	}
	return 0;
}

返回目录

最多的可变字符串

  • 最多的可变字符串
  • 模拟题，重在实现代码，思路很直接
  • 关于<string.h>头文件里的两个函数
  • 1.strcpy

strcpy函数用于将一个字符串复制到另一个字符串中，其函数原型为：

char *strcpy(char *dest, const char *src);

其中，dest为指向目标字符串的指针，src为指向源字符串的指针。strcpy函数会将src指向的字符串复制到dest指向的字符串中，并返回dest指针
strcpy函数会复制包括字符串结尾的空字符’\0’在内，因此目标字符串dest必须有足够的空间来存储源字符串

  • 2.strcmp

strcmp函数用于比较两个字符串的大小，其函数原型为：

int strcmp(const char *str1, const char *str2);

参数说明：
str1：要比较的第一个字符串。
str2：要比较的第二个字符串。
返回值：
strcmp 函数返回一个整数，表示两个字符串的比较结果：

返回 0：表示 str1 和 str2 内容相同。
返回正值：表示 str1 按字典顺序大于 str2，即 str1 中第一个不同字符的 ASCII 值大> 于 str2 中对应字符的 ASCII 值。
返回负值：表示 str1 按字典顺序小于 str2，即 str1 中第一个不同字符的 ASCII 值小> 于 str2 中对应字符的 ASCII 值。
工作原理：
strcmp 逐个比较两个字符串的字符，直到找到第一个不同的字符或其中一个字符串结束（遇到空字符 ‘\0’）。
如果字符串在比较之前的部分完全相同且长度不同，则较短的字符串按字典顺序被认为是较小的。

  • 上代码
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
43
44
45
46
47
48
49
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char s[111][22];
char id[111][22];
int cnt[111];

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

void solve(){
    int i, j, n, k;
    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        scanf("%s", s[i]);//读入
        strcpy(id[i], s[i]);
        qsort(s[i], strlen(s[i]), sizeof(char), cmp);//排序
    }
    memset(cnt, 0, sizeof(cnt));
    for(i = 1; i < n; i++)
        if(cnt[i] == 0){
            cnt[i] = 1;
            for(j = i + 1; j <= n; j++)
                if(strcmp(s[i], s[j]) == 0){
                    cnt[i]++;
                    cnt[j] = -i;
                }
        }
    k = 1;
    for(i = 2; i <= n; i++)
        if(cnt[i] > cnt[k]) k = i;
    printf("%d\n", cnt[k]);
    printf("%s\n", id[k]);
    for(i = 1; i <= n; i++)
        if(cnt[i] == -k)
            printf("%s\n", id[i]);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--){
	    solve();
	    printf("\n");
	}
	return 0;
}

返回目录

青蛙

该题不是很难，本质是一个数学题，找到规律即可做出
但是如果没有想到数学方法，就会很困难，纯模拟的思路只有循环队列可以较为轻松的实现

code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int a,b;
        scanf("%d%d",&a,&b);
        if(gcd(a,b+1)==1){//很正常，如果两个数互质，那么两个数取模，就可以取遍所有的可能
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}

返回目录

完全平方数2

找个时间重写一下

总结以下这类题型的规律
对于给定方程的求解，参变分离，把方程转化成两个因式相乘=一个已知数的形式
枚举其中两个因式，解方程，判断是否符合条件即可
所以，重点就在于怎么构造方程

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

typedef long long ll;

void cramer_del(ll a1, ll b1, ll c1, ll a2, ll b2, ll c2, double *x1, double *x2) {
    ll D = a1 * b2 - a2 * b1;
    ll D1 = c1 * b2 - c2 * b1;
    ll D2 = a1 * c2 - a2 * c1;
    *x1 = (double)D1 / D;
    *x2 = (double)D2 / D;
}//克莱姆法则

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

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        ll b, c;
        scanf("%lld %lld", &b, &c);
        ll sum = 4 * c - b * b;

        if (sum == 0) {
            printf("-1\n");
            continue;
        }

        ll solutions[2000];  // 用于存储解
        int solution_count = 0;

        for (ll f = 1; f * f <= llabs(sum); f++) {//添加绝对值，因为sum可能为负数
            if (sum % f == 0) {
                ll factors[2] = {f, sum / f};

                for (int i = 0; i < 2; i++) {
                    ll factor = factors[i];
                    double x, t;
                    cramer_del(-2, 2, factor + b, 2, 2, sum / factor - b, &x, &t);

                    if (x == (ll)x && x > 0) {
                        solutions[solution_count++] = (ll)x;
                    }
                }
            }
        }

        if (solution_count == 0) {
            printf("0");
        } else {
            qsort(solutions, solution_count, sizeof(ll), compare);
            for (int i = 0; i < solution_count; i++) {
                if (i > 0) {
                    printf(" ");
                }
                printf("%lld", solutions[i]);
            }//满足输出格式
        }
        
        printf("\n");
    }
    return 0;
}

返回目录

拼图

这个题凭我自己是写不出来的，下面这个代码用了回溯，十分巧妙
详细过程我用流程图展示了

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
solve(puzzles, index)
 ├── index == 4 ?
 │    ├── 是：尝试不同旋转组合
 │    │    ├── r0 = 0 to 3
 │    │    │    ├── r1 = 0 to 3
 │    │    │    │    ├── r2 = 0 to 3
 │    │    │    │    │    ├── r3 = 0 to 3
 │    │    │    │    │    │    ├── check(puzzles) ?
 │    │    │    │    │    │    │    ├── 是：返回 true
 │    │    │    │    │    │    │    └── 否：rotate(puzzles[3])
 │    │    │    │    │    │    └── 结束 r3 循环
 │    │    │    │    │    └── rotate(puzzles[2])
 │    │    │    │    └── 结束 r2 循环
 │    │    │    └── rotate(puzzles[1])
 │    │    └── 结束 r1 循环
 │    └── rotate(puzzles[0])
 │    └── 结束 r0 循环
 │    └── 返回 false
 └── 否：生成全排列
      ├── i = index to 3
      │    ├── 交换 puzzles[index] 和 puzzles[i]
      │    ├── solve(puzzles, index + 1) ?
      │    │    ├── 是：返回 true
      │    │    └── 否：恢复 puzzles[index] 和 puzzles[i]
      └── 结束 i 循环
 └── 返回 false
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
75
solve(puzzles, index)
 ├── index == 4 ?
 │    └── 否：生成全排列
      ├── i = index to 3
      │    ├── 交换 puzzles[index] 和 puzzles[i]
      │    │    ├── index = 0, i = 0
      │    │    │    ├── puzzles[0] 和 puzzles[0] 交换
      │    │    │    └── solve(puzzles, 1)
      │    │    │         ├── index = 1, i = 1
      │    │    │         │    ├── puzzles[1] 和 puzzles[1] 交换
      │    │    │         │    └── solve(puzzles, 2)
      │    │    │         │         ├── index = 2, i = 2
      │    │    │         │         │    ├── puzzles[2] 和 puzzles[2] 交换
      │    │    │         │         │    └── solve(puzzles, 3)
      │    │    │         │         │         ├── index = 3, i = 3
      │    │    │         │         │         │    ├── puzzles[3] 和 puzzles[3] 交换
      │    │    │         │         │         │    └── solve(puzzles, 4)
      │    │    │         │         │         │         ├── index == 4 ? 是：尝试不同旋转组合
      │    │    │         │         │         │         └── 返回 true 或 false
      │    │    │         │         │         └── 结束 i 循环
      │    │    │         │         └── 结束 i 循环
      │    │    │         └── 结束 i 循环
      │    │    ├── index = 0, i = 1
      │    │    │    ├── puzzles[0] 和 puzzles[1] 交换
      │    │    │    └── solve(puzzles, 1)
      │    │    │         ├── index = 1, i = 1
      │    │    │         │    ├── puzzles[1] 和 puzzles[1] 交换
      │    │    │         │    └── solve(puzzles, 2)
      │    │    │         │         ├── index = 2, i = 2
      │    │    │         │         │    ├── puzzles[2] 和 puzzles[2] 交换
      │    │    │         │         │    └── solve(puzzles, 3)
      │    │    │         │         │         ├── index = 3, i = 3
      │    │    │         │         │         │    ├── puzzles[3] 和 puzzles[3] 交换
      │    │    │         │         │         │    └── solve(puzzles, 4)
      │    │    │         │         │         │         ├── index == 4 ? 是：尝试不同旋转组合
      │    │    │         │         │         │         └── 返回 true 或 false
      │    │    │         │         │         └── 结束 i 循环
      │    │    │         │         └── 结束 i 循环
      │    │    │         └── 结束 i 循环
      │    │    ├── index = 0, i = 2
      │    │    │    ├── puzzles[0] 和 puzzles[2] 交换
      │    │    │    └── solve(puzzles, 1)
      │    │    │         ├── index = 1, i = 1
      │    │    │         │    ├── puzzles[1] 和 puzzles[1] 交换
      │    │    │         │    └── solve(puzzles, 2)
      │    │    │         │         ├── index = 2, i = 2
      │    │    │         │         │    ├── puzzles[2] 和 puzzles[2] 交换
      │    │    │         │         │    └── solve(puzzles, 3)
      │    │    │         │         │         ├── index = 3, i = 3
      │    │    │         │         │         │    ├── puzzles[3] 和 puzzles[3] 交换
      │    │    │         │         │         │    └── solve(puzzles, 4)
      │    │    │         │         │         │         ├── index == 4 ? 是：尝试不同旋转组合
      │    │    │         │         │         │         └── 返回 true 或 false
      │    │    │         │         │         └── 结束 i 循环
      │    │    │         │         └── 结束 i 循环
      │    │    │         └── 结束 i 循环
      │    │    ├── index = 0, i = 3
      │    │    │    ├── puzzles[0] 和 puzzles[3] 交换
      │    │    │    └── solve(puzzles, 1)
      │    │    │         ├── index = 1, i = 1
      │    │    │         │    ├── puzzles[1] 和 puzzles[1] 交换
      │    │    │         │    └── solve(puzzles, 2)
      │    │    │         │         ├── index = 2, i = 2
      │    │    │         │         │    ├── puzzles[2] 和 puzzles[2] 交换
      │    │    │         │         │    └── solve(puzzles, 3)
      │    │    │         │         │         ├── index = 3, i = 3
      │    │    │         │         │         │    ├── puzzles[3] 和 puzzles[3] 交换
      │    │    │         │         │         │    └── solve(puzzles, 4)
      │    │    │         │         │         │         ├── index == 4 ? 是：尝试不同旋转组合
      │    │    │         │         │         │         └── 返回 true 或 false
      │    │    │         │         │         └── 结束 i 循环
      │    │    │         │         └── 结束 i 循环
      │    │    │         └── 结束 i 循环
      │    └── 结束 i 循环
 └── 返回 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
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
#include<stdio.h>
#include<string.h>
#include<stdbool.h>

char puzzle[4][4];

void rotate(char *puzzle){
    char temp[4];
    for(int i=0;i<4;i++){
        temp[i]=puzzle[(i+1)%4];
    }
    for(int i=0;i<4;i++){
        puzzle[i]=temp[i];
    }
}

void swap(char puzzle1[],char puzzle2[]){
    char temp[4];
    memcpy(temp,puzzle1,sizeof(temp));
    memcpy(puzzle1,puzzle2,sizeof(temp));
    memcpy(puzzle2,temp,sizeof(temp));
}

bool match(char a,char b){
    return a-b==32||b-a==32;
}

bool check(char puzzle[4][4]){
    return match(puzzle[0][1],puzzle[1][3])&&
    match(puzzle[0][2],puzzle[3][0])&&
    match(puzzle[3][1],puzzle[2][3])&&
    match(puzzle[1][2],puzzle[2][0]);
}

bool solve(char puzzle[4][4],int index){
    if(index==4){
        for(int x0=0;x0<4;x0++){
            for(int x1=0;x1<4;x1++){
                for(int x2=0;x2<4;x2++){
                    for(int x3=0;x3<4;x3++){
                        if(check(puzzle)) return true;
                        rotate(puzzle[3]);
                    }
                    rotate(puzzle[2]);
                }
                rotate(puzzle[1]);
            }
            rotate(puzzle[0]);
        }
    return false;
    }else{
        for(int i=index;i<4;i++){
            swap(puzzle[i],puzzle[index]);
            if(solve(puzzle,index+1)) return true;
            swap(puzzle[i],puzzle[index]);
        }
    }
    return false;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        for(int i=0;i<4;i++){
            scanf("%s",puzzle[i]);
        }
        if(solve(puzzle,0)){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}

返回目录

prime palindromes

problem

本题是在洛谷上的题
其实说明和提示在题目里面就有了
本题重要的是先生成所有的回文质数，然后再判断是否符合条件
否则，TLE警告
详细讲解在注释

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
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
#include <iostream>
using namespace std;

// 检查一个数是否为质数
bool isPrime(int n) {
    if (n <= 1) return false;           // 小于等于1的数不是质数
    if (n == 2 || n == 3) return true;  // 2和3是质数
    if (n % 2 == 0 || n % 3 == 0) return false;  // 任何偶数和3的倍数不是质数
    for (int i = 5; i * i <= n; i += 6) {        // 从5开始检查因子，每次增量为6（检查6k±1的形式）
        if (n % i == 0 || n % (i + 2) == 0) return false;  // 如果n能被i或i+2整除，则n不是质数
    }
    return true;  // 如果通过所有测试，n是质数
}

// 生成给定长度的回文数并检查它们是否为质数
void generatePalindromes(int a, int b, int length) {
    int start = 1, end = 1;
    
    // 手动计算start和end的值，不使用pow函数
    for (int i = 1; i < (length + 1) / 2; ++i) {
        start *= 10;  // start为10的(length-1)/2次方
        end *= 10;    // end为10的(length)/2次方
    }
    end *= 10;

    // 如果长度是奇数
    if (length % 2 == 1) {
        for (int i = start; i < end; ++i) {
            // 生成一个奇数长度的回文数
            int palindrome = i;
            int n = i / 10;  // 忽略中间的数字，以生成回文数
            while (n > 0) {
                palindrome = palindrome * 10 + (n % 10);  // 反转数字并附加到palindrome的末尾
                n /= 10;
            }

            // 检查生成的回文数是否在[a, b]范围内并且是质数
            if (palindrome >= a && palindrome <= b && isPrime(palindrome)) {
                cout << palindrome << endl;
            }
        }
    } else {
        // 如果长度是偶数
        for (int i = start; i < end; ++i) {
            int palindrome = i;
            int n = i;  // 保留完整的数字以生成回文数
            while (n > 0) {
                palindrome = palindrome * 10 + (n % 10);  // 反转数字并附加到palindrome的末尾
                n /= 10;
            }

            // 检查生成的回文数是否在[a, b]范围内并且是质数
            if (palindrome >= a && palindrome <= b && isPrime(palindrome)) {
                cout << palindrome << endl;
            }
        }
    }
}

int main() {
    int a, b;
    cin >> a >> b;

    // 调整a和b，使得b最大为10000000
    if (b > 9989899) b = 9989899;

    // 遍历长度为1到7的所有可能的回文数
    for (int length = 1; length <= 7; ++length) {
        generatePalindromes(a, b, length);
    }

    return 0;
}

返回目录

众数

problem

二分基础题，但由于我刚接触二分的原因，这个题卡了很久，而且一贯的，这个题卡了Long long
二分+检查
二分查找区间最大值，区间最大值可以转化为众数的出现次数
在条件k的限制下，检查区间内的操作能否满足条件，满足则扩大区间，不满足则缩小区间

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

typedef long long ll;

ll a[100010] = {0}, s[100010] = {0};

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

int check(ll n, ll k, ll mid) {
    for (ll i = 1; i <= n - mid + 1; i++) {
        ll op = a[i + mid - 1] * mid - (s[i + mid - 1] - s[i - 1]);
        if (op <= k) return 1;
    }
    return 0;
}

ll solve(ll n, ll k) {
    qsort(a + 1, n, sizeof(ll), cmp);

    for (ll i = n; i > 0; i--) {
        a[i] -= a[1];
    }

    for (ll i = 1; i <= n; i++) {
        s[i] = a[i] + s[i - 1];
    }//我在调代码的过程中发现，要使用前缀和只能让a[n]从下标1开始，不然处理起来会很麻烦，导致数组越界

    ll left = 1, right = n;
    ll ans = 1;
    while (left <= right) {
        ll mid = left + (right - left) / 2;
        if (check(n, k, mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

int main() {
    ll T;
    scanf("%lld", &T);
    while (T--) {
        ll n, k;
        scanf("%lld%lld", &n, &k);
        
        for (ll i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }

        printf("%lld\n", solve(n, k));
        memset(a, 0, sizeof(ll) * 100010);
        memset(s, 0, sizeof(ll) * 100010);
    }
    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
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#include <stdlib.h>

#define MAXN 100000
typedef long long ll;


ll a[MAXN + 1], sum[MAXN + 1];


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

void solve(int n, ll k) {
    qsort(a + 1, n, sizeof(ll), cmp);
    //前缀和
    sum[0] = 0;
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i];
    }

    ll ans = 1;  // 至少每个数自己本身出现一次
    
    for (int i = 1; i <= n; i++) {
        ll left = 1, right = i, best = 1;
        //right表示区间的最右侧，一开始初始化为区间最大值
        //二分查找
        
        while (left <= right) {
        	
            ll mid = (left + right) / 2;
            
            
            //其他都没有变化，变化的只有i，也就是说，二分查找的是在以a[i]为众数的情况下，最大的区间长度
            ll op = a[i] * mid - (sum[i] - sum[i - mid]);//op是操作次数
            //mid表示区间长度
            if (op <= k) {
                best = mid;
                left = mid + 1;//如果满足，则扩充区间长度
            } else {
                right = mid - 1;//不满足，则减少区间长度
            }
            
        }
        if (best > ans) {
            ans = best;
        }
    }

    printf("%lld\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        ll k;
        scanf("%d %lld", &n, &k);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }//从下标1开始
        solve(n, k);
    }
    return 0;
}

返回目录

premixSum

  • 前缀和
    思路打开了，这个题目用二分
    总结一下使用二分的情况：
    在单个数组里高效的查找最大最小值，或者最小最大值
    对于向下查找还是向上查找，就要看目的是什么了
    使用二分时，往往有一个可以用在check函数里的限制条件
    left和right可以对应区间里的最小值或者最大值
    这些都是套路，真正重要的是明白二分查找什么时候该用，该怎么用
    oj上使用二分的题目大部分都是一个套路，只是有些题目的二分方法比较难发现，比如众数，比如这道题
premix_sum 
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 <stdlib.h>

#define N 1011
int a[N], b[N];

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

int find(int left, int right, int x) {
    //to find the maximum index of b[] that b[index]<=x
    int mid, ans = 0;
    while (left <= right) {
        mid = (left + right) >> 1;
        if (b[mid] <= x) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

int main() {
    int T, i, n, m, index, ans;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        for (i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (i = 1; i <= m; i++) scanf("%d", &b[i]);
        qsort(b + 1, m, sizeof(int), cmp);
        //prefix sum
        for (i = 1; i <= n; i++) a[i] += a[i - 1];
        for (i = 1; i <= m; i++) b[i] += b[i - 1];
        ans = 0;
        for (i = 0; i <= n; i++) {
            //bs(int left, int right, int x)
            //return the maximum index of b[] that b[index]<=x
            index = find(1, m, -a[i]-1);
            //why is -a[i]-1? because only that can make sure a[i]+b[index]<0 <==> a[i]+b[index]+1<=0
            if (a[i] + b[index] < 0 && index + i > ans) ans = index + i;
            //the logic of refreshing ans 
        }
        printf("%d\n", ans);
    }
    return 0;
}

埃氏筛

两份代码没什么区别，只有一个关于埃氏筛的小细节，导致时间效率不一样
原题：哈希

code1 
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>

#define MAXN 10000
int prime[MAXN];
int count[MAXN];

void oula() {
    for (int i = 2; i < MAXN; i++) {
        prime[i] = 1;
    }
    for (int i = 2; i * i < MAXN; i++) {
        if (prime[i]) {
            for (int j = i * i; j < MAXN; j += i) {
                prime[j] = 0;
            }
        }
    }
}

int solve(int *num, int n) {
    for (int sz = 2; sz < MAXN; sz++) {
        if (prime[sz]) {
            memset(count, 0, sizeof(count));
            int flag = 1;
            for (int j = 0; j < n; j++) {
                int hash_val = num[j] % sz;
                count[hash_val]++;
                if (count[hash_val] > 2) {
                    flag = 0;
                    break;
                }
            }
            if (flag) return sz;
        }
    }
    return -1;
}

int main() {
    oula();
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        int num[n];
        for (int i = 0; i < n; i++) {
            scanf("%d", &num[i]);
        }
        printf("%d\n", solve(num, n));
    }
    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
57
58
59
60
#include<stdio.h>
#include<string.h>
#define MAXN 100010
int prime[MAXN];

int genPrime(){
	for(int i=0;i<MAXN;i++){
		prime[i]=1;
	}
	for(int i=2;i<MAXN;i++ ){
		if(prime[i]){
			for(int j=i*2;j<MAXN;j+=i){
				
				prime[j]=0;
			}
		}
	}
	
}

int solve(int *a,int n){
	int temp=0,flag=0;
	
	int cnt[MAXN]={};
	for(int i=2;i<MAXN;i++){
		if(prime[i]){
			flag=0;
			for(int j=0;j<n;j++){
				temp=a[j]%i;
				cnt[temp]++;
				if(cnt[temp]>2){
					flag=1;
					break;
				}
			}
			memset(cnt,0,sizeof(cnt));	
		}
		if(flag==0){
			return i;
			break;
		}	
	}
}
int main()
{
	int T;
	genPrime();
	
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		int a[n];
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		printf("%d\n",solve(a,n));
	}
	return 0;
}

返回目录

cs xtuoj
#oj
xtuoj-part1
http://example.com/2024/10/17/xtuoj/
Author
Anfsity
Posted on
October 17, 2024
Licensed under