【CCCC】PAT : 团体程序设计天梯赛-练习集 L3 答案（01-23）

【CCCC】PAT : 团体程序设计天梯赛-练习集 L3 答案

顶着满课，整整一星期，终于咕完了。（；´д｀）ゞ

知识点分类（23）：

1、搜索模拟（5）：BFS，DFS，最短路，路径打印

2、计算几何（5）：找规律，斜率计算，极角排序，三角形面积，三点共线，凸包

3、数据结构（5）：栈，并查集，二叉树，堆，线段树

4、图论模板（4）：Dijkstra，Floyd

4、零零碎碎（4）：数学（1）+物理（1）+DP（2）

Codes

L3-001

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;//RE3,4
const int maxm = 110;
int v[maxn], dp[maxm], pre[maxn][maxm];
bool cmp(int a, int b){return a>b;}
int main(){
  int n, m;
  cin>>n>>m;
  for(int i = 1; i <= n; i++)
    cin>>v[i];
  sort(v+1,v+n+1,cmp);//结论：降序排序=最小字典序
  for(int i = 1; i <= n; i++){
    for(int j = m; j >= v[i]; j--){
      if(dp[j]<=dp[j-v[i]]+v[i]){
        dp[j]=dp[j-v[i]]+v[i]; //选择的代价为v[i],价值为v[i]
        pre[i][j] = 1;//选择了硬币i，标记当前背包位置，记录路径
      }
    }
  }
  if(dp[m]!=m){//容量为m（面额）的背包能获得的最大价值为m。。
    cout<<"No Solution"<<endl;
    return 0;
  }
  //路径打印
  int ok = 0;
  for(int i=n, j=m; i>=1 && j>=0; i--){//注意顺序必须是逆序，和前面相反
    if(pre[i][j]){
      if(!ok){cout<<v[i];ok=1;}
      else cout<<" "<<v[i];
      j -= v[i];//当第i个硬币选中，剩余价值-=vi[i]；
    }
  }
  return 0;
}

L3-002

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
stack<int>stk;
//multiset<int>se;
vector<int>order;
int main(){
  //freopen("ans.cpp","r",stdin);
  int T;  cin>>T;
  while(T--){
    string s;  cin>>s;
    int re = 0;
    if(s=="Push"){
      int x;  cin>>x;
      stk.push(x);
      order.insert(lower_bound(order.begin(), order.end(), stk.top()), stk.top());
    }
    if(s=="Pop"){
      if(stk.size()){
        cout<<stk.top()<<"\n";
        order.erase(lower_bound(order.begin(), order.end(), stk.top()));
        stk.pop();
      }else{
        re = 1;
      }
    }
    if(s=="PeekMedian"){
      if(stk.size()){
        //cout<<stk.size()<<" ";
        cout<<order[(stk.size()-1)/2]<<endl;
      }else{
        re = 1;
      }
    }
    if(re)cout<<"Invalid\n";
  }
  return 0;
}

L3-003

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;

vector<int>man[maxn];
bool cmp(pair<int,int> a, pair<int,int> b){return a.second>b.second;}

int fa[maxn+10];
void init(int n){for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}

int main(){
  int n;  cin>>n;
  init(maxn);
  for(int i = 1; i <= n; i++){
    int k;  scanf("%d:",&k);
    int x;  cin>>x;
    man[i].push_back(x);
    for(int j = 2; j <= k; j++){
      int xx;  cin>>xx;
      merge(x,xx);
      man[i].push_back(xx);
    }
  }
  map<int,int>ma;
  for(int i = 1; i <= n; i++){
    ma[find(man[i][0])]++;
  }
  vector<pair<int,int> >vec(ma.begin(),ma.end());
  sort(vec.begin(),vec.end(),cmp);
  cout<<vec.size()<<endl;
  for(int i = 0; i < vec.size()-1; i++)
    cout<<vec[i].second<<" ";
  cout<<vec[vec.size()-1].second;
  /*
  map<int,int>::reverse_iterator it = ma.rbegin();
  cout<<(it->second);  it++;
  for( ; it != ma.rend(); it++)
    cout<<" "<<(it->second);
  */
  return 0;
}

L3-004

#include<bits/stdc++.h>
using namespace std;

int n, m, l, t, a[61][129][1287];

