2021-天梯赛（cccc）比赛题解

写在前面

今年的天梯赛因为四月事多，没有参加，后面抽空把题做了一下，难度不大，但是有不少细节需要注意。写一篇博客来稍微总结一下这套比赛的一些坑点吧。第一部分题目没什么好说的，贴一份代码放着。

L-1-1 人与神

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<"To iterate is human, to recurse divine.";
    return 0;
}

L-1-2 两小时学完C语言

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,m;
    cin>>n>>k>>m;
    cout<<n-k*m<<endl;
    return 0;
}

L-1-3 强迫症

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n>10000)
    {
        int a,b;
        a=n/100;
        b=n%100;
        if(b<10)
        cout<<a<<'-'<<0<<b<<endl;
        else cout<<a<<'-'<<b<<endl;
    }
    else {
        int a,b;
        a=n/100;
        b=n%100;
             if(a<22)a+=2000;
             else a+=1900;

        if(b<10)cout<<a<<'-'<<0<<b<<endl;
        else cout<<a<<'-'<<b<<endl;
        }
    }

L-1-4 降价提醒机器人

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    double q;
    while (n -- )
    {
        cin>>q;
        if(q<m)printf("On Sale! %.1lf\n",q);
    }
    return 0;
}

L-1-5 大笨钟的心情

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a[50];
    for(int i=0;i<=23;i++)
    cin>>a[i];
    int q;
    while(cin>>q)
    {
        if(q<0||q>23)break;
        if(a[q]>50)cout<<a[q]<<" "<<"Yes"<<endl;
        else cout<<a[q]<<" "<<"No"<<endl;
    }
    return 0;
}

L-1-6 吉老师的回归

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string ss;
    string s1="easy",s2="qiandao";
    int n,m,f=0;
    cin>>n>>m;
    getchar();
    while(n--)
    {
        getline(cin,ss);
        if(ss.find(s1)==-1&&ss.find(s2)==-1)m--;
        if(m<0){
            cout<<ss<<endl;
            f=1;
            break;
        }
    }
    if(f==0)cout<<"Wo AK le"<<endl;
    return 0;
}

L-1-7 天梯赛的善良

#include<bits/stdc++.h>
using namespace std;
map<int,int>a;
int main()
{
    int n,mi=10000000,ma=-100000000;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int q;
        cin>>q;
        a[q]++;
        if(q>ma)ma=q;
        if(q<mi)mi=q;
    }
    cout<<mi<<" "<<a[mi]<<endl;
    cout<<ma<<" "<<a[ma]<<endl;
}

L-1-8 乘法口诀数列

#include<bits/stdc++.h>
using namespace std;
vector<int>a;
int main()
{
    int c,b,n,f=0;
    cin>>c>>b>>n;
    a.push_back(c);
    a.push_back(b);
    while(1)
    {
        if(a.size()>=n)break;
        int q=a[f]*a[f+1];

        if(q>=10)
        {
            a.push_back(q/10);
            a.push_back(q%10);
        }
        else a.push_back(q);
        f++;
    }
    for(int i=0;i<n-1;i++)
    cout<<a[i]<<" ";
    cout<<a[n-1]<<endl;
    return 0;
}

L-2-1 包装机

题目就是简单的栈和队列的模拟题，熟悉进栈出栈等操作就可以了。

#include<bits/stdc++.h>
using namespace std;
queue<char>a[110];
stack<char>b;
int main()
{
    string s;
    int n,m,l,q;
    cin>>n>>m>>l;
    for(int i=1;i<=n;i++)
    {
          cin>>s;
        for(int j=0;j<m;j++)
            a[i].push(s[j]);
    }
    while(1)
    {
        cin>>q;
        if(q==-1)break;
        if(q==0){
            if(b.size())
            {
                cout<<b.top();
                b.pop();
            }
        }
        else{
            if(a[q].size())
            {   
                if(b.size()==l)
                {
                    cout<<b.top();
                    b.pop();
                }
                b.push(a[q].front());
                a[q].pop();
            }
        }
    }
    return 0;
}

L-2-2 病毒溯源

题目要求最长的子链，其实是一个简单的树形dp。我们先统计入度，找到根节点，然后从根节点开始搜索。记录好每一层路径的长度就可以了。注意答案的存储方式，还有就是深度相同的情况下，我们要比较保证字典序最小。

#include<bits/stdc++.h>
using namespace std;
const int N = 10010, M = 10010;
struct edge{
    int u,v,ne;
}e[N];
int idx;
int ans[N],in[N],head[N]; ;
void add(int a, int b)
{
    e[idx].v=b, e[idx].ne =head[a], head[a] = idx ++ ;
}
int dfs(int u)
{
    int res = 0;
    ans[u] = -1;
    for (int i = head[u]; ~i; i = e[i].ne)
    {
        int j = e[i].v;
        int d = dfs(j);
        if (res < d) res = d, ans[u] = j;
        else if (res == d) ans[u] = min(ans[u], j);
    }
    return res + 1;
}
int main()
{
    memset(head, -1, sizeof head);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int cnt;
        scanf("%d", &cnt);
        while (cnt -- )
        {
            int x;
            scanf("%d", &x);
            add(i, x);
            in[x]++;
        }
    }
    int root = 0;
    while (in[root]) root ++ ;
    printf("%d\n", dfs(root));
    printf("%d", root);
    while (ans[root] != -1)
    {
        root = ans[root];
        printf(" %d", root);
    }
    return 0;
}

L-2-3 清点代码库

题目就是去重加记录数量加排序，自己写结构体桶排序或者map都能解决问题，这里说一下map需要注意的细节。我们在把所有map存储结果从小到大排序时，首先要保证按键值排序，也就是map的second来决定，然后由于从大往小排，我们直接把负数加进去就行了。在输出是，如果不支持c++17特性，需要自己写迭代器的定义，注意如果用迭代器枚举，map的键值不能用.first来获取，而是要用指针->first来解决问题。

