2023级软院算法第一次练习赛

测评情况

A sort

考察知识点

排序

思路分析

题目写得比较明白，就是需要进行一个多关键字排序，具体实现比较简单，就不详细说明了

AC代码

#include<bits/stdc++.h>
using namespace std;

typedef struct Student {
    char name[9];
    int algo_score;
    int ds_score;
    int cp_score;
    int total_score;
} Student;

Student students[100000] = {0};

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        char temp_name[9];
        scanf("%s %d %d %d", &students[i].name, &students[i].algo_score, &students[i].ds_score, &students[i].cp_score);
        students[i].total_score = students[i].algo_score + students[i].ds_score + students[i].cp_score;
    }

    sort(students, students + n, [](Student a, Student b) {
        if (a.total_score == b.total_score) {
            if (a.algo_score == b.algo_score) {
                return strcmp(a.name, b.name) < 0;
            } else {
                return a.algo_score > b.algo_score;
            }
        } else {
            return a.total_score > b.total_score;
        }
    });

    for (int i = 0; i < n; i++) {
        printf("%s\n", students[i].name);
    }

    return 0;
}

B Hope Is the Thing with Feathers

考察知识点

排序
查找

思路分析

由于时间复杂度要求，不能够进行暴力搜索来遍历查找最终答案，所以我们可以缩小范围，对于数字序列进行排序后二分查找，同时查找只需要找到对应的答案的一个区间长度即可，对于具体是什么数字可以不用关心

使用cpp的一个好处就是可以使用现成的upper_bound()和lower_bound()函数，省去了手写二分查找的麻烦

AC代码

#include<bits/stdc++.h>
using namespace std;

long long a[1000000] = {0};

int main() {
    int n, q;
    scanf("%d %d", &n, &q);

    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    sort(a, a + n);

    for (int i = 0; i < q; i++) {
        long long d, k;
        scanf("%lld %lld", &d, &k);
        int start, end;
        start = lower_bound(a, a + n, d * k) - a;
        end = upper_bound(a, a + n, d * (k + 1ll) - 1ll) - a;
        printf("%d\n", end - start);
    }

    return 0;
}

C 莫卡寻宝

考察知识点

模拟

思路分析

这个数据范围太小了，可以直接暴力遍历

AC代码

#include<bits/stdc++.h>
using namespace std;

int a[1000] = {0};

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);

    int max = 0, min = 0, max_value = 0, value = 0;
    for (int i = 0; i < n; i++) {
        min = a[i];
        max = a[i] + k;
        value = a[i];
        for (int j = i + 1; j < n; j++) {
            if (a[j] <= max) {
                value += a[j];
            } else {
                break;
            }
        }
        if (value > max_value) {
            max_value = value;
        }
    }
    printf("%d\n", max_value);
    return 0;
}

D 莫卡与序列

原题如下

考察知识点

数学取模

思路分析

由于整除的数也是序列中的正整数，所以必定有其中一个数是全序列中的最小数字

同理，再除去序列中被最小数整除的所有数后，剩下的数的最小数字也必定是存在的答案中的一个数

得到两个数后遍历序列按个判断是否整除即可

算法时间复杂度

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000000000

int a[100000] = {0};

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        int min1, min2;
        min1 = min2 = MAX;
        for (int i = 0; i < n; i++) {
            if (a[i] < min1) {
                min1 = a[i];
            }
        }
        for (int i = 0; i < n; i++) {
            if (a[i] % min1) {
                if (a[i] < min2) {
                    min2 = a[i];
                }
            }
        }
        int flag = 1;
        for (int i = 0; i < n; i++) {
            if (a[i] % min1 != 0 && a[i] % min2 != 0) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

E 排位胜率（Easy Version）

原题如下

考察知识点

概率论

思路分析

如果暴力枚举加模拟，时间复杂度最大，即3.0414093201713378043612608166065e+64，放弃

仔细看时间限制放成了2s，说明时间上要求宽泛很多了，

嘶难www烦

条件概率问题

先不要管那个机制本身，数学分析一下

假设事件A为“第n+1局比赛赢”，事件B为“n + 1局比赛全输”

游戏机制就是让B事件成为不可能事件

那么题目要求算的概率就是

因为B包含A，所以题目给的概率就是

AC代码

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, p;
    scanf("%d%d", &n, &p);
    double win = p / 100.0;
    double lose  = 1 - win;
    double ans = win / (1 - pow(lose, n + 1));
    printf("%.3f\n", ans);
    return 0;
}