int ans = 0;
struct xyz{int x, y, z;};
int dx[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int check(int x, int y, int z){if(x<0||y<0||z<0||x>=l||y>=n||z>=m)return 0;return 1;}
void bfs(int x, int y, int z){
  queue<xyz>q;  
  q.push(xyz{x,y,z}); 
  a[x][y][z] = 0;
  int sum = 1;
  while(q.size()){
    xyz k = q.front(); q.pop();
    for(int i = 0; i < 6; i++){
      xyz kk = k;//kk!=k,WA3,6,这TM也能过样例？！
      kk.x += dx[i][0];
      kk.y += dx[i][1];
      kk.z += dx[i][2];
      if(check(kk.x,kk.y,kk.z) && a[kk.x][kk.y][kk.z]){
        a[kk.x][kk.y][kk.z] = 0;
        sum++;
        q.push(kk);
      }
    }
  }
  if(sum>=t)ans += sum;
}


int main(){
  cin>>n>>m>>l>>t;
  for(int k = 0; k < l; k++)
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        cin>>a[k][i][j];
  for(int k = 0; k < l; k++)
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        if(a[k][i][j])bfs(k,i,j);
  cout<<ans<<endl;
  return 0;
}

L3-005

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1050;//RE6?

int n, m, k, ds;
struct lajitong{
  string id;
  double minds, aveds;
  bool operator < (const lajitong &b){
    if(minds != b.minds)return minds>b.minds;
    if(aveds != b.aveds)return aveds<b.aveds;
    return id < b.id;
  }
};

int e[maxn][maxn], dist[maxn], vis[maxn];
void Dijkstra(int u){
  memset(dist,0x3f,sizeof(dist));
  memset(vis,0,sizeof(vis));
  dist[u] = 0;
  for(int i = 1; i <= n+m; i++){
    int v = -1, _min = (1e9);
    for(int j = 1; j <= n+m; j++)
      if(!vis[j] && dist[j]<_min)
        {_min = dist[j]; v= j;}
    if(v==-1)return ;
    vis[v] = 1;
    for(int j = 1; j <= n+m; j++){
      if(!vis[j] && dist[j]>dist[v]+e[v][j]){//vis[jjjjjj],NotVVVVV
        dist[j] = dist[v]+e[v][j];
      }
    }
  }
}

int main(){
  //input
  cin>>n>>m>>k>>ds;
  memset(e,0x3f,sizeof(e));
  for(int i = 0; i < k; i++){
    char a[10], b[10]; int c;
    scanf("%s%s%d",a,b,&c);
    int aa = (a[0]=='G' ? n+atoi(&a[1]) : atoi(a));
    int bb = (b[0]=='G' ? n+atoi(&b[1]) : atoi(b));
    e[aa][bb] = e[bb][aa] = c;
  }
  //对于每个垃圾桶，跑完dij后统计最短距离和平均距离
  lajitong ans;
  for(int i = 1; i <= m; i++){
    Dijkstra(n+i);
    double aveds = 0, minds = dist[1];
    int flag = 1;
    for(int j = 1; j <= n; j++){
      aveds += dist[j];
      minds = min(minds, dist[j]*1.0);
      if(dist[j]>ds)flag = 0; //dist[jjjjjj],NotIIIIII
    }
    //更新答案
    lajitong tmp = lajitong{"G"+to_string(i),minds,aveds/n};
    //cout<<flag<<"\n";
    if(flag && (ans.id.empty() || tmp<ans)){
      ans = tmp;
    }
  }
  if(ans.id.empty())
    cout<<"No Solution"<<endl;
  else
    printf("%s\n%.1lf %.1lf", ans.id.c_str(), ans.minds, ans.aveds);
  return 0;
}

L3-006

//超级注释版
#include<bits/stdc++.h>
using namespace std;

//1.分别存储两个图形的斜边(2个点)，顶点数，
vector<int> v[2], n;
//2.特判情况:四边形直角腰，矩形个数
vector<int>len; int flag;

//1.找到斜边
void deal(int id, vector<int>& x, vector<int>& y){
  int sz = x.size(); set<int>st;
  for(int i = 0; i < sz; i++){
    //相邻点横纵坐标都不等：这两点构成斜边。
    if(x[i]!=x[(i+1)%sz] && y[i]!=y[(i+1)%sz]){
      st.insert(i);  st.insert((i+1)%sz);
      //如果是四边形：存储直角腰的长度 
      if(sz==4)len.push_back(abs(x[(i+2)%4]-x[(i+3)%4])+abs(y[(i+2)%4]-y[(i+3)%4]));
    }
  }
  if(st.size()==0){//没有斜边，所以是矩形
    //存下两条直角边
    v[id].push_back(abs(x[2]-x[0]));
    v[id].push_back(abs(y[2]-y[0]));
    flag++; //矩形个数+1
  }else{
    //存储斜边(2个端点)
    for(int i : st){
      v[id].push_back(x[i]);
      v[id].push_back(y[i]);
    }
  }
}
//2.情况判断
void solve(){
  //最多也就三边形+五边形，超过8个点就错。
  if(n[0]<=5 && n[1]<=5 && n[0]+n[1]<=8){
    if(flag==2){//两个矩形
      //只要矩形A(x,y)两条直接边有一条能和矩形B合上就行
      int x=v[0][0],y=v[0][1],c=v[1][0],d=v[1][1];
      if(x==c||x==d||y==c||y==d){cout<<"YES\n";return;}
    }
    if(flag==0){//没有矩形
      //如果没有斜边，不成立
      if(v[0].size()==4 && v[1].size()==4){
        //特判直角腰
        if(n[0]==4&&n[1]==4&&len[0]!=len[1]){cout<<"NO\n";return;}
        //存下两条直角边(斜边分别做垂直的直角三角形)
        int x=abs(v[0][2]-v[0][0]),y=abs(v[0][3]-v[0][1]); if(x>y) swap(x,y);
        int c=abs(v[1][2]-v[1][0]),d=abs(v[1][3]-v[1][1]); if(c>d) swap(c,d);
        //当且仅当直角边都相等，斜边相等
        if(x==c&&y==d){cout<<"YES\n";return;}
      }
    }
    //一个矩形的情况不存在
  }
  cout<<"NO\n";
}

int main(){
  int T;  cin>>T;
  while(T--){
    //1. 变量全部初始化
    flag = 0; n.clear();  len.clear();
    v[0].clear();  v[1].clear();
    //2. 输入两个多边形
    for(int i = 0; i < 2; i++){
      int k;  cin>>k;  n.push_back(k);
      vector<int>x(k), y(k);
      for(int j = 0; j < k; j++)cin>>x[j]>>y[j];
      //2.1 找到斜边
      deal(i,x,y);
    }
    //3. 结论判断
    solve();
  }
  return 0;
}

L3-007

//AC
#include<bits/stdc++.h>
using namespace std;
const int maxn = 550;

int n, m, s, t;
int e[2][maxn][maxn], dist[2][maxn], vis[2][maxn], pre[2][maxn], w[2][maxn];
void Dijkstra(int rk){
  memset(dist[rk],0x3f,sizeof(dist[rk]));
  memset(vis[rk],0,sizeof(vis[rk]));
  memset(pre[rk],-1,sizeof(pre[rk]));
  dist[rk][s] = 0;
  for(int i = 0; i < n; i++){
    int u = -1, _min = 1e9;
    for(int j = 0; j < n; j++){
      if(!vis[rk][j] && dist[rk][j]<_min){
        _min = dist[rk][j];  u = j;
      }
    }
    if(u==-1)return ;
    vis[rk][u] = 1;
    for(int j = 0; j < n; j++){
      if(!vis[rk][j] && dist[rk][j]>dist[rk][u]+e[rk][u][j]){
        dist[rk][j] = dist[rk][u]+e[rk][u][j];
        pre[rk][j] = u;
        //距离
        if(rk==0){
          w[rk][j] = w[rk][u]+1;//+1?!!:WA4!!         
        }
        //时间
        if(rk==1){
          w[rk][j] = w[rk][u]+e[!rk][u][j];//WA2!
        }
      }else if(!vis[rk][j] && dist[rk][j] == dist[rk][u]+e[rk][u][j]){
        //距离
        if(rk==0){
          if(w[rk][j] > w[rk][u]+1){
            w[rk][j] = w[rk][u]+1;
            pre[rk][j] = u;
          }
        }
        //时间
        if(rk==1){
          if(w[rk][j] > w[rk][u]+e[!rk][u][j]){
            w[rk][j] = w[rk][u]+e[!rk][u][j];
            pre[rk][j] = u;
          }
        }       
      }
    }
  }
}
void Print(int rk, int x){
  if(x==-1){
    return ;
  }else{
    Print(rk, pre[rk][x]);
    printf(" %d =>", x);
  }
}

int main(){
  memset(e,0x3f,sizeof(e));
  cin>>n>>m;
  for(int i = 1; i <= m; i++){
    int a, b, on, le, ti;
    cin>>a>>b>>on>>le>>ti;
    if(on==1){
      e[0][a][b] = le;
      e[1][a][b] = ti;
    }else{
      e[0][a][b] = le;
      e[1][a][b] = ti;
      e[0][b][a] = le;
      e[1][b][a] = ti;
    }
  }
  cin>>s>>t;
  Dijkstra(0);
  Dijkstra(1);
  int ok = 1, i = pre[0][t], j = pre[1][t];
  while(i!=-1 && j!=-1){
    if(pre[0][i] != pre[0][j]){ok=0;break;}
    i = pre[0][i];
    j = pre[1][j];
  }
  if(ok){
    printf("Time = %d;",dist[1][t]);
    printf(" Distance = %d:",dist[0][t]);
    Print(1,pre[1][t]);
    printf(" %d\n",t);
    return 0;
  }
  printf("Time = %d:",dist[1][t]);
  Print(1,pre[1][t]);
  printf(" %d\n",t);
  printf("Distance = %d:",dist[0][t]);
  Print(0,pre[0][t]);
  printf(" %d",t);
  return 0;
}

L3-008

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
vector<int>G[maxn];
int vis[maxn];
bool cmp(int a, int b){return a>b;}
int bfs(int x){
  memset(vis,0,sizeof(vis));
  int u = -1, val = 1e9;
  queue<pair<int,int> >q;
  q.push({x,1});
  vis[x] = 1;
  while(q.size()){
    pair<int,int> t = q.front();  q.pop();
    vis[t.first] = 1;
    for(int i = 0; i < G[t.first].size(); i++){
      sort(G[t.first].begin(),G[t.first].end(),cmp);//编号小的先输出
      if(!vis[G[t.first][i]])q.push({G[t.first][i],t.second+1});
    }
    if(u==-1 || t.second>val){
      val = t.second;
      u = t.first;
    }else if(t.second==val && t.first<u){
      u = t.first;
    }
  } 
  return u;
}
int main(){
  int n, m, k;
  cin>>n>>m>>k;
  for(int i = 1; i <= m; i++){
    int a, b;  cin>>a>>b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  for(int i = 1; i <= k; i++){
    int x;  cin>>x;
    if(G[x].size()==0)cout<<0<<endl;
    else cout<<bfs(x)<<endl;
  }
  return 0;
}

L3-009

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+10;

LL x[maxn], y[maxn];
int stk[maxn], top;
set<int>se;

bool check(int a, int b, int c){//向量ab在ac下面(kab<kac)，b是凹点
  return (x[c]-x[a])*(y[b]-y[a])<=(x[b]-x[a])*(y[c]-y[a]);
}

int main(){
  ios::sync_with_stdio(false);
  int n;  cin>>n;
  for(int i = 0; i < n; i++){
    cin>>x[i]>>y[i];
    if(top>=1){
      while(top>=2 && check(i,stk[top-1],stk[top-2]))top--;//b是凹点不要它了
      if(stk[top-1])se.insert(stk[top-1]);//找到凸点了入栈
    }
    stk[top++] = i;
  }
  cout<<se.size()<<endl;
  return 0;
}

L3-010

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;

int Tree[maxn];
void update(int root, int val){
  if(!Tree[root])
    Tree[root] = val;
  else if(val > Tree[root])
    update(root*2, val);
  else 
    update(root*2+1,val);
}

int main(){
  int n;  cin>>n;
  for(int i = 1; i <= n; i++){
    int x;  cin>>x;  update(1,x);
  }
  int ok = 0, cnt = 0;
  for(int i = 1; i < maxn; i++){
    if(Tree[i]){
      if(ok)cout<<" ";
      else ok = 1;
      cout<<Tree[i];
      cnt = i;
    }
  }
  if(cnt > n)cout<<"\nNO\n";
  else cout<<"\nYES\n";
  return 0;
}

L3-011

#include<bits/stdc++.h>
using namespace std;
const int maxn = 250;

map<string,int>ma;
map<int,string>mb;
int tot = 1;
int getid(string s){
  if(ma.count(s))return ma[s];
  else{
    mb[tot] = s;
    ma[s] = tot;
    tot++;
    return ma[s];
  }
}

int n, k, s, t;
int e[maxn][maxn], w[maxn];
int dist[maxn], vis[maxn], pre[maxn], cnt[maxn], weight[maxn], cc[maxn];
void Dijkstra(int u){
  memset(dist, 0x3f,sizeof(dist));
  memset(pre,-1,sizeof(pre));
  dist[u] = 0; cnt[u] = 0; weight[u]=w[u];  cc[u] = 1;
  for(int i = 1; i <= n; i++){
    int v = -1, minn = 1e9;
    for(int j = 1; j <= n; j++){
      if(!vis[j] && dist[j]<minn){
        minn = dist[j];
        v = j;
      }
    }
    vis[v] = 1;
    for(int j = 1; j <= n; j++){
      if(!vis[j] && dist[j]>dist[v]+e[v][j]){
        dist[j] = dist[v]+e[v][j];
        cc[j] = cc[v];
        cnt[j] = cnt[v]+1;
        weight[j] = weight[v]+w[j];
        pre[j] = v;
      }else if(!vis[j] && dist[j]==dist[v]+e[v][j]){
        cc[j] += cc[v];//+=
        if(cnt[j]<cnt[v]+1){
          cnt[j] = cnt[v]+1;
          weight[j] = weight[v]+w[j];
          pre[j] = v;
        }else if(cnt[j]==cnt[v]+1){
          if(weight[j]<weight[v]+w[j]){
            weight[j] = weight[v]+w[j];
            pre[j] = v;
          }
        }
      }
    }
  }
}

int main(){
  cin>>n>>k;
  string a,b;  cin>>a>>b;
  s = getid(a);  t = getid(b);
  memset(e,0x3f,sizeof(e));
  for(int i = 1; i < n; i++){
    string a; int b;  cin>>a>>b;
    w[getid(a)] = b;
  }
  for(int i = 1; i <= k; i++){
    string a, b;  cin>>a>>b;
    int aa = getid(a), bb = getid(b);
    int cc;  cin>>cc;
    e[aa][bb] = e[bb][aa] = cc;
  }
  Dijkstra(s);
  vector<string>vec;
  int x = t;
  while(x!=-1){
    vec.push_back(mb[x]);
    x = pre[x];
  }
  reverse(vec.begin(),vec.end());
  for(int i = 0; i < vec.size(); i++){
    if(i==vec.size()-1)cout<<vec[i]<<endl;
    else cout<<vec[i]<<"->";
  }
  cout<<cc[t]<<" "<<dist[t]<<" "<<weight[t]<<"\n";
  return 0;
}

L3-012

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
struct seg{ double x, y1, y2; }s[maxn];
bool cmp(seg a, seg b){return a.x<b.x;}
double maxk,mink,ansmaxk,ansmink,ansx,ansy;
int main(){
  int n;  cin>>n;
  for(int i = 1; i <= n; i++)
    cin>>s[i].x>>s[i].y1>>s[i].y2;//y1在上,y2在下
  sort(s+1,s+n+1,cmp);
  for(int i = 1; i <= n; i++){
    ansmaxk = 1e9;
    ansmink = -1e9;
    int j;
    for(j = 1; j <= n; j++){
      if(j==i)continue;
      if(i<j){// j在i右侧
        maxk = (s[i].y2-s[j].y1)/(s[i].x-s[j].x);
        mink = (s[i].y2-s[j].y2)/(s[i].x-s[j].x);
      }else{ //j在i左侧
        maxk = (s[i].y2-s[j].y2)/(s[i].x-s[j].x);
        mink = (s[i].y2-s[j].y1)/(s[i].x-s[j].x);
      }
      if(ansmaxk<mink || ansmink>maxk)break;
      if(maxk<ansmaxk){
        ansmaxk = maxk;
        ansx = s[j].x;
        ansy = s[j].y1;
      }
      ansmink = max(ansmink, mink);
    }
    if(j==n+1){//存在解
      //线段i上取了最低点，则另一条线段要取最高点
      printf("%.0lf %.0lf %.0lf %.0lf\n",s[i].x,s[i].y2,ansx,ansy); 
      return 0;
    }
  }
  return 0;
}

L3-013

#include<bits/stdc++.h>
using namespace std;
int main(){
  double w, p; cin>>w>>p;
  double E = 1000, g = 9.8;
  double s = 1, sum = 0;
  while(s>1e-8){//精度
    s = 2*E/(w/100*g);
    sum += s;
    E *= (100-p)/100;
  }
  printf("%0.3lf",sum);
  return 0;
}

L3-014

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;

int minCnt, minTrans;
vector<int>path, tempath;

int line[maxn][maxn]; //维护两点之间的线路归属
int count(vector<int>a){//给出路径，计算换乘
  int cnt = -1, preLine = 0;
  for(int i = 1; i < a.size(); i++){
    if(line[a[i-1]][a[i]] != preLine)cnt++;
    preLine = line[a[i-1]][a[i]];
  }
  return cnt;
}

vector<int>G[maxn]; int vis[maxn];
void dfs(int u, int end, int cnt){
  if(u==end){
    if(cnt<minCnt || (cnt==minCnt && count(tempath)<minTrans)){
      minCnt = cnt;
      minTrans = count(tempath);
      path = tempath;
    }
    return ;
  }
  for(int i = 0; i < G[u].size(); i++){
    int v = G[u][i];
    if(!vis[v]){
      vis[v] = 1;
      tempath.push_back(v);
      dfs(v,end,cnt+1);
      vis[v] = 0;
      tempath.pop_back();
    }
  }
}

int main(){
  int n, m, k, pre, tmp, a, b;
  cin>>n;
  for(int i = 1; i <= n; i++){
    cin>>m>>pre;
    for(int j = 2; j <= m; j++){
      cin>>tmp;
      G[pre].push_back(tmp);
      G[tmp].push_back(pre);
      line[pre][tmp] = i;
      line[tmp][pre] = i;
      pre = tmp;
    }
  }
  cin>>k;
  for(int i = 1; i <= k; i++){
    cin>>a>>b;
    //memset(vis,0,sizeof(vis));
    minCnt = 1e9, minTrans = 1e9;
    tempath.clear();  tempath.push_back(a);
    vis[a] = 1;
    dfs(a,b,0);
    vis[a] = 0;//memset
    if(minCnt == 1e9) {
      printf("Sorry, no line is available.\n");
      continue;
        }
    cout<<minCnt<<"\n";
    int preLine = 0, preTrans = a;//上次的线路，以及转乘点
    for(int j = 1; j < path.size(); j++){
      if(line[path[j-1]][path[j]]!=preLine){
        if(preLine!=0)printf("Go by the line of company #%d from %04d to %04d.\n", preLine, preTrans, path[j-1]);
        preLine = line[path[j-1]][path[j]];
        preTrans = path[j-1];
      }
    }
    printf("Go by the line of company #%d from %04d to %04d.\n", preLine, preTrans, b);
  }
  return 0;
}

L3-015

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50;

int n, T0, ok;
int e[maxn][maxn], vis[maxn];
vector<int>q;
void dfs(int u, int k){
  for(int i = 1; i <= n; i++){
    int flag = 0;//剩余队伍不存在战胜第一只队伍
    for(int j = 1; j <= n; j++){
      if(!vis[j] && e[j][T0]){
        flag = 1; break;
      }
    }
    if(flag && !ok && !vis[i] && e[u][i]){
      vis[i] = 1;  q.push_back(i);
      if(k==n-1 && e[i][T0]){
        ok = 1;
        for(int j = 0; j < q.size(); j++){
          if(j!=0)cout<<" "; 
          cout<<q[j];
        }
      }else{
        dfs(i,k+1);
      }
      vis[i] = 0;  q.pop_back();
    }
  }
}

int main(){
  cin>>n;  cin.get();
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      char ch;  cin>>ch;
      if(ch=='W')e[i][j] = 1;
      if(ch=='L')e[j][i] = 1;
    }
    cin.get();
  }
  for(int i = 1; i <= n; i++){//另i为队首
    vis[i] = 1;  q.push_back(i);
    T0 = i;  dfs(i,1); 
    if(ok)return 0;
    vis[i] = 0;  q.pop_back();
  }
  cout<<"No Solution";
  return 0;
}

