CSDN競(jìng)賽70期

1.小張的手速大比拼

在很久很久以前，小張找到了一顆有 N 個(gè)節(jié)點(diǎn)的有根樹(shù) T 。 樹(shù)上的節(jié)點(diǎn)編號(hào)在 1 到 N 范圍內(nèi)。 他很快發(fā)現(xiàn)樹(shù)上的每個(gè)節(jié)點(diǎn) i 都有一個(gè)對(duì)應(yīng)的整數(shù)值 V[i]。 一個(gè)老爺爺對(duì)他說(shuō)，給你一個(gè)整數(shù) X， 如果你能回答我的 M 個(gè)問(wèn)題，他就給張浩揚(yáng)購(gòu)買(mǎi)一些零食。 對(duì)于每個(gè)問(wèn)題 Q[i], 請(qǐng)你找到 在 T 中以節(jié)點(diǎn) Q[i] 為根的子樹(shù)中的所有節(jié)點(diǎn)(包括 Q[i])中， 有沒(méi)有兩個(gè)節(jié)點(diǎn) A, B (A != B) 的值 V[A] ^ V[B] 的異或和為 X。 如果有這樣的兩個(gè)節(jié)點(diǎn)， 請(qǐng)你輸出 YES。 否則你需要輸出 NO 表示
沒(méi)有節(jié)點(diǎn)符合上面的條件。

分析

這一題有點(diǎn)復(fù)雜，考試的時(shí)候考慮復(fù)雜性，先做了后面的題，之后沒(méi)時(shí)間做了。賽后搜了一下，也沒(méi)解決方案。這次的前10名也沒(méi)有誰(shuí)給出了代碼，所以我說(shuō)一下自己的思考

為了能夠滿足題目的時(shí)間復(fù)雜度要求，要先計(jì)算出每個(gè)節(jié)點(diǎn)為根的樹(shù)是否存在A^B=X.
要從后向前計(jì)算，如果節(jié)點(diǎn)i為根的子樹(shù)中存在，那么i的父節(jié)點(diǎn)也存在，如果不存在，就要計(jì)算樹(shù)中是否存在。
假設(shè)有節(jié)點(diǎn)i，dp[i]表示是否存在這樣的節(jié)點(diǎn)A和B，i有兩個(gè)子節(jié)點(diǎn)i1和i2，如果dp[i1]或者dp[i2]是true,那么dp[i]就是true，否則就需要計(jì)算
如何計(jì)算樹(shù)中是否存在A,B呢？我一看到異或就想到異或相關(guān)的規(guī)律，比如a^a=0,a0=a,a^-1=~a，想著找一找異或的特殊性，但是這些好像都用不上，那只能用笨辦法了，遍歷所有的結(jié)點(diǎn)，兩兩異或計(jì)算是否等于X。如果dp[i1]和dp[i2]都是false，就不要在i1和i2的子樹(shù)內(nèi)部找了，只需要找節(jié)點(diǎn)i和i1子樹(shù)，節(jié)點(diǎn)i和i2子樹(shù)，i1子樹(shù)中的節(jié)點(diǎn)和i2子樹(shù)的結(jié)點(diǎn)。輸入的數(shù)據(jù)有兩個(gè)數(shù)組，數(shù)組N表示節(jié)點(diǎn)的父節(jié)點(diǎn)，數(shù)組V表示節(jié)點(diǎn)的值，這樣的輸入比較方便查找每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，但是不好查找子節(jié)點(diǎn)，在計(jì)算的時(shí)候是需要不斷的找子節(jié)點(diǎn)的，如果每次都需要遍歷數(shù)組N，那肯定有很多次的重復(fù)查找，比如說(shuō)計(jì)算dp[i]的時(shí)候需要找子節(jié)點(diǎn)i1和i2，計(jì)算i父節(jié)點(diǎn)的時(shí)候可能還要找i1和i2，中間的重復(fù)是很多的，因?yàn)槊總€(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)一定是相鄰的，所以需要再定義一個(gè)數(shù)組Firstchild來(lái)存放每個(gè)節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)的位置，其他的子節(jié)點(diǎn)都在這個(gè)節(jié)點(diǎn)的相鄰后面，這樣在查找子節(jié)點(diǎn)的時(shí)候不用每次都遍歷數(shù)組N了。我在寫(xiě)代碼的時(shí)候又想到，因?yàn)槭菑暮笙蚯坝?jì)算dp，不需要知道父節(jié)點(diǎn)，只需要知道子節(jié)點(diǎn)就行了，所以可以直接定義一個(gè)child[n][2]數(shù)組，child[n][0]表示第一個(gè)子節(jié)點(diǎn)，child[n][1]表示最后一個(gè)子節(jié)點(diǎn)（代碼中為了好寫(xiě)代碼，表示的是最后一個(gè)子節(jié)點(diǎn)編號(hào)+1）
其實(shí)最開(kāi)始的時(shí)候我想過(guò)根據(jù)N和V來(lái)創(chuàng)建一個(gè)鏈表結(jié)構(gòu)的多叉樹(shù)，后來(lái)想想也挺麻煩的，不如直接多加一個(gè)數(shù)組Firstchild。

