JZ DAY6总结

$DAY6$

$T1$

$超氧化钾$

作为一个化学小考只有77分的同学，小W感觉很有压力，所以他决定搞化学。今天他开始研究超氧化钾，这是一种很神奇的离子化合物，在高温下空间结构是立方体，如下图所示。有一天教黄交给了小W一个任务：根据教黄多年淘金的经验，他发现超氧化钾有一个神奇的性质就是如果一组有序的整数(x,y,z)满足z=x mod 1+x mod 2+…+x mod y，那么对于超氧化钾来说这个位置上的离子就是一个关键离子。通过用回旋加速器得到高速粒子来攻击这个离子，他就可以获得铜铝制金法的催化剂。现在教黄想知道对于一个给定的x和y对应的z值是多少。

Input
两个整数x,y。

Output
一个整数z。

Sample Input
1 1

Sample Output
0

Data Constraint
40%的数据，y<=10^5。
100%的数据，1<=x,y<=10^9。

这副图没有什么鸟用，那么简洁明了的题目，让我着实很想AC，前几次数论题的成功AC，让我坚信自己可以AC，可是事实大辣么大。常规打法，先是打了一个暴力，然后开始埋头苦干扎规律。这个规律着实不好找，我找了近个把小时才得到一个很牵强的规律。暴力分是三十分，本以为我这牵强的规律可以帮助我骗更多的分，可谁知$O(max(n,m)/2)$的时间复杂度竟然也是三十分，表示很生气，超时500ms。
考后改题，原来正解是数论分块，恰好自己不太熟悉，就算是个收获吧，让我好好地认识了一下数论分块。基本概念是这样的对于$n/i(n<=i)$的向下取整的值只有 2 ∗ n 2 * \sqrt n 2∗n ​种，且每段取值是一个连续的范围。对于左端点$L$的右端点为$N/(N/L)$，然后就可以以根号级别的时间复杂度成功AC。
对于此题为什么可以用数论分块，理由如下，首先明确一个很显而易见二点思路，对于z只用求出 ∑ i = 1 m i n ( y , x ) x m o d i \sum\limits^{min(y,x)}_{i = 1} x \ mod \ i i=1∑min(y,x)​x mod i 即可，加入$y>x$那么剩下的加上$x\ast (y-x)$即可。所以 ∑ i = 1 m i n ( x , y ) x m o d i \sum\limits^{min(x,y)}_{i = 1} x \ mod \ i i=1∑min(x,y)​x mod i的值可以分解为 ∑ i = 1 m i n ( x , y ) x − ⌊ x i ⌋ ∗ i \sum\limits^{min(x,y)}_{i = 1} x \ - \lfloor\frac{x}{i}\rfloor * i i=1∑min(x,y)​x −⌊ix​⌋∗i然后拆开得， m i n ( x , y ) ∗ x − ∑ i = 1 m i n ( x , y ) ⌊ x i ⌋ ∗ i min(x,y) * x - \sum\limits^{min(x,y)}_{i = 1}\lfloor\frac{x}{i}\rfloor * i min(x,y)∗x−i=1∑min(x,y)​⌊ix​⌋∗i，那么成功晋级成数论分块板子题。
AC Code

#include 
#define ll long longll x,y,l,r,ans,mi;ll min(ll a,ll b) {return a < b ? a : b;}int main()
{scanf("%lld%lld",&x,&y);mi = min(x,y);ans = x * mi;for (l = 1; l <= mi; l = r + 1){r = min(x / (x / l),mi);ans -= (x / l * (l + r) * (r - l + 1) / 2);}if (y > x) ans += (y - x) * x;printf("%lld",ans);return 0;
}

如此简短的代码，考场上硬是想不到。

$T2$

$艰难的选择$

Yzx已经当过多次“媒人”了。他因此获得了许多经验。例如，距Yzx观察，身高相近的人似乎比较合得来。Yzx在学校策划了一次大型的“非常男女”配对活动。对于这次活动的参与者，Yzx有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单，他让学校的所有人按照身高排成一排，然后从中选出连续的若干个人，使得这些人中男女人数相等。Yzx当然希望他能选出的人越多越好，请告诉他最多可以选出多少人来。

Input
第一行有一个正整数n，代表学校的人数。
第二行有n个用空格隔开的数，这些数只能是0或1，其中，0代表一个男生，1代表一个女生。

Output
一个非负整数，表示最长的一段男女人数相等的子序列长度（如果不存在男女人数相等的子序列输出0）。

Sample Input
9
0 1 0 0 0 1 1 0 0

Sample Output
6

Data Constraint
30%的数据，n<=100。
50%的数据，n<=1000。
100%的数据，n<=100000。

考场一看这不是水题一道吗，直接前缀和一波乱搞就可以啦。可是考场第一次打的程序竟然WA了，于是我认真捋了一遍思路，重打，思路如下。
将男孩看作$-1$，女孩看作$+1$，然后用前缀和记录下来，那么如果两个位置间的$sum$值之差为零那么就说明这段区间内是合法的，求出最长的区间即可。时间复杂度$O(nlogn+n)$，难得一道考场切的题目啊。