L3-016

#include<bits/stdc++.h>
using namespace std;

struct node{int l=-1, r=-1, fa=-1, h;};
map<int,node>Tree;
void insert(int u, int h, int v){
  if(u==-1)return ;
  int uu = (v<u ? Tree[u].l : Tree[u].r);
  if(uu!=-1){
    insert(uu,h+1,v);
  }else{
    if(v<u)Tree[u].l = v;
    else Tree[u].r = v;
    Tree[v].fa = u;
    Tree[v].h = h;
  }
}

bool judge(int u, int a, int b, string lk){
  if(lk=="root")return u==a;;
  if(Tree.find(a)==Tree.end() || Tree.find(b)==Tree.end())return false;
  if(lk=="siblings")return Tree[a].fa==Tree[b].fa;
  if(lk=="parent")return Tree[a].l==b || Tree[a].r==b;
  if(lk=="left")return Tree[b].l == a;
  if(lk=="right")return Tree[b].r == a;
  if(lk=="level")return Tree[a].h==Tree[b].h; 
}

int main(){
  int n, rt, t;
  cin>>n>>rt; //rt是根
  for(int i = 2; i <= n; i++){
    cin>>t;
    insert(rt,1,t);
  }
  int m, a=0, b=0;  cin>>m;
  for(int i = 1; i <= m; i++){
    string s, lk;  cin>>a>>s;
    if(s=="and"){
      cin>>b>>s>>s;
      if(s=="siblings")lk = s;
      else cin>>s>>s>>lk;
    }else{
      cin>>s>>lk;
      if(lk=="parent")cin>>s>>b;
      else if(lk!="root")cin>>s>>s>>b;
    }
    if(judge(rt,a,b,lk))cout<<"Yes\n";
    else cout<<"No\n";
  }
  return 0;
}

