题意：月月熟知华华搭讪的规则。华华想与某个小姐姐搭讪，当且仅当小姐姐的昵称是他的昵称的子序列。为了方便，华华和小姐姐的昵称只由小写字母构成。为了更加方便，保证小姐姐的昵称长度不会比华华的长。现在月月要快速的判断出哪些推荐好友要删掉，因为华华快回来了，时间紧迫，月月有点手忙脚乱，所以你赶紧写个程序帮帮她吧！思路：序列自动机？ #include<bits/stdc++.h> using namespace std; map<char,int>mp; const int N=1000010; int dp[N][27]; string s; int n,m; bool che...

链接题意：Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权 wi 现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。定义删除一条边的代价为这条边的边权，现在 Rinne 想知道完成这个游戏的最小的代价，这样她就能轻松到达 rk1 了！作为回报，她会让你的排名上升一定的数量。思路：树形dp 用边权和子树的消耗取min 然后加到父节点上。 #include<bits/stdc++.h> using name...

https://ac.nowcoder.com/acm/contest/82/B题意m次询问，询问其中最少有多少段数的和小于等于k题解：其实就是st表的运用吧，但很多边界我还是不大清楚，不过可以无脑便利整个数组写，因为跳出去的地方都是会被变为0，我们不跳就可以啦，然后如果其中区间有大于k的val我们拿个前缀来判断即可，即upper[r]-upper[l-1]如果大于0就是不存在的。 #include<bits/stdc++.h> using namespace std; const int N=1000010; #define int long long int st[N][21]...

链接：https://ac.nowcoder.com/acm/problem/13331题意：q次询问求v一定在u到根的路径上，问u到v这条树链上有多少个大于c的递增数，意思就是从u开始出发，碰到一个比当前数大的数就要+1，初始值为c。q<=1e5题解：倍增，f[u][i]代表从u出发走2^i到达的点，转移还是蛮简单的，i从小到大枚举，f[u][i]=f[f[u][i-1]][i-1]那么如何预处理出来f[x][0]呢，肯定不能暴力往上面跳着找，我们i从大到小枚举，fa，即他的父亲，比他父亲大的位置，如果还是比当前位置小，那么就继续跳，如果他的父亲比他大就是他父亲，如果不是的话，当前的x...

滑动窗口板子 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2000010; int a[N]; int q[N]; int main() { ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int n,k; cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; int hh=0,tt=-1; vector<int>res; hh=0,...

https://ac.nowcoder.com/acm/problem/15553题意：今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间,即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。思路：从前往后递推，求出前缀的最大值，和目前的值。然后每次取max #include<bits/stdc++.h> using namespace std; typedef ...

链接：https://ac.nowcoder.com/acm/problem/13230题意给定两个子序列，让他们合并，然后求最长回文子串。思路就是区间dp dp[N][N][N][N];//a中子序列l～r和b中序列l～r是否为回文串转移考虑边界就行了，详细看代码。 #include<bits/stdc++.h> using namespace std; const int N=55; bool dp[N][N][N][N];//a中子序列l～r和b中序列l～r是否为回文串 int main() { int t; cin>>t; while(t--) { memset...