首页 > 其他分享 >ABC382&ABC383题解

ABC382&ABC383题解

时间:2025-01-14 11:22:40浏览次数:1  
标签:颜色 int 题解 leq ABC383 ABC382 alpha include dp

[ABC382C] Kaiten Sushi

题目描述

有 \(N\) 个人,编号从 \(1\) 到 \(N\),他们正在访问一家传送带寿司餐厅。第 \(i\) 个人的美食级别是 \(A_i\)。

现在,将会有 \(M\) 份寿司放置在传送带上。第 \(j\) 份寿司的美味度为 \(B_j\)。每份寿司将按照顺序经过编号为 \(1\),\(2\),\(\dots\),\(N\) 的人。每个人在看到美味度不低于他们美食级别的寿司经过时,会拿走并吃掉那份寿司;否则,他们什么也不做。一旦第 \(i\) 个人拿走并吃掉了寿司,那份寿司就不会再经过编号大于 \(i\) 的人。

对于每份 \(M\) 份寿司中的一份,请确定是谁吃掉了那份寿司,或者是否没有人吃掉它。

约束条件

\(1\le N\),\(M\le2\times10^5\)

\(1\le A_i\),\(B_i\le2\times10^5\)

所有输入值均为整数。

制約

  • $ 1\leq\ N,M\ \leq\ 2\times\ 10^5 $
  • $ 1\leq\ A_i,B_i\ \leq\ 2\times\ 10^5 $
  • 入力は全て整数

解题思路

以吃寿司的人为单位构造结构体,存储位置和美食级别。吃寿司的时候跟位置有关系,如果在后面的人的美食级别比前面的人还高的话,那肯定一口都吃不到,所以没必要存储。

所以存储的优先级第一为位置,第二为美食级别。存的一定是位置递增和美食级别递减的序列。

可以发现,对于美味度为\(d\)的寿司而言,如果能够被吃,一定是在这个序列当中美食级别第一个小于\(d\)的位置被吃的。因此可以考虑使用二分来解决该问题,总时间复杂度为\(O(nlogn)\)

将存储序列逆序排列,那么要找到的就是序列里小于等于\(d\)且最接近\(d\)的元素。因此注意二分的写法应当是

mid = (l + r + 1) / 2;
if(check())		l = mid;
else	r = mid - 1;

参考代码为:

//abc382c
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200005;
int a[N], b[N];

struct pp{
    int val, idx;
}p[N];

bool cmp(pp a, pp b){
    return a.val < b.val;
}

int main(){
    int n, m;
    cin >> n >> m;
    int minn = 0x3f3f3f, idx = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i] < minn){
            minn = a[i];
            p[++idx].val = a[i];
            p[idx].idx = i;
        }
    }
    sort(p, p+idx+1, cmp);
    int min_val = p[1].val;
    for(int i = 1; i <= m; i++){
        cin >> b[i];
        if(b[i] < min_val){
            cout << -1 << endl;
            continue;
        }
        //bs
        int l = 1, r = idx;
        int mid = (l + r + 1) / 2;
        while(l < r){
            mid = (l + r + 1) / 2;
            //cout << mid << endl;
            if(p[mid].val <= b[i])      l = mid;
            else    r = mid - 1;
        }
        cout << p[l].idx << endl;
    }
    return 0;
}

[ABC382D] Keep Distance

题目描述

给定整数 \(N\) 和 \(M\) 。按照字典序打印出来所有长度为 \(N\) ,且满足如下条件的整数序列 \((A_1, A_2, ..., A_N)\) :

  • \(1 \leq A_i\) ;
  • 对 \(i=2, ..., N\), 有 \(A_{i-1} + 10 \leq A_i\) ;
  • \(A_N \leq M\) 。

输入格式

一行,空格分隔的两个整数: \(N\ M\) 。

输出格式

第一行是一个整数,为所有满足条件的序列的个数;

之后每一行为空格分隔的 \(N\) 个整数,对应一个满足条件的整数序列。

制約

  • $ 2\ \leq\ N\ \leq\ 12 $
  • $ 10N\ -\ 9\ \leq\ M\ \leq\ 10N $
  • 入力される値はすべて整数

解题思路