下面是我的代碼，注意：代碼是后來(lái)寫(xiě)的，沒(méi)有經(jīng)過(guò)平臺(tái)的測(cè)試，不能保證一定正確。如果代碼有不對(duì)的地方，歡迎在評(píng)論區(qū)指正。

寫(xiě)完代碼和測(cè)試之后，我又想可能不需要求出每個(gè)節(jié)點(diǎn)的dp[i],只需要求出大于等于Q中最小值的dp[i]，小于i（i的父節(jié)點(diǎn)）的節(jié)點(diǎn)沒(méi)被要求計(jì)算，不用計(jì)算。

代碼

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// // 計(jì)算樹(shù)中是否有節(jié)點(diǎn)和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的子節(jié)點(diǎn)異或是否為xreturn true;else{// i和i子節(jié)點(diǎn)的子節(jié)點(diǎn)異或if (child[tree_num][0] == -1)  // i的子節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)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的根節(jié)點(diǎn)和tree2整個(gè)樹(shù)異或if (vi_exor_tree_equal_x(V[num1],child,V,num2,x))return true;// tree1的所有節(jié)點(diǎn)依次和tree2整個(gè)樹(shù)異或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)  // 沒(méi)有子節(jié)點(diǎn)dp[i] = false;else  // 有子節(jié)點(diǎn){// 遍歷每個(gè)子節(jié)點(diǎn)int j = child[i][0];       // i的第一個(gè)子節(jié)點(diǎn)while (j < child[i][1] && dp[j] == false)  // j的父節(jié)點(diǎn)是ij++;if (j < child[i][1] && dp[j])   // 有子節(jié)點(diǎn)是truedp[i] = true;else{dp[i] = false; // 先設(shè)置為false// 計(jì)算子樹(shù)中是否有節(jié)點(diǎn)和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]);}// 子樹(shù)與子樹(shù)之間是否有節(jié)點(diǎn)異或和為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]);}// 計(jì)算childfor (int i = 0; i < n; i++){int j = i+1;         // 子節(jié)點(diǎn)一定在父節(jié)點(diǎn)的右邊while (j < n && parent[j] < (i+1))  // 輸入的樹(shù)編號(hào)是從1開(kāi)始的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;  // 沒(méi)有子節(jié)點(diǎn)}// 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");}
}

測(cè)試用例：

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排凳子，每排有兩個(gè)凳子，每一排的凳子寬度不一樣。有一些內(nèi)向和外向的人按照順序上車(chē)。
外向的人（0）：只會(huì)選擇沒(méi)人的一排坐下，如果有很多排符合要求，他會(huì)選擇座位寬度最小的坐下。
內(nèi)向的人（1）：只會(huì)選擇有人的一排坐下，如果有很多排符合要求，他會(huì)選擇座位寬度最大的坐下。
數(shù)據(jù)保證存在合理。輸出每個(gè)人所在的排。

分析