L3-017

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;

struct seg{int x, y;}sg[maxn];
bool cmp(seg a, seg b){return a.y!=b.y?a.y<b.y:a.x<b.x;}

LL rmq[maxn<<2], tag[maxn<<2], c[maxn];
#define lch p<<1
#define rch p<<1|1
void pushdown(int p){
  if(tag[p]){
    tag[lch] += tag[p], tag[rch]+=tag[p];
    rmq[lch] += tag[p], rmq[rch]+=tag[p];
    tag[p] = 0;
  }
}
void pushup(int p){
  rmq[p] = min(rmq[lch], rmq[rch]); 
}
void build(int p, int l, int r){
  tag[p] = 0;
  if(l==r){
    rmq[p] = c[l];
    return ;
  }else{
    int m = l+r>>1;
    build(lch,l,m);
    build(rch,m+1,r);
    pushup(p);
  }
}
void update(int p, int l, int r, int L, int R, int v){
  if(l>R || r<L)return ;
  if(L<=l && r<=R){
    rmq[p] += v;  tag[p] += v;
    return ;
  }
  pushdown(p);
  int mid = l+r>>1;
  update(lch,l,mid,L,R,v);
  update(rch,mid+1,r,L,R,v);
  pushup(p);
}
LL query(int p, int l, int r, int L, int R){
  if(l>R || r<L)return (1ll<<60);
  if(L<=l && r<=R)return rmq[p];
  pushdown(p);
  LL mid = l+r>>1, ans = 1ll<<60;
  ans = min(ans, query(lch,l,mid,L,R));
  ans = min(ans, query(rch,mid+1,r,L,R));
  return ans;
}