一道很有意思的递归的题目

  • 递归时需要记录下当前递归到的值,以及递归到第几个位置。
  • 用一个二位数组记录所有答案(因为要先输出方案数量再输出每个方案)
  • 注意剪枝,否则会t。
//abc382d
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int n, m, idx = 0;
int a[15], ans[500005][15];

void f(int val, int pos){
    a[pos] = val;
    if(pos == n){
        idx ++;
        //存答案
        for(int i = 1; i <= n; i++)     ans[idx][i] = a[i];
        return;
    }
    int sep = 10;
    while(val + sep <= m && (m - val - sep) / 10 >= n - pos - 1){
        f(val + sep, pos + 1);
        sep++;
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i + (n-1) * 10 <= m; i++)        f(i, 1);
    cout << idx << endl;
    for(int i = 1; i <= idx; i++){
        for(int j = 1; j <= n; j++)
            cout << ans[i][j] << " ";
        cout << endl;
    }
    return 0;
}

[ABC383C] Humidifier 3

题目描述

给你一个 \(H\) 行 \(W\) 列的矩阵,如果为 # 代表为障碍物,. 为空地, H 为喷水器。
定义一个地方是湿的,当且仅当有从一个喷水器可以通过最多 \(D\) 步移动(四联通)到达这个地方。
注意,喷水器所在的地方也是湿的。
求有多少个湿的地方。

输入格式

第一行三个整数 \(H,W,D\)。
接下来 \(H\) 行,每行 \(W\) 个字符,描述矩阵。

输出格式

输出一个整数,表示答案。

数据范围

\(1\le H,W\le1000\)
\(1\le D\le H\times W\)

解题思路

用dfs一定会t...别问我怎么知道的

这道题用bfs做就没有问题啦

注意建立一个\(step\)数组,\(step[i][j]\)存储到达坐标点\((i,j)\)时还可以走多少步。

初始状态:所有喷水点的\(step\)值设为\(d\),并且将喷水点入队列。其他点\(step\)值默认都为\(0\)。

扩散状态:每次取队头,朝四个方向扩散,如果扩散到的点\(step[i'][j']<=step[i][j]-1\),代表当前的扩散是可能对答案有贡献的,因此记录新\(step\)值并将新点入队。如果不满足该条件,证明本次扩散已经在前面的状态出现过了,没有必要再入队重复操作。

//abc383c
#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
char ch[1005][1005];
bool flag[1005][1005];
int step[1005][1005];
int h, w, d, ans = 0;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

void bfs(){
    while(!q.empty()){
        PII t = q.front();
        q.pop();
        if(step[t.first][t.second] > 0){
            for(int i = 0; i < 4; i++){
                int xx = t.first + dx[i];
                int yy = t.second + dy[i];
                if(1 <= xx && xx <= h && 1 <= yy && yy <= w &&  ch[xx][yy] == '.' && step[xx][yy] <= step[t.first][t.second] - 1){
                    q.push({xx, yy});
                    step[xx][yy] = step[t.first][t.second] - 1;
                    if(!flag[xx][yy])	flag[xx][yy] = 1, ans ++;
                }
            }
        }
    }
}

int main(){
    cin >> h >> w >> d;
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++)
            cin >> ch[i][j];
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++)
            if(ch[i][j] == 'H'){
                q.push({i, j});
                ans ++;
                flag[i][j] = 1;
                step[i][j] = d;
            }
    if(!q.empty())  bfs();
    cout << ans << endl;
    return 0;
}

[ABC383D] 9 Divisors

题目描述

找出不大于 \(N\) 且恰好有 \(9\) 个因数的正整数的个数。

输入格式

只有一行,一个整数 \(N\)。

输出格式

一行一个整数,表示答案。

数据范围

  • \(1 \leq N \leq 4 \times 10^{12}\)
  • 所有输入值均为整数。

解题思路

前置知识:如何判断一个正整数\(N\)的因数个数

当\(N = p_1^{\alpha_1}* p_2^{\alpha_2}*...*p_k^{\alpha_k}\)(其中\(p_i\)代表质数)

对于一个数的所有约数,一定可以由上面的通式来表示,且有所对应的\(\alpha_1\)、\(\alpha_2\)、\(\alpha_3\)。