F 莫卡的手套

原题如下

考察知识点

组合数学/离散数学3
逆元
快速幂

思路分析

从n副手套里拿出m只要求存在k对的情况数目，从组合数学的角度考虑

从n里挑k副

$副种数$

在的情况下，剩下副即只，要求再挑只且无成双的

$情况数鸽巢原理$

综合一下

$情况数鸽巢原理或$

问题是怎么计算数字了

把组合数简化为

需要计算阶乘、大数除法求模、幂

阶乘采用最普通的循环求模计算即可

大数除法求模需要用到逆元，将除法转化为在模的意义下等价的乘法运算，避免数据过大溢出，同时求逆元的算法有拓展欧几里得算法和快速幂加费马小定理算法，我选择了后者，具体理论详细可以自行网上搜索

幂的计算涉及快速幂降低时间复杂度，具体模板可以网上搜索

综合以上，尤其注意数据溢出问题，对于每个乘法结果都需要立即求模避免多个大数相乘溢出

AC代码

#include<bits/stdc++.h>
using namespace std;

#define MOD 1000000007

long long cmod(long long a, long long b, long long mod);
long long qpowmod(long long a, long long b, long long mod);
long long stairmod(long long a, long long mod);
long long reverse_multmod(long long a, long long mod);

int main() {
    int t;
    scanf("%d", &t);
    int n, m, k;
    while (t--) {
        scanf("%d%d%d", &n, &m, &k);
        if (2 * k > m || m - 2 * k > n - k) {
            printf("0\n");
        } else {
            long long ans = stairmod(n, MOD) * reverse_multmod(stairmod(k, MOD), MOD) % MOD * reverse_multmod(stairmod(m - 2 * k, MOD), MOD) % MOD * reverse_multmod(stairmod(n - m + k, MOD), MOD) % MOD * qpowmod(2, m - 2 * k, MOD) % MOD;
            printf("%lld\n", ans);
        }
    }
    return 0;
}

// 组合数取模
long long cmod(long long a, long long b, long long mod) {
    long long fracup = stairmod(a, mod);
    long long fracdown1 = reverse_multmod(stairmod(b, mod), mod);
    long long fracdown2 = reverse_multmod(stairmod(a - b, mod), mod);
    return ((((fracup % mod) * (fracdown1 % mod)) % mod) % mod * (fracdown2 % mod)) % mod;
}

// 快速幂取模
long long qpowmod(long long a, long long b, long long mod) {
    long long ans = 1;
    a = (a % mod + mod) % mod;
    for (; b; b >>= 1) {
        if (b & 1) {
            ans = (a * ans) % mod;
        }
        a = (a * a) % mod;
    }
    return ans;
}

// 阶乘取模
long long stairmod(long long a, long long mod) {
    long long temp = 1;
    for (int i = 2; i <= a; i++) {
        temp *= i;
        temp %= mod;
    }
    return temp;
}

// 逆元取模
long long reverse_multmod(long long a, long long mod) {
    return qpowmod(a, mod - 2, mod);
}

G 莫卡和魔法图案

原题如下

考察知识点

分治

思路分析

题目描述已经涉及到了递归操作和问题分解，那么就直接分治处理就行了，具体实现看代码

AC代码

#include<bits/stdc++.h>
using namespace std;

char picture[729][729] = {0};

