题目链接：F-小苯的01背包（hard）_牛客小白月赛94   题目分类：贪心，位运算   思路：看到题目范围(2e5,1e9)，首先排除DP   我们需要选择物品子集，使得体积的按位与不超过k，价值的按位与最大。    看到按位与，可以想到应该要在数的二进制方面解出此题   按位与操作具有性质：选择的物品越多，结果的位数可能越少。        考虑二进制按位枚举，如何枚举最优？肯定是从高位到低位枚举   我们可以尝试从最高位到最低位逐位检查是否可以将该位设为1。对于每个候选值，检查是否存在物品子集，其中所有物品的价值包含该候选值，且这些物品的体积按位与结果不超过k。   若满足上述条件，则...

题目链接：E-奏绝_牛客小白月赛93   题目分类：前缀和与差分   思路：由于需要统计区间内端点不同的子区间的长度总和   先设ans[i]:区间[1,i]中的端点不同的子区间的长度总和   考虑如何求解ans[i]   我们遍历一遍1~n，设当前遍历到了第i个字符   若字符i为0，则ans[i]=前面每一个1与这个0的长度总和   考虑如何求解这个   我们发现，前面每一个1与这个0的长度总和 可以转化成 前面1的个数*i的下标-前面每个1所在的下标   所以可以设数组    pre0[i],pre1[i]:前i位数字中0/1数字之和   sum0[i],sum1[i]:前i位数字中0/...

题目链接：F-快快乐乐剪羊毛_牛客小白月赛92   题目分类：思维转换题   思路：题目要求水平向左或向右任意挪动整个羊场的草皮，计算你所能得到的羊毛价值之和的取值有多少种   一个很朴素的思路是：可以先把草皮移到最左边，让最右边草皮的右端点对准第一只羊位置下标，然后不断向右移动草皮，每移动一单位，O(n)遍历每只羊，对羊毛价值求和并存入set中（set初始插入一个0），最后答案为set的大小   但是这个时间复杂度是O()，当w大时显然超时   注意到草皮只有m块，且m*n<=1e5，如果可以把换成m就好了   我们发现，移动草皮会改变绵羊相对于草皮的位置，从而影响其价值。每个绵羊的价...

题目链接：E-来硬的_牛客小白月赛92   题目分类：常规DP题，是DP各维表示的状态设对，转移方程就可以直接出的那种   思路：看到题目里面有m个煤炭，有n个铁矿，求最小时间   发现没有魔法的时候，就是一个经典的01背包问题   设dp[i][j]=烧了i个煤炭，获得了j个铁矿时所用的最小时间   转移方程有：dp[i][j]=min(dp[i-1][j](不用第i个煤炭)，dp[i-1][j-x[i]]+y[i]（用第i个煤炭）)   最终答案为dp[n][m]   但是这一题有一个最多释放一次的魔法   所以考虑在原先的dp基础上再开一维   设dp[i][j][k]=烧了i个煤炭，获...

题目链接：G-Colorful String_牛客竞赛字符串专题班pam+manacher习题      PAM板子题      思路：所有的回文串长度好统计，manacher或者PAM都可以做，难点在于统计回文串内的字符种类   观察PAM中的增加字符的add函数的代码   // 节点：0为偶根，1为奇根。从2开始是有效节点。     int nxt[N][26];         // 类似Trie的指针     int fail[N];    &nb...

题目链接：E-[SHOI2011]双倍回文_牛客竞赛字符串专题班pam+manacher习题      仔细分析，逐个击破      思路：先分析双回文串的性质，即一个 长度为4的倍数（条件1），左右两部分相等（条件2） 且 左右两部分都为长度为偶数的回文串（条件3） 的回文串（条件4）   可以看出，当满足条件2，3，4时，条件1自动满足（这个特别明显，看不出来可以自己画一下），所以可以不用特别考虑条件1   又可以看出，当满足条件2，4时，条件3自动满足，当满足条件3，4时，条件2自动满足（这个也很明显），所以条件2，3只需要考虑其中一个即可      所以，问题从需要考虑4个条件变成了考...