int main(){
  int n, q;
  cin>>n>>q;
  for(int i = 1; i < n; i++)
    cin>>c[i];
  build(1,1,n-1); //1-(n-1)号城市分别对应i与i+1的边
  for(int i = 1; i <= q; i++){
    cin>>sg[i].x>>sg[i].y;
    if(sg[i].x>sg[i].y)swap(sg[i].x,sg[i].y);
  }
  sort(sg+1,sg+q+1,cmp);
  LL ans = 0;
  for(int i = 1; i <= q; i++){
    //cout<<sg[i].x+1<<" "<<sg[i].y<<" ";
    LL res = query(1,1,n-1,sg[i].x+1,sg[i].y);//因为编号从0开始，所以x+1。
    //cout<<res<<"\n";
    ans += res;
    if(res)update(1,1,n-1,sg[i].x+1,sg[i].y,-res);
  }
  cout<<ans<<endl;
  return 0;
}

L3-018

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9+10;
const int maxn = 110;

struct point{ int x, y;  double dis;};
bool operator!=(point a, point b){return a.x!=b.x||a.y!=b.y;}
bool operator==(point a, point b){return a.x==b.x&&a.y==b.y;}

int n, m;
double sc[maxn][maxn];//分数
point s, t;
void input(){
  cin>>n>>m;
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
      cin>>sc[i][j];
  cin>>s.y>>s.x>>t.y>>t.x;
  s.x++;s.y++;t.x++;t.y++;
  s.dis = sc[s.x][s.y];
}