#include<bits/stdc++.h>
using namespace std;
int n,m,x;
map<vector<int>,int> mp;
vector<pair<int,vector<int>>> ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        vector<int> v;
        for(int j=0;j<m;j++){
            scanf("%d",&x);
            v.push_back(x);
        }
        mp[v]++;
    }
    printf("%ld\n",mp.size());
    for (auto it:mp) 
        ans.push_back({-it.second,it.first});
    sort(ans.begin(),ans.end());
    for(auto i:ans){
        printf("%d",-i.first);
        for(auto j:i.second){
            printf(" %d",j);
        }
        printf("\n");
    }
}

给一个迭代器版本的代码

#include<bits/stdc++.h>
using namespace std;
int n,m,x;
map<vector<int>,int> mp;
vector<pair<int,vector<int>>> ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        vector<int> v;
        for(int j=0;j<m;j++){
            scanf("%d",&x);
            v.push_back(x);
        }
        mp[v]++;
    }
    printf("%ld\n",mp.size());
    map<vector<int>,int>::iterator it;      
    for (it = mp.begin(); it != mp.end(); ++it) 
        ans.push_back({-it->second,it->first});
    sort(ans.begin(),ans.end());
    vector<pair<int,vector<int>>>::iterator i;
    vector<int>::iterator j;
    for(i = ans.begin(); i != ans.end(); ++i){
        printf("%d",-i->first);
        for(j=i->second.begin();j!=i->second.end();j++){
            printf(" %d",*j);
        }
        printf("\n");
    }
}

L-2-4 哲哲打游戏

直接vector存图，模拟一下就行了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=105;
int n,m,record[M],k,x;
vector<int> g[N];
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>k;
        while(k--) cin>>x,g[i].push_back(x);
    }
    int pos=1;
    while(m--){
        cin>>x>>k;
        if(x==0) pos=g[pos][k-1];
        else if(x==1) record[k]=pos,cout<<pos<<endl;
        else pos=record[k];
    }
    cout<<pos<<endl;
}

L-3-1 森森旅游

题目挺长，但大概可以分成两部分，第一部分就是先求出最基础的单源最短路，一遍从前面扫，一遍从后面扫，枚举中点，从前面的用人民币，后面的用旅游金。后面维护一个数据结构保护所有汇率的变化后最优解，可以写线段树，可以用优先队列，也可以multiset来维护，关键就是我们不能把所有重复的值都删掉，如果用优先队列，我们需要加一维变量记录该点汇率有没有发生变化。然后如果堆顶不合法，就直接删除。保证解的合法性

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
const int N = 100010, M = 200010 * 2;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
int n, m, Q;
int h1[N], h2[N], e[M], w[M], ne[M], idx;
LL dist1[N], dist2[N];
bool st[N];
LL rato[N],g[N];
void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra(int h[], LL dist[], int start) 
{
    memset(dist, 0x3f, sizeof dist1);
    memset(st, 0, sizeof st);
    dist[start] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, start});
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &Q);
    memset(h1, -1, sizeof h1);
    memset(h2, -1, sizeof h2);
    while (m -- )
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(h1, a, b, c), add(h2, b, a, d);
    }
    for (int i = 1; i <= n; i ++ ) scanf("%d", &rato[i]);
    dijkstra(h1, dist1, 1);
    dijkstra(h2, dist2, n);
       priority_queue<PII, vector<PII>, greater<PII> > heap;
    for (int i = 1; i <= n; i ++ )
        if (dist1[i] != INF && dist2[i] != INF)
        {
            g[i] = dist1[i] + (dist2[i] + rato[i] - 1) / rato[i];
            heap.push({g[i],i});
        }
    while (Q -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (dist1[a] != INF && dist2[a] != INF)
        {
            rato[a] = b;
            LL t1 =dist1[a] + (dist2[a] + rato[a] - 1) / rato[a];
            g[a] = t1;
            heap.push({g[a],a});
        }
        PII t = heap.top();
        
        if (Q!=0)
        cout<<t.first<<endl;
        else cout<<t.first;
    }
    return 0;
}

L-3-2 还原文件

其实就是一个字符串匹配加搜索，字符串匹配暴力匹配都已经能那一半分了，如果要继续优化。可以用kmp来找，也可以用hash直接O（1）判断。或者AC自动机也能达到同样的效果。这里给一个字符串hash的做法，注意定义unsigned long long为数组大小，相当与对2的64次方自动取模。p选择131，冲突概率很小。剩下的就搜一下就行了。

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=110,P=131;
typedef unsigned long long ULL;
ULL g[N],h[N],p[N];
int a[N],ans[N],n,m;
bool mp[N];
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
bool dfs(int u,int end)
{
    if(end==n)return true;
    for(int i=1;i<=m;i++)
    {
        if(!mp[i]&&g[i]==get(end,end+a[i]-1))
        {
            mp[i]=1;
            ans[u]=i;
             if (dfs(u + 1, end + a[i] - 1)) return true;
            mp[i] = 0;
        }
    }
    return false;

}
int main()
{
    scanf("%d", &n);
    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + x + 1;
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i ++ )
    {
        scanf("%d", &a[i]);
        for (int j = 0; j < a[i]; j ++ )
        {
            int x;
            scanf("%d", &x);
            g[i] = g[i] * P + x + 1;
        }
    }
    dfs(1, 1);
    for (int i = 1; i <= m; i ++ )
    {
        printf("%d", ans[i]);
        if (i != m) printf(" ");
    }
return 0;
}