D A Y 7 DAY 7 DAY7
T 1 T1 T1
改 造 二 叉 树 改造二叉树 改造二叉树
小Y在学树论时看到了有关二叉树的介绍:在计算机科学中,二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子”。二叉树被用作二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树。
什么是二叉搜索树呢?二叉搜索树首先是一棵二叉树。设key[p]表示结点p上的数值。对于其中的每个结点p,若其存在左孩子lch,则key[p]>key[lch];若其存在右孩子rch,则key[p]<key[rch];注意,本题中的二叉搜索树应满足对于所有结点,其左子树中的key小于当前结点的key,其右子树中的key大于当前结点的key。
小Y与他人讨论的内容则是,现在给定一棵二叉树,可以任意修改结点的数值。修改一个结点的数值算作一次修改,且这个结点不能再被修改。若要将其变成一棵二叉搜索树,且任意时刻结点的数值必须是整数(可以是负整数或0),所要的最少修改次数。
相信这一定难不倒你!请帮助小Y解决这个问题吧。
Input
第一行一个正整数n表示二叉树结点数。结点从1~n进行编号。
第二行n个正整数用空格分隔开,第i个数ai表示结点i的原始数值。
此后n - 1行每行两个非负整数fa, ch,第i + 2行描述结点i + 1的父亲编号fa,以及父子关系ch,(ch = 0 表示i + 1为左儿子,ch = 1表示i + 1为右儿子)。
结点1一定是二叉树的根。
Output
仅一行包含一个整数,表示最少的修改次数。
Sample Input
3
2 2 2
1 0
1 1
Sample Output
2
Data Constraint
20 % :n <= 10 , ai <= 100
40 % :n <= 100 , ai <= 200
60 % :n <= 2000
100 % :n <= 10 ^ 5 , ai < 2 ^ 31.
考场将左右子树错看成左右儿子,害的爆零,最后随意打了个无厘头贪心。考场就已经想到了,按照某种顺序将其转换成一个序列,然后求最长上升子序列之类的。可是由于审题有误,硬是不知道怎么转换成队列。考完试经人指点,看清楚题后,这是个显然的中序遍历,然后再求LIS。可是有个细节考场没有想到,就是只能取整数。比方说,你得到的中序遍历的序列是1 2 2 3,本来ans应该为1,可是因为不能取小数所以此题需要对于每个 a i a_i ai减去一个 i i i,然后求最长不下降子序列。至于原因,以下是证明,若想满足题目条件那么序列一定是 a 1 , a 1 + 1 , a 1 + 2 … … a n + n − 1 a_1,a_1 +1,a_1 + 2……a_n + n - 1 a1,a1+1,a1+2……an+n−1那么只要在每项都减去一个 i i i,然后改为求最长不下降子序列。这里应该比较显然吧。
AC Code:
#include <cstdio> using namespace std; const int maxn = 1e5 + 10; int n,v[maxn],son[maxn][2],dfn[maxn],cnt = 0,q[maxn],len = 0; int read() {
int x = 0,w = 1; char ch = getchar(); while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;ch = getchar();} while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';ch = getchar();} return x * w; } void dfs(int x) {
if (son[x][0]) dfs(son[x][0]); dfn[++ cnt] = v[x]; if (son[x][1]) dfs(son[x][1]); } int find(int x) {
int l = 1,r = len; while (l < r) {
int mid = (l + r) >> 1; if (q[mid] > x) r = mid; else l = mid + 1; } return l; } int main() {
n = read(); for (int i = 1; i <= n; i ++) v[i] = read(); for (int i = 2,fa,ch; i <= n; i ++) fa = read(),ch = read(),son[fa][ch] = i; dfs(1); for (int i = 1; i <= n; i ++) dfn[i] -= i; q[0] = -0x3f3f3f3f; for (int i = 1; i <= n; i ++) {
if (dfn[i] >= q[len]) q[++ len] = dfn[i]; else q[find(dfn[i])] = dfn[i]; } printf("%d",n - len); return 0; }
讯享网
感觉这是一道不错的题目,也许对于以后的类似题目会有较强的借鉴价值。
T 2 T2 T2
数 字 对 数字对 数字对
小H是个善于思考的学生,现在她又在思考一个有关序列的问题。
她的面前浮现出一个长度为n的序列{ai},她想找出一段区间[L, R](1 <= L <= R <= n)。
这个特殊区间满足,存在一个k(L <= k <= R),并且对于任意的i(L <= i <= R),ai都能被ak整除。这样的一个特殊区间 [L, R]价值为R - L。
小H想知道序列中所有特殊区间的最大价值是多少,而有多少个这样的区间呢?这些区间又分别是哪些呢?你能帮助她吧。
Input
第一行,一个整数n.
第二行,n个整数,代表ai.
Output
第一行两个整数,num和val,表示价值最大的特殊区间的个数以及最大价值。
第二行num个整数,按升序输出每个价值最大的特殊区间的L.
Sample Input1
5
4 6 9 3 6
Sample Output1
1 3
2
Sample Input2
5
2 3 5 7 11
Sample Output2
5 0
1 2 3 4 5
Data Constraint
30%: 1 <= n <= 30 , 1 <= ai <= 32
60%: 1 <= n <= 3000 , 1 <= ai <= 1024
80%: 1 <= n <= , 1 <= ai <=
100%: 1 <= n <= , 1 <= ai < 2 ^ 31
这道题明明不难,可我就是不知道为什么考场上一顿乱搞,怎么想怎么错,然后最后保险起见交了一个暴力30分。心态都炸了,直接自闭。考场我想到了求区间最小值,然后看一下是否能被每个数整除。然而考完试,看到题解茅塞顿开。这不就是比较每个区间的最小值和gcd是否相等吗。然后就是用 R M Q RMQ RMQ,这题也让我很好地巩固了这个算法。
AC Code:
讯享网#include <cstdio> using namespace std; const int maxn = 5e5 + 10; int n,mi[maxn][50],gd[maxn][50],log[maxn],l,r,cnt,ans[maxn],res; int read() {
int x = 0,w = 1; char ch = getchar(); while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;ch = getchar();} while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';ch = getchar();} return x * w; } int min(int a,int b) {
return a < b ? a : b;} int gcd(int a,int b) {
if (!b) return a; else return gcd(b,a % b); } bool query(int l,int r) {
int k = log[r - l + 1]; return min(mi[l][k],mi[r - (1 << k) + 1][k]) == gcd(gd[l][k],gd[r - (1 << k) + 1][k]); } void check(int x) {
int k = log[x]; for (int i = 1; i + x - 1<= n; i ++) if (query(i,i + x - 1)) ans[++ cnt] = i; } int main() {
n = read(); log[0] = -1; for (int i = 1; i <= n; i ++) log[i] = log[i >> 1] + 1,mi[i][0] = gd[i][0] = read(); for (int j = 1; j <= 25; j ++) for (int i = 1; i + (1 << j) - 1 <= n; i ++) mi[i][j] = min(mi[i][j - 1],mi[i + (1 << (j - 1))][j - 1]), gd[i][j] = gcd(gd[i][j - 1],gd[i + (1 << (j - 1))][j - 1]); l = 1,r = ; while (l <= r) {
int mid = (l + r) >> 1; cnt = 0; check(mid); if (cnt) res = mid,l = mid + 1; else r = mid - 1; } cnt = 0; check(res); printf("%d %d\n",cnt,res - 1); for (int i = 1; i <= cnt; i ++) printf("%d ",ans[i]); return 0; }
感觉自己码风还是阔以的。
T 3 T3 T3
战 争 游 戏 战争游戏 战争游戏



