2022 CCCC 团体程序设计天梯赛（个人题解）

L1-1 今天我要赢（5分）

#include
using namespace std;
int main(){
    cout<<"I'm gonna win! Today!\n2022-04-23";
}

L1-2 种钻石（5分）

#include
using namespace std;
int main(){
    int N,v;cin>>N>>v;
    cout<<N/v;
}

L1-3 谁能进图书馆（10分）

#include
using namespace std;
int main(){
    int x,y,p,q,cnt=0;scanf("%d%d%d%d",&x,&y,&p,&q);
    if(p>=x) cnt++;
    if(q>=x) cnt++;
    if(cnt==2) printf("%d-Y %d-Y\nhuan ying ru guan",p,q);
    else if(cnt==0) printf("%d-N %d-N\nzhang da zai lai ba",p,q);
    else{
        int older=(p>=x)?p:q;
        if(older>=y) printf("%d-Y %d-Y\nqing %d zhao gu hao %d",p,q,(older==p)?1:2,(older==p)?2:1);
        else if(p>=x) printf("%d-Y %d-N\n1: huan ying ru guan",p,q);
        else printf("%d-N %d-Y\n2: huan ying ru guan",p,q);
    }
}

L1-4 拯救外星人（10分）

#include
using namespace std;
int main(){
    int x,y;cin>>x>>y;
    long long ans=1;
    for(int i=1;i<=(x+y);++i) ans=ans*i;
    cout<<ans;
}

L1-5 试试手气（15分）

#include
using namespace std;
int A[10],vis[10][10];
int main(){
    for(int i=0;i<6;++i) cin>>A[i],vis[i][A[i]]=1;
    int n;cin>>n;
    for(int k=1;k<=n;++k)
        for(int i=0;i<6;++i)
            for(int j=6;j>0;--j)
                if(!vis[i][j]) {A[i]=j,vis[i][j]=1;break;}
    cout<<A[0];
    for(int i=1;i<6;++i) cout<<' '<<A[i];
}

L1-6 斯德哥尔摩火车上的题（15分）

#include
using namespace std;
string Solve(string str){
    string ans="";int len=str.length();
    for(int i=1;i<len;++i) 
        if(str[i]%2==str[i-1]%2) ans+=max(str[i],str[i-1]);
    return ans;
}
int main(){
    string str1,str2;cin>>str1>>str2;
    string ans1=Solve(str1),ans2=Solve(str2);
    if(ans1==ans2) cout<<ans1;
    else cout<<ans1<<"\n"<<ans2;
}

L1-7 机工士姆斯塔迪奥（20分）

#include
#define close ios::sync_with_stdio(false)
const int maxn=1e5+100;
int hor[maxn],ver[maxn];
using namespace std;
int main(){
    close;int N,M,Q;cin>>N>>M>>Q;
    for(int i=0;i<Q;++i){
        int op,x;cin>>op>>x;
        if(op==0) hor[x]=1;
        else ver[x]=1;
    }
    int ans=0;
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
            if(!hor[i] && !ver[j]) ans++;
    cout<<ans;
}

L1-8 静静的推荐（20分）

  这个题感觉有点思维的意思。简单来说，不应该去考虑一批推荐名单里面怎么安排人员，而应该考虑同一分数（排除PAT分数达到企业分数线）的人需要推荐多少批。

#include
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=1e5+100;
struct Person{
    int g,p;
    bool operator <(const Person&a)const{
        return g>a.g;
    }
}person[maxn];
int main(){
    close;int N,K,S,ans=0;cin>>N>>K>>S;
    for(int i=0;i<N;++i) cin>>person[i].g>>person[i].p;
    sort(person,person+N);
    int last=-1,cnt=0;
    for(int i=0;i<N;++i){
        if(person[i].g<175) break;
        if(person[i].g!=last){
            if(last!=-1) ans+=min(cnt,K);
            last=person[i].g;
            if(person[i].p>=S) ans++,cnt=0;
            else cnt=1;
        }
        else if(person[i].p>=S) ans++;
        else cnt++;
    } 
    ans+=min(K,cnt);cout<<ans;
}   

