首页 💻 数据结构,📝 算法学习

写在前面: 上周六举办了今年的天梯赛, 其实本来不想参加了, 但是看了看220分能拿国二, 就抱着试一试的心态参加了, 结果还算比较满意, L1和L2都做完啦最终227分, 水了个个人国二hh, 下面来看一下本届的题目

PTA传送门

https://pintia.cn/problem-sets/994805046380707840/problems/type/7


L1-1、人与神

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652352

题意

输出 To iterate is human, to recurse divine.

思路

代码

print("To iterate is human, to recurse divine.")

L1-2、两小时学完C语言

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652353

题意

输入 $a, b, c$ , 输出 $a - b * c$

思路

代码

a = input().split()
print(int(a[0]) - int(a[1]) * int(a[2]))

L1-3、强迫症

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652354

题意

输入一个四位数或者六位数将其转换为年月

思路

六位直接中间加 -, 四位判断一下前两位

代码

s = input()
if len(s) == 4:
    if int(s) // 100 < 22:
        print("20" + s[0] + s[1] + "-" + s[2] + s[3])
    else:
        print("19" + s[0] + s[1] + "-" + s[2] + s[3])
else:
    print(s[0] + s[1] + s[2] + s[3] + "-" + s[4] + s[5])

L1-4、降价提醒机器人

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652355

题意

输入 $n, m$, 接下来输入 $n$ 个数 $x$ , 如果 $x < m$ 则输出 On Sale! x

思路

代码

a = input().split()
a[0] = int(a[0])
a[1] = float(a[1])
while a[0] != 0:
    a[0] -= 1
    x = float(input())
    if x < a[1]:
        print("On Sale! %.1f" % x)

L1-5、大笨钟的心情

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652356

题意

给出24个数如果大于50输出 Yes , 小于输出 No

思路

代码

a = input().split()
for i in range(24):
    a[i] = int(a[i])
x = int(input())
while x > -1 and x < 24:
    print(a[x], end = " ")
    if a[x] > 50:
        print("Yes")
    else:
        print("No")
    x = int(input())

L1-6、吉老师的回归

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652357

题意

输入一些题目名字, jls 会跳过带有 easyqiandao 的题目, 问 jls 现在在做哪个题

思路

直接模拟就行, 不过有两个细节

  • 就算当前已经做了 $m$ 个题, 接下来也要跳过所有带有 easyqiandao 的题目
  • 最后如果都做完了输出 Wo AK le

代码

n, m = input().split()
n = int(n)
m = int(m)
k = 0
f = False
while n != 0:
    n -= 1
    s = input()
    if 'easy' in s or 'qiandao' in s:
        continue
    if k == m:
        print(s)
        f = True
    k += 1
if f == False:
    print("Wo AK le")

L1-7、天梯赛的善良

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652358

题意

给出 $n$ 个数, 求其中最大和最小值并求出出现次数

思路

第一遍遍历求最值, 第二遍遍历求个数

代码

maxx = -1000000000000000000000
minn = 1000000000000000000000
x = 0
y = 0
n = int(input())
a = input().split()
for it in a:
    minn = min(minn, int(it))
    maxx = max(maxx, int(it))
for it in a:
    if int(it) == minn:
        x += 1
    if int(it) == maxx:
        y += 1
print(minn, x)
print(maxx, y)

L1-8、乘法口诀数列

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652359

题意

给出 $a_1, a_2, n$ , 定义 $a_i = a_{i-1} * a_{i-2}$ (PS: 如果 $a_i$ 大于9则拆分)

思路

斐波那契数列加强版, 将加法变为乘法, 如果结果大于9就拆分一下 push 到后面

代码

k = 1
a = input().split()
n = int(a[2])
a.pop()
a[0] = int(a[0])
a[1] = int(a[1])
while k < n - 1:
    x = a[k - 1] * a[k]
    if x < 10:
        a.append(x)
    else:
        y = str(x)
        for i in range(len(y)):
            a.append(int(y[i]))
    k += 1
for i in range(n - 1):
    print(a[i], end = " ")
print(a[n - 1])

L2-1、包装机

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652360

题意

题目有点长就不写了

思路

筐用栈维护, $n$ 条轨道用 $n$ 个队列维护, 模拟一下记录答案即可

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 105;
queue<char> q[maxn];
stack<char> s;
string ans;
ll n, m, k, x;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(ll i = 1; i <= n; i++){
        string _;
        cin >> _;
        for(auto it : _) q[i].push(it);
    }
    while(cin >> x && x != -1){
        if(x == 0 && !s.empty()) ans += s.top(), s.pop();
        else{
            if(q[x].empty()) continue;
            if(s.size() == k) ans += s.top(), s.pop();
            auto head = q[x].front(); q[x].pop();
            s.push(head);
        }
    }
    cout << ans << endl;
    
    return 0;
}

L2-2、病毒溯源

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652361

