L1-039 古风排版
#include<bits/stdc++.h> #define ll long long #define endl ' ' using namespace std; const int INF=0x3f3f3f3f; const int mod=1e9+7; const int maxn=5005; char libm[maxn][maxn]; int main(){ ll n;cin>>n; getchar(); string a; getline(cin,a); double N=n*1.0; double x=a.length()/N; ll len=ceil(x); ll cnt=0; for(ll i=len;i>=1;i--){ for(ll j=1;j<=n;j++){ if(cnt<a.length()) {libm[j][i]=a[cnt];cnt++;} else libm[j][i]=' '; } } for(ll i=1;i<=n;i++){ for(ll j=1;j<=len;j++){ cout<<libm[i][j]; } cout<<endl; } }
L1-049 天梯赛座位分配
题解：分组模拟
#include<bits/stdc++.h> #define ll long long #define endl ' ' using namespace std; int a[1005]; vector<ll> libm[100005]; int main() { int n;cin>>n; ll sum=0,m=n; for(int i=1;i<=n;i++){ cin>>a[i];a[i]*=10; sum+=a[i]; } ll now=1; ll pre=0; while(sum){ ll ct=0; for(ll i=1;i<=n;i++){ if(a[i]) ct++; } for(ll i=1;i<=n;i++){ if(a[i]&&ct>1){ libm[i].push_back(now); now++; a[i]--; sum--; } else if(a[i]&&ct==1){ if(!pre&&i!=1) now+=1; libm[i].push_back(now); pre++; now+=2; a[i]--; sum--; } } } if(n>1){ for(ll i=1;i<=n;i++){ cout<<"#"<<i<<endl; ll cnt=0; for(ll j=0;j<libm[i].size();j++){ cnt++; if(cnt%10!=0) cout<<libm[i][j]<<" "; else if(cnt%10==0) cout<<libm[i][j]<<endl; } } }else if(n==1){ cout<<"#1"<<endl; ll cnt=0; for(ll j=0;j<libm[1].size();j++){ cnt++; if(cnt%10!=0) cout<<libm[1][j]<<" "; else if(cnt%10==0) cout<<libm[1][j]<<endl; } }else{ return 0; } }
L2-004 这是二叉搜索树吗？
题解：根据性质，对于一个BST来说，其root的左子树的结点<root,其root的右子树结点>=root。所以按照先序遍历的性质我们可以得知：在先序遍历完后的框架数组中，数组首永远是根节点。所以对于[root+1,tail]中我们需要找到哪些结点为它的左子树结点，哪些结点是它的右子树结点。我们用dfs框出范围然后分治解决即可。
难点1：如何把先序遍历后的结果转化成后序遍历？
难点2：如何判断该BST合法？
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; int a[maxn];bool flag; vector<int> pos; void dfs(int root,int tail){ if(root>tail) return ; int i=root+1,j=tail; if(!flag){ while(i<=tail&&a[i]<a[root]) i++; while(j>root&&a[j]>=a[root]) j--; }else{ while(i<=tail&&a[i]>=a[root]) i++; while(j>root&&a[j]<a[root]) j--; } if(i-j!=1) return ; dfs(root+1,i-1); dfs(j+1,tail); pos.pb(a[root]); } int main(){ int n;cin>>n;flag=0; rep(i,1,n) cin>>a[i]; dfs(1,n); if(pos.size()!=n){ flag=1; pos.clear(); dfs(1,n); } if(pos.size()!=n){ puts("NO");return 0; }else{ puts("YES"); rep(i,0,n-2) cout<<pos[i]<<" "; cout<<pos[n-1]<<endl; } }
L2-006 树的遍历(L2-011玩转二叉树为其改版，思路一致)
题解：根据后序遍历和中序遍历来确定整棵树。后序遍历的性质是(root在最后)；中序遍历的性质是(root在中间);可以先通过后序遍历得知root，然后在中序遍历中确定哪些是root的左子树，哪些是root的右子树，继而确定整棵树。而对于层次遍历无非就是以root为根开始bfs，先把左儿子入队，再入队右儿子。
难点：如何通过已知的两个遍历继而确定整棵树的构造？
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; struct node{ int lson,rson; }p[maxn]; int n,post[maxn],mid[maxn]; int build(int lmid,int rmid,int lpost,int rpost){ if (lmid>rmid||lpost>rpost) return 0; int num=lmid; int aim=post[rpost]; while(mid[num]!=aim) ++num; int len=num-lmid; p[aim].lson=build(lmid,num-1,lpost,lpost+len-1); p[aim].rson=build(num+1,rmid,lpost+len,rpost-1); return aim; } vector<int> vec; void bfs(int root){ queue<int> q; q.push(root); while(!q.empty()){ int now=q.front();q.pop(); vec.pb(now); if(p[now].lson) q.push(p[now].lson); if(p[now].rson) q.push(p[now].rson); } } int main(){ cin>>n; rep(i,1,n) cin>>post[i]; rep(i,1,n) cin>>mid[i]; build(1,n,1,n); bfs(post[n]); int cnt=0; for(auto it:vec){ cout<<it; ++cnt; if(cnt<vec.size()) cout<<" "; } return 0; }
L2-020 功夫传人
难点：祖师爷自己就是得道者，没有弟子，所以需要自己放大自己
#include<bits/stdc++.h> #define endl ' ' #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=1e5+5; int head[maxn],tot; struct E{ int to,next; }edge[maxn<<1]; void add(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int n;double z[maxn],r; double b[maxn];int vis[maxn]; double sum; void dfs(int x,int fa){ for(int i=head[x];i!=-1;i=edge[i].next){ int v=edge[i].to; z[v]=z[x]*1.00*(100-r)/100*b[v]; dfs(v,x); } } int main(){ cin>>n>>z[0]>>r; memset(head,-1,sizeof(head));sum=0; for(int i=0;i<n;i++) b[i]=1.00; rep(i,0,n-1){ int t;cin>>t; if(!t){ cin>>b[i];vis[i]=1; }else{ rep(j,1,t){ int x;cin>>x; add(i,x); } } } z[0]*=b[0]; dfs(0,-1); rep(i,0,n-1){ if(vis[i]) sum+=z[i]; } long long x=floor(sum); cout<<x<<endl; }