L2-1 插松枝（25分）

#include
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=1e3+100;
int A[maxn];
int main(){
    close;int N,M,K,cnt=0,index=0,num=0,last;cin>>N>>M>>K;
    //cnt表示栈中元素的数量,num表示当前松枝干上插的松枝数量
    //index表示流水线上的松针下标,last表示上一松针的大小
    stack<int> st;
    for(int i=0;i<N;++i) cin>>A[i];
    while(index<N){
        if(num==0){
            num++;
            if(cnt!=0) last=st.top(),st.pop(),cnt--,cout<<last;
            else last=A[index++],cout<<last;
            if(num==K) cout<<"\n",num=0;
        }
        else{
            if(cnt>0 && st.top()<=last) last=st.top(),st.pop(),cnt--,num++,cout<<' '<<last;
            else if(A[index]<=last) last=A[index++],num++,cout<<' '<<last;
            else if(cnt<M) st.push(A[index++]),cnt++;
            else cout<<"\n",num=0;
            if(num==K) cout<<"\n",num=0;
        }
    }
    while(cnt>0){
        if(num==0) last=st.top(),st.pop(),cnt--,num++,cout<<last;
        else if(st.top()<=last) last=st.top(),st.pop(),cnt--,num++,cout<<' '<<last;
        else cout<<"\n",num=0;
        if(num==K) cout<<"\n",num=0;
    }
}     

L2-2 老板的作息表（25分）

  这种时间段的题目，把他转换成秒就非常好处理了。

#include
using namespace std;
const int maxn=1e5+100;
struct Interval{
    int sta,fin;
    bool operator <(const Interval&a)const{
        return fin<a.fin;
    }
}intv[maxn];
void Print(int s,int f){
    printf("%02d:%02d:%02d - %02d:%02d:%02d\n",s/3600,s%3600/60,s%3600%60,f/3600,f%3600/60,f%3600%60);
}
int main(){
    int N,h1,h2,m1,m2,s1,s2;scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%d:%d:%d - %d:%d:%d",&h1,&m1,&s1,&h2,&m2,&s2);
        intv[i].sta=3600*h1+60*m1+s1;
        intv[i].fin=3600*h2+60*m2+s2;
    }
    sort(intv,intv+N);int last=0;
    for(int i=0;i<N;++i){
        if(intv[i].sta!=last) Print(last,intv[i].sta);
        last=intv[i].fin;
    }
    if(last!=24*60*60-1) Print(last,24*60*60-1);
}   

L2-3 龙龙送外卖（25分）

  这个题感觉很有意思。其实做法就是每次总和加上从新增的结点走到【已经走过的链/根节点】的距离*2，每次的答案就是总和减去所有节点中深度最大的节点的距离（因为不需要返回外卖站）。

#include
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=1e5+100;
int pa[maxn],dep[maxn],vis[maxn];
vector<int> e[maxn];
void DFS(int root,int d){
    dep[root]=d;
    for(int u:e[root]) DFS(u,d+1);
}
int main(){
    close;int N,M,root;cin>>N>>M;
    for(int i=1;i<=N;++i){
        cin>>pa[i];
        if(pa[i]!=-1) e[pa[i]].push_back(i);
        else root=i;
    }
    DFS(root,0);
    int ans=0,maxnum=0;vis[root]=1;
    while(M--){
        int x,cnt=0;cin>>x;maxnum=max(maxnum,dep[x]);
        while(x!=root && !vis[x]) vis[x]=1,cnt++,x=pa[x];
        ans+=cnt*2;cout<<ans-maxnum<<"\n";
    }
}   

L2-4 大众情人（25分）

  有向图里面的最短路问题，对于 n < 500 n<500 n<500，且同时要求求出所有点对之间的最短路径，很明显使用Floyd算法。同时因为有向图，注意题目中的描述（也就是边的方向）。

