2021/4/24天梯赛

作者： 作者的头像   Auto ,  2021-04-25 13:17:58 ,  所有人可见 ,  阅读 737

5


3
  • L1-1
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    cout << "To iterate is human, to recurse divine.";

    return 0;
}
  • L1-2

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

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    cin >> n >> m >> k;
    cout << n - m * k << endl;

    return 0;
}
  • L1-3
// 这个题有个坑点，也不算是坑点吧，题目给的是6位或者4位，我直接认为给了4位开始。


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

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    string str;
    cin >> str;

    if(str.size() == 4){
        int f1 = (str[0] - '0') * 10 + str[1] - '0';
        if(f1 < 22){
            printf("20%02d-%c%c",f1,str[2],str[3]);
        }else{
            cout << 19 << f1 << '-' << str[2]  << str[3] << endl;
        }
    }else{
        string s1;
        s1 += str[0];
        s1 += str[1];
        s1 += str[2];
        s1 += str[3];
        cout << s1 << '-' << str[4] << str[5] << endl;
    }



    return 0;
}
  • L1-4
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    int n,m;
    cin >> n >> m;
    double p;
    while(n --){
        double x;
        cin >> x;
        if(x < m){
            printf("On Sale! %.1lf\n",x);
        }
    }


    return 0;
}
  • L1-5
// 有个坑点就是超出了范围，题目里面明确说了，希望这个地方注意一下
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    for(int i = 0;i < 24;i ++){
        cin >> ans[i];
    }
    int x;
    while(cin >> x && x != -1){
        if(x >= 24 || x < 0) break;
        if(ans[x] > 50){
            printf("%d Yes\n",ans[x]);
        }else{
            printf("%d No\n",ans[x]);
        }
    }


    return 0;
}
  • L1-6
// 我当时没有getchar()，找了好长时间的bug
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<string>vec;
int k;
int ans[N];

int main()
{
    vec.clear();
    cin >> n >> k;
    getchar();
    for(int i = 0;i < n;i ++){
        string str;

        getline(cin,str);
        if(str.find("easy") != -1) continue;
        if(str.find("qiandao")!= -1) continue;
        vec.push_back(str);
    }


    if(k >= vec.size()) cout << "Wo AK le" << endl;
    else
    cout << vec[k] << endl;

    return 0;
}
  • L1-7
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec;
int k;
int ans[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0,x;i < n;i ++){
        cin >> x;
        vec.push_back(x);
    }

    sort(vec.begin(),vec.end());

    int f1 = vec[0],f2 = vec[vec.size() - 1];
    int cnt = 0;
    for(auto &x : vec){
        if(x == f1){
            cnt ++;
        }
    }
    cout << f1 << ' ' << cnt << endl;
    cnt = 0;
    for(auto &x : vec){
        if(x == f2){
            cnt ++;
        }
    }

    cout << f2 << ' ' << cnt << endl;

    return 0;
}
  • L1-8
// 这个直接模拟就好了，有个点就是 >= 10，我当时写成了 > 10，差一分满分，不过立刻找出来了这个错误
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec;
int k;
int ans[N];

int main()
{
    int a,b,c;
    cin >> a >> b >> c;

    vec.push_back(a);
    vec.push_back(b);
    int f1 = 0,f2 = 1;
    while(vec.size() < c + 100){
        int f3 = vec[f1] * vec[f2];
    //  cout << f3<< endl;

        if(f3 >= 10){
            vec.push_back(f3 / 10);
            vec.push_back(f3 % 10);
        }
        else{
            vec.push_back(f3);
        }
        f1 ++;
        f2 ++;
    }

    for(int i = 0;i < c;i ++){
        if(i == c - 1){
            cout << vec[i];
        }else{
            cout << vec[i] << ' ';
        }
    }

    return 0;
}
  • L2-1
// 我个人觉得题意有点问题，也可能是我的阅读理解不太好，就是如果栈满了话，并且此时操作的那个序列已经到头了，这视为一种无用的操作，而不是把栈顶元素放入到答案中
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m,k;
vector<pair<string,int>>vec;

