CSDN競賽70期

1.小張的手速大比拼

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

分析

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

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

下面是我的代碼，注意：代碼是后來寫的，沒有經(jīng)過平臺的測試，不能保證一定正確。如果代碼有不對的地方，歡迎在評論區(qū)指正。

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

代碼

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// // 計算樹中是否有節(jié)點和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é)點異或是否為xreturn true;else{// i和i子節(jié)點的子節(jié)點異或if (child[tree_num][0] == -1)  // i的子節(jié)點沒有子節(jié)點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é)點和tree2整個樹異或if (vi_exor_tree_equal_x(V[num1],child,V,num2,x))return true;// tree1的所有節(jié)點依次和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)  // 沒有子節(jié)點dp[i] = false;else  // 有子節(jié)點{// 遍歷每個子節(jié)點int j = child[i][0];       // i的第一個子節(jié)點while (j < child[i][1] && dp[j] == false)  // j的父節(jié)點是ij++;if (j < child[i][1] && dp[j])   // 有子節(jié)點是truedp[i] = true;else{dp[i] = false; // 先設(shè)置為false// 計算子樹中是否有節(jié)點和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]);}// 子樹與子樹之間是否有節(jié)點異或和為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;         // 子節(jié)點一定在父節(jié)點的右邊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;  // 沒有子節(jié)點}// 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排凳子，每排有兩個凳子，每一排的凳子寬度不一樣。有一些內(nèi)向和外向的人按照順序上車。
外向的人（0）：只會選擇沒人的一排坐下，如果有很多排符合要求，他會選擇座位寬度最小的坐下。
內(nèi)向的人（1）：只會選擇有人的一排坐下，如果有很多排符合要求，他會選擇座位寬度最大的坐下。
數(shù)據(jù)保證存在合理。輸出每個人所在的排。

分析

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

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

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

代碼

#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ù)分開做。 小藝接到一個任務(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)
當t趨向于無窮大的時候，
x >= n*(1-1/k)

但是，因為每天完成的工作量不能是小數(shù)，所以直接用n*(1-1/k)求出來的值肯定是會小于真實值的。
所以，把n*(1-1/k)作為最小值，然后遞增，判斷是否能完成任務(wù)。其實還有一個問題，就是真實的值和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個節(jié)點兩兩建邊。 不存在3個節(jié)點相互之前全部相連。(3個節(jié)點連接成環(huán)) 最多能建立多少條邊？

分析

這一題是通過找規(guī)律來計算出來的

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
我是當成了動態(tài)規(guī)劃來解的。

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

我會總結(jié)成f(n) = f(n-1) + n/2是因為我是通過畫圖，每多加一個節(jié)點，是在前面的基礎(chǔ)上增加x個邊，我是在總結(jié)這個x。如果對數(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;
}