CSDN竞赛70期

1.小张的手速大比拼

在很久很久以前，小张找到了一颗有 N 个节点的有根树 T 。 树上的节点编号在 1 到 N 范围内。 他很快发现树上的每个节点 i 都有一个对应的整数值 V[i]。 一个老爷爷对他说，给你一个整数 X， 如果你能回答我的 M 个问题，他就给张浩扬购买一些零食。 对于每个问题 Q[i], 请你找到 在 T 中以节点 Q[i] 为根的子树中的所有节点(包括 Q[i])中， 有没有两个节点 A, B (A != B) 的值 V[A] ^ V[B] 的异或和为 X。 如果有这样的两个节点， 请你输出 YES。 否则你需要输出 NO 表示
没有节点符合上面的条件。

分析

这一题有点复杂，考试的时候考虑复杂性，先做了后面的题，之后没时间做了。赛后搜了一下，也没解决方案。这次的前10名也没有谁给出了代码，所以我说一下自己的思考

为了能够满足题目的时间复杂度要求，要先计算出每个节点为根的树是否存在A^B=X.
要从后向前计算，如果节点i为根的子树中存在，那么i的父节点也存在，如果不存在，就要计算树中是否存在。
假设有节点i，dp[i]表示是否存在这样的节点A和B，i有两个子节点i1和i2，如果dp[i1]或者dp[i2]是true,那么dp[i]就是true，否则就需要计算
如何计算树中是否存在A,B呢？我一看到异或就想到异或相关的规律，比如a^a=0,a0=a,a^-1=~a，想着找一找异或的特殊性，但是这些好像都用不上，那只能用笨办法了，遍历所有的结点，两两异或计算是否等于X。如果dp[i1]和dp[i2]都是false，就不要在i1和i2的子树内部找了，只需要找节点i和i1子树，节点i和i2子树，i1子树中的节点和i2子树的结点。输入的数据有两个数组，数组N表示节点的父节点，数组V表示节点的值，这样的输入比较方便查找每个节点的父节点，但是不好查找子节点，在计算的时候是需要不断的找子节点的，如果每次都需要遍历数组N，那肯定有很多次的重复查找，比如说计算dp[i]的时候需要找子节点i1和i2，计算i父节点的时候可能还要找i1和i2，中间的重复是很多的，因为每个节点的子节点一定是相邻的，所以需要再定义一个数组Firstchild来存放每个节点的第一个子节点的位置，其他的子节点都在这个节点的相邻后面，这样在查找子节点的时候不用每次都遍历数组N了。我在写代码的时候又想到，因为是从后向前计算dp，不需要知道父节点，只需要知道子节点就行了，所以可以直接定义一个child[n][2]数组，child[n][0]表示第一个子节点，child[n][1]表示最后一个子节点（代码中为了好写代码，表示的是最后一个子节点编号+1）
其实最开始的时候我想过根据N和V来创建一个链表结构的多叉树，后来想想也挺麻烦的，不如直接多加一个数组Firstchild。

下面是我的代码，注意：代码是后来写的，没有经过平台的测试，不能保证一定正确。如果代码有不对的地方，欢迎在评论区指正。

写完代码和测试之后，我又想可能不需要求出每个节点的dp[i],只需要求出大于等于Q中最小值的dp[i]，小于i（i的父节点）的节点没被要求计算，不用计算。

