思路： ) #include using namespace std; typedef long long ll; const int maxn = 2e3 + 10; int n; char s[maxn]; int dp[maxn][maxn]; int main(){ scanf("%s", s + 1); n = strlen(s + 1); for(int i = 1; i <= n; i++){ dp[i][i] = 1; ...

  按道理是可以构造出的，构造方法如下94个0、-1、-1、-1、0、1、2、2 前100项和为0,101项为2，而且可以保证相邻两项差的绝对值小于等于1.。所以怀疑这题数据和样例有锅

感受巨水@_@ 思路最开始的思路比较暴力，直接从s出发然后干掉距离小于等于1的点，对于剩下的点构成很多连通块，我们只需求所有连通块的最大独立集合的和即可。有点懒，然后就用DP实现了。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 500000 + 10; struct edge{ int v, nex; }e[maxn << 1]; int n, head[maxn], cnt, s, dp[maxn][2]; voi...

感受思路很常规，二进制拆位算贡献，但是苦逼的我debug一下午，代码实现能力有待提高 思路 常规做法，枚举区间左端点L，如何找右端点呢？异或题，肯定要想到二进制拆位，于是，问题就简单转化为对于某一二进制位，算出这个位对答案的贡献。 贡献 = ((ll)1<<i) * (区间种数) 于是，考虑怎么算区间种数？区间有什么特性吗？显然，把区间里的每个数拆成二进制，统计第i位的值，作一个求和，如果为奇数，那么对答案有贡献，否则无贡献。于是，我们言归正传，看看此题 首先题目有两个限制条件：（1）区间长度为偶数（2）区间长度属于[l, r]其实，限制(2)很好转化，我们枚举左端点L，那么...

感受随手一画，有点难，再看看题目，原来b在数组中只有一个呀！（要是有多个，难度就加大了，主要容易T）然后，不难，简单模拟即可 思路假设,那么我们统计一组数据，pos、pos+1、...、n中小与b的个数 - 大于b的个数对于，答案怎么统计呢？p枚举pos左边的位置L，记录L到pos中大于b的个数-小与b的个数，然后这个位置对答案的贡献就是之前数据中小与b的个数 - 大于b的个数，而且也保证这是奇数长度。其实这题目也没啥讲的，就是左边枚举+右边枚举优化即枚举 + 优化 AC代码 #include <bits/stdc++.h> using namespace std; type...

感受噫，怎么这么少人过？难道很难，不如先看看再说。读完题，怎么没思路，简单想一下，如果图是连通的，那么怎样可以保证一定遍历完呢？画一画，这不是so easy吗。那如果有其他连通分量，怎么弄呢？噢噢，这样弄这样弄。恍然大悟，这不就是xx题吗？ 思路先考虑简单版问题：保证图的连通性（也就是从1遍历，可以访问任意点），怎么解决呢？多画画，就会发现，如果图中存在奇环，那么一定有一条路径使得从1经过那个奇环到达1的儿子节点。也就是说，存在奇环就保证我们既可以从1节点“走两步”，也可以从1的儿子节点“走两步”，这样显然可以遍历整张图。所以，存在奇环时，ans = 0；不存在奇环时，ans = 1（构造奇...

感受苦苦针扎，一直想不到题目有什么暗示优化的地方。做着做着把题目当成 来做，然后用树状数组优化，好不容易搞出了一个3e8的复杂度，准备测试样例时，卧槽，这求的和我做的不一样。索性放弃了，看完题解，感叹bitset优化这么牛吗？整体移动可以达到,n是Bitset容器大小 知道bitset的优秀复杂度，就可以直接愉快地状态转移了。 bitset<100> bit; bit << 5 相当于原来状态的值 + 5 #include <bits/stdc++.h> using namespace std; typedef long long ll; const i...

感受又被卡精度了，看来要理解出题组的意思。 两种求法，求解每一道题解出的概率 求解完之后，就愉快地dfs #include <bits/stdc++.h> using namespace std; typedef long long ll; double p[15]; double ans[15], a[15], b[15], c[15]; double solve(double a, double b, double c){ return 1.0 - (1.0 - a) * (1.0 - b) * (1.0 - c); //return a + (1.0 - ...

感受今天空闲下来，于是做了这道题，乍一看，这不就是拿着一个正方形在地图上跑来跑去吗？一眼题，巨水 思路很容易得出，如果一个正方形内有1，那么对答案贡献+1枚举所有正方形的位置只需要O（n * m），于是考虑如何快速check正方形内有无1。这不是很眼熟吗？二维区间前缀和，于是就快速秒到这道题目了。怎么求二维前缀和呢？太简单了，网上博客看一眼就懂了，这里就不赘述了。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1000 + 10; int n, m, k; ...

感受水题，然后被题意和各种弱智性错误恶搞我居然还会犯变量未初始化问题？ 思路很显然，找到两方的连通块分量个数，以及对应连通块大小，然后贪心取即可 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 8e2 + 10; int fa[maxn], num[maxn]; int m, tot, sum; vector<int> vec; map<int, bool> mp; char s[10][200]; void print(){ ...

感受似乎贪心就解决这个问题了，为什么当时比赛过得人这么少？ 思路首先，我们处在p位置，显然要么向左走到相邻的城市，要么向右走走到相邻的城市。有一个不会证明但观察到的结论，从这两个位置走的话，只有四种可能。可能1：一直向左走可能2：一直向右走可能3：一直向左走到第i个城市，然后再向右走到第i+1个城市，然后再向左走到第i个城市，然后再向右走到第i+1个城市...可能4：一直向右走到第i个城市，然后再向左走到第i-1个城市，然后再向右走到第i个城市，然后再向左走到第i-1个城市... 观察的结论讲实话我也不会证明，坐等明天题解 #include <bits/stdc++.h> ...

感想处理这种某一个位置会影响其相邻位置的题型原来可以这样设DP状态式我菜到真实 解题思路参考https://blog.nowcoder.net/n/c172ed50c89843218584524ea4197bcc?&toCommentId=6079660 思路其实，我觉得如果你的状态表示成这样，那么状态转移时应该SO EASY，所以，我就直接贴转移代码了 其实，是不是看到这内心有一点疑惑，为什么我们不需要考虑第i + 1位上的数字是0还是1还是2还是*还是？呢这其实也就是动态规划的思想，当我们考虑前i位时，我们并不需要关心第i+1位的情况。如果dp[i][i的状态一定正确，但i ...

感受原来换根操作是这样，虽然做的时候并不了解这个概念 思路 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 10; struct edge{ int v, nex; }e[maxn * 2]; int n, head[maxn], cnt; ll dp[maxn], num[maxn];///dp[i]表示以i为根的树的W num[i]表示以i为根的树大小 void add_edge(int u, int v){ c...

感受权值线段树模板题，随便搞一搞 思路很显然，每次往后推一个数时，只要求出已覆盖数的第k大，明显就是板子题目呀！叶子节点维护的是小与等于这个权值的有多少个，可以离散化乱搞 #include <bits/stdc++.h> #define ls o << 1 #define rs o << 1 | 1 using namespace std; typedef long long ll; const int maxn = 1e4+ 10; vector<int> vec; int a[maxn << 2];///叶子节点表示小与等于这...