题意

给出一棵树, 求从根节点出发的一条字典序最小且最深的链

思路

正解应该是拓扑排序, 本蒟蒻已经忘了拓扑排序是什么了emmm, 所以现场的时候写的巨复杂 dfs(求最大深度) + bfs(求路径) 轰炸

代码

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll maxn = 1e4 + 5;
vector<ll> edge[maxn];
ll n, k, x, y, ans, in[maxn], o[maxn];
vector<ll> res;

void dfs1(ll fa, ll step){
    ans = max(ans, step);
    for(auto it : edge[fa]){
        dfs1(it, step + 1);
    }
}

bool dfs2(ll fa, ll step){
    if(ans == step){
        return true;
    }
    bool f = false;
    for(auto it : edge[fa]){
        if(dfs2(it, step + 1)){
            o[it] = ans;
            f = true;
        }
    }
    return f;
}

queue<pair<ll, ll>> q;
void bfs(ll s){
    res.push_back(s);
    q.push({s, 1});
    while(!q.empty()){
        auto head = q.front();
        q.pop(); ll minn = 1e18;
        if(head.second == ans) return;
        for(auto it : edge[head.first]){
            if(o[it] != ans) continue;
            else{
                minn = min(minn, it);
            }
        }
        q.push({minn, head.second + 1});
        res.push_back(minn);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(ll i = 0; i < n; i++){
        cin >> k;
        while(k--){
            cin >> x;
            edge[i].push_back(x);
            in[x]++;
        }
    }
    for(ll i = 0; i < n; i++){
        if(!in[i]){
            dfs1(i, 1);
            y = i;
            break;
        }
    }
    dfs2(y, 1); o[y] = ans;
    cout << ans << endl;
    vector<ll> v; v.clear(); v.push_back(y);
    bfs(y);
    for(ll i = 0; i < res.size() - 1; i++) cout << res[i] << " ";
    cout << res[res.size() - 1];
    
    return 0;
}

L2-3、清点代码库

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652362

题意

给出一系列数组, 首先按照出现次数降序排序, 出现次数相同的情况下按照字典序升序排序

思路

巧用 stl , map 计数, vector + pair 排序(PS: 这题对时间卡的比较严, 如果第一次提交 TLE, 就再提交两次, 轰炸一下判题机)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e4 + 5;
map<vector<ll>, ll> mp;
vector<pair<ll, vector<ll>>> v;
ll n, m, x;

bool cmp(pair<ll, vector<ll>> x, pair<ll, vector<ll>> y){
    if(x.first != y.first) return x.first > y.first;
    else{
        for(ll i = 0; i < m; i++)
            if(x.second[i] != y.second[i]) return x.second[i] < y.second[i];
    }
}

int main(){
    scanf("%lld%lld", &n, &m);
    while(n--){
        vector<ll> _; _.clear();
        for(ll i = 1; i <= m; i++) scanf("%lld", &x), _.push_back(x);
        mp[_]++;
    }
    for(auto it : mp) v.push_back({it.second, it.first});
    sort(v.begin(), v.end(), cmp);
    printf("%lld\n", mp.size());
    for(ll i = 0; i < v.size(); i++){
        pair<ll, vector<ll>> it = v[i];
        printf("%lld", it.first);
        for(ll j = 0; j < it.second.size(); j++) printf(" %lld", it.second[j]);
        printf("\n");
    }
    
    return 0;
}

L2-4、哲哲打游戏

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652363

题意

给出一个图, 一共有三个操作

  1. 输入0, 接着输入 $j$ , 进入当前节点的第 $j$ 个邻接点
  2. 输入1, 接着输入 $j$ , 将当前节点存档到第 $j$ 个挡位并输出
  3. 输入2, 接着输入 $j$ , 选择第 $j$ 个挡位

思路

这题本人感觉原题叙述不太好读懂, 我这题读了好久才明白题意, 其实就是建图, 然后模拟输出emmm

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
vector<ll> edge[maxn];
ll n, m, k, s = 1, a[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(ll i = 1; i <= n; i++){
        cin >> k; ll x;
        while(k--) cin >> x, edge[i].push_back(x);
    }
    while(m--){
        ll op, x;
        cin >> op >> x;
        if(op == 0) s = edge[s][x - 1];
        else if(op == 1) a[x] = s, cout << s << "\n";
        else s = a[x];
    }
    cout << s;
    
    return 0;
}

L3-1、森森旅游

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652364

题意

给出一个图, 途中可以再某个城市将现金换为旅游金, 多次改变更换汇率, 问从起点到终点所需要花费的最少现金

思路

迪杰斯特拉+优先队列(PS: 借鉴huah聚代码)

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void out(int x){printf("%d\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
const int N=2e5+5;
int n,m,k,a[N];
ll dis[2][N];
vector<pair<int,int>>e[2][N];
struct node
{
    int u;ll dis;
    node(int u=0,ll dis=0):u(u),dis(dis){}
    bool operator<(const node&o)const
    {
        return dis>o.dis;
    }
};
priority_queue<node>q;
bool vis[N];
void dij(int u,vector<pair<int,int>>e[N],ll dis[N])
{
    memset(vis,false,sizeof(vis));
    rep(i,1,n) dis[i]=inf;
    dis[u]=0;
    q.push(node(u,dis[u]));
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(pair<int,int>x:e[u])
        if(dis[x.first]>dis[u]+x.second)
        {
            dis[x.first]=dis[u]+x.second;
            q.push(node(x.first,dis[x.first]));
        }
    }
}
priority_queue<ll,vector<ll>,greater<ll>>ans,del;
ll cal(int u)
{
    if(dis[0][u]==inf||dis[1][u]==inf) return inf;
    return dis[0][u]+dis[1][u]/a[u]+(dis[1][u]%a[u]!=0);
}
int main()
{
    sc(n,m,k);
    while(m--)
    {
        int u,v,c,d;
        sc(u,v);sc(c,d);
        e[0][u].push_back({v,c});
        e[1][v].push_back({u,d});
    }
    rep(i,1,n) sc(a[i]);
    dij(1,e[0],dis[0]);
    dij(n,e[1],dis[1]);
    rep(u,1,n) ans.push(cal(u));
    while(k--)
    {
        int u,y;sc(u,y);
        del.push(cal(u));
        a[u]=y;
        ans.push(cal(u));
        while(del.size()&&del.top()==ans.top()) del.pop(),ans.pop();
        printf("%lld\n",ans.top());
    }
    return 0;
}

L3-2、还原文件

展开查看详情

题目传送门

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652365

题意

题目太长懒得写了

思路

dfs+暴力, 这题场上我差不多也是这样写的, 但是 wa 了一个点(并不是 TLE , 就很神奇), 不知道是哪里出问题了

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void out(int x){printf("%d\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
const int N=2e5+5,mod1=998244353,mod2=1e9+7;
const int b1=233,b2=2992;
int ib1,ib2;
ll qpow(ll a,ll n,ll mod)
{
    ll ans=1;
    for(;n;n>>=1,a=a*a%mod)
        if(n&1) ans=ans*a%mod;
    return ans;
}
int n,m,a[N],k[N],las[N];
ll hh1[N],hh2[N],gh1[N],gh2[N];
ll f1[N],f2[N],if1[N],if2[N],hs1[N],hs2[N];
vector<int>e[N];
int top,s[N];
bool inq[N];
void dfs(int cur,int len,ll h1,ll h2)
{
    if(h1!=hs1[len]||h2!=hs2[len]) return;
    if(len==n)
    {
        for(int i=1;i<=top;i++)
            printf(i==top?"%d\n":"%d ",s[i]);
        exit(0);
    }
    for(int nex:e[las[cur]])
    if(!inq[nex])
    {
        inq[s[++top]=nex]=true;
        dfs(nex,len+k[nex]-1,(h1+gh1[nex]*f1[len]%mod1)%mod1,(h2+gh2[nex]*f2[len]%mod2)%mod2);
        inq[s[top--]]=false;
    }
}
int main()
{
    ib1=qpow(b1,mod1-2,mod1);
    ib2=qpow(b2,mod2-2,mod2);
    f1[0]=f2[0]=1;
    rep(i,1,N-1)
    {
        f1[i]=f1[i-1]*b1%mod1;
        f2[i]=f2[i-1]*b2%mod2;
        if1[i]=if1[i-1]*ib1%mod1;
        if2[i]=if2[i-1]*ib2%mod2;
    }
    sc(n);
    rep(i,1,n) sc(a[i]),a[i]++;
    rep(i,1,n)
    {
        hs1[i]=(hs1[i-1]+a[i]*f1[i])%mod1;
        hs2[i]=(hs2[i-1]+a[i]*f2[i])%mod2;
    }
    sc(m);
    rep(i,1,m)
    {
        sc(k[i]);
        rep(j,1,k[i])
        {
            int x;sc(x);x++;
            hh1[i]=(hh1[i]+x*f1[j])%mod1;
            hh2[i]=(hh2[i]+x*f2[j])%mod2;
            if(j==1) e[x].push_back(i);
            else
            {
                gh1[i]=(gh1[i]+x*f1[j-1])%mod1;
                gh2[i]=(gh2[i]+x*f2[j-1])%mod2;
            }
            las[i]=x;
        }
    }
    for(int i=1;i<=m;i++)
    {
        inq[s[++top]=i]=true;
        dfs(i,k[i],hh1[i],hh2[i]);
        inq[s[top--]]=false;
    }
    return 0;
}

L3-3、可怜的简单题




文章评论

    巴别塔 访客ChromeWindows
    2021-05-5 21:27   回复

    楼主代码好棒啊,主页做的也好棒啊.