int flag;//1上半部分，0下半部分
double f[maxn][maxn]; //到i,j为止的最小值
int dir[][2]= {{0,1},{1,0},{-1,0},{0,-1},{-1,-1},{1,-1},{-1,1},{1,1}}; //上下左右+前后左右
int cross(point a,point b,point p){//三角形行列式公式,判断三点是否在一个直线上
  return (b.x-a.x)*(p.y-a.y)-(p.x-a.x)*(b.y-a.y);
}
bool check(point p){//检查p是否合法（越界）
  if(p.x<1||p.x>n||p.y<1||p.y>m)return false;//越界
  if(flag && p!=s&&p!=t && cross(s,t,p)<=0)return false;//1:上半部分但点在下面(起点终点不算)
  if(!flag && p!=s&&p!=t && cross(s,t,p)>=0)return false;//2.下半部分但点在上面
  if(p.dis>=f[p.x][p.y])return false;//不是最小值
  return true;
}
void bfs(){
  //init
  queue<point>q;
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
      f[i][j] = inf;
  //search
  if(check(s)){
    f[s.x][s.y] = s.dis;
    q.push(s);
  }
  while(q.size()){
    point now = q.front(); q.pop();
    point next;
    for(int i = 0; i < 8; i++){
      next.x=now.x+dir[i][0];
      next.y=now.y+dir[i][1];
      if(i<4)next.dis = f[now.x][now.y]+sc[next.x][next.y];
      else next.dis=f[now.x][now.y]+sc[next.x][next.y]+(sc[next.x][next.y]+sc[now.x][now.y])*(sqrt(2)-1);
      if(check(next)){
        f[next.x][next.y] = next.dis;
        q.push(next);
      }
    }
  }
}