约数用M表示,那么\(M = p_1^{\beta_1}* p_2^{\beta_2}*...*p_k^{\beta_k}\)

对于\(\beta_1\)、\(\beta_2\)、\(\beta_3\)的取值范围,为\(0~\)~\(\alpha_i\),就能够表示出来所有的约数。所以求约数个数实际可拆解为组合数学(乘法原理)。

所以对于正整数\(N\)而言,其对应的约数个数为\((\alpha_1+1)*(\alpha_2+1)*(\alpha_3+1)...(\alpha_k+1)\)

对于该结论,结合本道题要求恰好有 \(9\) 个因数,可以分析得出:

  • 因数都是成对出现,若一个数\(X\)恰好有\(9\)个因数,代表一定有一对的因数相等,所以\(X\)一定是一个完全平方数。

  • 约数个数满足\((\alpha_1+1)*(\alpha_2+1)*(\alpha_3+1)...(\alpha_k+1)=9\),其组合方法可以表示为\(9\)或是\(3*3\)。

    1)对于第一种,若\(X=p^8\)且\(X<=N\),那么\(X\)符合题目要求

    2)对于第二种,若\(X={p_1}^2*{p_2}^2\)且\(X<=N\),那么\(X\)符合题目要求

    因此对于一个可能作为答案的完全平方数\(X\),先去找到所有小于等于\(logX\)的质因数\(p\),再分两种方案枚举可能的值。最终把所有方案数加起来即为答案。

//abc383d
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
typedef long long ll;
const int N = 2e6+5;
ll prime[N];
bool not_prime[N];

int main(){
    ll n, idx = 0, ans = 0;
    cin >> n;
    //找出logn以内的所有指数 埃式筛法
    for(ll i = 2; i * i<= n; i++){
        if(!not_prime[i]){
            prime[++idx] = i;
            for(ll j = 2; j * i <= sqrt(n); j++)      not_prime[j * i] = 1;
        }
    }
    //算p^8的个数
    for(ll i = 1; i <= idx; i++)	if(pow(prime[i], 8) <= n)  ans ++;
    //算p^2和q^2的个数
    for(ll i = 1; i < idx; i++){
        for(ll j = i + 1; j <= idx; j++){
            if (pow(prime[i], 2) * pow(prime[j], 2) <= n)    ans ++;
            else    break;
        }
    }
    cout << ans << endl;
    return 0;
}

[ABC383F] Diversity

题目描述

Aya 非常喜欢奶龙。

今天他来到商店,发现商店里正在出售 \(N\) 个奶龙!第 \(i\) 个奶龙的价格是 \(P_i\) 元,实用性是 \(U_i\),颜色是 \(C_i\)。

Aya 可以选择所有奶龙的一个子集进行购买(可以是空集),但最多只能用 \(X\) 元。

Aya 的满意度是 \(S+T\times K\),其中 \(S\) 是购买的奶龙实用性之和,\(T\) 是购买的奶龙中不同颜色的种类数,\(K\) 是一个给定的常数。

请帮 Aya 最大化满意度。

制約

  • $ 1\ \leq\ N\ \leq\ 500 $
  • $ 1\ \leq\ X\ \leq\ 50000 $
  • $ 1\ \leq\ K\ \leq\ 10^9 $
  • $ 1\ \leq\ P_i\ \leq\ X $ $ (1\ \leq\ i\ \leq\ N) $
  • $ 1\ \leq\ U_i\ \leq\ 10^9 $ $ (1\ \leq\ i\ \leq\ N) $
  • $ 1\ \leq\ C_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ N) $
  • 入力は全て整数

解题思路

背包问题 选or不选

状态转移方程

\(f[i][j][0]\)表示对于第\(i\)组颜色,花了\(j\)元,不选该颜色能够获得的最大满意度

\(f[i][j][1]\)表示对于第\(i\)组颜色,花了\(j\)元,选了该颜色能够获得的最大满意度

  • 在写状态转移方程的时候要注意判断,当前的颜色是否是一个新的颜色

​ (1)当前面没有出现过该颜色:

​ \(f[w[i].c][j][0] = max(f[w[i].c-1][j][0], f[w[i].c-1][j][1])\)