void draw(int k, int x, int y);
void draw_white(int k, int x, int y);
void print(int k);

int main() {
    int k;
    scanf("%d", &k);
    draw(k, 0, 0);
    print(k);
    return 0;
}

void draw(int k, int x, int y) {
    if (k == 0) {
        picture[x][y] = '#';
    } else {
        int len = pow(3, k - 1);
        draw(k - 1, x, y);
        draw(k - 1, x + len, y);
        draw(k - 1, x + 2 * len, y);
        draw(k - 1, x, y + len);
        draw_white(k - 1, x + len, y + len);
        draw(k - 1, x + 2 * len, y + len);
        draw(k - 1, x, y + 2 * len);
        draw(k - 1, x + len, y + 2 * len);
        draw(k - 1, x + 2 * len, y + 2 * len);
    }
}

void draw_white(int k, int x, int y) {
    if (k == 0) {
        picture[x][y] = '.';
    } else {
        int len = pow(3, k);
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                picture[x + i][y + j] = '.';
            }
        }
    }
}

void print(int k) {
    int len = pow(3, k);
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            printf("%c", picture[i][j]);
        }
        printf("\n");
    }
}

H 多种口味的月饼

中秋节也过了，就别搞那么多坑了叭ww

原题如下

考察知识点

细致入微
滑动窗口

思路分析

按这个数据量最好是在线处理时间复杂度为

注意不存在的情况下输出为N0不是NO，以后老实复制叭，这个问题会挂第2, 3点

看问题是满足特定要求的最小区间问题，套路滑动窗口

滑动窗口就是一个动态的区间范围，为了满足题目要求在线性处理的过程中动态变化找到最优解

在这里要求是区间内所有种类月饼都满足，且要求区间长度最小，不难想到在在线处理的过程中，对于每种特定的月饼记录最大位置，因为是在线处理所以最大位置是最紧凑的一种区间，可能有点抽象可以看下图

-----------
|1|2|2|1|4|
-----------
       ^

当指针指到1时，我们需要的是最靠右的1，于此同时前面的2也应该取最靠右的2作为更新的参考位置，因为当1位置更新到2右边时，此时最优应该取靠右的2

举例说明滑动窗口

输入为

1
6 3
1 2 2 1 3 1

设置数组kind用来存每种月饼的最右位置

处理过程如下

1 2 2 1 3 1  left = 1 right = 1 kind[1] = 1 left 表示可能为答案的区间的最左端 同理 right 为答案的区间的最右端
^
1 2 2 1 3 1  left = 1 right = 2 kind[1] = 1 kind[2] = 2
  ^
1 2 2 1 3 1  left = 1 right = 2 kind[1] = 1 kind[2] = 3
    ^
1 2 2 1 3 1  left = 3 right = 4 kind[1] = 4 kind[2] = 3 此时第1种月饼出现更后的位置，更新窗口
      ^
1 2 2 1 3 1  left = 3 right = 5 kind[1] = 4 kind[2] = 3 kind[3] = 5 l = 3 r = 5 此时开始存在答案
        ^
1 2 2 1 3 1  left = 3 right = 5 kind[1] = 4 kind[2] = 3 kind[3] = 5 l = 3 r = 5
          ^

大体过程如上，利用滑动区间就能很好地解决同类满足特定条件的最小区间问题

AC代码

#include<bits/stdc++.h>
using namespace std;

