526互联

AtCoder Beginner Contest(abc) 321

发布时间 2023-11-09 22:46:09作者: mostimali



B - Cutoff

难度: ⭐⭐

题目大意

一场考试有n门成绩, 最终成绩是减去最大值和最小值后的和; 现在给出n-1门成绩, 问最后一门成绩最少为多少可以让总成绩大于等于m;

解题思路

列举第n门成绩由小到大时其他成绩所要满足的条件即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 300 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
signed main() {
    cin>>n>>m;
    int mx=0,mn=1e9;
    for(int i=1;i<n;i++){
        int x;
        cin>>x;
        mx=max(mx,x);
        mn=min(mn,x);
        idx+=x;
    }
    if(idx-mx>=m) cout<<0;
    else if(m-idx+mx+mn<=mx) cout<<m-idx+mx+mn;
    else if(idx-mn>=m) cout<<mx;
    else cout<<-1;
    return 0;
}



C - 321-like Searcher

难度: ⭐⭐⭐

题目大意

如果一个数字从前往后各位上的数字是递减的, 那么那个数字就被称为321型数字; 个位数也算321型数字; 问从1开始第k个321型数字是多少;

解题思路

本题想要设计算法来求第k个321型数字就比较困难的, 但是通过打表我们发现整数范围内321型数字数量并不算多, 根据其特性, 我们可以用bfs得到所有321型数字;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int d[N];
void bfs(){
    queue<int> q;
    for(int i=1;i<=9;i++){
        q.push(i);
    }
    while(q.size()){
        int t =q.front();
        q.pop();
        d[++idx]=t;
        for(int i=0;i<t%10;i++){
            int x=t*10+i;
            q.push(x);
        }
    }
}
signed main() {
    bfs();
    cin>>n;
    cout<<d[n];
    return 0;
}



D - Set Menu

难度: ⭐⭐

题目大意

菜单上有n种汉堡和m种薯条, 其价格为Ai和Bi; 我们需要把一个汉堡和一个薯条组成一个套餐; 如果该汉堡和薯条的价值和Ai + Bi大于p, 那么该套餐的价格就是p; 否则价格就是Ai + Bi; 请问所有可能的套餐组合的价格总和是多少;

解题思路

因为当Ai + Bi大于p时, 价格就设为p, 所以我们可以把薯条的价格从小到大排序, 对于每种汉堡, 我们用二分找到薯条中第一个与其价格相加大于等于p的; 在这个薯条之前的价格和可以用前缀和来算, 后面的就可以都用p来算; 注意可能薯条中没有与汉堡价格相加大于等于p的, 所以我们的右边界要多出一个表示没找着;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int a[N],b[N],bs[N];
signed main() {
    int p;
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    sort(b+1,b+1+m);
    for(int i=1;i<=m;i++) bs[i]=bs[i-1]+b[i];
    for(int i=1;i<=n;i++){
        int x=a[i];

        int l=1,r=m+1;
        while(l<r){
            int mid=l+r>>1;
            if(b[mid]+x<p) l=mid+1;
            else r=mid; 
        }
        idx = idx+p*(m-l+1)+bs[l-1]+(l-1)*x;
    }
    cout<<idx;
    return 0;
}



E - Complete Binary Tree

难度: ⭐⭐⭐⭐

题目大意

给定一颗二叉树, 设根节点是n, 那么其左孩子就是2 * n, 右孩子是2 * n+1; 这棵树的根节点是1; 给出q次询问, 每次询问给出三个参数n, x, k; 表示这颗二叉树一共有n个节点, 请问和节点x相距k条边的节点数量;

解题思路

因为节点数量n的范围太大, 暴力遍历肯定是不可能的; 我们先看从节点x往下找的时候, 通过观察二叉树我们发现, 所有与x相距k条边的节点都在同一层上, 并且是连续的; 所以我们可以去确定这一层中满足条件区间的左端点和右端点; 左端点好找, 我们需要让x * 2重复k遍就可以到达该层; 右端点则是x * 2 + 1; 注意如果最终左端点大于n, 则说明我们找的那一层不存在; 如果右端点大于n, 则说明这一层就是二叉树的最后一层, 并且该二叉树不是一颗满二叉树, 这时候我们直接让r=n即可, n一定就在那一层;
这样我们就找到了从节点x向下找距离其k条边的所有结点; 然后我们开始往上走, 用x / 2就可以得到x的祖先, 对于x的第p个祖先, 我们只需要向下找距离其k-p条边的点就可以了; 注意从祖先往下走时可能会找到之前已经找过的节点, 所以在计算完x的第p个祖先时, 要将其减去x的第p-1个祖先往下距离其k-p-1条边的节点数量就可以完成去重了; 复杂度是(n*logn2);

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int find(int u,int k){
    if(k<0) return 0;
    int l=u, r=u;
    for(int i=1;i<=k;i++){
        l*=2;
        r=r*2+1;
        if(l>n) return 0;
    }
    if(r>n) r=n;
    return r-l+1ll;
}
signed main() {
    int t;
    cin>>t;
    while(t--){
        int x,k;
        cin>>n>>x>>k;
        int r=x;
        int p=0;
        int sum=find(x,k);
        while(r/2>=1){
            p++;
            sum+=find(r/2,k-p)-find(r,k-p-1);
            r/=2;
        }
        cout<<sum<<endl;
    }
    return 0;
}



F - #(subset sum = K) with Add and Erase

难度: ⭐⭐⭐

题目大意

现在有一个箱子,我们进行q次操作, 操作分两种, 一是往箱子里放一个值为x的球, 二是从箱子里拿出一个值为x的球(题目保证此时箱子里有这个球); 每次操作完都要输出此时用箱子里的球的值凑出k的方式有多少种;

解题思路

因为q和k都很小, 所以可以考虑O(q*k)的复杂度; 因为要计数, 所以可以考虑用dp; 如果往里面放一个值为x的球, 那么就可以让dp[i]+=dp[i-x], 但是要注意, 我们只往里放了一个球, 并且当前转移是把球作用于让i-x变成i, 所以我们此时用的dp[i-x]是每用过新放入的球的状态, 对此我们可以倒序遍历来解决; 对应的, 当我们从里面取出一个值为x的球时, 就是dp[i]-=dp[i-x]; 一样的问题, 该转移意思是这个球之前是让i-x变成i, 那么就要求dp[i-x]这个状态和这个球无关, 但是之前放这个球的时候dp[i-x]已经更新了, 所以我们要在更新dp[i-x]之后更新dp[i], 所以是正序遍历;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int dp[N];
signed main() {
    cin>>n>>m;
    dp[0]=1;
    while(n--){
        char c;
        int x;
        cin>>c>>x;
        if(c=='+'){
            for(int i=m;i>=x;i--){
                dp[i]=(dp[i]+dp[i-x])%mod;
            }
        }
        else{
            for(int i=x;i<=m;i++){
                dp[i]=(dp[i]-dp[i-x]+mod)%mod;
            }
        }
        cout<<dp[m]<<endl;
    }
    return 0;
}