int main()
{
    cin >> n >> m >> k;   
    string str;
    vec.push_back({"",0});
    for(int i = 0;i < n;i ++){
        cin >> str;
        vec.push_back({str,0});
    }

    string ans;
    int op;
    stack<char>stk;
    while(cin >> op && op != -1){

        int id1 = vec[op].second;
        if(id1 >= m) continue;
        if(stk.size() == 0 && op == 0) continue;
        if(op != 0 && stk.size() >= k){
            ans += stk.top();
            stk.pop();
        }

        if(op == 0){

            ans += stk.top();
            stk.pop();
        }else{

            int id = vec[op].second;
            if(id >= m) continue;
            stk.push(vec[op].first[id]);
            vec[op].second ++;
        }

    }
    cout << ans << endl;

    return 0;
}
/*
3 4 100
GPLT
PATA
OMSA
3 2 3 0 1 2 0 2 2 0 -1

*/
  • L2-2
// 那个字典序最小的串，有点难到我了，于是就先放了一下，先做L2-3，然后L2-310分钟左右写完了，就发现这俩好像一模两样，把所有的答案记录下来，然后按照L2-3的那个排序排个序就好了
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int din[N];

int dist[N];
int pre[N];
int ans = 0;
vector<int>v;

void dfs(int p)
{
    for(auto &x : vec[p]){
        if(dist[x] <= dist[p] + 1){
            dist[x] = dist[p] + 1;  
            pre[x] = p;
        }

        if(dist[x] > dist[ans]){
            ans = x;
        }
        else if(dist[x] == dist[ans]){
            if(x < ans){
                ans = x;
            }
        }
        dfs(x);
    }
}

vector<int> ans1;

void dfs1(int p)
{
    ans1.push_back(p);
    if(pre[p] == -1) return;
    dfs1(pre[p]);
}

int main()
{
    memset(pre,-1,sizeof(pre));

    cin >> n;
    for(int i = 0;i < n;i ++){
        int k;
        cin >> k;
        while(k --){
            int x;
            cin >> x;
            vec[i].push_back(x);
            din[x] ++;
        }
    }
    int root;
    for(int i = 0;i < n;i ++){
        if(din[i] == 0){
            root = i;
            break;
        }
    }

    ans = root;
    dist[root] = 1;

    dfs(root);
    vector<vector<int>>v1;
    for(int i = 0;i < n;i ++){
        if(dist[i] == dist[ans]){
            v.push_back(i);
            dfs1(i);
            reverse(ans1.begin(),ans1.end());
            v1.push_back(ans1);
            ans1.clear();
        }
    }

    cout << dist[ans] << endl;

    sort(v1.begin(),v1.end(),[](vector<int>p1,vector<int>p2){
        int n1 = p1.size();
        int n2 = p2.size();
        for(int i = 0;i < n1 && i < n2;i ++){
            if(p1[i] == p2[i]) continue;
            return p1[i] < p2[i];
        }

        return n1 < n2;

    });

    for(int i = 0;i < v1[0].size();i ++){
        if(i == v1[0].size() - 1){
            cout << v1[0][i];
        }else{
            cout << v1[0][i] << ' ';
        }
    }

    return 0;
}
  • L2-3
// 我同学第一维有用string的，我认为这是一个好的选择
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];

map<vector<int>,int>mp;

vector<pair<vector<int>,int>>v;

int main()
{
    cin >> n >> m;
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < m;j ++){
            int x;
            cin >> x;
            vec[i].push_back(x);
        }
        mp[vec[i]] ++;
    }

    for(auto &x : mp){
        v.push_back({x.first,x.second});
    }

    sort(v.begin(),v.end(),[](pair<vector<int>,int> p1,pair<vector<int>,int> p2){

        if(p1.second == p2.second){
            for(int i = 0;i < p1.first.size();i ++){
                if(p1.first[i] == p2.first[i]) continue;
                return p1.first[i] < p2.first[i];
            }
        }
        return p1.second > p2.second;
    });
    cout << v.size() << endl;

    for(auto &x : v){
        cout << x.second;

        for(auto &y : x.first){
            cout << ' ' << y;
        }
        cout << endl;
    }


    return 0;
}
  • L2-4