int kind[100001] = {0};
int a[100001] = {0};

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n, k;
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
        if (n < k) {
            printf("N0\n");
            memset(kind, 0, sizeof(kind[0]) * (k + 1));
            memset(a, 0, sizeof(a[0]) * (n + 1));
            continue;
        }
		for (int i = 1; i <= k; i++) {
			kind[a[i]] = i;
		}
		int p = k;
		int end = 0;
		while (1) {
			int flag = 1;
			for (int i = 1; i <= k; i++) {
				if (kind[i] == 0) {
					flag = 0;
					break;
				}
			}
			if (flag) {
				break;
			} else {
				p++;
				if (p <= n) {
					kind[a[p]] = p;
				} else {
					printf("N0\n"); // 1 2 3dian NOOOOOOOOOO0!!!
					memset(kind, 0, sizeof(kind[0]) * (k + 1));
					memset(a, 0, sizeof(a[0]) * (n + 1));
					end = 1;
					break;
				}
			}
		}
		if (end) {
			continue;
		}
		int r = p;
		int l = p;
		for (int i = 1; i <= k; i++) {
			if (kind[i] <= l) {
				l = kind[i];
			}
		}
		int minlen = r - l;
		int left = l;
		int right = r;
		while (p <= n - 1) {
			p++;
			kind[a[p]] = p;
			if (a[p] == a[left]) {
				right = p;
				while (kind[a[left]] != left) {
					left++;
				}
				if (right - left < minlen) {
					r = right;
					l = left;
					minlen = right - left;
				}
			}
		}
		
		printf("%d %d\n", l, r);
		memset(kind, 0, sizeof(kind[0]) * (k + 1));
		memset(a, 0, sizeof(a[0]) * (n + 1));
	}
	return 0;
}

I If I Can Stop One Heart From Breaking

好可爱的题ww

原题如下

考察知识点

链表

思路分析

这里初步观察觉得最耗时间的是同类鱼的最短距离查找，然后可能还有非同类🐟之间的还有还有…

用链表试试

链表结点记录一下几项

左节点非同类的指针
距离左节点非同类的指针的距离
左节点同类的指针
距离左节点同类的指针的距离
🐟的种类
是否被吃
距离右节点同类的指针的距离
右节点同类的指针
距离右节点非同类的指针的距离
右节点非同类的指针
对于每个🐟被吃了后还可以尝试更新距离信息，不过感觉这样做不太好就先不做
端点🐟指针可以为NULL用来识别是否同类🐟被吃完啦或者到坐标尽头啦

一开始查询最近🐟🐟是靠链表来的，但是TLE了www

后面决定改进！

涉及几个函数

新建结点
构建链接并记录数据
删除结点并重新处理数据

最后试了试好像还是不行，这里放一个我写的很喜欢的但是TLE的代码

#include<stdio.h>
#include<string.h>

typedef struct fish {
    struct fish* left_diff;
    int left_diff_distance;
    struct fish* left_same;
    int left_same_distance;
    int type;
    int is_left;
    int position;
    int right_diff_distance;
    struct fish* right_diff;
    int right_same_distance;
    struct fish* right_same;
} fish, *fish_pointer;

fish fishs[100000] = {0};
fish_pointer fish_list[100000] = {0};



void fish_init(fish_pointer fish, int type, int position);

void add_fish_to_fishlist(fish_pointer fish);

void link_fish_diff(fish_pointer fish_left, fish_pointer fish_right);

void link_fish_same(fish_pointer fish_left, fish_pointer fish_right);

void eat_fish(fish_pointer fish);

int find_next_same_fish_pos(fish_pointer fish);

int find_next_diff_fish_pos(fish_pointer fish);

fish_pointer find_left_diff(fish_pointer fish);

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);
        for (int i = 0; i < n; i++) {
            int type;
            scanf("%d", &type);
            fish_init(&fishs[i], type, i);
            if (i == 0) {
                add_fish_to_fishlist(&fishs[i]);
            } else {
                add_fish_to_fishlist(&fishs[i]);
                fish_pointer left_diff = find_left_diff(&fishs[i]);
                if (left_diff != NULL) {
                    link_fish_diff(left_diff, &fishs[i]);
                }
            }
        }

        int now = k - 1;
        eat_fish(&fishs[now]);
        while (1) {
            int next = find_next_same_fish_pos(&fishs[now]);
            if (next == -1) {
                next = find_next_diff_fish_pos(&fishs[now]);
                if (next == -1) {
                    memset(fishs, 0, sizeof(fish) * n);
                    break;
                }
            }
            now = next;
            eat_fish(&fishs[now]);
        }
    }
    return 0;
}