int main(){
  input();
  double ans = 0;
  flag = 1; bfs(); ans += f[t.x][t.y];//搜上面
  flag = 0; bfs(); ans += f[t.x][t.y];//搜下面
  ans -= sc[s.x][s.y]+sc[t.x][t.y];//重复
  printf("%.2f\n",ans);
  return 0;
}

L3-019

#include<bits/stdc++.h>
using namespace std;

//判断语句块类型
int judge(string dat, int i){
    //WA3:当前位置是if并且不是在字符串内
    if(dat.find("if", i)==i && (dat[i+2]==' '||dat[i+2]=='('))return 2;
    if(dat.find("for",i)==i && (dat[i+3]==' ' ||dat[i+3]=='('))return 3;
    if(dat.find("while",i)==i && (dat[i+5]==' '||dat[i+5]=='('))return 5;
    if(dat.find("else",i)==i && dat[i+4]==' ')return 4;
    return 0;//普通语句
}
//输出前删除多余空格, 并输出当前对应的空格
void erase_space(string dat,int &i){while(dat[i]==' ')i++;}
void print_space(int sp){for(int i=0;i<sp;i++)putchar(' ');}

int main(){
    string dat;  getline(cin,dat);
    
    //处理int main()  找i和)输出
    int l = dat.find('i',0), r = dat.find(')',0);
    cout<<dat.substr(l,r-l+1)<<"\n{\n";
    
    //处理其他，按照行分类
    int tmp, space = 2;//语句类型,空格数
    int flag, debt=0;//单句标记，层数（补全缺少的}）
    for(int i = dat.find('{')+1,j=0,k; i < dat.size(); ){
        erase_space(dat,i);//删除每行前的空格
        if(dat[i]=='{' || dat[i]=='}'){
            if(dat[i]=='{'){
                print_space(space);
                printf("{\n");
                space += 2;
                i++;
                continue;
            }else{
                space -= 2;
                print_space(space);
                printf("}\n");
                i++;
                if(space==0)break;//main的}输完就结束了
                
                //【重复】单句特判
                erase_space(dat,i);
                while(debt && judge(dat,i)!=4){
                    space -= 2;
                    print_space(space);
                    printf("}\n");
                    debt--;
                }
            }
        }else if((tmp=judge(dat,i))){
            print_space(space);
            //处理for,while,if,+()或者else
            if(tmp==4){
                printf("else");
                k = i+3;
            }else{
                cout<<dat.substr(i,tmp)<<" ";
                i += tmp;
                erase_space(dat, i);
                //考虑if()中也有()条件的情况
                k = i; int t = 0;
                while(1){
                    if(dat[k]=='(')t++;
                    if(dat[k]==')')t--;
                    if(!t)break;
                    k++;
                }
                cout<<dat.substr(i,k-i+1);
            }
            //预处理{}的内容,考虑单句特判
            int m = k+1;
            erase_space(dat,m);
            if(dat[m] != '{'){//单句标记
                printf(" {\n");
                flag = 1;
                debt++;
                i = m;
            }else{
                printf(" {\n");
                flag = 0;
                i = m+1;
            }
            space += 2;
        }else{//普通语句
            int ed = dat.find(';', i);
            print_space(space);
            cout<<dat.substr(i,ed-i+1)<<"\n";
            i = ed+1;
            
            //这是单句内的语句
            if(flag && debt){
                space -= 2;
                print_space(space);
                printf("}\n");
                debt--;
                
                //【重复】单句特判
                erase_space(dat,i);
                while(debt && judge(dat,i)!=4){
                    space -= 2;
                    print_space(space);
                    printf("}\n");
                    debt--;
                }
            }
        }
    }
    return 0;
}

L3-020

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
LL f[maxn][5];
int main(){
  string s;  cin>>s; s = "0"+s;//从1开始
  f[0][0] = 1;
  for(int i = 1; i < s.size(); i++){
    for(int j = 0; j <= 3; j++){//删0-3个
      f[i][j] = f[i-1][j]+f[i-1][j-1];//第i个删还是不删
      for(int k=i-1; k>=1 && (i-k)<=j; k--){//去重
        if(s[k]==s[i]){//如果当前字符一样，那么前面的重复统计了
          f[i][j] -= f[k-1][j-(i-k)];
          break;
        }
      }
    }
  }
  LL ans = 0;
  for(int i = 0; i <= 3; i++)
    ans += f[s.size()-1][i];
  cout<<ans<<endl;
  return 0;
}

L3-021

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+10;

struct point{LL x, y;}pp[maxn], tmp[maxn];
bool cmp(point a, point b){return a.x*b.y>a.y*b.x;}