#include
#define PII pair<int,int>
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=600;
const int INF=0x3f3f3f3f;
int dist[maxn][maxn];bool sex[maxn];
void Floyd(int N){
    for(int k=1;k<=N;++k)
        for(int i=1;i<=N;++i)
            if(dist[i][k]<INF)
                for(int j=1;j<=N;++j)
                    if(dist[k][j]<INF && dist[i][j]>dist[i][k]+dist[k][j]) 
                        dist[i][j]=dist[i][k]+dist[k][j];
}
int main(){
    int N;scanf("%d",&N);
    for(int i=1;i<=N;++i) for(int j=1;j<=N;++j) dist[i][j]=(i==j)?0:INF;
    for(int i=1;i<=N;++i){
        getchar();char s;int num;scanf("%c%d",&s,&num);
        sex[i]=(s=='F')?false:true;
        for(int j=0;j<num;++j){
            int id,d;scanf("%d:%d",&id,&d);
            dist[i][id]=d;
        }
    }
    Floyd(N);
    vector<PII> M,F;
    for(int i=1;i<=N;++i)
    {
        int maxnum=0;
        for(int j=1;j<=N;++j) 
            if(i!=j && sex[i]!=sex[j]) maxnum=max(maxnum,dist[j][i]);
        if(sex[i]) M.push_back(PII(maxnum,i));
        else F.push_back(PII(maxnum,i));
    }
    sort(F.begin(),F.end());
    printf("%d",F[0].second);
    for(int i=1;i<(int)F.size();++i) if(F[i].first==F[0].first) printf(" %d",F[i].second);
    sort(M.begin(),M.end());
    printf("\n%d",M[0].second);
    for(int i=1;i<(int)M.size();++i) if(M[i].first==M[0].first) printf(" %d",M[i].second);
}   

L3-1 千手观音（30分）

  这道题比赛没做满，因为自己没弄清楚那句“当若干根手指之间的相对顺序无法确定时，就暂且按它们的英文字典序升序排列”…然后写假了（不过这居然有24分这数据也真的是友好hhh).
  相邻两个数字比较大小，能够确定的符号的大小，当前仅当两个数字的位数一致，而且只能确定最左侧第一次不相同的符号.这个事情解决了以后，建个图，跑一个拓扑排序，然后结合上面那句话使用一个优先队列就可以了。

#include
#define close ios::sync_with_stdio(false)
using namespace std;
int tot=0;
unordered_map<string,int> mp;
const int maxn=1e4+100;
vector<int> rec[maxn];
string name[maxn];
int id[maxn],deg[maxn];
vector<string> Solve(string s){
    string cur="";
    vector<string> ans;
    for(char u:s){
        if(u!='.') cur+=u;
        else{
            ans.push_back(cur);
            if(mp.count(cur)==0) mp[cur]=++tot,name[tot]=cur;
            cur="";
        }
    }
    ans.push_back(cur);
    if(mp.count(cur)==0) mp[cur]=++tot,name[tot]=cur;
    return ans;
}

int main(){
    close;int N;cin>>N;
    string str;cin>>str;
    vector<string> now1=Solve(str);
    for(int i=2;i<=N;++i){
        cin>>str;
        vector<string> now2=Solve(str);
        int s1=now1.size(),s2=now2.size();
        if(s1==s2){
            for(int i=0;i<s1;++i){
                if(now1[i]!=now2[i]){
                    rec[mp[now1[i]]].push_back(mp[now2[i]]);
                    deg[mp[now2[i]]]++;
                    break;
                }
            }
        }
        now1=move(now2);
    }
    vector<string> ans;
    priority_queue<string,vector<string>,greater<string>> Q;
    for (int i=1;i<=tot;i++) if (deg[i]==0) Q.push(name[i]);
    while(!Q.empty()) {
        string cur=Q.top();Q.pop();
        int root=mp[cur];
        ans.push_back(cur);
        for(int u:rec[root]){
            deg[u]--;
            if(deg[u]==0) Q.push(name[u]);
        }
    }
    cout<<ans[0];
    for(int i=1;i<ans.size();++i) cout<<'.'<<ans[i];
}

