P1040[NOIP2003提高组]加分二叉树-洛谷|计算机科学教育新生态(luogu.com.cn)题意：给你一颗中序遍历为1到n的二叉树，和每个节点的val。树的值=左子树的值×右子树的值+根的val，空树值为1，求整个树最大值和这个值树的前序遍历。题解：区间dp。dp[l][r]表示最大值，root[l][r]表示最大值的根，枚举区间然后枚举根，根据题目中的计算公式搞最大值。 树形dp。一样的dp[l][r]表示子树罢了。 多想想，一步步讨论就好了，关键是找能做出答案的状态表示再想转移方程。int n,a[N],dp[N][N],rt[N][N];void pre_ans(int l
位运算题目背景题目由daiyulong20120222创作（me）并由QBW1117完善以及数据。题目描述给定两个数\(x,y\)，在给定一个位运算符号\(c\)。请你列出\(x,y\)进行\(c\)位运算是的算数竖式式。注：竖式这么列：显示出两个数的完整二进制，包括前导零。32个'-'。显示出\(ans\)，包括前导零。位运算符号可能是：&|^输入格式三个整数\(x,y,c\)同题意输出格式竖式结果样例#1样例输入#13221&样例输出#10000000000000000000000000010000000000000000000000000000000010101-------------
有线电视网题目描述某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。输入格式输入文件的第一行包含两个用空格隔开的整数\(N\)和\(M\)，其中\(2\leN\le3000\)，\(1
原题链接第一步对于学过差分的人应该不难想定义差分数组$dis\quads.t.\quaddis[i]=a[i]-a[i-1]$那么不难发现问题一只要让\(dis[2]...dis[n]\)中全部为\(0\)即可区间\([l,r]\)加一操作在差分数组中意味着\(dis[l]=dis[l]+1,dis[r+1]=dis[r+1]-1\)即在差分数组中每次选取\((x,y),dis[x]=dis[x]+1,dis[y]=dis[y]-1\)注意这里\(x,y\)可以选取\(1...n+1\)减一同理最后要使\(dis[2]...dis[n]\)全为0,首先在\(dis[2]...dis[n]\)选
Luogu链接：上帝造题的七分钟2/花神游历各国${\scr\color{ForestGreen}{\text{Solution}}}$题目大意支持两种操作：区间开方（向下取整）区间求和分析发现线段树容易实现区间求和，考虑区间开方操作其实并没有什么思路我们发现了一个很显而易见神奇的事情,如果对一个正整数进行无限多的开方且下取整操作，最后这个数一定会变成$1$然后用计算器计算一下，发现$1$~$10^{12}$里的一个数，最多开方$6$次，就能变成$1$所以一共最多只用修改$6\timesn$次，发现这是可以承受的所以就很简单啦！维护区间最大值，如果区间内所有数都小于等于$1$，就跳过这段区间如
Luogu链接：上帝造题的七分钟2/花神游历各国${\scr\color{ForestGreen}{\text{Solution}}}$题目大意支持两种操作：区间开方（向下取整）区间求和分析发现线段树容易实现区间求和，考虑区间开方操作其实并没有什么思路我们发现了一个很显而易见神奇的事情,如果对一个正整数进行无限多的开方且下取整操作，最后这个数一定会变成$1$然后用计算器计算一下，发现$1$~$10^{12}$里的一个数，最多开方$6$次，就能变成$1$所以一共最多只用修改$6\timesn$次，发现这是可以承受的所以就很简单啦！维护区间最大值，如果区间内所有数都小于等于$1$，就跳过这段区间如
