对于该题的建模考虑类型为二分图，即对N个点进行拆点，左边与行相连，容量为1，右边与列相连，容量为1，然后跑最大流即可 #include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N = 1e6+10; struct Edge{ int v,next,w; }edge[N<<1]; int tot=1,head[N],S,T; const int INF = 1e9; int d[...

显然，当枚举的值等于k+1时，结束循环即可 #include <bits stdc++.h> using namespace std; int n,k; const int N = 1e6 + 10; bool st[N]; int main(){ cin >> n >> k; int a = 1; while(1){ if(a == k + 1) break; for(int i=a;i<=n;i+=k){ if(!st[i]) cout << i <&...

即对于非强制在线题目，可以通过对查询排序从而使用线段树维护降低时间复杂度的思路 例题：[USACO18FEB]Snow Boots G

求两两之间和的异或和, #include<bits/stdc++.h> using namespace std; #define ll long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) const int MAXN = 1e6+5; const int MOD= 998244353; int n; int a[MAXN],b[MAXN]; int main() { while(~scanf("%d",&am...

题意，对于每个点，求出它的子树中任意一点（包括该点）的lca为该点的最大的gcd(v[i],v[j]) 由于的大小只有1e5,显然可以用欧拉筛预处理 void get(int n){ for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i) v[j].push_back(i); }然后从子树往父节点进行线段树合并即可，维护sum[N * 300]表示每个子节点处因子的出现次数，在合并时，如果父节点与子节点在该点处均有值，即可更新，然后sum[fa] += sum[son]完整代码： #pragma G...

a个甲物品和b个乙物品，一次随机取一台，求第k次拿出乙物品的概率 /* 思路：本题的推导十分巧妙，显然是不能写出第k次来找规律 第k次拿出乙物品即从b中随便选一个来填补第k位，剩下a+b-1个位置随便进行排列即可，在除以全排列即为概率 化简即得b/(a+b) */ #include <bits/stdc++.h> using namespace std; string c; int main(){ int t; cin >> t; while(t--){ int a,b,k; cin &g...

本题考虑的是平方数的性质，即平方数的每个质因数的出现次数为偶数，那么对于n个数而言，它们的质因数次数为偶数的标记为0，奇数的标记为1，那么由线性基的性质可得最少的基底数，可以表示所有的线性空间。所以除开基地，即可以选择任意的数字，所以答案即是 #include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7,N = 1e5 + 10; int n; int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67}; int d[40]; int a...

链接：https://www.luogu.com.cn/problem/P4570 线性基最重要的性质 1、原序列任意数字，都可由线性基异或得到。 2、线性基不可能异或得到0 3、无论怎么用原序列对线性基进行插入，得到的线性基是一定的。 题目分析：由于线性基不可能为0，而线性基已经满足不会异或到0且最大的条件(不然可以继续往线性基里插入元素)那么这时即可贪心，按权值排序，如果能插入则更新答案 #include <bits/stdc++.h> using namespace std; typedef long long ll; int n; const int ...

思路：维护一个单调栈，同时维护字符是否出现过和字符的剩余个数链接：https://ac.nowcoder.com/acm/contest/551/D // #include <bits/stdc++.h> int vis[300]; using namespace std; int main(){ string s,res; cin >> s; unordered_map<int,int>cnt; for(auto c:s) cnt[c]++; for(int i=0;i<s.size();i++){ ...

魔法指纹 分析：乍一看，会认为是数位dp，但根本无法确定数位dp的状态和转移方程。所以可以采用分块打表方法即预处理[1,1e6],[1e6,2e6].......的前缀和，块内直接暴力即可 #include<bits/stdc++.h> //#define int long long using namespace std; int a[20],l,r; int b[]={0,2045,3089,3839,4196,4512,4828,5186,5935,6979,8453,9319,10363,10666,10886,11040,11155,11239,11364,11710...

常用next[i][j]来表示从第i个位置开始，字符串j出现的第一个位置或其他含义从而达到快速判断是否为模式串的(子序列)或者优化dp的目的 例题：小Z的笔记 #include <bits/stdc++.h> using namespace std; int n,m; const int N = 1e5 + 10; char s[N]; char vis[26][26]; int nex[N][26]; int dp[N]; int main(){ scanf("%d",&n); scanf("%s",s + 1)...

好久没有复习数位dp了，今天来补下这个题链接 思路：简化一下即是求的对数满足且,很明显这是一个数位dp，即f[len][limit1][limit2]来表示，那么本题就可以考虑将每个数进行状态压缩 对于limit，0表示有限制，1表示无限制state表示1~n的每个r[i]对x位的取值state|limit：表示当前位限制对下一位的影响如果当前没有限制，则取1如果有限制，且可以放1，那么当前位保持限制，其他位解除限制 #include <bits/stdc++.h> using namespace std; #define int long long const int mo...

好吧，这次没有调出来，所以还是记录一下但它和黑妹的游戏II 是非常相似的思路：对于ALICE和BOB，每次获得的分数即为前缀和，那么令dp[i]表示当前选择i的人能获得的当前分数-对手分数的最大差值倒推，dp[i] = max(dp[i],sum[i] - dp[i+1]);而因为选择个数>=2，则对于ALICE来说1必选故答案为dp[1] 但是为什么初始化不同呢？因为在黑妹的游戏这里，对手的状态在我的状态之后而本题中，我的状态在对手的状态之后所以初始化是不同的 class Solution { public: int stoneGameVIII(vector<int&gt...