KMP /* kmp算法： * kmp()返回匹配数。 * next[i]:ss的第i个位置前的最长与模式串ss前缀匹配的长度。 * vis[i]:第i个位置是否被匹配。 * 使用kmp()前必须调用pre_kpm(); * 时间复杂度O(n+m) */ #define MAXN 100005 int nex[MAXN]; int vis[MAXN]; void pre_kmp(string ss,int m)//子串，求next数组 { nex[0]=-1; int i=0,j=-1; while(i<m) { while(j!=-1&&ss[i]!=ss[j]) j=...

这一场，题目好多都还不会，sg函数，FFT,DFT啥的都还不会。 B 几何题，给问球是否会掉下，不会球在什么位置   代码： #include<bits/stdc++.h> #include <iostream> using namespace std; typedef long long ll; int main() { //freopen("in.txt","r",stdin); double r,a,b,h,o,x,y,z; scanf("%lf%lf%lf%lf",&r,&a,&...

C 给你n*m的网格，每一次可以横的或者竖的连接两个相邻的两个格点，轮流操作，连接的过程中不能有封闭图形，问最后先手赢还是后手赢 #include<bits/stdc++.h> using namespace std; int main() { int n,m;cin>>n>>m; if(n>m){int x=n;n=m;m=x;} int ans=m*n-1; if(ans%2)puts("YES"); else puts("NO"); } 数据其实可以出的大一点。 D 比牌的大小，(2,8)最大，a=b仅次，...

__int 128,不能使用普通的cin,cout,输入，输出，需要自己写一个输入输出的模板 #include <bits/stdc++.h> using namespace std; void scan(__int128 &x)//输入 { x = 0; int f = 1; char ch; if((ch = getchar()) == '-') f = -f; else x = x*10 + ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') x = x*10 + ch-'0'; x *=...

HDU4823  代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; #define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) const int N=100010; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; const ll INF64 = 0x3f3f3f3f3f3f3f3f; ll qpow(ll a,int b){ll ans=1;while(b){if...

题目描述  数据范围 对于20%的评测用例，；对于所有评测用例，。 思路： 组合数和杨辉三角：第i行第j列的数都是组合数C(i, j) （i，j从0开始） C(n, 1) = n --> 对应从左向右看斜着的第二列！ ---> 一定有解 由于杨辉三角左右对称（C(a, b) == C(a, a-b)），又由于找第一次出现，因此一定在左边，右边可以直接删掉！ 1 ---> C(0, 0) 1 1 2 ---> C(2, 1) 1 3 ---> C(2n, n) 1 4 6 ---> C(4, 2) 1 5 10 1 6 15 20 ---> C(6, 3...

题目描述 给定一个 的整数矩阵，其中第 行第 列的元素为 aij。 你可以进行任意多次如下操作： 选择矩阵中的两个相邻元素，将它们均乘以 −1。 同一个元素可以被选中多次。 你需要通过上述操作，使得矩阵中所有元素的和尽可能大。 计算并输出这个和的最大可能值。 输入格式 T组输入，给定n,m；表示n*m的矩阵 输出格式 输出最大值 样例描述： 2 2 2 -1 1 1 1 3 4 0 -1 -2 -3 -1 -2 -3 -4 -2 -3 -4 -5思路： 开始我的想法是盲猜所有的负数都可以转变成正数，对比样例发现，这种情况只有在，负数为偶数的时候才可以全部变成负数，而奇数的时候，可以看成是偶数+...

A 题目描述：  我是***，我不知道 答案：25 B 题目描述：  开头两题直接***，这题又没读清题目，存质数，首先自己是质数然后再去判断每一位是不是质数 代码： #include<bits/stdc++.h> using namespace std; const int N=20210605; bool st[N]; int prime[N],cnt; void get_primes(){//欧拉筛 memset(st,true,sizeof(st)); cnt=0; st[0]=st[1]=false; for(int i=2;i<=N;i++){ if(st[i])...

图的存储 1.邻接矩阵 用二维数组存储即可，int g[N][N]; 无向图：g[i][j]=g[j][i],g[i][i]=0; 有向图：g[i][j]!=g[j][i],缺点：  空间复杂度太高，只适合于存储稠密图， 不能存储重边  2.邻接表 struct edge{//边类型 int from,to,w; edge(int a,int b,int c){ from=a;to=b;w=c; } }; vector<edge> e[N]; //初始化 for(int i=1;i<=n;i++){ a[i].clear(); } //存边 e[a].push_back(ed...

题目 给出两个长度为 n 的整数序列，求它们的最长公共子序列（LCS）的长度，保证第一个序列中所有元素都不重复。 样例： 输入 5 1 2 3 4 5 1 2 3 4 5 5 1 2 3 5 4 1 2 3 4 5 输出 5 4思路 读题会发现这个跟普通的最长公共子序列不太一样，他的自己的序列没有重复的数。我们会发现最长公共子序列这个序列的下标是单调递增的，在读题发现他让我们求得仅仅仅仅知识最长公共子序列的长度，把这个序列的下标放进一个数组里，答案就是这个数组的长度。那么问题似乎就变成了求最长子序列。 那么这个问题为什么能变成最长子序列的问题？  > 因为公共子序列中值的相同的，所以数组...

题意描述  给你一个数n，问能否用几个数的阶乘的和组成n，每一个数的阶乘只能够用一次  思路： 把0~9的阶乘打表打出来，每一个只能选一次，这不就是01背包问题啊，每一个只能用一次，n就是最大背包容量，跟这一次选拔赛那个D题几乎一样既可以01背包、也可以二进制枚举。我真的服了，当时为啥不好好读题呢。回到这里，这个题同样也可以采用二进制枚举的方法，求出每一种情况的和，丢进哈希表里，然后查询n是否在哈希表中。 二进制枚举：> 二进制的每一位都可以代表一种状态，选择或者不选择，那么每一个二进制数都代表一种情况。 二进制枚举代码： #include <iostream> #inclu...

目录   01背包   完全背包   多重背包   分组背包   线性dp    数字三角形 最长上升子序列 最长上升子序列II 最长公共子序列 最短编辑距离      区间DP    石子合并      数位DP    计数问题      最长回文子串   01背包   题意：n个物品，每一个物品只能选一次，体积不超过m能得到的最大价值。   状态方程：   f[i][j]=f[i-1][j];//放不下的情况 if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);//第i个物品选不选   代码：  #include<bits/...

A.  题意：给你一个数n；问他是否有一个奇数的公因子。 思路：除了质数2，其他的质数都是奇数。我么可以直接判断n是否为2的次幂就行。签到，当时看错了题意，真***。 代码：  #include<bits stdc++.h> using namespace std; int a[100010]; int main(){ long long n; while(cin>>n){ int flag=0; for(int i=1;i<=64;i++){ if(n==pow(2,i)) flag=1; } if(!flag) puts("YES");...

判定质数 bool is_prime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) return false; return true; }分解质因数 据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。  所以他的组合应该有,因数的个数就是这个。 每一个质因数都可以选0~an个，由排列组合推出。 如果 N = p1^c1 * p2^c2 * ... *pk^ck 约数个数： (c1 + 1) * (c2 + 1) * ...