input的使用：input()是整行读取，如果要跳过空格需要用a,b = input().split()。当然a,b,c=input().split()都可以，a,b,c都是字符串。如果要a，b保存的是整数，可以这么做：a,b = map(int,input().split())

hdu 1710 1.模板：  #include<bits/stdc++.h> using namespace std; const int N = 1010; int pre[N],in[N],post[N]; int k; struct node{ int value; node *l,*r; node(int value=0,node *l=NULL,node *r=NULL):value(value),l(l),r(r){} //初始化 }; void buildtree(int l,int r,int&t,node* &root) { //以先序为模板，先...

hdu 2243 1.解释： 先构造矩阵A，AnA^nAn表示含有词根长度为n的单词数量，长度不小于n且含词根的单词数量X=A+A2+...+AnX=A+A^2+...+A^nX=A+A2+...+An，单词总数sum=26+26……2+...+26nsum=26+26……2+...+26^nsum=26+26……2+...+26n,根据题意，需要求长度不小于n且不含词根的单词数量，则ans=sum-X; 可以参考二分幂的方法:先求出(A+A2+A3……An/2)(A+A^2+A^3……A^{n/2})(A+A2+A3……An/2)【记为B】和An/2A^{n/2}An/2的值,则X=(An/...

1.poj 2778题解加代码注释   转载处：https://blog.csdn.net/morgan_xww/article/details/7834801?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task和https://www.cnblogs.com/WABoss/p/5167101.html         这个图是例子{“ACG”,”C”},构建trie图后如图所示，从每个结点出发都有4条边（A,T,C,G） •从状态0出发走一步有4...

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include <vector> #include<map> #include<set> #include<utility> #define js ios::sync_with_stdio(false) #define mes(a,b) memset(a,b,siz...

基于bfs的：hdu1285有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。  #include<bits/stdc++.h> #define js ios::sync_with_stdio(false) #define mes(a,b) memset(a,b,sizeof a) using namespace std; typedef l...

1.用数组表示二叉树的编号，取出数值时是最小值 int heap[N],sz=0; void push(int x){ int i=sz++; while(i>0){ int p=(i-1)/2; if(heap[p]<=x) break; heap[i]=heap[p]; i=p; } heap[i]=x; } int pop(){ int ret=heap[0]; int x=heap[sz--]; int i=0;while(i*2+1<sz){ int a=i*2+1,b=i*2+2; if(b<sz&&a...

1.本菜鸡只会用模板求逆元，逆元是什么我都不知道，上模板： #include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; /*扩展欧几里得算法 如果a,b互质，则x为a摸b的逆元,即exgcd(a,b)=1； 返回值为a，b的最大共约数 ax+by=exgcd(a,b) */ ll exgcd(ll a,ll b,ll &x,ll &y){ if(b==0){ x=1,y=0; return a; //...

紫书习题的代码，虽然能ac，但是板子有问题，如果输入，就会错，我在别的博客修改了板子戳我传送，这里懒得改了（毕竟紫书的板子只要输入的字符串的字符种类大于1就不会错）。78ms代码： #include<bits/stdc++.h> using namespace std; const int MAXN=200005; //字符串的长度 char s[MAXN]; //输入字符串 int sa[MAXN],cnt[MAXN],t1[MAXN],t2[MAXN],rk[MAXN],height[MAXN]; int n; void calc_sa(){ //n是字符串长度 int m=1...

前言：紫书代码如果输入的字符串是就会错，需要把;改成，同时的板子也要改一个地方，最后的索引范围为。我太难了，之前看了好久才懂的模板，现在又看不懂了，看了好久第二个模板还是懵逼。。1.用sort()函数求后缀数组sa[]总复杂度：O() #include<bits/stdc++.h> using namespace std; const int MAXN=200005; //字符串的长度 char s[MAXN]; //输入字符串 int sa[MAXN],rk[MAXN],tmp[MAXN+1],height[MAXN]; int n,k; /*比较函数 每一步使得 sa[]从0到...

#include<bits/stdc++.h> using namespace std; const int maxn =1000000+100; const int SIGMA_SIZE=26; const int maxnode =1000000+100; int n,ans; bool vis[maxn]; int ch[maxnode][SIGMA_SIZE]; int val[maxnode]; int idx(char c){return c-'a';}; struct Trie{ int sz; Trie(){ sz = 1; memset(ch[0],0,sizeo...

Next[i]Next[i]Next[i]数组表示字符串p[0]∼p[i−1]p[0]\sim p[i-1]p[0]∼p[i−1]除自身以外的最长相同前缀和后缀的长度  Next[j]Next[j]Next[j]表示当p[j]p[j]p[j]失配时，j回溯的位置。还有以下含义 1.匹配串ppp能向右滑动尽可能远的距离（辅助理解而已） 2.前j−1j-1j−1个字符串中，前缀字符串和后缀字符串的最大匹配长度。（后面有应用） #include<bits stdc++.h> using namespace std; const int MAXN=1000+5; char str[MAXN...

#include<iostream> #include<algorithm> #include<vector> #include<cstring> using namespace std; const int N=10005; struct node{ char name[35]; int price; }; vector<node>List[N]; //用于解决冲突 unsigned int BKDRHash(char *str){ unsigned int seed=31,key=0; while(*str) key=key*se...

1.用字典树实现空间超额（MLE）的代码，还有更好更紧凑的字典树实现方法 #include<bits/stdc++.h> using namespace std; struct Trie{ //字典树的定义 Trie* next[26]; int num; //以当前字符串为前缀的单词的数量 Trie(){ //构建函数 for(int i=0;i<26;i++) next[i]=NULL; num=0; } }; Trie root; void Insert(char str[]){ //将字符插入字典树中 Trie *p=&root; for(int i=0;st...