內(nèi)向的人和外向的人的行為完全相反，對(duì)外向的人的座位做入棧操作，對(duì)內(nèi)向的人做出棧操作。首先以寬度來(lái)對(duì)座位進(jìn)行排序，外向的人選擇沒(méi)人且寬度最小的座位，第一個(gè)外向的人選擇最小的座位，第二個(gè)外向的人選擇第二小的座位，……。對(duì)于內(nèi)向的人選擇有人且寬度最大的座位，入棧的時(shí)候代表有人坐，且先入棧的寬度肯定小于后入棧的寬度，所以內(nèi)向的人直接做出棧操作就可以了。

這題需要排序，排序算法有很多，最簡(jiǎn)單的是冒泡排序，但冒泡排序的時(shí)間復(fù)雜度是O(n^2)，肯定會(huì)超時(shí)，我是使用的快速排序，時(shí)間復(fù)雜度O(nlog(n))，但是快速排序是不穩(wěn)定的排序，如果遇到相同的值，有可能導(dǎo)致順序調(diào)換，但是題目中沒(méi)有說(shuō)有寬度相同的情況。還有一個(gè)歸并排序，時(shí)間復(fù)雜度和快速排序相同，而且是穩(wěn)定的，只是忘了怎么寫(xiě)了。

這一題我得了0分，很奇怪，測(cè)試用例是沒(méi)問(wèn)題的，而且我自己試了很多例子也沒(méi)問(wèn)題，但是執(zhí)行代碼，通過(guò)率是0。即使是使用了不穩(wěn)定的快速排序，也不可能一個(gè)測(cè)試用例都沒(méi)過(guò)吧，我懷疑是數(shù)據(jù)輸入的格式問(wèn)題，考試時(shí)，已經(jīng)給我了獲取輸入的代碼，但是代碼都是錯(cuò)的。

代碼

#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.三而竭

一鼓作氣再而衰三而竭。 小藝總是喜歡把任務(wù)分開(kāi)做。 小藝接到一個(gè)任務(wù)，任務(wù)的總?cè)蝿?wù)量是n。 第一天小藝能完成x份任務(wù)。 第二天能完成x/k。 。。。 第t天能完成x/(k^(t-1))。 小藝想知道自己第一天至少完成多少才能完成最后的任務(wù)。

分析

等比數(shù)列求和公式：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)
當(dāng)t趨向于無(wú)窮大的時(shí)候，
x >= n*(1-1/k)

但是，因?yàn)槊刻焱瓿傻墓ぷ髁坎荒苁切?shù)，所以直接用n*(1-1/k)求出來(lái)的值肯定是會(huì)小于真實(shí)值的。
所以，把n*(1-1/k)作為最小值，然后遞增，判斷是否能完成任務(wù)。其實(shí)還有一個(gè)問(wèn)題，就是真實(shí)的值和n*(1-1/k)到底相差多少呢？如果差的太多，查找起來(lái)也會(huì)比較慢，所以想到二分查找，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;  // 當(dāng)天的工作量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.爭(zhēng)風(fēng)吃醋的豚鼠

N個(gè)節(jié)點(diǎn)兩兩建邊。 不存在3個(gè)節(jié)點(diǎn)相互之前全部相連。(3個(gè)節(jié)點(diǎn)連接成環(huán)) 最多能建立多少條邊？

分析

這一題是通過(guò)找規(guī)律來(lái)計(jì)算出來(lái)的

f(1) = 0
f(2) = 1
f(3) = 2
f(4) = 4
f(5) = 6
f(6) = 9
于是我總結(jié)出：
f(n) = f(n-1) + n/2
我是當(dāng)成了動(dòng)態(tài)規(guī)劃來(lái)解的。

后來(lái)看別人的代碼，發(fā)現(xiàn)：
f(n) = (n + 1)/2 * (n /2)

我會(huì)總結(jié)成f(n) = f(n-1) + n/2是因?yàn)槲沂峭ㄟ^(guò)畫(huà)圖，每多加一個(gè)節(jié)點(diǎn)，是在前面的基礎(chǔ)上增加x個(gè)邊，我是在總結(jié)這個(gè)x。如果對(duì)數(shù)字更敏感的話，應(yīng)該就能總結(jié)出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;
}