// 最开始做的这个题，我当时以为我是第一个A掉的，原来是我想多了。
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    cin >> n >> m;

    for(int i = 1;i <= n;i ++){
        vec[i].push_back(0);
    }

    for(int i = 1;i <= n;i ++){
        cin >> k;
        for(int j = 0,x;j < k;j ++){
            cin >> x;
            vec[i].push_back(x);
        }
    }
    int s = 1,cnt = 1;
    for(int i = 1;i <= m;i ++){
        int op,w;
        cin >> op >> w;
        if(op == 0){
            s = vec[s][w];
        }else if(op == 1){
            ans[w] = s;
            cout << s << endl;
            s = ans[w];

        }else if(op == 2){
            s = ans[w];
        }
    }
    cout << s << endl;

    return 0;
}
  • L3-1
  • 这个题好像是卡掉spfa，我超时了一个点，，用了对优化的dijkstra，就不超时了，
  • 还有一个点错的可能是n等于1的情况
  • 思路:计算1各个点的最短路，这个是记录花费现金到每个地方的最小花费
  • 再计算n到各个点的最短路，这个记录的是n号点用旅游金到每个点的最少花费
  • 路是单向的，不要弄错了。
  • 然后通过优先队列来找到目标答案
  • 注意一下我这里虽然写的spfa，但是实际用的对优化的dijkstra
  • 注意这个题如果不能到达的话，不能加入到答案的优先队列中
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m,q;
const LL N = 1e6 + 10;
vector<pair<LL,pair<LL,LL>>>vec[N];
LL w[N];
const LL INF = 1e18;
bool st[N];
LL dist1[N];
LL dist2[N];

LL cost[N];

void spfa(LL *dist,LL op,LL s)
{
    memset(st,0,sizeof st);
    dist[s] = 0;

    priority_queue<pair<LL,LL>,vector<pair<LL,LL>>,greater<pair<LL,LL>>>heap;
    heap.push({0,s});

    while(heap.size())
    {
        auto tt = heap.top();
        LL t = tt.second;
        heap.pop();
        if(st[t]) continue;
        st[t] = false;
        for(auto &x : vec[t]){
            LL f1 = x.first;
            LL f2;
            if(op == 1){
                f2 = x.second.first;
            }
            else{
                f2 = x.second.second;
            }
            if(dist[f1] > dist[t] + f2){
                dist[f1] = dist[t] + f2;
                    heap.push({dist[f1],f1});
            }
        }
    }
}


int main()
{
    cin >> n >> m >> q;

    for(LL i = 0;i < m;i ++){
        LL a,b,c,d;
        cin >> a >> b >> c >> d;
        if(a == b) continue;
        vec[a].push_back({b,{c,INF}});
        vec[b].push_back({a,{INF,d}});
    }

    for(LL i = 1;i <= n;i ++){
        cin >> w[i];
        dist1[i] = INF;
        dist2[i] = INF;
    }

    spfa(dist1,1,1);
    spfa(dist2,2,n);

    LL sum = INF;
    LL s;

    priority_queue<pair<LL,LL>,vector<pair<LL,LL>>,greater<pair<LL,LL>>>heap;

    for(LL i = 1;i <= n;i ++){
        if(dist1[i] == INF || dist2[i] == INF) continue;
        cost[i] = dist1[i] + (dist2[i] + w[i] - 1) / w[i];
        heap.push({cost[i],i});
    }
    sum = heap.top().first;
    while(q --)
    {
        LL a,b;
        cin >> a >> b;
        w[a] = b;
        if(dist1[a] == INF || dist2[a] == INF){
            cout << sum << endl;
            continue;
        } 
        cost[a] = dist1[a] + (dist2[a] + w[a] - 1) / w[a];
        heap.push({cost[a],a});

        while(heap.size())
        {
            auto t = heap.top();
            LL f1 = t.first,f2 = t.second;
            if(f1 < cost[f2]){
                heap.pop();
            }
            else{
                sum = f1;
                break;
            }
        }

        cout << sum << endl;
    }

    return 0;
}
  • L3-2