int main(){
  int n;  cin>>n;
  for(int i = 0; i < n; i++)
    cin>>pp[i].x>>pp[i].y;
  double ans = 1e18;
  for(int i = 0; i < n; i++){
    int cc = 0;
    for(int j = 0; j < n; j++){
      if(i==j)continue;
      tmp[cc].x = pp[j].x-pp[i].x;
      tmp[cc].y = pp[j].y-pp[i].y;
      cc++;
    }
    sort(tmp,tmp+cc,cmp);
    for(int j = 0; j < cc; j++)
      ans=min(ans,abs(0.5*(tmp[j].x*tmp[(j+1)%cc].y-tmp[(j+1)%cc].x*tmp[j].y)));
  }
  printf("%.3f\n",ans);
  return 0;
}

L3-022

#include<bits/stdc++.h>
using namespace std;
const int maxn = 210;
const int inf = 1e9+10;
int G[maxn][maxn];
vector<int>st[maxn]; int ed[maxn], vis[maxn];
void dfs(int u){
  for(int i = 0; i < st[u].size(); i++){
    int v = st[u][i];
    if(!vis[v]){
      vis[v] = 1;
      dfs(v);
    }
  }
}
int main(){
  //input
  int n, m, k;  cin>>n>>m>>k;
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      G[i][j] = inf;
  for(int i = 1; i <= m; i++){
    int a, b, dis;
    cin>>a; ed[a] = 1;
    while(cin>>dis>>b){
      G[a][b] = min(G[a][b], dis);
      G[b][a] = min(G[b][a], dis);
      a = b;
      if(getchar()=='\n')break;
    }
    ed[a] = 1;
  }
  //solve
  for(int k = 1; k <= n; k++)//Floyd
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= n; j++)
        if(i!=j)G[i][j] = min(G[i][j],G[i][k]+G[k][j]);
  for(int i = 1; i <= n; i++){//从点i出发
    map<int,int>cost;//各种费用能到的最远距离
    for(int j = 1; j <= n; j++){//遍历到每个点的费用去更新距离
      if(G[i][j]==inf)continue;
      cost[2+G[i][j]/k] = max(cost[2+G[i][j]/k],G[i][j]);
    }
    for(int j = 1; j <= n; j++){//更新点i能到达的最远点或者端点
      if(G[i][j]==cost[2+G[i][j]/k] || i!=j&&ed[j]&&G[i][j]!=inf){
        st[i].push_back(j);
      }
    }
  }
  int q;  cin>>q;
  for(int i = 1; i <= q; i++){
    int x;  cin>>x;
    memset(vis,0,sizeof(vis));
    vis[x] = 1;
    dfs(x);
    for(int j = 1; j <= n; j++)
      if(vis[j])st[x].push_back(j);
    sort(st[x].begin(), st[x].end());
    st[x].erase(unique(st[x].begin(), st[x].end()), st[x].end());
    for(int j = 0; j < st[x].size(); j++){
      if(j!=0)cout<<" ";
      cout<<st[x][j];
    }
    cout<<"\n";
  }
  return 0;
}

L3-023

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4+10;

struct node{
  int op, left, right; //运算符和数值
  double val; //当前节点的值
  int post;  //后继节点的
}a[maxn];
map<int,map<int,map<int,double>>>f;//记忆化数组

//第一个参数为结点，第二个参数决定是否求导，第三个参数是对谁求导
double calc(int nd, int key, int p){
  if(f[nd][key][p])return f[nd][key][p];
  int id = a[nd].op;
  if(id==0)return f[nd][key][p] = (key == 0 ? a[nd].val : (nd == p ? 1 : 0)); 
  if(id==1)return f[nd][key][p] = calc(a[nd].left, key, p) + calc(a[nd].right, key, p); 
  if(id==2)return f[nd][key][p]= calc(a[nd].left, key, p) - calc(a[nd].right, key, p); 
  if(id==3)return f[nd][key][p] = (key ? calc(a[nd].left, key, p) * calc(a[nd].right, 0, p) + calc(a[nd].left, 0, p) * calc(a[nd].right, key, p) : calc(a[nd].left, key, p) * calc(a[nd].right, key, p)); 
  if(id==4)return f[nd][key][p]=(key ? exp(calc(a[nd].left, 0, p)) * calc(a[nd].left, key, p) : exp(calc(a[nd].left, key, p)));
  if(id==5)return f[nd][key][p] = (key ? 1 / (calc(a[nd].left, 0, p)) * (calc(a[nd].left, key, p)) : log(calc(a[nd].left, key, p)));
  if(id==6)return f[nd][key][p] = (key ? cos(calc(a[nd].left, 0, p)) * calc(a[nd].left, key, p) : sin(calc(a[nd].left, key, p)));
}

int main(){
  int n;  cin>>n;
  for(int i = 0; i < n; i++){
    cin>>a[i].op;
    if(a[i].op==0){
      cin>>a[i].val;
    }else if(a[i].op<=3){
      cin>>a[i].left>>a[i].right;
      a[a[i].left].post = 1;
      a[a[i].right].post = 1;
    }else{
      cin>>a[i].left;
      a[a[i].left].post = 1;
    }
  }
  int ed = 0, ok=0;
  while(a[ed].post)ed++;
  printf("%0.3lf\n",calc(ed,0,-1));
  for(int i = 0; i < n; i++){
    if(a[i].op==0){
      if(ok)cout<<" ";
      printf("%0.3lf",calc(ed,1,i));
      ok = 1;
    }
  }
  return 0;
}