L3-2 关于深度优先搜索和逆序对的题应该不会很难吧这件事（30分）

  这个题吧…比赛的时候我没想清楚不在同一棵子树里面的结点形成的逆序对数的关系，然后就挂了…
  我觉得这个题分为两个部分。①一共能形成多少种DFS序？假设一共有 1... N 1...N 1...N个结点，每个结点的子树的个数（直接子结点的个数）分别是 p 1 . . . p N p_1...p_N p1​...pN​，那一共就能形成 t o t = p 1 ! × p 2 ! × . . . × p N ! tot=p_1!\times p_2!\times ... \times p_N! tot=p1​!×p2​!×...×pN​!种DFS序.②对于任何一对结点A和B，只要他俩不满足【其中一个结点是另一个结点的祖先结点】，那形成的逆序对数量就是 t o t ∗ 1 2 tot*\frac{1}{2} tot∗21​（一半DFS序中A在B前，一半DFS序中B在A前）；否则形成的逆序对数就是 t o t tot tot或者 0 0 0。这个发现了以后就很简单了（可惜我当时没想明白hhh

#include
#define close ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int maxn=3e5+100;
const int mod=1e9+7;
vector<int> v[maxn];
vector<int> dep[maxn];
ll f[maxn],chd[maxn],ans=0,tot=1,C;
int tree[maxn],n,r,maxnum=0;
int lowbit(int x){return x&(-x);}
void update(int loc,int d){
    while(loc<=n){
        tree[loc]+=d;
        loc+=lowbit(loc);
    }
}
int query(int loc){
    int ans=0;
    while(loc){
        ans+=tree[loc];
        loc-=lowbit(loc);
    }
    return ans;
}
int DFS(int root,int fa,int d){
    dep[d].push_back(root);
    if(d>maxnum) maxnum=d;
    int x=query(root),cnt=0,sum=0;
    for(int u:v[root]){
        if(u==fa) continue;
        cnt++;sum+=DFS(u,root,d+1);
    }
    ans=(ans+(query(root)-x)*2%mod)%mod;
    update(root,1);
    if(cnt==0) {chd[root]=0;return 1;}
    else{
        chd[root]=sum;
        tot=tot*f[cnt]%mod;
        return 1+sum;
    }
}
ll qpow(ll base,ll x){
    ll ans=1;
    while(x){if(x&1) ans=ans*base%mod;base=base*base%mod;x>>=1;}
    return ans;
}
int main(){
    close;cin>>n>>r;
    f[0]=1;C=qpow(2,mod-2);
    for(int i=1;i<=n;++i) f[i]=f[i-1]*i%mod;
    for(int i=1;i<n;++i){
        int x,y;cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(r,-1,0);
    for(int i=1;i<=maxnum;++i){
        ll cur_sum=0,cur_cnt=dep[i].size();
        for(int id:dep[i]) cur_sum+=chd[id];
        ans=((ans+cur_sum*(cur_cnt-1)%mod)%mod+cur_cnt*(cur_cnt-1)%mod*C%mod)%mod;
    }
    cout<<ans*tot%mod*C%mod;
}

L3-3 教科书般的亵渎（30分）

  比赛就没想明白，现在仍然没想明白TAT蹲一个好心人的详细题解。


【总结（小小的感慨】
  最后一次参加天梯赛了吧。大一就有幸打过天梯赛，那时候数据结构都不会hhh好像一共就拿了70来分？去年一直忙着写L3-1，最后29分，没发现L3-2那么简单，暴力都能26…（223我记得？遗憾没有国一）今年也是佛系了，也不想骗分了，最后228hhh也还行，水平没咋退步哈哈哈。
  四次天梯赛也算见证我的成长了吧，虽然好多算法因为比赛useless都没学过，虽然感觉自己还是个菜狗hhh最后写一次天梯赛的题解，就当是留个纪念吧。