void fish_init(fish_pointer fish, int type, int position) {
    fish->type = type;
    fish->position = position;
    fish->is_left = 1;
    fish->left_diff = NULL;
    fish->left_diff_distance = 0;
    fish->left_same = NULL;
    fish->left_same_distance = 0;
    fish->right_diff = NULL;
    fish->right_diff_distance = 0;
    fish->right_same = NULL;
    fish->right_same_distance = 0;
}

void add_fish_to_fishlist(fish_pointer fish) {
    if (fish_list[fish->type] == NULL) {
        fish_list[fish->type] = fish;
    } else {
        link_fish_same(fish_list[fish->type], fish);
        fish_list[fish->type] = fish;
    }
}

void link_fish_diff(fish_pointer fish_left, fish_pointer fish_right) {
    fish_left->right_diff = fish_right;
    fish_left->right_diff_distance = fish_right->position - fish_left->position;
    fish_right->left_diff = fish_left;
    fish_right->left_diff_distance = fish_right->position - fish_left->position;
}

void link_fish_same(fish_pointer fish_left, fish_pointer fish_right) {
    fish_left->right_same = fish_right;
    fish_left->right_same_distance = fish_right->position - fish_left->position;
    fish_right->left_same = fish_left;
    fish_right->left_same_distance = fish_right->position - fish_left->position;
}

void eat_fish(fish_pointer fish) {
    fish->is_left = 0;
    printf("%d ", fish->position + 1);
    if (fish->left_same != NULL && fish->right_same != NULL) {
        fish->left_same->right_same = fish->right_same;
        fish->left_same->right_same_distance += fish->right_same_distance;
        fish->right_same->left_same = fish->left_same;
        fish->right_same->left_same_distance += fish->left_same_distance;
    } else if (fish->left_same == NULL && fish->right_same != NULL) {
        fish->right_same->left_same = NULL;
        fish->right_same->left_same_distance = 0;
        fish_list[fish->type] = fish->right_same;
    } else if (fish->left_same != NULL && fish->right_same == NULL) {
        fish->left_same->right_same = NULL;
        fish->left_same->right_same_distance = 0;
    } else {
        fish_list[fish->type] = NULL;
    }

    if (fish->left_diff != NULL && fish->right_diff != NULL) {
        fish->left_diff->right_diff = fish->right_diff;
        fish->left_diff->right_diff_distance += fish->right_diff_distance;
        fish->right_diff->left_diff = fish->left_diff;
        fish->right_diff->left_diff_distance += fish->left_diff_distance;
    } else if (fish->left_diff == NULL && fish->right_diff != NULL) {
        fish->right_diff->left_diff = NULL;
        fish->right_diff->left_diff_distance = 0;
        fish_list[fish->type] = fish->right_diff;
    } else if (fish->left_diff != NULL && fish->right_diff == NULL) {
        fish->left_diff->right_diff = NULL;
        fish->left_diff->right_diff_distance = 0;
    } else {
        return;
    }
}

int find_next_same_fish_pos(fish_pointer fish) {
    if (fish->left_same == NULL && fish->right_same == NULL) {
        return -1;
    } else if (fish->left_same == NULL && fish->right_same != NULL) {
        return fish->right_same->position;
    } else if (fish->left_same != NULL && fish->right_same == NULL) {
        return fish->left_same->position;
    } else {
        if (fish->left_same_distance <= fish->right_same_distance) {
            return fish->left_same->position;
        } else {
            return fish->right_same->position;
        }
    }
}

int find_next_diff_fish_pos(fish_pointer fish) {
    if (fish->left_diff == NULL && fish->right_same == NULL) {
        return -1;
    } else if (fish->left_diff == NULL && fish->right_diff != NULL) {
        return fish->right_diff->position;
    } else if (fish->left_diff != NULL && fish->right_diff == NULL) {
        return fish->left_diff->position;
    } else {
        if (fish->left_diff_distance <= fish->right_diff_distance) {
            return fish->left_diff->position;
        } else {
            return fish->right_diff->position;
        }
    }
}