// 官方题解好像是KMP，但是我建了一个图，然后爆搜了一下，就过了
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n;
int a[N];
int k;
vector<int>vec[N];

int g[110][110];
vector<int>ans;

bool st[N];

bool dfs(int p,int s)
{

    int l1 = vec[p].size();
//  cout << p << ' ' << l1 << endl;

    for(int i = 0;i < l1;i ++){
        int i1 = s + i,i2 = i;
    //  cout << a[i1] << ' ' << vec[p][i2] << endl;
        if(a[i1] != vec[p][i2]){
            return false;
        }
    }

    if(s + l1 - 1 == n) {
        return true;    
    }

    for(int i = 1;i <= k;i ++){
        if(st[i]) continue;
        if(g[p][i]){
            st[i] = true;
            ans.push_back(i);
            if(dfs(i,s + l1 - 1)){
                return true;
            }
            ans.pop_back();

            st[i] = false;
        }
    }
    return false;
}

int main()
{

    cin >> n;
    for(int i = 1;i <= n;i ++)
        cin >> a[i];

    cin >> k;
    for(int i = 1;i <= k;i ++){
        int m;
        cin >> m;
        while(m --){
            int x;
            cin >> x;
            vec[i].push_back(x);
        }
    }

    unordered_set<int>stt;

    for(int i = 1;i <= k;i ++){
        int ed = vec[i][vec[i].size() - 1];
        for(int j = 1;j <= k;j ++){
            int f1 = vec[j][0];
            if(ed == f1){
                g[i][j] = 1;
            }
            if(f1 == a[1]){
                stt.insert(j);
            }
        }
    }

    for(auto &x : stt){
        ans.push_back(x);
        st[x] = true;
        if(dfs(x,1)){
            break;
        }
        st[x] = false;
        ans.clear();
    }

    for(int i = 0;i < ans.size();i ++){
        if(i == ans.size() - 1){
            cout << ans[i];
        }else{
            cout << ans[i] << ' ';
        }
    }

    return 0;
}

10 评论

用户头像
SolitudeAlma   2022-03-11 00:35         踩      回复

您好，我又来了，hhh
病毒那题其实有点问题，只不过测试数据没有给到，以下的测试数据能测

10
0
0
0
3 6 4 8
2 5 9
0
1 7
1 2
0
1 1

能救救废物吗

用户头像
Auto   2022-03-13 20:11         踩      回复

我默认为那个题为连通图，你这个好像0号点是孤立出来的

用户头像
SolitudeAlma   2022-03-13 21:35    回复了 Auto 的评论         踩      回复

是的，不是所有点都变异，y总的代码也不能过这个数据，因为不变异的点和起点（root）被标记为一样了

用户头像
凌乱之风   2021-04-25 21:26         踩      回复

现在这些题从哪里能交

用户头像
Auto   2021-04-26 12:42         踩      回复

目前好像还没更新到PTA题库，hh

用户头像
Auto   2021-04-26 12:44         踩      回复

PTA题库里面已经有了

用户头像
SolitudeAlma   2021-04-25 17:09         踩      回复

tql,签到那题没想到这么做，呜呜呜，还有那个栈的只拿了20，呜呜呜

用户头像
Auto   2021-04-25 17:16         踩      回复

那个栈我个人觉得题意不太清楚，我5分钟就写完了，应该是debug了20多分钟

用户头像
Auto   2021-04-25 17:18         踩      回复

有个地方就是判断栈满并且下一次操作的序列已经到头了，这相当于没有操作，也就是不能把栈顶元素放入到答案中

用户头像
SolitudeAlma   2021-04-25 19:03    回复了 Auto 的评论         踩      回复

我刚开始也没考虑栈空的情况，后来改来改去还是20