《数据结构与算法》编程练习
数据结构与算法(上)
百练2746:约瑟夫问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; vector<int> ve; int main() { n=read();m=read(); for(int i=1;i<=n;i++) ve.push_back(i); int t=0; for(int i=1;i<n;i++) { t=(t+m-1)%ve.size(); ve.erase(ve.begin()+t); } cout<<ve[0]<<endl; return 0; } |
多项式加法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,a,b; map<int,int> p; int main() { T=read(); while(T--) { p.clear(); while(1) { a=read();b=read(); if(b<0)break; p[b]+=a; } while(1) { a=read();b=read(); if(b<0)break; p[b]+=a; } for(map<int,int>::reverse_iterator i=p.rbegin();i!=p.rend();i++) if(i->second)printf("[ %d %d ] ",i->second,i->first); puts(""); } return 0; } |
百练2980:大整数乘法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main() { char a1[500],b1[500]; int a[500],b[500],c[1000],la,lb,lc,x,i,j; while ((scanf("%s",a1))!=EOF) { scanf("%s",b1); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); la=strlen(a1); lb=strlen(b1); for(i=0;i<la;i++) a[la-i]=a1[i]-48; for(i=0;i<lb;i++) b[lb-i]=b1[i]-48; for(i=1;i<=la;i++) { x=0; for(j=1;j<=lb;j++) { c[i+j-1]=a[i]*b[j]+x+c[i+j-1]; x=c[i+j-1]/10; c[i+j-1]%=10; } c[i+lb]=x; } lc=la+lb; while(c[lc]==0&&lc>1)lc--; for(i=lc;i>=1;i--) cout<<c[i]; cout<<endl; } } |
百练2702:密码翻译
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } string str; int main() { int T=read(); while(T--) { getline(cin,str); for(int i=0;i<str.length();i++) if(str[i]>='a'&&str[i]<='y')str[i]++; else if(str[i]>='A'&&str[i]<='Y')str[i]++; else if(str[i]=='z')str[i]='a'; else if(str[i]=='Z')str[i]='A'; cout<<str<<endl; } return 0; } |
百练4077:出栈序列统计
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> using namespace std; int main() { int n,f[20]={0}; cin>>n; f[0]=1;f[1]=1; for(int i=2;i<=n;i++) for(int j=0;j<i;j++) f[i]+=f[j]*f[i-j-1]; cout<<f[n]<<endl; return 0; } |
POJ1686.等价表达式(Lazy Math Instructor)
给每个字母一个随机值,对两个式子做表达式计算
用一个数字栈+操作栈来实现
从左往右,将扫到的数字入数字栈,将扫到的操作与操作栈的栈顶对比优先级
如果当前操作优先级高,将其入栈
否则从数字栈中取出两个数字,用栈顶的操作进行运算
优先级次序是右括号和栈内左括号,运算符,未入栈的左括号
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include<map> #include<queue> #include<cmath> #include<stack> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 10007 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; map<char,int>mp; string a,b; int getint(char a) { if((a<='Z'&&a>='A')||(a<='z'&&a>='a')) { if(mp[a]==0)mp[a]=rand()%10007; return mp[a]; } else if(a>='0'&&a<='9') return a-'0'; else { if(a=='(')return -1; else if(a==')')return -2; else if(a=='(')return -3; else return -4; } } stack<int>num; stack<char>opt; void cal() { if(opt.top()=='#')return; int b,a; b=num.top();num.pop(); a=num.top();num.pop(); if(opt.top()=='+')num.push(a+b); if(opt.top()=='-')num.push(a-b); if(opt.top()=='*')num.push(a*b); opt.pop(); } int sum(string a) { for(int i=0;i<a.size();i++) { if(a[i]==' ')continue; int t=getint(a[i]); if(t>=0)num.push(t); else { int pri=-t; if(a[i]=='(')pri=inf; if(pri<=-getint(opt.top()))cal(); if(a[i]==')') { while(opt.top()!='(')cal(); opt.pop(); } else opt.push(a[i]); } } while(opt.size()!=1)cal(); return num.top(); } int main() { opt.push('#'); T=read(); while(T--) { getline(cin,a); getline(cin,b); if(sum(a)==sum(b))puts("YES"); else puts("NO"); } return 0; } |
百练2121:英语数字转换器
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int ans,tmp,sign=1; string snum[28]={"zero","one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"}; int num[28]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,30,40,50,60,70,80,90}; string sunit[4]={"negative","hundred","thousand","million"}; int unit[4]={-1,100,1000,1000000}; int solve(int x,string a) { for(int i=0;i<28;i++) if(snum[i]==a)return x+num[i]; if(a=="hundred")return x*100; else if(a=="thousand") ans+=x*1000,x=0; else if(a=="million") ans+=x*1000000,x=0; else sign=-1; return 0; } int main() { string a; while(cin>>a) { tmp=solve(tmp,a); char ch=getchar(); if(ch=='\n') { cout<<sign*(tmp+ans)<<endl; tmp=ans=0;sign=1; } } return 0; } |
百练1035:拼写检查
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } string a; vector<string> dic,ans; bool check(string a,string b) { if(a.length()<b.length())swap(a,b); if(a.length()>b.length()+1)return 0; if(a.length()==b.length()) { int cnt=0; for(int i=0;i<a.length();i++) if(a[i]!=b[i])cnt++; return (cnt==1); } else { for(int i=0,j=0;i<a.length();i++) { if(a[i]==b[j])j++; if(j==b.length())return 1; } } return 0; } void solve() { ans.clear(); for(int i=0;i<dic.size();i++) { if(check(dic[i],a))ans.push_back(dic[i]); if(dic[i]==a) { cout<<a<<' '<<"is correct"<<endl; return; } } cout<<a<<":"; for(int i=0;i<ans.size();i++) cout<<' '<<ans[i]; cout<<endl; } int main() { while(cin>>a) { if(a=="#")break; dic.push_back(a); } while(cin>>a) { if(a=="#")break; solve(); } return 0; } |
poj1961.前缀中的周期(Period)
kmp求出fail数组后,前i个的重复子串就是i-fail(i)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,T,l; int fail[1000005]; char ch[1000005]; int main() { while(scanf("%d",&n),n) { T++; printf("Test case #%d\n",T); scanf("%s",ch+1); l=strlen(ch+1); int t=0; for(int i=2;i<=n;i++) { while(ch[t+1]!=ch[i]&&t)t=fail[t]; if(ch[t+1]==ch[i])t++; fail[i]=t; } for(int i=2;i<=n;i++) { if(fail[i]&&i%(i-fail[i])==0) printf("%d %d\n",i,i/(i-fail[i])); } puts(""); } return 0; } |
由中根序列和后根序列重建二叉树
后根序列的最后一个元素是树根,在中根序列中找出这个根,划分左右子树递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<queue> #include<cmath> #include<stack> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int x,rt,cnt; int l[100005],r[100005],v[100005]; void insert(int &k,int x) { if(!k) { k=++cnt;v[k]=x; return; } if(v[k]==x)return; if(x<v[k])insert(l[k],x); else insert(r[k],x); } void dfs(int x) { if(!x)return; printf("%d ",v[x]); dfs(l[x]);dfs(r[x]); } int main() { while(scanf("%d",&x)!=EOF) insert(rt,x); dfs(rt); return 0; } |
实现堆结构
二叉堆模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,T; struct data{ int size; int heap[1000005]; void swim(int x){ while(x>1) { if(heap[x]<heap[x>>1]) swap(heap[x],heap[x>>1]); else break; x>>=1; } } void sink(int x){ while(1) { int mn=x; int l=(x<<1),r=(x<<1|1); if(l<=size&&heap[l]<heap[mn])mn=l; if(r<=size&&heap[r]<heap[mn])mn=r; if(mn!=x) swap(heap[mn],heap[x]),x=mn; else break; } } void push(int a){ heap[++size]=a; swim(size); } void pop(){ heap[1]=heap[size--]; sink(1); } }q; int main() { T=read(); while(T--) { while(q.size)q.pop(); n=read(); for(int i=1;i<=n;i++) { int opt=read(),x; if(opt==1) { x=read(); q.push(x); } else { printf("%d\n",q.heap[1]); q.pop(); } } } return 0; } |
百练4080:Huffman编码树
用小根堆实现哈夫曼树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<map> #include<queue> #include<cmath> #include<stack> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll ans; int n; priority_queue<int,vector<int>,greater<int> >q; int main() { n=read(); for(int i=1;i<=n;i++) { int x=read(); q.push(x); } while(q.size()!=1) { int a,b; a=q.top();q.pop(); b=q.top();q.pop(); ans+=(a+b); q.push(a+b); } cout<<ans; return 0; } |
百练4079:二叉搜索树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<queue> #include<cmath> #include<stack> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int x,rt,cnt; int l[100005],r[100005],v[100005]; void insert(int &k,int x) { if(!k) { k=++cnt;v[k]=x; return; } if(v[k]==x)return; if(x<v[k])insert(l[k],x); else insert(r[k],x); } void dfs(int x) { if(!x)return; printf("%d ",v[x]); dfs(l[x]);dfs(r[x]); } int main() { while(scanf("%d",&x)!=EOF) insert(rt,x); dfs(rt); return 0; } |
表达式•表达式树•表达式求值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include<map> #include<cmath> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,m; struct node{ char c; int pos,dep; node* ch[2]; node(){ ch[0]=ch[1]=NULL; } }; string s; map<char,int> mp; int findopt(int l,int r) { int cnt=0,tmp1=0,tmp2=0; for(int i=r;i>=l;i--) { if(s[i]=='(')cnt++; if(s[i]==')')cnt--; if(cnt!=0)continue; if((!tmp1)&&(s[i]=='+'||s[i]=='-'))tmp1=i; if((!tmp2)&&(s[i]=='*'||s[i]=='/'))tmp2=i; } if(tmp1)return tmp1; return tmp2; } node* build(int l,int r) { if(l==r) { node* t=new node; t->c=s[l]; return t; } node *pre=new node; int t=findopt(l,r); if(t==0)return build(l+1,r-1); pre->c=s[t]; pre->ch[0]=build(l,t-1); pre->ch[1]=build(t+1,r); return pre; } int mxdep; void dfs(node *x) { if(x==NULL)return; if(x->ch[0]) { x->ch[0]->pos=(x->pos<<1)-1; x->ch[0]->dep=x->dep+1; } if(x->ch[1]) { x->ch[1]->pos=(x->pos<<1); x->ch[1]->dep=x->dep+1; } mxdep=max(mxdep,x->dep); dfs(x->ch[0]);dfs(x->ch[1]); printf("%c",x->c); } char st[105][200005]; void print(node *x) { if(x==NULL)return; int dep=mxdep-x->dep+1,pos=(1<<(dep-1))+(1<<dep)*(x->pos-1); st[x->dep*2][pos]=x->c; if(x->ch[0])st[x->dep*2+1][pos-1]='/'; if(x->ch[1])st[x->dep*2+1][pos+1]='\\'; print(x->ch[0]);print(x->ch[1]); return; } int cal(node *x) { if(mp.count(x->c))return mp[x->c]; int a=cal(x->ch[0]),b=cal(x->ch[1]); if(x->c=='-')return a-b; if(x->c=='+')return a+b; if(x->c=='*')return a*b; if(x->c=='/')return a/b; return 0; } int main() { cin>>s; n=s.length(); s=" "+s; cin>>m; for(int i=1;i<=m;i++) { char c;cin>>c; cin>>mp[c]; } node *root=build(1,n); root->pos=1; dfs(root); puts(""); print(root); for(int i=0;i<=mxdep*2;i++) { for(int j=1;j<=200000;j++) if(!st[i][j])st[i][j]=' '; for(int j=200000;st[i][j]==' ';j--)st[i][j]=0; printf("%s\n",st[i]+1); } printf("%d\n",cal(root)); return 0; } |
森林的带度数层次序列存储
从左往右扫过带度数层次序列,一个度数为x的结点决定之后x个连续结点的父亲
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<queue> #include<cmath> #include<stack> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,last,top,cur; int d[30],st[30],fa[30]; vector<int>e[30]; string a; void dfs(int x) { for(int i=0;i<e[x].size();i++) dfs(e[x][i]); printf("%c ",x+'A'); } int main() { T=read(); while(T--) { getline(cin,a); while(a[0]<'A'||a[0]>'Z')getline(cin,a); top=0;cur=1; for(int i=0;i<a.length();i++) { if(a[i]>='A'&&a[i]<='Z') { last=a[i]-'A'; st[++top]=last; } else if(a[i]!=' ') d[last]=d[last]*10+a[i]-'0'; } for(int i=1,k=1;i<=top;i++) for(int j=1;j<=d[st[i]];j++) fa[++k]=st[i]; for(int i=2;i<=top;i++) e[fa[i]].push_back(st[i]); dfs(st[1]); } return 0; } |
poj1182:食物链(food chain)
带权并查集
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans; int d[50005],fa[50005]; //x=y x->y y->x int find(int x) { if(x==fa[x])return x; int t=fa[x];fa[x]=find(fa[x]); d[x]=(d[x]+d[t])%3; return fa[x]; } void un(int x,int y,int f) { int fx=find(x),fy=find(y); fa[fx]=fy; d[fx]=(d[y]-f-d[x]+3)%3; } int main() { n=read();m=read(); int f,u,v; for(int i=1;i<=n;i++)fa[i]=i; while(m--) { f=read(),u=read(),v=read(); if(u>n||v>n||(f==2&&u==v))ans++; else { if(find(u)==find(v)) { if(f==1&&d[u]!=d[v])ans++; if(f==2&&(d[u]+1)%3!=d[v])ans++; } else un(u,v,f-1); } } printf("%d\n",ans); return 0; } |
百练4083:我爱北大
floyd求最短路,同时记录最短路上的最后一个结点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<map> #include<queue> #include<cmath> #include<stack> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,q,r; int dis[105][105],pre[105][105]; string str[105],str1,str2; map<string,int>mp; vector<int>ans; void solve(int p,int q) { ans.push_back(q); if(p==q)return; q=pre[p][q]; solve(p,q); } int main() { n=read(); for(int i=1;i<=n;i++) { cin>>str[i]; mp[str[i]]=i; } q=read(); memset(dis,127/3,sizeof(dis)); for(int i=1;i<=q;i++) { int x,p1,p2; cin>>str1>>str2;x=read(); p1=mp[str1],p2=mp[str2]; if(dis[p1][p2]>x) { dis[p1][p2]=dis[p2][p1]=x; pre[p1][p2]=p1; pre[p2][p1]=p2; } } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(dis[i][k]+dis[k][j]<dis[i][j]) { dis[i][j]=dis[i][k]+dis[k][j]; pre[i][j]=pre[k][j]; } r=read(); while(r--) { cin>>str1>>str2; int p=mp[str1],q=mp[str2]; ans.clear(); solve(p,q); reverse(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) { cout<<str[ans[i]]; if(i!=ans.size()-1)cout<<"->("<<dis[ans[i]][ans[i+1]]<<")->"; } puts(""); } return 0; } |
百练4084:拓扑排序
用小根堆来实现字典序最小的拓扑序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<queue> #include<cmath> #include<stack> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int d[100005]; vector<int>e[100005]; priority_queue<int,vector<int>,greater<int> >q; int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); e[u].push_back(v); d[v]++; } for(int i=1;i<=n;i++) if(!d[i])q.push(i); while(!q.empty()) { int x=q.top();q.pop(); printf("v%d ",x); for(int i=0;i<e[x].size();i++) { int y=e[x][i]; d[y]--; if(!d[y])q.push(y); } } return 0; } |
poj2049:Finding Nemo
建图后01-bfs,由0的边扩展的点放在队首,1的边扩展的点放在队尾
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include<map> #include<cmath> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,m; int mp[50005][4]; deque<int>q; int xx[4]={0,1,0,-1},yy[4]={-1,0,1,0}; int dis[205][205],p[205][205],X[50005],Y[50005]; void bfs() { q.push_back(0); dis[0][0]=0; while(!q.empty()) { int now=q.front();q.pop_front(); int x=X[now],y=Y[now]; for(int d=0;d<4;d++) { int nx=x+xx[d],ny=y+yy[d]; if(mp[now][d]==inf||nx<0||ny<0||nx>=200||ny>=200)continue; if(dis[nx][ny]==-1) { dis[nx][ny]=dis[x][y]+mp[now][d]; if(mp[now][d]==0)q.push_front(p[nx][ny]); else q.push_back(p[nx][ny]); } } } } int main() { int cnt=0; for(int i=0;i<=200;i++) for(int j=0;j<=199;j++) { p[i][j]=cnt; X[cnt]=i,Y[cnt]=j;cnt++; } while(scanf("%d%d",&n,&m)!=EOF) { if(n==-1)return 0; memset(dis,-1,sizeof(dis)); memset(mp,0,sizeof(mp)); int x,y,d,t; for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&x,&y,&d,&t); if(d==0) for(int j=0;j<t;j++) { mp[p[x+j][y]][0]=inf; mp[p[x+j][y-1]][2]=inf; } else for(int j=0;j<t;j++) { mp[p[x][y+j]][3]=inf; mp[p[x-1][y+j]][1]=inf; } } for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&d); if(d==0) { mp[p[x][y]][0]=1; mp[p[x][y-1]][2]=1; } else { mp[p[x][y]][3]=1; mp[p[x-1][y]][1]=1; } } bfs(); double px,py; scanf("%lf%lf",&px,&py); if(px<0||py<0||px>199||py>199)puts("0"); else printf("%d\n",dis[(int)px][(int)py]); } return 0; } |
数据结构与算法(下)
距离排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int x[15],y[15],z[15]; struct data{ int a,b; int dis; friend bool operator<(data a,data b){ return a.dis<b.dis; } }a[105]; int main() { n=read(); for(int i=1;i<=n;i++) x[i]=read(),y[i]=read(),z[i]=read(); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { a[++m].a=i,a[m].b=j; a[m].dis=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]); } for(int i=1;i<=m;i++) for(int j=1;j<m;j++) if(a[j]<a[j+1])swap(a[j],a[j+1]); for(int i=1;i<=m;i++) printf("(%d,%d,%d)-(%d,%d,%d)=%.2lf\n",x[a[i].a],y[a[i].a],z[a[i].a],x[a[i].b],y[a[i].b],z[a[i].b],sqrt(a[i].dis)); return 0; } |
数据筛选
快速选择函数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K; int a[1000005]; int main() { n=read();K=read(); for(int i=1;i<=n;i++) a[i]=read(); nth_element(a+1,a+K,a+n+1); printf("%d\n",a[K]); return 0; } |
数组取数
对每个数\(a_i\),二分查询\(a_i-T\),注意\(T=0\)的情况
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans; vector<int>a; int main() { n=read();m=read(); for(int i=1;i<=n;i++) { int x=read(); a.push_back(x); } sort(a.begin(),a.end()); a.push_back(inf); if(m==0) { for(int i=1;i<a.size()-1;i++) if(a[i]==a[i-1]&&a[i]!=a[i+1]) ans++; } else { a.erase(unique(a.begin(),a.end()),a.end()); for(int i=0;i<a.size();i++) { if(*lower_bound(a.begin(),a.end(),a[i]-m)==a[i]-m) ans++; } } printf("%d\n",ans); return 0; } |
牛的选举
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K; struct data{ int a,b,id; }a[50005]; bool cmp1(data a,data b) { return a.a>b.a; } bool cmp2(data a,data b) { return a.b>b.b; } int main() { n=read();K=read(); for(int i=1;i<=n;i++) a[i].a=read(),a[i].b=read(); for(int i=1;i<=n;i++) a[i].id=i; sort(a+1,a+n+1,cmp1); sort(a+1,a+K+1,cmp2); printf("%d\n",a[1].id); return 0; } |
The Peanuts
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; int m,n,K; int ans,cnt; struct data{ int x,y,v; friend bool operator<(data a,data b){ return a.v>b.v; } }a[2505]; int dis(int x,int y) { return abs(a[x].x-a[y].x)+abs(a[x].y-a[y].y); } int main() { T=read(); while(T--) { ans=cnt=0; m=read();n=read();K=read(); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { int x=read(); if(x!=0) { a[++cnt].x=i;a[cnt].y=j; a[cnt].v=x; } } sort(a+1,a+cnt+1); a[0].y=a[1].y; for(int i=1;i<=cnt;i++) if(K-dis(i-1,i)-1-a[i].x>=0) { ans+=a[i].v; K-=dis(i-1,i)+1; } else break; printf("%d\n",ans); } return 0; } |
DNA排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; struct data{ string str; int num; friend bool operator<(data a,data b){ return a.num<b.num; } }a[105]; int main() { n=read();m=read(); for(int i=1;i<=m;i++) { cin>>a[i].str; for(int j=0;j<n;j++) for(int k=j+1;k<n;k++) if(a[i].str[j]>a[i].str[k]) a[i].num++; } sort(a+1,a+m+1); for(int i=1;i<=m;i++) cout<<a[i].str<<endl; return 0; } |
置换选择排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int a[100005]; priority_queue<int,vector<int>,greater<int> >q; vector<int> ve; int main() { n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++) { int x=read(); q.push(x); } for(int i=1;i<=n;i++) { if(!q.empty()) { if(a[i]>q.top()) q.push(a[i]); else ve.push_back(a[i]); printf("%d ",q.top());q.pop(); } } return 0; } |
败方树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt,rt; queue<int>q; int l[100005],r[100005],fa[100005],lose[100005],win[100005]; int val[100005]; void update(int rt) { int a=l[rt],b=r[rt]; if(val[win[a]]>val[win[b]]) lose[rt]=win[a],win[rt]=win[b]; else lose[rt]=win[b],win[rt]=win[a]; } int merge(int a,int b) { int rt=++cnt; l[rt]=a;r[rt]=b;fa[a]=fa[b]=rt; update(rt); return rt; } void print() { q.push(rt); cout<<val[win[rt]]<<' '; while(!q.empty()) { int x=q.front();q.pop(); if(l[x]>n)q.push(l[x]); if(r[x]>n)q.push(r[x]); printf("%d ",val[lose[x]]); } puts(""); } int main() { n=read();m=read();cnt=n; for(int i=1;i<=n;i++)val[i]=read(); for(int i=1;i<=n;i++)win[i]=i,q.push(i); while(q.size()!=1) { int a=q.front();q.pop(); int b=q.front();q.pop(); q.push(merge(a,b)); } rt=q.front();q.pop(); print(); for(int i=1;i<=m;i++) { int x=read();x++; val[x]=read(); while(fa[x]!=0) x=fa[x],update(x); print(); } return 0; } |
词典
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } string str; map<string,string>mp; int main() { while(getline(cin,str)) { string a,b;a=b=""; bool flag=0; if(str=="")break; for(int i=0;i<str.length();i++) if(str[i]==' ')flag=1; else if(flag)b+=str[i]; else a+=str[i]; mp[b]=a; } while(cin>>str) { if(mp[str]!="")cout<<mp[str]<<endl; else puts("eh"); } return 0; } |
集合运算
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int a[1000005],b[1000005]; int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); m=read(); for(int i=1;i<=m;i++)b[i]=read(); int i=1,j=1; while(i<=n||j<=m) { if(i>n)printf("%d ",b[j]),j++; else if(j>m)printf("%d ",a[i]),i++; else if(a[i]==b[j])i++,j++; else if(a[i]<=b[j])printf("%d ",a[i]),i++; else printf("%d ",b[j]),j++; } return 0; } |
发现它,抓住它
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,m; int fa[200005]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { T=read(); while(T--) { n=read();m=read(); for(int i=1;i<=2*n;i++)fa[i]=i; for(int i=1;i<=m;i++) { char ch[2];int a,b; scanf("%s",ch+1); a=read();b=read(); if(ch[1]=='D') fa[find(a)]=find(b+n),fa[find(b)]=find(a+n); else { if(find(a)==find(b)||find(a+n)==find(b+n)) puts("In the same gang."); else if(find(a)==find(b+n)||find(b)==find(a+n)) puts("In different gangs."); else puts("Not sure yet."); } } } return 0; } |
倒排索引
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; map<string,vector<int> >mp; string str; int main() { n=read(); for(int i=1;i<=n;i++) { int x=read(); for(int j=1;j<=x;j++) { cin>>str; mp[str].push_back(i); } } m=read(); for(int i=1;i<=m;i++) { cin>>str; vector<int> ve=mp[str]; if(ve.size()) { for(int j=0;j<ve.size();j++) if(j==0||ve[j]!=ve[j-1]) printf("%d ",ve[j]); puts(""); } else puts("NOT FOUND"); } return 0; } |
倒排索引查询
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool flag; int n,m,cnt; map<int,int>mp[100005],Hash; int a[105],id[100005]; bool check(int x) { for(int i=1;i<=n;i++) if(a[i]==1&&!mp[x][i])return 0; else if(a[i]==-1&&mp[x][i])return 0; return 1; } int main() { n=read(); for(int i=1;i<=n;i++) { int x=read(); while(x--) { int y=read(); if(!Hash[y]) { Hash[y]=++cnt; id[cnt]=y; } y=Hash[y]; mp[y][i]=1; } } m=read(); for(int i=1;i<=m;i++) { vector<int>ans; for(int j=1;j<=n;j++) a[j]=read(); for(int j=1;j<=cnt;j++) if(check(j)) { ans.push_back(id[j]); flag=1; } if(!ans.size())puts("NOT FOUND"); else { sort(ans.begin(),ans.end()); for(int j=0;j<ans.size();j++) printf("%d ",ans[j]); puts(""); } } return 0; } |
开关问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,ans; int n; int a[35],b[35]; map<int,int>mp; vector<int>e[35]; void dfs(int k,int n,int flag,int sta) { if(k==n+1) { if(flag==0)mp[sta]++; else ans+=mp[sta]; return; } int tmp=sta^(1<<k-1); for(int j=0;j<e[k].size();j++) tmp^=(1<<e[k][j]-1); dfs(k+1,n,flag,sta); dfs(k+1,n,flag,tmp); } int main() { T=read(); while(T--) { n=read(); int st=0,ed=0; ans=0; for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)b[i]=read(); for(int i=1;i<=n;i++) st|=(a[i]<<i-1),ed|=(b[i]<<i-1); while(1) { int u=read(),v=read(); if(u==0)break; e[u].push_back(v); } dfs(1,n/2,0,st^ed); dfs(n/2+1,n,1,0); if(ans)printf("%d\n",ans); else puts("Oh,it's impossible~!!"); mp.clear(); for(int i=1;i<=n;i++)e[i].clear(); } return 0; } |
Binary Search Heap Construction
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,rt,cnt; int l[50005],r[50005],fa[50005]; struct data{ string lab;int pri; friend bool operator<(data a,data b){ return a.lab<b.lab; } }a[50005]; char ch[50005]; void dfs(int x) { if(!x)return; printf("("); dfs(l[x]); cout<<a[x].lab<<a[x].pri; dfs(r[x]); printf(")"); } int main() { while(1) { memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); memset(r,0,sizeof(fa)); n=read();if(n==0)return 0; rt=cnt=0; for(int i=1;i<=n;i++) { scanf("%s",ch+1); a[i].pri=0;a[i].lab=""; int l=strlen(ch+1); for(int j=1;j<=l;j++) { if(ch[j]>='0'&&ch[j]<='9')a[i].pri=a[i].pri*10+ch[j]-'0'; else a[i].lab+=ch[j]; } } sort(a+1,a+n+1); int now=0; for(int i=1;i<=n;i++) if(a[i].pri>=a[rt].pri) { l[i]=rt;fa[rt]=i;rt=i; now=rt; } else { while(a[now].pri<a[i].pri) now=fa[now]; l[i]=r[now];fa[r[now]]=i; r[now]=i;fa[i]=now;now=i; } dfs(rt); puts(""); } return 0; } |
Training little cats
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,K; struct M{ ll a[105][105]; M(){ memset(a,0,sizeof(a)); } friend M operator*(M a,M b){ M c; for(int i=0;i<=n;i++) for(int k=0;k<=n;k++) if(a.a[i][k]) for(int j=0;j<=n;j++) c.a[i][j]+=a.a[i][k]*b.a[k][j]; return c; } friend M operator^(M a,int b){ M ans; for(int i=0;i<=n;i++) ans.a[i][i]=1; for(int i=b;i;i>>=1,a=a*a) if(i&1)ans=ans*a; return ans; } }; int main() { while(1) { n=read();m=read();K=read(); if(!n)break; M I,T;for(int i=0;i<=n;i++)I.a[i][i]=1;T=I; for(int i=1;i<=K;i++) { string opt;int u,v; M tmp=I; cin>>opt;u=read(); if(opt=="g") tmp.a[u][0]=1; else if(opt=="e") tmp.a[u][u]=0; else { v=read(); tmp.a[u][u]=tmp.a[v][v]=0; tmp.a[u][v]=tmp.a[v][u]=1; } T=tmp*T; } T=T^m; for(int i=1;i<=n;i++) cout<<T.a[i][0]<<' '; cout<<endl; } return 0; } |
Shortest Prefixes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt; string a[1005]; int ch[20005][26],val[20005]; void add(int x) { int now=0; for(int i=0;i<a[x].length();i++) { int t=a[x][i]-'a'; if(!ch[now][t])ch[now][t]=++cnt; now=ch[now][t]; val[now]++; } } string query(int x) { string ans=""; int now=0; for(int i=0;i<a[x].length();i++) { int t=a[x][i]-'a'; ans+=t+'a'; now=ch[now][t]; if(val[now]==1)break; } return ans; } int main() { while(cin>>a[++n]) add(n); for(int i=1;i<n;i++) cout<<a[i]<<' '<<query(i)<<endl; return 0; } |
双队列