Tree IV 注意到第i层的最多有2^(i-1)个结点，并且编号都是连续的即可答题 #include<bits/stdc++.h> #define pb push_back using namespace std; typedef long long ll; const int maxn = 2e5 + 6; const int mod = 998244353; class Solution { public:     /**      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可      *      * @param n lo...

题解： 每一步最多有4种选择，并且题目保证全部卡片用光后一定会正好走到终点，那么我们直接记忆化搜索就可以dp[i][j][k][l] 表示 当前1，2，3，4卡片还剩i,j,k,l个得到的最大分数。时间复杂度为O(404040*40) 代码： #include<bits/stdc++.h> #define pb push_back #define SZ(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef vector&...

解题报告：看到 每行取数的得分 = 被取走的元素值 * 2^i，由于i是递增的。所以第一想法就是把大的留在最后，即每次取每行首尾最小的那个，但是样例二则轻易的否定这种做法。 考虑到其实每行的贡献是独立的，相当于把每次操作拆成n次操作，那么我们考虑怎么得到一行的最大值。 可以发现每次操作的区间是不断缩小的，可以看出是一个区间dp，我们让dp[i][j]为 [i j] 取完的最大值，所以dp[i][j] = max {dp[i+1][j]+a[i],dp[i][j-1]+a[j]} ;就相当于在区间[i j] 时取首还是尾。 用 __int128 #include<bits/stdc++.h...

异或操作，直接考虑如何构造x对应二进制的每一位能使 x ^ a[i] 最大。那么x的第i位为0时当前位的贡献为[l,r]内a[j]的第i位为1的个数*2^i。所以我们只需要预处理出a[i]对应二进制为的前缀1的个数，然后每次询问枚举每一位分类讨论就好了 #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define SZ(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() #define rep(i,a,b)...

B 先选出n-1种颜色C(n,n-1)=n剩下的就是n-1个不同的数放n个位置然后从n-1种颜色种选择一个作为重复的颜色 C(n-1,1)=n-1在从n个位置选择两个放重复颜色，C(n,2)最后n-2个位置为(n-2)!整理： #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define fi first #define se second #define pb push_back #define all(x) (x).begin(),(x).end() using namespac...

题解： 由于本题数据范围较小，很容易想到状态压缩Dp的方式进行模拟，我们让dp[i][S]表示第i行的勇士状态为S(将s拆成二进制位，1表示该为有勇士)时的方案数，那么最后总的答案就为 ,所以直接枚举就可以啦！注意要过滤掉其中一些非法状态，就是题目所说的那些，为了检测方便，可以将每行的状态转换为一个二进制数，直接位运算判断即可 代码 #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define fi first #define se second #define pb push_ba...

题解： 分析一下题目的每次操作，其实就是u节点选后，与其相连的点 都不能在选，然后要求选择最多的点，那么这就是一个树的最大独立集问题，我们用得dp[][]解决，并且由于题目要求S点必须选择，那么我们将点S设为根够令dp[i][0]表示i节点不选时，以i为根的子树的最大独立集，dp[i][1]则为选时，则有 代码： #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define fi first #define se second #define pb push_back using ...

题解： 很套路的一道题：由于所求的是异或之和，我们知道位运算不产生进位，所以每个数位与位之间的贡献是独立的，不想不影响，那么我们考虑按位计算对 答案的贡献即可，令pre[i][j]表示 前i个数中第j位为1的个数，那么当我们枚举所有区间的左端点i时，如果pre[i-1][j]是奇数，那么所有能对答案造成贡献的右端点r的pre[r][j]一定是偶数，反之亦然。所以，我们在令cnt[i][j]表示前i个数中,pre[i][j]为奇数的个数，但是题目还有一个限制条件就是长度必须是偶数，所以我们把cnt[i][j]表示前面与i奇偶性相同的个数，这样，当我们枚举所有区间的左端点i时，就可以O1的计算答案...

题解： 很明显的贪心题目，首先我们考虑按t2排序，因为我们先完成t2小的，那么这会比先完成t2大的留给后面人的时间更多。但是这样会出现一个问题就是 由一个项目虽然她的t2很小，但是他的t1占用了后面太多的时间，使后面又任务不能及时完成。那么这时候我们就需要给程序填加一个反悔的功能：即当我们发现一个任务不能及时完成之后，这时其实我们可以用她和前面一个比他t1大的替换一下，那么此时我们的答案数仍然不变，但是我们的时间线确减小了。 代码： #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #d...

题目描述 给出1-n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。 题解： 由于题目所给的是一个排列，即1~n每个数值出现一次，那么一个连续的子序列要想包含b只有3中情况，假设b在pos i ~ pos pos ~ j i ~ pos ~ j并且由于中位数只可以 为b，那么所有数也可以分为3类，>b <b ==b,我们把 >b 看成1 ,< b 看成-1.所以对于情况 1 2 只要从pos开始分别向前向后累加，和为0时即为一种有效情况。对于情况 3 也只需要先统计一下，左边所有和能出现的情况，然...

题解： 假设图联通，那么由于每次走两步，相当于在规定一个起点后只能走奇偶性相同的点，所以，对于每一个连通块，我们只需要01染色后，看一下有没有相同颜色连边的情况，如果有，那就说明奇偶性不同的点能够到达，也就是说，我们可以遍历整张图，如果没有，那么我们直接加一条即可，然后如果图不连通，那么首先，我们最少要多加连通块-1条边，然后如果这些连通块中有一个出现相同颜色边的情况，那么我们的只有把图联通即可，否则，则需多加一条 代码 #include <bits/stdc++.h> #define pb push_back using namespace std; typedef long ...

简单瞎搞题 题目描述 一共有 n个数，第 i 个数是 xixi 可以取 [li , ri] 中任意的一个值。，求 S 种类数。0<=li<=ri<=100 思路 由于li,ri，n范围只有100 显然可以暴力扫描所有区间中的每个值 然后dpdp[i][S] 表示 1~i个数能否组成S，但是我们发现这样的复杂度为 100100100*100 = 1e8 似乎时间有点紧张。在仔细想想其实发现dp数组只表示 0 / 1 两种状态，那么直接 利用 bitset类似状压优化就可以了 代码 #pragma GCC optimize(2) #include<bits/stdc+...

题目描述 帕秋莉掌握了一种火属性魔法由于钟爱扫雷游戏，帕秋莉把自己图书馆前的走廊看作一个一维的扫雷地图，她制造了很多烈焰，排在这条走廊内现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种对于一个格子，里面会有以下几种字符：0：这个格子没有烈焰，且其左右两个格子均没有烈焰1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰2：这个格子没有烈焰，且其左右两个格子中均有烈焰*：这个格子有烈焰？：未告诉你本格情况 题解 很明显是一道dp的题目，我们考虑它的转移方程是怎么样的。由题目里的限制 可以得到，当前位置是否为烈焰与他前一位和后一位是否为烈焰都有关，并且当我们枚举到当前位置的时候...

2017 中国大学生程序设计竞赛 女子组 hdu 6030 矩阵快速幂模板 重载结构体运算符实现 主要注意 行列式相乘不能改变顺序 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9+7; struct MUL { ll a[4][4]; MUL operator*(const MUL &k2) const{ MUL p; memset(p.a,0,sizeof p.a); for(int...