HDU-6624 fraction  给定 ,求出并且要最小,,满足  可以写成,根据可以推出即,因为,所以两边可以减去最大的整数.变成,再倒过来变成 ，重复以上步骤直到两端点之间有整数时取最小的整数,，所以可以用辗转相除法得到.   #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout)...

HDU-6635 Nonsense Time  给定一个排列,每次插入,查询最长上升子序列长度.  由于数据随机,每次只要标记其中能构成最长上升的元素,然后暴力找.   #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; const long long mod=1e9+7; const int oo=0x7fffffff; const int sup=0x80000000...

HDU-6156 Palindrome Function       #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=2e5; const long long mod=1e9+7; const long long mod2=998244353; const int oo=0x7fffffff; const int sup=0x80000000; typedef long lon...

void getnx(char *str){ //nx[i] 是str[1..x]与str[y..i]的最大公共前缀长度 x<i,y>1 int len=strlen(str);int i=0,k=-1;nx[0]=-1; while(i<len)if(k==-1||str[i]==str[k])nx[++i]=++k;else k=nx[k]; } int index(char *str,char *p){ int i=0,j=0;int len1=strlen(str),len2=strlen(p); if(len1==1&&len2==1)if(str[...

char str[N],s[N]; int len[N]={0}; int manachr(){ s[0]='$'; int n=1; for(int i=0;str[i];i++)s[n++]='#',s[n++]=str[i]; s[n++]='#';s[n]='\0'; int MAX=0,id=0,mix=0; for(int i=1;i<n;i++){ if(i<mix)len[i]=min(len[2*id-i],mix-i); else len[i]=1; while(s[i-len[i]]==s[i+len[i]])len[i]++; if(len[i]+i>...

#include<cstdio> #include<cstring> #include<algorithm> #define mid (l+r)/2 using namespace std; const int N = 100010; int n, q, m, cnt = 0; int a[N], b[N], T[N]; int sum[N<<5], L[N<<5], R[N<<5]; int getid(int x){return lower_bound(b+1,b+1+m,x)-b;} inline int build...

#include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define scnaf scanf #define itn int using namespace std; const int o_o=5e5+5; const int mod=1e9+7; const int oo=0x7fffffff; const int sup=0x80000000; const int bit=21; typedef long long ll; typedef unsigned long long ull; void read(...

#include<iostream> #include <cstdio> #include <cstring> using namespace std; #define me(a,x) memset(a,x,sizeof(a)) struct Trie{ Trie *next[27]; int num; Trie(){me(next,NULL);num=1;} }; void insert(char *str,int n,Trie* &root){ if(str[n]=='\0')return; int key=str[n]-'a'; if(root...

prim int prim(int x,int n) { int sum=0; memset(visit,false,sizeof(visit)); for(int i=1;i<=n;i++) dis[i]=mp[x][i]; dis[x]=0; visit[x]=true; for(int i=1;i<=n;i++) { int k,mincost=INF; for(int j=1;j<=n;j++) if(!visit[j]&&dis[j]<mincost) mincost=dis[k=j]; if(mincost==INF) break; visi...

for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]); 传递闭包 for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) dp[i][j]|=dp[i][k]&dp[k][j]; or for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++...

最大匹配=最小点集 最大独立集=最小边集(最小路径覆盖)=|V|-最大匹配   匈牙利算法 struct edge{int u,v;edge *next;}*head[N],e[N]; void add(int u,int v){ edge *p=&e[cnt++]; p->u=u;p->v=v;p->next=head[u];head[u]=p; } bool dfs(int u){ vis[u]=1; for(edge *p=head[u];p;p=p->next){ if(!vis[p->v]){ vis[p->v]=1; if(!y[p-&g...

强连通 void tarjan(int u){ vis[u]=true; Q.push(u); LOW[u]=DFN[u]=++cnt; for(int v:g[u]){ if(!DFN[v]){ LOW[u]=min(LOW[u],LOW[v]); }else if(vis[v])LOW[u]=min(LOW[u],DFN[v]); //还在栈中 } if(DFN[u]==LOW[u]){ ans++; int x; do{ x=Q.top();Q.pop(); vis[x]=0;num[x]=ans; }while(u!=x); } }割点 void tarjan(int u,int fa...

1189E.Count Pairs  You are given a prime number , different integers and an integer .Find the number of pairs of indexes for which .  因为 所以 整理得 . 又因为 所以上述式子与原式等价.    #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=...

1187E.Tree Painting  给定一颗树,求以任意结点为根,所有子树大小的和的最大值.  树形 ,换根.先以任意结点为根,处理出 数组, 表示子树 中所有子树大小的总和.然后在进行一边遍历,进行换根操作,推出转移方程:    #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; const long long mod=1e9+7; const int oo=0x...