fish_pointer find_left_diff(fish_pointer fish) {
    fish_pointer left_diff;
    if (fish->position != 0) {
        left_diff = &fishs[fish->position - 1];
    } else {
        left_diff = NULL;
    }
    while (left_diff != NULL && left_diff->type == fish->type) {
        left_diff = left_diff->left_diff;
    }
    return left_diff;
}

好了，改思路

后面发现主要是寻找不同🐟🐟那里时间复杂度高了，所以干脆不找不同🐟🐟了，因为相同鱼鱼有限级更高，只需要吃🐟时删除总的链上的🐟，那么当相同🐟吃完时自然总链就不会有其它🐟了。

后期直接用数组维护信息，不加额外的函数，减少函数调用的时间开销，AC了

AC代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int fishs_same_before[100002] = {0};
int fishs_same_after[100002] = {0};
int fishs_diff_before[100002] = {0};
int fishs_diff_after[100002] = {0};
int fishs_same[100002] = {0};

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++) {
            int type;
            scanf("%d", &type);
            if (fishs_same[type] == 0) {
                fishs_same[type] = i;
            } else {
                fishs_same_before[i] = fishs_same[type];
                fishs_same_after[fishs_same[type]] = i;
                fishs_same[type] = i;
            }
            fishs_diff_after[i] = i + 1 > n ? 0 : i + 1;
            fishs_diff_before[i] = i - 1;
        }

        int now = k;
        while (now != 0) {
            int next = now;
            printf("%d ", next);
            if (fishs_same_before[now] == 0 && fishs_same_after[now] == 0) {
                if (fishs_diff_before[now] == 0 && fishs_diff_after[now] == 0) {
                    break;
                } else if (fishs_diff_before[now] == 0 && fishs_diff_after[now] != 0) {
                    next = fishs_diff_after[now];
                } else if (fishs_diff_before[now] != 0 && fishs_diff_after[now] == 0) {
                    next = fishs_diff_before[now];
                } else {
                    if (now - fishs_diff_before[now] <= fishs_diff_after[now] - now) {
                        next = fishs_diff_before[now];
                    } else {
                        next = fishs_diff_after[now];
                    }
                }
            } else if (fishs_same_before[now] == 0 && fishs_same_after[now] != 0) {
                next = fishs_same_after[now];
            } else if (fishs_same_before[now] != 0 && fishs_same_after[now] == 0) {
                next = fishs_same_before[now];
            } else {
                if (now - fishs_same_before[now] <= fishs_same_after[now] - now) {
                    next = fishs_same_before[now];
                } else {
                    next = fishs_same_after[now];
                }
            }
            fishs_same_before[fishs_same_after[now]] = fishs_same_before[fishs_same_after[now]] ? fishs_same_before[now] : 0;
            fishs_same_after[fishs_same_before[now]] = fishs_same_after[fishs_same_before[now]] ? fishs_same_after[now] : 0;
            fishs_diff_before[fishs_diff_after[now]] = fishs_diff_before[fishs_diff_after[now]] ? fishs_diff_before[now] : 0;
            fishs_diff_after[fishs_diff_before[now]] = fishs_diff_after[fishs_diff_before[now]] ? fishs_diff_after[now] : 0;
            fishs_same_before[now] = 0;
            fishs_same_after[now] = 0;
            fishs_diff_before[now] = 0;
            fishs_diff_after[now] = 0;
            now = next;
        }
        printf("\n");
        memset(fishs_same_before, 0, sizeof(fishs_same_before[0]) * (n + 2));
        memset(fishs_same_after, 0, sizeof(fishs_same_after[0]) * (n + 2));
        memset(fishs_diff_before, 0, sizeof(fishs_diff_before[0]) * (n + 2));
        memset(fishs_diff_after, 0, sizeof(fishs_diff_after[0]) * (n + 2));
        memset(fishs_same, 0, sizeof(fishs_same));
    }
}

