题意看了好久才明白(:з」∠)给一个序列a[],要求一个不会递减的数组b[]，并且b要满足|a[i]-b[i]|尽量小 用二分找a与b的差值如果差值是x如果a[i]>=b[i-1],那b[i]=max(b[i-1],a[i]-x)如果a[i]<b[i-1]-x,那差值x就不成立其他情况就可以让b[i]=b[i-1] #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include ...

推导一下f的式子所以用dp[l][r]来表示区间l,r的答案就可以得到 dp[l][r]=dp[l][r-1] dp[l+1][r] #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.141...

用dfs序来存这个树，然后来进行加权值和查询操作因为要添加节点，所以先提前把节点都算上，再在最后把多加的值给减去 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.1415927 #defin...

n最大21个，直接dfs用一个数组来保存装箱的货物dfs的时候判断当前货物能不能放到箱子里在dfs前先从大到小排序一下，因为先放大的肯定是最优的方案 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define p...

尺取法用一个数组来记录颜色，先固定左边，右移右边的范围，如果满足条件，再把左边的范围缩小，来找出最小的区间 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.1415927 #define i...

推出前几项为1,5,11,36 ，直接用oeis找出规律(:з」∠)a(n) = a(n-1) + 5*a(n-2) + a(n-3) - a(n-4)因此，可以用矩阵快速幂来算[a(5),a(4),a(3),a(2)] = [a(4),a(3),a(2),a(1)] * #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include &lt...

因为行和列有不同的划分，所以要分别处理行和列每次输入两个人的坐标后，判断是在行还是列进行划分，在这一行(列)进行计数最后按照计数的大小排序一下即可因为输出要按照从小到大，所以再对序号进行一次排序 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define...

在最短路上进行一些改变将原本的dis[n] 改为dis[n][i] (i为天数然后用dijkstra，在计算的时候把天数算上去 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.141592...

做树形dp，dp[i][j]表示根为i的节点，连通块为j时的方案数在处理的时候有两种情况断开当前节点和儿子节点，那么直接将儿子节点的所有方案乘上当前节点的方案就行了如果不断开，那就需要合并，假设当前节点有p个连通块，儿子节点有q个那么dp[u][p+q]+=dp[u][p]*dp[v][q] #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #inc...

用二进制模拟行的选择，然后从大到小选列比如1010就是第2和4行被选中这样枚举，如果这一行被选，就加上这一行的值没有选中的就计算列的和，从大到小再选列即可 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #defin...

用dp来做，dp[i][j]表示第i天买j个糖果的最小值转移方程就可以写成dp[i][j]=min(dp[i][j],dp[i-1][k]+sum[i][j-k]+(j-k)(j-k)) k的值从i-1到(i-1)m #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cm...

先不看线缆，会发现，直接用lca求最短路就行了加上线缆，就多加一个判断即可比如询问x到y，线缆是j到k在dis(x,y)，dis(x,j)+dis(k,y)，dis(x,k)+dis(j,y)这三个中取最小 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #...

要让异或后的值尽量大，那就应该让两个数的对于位置的值尽量不一样从l，r的最高位开始看，如果相同，那异或之后就是0了，因此直接不考虑继续往后面的位置看，当他们不一样的时候，一定是l当前位为0，r当前为1假如当前是第i位，那么l一定小于2^i,并且之后的每一位，都可以在异或后得到1所以，直接把l，r异或，然后将每一位都改成1就是最终答案了 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #incl...

因为要求所有路径的异或和，而异或又有个特殊性质a xor a =0因此只需要求每个点在最短路径上的出现次数可以通过计算与点相连的边的经过次数来计算点的次数 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #defin...