​ \(f[w[i].c][j][1] = max(f[w[i].c-1][j-w[i].p][0],f[w[i].c-1][j-w[i].p][1])+k+w[i].u\) (当\(j>=w[i].p\)时)

可以发现,在很多地方都出现了\(max(f[w[i].c-1][j][0], f[w[i].c-1][j][1])\)

因此可以每计算一组颜色的dp值,统一\(f[w[i].c-1][j][0] = max(f[w[i].c-1][j][0], f[w[i].c-1][j][1])\)

状态转移方程可以改成:

​ \(f[w[i].c][j][0] = f[w[i].c-1][j][0]\)

​ \(f[w[i].c][j][1] = f[w[i].c-1][j-w[i].p][0]+k+w[i].u\) (当\(j>=w[i].p\)时)

​ (2)当前面出现过该颜色:

​ 不选该颜色的状态同样只能从前一种颜色转移而来

​ \(f[w[i].c][j][0] = f[w[i].c-1][j][0]\)

​ 选该颜色时 (当\(j>=w[i].p\)时),状态可以是:

  • 前面的同一颜色都不选,只选当前物品,dp值表示为\(f[w[i].c-1][j-w[i].p][0]+k+w[i].u\)
  • 前面已选了当前颜色,还选当前物品,dp值表示为\(f[w[i].c][j-w[i].p][1]) + w[i].u\)
  • 前面已选了当前颜色,不选当前物品,dp值表示为\(dp[w[i].c][j][1]\)

这几个值取max即为\(f[w[i].c][j][1]\)的值

几个小点

  • 第一维是以颜色种类来表示,题目所给颜色不一定连续,所以要对颜色进行离散化处理

  • 相同颜色的物品在dp时所用的是同一空间,所以要注意第二维的枚举要 从后往前,比较最大值时还要记得跟当前位置原本的值比较

  • 所有的值只跟当前行和上一行有关系,所以数组的第一维空间可以压缩成\(2\)

//abc383f
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
//分组背包
//dp[i][j][0]代表对于第i个物品,花了j元,不选该物品所属的颜色能够获得的最大满意度
//dp[i][j][1]代表对于第i个物品,花了j元,选了该物品所属的颜色能够获得的最大满意度
ll dp[505][50005][2];

struct nl{
    ll p, u, c, cc;
}w[505];

bool cmp(nl a, nl b){
    return a.c < b.c;
}

int main(){
    ll n, x, k;
    cin >> n >> x >> k;
    for(int i = 1; i <= n; i++)     cin >> w[i].p >> w[i].u >> w[i].c;
    sort(w+1, w+n+1, cmp);
    //颜色离散化
    w[1].cc = 1;
    ll i = 2, temp = 1;;
    while(i <= n){
        while(w[i].c == w[i-1].c){
            w[i].cc = temp;
            i++;
        }
        w[i].cc = ++temp;
        i ++;
    }
    //dp过程
    for(ll i = 1; i <= n; i++){
        //统一前一组颜色的最大值
        if(w[i].cc != w[i-1].cc){
            for(int j = 0; j <= x; j++)     dp[w[i-1].cc][j][0] = max(dp[w[i-1].cc][j][0], dp[w[i-1].cc][j][1]);
        }
        for(ll j = x; j >= 0; j--){
            dp[w[i].cc][j][0] = dp[w[i].cc-1][j][0];
            if(j >= w[i].p){
                //一个新的颜色
                if(w[i].cc != w[i-1].cc)
                    dp[w[i].cc][j][1] = dp[w[i].cc-1][j-w[i].p][0] + k + w[i].u;
                else
                    dp[w[i].cc][j][1] = max(dp[w[i].cc][j][1], max(dp[w[i].cc-1][j-w[i].p][0] + k, dp[w[i].cc][j-w[i].p][1]) + w[i].u);
            }
        }
    }
    ll ans = 0;
    for(int i = 1; i <= x; i++){
        ans = max(dp[w[n].cc][i][0], ans);
        ans = max(dp[w[n].cc][i][1], ans);
    }
    cout << ans << endl;
    return 0;
}

