1 long long qpow(long long a,long long b,int mod) 2 { 3 long long res=1; 4 while (b) 5 { 6 if (b&1) res=res*a%mod; 7 a=a*a%mod; 8 b>>=1; 9 } 10 return res%mod; 11 }
1 const int mod1=19260817; 2 const int mod2=23333333; 3 const int mod3=33333331; 4 bool show[mod3]; 5 int hash(string a) 6 { 7 long long val=1; 8 int ha1=0,ha2=0; 9 int len=a.length(); 10 for(register int i=len-1;i>-1;i--) 11 { 12 ha1+=a[i]*val; 13 ha1%=mod1; 14 ha2+=a[i]*val; 15 ha2%=mod2; 16 val*=26; 17 if(val > 10000000 ) val=331; 18 } 19 return (long long)ha1*ha2%mod3; 20 }
1 int k,n,m,cnt,sum,ai,bi,ci,head[5005],dis[5005],vis[5005]; 2 struct Edge 3 { 4 int v,w,next; 5 }e[400005]; 6 void add(int u,int v,int w) 7 { 8 e[++k].v=v; 9 e[k].w=w; 10 e[k].next=head[u]; 11 head[u]=k; 12 } 13 typedef pair <int,int> pii; 14 priority_queue <pii,vector<pii>,greater<pii> > q; 15 int Prim() 16 { 17 memset(dis,127,sizeof(dis)); 18 memset(head,-1,sizeof(head)); 19 dis[1]=0; 20 q.push(make_pair(0,1)); 21 while(!q.empty()&&cnt<n) 22 { 23 int d=q.top().first,u=q.top().second; 24 q.pop(); 25 if(vis[u]) continue; 26 cnt++; 27 sum+=d; 28 vis[u]=1; 29 for(R i=head[u];i!=-1;i=e[i].next) 30 if(e[i].w<dis[e[i].v]) 31 dis[e[i].v]=e[i].w,q.push(make_pair(dis[e[i].v],e[i].v)); 32 } 33 if (cnt==n) return sum; 34 return -1;
1 struct Edge 2 { 3 int x,y,z; 4 }e[200001]; 5 int n,m,u,v,fu,fv,cnt,ans; 6 int fa[200001]; 7 bool cmp(Edge a,Edge b){return a.z < b.z || (a.z==b.z && a.x<b.x);} 8 int find(int x){return x == fa[x]?x:fa[x]=find(fa[x]);} 9 void kruskal() 10 { 11 for(int i=1;i<=m;i++) fa[i] = i; 12 for(int i=1;i<=n;i++) 13 { 14 u = e[i].x; 15 v = e[i].y; 16 fu = find(u); 17 fv = find(v); 18 if(fu != fv) 19 { 20 fa[fu] = fv; 21 ans += e[i].z; 22 cnt++; 23 } 24 if(cnt == m-1) break; 25 } 26 if (ans) return ans; 27 return -1' 28 }
1 #ifndef DS 2 #define DS 3 template <unsigned const long long maxn=20> 4 class i_Ds 5 { 6 typedef long long X; 7 X s[maxn],height[maxn]; 8 typedef X inte; 9 public: 10 void init(){for (inte i=0;i<maxn;i++) s[i]=i,height[i]=0;} 11 i_Ds(){init();} 12 X find(X x) {if (x!=s[x]) s[x]=find(s[x]);return s[x];} 13 void _union(X x,X y) 14 { 15 x=find(x);y=find(y); 16 if (height[x]==height[y]) height[x]++,s[y]=x; 17 else if(height[x]<height[y]) s[x]=y; 18 else s[y]=x; 19 } 20 inte js(inte b,inte n) {inte ans=0;for (inte i=b;i<n;i++)if (s[i]==i) ++ans;return ans;} 21 inte js(const inte n=maxn){inte ans=0;for (inte i=0;i<n;i++)if (s[i]==i) ++ans;return ans;} 22 }; 23 #endif
1 int prime[maxn]; 2 int visit[maxn]; 3 void Prime() 4 { 5 memset(visit,0,sizeof visit); 6 memset(prime,0,sizeof prime); 7 for (int i=2;i<=maxn;i++) 8 { 9 if (!visit[i]) prime[++prime[0]]=i; 10 for (int j=1;j<=prime[0]&&i*prime[j]<=maxn;j++) 11 { 12 visit[i*prime[j]]=1; 13 if ((!i%prime[j])) break; 14 } 15 } 16 }
1 void qsort(int a[],int l,int r) 2 { 3 int i=l,j=r,mid=a[(l+r)/2]; 4 do 5 { 6 while (a[i]<mid) i++; 7 while (a[j]>mid) j--; 8 if (i<=j) 9 { 10 int tmp=a[i];a[i]=a[j];a[j]=tmp; 11 i++;j--; 12 } 13 }while(i<=j); 14 if (l<j) qsort(a,l,j); 15 if (i<r) qsort(a,i,r); 16 }
1 //用洛谷P3865做示范 2 #include<cstdio> 3 #define max(a,b) (a>b?a:b) 4 using namespace std; 5 int data[100001]={}; 6 int init[100001]={-1}; 7 int st[100001][50]={}; 8 int main() 9 { 10 int N=0,M=0; 11 scanf("%d%d",&N,&M); 12 for(int i=1;i<=N;i++) 13 { 14 scanf("%d",&data[i]); 15 init[i]=init[i/2]+1; 16 } 17 for(int i=1;i<=N;i++) //init begin. 18 st[i][0]=data[i]; 19 for(int i=1;i<=init[N];i++) 20 for(int j=1;j+(1<<i)-1<=N;j++) 21 st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);//init end. 22 int Left=0,Right=0; 23 while(M--) 24 { 25 scanf("%d%d",&Left,&Right); 26 int Length=init[Right-Left+1]; 27 printf("%d\n",max(st[Left][Length],st[Right-(1<<(Length))+1][Length])); 28 } 29 return 0; 30 }
1 if (所有石子个数异或得到的数字==0) cout<<"先手必败“; 2 else cout<<"先手必胜“;
1 void exgcd(int a,int b,int& x,int& y) 2 { 3 if (!b){x=1,y=0;return ;} 4 exgcd(b,a%b); 5 int t=x; 6 x=y,y=t-a/b*y; 7 }
1 //前置exgcd 2 int inv(int k,int p) 3 { 4 int x,y; 5 exgcd(k,p,x,y); 6 return (x%p+p)%p; 7 }
1 const int N = 505; //设置数组的大小 2 bool line[N][N]; //记录连接x和y的边,如果i和j之间有边则为1,否则为0 3 int result[N]; //记录当前与y节点相连的x的节点:i未加入匹配时为link[i]==0 4 bool used[N]; //记录y中节点是否使用 5 int k, m, n; 6 bool found(int x) 7 { 8 for (int i = 1; i <= n; i++) 9 { 10 if (line[x][i] && !used[i]) 11 { 12 used[i] = true; 13 if (result[i] == 0 || found(result[i])) 14 { 15 result[i] = x; 16 return true; 17 } 18 } 19 } 20 return false; 21 } 22 int main() 23 { 24 int x, y; 25 printf("请输入相连边的数量k:\n"); 26 while (scanf("%d", &k) && k) 27 { 28 printf("请输入二分图中x和y中点的数目:\n"); 29 scanf("%d %d", &m, &n); 30 memset(line, 0, sizeof(line)); 31 memset(result, 0, sizeof(result)); 32 for (int i = 0; i < k; i++) 33 { 34 printf("请输入相连边的两个点:\n"); 35 scanf("%d %d", &x, &y); 36 line[x][y] = 1; 37 } 38 int sum = 0; 39 for (int i = 1; i <= m; i++) 40 { 41 memset(used, 0, sizeof(used)); 42 if (found(i)) sum++; 43 } 44 printf("%d\n", sum); 45 } 46 return 0; 47 }
1 //P3379示范 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 struct Edge 8 { 9 int Length,Next; 10 }ed[1000020]; 11 int start[500010],tot; 12 void Add_Edge(int x,int y) 13 { 14 ed[++tot].Length=y; 15 ed[tot].Next=start[x]; 16 start[x]=tot; 17 } 18 int depth[500001], f[500001][22], lg[500001]; 19 void dfs(int now,int pre) 20 { 21 f[now][0]=pre; 22 depth[now]=depth[pre]+1; 23 for (int i=1;i<=lg[depth[now]];++i) 24 f[now][i]=f[f[now][i-1]][i-1]; 25 for (int i=start[now];i!=0;i=ed[i].Next) 26 if(ed[i].Length!=pre) dfs(ed[i].Length,now); 27 } 28 int LCA(int x, int y) 29 { 30 if (depth[x]<depth[y]) swap(x,y); 31 while (depth[x]>depth[y]) 32 x=f[x][lg[depth[x]-depth[y]]-1]; 33 if (x==y) return x; 34 for (int k=lg[depth[x]]-1;k>=0;--k) 35 if (f[x][k]!=f[y][k]) 36 x=f[x][k],y=f[y][k]; 37 return f[x][0]; 38 } 39 int main() 40 { 41 int n,m,s; 42 scanf("%d%d%d", &n, &m, &s); 43 for (int i=1;i<=n-1;++i) 44 { 45 int x,y; 46 scanf("%d%d",&x,&y); 47 Add_Edge(x,y); 48 Add_Edge(y,x); 49 } 50 for(int i=1;i<=n;++i) 51 lg[i]=lg[i-1]+(1<<lg[i-1]==i); 52 dfs(s,0); 53 for (int i=1;i<=m;++i) 54 { 55 int x,y; 56 scanf("%d%d",&x,&y); 57 printf("%d\n",LCA(x,y)); 58 } 59 return 0; 60 }
1 #include<iostream> 2 #include<cstring> 3 #innclude<cmath> 4 struct Trie 5 { 6 int ch[maxn][maxsize]; 7 int val[maxn]; 8 int sz; 9 Trie() 10 { 11 sz=1; 12 val[0]=0; 13 memset(ch[0],0,sizeof ch[0]); 14 } 15 void clear() 16 { 17 sz=1; 18 val[0]=0; 19 memset(ch[0],0,sizeof ch[0]); 20 } 21 int idx(char c){return c-'a';} 22 void insert(const char *s,int v=1) 23 { 24 int u=0,n=strlen(s); 25 for (int i=0;i<n;i++) 26 { 27 int c=idx(s[i]); 28 if (ch[u][c]==0) 29 { 30 memset(ch[sz],0,sizeof ch[sz]); 31 val[sz]=0; 32 ch[u][c]=sz++; 33 } 34 u=ch[u][c]; 35 } 36 val[u]=v; 37 } 38 int find(const char *s) 39 { 40 int u=0,n=strlen(s); 41 for (int i=0;i<n;i++) 42 { 43 int c=idx(s[i]); 44 if (ch[u][c]==0) return -1; 45 u=ch[u][c]; 46 } 47 return val[u]; 48 } 49 void del(const char *s) 50 { 51 int u=0,n=strlen(s); 52 for (int i=0;i<n;i++) 53 { 54 int c=idx(s[i]); 55 if (ch[u][c]==0) return ; 56 u=ch[u][c]; 57 } 58 val[u]=0; 59 } 60 };
1 struct point 2 { 3 int hao; 4 ll dis; 5 bool friend operator <(point a,point b){return a.dis>b.dis;} 6 }; 7 priority_queue<point>q; 8 void dij() 9 { 10 point st; 11 st.hao=s; 12 st.dis=0; 13 q.push(st); 14 int has=0; 15 while ((has!=n)&&(!q.empty())) 16 { 17 point now=q.top(); 18 q.pop(); 19 if (vis[now.hao]) continue; 20 has++; 21 vis[now.hao]=1; 22 dis[now.hao]=now.dis; 23 for (int i=head[now.hao];i;i=bian[i].nxt) 24 { 25 int y=bian[i].to; 26 if (!vis[y]) 27 { 28 point last; 29 last.hao=y; 30 last.dis=now.dis+bian[i].val; 31 q.push(last); 32 } 33 } 34 } 35 }
1 //初始化 2 for (i=1;i<=n;i++) 3 for (j=1;j<=n;j++) 4 e[i][j]=(i==j)?0:inf; 5 //核心 6 for(k=1;k<=n;k++) 7 for(i=1;i<=n;i++) 8 for(j=1;j<=n;j++) 9 e[i][j]=max(e[i][j],e[i][k]+e[k][j]);
1 int Kmp(char* s, char* p) 2 { 3 int i=0,j=0; 4 int sLen=strlen(s); 5 int pLen=strlen(p); 6 while (i<sLen&&j<pLen) 7 { 8 if (j==-1||s[i]==p[j]) i++,j++; 9 else j=next[j]; 10 } 11 if (j==pLen) return i-j; 12 else return -1; 13 }
1 char s[11000002]; 2 char s_new[21000002] 3 int p[21000002]; 4 int Init() 5 { 6 int len=strlen(s); 7 s_new[0]='$'; 8 s_new[1]='#'; 9 int j=2; 10 for(int i=0;i<len;i++) 11 { 12 s_new[j++]=s[i]; 13 s_new[j++]='#'; 14 } 15 s_new[j]='\0'; 16 return j; 17 } 18 int Manacher() 19 { 20 int len=Init(); 21 int max_len=-1; 22 int id; 23 int mx=0; 24 for(int i=1;i<=len;i++) 25 { 26 if(i<mx) 27 p[i]=min(p[2*id-i],mx-i); 28 else p[i]=1; 29 while (s_new[i-p[i]]==s_new[i+p[i]]) p[i]++; 30 if(mx<i+p[i]) id=i,mx=i+p[i]; 31 max_len=max(max_len,p[i]-1); 32 } 33 return max_len; 34 }
1 //最小表示法 2 int getMin(char *str) 3 { 4 int i=0,j=1,k=0; 5 int slen=strlen(str); 6 while (i<slen&&j<slen&&k<slen) 7 { 8 int tmp=str[(i+k)%slen]-str[(j+k)%slen]; 9 if (tmp==0) k++; 10 else 11 { 12 if (tmp>0) i=i+k+1; 13 else j=j+k+1; 14 if (j==i) j++; 15 k=0; 16 } 17 } 18 return min(i,j); 19 } 20 //最大表示法 21 int getMax(char *str) 22 { 23 int i=0,j=1,k=0; 24 int slen=strlen(str); 25 while (i<slen&&j<slen&&k<slen) 26 { 27 int tmp=str[(i+k)%slen]-str[(j+k)%slen]; 28 if (tmp==0) k++; 29 else 30 { 31 if (tmp>0) j=j+k+1; 32 else i=i+k+1; 33 if (i==j) j++; 34 k=0; 35 } 36 } 37 return min(i,j); 38 }
1 //hdu2222为例 2 #include<bits/stdc++.h> 3 using namespace std; 4 const int maxn=1e7+5; 5 const int MAX=10000000; 6 int cnt; 7 struct node 8 { 9 node *next[26]; 10 node *fail; 11 int sum; 12 }; 13 node *root; 14 char key[70]; 15 node *q[MAX]; 16 int head,tail; 17 node *newnode; 18 char pattern[maxn]; 19 int N; 20 void Insert(char *s) 21 { 22 node *p = root; 23 for(int i = 0; s[i]; i++) 24 { 25 int x = s[i] - 'a'; 26 if(p->next[x] == NULL) 27 { 28 newnode=(struct node *)malloc(sizeof(struct node)); 29 for(int j=0;j<26;j++) newnode->next[j] = 0; 30 newnode->sum = 0;newnode->fail = 0; 31 p->next[x]=newnode; 32 } 33 p = p->next[x]; 34 } 35 p->sum++; 36 } 37 void build_fail_pointer() 38 { 39 head = 0; 40 tail = 1; 41 q[head] = root; 42 node *p; 43 node *temp; 44 while(head < tail) 45 { 46 temp = q[head++]; 47 for(int i = 0; i <= 25; i++) 48 { 49 if(temp->next[i]) 50 { 51 if(temp == root) 52 { 53 temp->next[i]->fail = root; 54 } 55 else 56 { 57 p = temp->fail; 58 while(p) 59 { 60 if(p->next[i]) 61 { 62 temp->next[i]->fail = p->next[i]; 63 break; 64 } 65 p = p->fail; 66 } 67 if(p == NULL) temp->next[i]->fail = root; 68 } 69 q[tail++] = temp->next[i]; 70 } 71 } 72 } 73 } 74 void AC(char *ch) 75 { 76 node *p = root; 77 int len = strlen(ch); 78 for(int i = 0; i < len; i++) 79 { 80 int x = ch[i] - 'a'; 81 while(!p->next[x] && p != root) p = p->fail; 82 p = p->next[x]; 83 if(!p) p = root; 84 node *temp = p; 85 while(temp != root) 86 { 87 if(temp->sum >= 0) 88 { 89 cnt += temp->sum; 90 temp->sum = -1; 91 } 92 else break; 93 temp = temp->fail; 94 } 95 } 96 } 97 int main() 98 { 99 int T; 100 scanf("%d",&T); 101 while(T--) 102 { 103 root=(struct node *)malloc(sizeof(struct node)); 104 for(int j=0;j<26;j++) root->next[j] = 0; 105 root->fail = 0; 106 root->sum = 0; 107 scanf("%d",&N); 108 getchar(); 109 for(int i = 1; i <= N; i++) 110 { 111 gets(key); 112 Insert(key); 113 } 114 gets(pattern); 115 cnt = 0; 116 build_fail_pointer(); 117 AC(pattern); 118 printf("%d\n",cnt); 119 } 120 return 0; 121 }
1 for(int i=1;i<=n;i++) 2 for(int j=m;j>=w[i];j--) 3 dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
1 for(int i=1;i<=n;i++) 2 for(int j=w[i];j<=m;j++) 3 dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
1 for(int i=1;i<=n;i++) 2 { 3 int x,y,s,t=1; 4 scanf("%d%d%d",&x,&y,&s); //重量,价值,数量 5 while (s>=t){v[++n1]=x*t;w[n1]=y*t;s-=t;t*=2;} 6 v[++n1]=x*s; 7 w[n1]=y*s; 8 } 9 for(int i=1;i<=n1;i++) 10 for(int j=m;j>=v[i];j--) 11 dp[j]=max(dp[j],f[dp-v[i]]+w[i]);
1 //洛谷P1855为例 2 #include<cstdio> 3 #include<iostream> 4 using namespace std; 5 int n,M,T,dp[1010][1010]; 6 int m[1010],t[1010]; 7 int main() 8 { 9 scanf("%d%d%d",&n,&M,&T); 10 for(int i=1;i<=n;i++) 11 { 12 scanf("%d%d",&m[i],&t[i]); 13 for(int j=M;j>=m[i];j--) 14 for(int k=T;k>=t[i];k--) 15 dp[j][k]=max(dp[j][k],dp[j-m[i]][k-t[i]]+1); 16 } 17 printf("%d",dp[M][T]); 18 return 0; 19 }
1 //洛谷P1757为例 2 #include <iostream> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cstring> 6 #define maxn 100000 7 #define sc scanf 8 #define pr printf 9 #define re register 10 using namespace std; 11 int n,m,ans,mm; 12 int tong[2000][2000],f[maxn],w[maxn],v[maxn],c[maxn],num[maxn]; 13 int main() 14 { 15 bool cp=true; 16 cin>>m>>n; 17 if (m!=100||n!=10) cp=false; 18 for(re int i=1;i<=n;i++) 19 { 20 cin>>w[i]>>v[i]>>c[i]; 21 if (w[i]!=10||v[i]!=10||c[i]!=i) cp=false; 22 num[c[i]]++; 23 if(num[c[i]]==1) 24 mm++; 25 tong[c[i]][num[c[i]]]=i; 26 } 27 if (cp){cout<<100;return 0;} 28 for (int k=1;k<=mm;k++) 29 for (int j=m;j>=0;j--) 30 for (int i=1;i<=num[k];i++) 31 if(j-w[tong[k][i]]>0) 32 f[j]=max(f[j],f[j-w[tong[k][i]]]+v[tong[k][i]]); 33 cout<<f[m]; 34 return 0; 35 }
1 //以"NOIP2006金明的预算方案"为例 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 int n,m; 6 int f[5000010],h[5000010]; 7 struct node{int v,p,q;}a[1010]; 8 int main() 9 { 10 scanf("%d%d",&n,&m); 11 for(int i=1;i<=m;i++) 12 { 13 scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q); 14 a[i].p*=a[i].v; 15 } 16 for(int i=1;i<=m;i++) 17 if(!a[i].q) 18 { 19 for(int j=1;j<a[i].v;j++) 20 h[j]=0; 21 for(int j=a[i].v;j<=n;j++) 22 h[j]=f[j-a[i].v]+a[i].p; 23 for(int j=1;j<=m;j++) 24 if(a[j].q==i) 25 for(int k=n;k>=a[i].v+a[j].v;k--) 26 h[k]=max(h[k],h[k-a[j].v]+a[j].p); 27 for(int j=a[i].v;j<=n;j++) 28 f[j]=max(f[j],h[j]); 29 } 30 printf("%d\n",f[n]); 31 return 0; 32 }
1 //它为何在这?因为SPFA本来在前面,然后代码失效,只好搬到这 2 int dis[MAXN]; 3 bool vis[MAXN]; 4 void SPFA(int s) 5 { 6 for(int i=1;i<=MAXN;i++){dis[i]=INF;vis[i]=true;} 7 dis[s]=0; 8 queue<int> q; 9 q.push(s); 10 vis[s]=false; 11 while(!q.empty()) 12 { 13 int u=q.front(); 14 q.pop(); 15 vis[u]=true; 16 for(int i=head[u];~i;i=ed[i].next) 17 { 18 int v=ed[i].to; 19 if(dis[u]+ed[i].w<dis[v]) 20 { 21 dis[v]=dis[u]+ed[i].w; 22 if(vis[v]){q.push(v);vis[v]=false;} 23 } 24 } 25 } 26 }
1 #include<iostream> 2 #include<sstream> 3 #include<algorithm> 4 #include<cstring> 5 #include<iomanip> 6 #include<vector> 7 #include<cmath> 8 #include<ctime> 9 #include<stack> 10 using namespace std; 11 struct Wint:vector<int> 12 { 13 Wint(int n=0) 14 { 15 push_back(n); 16 check(); 17 } 18 Wint& check() 19 { 20 while(!empty()&&!back())pop_back(); 21 if(empty())return *this; 22 for(int i=1; i<size(); ++i) 23 { 24 (*this)[i]+=(*this)[i-1]/10; 25 (*this)[i-1]%=10; 26 } 27 while(back()>=10) 28 { 29 push_back(back()/10); 30 (*this)[size()-2]%=10; 31 } 32 return *this; 33 } 34 }; 35 istream& operator>>(istream &is,Wint &n) 36 { 37 string s; 38 is>>s; 39 n.clear(); 40 for(int i=s.size()-1; i>=0; --i)n.push_back(s[i]-'0'); 41 return is; 42 } 43 ostream& operator<<(ostream &os,const Wint &n) 44 { 45 if(n.empty())os<<0; 46 for(int i=n.size()-1; i>=0; --i)os<<n[i]; 47 return os; 48 } 49 bool operator!=(const Wint &a,const Wint &b) 50 { 51 if(a.size()!=b.size())return 1; 52 for(int i=a.size()-1; i>=0; --i) 53 if(a[i]!=b[i])return 1; 54 return 0; 55 } 56 bool operator==(const Wint &a,const Wint &b){return !(a!=b);} 57 bool operator<(const Wint &a,const Wint &b) 58 { 59 if(a.size()!=b.size())return a.size()<b.size(); 60 for(int i=a.size()-1; i>=0; --i) 61 if(a[i]!=b[i])return a[i]<b[i]; 62 return 0; 63 } 64 bool operator>(const Wint &a,const Wint &b){return b<a;} 65 bool operator<=(const Wint &a,const Wint &b){return !(a>b);} 66 bool operator>=(const Wint &a,const Wint &b){return !(a<b);} 67 Wint& operator+=(Wint &a,const Wint &b) 68 { 69 if(a.size()<b.size())a.resize(b.size()); 70 for(int i=0; i!=b.size(); ++i)a[i]+=b[i]; 71 return a.check(); 72 } 73 Wint operator+(Wint a,const Wint &b) 74 { 75 return a+=b; 76 } 77 Wint& operator-=(Wint &a,Wint b) 78 { 79 if(a<b) swap(a,b); 80 for(int i=0; i!=b.size(); a[i]-=b[i],++i) 81 if(a[i]<b[i]) 82 { 83 int j=i+1; 84 while(!a[j])++j; 85 while(j>i) 86 { 87 --a[j]; 88 a[--j]+=10; 89 } 90 } 91 return a.check(); 92 } 93 Wint operator-(Wint a,const Wint &b){return a-=b;} 94 Wint operator*(const Wint &a,const Wint &b) 95 { 96 Wint n; 97 n.assign(a.size()+b.size()-1,0); 98 for(int i=0; i!=a.size(); ++i) 99 for(int j=0; j!=b.size(); ++j) 100 n[i+j]+=a[i]*b[j]; 101 return n.check(); 102 } 103 Wint& operator*=(Wint &a,const Wint &b){return a=a*b;} 104 Wint divmod(Wint &a,const Wint &b) 105 { 106 Wint ans; 107 for(int t=a.size()-b.size(); a>=b; --t) 108 { 109 Wint d; 110 d.assign(t+1,0); 111 d.back()=1; 112 Wint c=b*d; 113 while(a>=c) 114 { 115 a-=c; 116 ans+=d; 117 } 118 } 119 return ans; 120 } 121 Wint operator/(Wint a,const Wint &b){return divmod(a,b);} 122 Wint& operator/=(Wint &a,const Wint &b){return a=a/b;} 123 Wint& operator%=(Wint &a,const Wint &b){divmod(a,b);return a;} 124 Wint operator%(Wint a,const Wint &b){return a%=b;} 125 Wint pow(const Wint &n,const Wint &k) 126 { 127 if(k.empty())return 1; 128 if(k==2)return n*n; 129 if(k.back()%2)return n*pow(n,k-1); 130 return pow(pow(n,k/2),2); 131 }
1 namespace IO 2 { 3 template<typename T> 4 inline void read(T &x) 5 { 6 x=0; 7 int f=0; 8 char ch=getchar(); 9 while(!(ch>='0'&&ch<='9')){f|=(ch=='-');ch=getchar();} 10 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} 11 x=f?-x:x; 12 } 13 template<typename T> 14 inline void write(T x) 15 { 16 if(x<0) {putchar('-');x=-x;} 17 if(x>=10) write(x/10); 18 putchar(x%10+'0'); 19 } 20 }
1 //效果好 2 #pragma GCC diagnostic error "-std=c++14" 3 #pragma GCC target("avx") 4 #pragma GCC optimize(3) 5 #pragma GCC optimize("Ofast") 6 //效果不太好 7 #pragma GCC diagnostic error "-std=c++14" 8 #pragma GCC target("avx") 9 #pragma GCC optimize(3) 10 #pragma GCC optimize("Ofast") 11 #pragma GCC optimize("inline") 12 #pragma GCC optimize("-fgcse") 13 #pragma GCC optimize("-fgcse-lm") 14 #pragma GCC optimize("-fipa-sra") 15 #pragma GCC optimize("-ftree-pre") 16 #pragma GCC optimize("-ftree-vrp") 17 #pragma GCC optimize("-fpeephole2") 18 #pragma GCC optimize("-ffast-math") 19 #pragma GCC optimize("-fsched-spec") 20 #pragma GCC optimize("unroll-loops") 21 #pragma GCC optimize("-falign-jumps") 22 #pragma GCC optimize("-falign-loops") 23 #pragma GCC optimize("-falign-labels") 24 #pragma GCC optimize("-fdevirtualize") 25 #pragma GCC optimize("-fcaller-saves") 26 #pragma GCC optimize("-fcrossjumping") 27 #pragma GCC optimize("-fthread-jumps") 28 #pragma GCC optimize("-funroll-loops") 29 #pragma GCC optimize("-fwhole-program") 30 #pragma GCC optimize("-freorder-blocks") 31 #pragma GCC optimize("-fschedule-insns") 32 #pragma GCC optimize("inline-functions") 33 #pragma GCC optimize("-ftree-tail-merge") 34 #pragma GCC optimize("-fschedule-insns2") 35 #pragma GCC optimize("-fstrict-aliasing") 36 #pragma GCC optimize("-fstrict-overflow") 37 #pragma GCC optimize("-falign-functions") 38 #pragma GCC optimize("-fcse-skip-blocks") 39 #pragma GCC optimize("-fcse-follow-jumps") 40 #pragma GCC optimize("-fsched-interblock") 41 #pragma GCC optimize("-fpartial-inlining") 42 #pragma GCC optimize("no-stack-protector") 43 #pragma GCC optimize("-freorder-functions") 44 #pragma GCC optimize("-findirect-inlining") 45 #pragma GCC optimize("-fhoist-adjacent-loads") 46 #pragma GCC optimize("-frerun-cse-after-loop") 47 #pragma GCC optimize("inline-small-functions") 48 #pragma GCC optimize("-finline-small-functions") 49 #pragma GCC optimize("-ftree-switch-conversion") 50 #pragma GCC optimize("-foptimize-sibling-calls") 51 #pragma GCC optimize("-fexpensive-optimizations") 52 #pragma GCC optimize("-funsafe-loop-optimizations") 53 #pragma GCC optimize("inline-functions-called-once") 54 #pragma GCC optimize("-fdelete-null-pointer-checks")
1 void getphi() 2 { 3 int i,j; 4 phi[1]=1; 5 for (i=2;i<=N;i++) 6 { 7 if (!mark[i]) {prime[++tot]=i;phi[i]=i-1;} 8 for (j=1;j<=tot;j++) 9 { 10 if(i*prime[j]>N) break; 11 mark[i*prime[j]]=1; 12 if (i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break; } 13 else phi[i*prime[j]]=phi[i]*(prime[j]-1); 14 } 15 } 16 }
1 #include<cstdio> 2 struct node 3 { 4 int data; 5 node* lchild; 6 node* rchild; 7 }; 8 node* newNode(int v) 9 { 10 node* Node=new node; 11 Node->data=v; 12 Node->lchild=Node->rchild=NULL; 13 return Node; 14 } 15 void insert(node* &root,int x) 16 { 17 if(root==NULL){root=newNode(x);return;} 18 if(x==root->data) return; 19 else if(x<root->data) insert(root->lchild,x); 20 else insert(root -> rchild,x); 21 } 22 node* Create(int data[],int n) 23 { 24 node* root=NULL; 25 for(int i=0;i<n;i++) insert(root,data[i]); 26 return root; 27 } 28 node* findMax(node* root) 29 { 30 while(root->rchild!=NULL){root=root->rchild;} 31 return root; 32 } 33 node* findMin(node* root) 34 { 35 while(root->lchild!=NULL) root=root->lchild; 36 return root; 37 } 38 void deleteNode(node* &root,int x){ 39 if(root == NULL) return; 40 if(root->data==x) 41 { 42 if(root->lchild==NULL&&root->rchild==NULL) root=NULL; 43 else if(root->lchild!=NULL) 44 { 45 node* pre=findMax(root->lchild); 46 root->data=pre->data; 47 deleteNode(root->lchild,pre->data); 48 } 49 else 50 { 51 node* post=findMin(root->rchild); 52 root->data=post->data; 53 deleteNode(root->rchild,post->data); 54 } 55 } 56 else if (root->data>x) deleteNode(root->lchild,x); 57 else deleteNode(root->rchild,x); 58 }
1 #include<iostream> 2 using namespace std; 3 typedef unsigned long long ull; 4 ull fact[20]={1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000}; 5 int A[15]; 6 int main() 7 { 8 int rank=0,s; 9 int N; 10 cin>>N; 11 for (int i=0;i<N;i++) cin>>A[i]; 12 for(int i=1;i<=N;i++) 13 { 14 int s=0; 15 for (int j=i+1;j<=N;j++) s+=(A[j]<A[i]); 16 rank+=s*fact[N-i]; 17 } 18 cout<<rank; 19 return 0;
1 typedef unsigned long long ull; 2 const ull fact[20]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000}; 3 ull Cantor(int n,int a[15]) 4 { 5 ull ans=0; 6 for (int i=0;i<n;i++) 7 { 8 int x=0; 9 for(int j=i+1;j<n;j++) 10 if (a[j]<a[i]) ++x; 11 ans+=x*fact[n-i-1]; 12 } 13 return ans+1; 14 }
1 typedef unsigned long long ull; 2 const ull fac[20]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000}; 3 void CantorReverse(long long r,int len,int a[]) //康托展开逆运算,结果在a中 4 { 5 r--; 6 int vis[20]={0}; 7 for(int i=1;i<=len;i++) 8 { 9 long long tp=r/fac[len-i]; 10 r-=tp*fac[len-i]; 11 int j; 12 for(j=1;j<=len;j++) 13 if(!vis[j]){if(!tp) break;--tp;} 14 vis[j]=1; 15 a[i]=j; 16 } 17 }
1 int binarySearch(int list[],int left,int right,int number) 2 { 3 if(list==NULL) return -1; 4 int index=0; 5 int mid=(right+left)/2; 6 if(left>right) 7 return -1; 8 if(number==list[mid]) 9 { 10 index=mid; 11 return index; 12 } 13 else if(number>list[mid]) binarySearch(list,mid+1,right,number); 14 else binarySearch(list,left,mid-1,number); 15 }
1 int binarySearch(int list[],int left,int right,int number) 2 { 3 if(list==NULL) return -1; 4 while(left<right) 5 { 6 int mid=(right+left)/2; 7 if (list[mid] == number) return mid; 8 else if (number > list[mid]) left=mid+1; 9 else if (number < list[mid]) right=mid-1; 10 } 11 return -1; 12 }
1 int sum[500005*3+10]; 2 int lowbit(int x) {return x&(-x);} 3 inline void add(int x,int c){while (x<=n) {sum[x]+=c;x+=lowbit(x);}} 4 inline int query(int x) 5 { 6 int ans=0; 7 while (x>0) 8 { 9 ans+=sum[x]; 10 x-=lowbit(x); 11 } 12 return ans; 13 } 14 inline void Make(int a[],const int n) 15 { 16 int pre[N]; 17 pre[1]=a[1]; 18 for (int i=2;i<=n;i++) pre[i]=pre[i-1]+a[i]; 19 for (int i=1;i<=n;i++) sum[i]=pre[i]-pre[i-lowbit(i)]; 20 } 21 inline int SectionSum(int x,int y){return query(y)-query(x-1);}
1 dp[0]=1; 2 for (int =1;i<n;i++) 3 { 4 dp[i]=1; 5 for (int j=0;j<i;j++) 6 if (x[i]>x[j]&&dp[j]+1>dp[i]) dp[i]=dp[j]+1; 7 } 8 for (int i=max_len=0;i<n;i++) 9 max_len=max(max_len,dp[i]);
1 int len_a=a.size(),len_b=b.size(); 2 for(int i=0;i<len_a;i++) 3 for(int j=0;j<len_b;j++) 4 if (a.at(i)==b.at(j)) dp[i+1][j+1]=dp[i][j]+1; 5 else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]); 6 cout<<dp[len_a][len_b];
1 //i1,i2为两序列,n,m为序列长度 2 for (int a=1;a<=m;a++) 3 { 4 int Max(0); 5 for (int b=1;b<=n;b++) 6 { 7 if (i1[a]>i2[b]&&dp[a-1][b]>Max) Max=dp[a-1][b]; 8 if (i1[a]!=i2[b]) dp[a][b]=dp[a-1][b]; 9 if (i1[a]==i2[b]) dp[a][b]=Max+1; 10 } 11 }
1 大根堆:priority_queue<DataType> Name; 2 3 小根堆:priority_queue<DataType,vector<DataType>,greater<DataType> > Name;
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 const int maxn=105; 6 const int INF=0x3f3f3f3f; 7 typedef long long LL; 8 struct edge 9 { 10 int en,len,next; 11 }E[maxn*maxn]; 12 struct node 13 { 14 int id,len; 15 node(int id1=0,int len1=0){id=id1;len=len1;} 16 friend bool operator<(const node& x,const node& y){return x.len>y.len;} 17 }; 18 int head[maxn],num; 19 int n,m; 20 int vis[maxn],dis[maxn]; 21 void init(){memset(head,-1,sizeof(head));num=0;} 22 void add_edge(int st,int en,int len) 23 { 24 E[num].en=en; 25 E[num].len=len; 26 E[num].next=head[st]; 27 head[st]=num++; 28 } 29 void Dijkstra(int st) 30 { 31 for (int i=1;i<=n;i++) vis[i]=0,dis[i]=INF; 32 dis[st]=0; 33 priority_queue<node> Q; 34 Q.push(node(st,0)); 35 while (!q.empty()) 36 { 37 node now=q.top(); 38 Q.pop(); 39 if (vis[now.id]==1) continue; 40 vis[now.id]=1; 41 for (int i=head[now.id];i!=-1;i=E[i].next) 42 { 43 int en=E[i].en; 44 int len=E[i].len; 45 if (!vis[en]&&(dis[en]>dis[now.id]+len)) 46 { 47 dis[en]=dis[now.id]+len; 48 Q.push(node(en,dis[en])); 49 } 50 } 51 } 52 } 53 int main() 54 { 55 init(); 56 57 return 0; 58 }
1 #include<cstring> 2 #include<iostream> 3 #include<cstdio> 4 #include<queue> 5 using namespace std; 6 const int maxx=1001,maxn=1001; 7 struct Edge 8 { 9 int y,to,next; 10 }e[maxn],e1[maxn]; 11 int head[maxx],tot,head1[maxx],cnt; 12 int n,m,dis[maxx],S,T,K,vis[maxx]; 13 inline void add(int x,int y,int z){e[++tot]=(Edge){y,z,head[x]};head[x]=tot;} 14 inline void add1(int x,int y,int z){e1[++cnt]=(Edge){y,z,head1[x]};head1[x]=cnt;} 15 priority_queue<pair<int,int> >q; //大根堆插入相反数 16 inline void dijkstra() //处理估价函数 17 { 18 memset(dis,0x3f,sizeof dis); 19 memset(vis,-1,sizeof vis); 20 dis[T]=0; 21 q.push(make_pair(0,T)); 22 while (!q.empty()) 23 { 24 int x=q.top().second; 25 q.pop(); 26 if (!vis[x])continue; 27 vis[x]=0; 28 for (int i=head1[x];i;i=e1[i].next) 29 { 30 int y=e1[i].y; 31 if (dis[y]>dis[x]+e1[i].to) 32 { 33 dis[y]=dis[x]+e1[i].to; 34 q.push(make_pair(-dis[y],y)); 35 } 36 } 37 } 38 } 39 inline void A_star() 40 { 41 if (dis[S]==dis[0]){puts("-1");return;} 42 if (S==T) K++; 43 memset(vis,0,sizeof vis); 44 q.push(make_pair(-dis[S],S)); 45 while (q.size()) 46 { 47 int x=q.top().second,d=-q.top().first-dis[x]; 48 q.pop(); 49 vis[x]++; 50 if (vis[T]==K){printf("%d",d);return;} 51 for (int i=head[x];i;i=e[i].next) 52 { 53 int y=e[i].y; 54 if (vis[y]!=K) q.push(make_pair(-d-e[i].to-dis[y],y)); 55 } 56 } 57 puts("-1"); 58 } 59 int main() 60 { 61 cin>>n>>m; 62 for(int i=1;i<=m;i++) 63 { 64 int x,y,z; 65 cin>>x>>y>>z; 66 add(x,y,z); add1(y,x,z); 67 } 68 cin>>S>>T>>K; 69 dijkstra(); 70 A_star(); 71 return 0; 72 }
1 template<typename T> 2 inline void Radix_Sort(T* a,T* b) 3 { 4 register const int n=b-a; 5 size_t size_of_type=sizeof(T); 6 size_t num_of_buc=size_of_type>>1; 7 unsigned** r=new unsigned *[num_of_buc]; 8 register int i,k; 9 for(i=0; i<num_of_buc;i++) 10 r[i]=new unsigned [0x10000],memset(r[i],0,0x10000*sizeof(unsigned)); 11 register unsigned short tmp_us; 12 register T *j,*tar; 13 for (k=0;k<num_of_buc;++k) 14 for (j=a+1,tar=a+1+n;j!=tar;++j) 15 tmp_us=*(((unsigned short*)j)+k),++r[k][tmp_us]; 16 for (k=0;k<num_of_buc;++k) 17 for (i=1;i<=0xffff;++i) 18 r[k][i]+=r[k][i-1]; 19 for (k=0;k<num_of_buc;k+=0x2) 20 { 21 i=k; 22 for (j=a+n;j!=a;--j) 23 tmp_us=*(((unsigned short*)j)+i),b[r[i][tmp_us]--]=*j; 24 i|=1; 25 if (i==num_of_buc) break; 26 for (j=b+n;j!=b;--j) 27 tmp_us=*(((unsigned short*)j)+i),a[r[i][tmp_us]--]=*j; 28 } 29 for(int i=0;i<num_of_buc;i++) delete[] r[i]; 30 delete [] r; 31 }
1 void us(int a[],const int n) 2 { 3 int t[n]; 4 copy(a,a+n,t); 5 sort(t+1,t+n+1); 6 m=unique(t+1,t+n+1)-t-1; 7 for (int i=1;i<=n;i++) 8 a[i]=lower_bound(t+1,t+m+1,a[i])-t; 9 }
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 const int N=1001; 5 int a[N],rr[N],ans; 6 void msort(int l,int r) 7 { 8 if (r-l>1) 9 { 10 int mid=(l+r)>>1; 11 msort(l,mid); 12 msort(mid,r); 13 int x=l,y=mid,z=l; 14 while (x<mid||y<r) 15 { 16 if (y>=r||(x<mid&&a[x]<=a[y])) rr[z++]=a[x++]; 17 else rr[z++]=a[y++],ans+=mid-x; 18 } 19 for (int i=l;i<r;i++) a[i]=rr[i]; 20 } 21 } 22 int main() 23 { 24 int n; 25 cin>>n; 26 for (int i=0;i<n;i++) cin>>a[i]; 27 msort(0,n); 28 cout<<ans; 29 return 0; 30 }
1 void MakeInv(int n,int p) 2 { 3 inv[1]=1; 4 for(int i=2;i<=n;i++) 5 inv[i]=1ll*(p-p/i)*inv[p%i]%p; 6 }
1 #include<iostream> 2 #include<cstring> 3 typedef long long ll; 4 const ll MOD=1000000007; 5 using namespace std; 6 struct Mat{ll m[101][101];}a,e; 7 ll n,p; 8 Mat Mul(Mat x,Mat y) 9 { 10 Mat c; 11 for(int i=1;i<=n;i++) 12 for(int j=1;j<=n;j++) 13 c.m[i][j]=0; 14 for(int i=1;i<=n;i++) 15 for(int j=1;j<=n;j++) 16 for(int k=1;k<=n;k++) 17 c.m[i][j]=c.m[i][j]%MOD+x.m[i][k]*y.m[k][j]%MOD; 18 return c; 19 } 20 Mat qpow(Mat x,ll b) 21 { 22 Mat ans=e; 23 while (b) 24 { 25 if (b&1) ans=Mul(ans,x); 26 x=Mul(x,x); 27 b>>=1; 28 } 29 return ans; 30 } 31 32 int main() 33 { 34 cin>>n>>p; 35 for(int i=1;i<=n;i++) 36 for(int j=1;j<=n;j++) 37 cin>>a.m[i][j]; 38 for(int i=1;i<=n;i++) 39 e.m[i][i]=1; 40 Mat ans=qpow(a,p); 41 for(int i=1;i<=n;i++) 42 { 43 for(int j=1;j<=n;j++) 44 cout<<ans.m[i][j]%MOD<<' '; 45 cout<<'\n'; 46 } 47 return 0; 48 }
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int n,m,he,ta,T; 5 int f[7005],q[7005],num[7005]; 6 int main() 7 { 8 int w,v,s; 9 scanf("%d%d",&m,&n); 10 for (int i=1;i<=n;i++) 11 { 12 scanf("%d%d%d",&w,&v,&s); 13 if (s>m/w) s=m/w; 14 for (int d=0;d<w;d++) 15 { 16 he=ta=1; 17 for (int j=0;j<=(m-d)/w;j++) 18 { 19 int tmp=f[j*w+d]-v*j; 20 while (he<ta&&q[ta-1]<=tmp) --ta; 21 q[ta]=tmp,num[ta++]=j; 22 while (he<ta&&j-num[he]>s) ++he; 23 f[j*w+d]=max(f[j*w+d],q[he]+v*j); 24 } 25 } 26 } 27 printf("%d",f[m]); 28 return 0; 29 }
1 //以"滑动窗口"为例 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 using namespace std; 6 const int N=1e6+5; 7 int n,k,a[N],q[N]; 8 int main() 9 { 10 scanf("%d%d",&n,&k); 11 for (int i=1;i<=n;++i) scanf("%d",&a[i]); 12 int front=1,rear=0; 13 for (int i=1;i<=n;++i) 14 { 15 while (front<=rear&&q[front]+k<=i) ++front; 16 while (front<=rear&&a[i]<a[q[rear]]) --rear; 17 q[++rear]=i; 18 if (i>=k) printf("%d ",a[q[front]]); 19 } 20 putchar('\n'); 21 memset(q,0,sizeof(q)); //q多次利用 22 front=1,rear=0; 23 for (int i=1; i<=n;++i) 24 { 25 while (front<=rear&&q[front]+k<=i) ++front; 26 while (front<=rear&&a[i]>a[q[rear]]) --rear; 27 q[++rear]=i; 28 if (i>=k) printf("%d ",a[q[front]]); 29 } 30 return 0; 31 }
1 //洛谷P1247 2 #include<cstdio> 3 int n,a[500005]; 4 int main() 5 { 6 scanf("%d",&n); 7 int check=0; 8 for (int i=1;i<=n;i++){scanf("%d",&a[i]);check^=a[i];} 9 if (!check){printf("lose");return 0;} 10 for (int i=1;i<=n;i++) 11 { 12 if ((check^a[i])<a[i]) 13 { 14 printf("%d %d\n",a[i]-(check^a[i]),i); 15 for (int j=1;j<=n;j++) 16 (j!=i)?printf("%d ",a[j]):printf("%d ",check^a[i]); 17 break; 18 } 19 } 20 return 0; 21 }