J tree tree de

原题如下

考察知识点

数学分析

思路分析

先观察规律叭

1
2 2 1
3 3 2 2 3 3 1
4 4 3 3 5 5 2 2 5 5 3 3 4 4 1
5 5 4 4 7 7 3 3 8 8 5 5 7 7 2 2 7 7 5 5 8 8 3 3 7 7 4 4 5 5 1

没什么规律

还是程序说话叭

初步发现可以递归求解，判断一个结点是否是父代的左孩子可以从结点左右值的大小关系判断，如果右比左大一定是左孩子，反之是右孩子

如果是左孩子，可以直接找亲本的右孩子得出下一个编号结点的值

如果是右孩子，还有两种情况

如果不在最右边，那么下一个结点的值可以通过求亲本的下一个兄弟结点的左孩子得出，而求亲本的下一个兄弟结点是又一个新问题，由此递归

如果恰好在最右边，那么下一个结点的值可以通过这个满二叉树的左右对称性，最右边结点与最左边结点的值恰好相反，由此可以通过求已知结点的对称结点的左孩子得到下一个结点

好哒TLE***

？？？

重理一下思路，目前时间复杂度应该是O(tlgn)

这个数据组数嘶，最坏情况下复杂度需要降到20次指令。好的，还是找规律，我们发现

非边缘右孩子与右兄弟结点有筝形的路径对称关系，什么意思呢，就是从右孩子到其兄弟孩子的计算路径总是可以通过一个合适的筝形（缺底一个角）路径得到

比如

     11
   12  21
13 32 23 31

这个32跟23可以沿着32->12->11->21->23的缺角筝形计算，并且对于所有正斜杆的边，结点的左值以右值为差成等差数列，反斜杠同理，于是可以进行计算，大大减少函数递归时间

换而言之，这个就是之前写的递归函数的搜索路径，只是把它的规律总结出来了而已

AC了

AC代码

#include<bits/stdc++.h>
using namespace std;

typedef struct node {
    long long left;
    long long right;
} node;

node find_next(node now) {
    long long now_left = now.left;
    long long now_right = now.right;
    node next;
    if (now.left < now.right) {
        next.left = now.right;
        next.right = now.right - now.left;
        return next;
    } else if (now.right != 1) {
        int left_distance = now_left / now_right;
        node left;
        left.left = now_left - now_right * left_distance;
        left.right = now_right;
        node top;
        top.left = left.left;
        top.right = left.right - left.left;
        next.left = top.left + top.right;
        next.right = top.right + next.left * left_distance;
        return next;
    } else {
        next.left = now.right;
        next.right = now.left + now.right;
        return next;
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        node now;
        scanf("%lld%lld", &now.left, &now.right);
        node next = find_next(now);
        printf("%lld %lld\n", next.left, next.right);
    }
    return 0;
}

Tengpaz.io

2023级算法E1练习赛

2023级软院算法第一次练习赛

测评情况

A sort

考察知识点

思路分析

AC代码

B Hope Is the Thing with Feathers

考察知识点

思路分析

AC代码

C 莫卡寻宝

考察知识点

思路分析

AC代码

D 莫卡与序列

原题如下

考察知识点

思路分析

AC代码

E 排位胜率（Easy Version）

原题如下

考察知识点

思路分析

AC代码

F 莫卡的手套

原题如下

考察知识点

思路分析

AC代码

G 莫卡和魔法图案

原题如下

考察知识点

思路分析

AC代码

H 多种口味的月饼

原题如下

考察知识点

思路分析

AC代码

I If I Can Stop One Heart From Breaking

原题如下

考察知识点

思路分析

AC代码

J tree tree de

原题如下

考察知识点

思路分析

AC代码