怎样在网站上做营业执照公示,青岛网站建设服务平台,陕西网络推广维护,wordpress拖曳组件CSDN竞赛70期 CSDN竞赛70期1.小张的手速大比拼分析代码 2.坐公交分析代码 3.三而竭分析代码 4.争风吃醋的豚鼠分析代码 CSDN竞赛70期
1.小张的手速大比拼
在很久很久以前#xff0c;小张找到了一颗有 N 个节点的有根树 T 。 树上的节点编号在 1 到 N 范围内。 他很快发现树上… CSDN竞赛70期 CSDN竞赛70期1.小张的手速大比拼分析代码 2.坐公交分析代码 3.三而竭分析代码 4.争风吃醋的豚鼠分析代码 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^BX. 要从后向前计算如果节点i为根的子树中存在那么i的父节点也存在如果不存在就要计算树中是否存在。 假设有节点idp[i]表示是否存在这样的节点A和Bi有两个子节点i1和i2如果dp[i1]或者dp[i2]是true,那么dp[i]就是true否则就需要计算 如何计算树中是否存在A,B呢我一看到异或就想到异或相关的规律比如aa0,a0a,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]小于ii的父节点的节点没被要求计算不用计算。
代码
#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 k1; 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 i1; // 子节点一定在父节点的右边while (j n parent[j] (i1)) // 输入的树编号是从1开始的j;if (j n parent[j] (i1)){child[i][0] j;while (j n parent[j] (i1))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
YES6 3 3
-1 1 1 2 2 3
5 1 4 8 0 3
3 2 1
NO
NO
YES2.坐公交
公交上有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[(ij)/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,j1,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*n1);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 t1;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.hvoid 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;
}