Sample Input
7 9
1 2
1 3
1 4
1 5
1 6
1 7
2 3
4 5
6 7
Sample Output
18
6
6
6
6
6
6
Data Constraint

前两题的自闭让我看到这题的时候时间仅剩半小时,并且还一脸懵逼。不过我大概推了点思路,和考后的正解有几分相似。 这题基本就是一个割点的板子题,可是我不熟悉模板,因此想不到正解。统计答案的时候注意一下即可。
AC Code:
#include <cstdio> using namespace std; const int maxn = 5e4 + 10; const int maxm = 1e5 + 10; struct Node{
int to,next; } f[maxm << 1]; int n,m,head[maxn],dfn[maxn],low[maxn],ans[maxn],cnt,size[maxn]; bool tre[maxn]; void add(int u,int v) {
f[++ cnt].to = v; f[cnt].next = head[u]; head[u] = cnt; } int read() {
int x = 0,w = 1; char ch = getchar(); while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;ch = getchar();} while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';ch = getchar();} return x * w; } int min(int a,int b) {
return a < b ? a : b;} void tarjan(int u,int fa) {
int sum = 0,a = 0,b = 0; dfn[u] = low[u] = ++ cnt; for (int i = head[u],v; i; i = f[i].next) {
v = f[i].to; if (v == fa) continue; tre[v] = 0; if (!dfn[v]) {
tarjan(v,u); low[u] = min(low[u],low[v]); tre[v] = 1; size[u] += size[v]; if (dfn[u] <= low[v]) sum += size[v]; } low[u] = min(low[u],dfn[v]); } for (int i = head[u],v; i; i = f[i].next) {
v = f[i].to; if (dfn[u] > low[v] || !tre[v]) continue; a += (sum - size[v]) * size[v]; b += (n - sum - 1) * size[v]; } ans[u] = a / 2 + b + n - 1; } int main() {
n = read(),m = read(); for (int i = 1,u,v; i <= m; i ++) u = read(),v = read(),add(u,v),add(v,u); for (int i = 1; i <= n; i ++) size[i] = 1; cnt = 0; tarjan(1,0); for (int i = 1; i <= n; i ++) printf("%d\n",ans[i]); return 0; }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/115733.html