代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// // 计算树中是否有节点和i的异或和为x
bool vi_exor_tree_equal_x(int vi, int child[][2], int V[], int tree_num, int x)
{// printf("vi=%d,V[%d]=%d,x=%d\n",vi,tree_num,V[tree_num],x);if ((vi ^ V[tree_num]) == x)  // i和i的子节点异或是否为xreturn true;else{// i和i子节点的子节点异或if (child[tree_num][0] == -1)  // i的子节点没有子节点return false;else{for (int j = child[tree_num][0]; j < child[tree_num][1]; j++){if (vi_exor_tree_equal_x(vi, child,V,j,x))return true;}return false;}}
}bool tree1_exor_tree2_equal_x(int child[][2], int V[], int num1, int num2, int x)
{// tree1的根节点和tree2整个树异或if (vi_exor_tree_equal_x(V[num1],child,V,num2,x))return true;// tree1的所有节点依次和tree2整个树异或if (child[num1][0] != -1){for (int i = child[num1][0]; i < child[num1][1]; i++){if (vi_exor_tree_equal_x(V[i],child,V,num2,x))return true;}}return false;
}void calculate_dp(int child[][2], int V[], int n, int x, bool dp[])
{for (int i = n-1; i >= 0; i--){if (child[i][0] == -1)  // 没有子节点dp[i] = false;else  // 有子节点{// 遍历每个子节点int j = child[i][0];       // i的第一个子节点while (j < child[i][1] && dp[j] == false)  // j的父节点是ij++;if (j < child[i][1] && dp[j])   // 有子节点是truedp[i] = true;else{dp[i] = false; // 先设置为false// 计算子树中是否有节点和i的异或和为xfor (int k = child[i][0]; k < child[i][1]; k++){if (vi_exor_tree_equal_x(V[i],child,V,k,x)){dp[i] = true;break;}}if (dp[i]){continue;// printf("1-dp[%d]=%d\n",i,dp[i]);}// 子树与子树之间是否有节点异或和为xfor (int k = child[i][0]; k < child[i][1]; k++){for (int m = k+1; m < child[i][1]; m++){if (tree1_exor_tree2_equal_x(child, V, k, m, x)){dp[i] = true;break;}}}// printf("2-dp[%d]=%d\n",i,dp[i]);}}// printf("3-dp[%d]=%d\n",i,dp[i]);}
}int main()
{int n, x, m;scanf("%d %d %d",&n, &x, &m);int parent[n], child[n][2], V[n], Q[m];bool dp[n];for (int i = 0; i < n; i++){scanf("%d", &parent[i]);}for (int i = 0; i < n; i++){scanf("%d", &V[i]);}for (int i = 0; i < m; i++){scanf("%d", &Q[i]);}// 计算childfor (int i = 0; i < n; i++){int j = i+1;         // 子节点一定在父节点的右边while (j < n && parent[j] < (i+1))  // 输入的树编号是从1开始的j++;if (j < n && parent[j] == (i+1)){child[i][0] = j;while (j < n && parent[j] == (i+1))j++;child[i][1] = j;}elsechild[i][0] = -1;  // 没有子节点}// printf("child0:\n");// for (int i = 0; i < n; i++)// {//     printf("%d ",child[i][0]);// }// printf("\n");// printf("child1:\n");// for (int i = 0; i < n; i++)// {//     printf("%d ",child[i][1]);// }// printf("\n");calculate_dp(child,V,n,x,dp);for (int i = 0; i < m; i++){printf("%s\n",dp[Q[i]-1]? "YES" : "NO");}
}

测试用例：

6 3 6
-1 1 1 2 2 3
5 1 4 3 0 8
6 5 4 3 2 1
NO
NO
NO
NO
YES
YES

6 3 3
-1 1 1 2 2 3
5 1 4 8  0 3
3 2 1
NO
NO
YES

2.坐公交

公交上有N排凳子，每排有两个凳子，每一排的凳子宽度不一样。有一些内向和外向的人按照顺序上车。
外向的人（0）：只会选择没人的一排坐下，如果有很多排符合要求，他会选择座位宽度最小的坐下。
内向的人（1）：只会选择有人的一排坐下，如果有很多排符合要求，他会选择座位宽度最大的坐下。
数据保证存在合理。输出每个人所在的排。

分析

内向的人和外向的人的行为完全相反，对外向的人的座位做入栈操作，对内向的人做出栈操作。首先以宽度来对座位进行排序，外向的人选择没人且宽度最小的座位，第一个外向的人选择最小的座位，第二个外向的人选择第二小的座位，……。对于内向的人选择有人且宽度最大的座位，入栈的时候代表有人坐，且先入栈的宽度肯定小于后入栈的宽度，所以内向的人直接做出栈操作就可以了。

这题需要排序，排序算法有很多，最简单的是冒泡排序，但冒泡排序的时间复杂度是O(n^2)，肯定会超时，我是使用的快速排序，时间复杂度O(nlog(n))，但是快速排序是不稳定的排序，如果遇到相同的值，有可能导致顺序调换，但是题目中没有说有宽度相同的情况。还有一个归并排序，时间复杂度和快速排序相同，而且是稳定的，只是忘了怎么写了。

这一题我得了0分，很奇怪，测试用例是没问题的，而且我自己试了很多例子也没问题，但是执行代码，通过率是0。即使是使用了不稳定的快速排序，也不可能一个测试用例都没过吧，我怀疑是数据输入的格式问题，考试时，已经给我了获取输入的代码，但是代码都是错的。

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MIN(x,y) ((x)<(y)? (x):(y))
void swap(int *a, int *b) 
{int t = *a;*a = *b;*b = t;
}
void quick_sort(int a[], int l, int r, int seq[]) 
{if (l >= r)return;int i = l - 1;int j = r + 1;int base = a[(i+j)/2];while(i < j) {do i++;while(a[i] < base);do j--;while(a[j] > base);if (i < j) {swap(&a[i],&a[j]);swap(&seq[i],&seq[j]);}}quick_sort(a,l,j,seq);quick_sort(a,j+1,r,seq);
}void solution(int n, int arr[], char *personality) 
{//char flag[n] = {0};char z[n];  // 栈int top = 0;int seq[n];for (int i = 0; i < n; i++) {seq[i] = i;}quick_sort(arr,0,n-1,seq);int count = 0;for (int i = 0; i < 2*n; i++) {if (personality[i] == '0') {int num = seq[count++]+1;printf("%d",num);z[top++] = num;} else {printf("%d",z[--top]);}if (i != 2*n-1)printf(" ");}// printf("\n");
}
int main() 
{int n;scanf("%d", &n);int* arr;arr = (int*)malloc(n * sizeof(int));for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);}char *personality = (char *)malloc(2*n+1);scanf("%s", personality);// printf("%s",personality);//printf("\n");solution(n, arr, personality);return 0;
}