题目链接：D-[POI2010]ANT-Antisymmetry_牛客竞赛字符串专题班pam+manacher习题  一道板子题的小变式   思路：先观察反对称的定义--"对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串" 先确认一点，**长度为奇数的字符串一定不可能是反对称的，因为其0和1的个数不相等，在取反之后一定与原来的不同**       现在，探究一下反对称串的性质   设原字符串s长度为4，字符为s1,s2,s3,s4，对其取反，得到1-s1,1-s2,1-s3,1-s4，将其反过来会和原串一样 即有：s1=1-s4,s2=1-s...

/*     Like a starship speeding into the night     You and I get lost in the infinite lights */ #include<bits/stdc++.h> #include<utility> #include<iostream> #include<algorithm> #include<cstdio> #include<stdio.h> #include<...

牛客周赛 Round 86--D题    链接：https://ac.nowcoder.com/acm/contest/104637/D 来源：牛客网    思路：   结论：对于任意的x,y，最多不会超过三次操作   原因：由于当a==b时，a^b==0，所以只需要第一次操作和第二次操作时，都取原先的x和y进行相同的操作（记为c和d，且c==d），那么第三次操作一定可以取c,d，作c^d，结果为0   下面为分类讨论   对于一次操作取到0：x==y（这样x^y=0）或x&y==0   对于二次操作取到0：记 x op y == a （op为某个操作），有 a&y==0 ||...

赛后复盘--对于E题只能通过33.33%的思考，线段的排序优先级问题   链接：https://ac.nowcoder.com/acm/contest/103948/E 来源：牛客网  题目描述      在数轴上，一共有 n 条线段，小红已经将所有线段都染成了红色。小紫准备至少选择一条线段，将它们都染成紫色，并且使得不存在两个红色的线段相交，也不存在两个紫色的线段相交。  小紫能成功吗？如果可以，请你帮小紫输出一个染色方案，如果不可以，请输出-1。        思路   对于每一条线段，存储其左端点l，右端点r，以及其编号index   然后开一个vector<int&gt...

链接：https://ac.nowcoder.com/acm/contest/102896/F 来源：牛客网  题目描述（简化）    有一个 n 行 m 列的二维垂直网格迷宫，我们使用 (i,j) 表示网格中从上往下数第 i 行和从左往右数第 j 列的单元格。每个方格要么是空方格 ‘.’，要么是障碍物方格 ‘#’。特别的，迷宫的边缘外视作无法被摧毁的边界。 每一个障碍物的初始耐久均为 h。方向向下的水流如果接触到障碍物，会使其下方的障碍物每秒损失 1 点耐久。当耐久为 0 时，再次造成耐久损失，则视为摧毁该障碍物。摧毁后，障碍物的位...

牛客周赛 round 82 A--F   A.夹心饼干   一个string   #include<bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; if(s[0]==s[2]) cout<<"YES"; else cout<<"NO"; return 0; } B.食堂大作战1.0   一个set求size() #include<bits/stdc++.h> using n...

F-怎么写线性SPJ_牛客周赛 Round 82   推导思路请看大佬写的这一篇：牛客周赛 Round 82 解题报告 | 珂学家_牛客博客   借鉴此思路，写一个十分简化的F题C++代码   #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; cout<<__lg(n)+1<<endl; for(int i=1;i<=n;i++){ cout<<__lg(i&(-i))+1&lt...

链接：https://ac.nowcoder.com/acm/problem/50505 来源：牛客网  题目描述      有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共N个节点，标号1至N，树根编号一定为1。 我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。      输入描述:  第一行两个数N和Q，N表示树的节点数，Q表示要保留的树枝数量。 接下来N-1行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝...