IDT's Round 43 题解

· · 个人记录

A

知识点考查

难度分析

知识点难度系数 应得分数
1 100
2 100
3 100
4 100
5 100
6 100
7 100
8 100
9 100
10 100

题目解析

可以去重看下最大值次大值，也可以使用枚举比较求最大值和次大值。

参考代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,mx=-1,mx2=-1;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        if(x>mx)mx2=mx,mx=x;
        else if(x==mx)continue;
        else if(x>mx2)mx2=x;
    }
    if(mx2==-1)cout<<"No";
    else cout<<mx2;
    return 0;
}

B

知识点考查

难度分析

知识点难度系数 应得分数
1 80
2 100
3 100
4 100
5 100
6 100
7 100
8 100
9 100
10 100

题目解析

根据传入和传出口的数据线颜色求出传出数据来自于传入数据的位置，输出的时候，计算下对应的下标即可。

参考代码


#include<bits/stdc++.h>
using namespace std;
int n,c[100010];
int main()
{
    string a,b;
    cin>>a>>b;
    map<int,int> mp;
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
        {
            if(a[i]==b[j])
            {
                mp[j]=i;
                break;
            }
        }
    cin>>n;
    for(int i=0;i<n;i++)cin>>c[i];
    for(int i=0;i<n;i++)
    {
        int t=i/8*8+mp[i%8];
        cout<<c[t]<<' ';
    }
    return 0;
}

C

知识点考查

难度分析

知识点难度系数 应得分数
1 35
2 55
3 100
4 100
5 100
6 100
7 100
8 100
9 100
10 100

题目解析

大量的输入输出，需要优化，使用scanf和printf也可以，另外使用map的话要是用unordered_map

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
struct node
{
    int x,cnt,idx;
    bool operator<(const node &a)const{
        if(cnt==a.cnt)return idx<a.idx;
        else return cnt>a.cnt;
    }
}nd[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    unordered_map<int,int> mp;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        mp[x]++;
        nd[i].x=x;
        nd[i].idx=i;
    }
    for(int i=1;i<=n;i++)nd[i].cnt=mp[nd[i].x];
    sort(nd+1,nd+n+1);
    for(int i=1;i<=n;i++)cout<<nd[i].x<<' ';
    return 0;
}

D

知识点考查

难度分析

知识点难度系数 应得分数
1 15
2 25
3 45
4 100
5 100
6 100
7 100
8 100
9 100
10 100

题目解析

动态规划思路：从位置 i 可以到达那些位置呢，可以枚举 m 个区间，对于每个区间 L_j-R_j，我们可以从 i 到大 L[j]+i~R[j]+i 这个区间，那么 dp[L[j]+i~R[j]+i] 整个区间都要加上 dp[i]。

如果这么做，时间复杂度为 n^2\times m,需要优化。快速区间加上同一个数，可以使用差分,在 L[j]+i 处加上 dp[i], R[j]+i+1 处减去 dp[i]，这样前缀和数组就是答案。这里可以一边求前缀和一边更新后面的区间。

另外这道题，强调：前进次数不同或前进次数相同但是存在某一步前进距离不同,则认为两个方案不同，那么不同的火箭并不是不同的方案。这里要先做一下区间合并在做动态规划。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=998244353;
int n,m,dp[N];
struct node{
    int l,r;
    bool operator<(const node&a)const{
        return l<a.l;
    }
}nd[210],nd2[210];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>nd[i].l>>nd[i].r;
    sort(nd+1,nd+m+1);
    int cnt=0,ed=-1;
    for(int i=1;i<=m;i++){
        if(ed<nd[i].l){
            nd2[cnt].r=ed;
            nd2[++cnt].l=nd[i].l;
            ed=nd[i].r;
        }
        else ed=max(nd[i].r,ed);
    }
    nd2[cnt].r=ed;
    dp[0]=1;dp[1]=-1;
    for(int i=0;i<=n;i++){
        if(i>0)dp[i]=(dp[i]+dp[i-1])%mod;
        for(int j=1;j<=cnt;j++){
            int l=i+nd2[j].l,r=i+nd2[j].r;
            if(l>n)continue;
            if(r>n)r=n;
            dp[l]=(dp[l]+dp[i])%mod;
            dp[r+1]=((dp[r+1]-dp[i])%mod+mod)%mod;
        }
    }
    cout<<dp[n];
    return 0;
}