3.三而竭

一鼓作气再而衰三而竭。 小艺总是喜欢把任务分开做。 小艺接到一个任务，任务的总任务量是n。 第一天小艺能完成x份任务。 第二天能完成x/k。 。。。 第t天能完成x/(k^(t-1))。 小艺想知道自己第一天至少完成多少才能完成最后的任务。

分析

等比数列求和公式：sum = x*(1-(1/k)^t)/(1-1/k)
x*(1-(1/k)^t)/(1-1/k) >= n
x >= n*(1-1/k) / (1 -(1/k)^t)
当t趋向于无穷大的时候，
x >= n*(1-1/k)

但是，因为每天完成的工作量不能是小数，所以直接用n*(1-1/k)求出来的值肯定是会小于真实值的。
所以，把n*(1-1/k)作为最小值，然后递增，判断是否能完成任务。其实还有一个问题，就是真实的值和n*(1-1/k)到底相差多少呢？如果差的太多，查找起来也会比较慢，所以想到二分查找，x可取的最大值是n（第一天就完成了），最小值是n*(1-1/k)，二分查找，知道找到满足条件的最小值。
我使用的第一种方法，能够AC。

代码

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>#define IS_INT(x)   ((x)-(int)(x) < 1e-7)
#define MAX(x,y)    ((x)>(y)? (x):(y))int main()
{int n, k;int min, max;scanf("%d %d",&n, &k);// clock_t start = clock();double t = n*(1-1.0/k);if (IS_INT(t))min = t;elsemin = t+1;while(1){int sum = 0;int work = min;  // 当天的工作量while(sum < n && work > 0){sum += work;work = work / k;}if (sum >= n)break;elsemin++;}printf("%d\n",min);// clock_t end = clock();// printf("time:%lu\n",end-start);
}

4.争风吃醋的豚鼠

N个节点两两建边。 不存在3个节点相互之前全部相连。(3个节点连接成环) 最多能建立多少条边？

分析

这一题是通过找规律来计算出来的

f(1) = 0
f(2) = 1
f(3) = 2
f(4) = 4
f(5) = 6
f(6) = 9
于是我总结出：
f(n) = f(n-1) + n/2
我是当成了动态规划来解的。

后来看别人的代码，发现：
f(n) = (n + 1)/2 * (n /2)

我会总结成f(n) = f(n-1) + n/2是因为我是通过画图，每多加一个节点，是在前面的基础上增加x个边，我是在总结这个x。如果对数字更敏感的话，应该就能总结出f(n) = (n + 1)/2 * (n /2)了。

代码

#include <stdio.h>
#include <stdlib.h>void solution(int n) 
{if(n == 1) {printf("0");return;}long dp_1 = 0;  // f(n-1),f(1)long dp;        // f(n)int i = 2;while (i <= n) {dp = dp_1 + i/2;dp_1 = dp;i++;}printf("%ld",dp);
}int main() 
{int n;scanf("%d", &n);solution(n);return 0;
}