标签:颜色,int,题解,leq,ABC383,ABC382,alpha,include,dp
From: https://www.cnblogs.com/hsy2093/p/18670404

相关文章

  • [CCO2021] Through Another Maze Darkly 题解
    思路很牛,代码很难,故写题解记之。前置知识:线段树。洛谷题目链接:P7830[CCO2021]ThroughAnotherMazeDarkly。原题题面很简洁,故不赘述题意。观察(70%)读完题,这是什么东西。我们直接去手玩样例,然后发现几个很有用的信息:一个点被进入一次后,必然会指针朝上。一个点被进......
  • 英雄联盟游戏黑屏有声音 原因分析及问题解决
    英雄联盟作为一款热门游戏,经常有玩家遇上电脑黑屏,但却可以听到游戏内的声音,这是怎么回事?这通常意味着显卡驱动程序可能遇到了某些问题,也可能与游戏文件损坏、系统设置不当等因素有关。以下是一些常见的解决方法:一、显卡问题更新显卡驱动:显卡驱动不兼容或过时可能导致游戏......
  • 题解:AT_abc353_f [ABC353F] Tile Distance
    [ABC353F]TileDistance题解cnblogs题目传送门:洛谷,AtcoderSolution很恶心人的分类讨论题。很显然走大格子大概率比走小格子快。对终点和起点向上下左右枚举大格子,我们就把问题转化为给两个大格子\((a,b)\)、\((c,d)\),求怎样走最快。对角的大格子可以通过\(2\)步相互到......
  • ABC388DEG 题解
    ABC388题解ABCDE+G,rk371。D观察到几个性质:一个人只会在成年的时候得到石头,在成年之后给出石头。第\(i\)个人成年之后,他要给之后的每个人一个石头(除非用光了)。也就是说,假设成年时它的石头数量为\(B_i\),则最终他的石头数量为\(\max(0,B_i-(n-i))\)。因此我们只需......
  • LeetCode 2275: 按位与结果大于零的最长组合题解
    LeetCode2275:按位与结果大于零的最长组合题解1.题目分析这道题目考察了位运算的基本概念和应用。我们需要在给定的数组中找出最长的子序列,使得这些数字进行按位与运算后的结果大于0。1.1关键概念按位与运算(&)两个二进制位都为1时,结果为1。只要有一个为0,结果就为0......
  • 【大数据】beeline 导出文件有特殊字符的问题解决
    问题近期在做大数据查询引擎导出文件的功能,使用了hive的beeline客户端。发现beeline导出的文件以及终端输出有许多特殊字符。按照官方文档使用beeline导出命令:[1]/usr/bin/beeline--silent=true--showHeader=true--outputformat=csv2-fquery.hql</dev/null>/tm......
  • Hetao P3804 Cut 题解 [ 蓝 ] [ AC 自动机 ] [ 差分 ]
    Cut:AC自动机简单题。思路看见多个模式串以及求前缀,很显然能想到构建一个AC自动机。那么在用\(T\)查询时,当前指针的深度就是该位置的最长前缀匹配长度。这个在字典树insert的时候就能求出来。求出每一位的最长前缀后,因为这些部分都不能作为分割点,所以将这些区域用差分......
  • 验证出栈顺序是否正确题解&队列
    (1)验证出栈顺序是否正确队列遵循先入后出的原则,故需要一个数组来模拟记录入栈和出栈再分别对出栈顺序进行遍历验证是否正确#include<iostream>usingnamespacestd;#definem100000intb[m],a[m],c[m];intmain(){ intt; cin>>t; while(t--){ intn;......
  • THUWC 2020 Day3 题解
    Cache一致性协议按照学习手册最后的模拟。\(\text{Exclusive}/\text{Shared}\)只有编号最小的返回,但都要改变状态。\(\text{Modified}\)的所有的都要返回且改变状态。Cache替换算法这里说一下\(\text{PLRU}\)算法。对于每次,先找是否命中。如果是否,就在二叉搜索树上......
  • 2021 年 3 月青少年软编等考 C 语言五级真题解析
    目录T1.红与黑思路分析T2.密室逃脱思路分析T3.求逆序对数思路分析T4.最小新整数思路分析T1.红与黑有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计......