#include 
#include 
using namespace std;const int maxn = 1e5 + 10;
struct Node{int id,sum;
} f[maxn];
int n,ans;int max(int a,int b) {return a > b ? a : b;}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;
}bool cmp(Node a,Node b) {return a.sum == b.sum ? a.id < b.id : a.sum < b.sum;}int main()
{n = read();for (int i = 1; i <= n; i ++){f[i].id = i;f[i].sum = read();if (f[i].sum == 0) f[i].sum = f[i - 1].sum - 1; else f[i].sum = f[i - 1].sum + 1;}sort(f,f + 1 + n,cmp);for (int i = 0,j,k; i <= n; i ++){j = i;while (j + 1 <= n && f[j + 1].sum == f[i].sum) j ++;if (j != i) ans = max(ans,f[j].id - (f[i].id + 1) + 1);i = j;}printf("%d",ans);return 0;
}

$T3$

$人品问题$

网上出现了一种高科技产品——人品测试器。只要你把你的真实姓名输入进去，系统将自动输出你的人品指数。yzx不相信自己的人品为0。经过了许多研究后，yzx得出了一个更为科学的人品计算方法。这种方法的理论依据是一个非常重要的结论：人品具有遗传性。因此，一个人的人品完全由他的祖先决定。yzx提出的人品计算方法相当简单，只需要将测试对象的k个祖先的人品指数（可能为负数）加起来即可。选择哪k个祖先可以由测试者自己决定，但必须要满足这个要求：如果除自己的父母之外的某个祖先被选了，那么他的下一代必需要选（不允许跳过某一代选择更远的祖先，否则将失去遗传的意义）。非常不幸的是，yzx测试了若干次，他的人品值仍然不能为一个正数。现在yzx需要你帮助他找到选择祖先的最优方案，使得他的人品值最大。

Input
第一行是两个用空格隔开的正整数n和k，其中n代表yzx已知的家谱中共有多少人（包括yzx本身在内），k的意义参见问题描述。
第二行有n-1个用空格隔开的整数（可能为负），这些数的绝对值在2^15以内。其中，第i个数表示编号为i+1的人的人品值。我们规定，编号为1的人是yzx。
接下来n行每行有两个用空格隔开的数，其中第i行的两个数分别表示第i个人的父亲和母亲的编号。如果某个人的父亲或母亲不在这个家谱内，则在表示他的父亲或母亲的编号时用0代替。
除yzx以外的所有人都是yzx的祖先，他们都会作为父亲或母亲被描述到。每个人都不可能同时作为多个人的父亲或者是母亲。

Output
一个整数，表示yzx能够得到的最大人品值。

Sample Input
6 3
-2 3 -2 3 -1
2 3
4 5
0 6
0 0
0 0
0 0

Sample Output
4
样例说明下图显示了输入样例所描述的家谱图。括号里的数表示的是该人的人品值。
显然，选择祖先2、3、5能使yzx的人品值达到最大。这个最大值为4，表示yzx能够得到的最大人品值。

Data Constraint
50%的数据，n<=10。
100%的数据，n<=100。

感觉今天一整套题都是那么言简意赅，让人看了就想做，可是就是做不出来。这题真的熟悉得不得了。我想到了树形背包，可就是不记得怎么敲。唉，靠后翻原题，终于是想起来了。
此处设$f[i][j]$表示以$i$为根节点的树，选了$j$个点的最大人品值。转移为$f[i][j]=max(f[i][j],f[i][j-l]+f[son[i]][l])$
AC Code:

#include 
#include 
#define ll long long
using namespace std;const int maxn = 110;
struct Edge{int to,next;
} f[maxn * 4];
int n,k,cnt,head[maxn],dp[maxn][maxn];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 max(int a,int b) {return a > b ? a : b;}void add(int u,int v)
{f[++ cnt].to = v;f[cnt].next = head[u];head[u] = cnt;
}void dfs(int u)
{for (int i = head[u]; i; i = f[i].next){dfs(f[i].to);for (int j = k; j >= 1; j --){for (int l = 1; l < j; l ++)dp[u][j] = max(dp[u][j],dp[u][j - l] + dp[f[i].to][l]);}}
}int main()
{memset(dp,-0x3f,sizeof dp);dp[1][1] = 0;n = read(),k = read() + 1;for (int i = 2; i <= n; i ++) dp[i][1] = read();for (int i = 1,u,v; i <= n; i ++){u = read(),v = read();if (u) add(i,u);if (v) add(i,v);}dfs(1);printf("%d",dp[1][k]);return 0;
}

今日分数$30+100+0$唉，应该是这六天里考得最差的一次吧，真想体验一把虐场的快感，可实力不允许啊。加油加油！@Sheep*

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！