比赛的时候不会做… 然后今天才得知是一道原题，一道二分图最小覆盖点的模板题… 为什么大佬什么算法都会，什么题都做过… 代码： #include <bits/stdc++.h> using namespace std; const int N=100050; const int M=100050; int n,m; char s[N]; struct Edge{  int v,next; }edge[M]; int cnt,head[N]; void init(){  cnt=0; memset(head,-1,sizeof(head)); } void addEdge(int u,...

dfs染色法 若是二分图也就说明不存在奇环 #include <bits/stdc++.h> using namespace std; const int N=1e4+50; const int M=1e5+50; int n,m; int u,v; struct Edge{  int v,next; }edge[M]; int cnt,head[N]; int color[N]; void init(){  cnt=0; memset(head,-1,sizeof(head)); } void addEdge(int u,int v){  edge[cnt]=Edge{ v,he...

邻接表数组记得要开两倍边啊 import java.util.Arrays; import java.util.Scanner; public class Main{  static final int N=(int)1e4+50; static final int M=(int)4e4+50; static int t,n,m,u,v; static int cnt; static int[] head=new int[N],color=new int[N]; static Edge[] edges=new Edge[2*M]; static class Edge{  int v,next;...

#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=2050; const int M=10050; int n,m; int u,v; struct Edge{  int to,next; }edge[M]; int cnt; int head[N]; void init(){  cnt=0; memset(head,-1,sizeof(head)); } void addEdge(int u,int v){  edge[cnt...

import java.util.Arrays; import java.util.Scanner; public class Main{  static final int N=(int)2e3+50; static final int M=(int)1e4+50; static int n,m,u,v; static int cnt; static int[] head=new int[N],link=new int[N]; static boolean[] vis=new boolean[N]; static Edge[] edges=new Edge[2*M]; static clas...

如果只是求最小覆盖数，直接求最大匹配就好，如果还要求覆盖点集，就还要再抄抄模板 这里是一道经典的最小覆盖点集的题目，所以左右点集都是确定好的，和上份模板最大匹配不太一样 #include <bits/stdc++.h> using namespace std; const int N=100050; const int M=100050; int n,m; char s[N]; struct Edge{  int v,next; }edge[M]; int cnt,head[N]; void init(){  cnt=0; memset(head,-1,sizeof(head));...

import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main{  static final int N=(int)1e5+50; static final int M=(int)1e5+50; static int n,m; static String s; static int cnt; static int[] head=new int[N],Left=new int[N],Right=new int[N]; static boolean[] S=new bo...

居然要用到kmp… 瞎搞了半天…不对是四个月，今天无意中翻到这题还是不会做，抄了下题解 首先这个kmp的匹配就稍微变形了一点，用kmp(a,b)然后不是输出匹配的位置，也不是输出匹配的数量，而是输入当i==sl的时候，也就是原串匹配完了，这时候pat匹配到那个位置，输入j，这样把a和b分别作为模式串去匹配另一个，看看谁的前缀能连上另一个的后缀的长度更长一些，如果相同再比较字典序 代码： #include <cstdio> #include <algorithm> #include <cstring> #include <string> using...

问答对一半的方案数，也就是k个错，n-k个对，k从0到n/2枚举，然后k个错的就用错排公式，然后还要乘上从n个人中选出k个错的的组合数 ，两个都可以打表出来 代码: #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=30; typedef long long ll; ll a[N],c[N][N]; void init(){  a[0]=1; a[1]=0; for(int i=2;i<N;i++){  a[i]=(i-1...

最简单的并查集 hdu1232 #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int N=1050; int p[N]; int n,m; void init(){  for(int i=1;i<=n;i++){  p[i]=i; } } int find(int x){  return p[x]==x ? x : p[x]=find(p[x]); } void unit(int a,int b){  p[find(a)]=fin...

import java.util.Scanner; public class Main{  static final int N=1050; static int n,m,u,v; static int[] p=new int[N]; static void init(){  for(int i=1;i<=n;i++){  p[i]=i; } } static int find(int x){  return p[x]==x?x:(p[x]=find(p[x])); } static void unit(int a,int b){  p[find(a)]=find(b); } stati...

要求出一个数最少能用几个完全平方数组成，有一个结论，一个数最多只要由四个完全平方数组成，有了这个结论就直接检查能不能1个数 2个数 3个数组成，都不行就只能用4个数了 代码： #include <bits/stdc++.h> using namespace std; int n; bool check1(int n){  int a=int(sqrt(n)); return a*a==n; } bool check2(int n){  for(int i=1;i*i<=n;i++){  if(check1(n-i*i)){  return true; } } return f...

经典的搜索题目，算24点，枚举四个数 枚举三个运算符，然后数和运算符的组合其实只有两种，分别判断一下，搜索还是不太熟悉，很多细节要考虑清楚 代码： #include <bits/stdc++.h> using namespace std; const double eps=1e-5; bool vis[4]; int num[4]; int now[4]; int op[3]; int t; double ope(double a,double b,int x){  switch(x){  case 1:{  return a+b; } case 2:{  return a-b; ...

用一个经典的种类并查集做例子，食物链那一题  #include <cstdio> #include <algorithm> using namespace std; const int N=50050; int n,k,q,a,b; int p[N]; //num数组 0表示和父节点同类 1表示被父节点吃，2表示吃父节点 //所有取模前提条件都是A吃B B吃C C吃A 长度为3的环 int num[N]; int find(int x){  if(x==p[x]){  return x; } //要先保存这个父节点，否则下面压缩路径后p[x]会变 int fa=p[x]...