首页 > 其他分享 >AtCoder Beginner Contest 338 c题二分思路

AtCoder Beginner Contest 338 c题二分思路

时间:2024-01-29 22:35:43浏览次数:22  
标签:AtCoder 338 Beginner Contest 制作 true

观察题目可知,会有一个最大的x(两个菜的最大制作数),大于这个x就不能做任何一盘菜,小于这个x那么一定可以做出来,这样分析就是显而易见的递归。

实现递归的check函数,那么我们就可以把两个菜的总制作数传进去。那么什么时候true什么时候false呢,就是判断每种材料的制作量有没有超过原材料的制作量。那么又要如何判断总量是x盘每个菜的制作数呢,就是A菜从0到xfor循环B由x到0for循环,如果有一次成功就返回true。

下面来自professor的代码(思路也是professor的)

 

标签:AtCoder,338,Beginner,Contest,制作,true
From: https://www.cnblogs.com/sixsix666/p/17995501

相关文章

  • ABC338 F
    link观察到\(n\)的范围不大,考虑状压。\(dp_{i,S}\)表示在经过顶点集合状态为\(S\)的情况下,终点为\(i\)的最小步数。错误示范:考虑对于状态\(S\),直接遍历经过的顶点\(i\),枚举\(i\)的出边进行转移。#include<bits/stdc++.h>typedeflonglongLL;typedefstd::......
  • 题解 [ABC338D] Island Tour
    【洛谷博客】被降智的一道简单题。题意\(n\)个岛屿,第\(i\)座桥连接\(i\)和\(i+1\)(第\(N\)座桥连接着\(1\)和\(N\))。有一条长度为\(M\)的旅游序列\(X\),你需要按照顺序依次经过这些点,选择断掉一座桥使得旅游经过的桥最少。分析设断掉第\(i\)座桥会因为绕行增......
  • AtCoder Beginner Contest 338
    A-Capitalized?#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingvi=vector<int>;usingi32=int32_t;usingpii=pair<int,int>;constintinf=1e9,INF=1e18;i32main(){strings;cin>>......
  • ABC338D 题解
    赛时怎么连这题都不会。再不练练思维真的就连普及题都不会做了啊。Solution题目来源:ABC338D(inAtcoder|in洛谷)。不妨先考虑应该断掉哪条边。首先我们发现,仅断掉一条边并不会让两个结点不可达,只会让我们从一个结点绕更远的路到达目标结点。如果我们要从结点\(u\)前往结点......
  • ABC338 F Negative Traveling Salesman 题解
    QuestionABC338FNegativeTravelingSalesman给出一个\(N\)个点\(M\)条边的有向图,边权可能为负数,但不可能有负环每经过一条边就要加上这条边的代价求,一条路径经过所有的点,并且要求总代价最小Solution观察到\(N\le20\)自然而然想到状压因为多次经过一条边的代价是......
  • AtCoder Beginner Contest 338
    基本情况A忘记大小写敏感卡了20分钟,BC秒了,E用树状数组草过去了,D错了25个点,似乎是交界没有判断好。B-FrequencyB-Frequency(atcoder.jp)这题还可以更优雅点。intmain(){strings;cin>>s;map<char,int>cnt;for(inti=0;i<s.size();i++......
  • AtCoder Beginner Contest 338
    基本情况:A和B直接秒了,C题没写出来大致是思路的问题,下面就讲一下C自己的思路和题解C-LeftoverRecipes题目概述,先输入一个数字代表有多少中配料,然后依次输入A菜每种配料所需的量,然后输入B菜每种配料所需的量,最后输出最多可以做多少盘菜样例:280030010010020010输出为......
  • ABC338 D Island Tour 题解
    Question有\(n\)座海岛由\(n\)条桥连着,第\(i\)座桥连接第\(i\)和\(i+1\)座海岛,第\(n\)座桥连接第\(n\)和\(1\)座海盗有一条长度为\(m\)的旅游路线,第\(X_i\)表示依次到达的岛屿现在需要切断一条桥,求总旅游路线最小值Solution显然,从第\(X_{i-1}\)到\(X_......
  • ABC338 E Chords 题解
    Question一个圆上有\(2N\)个点均匀分布,给出\(N\)条线,每条线连接两个顶点问,有没有两条线相交Solution也算一个比较典的题目考虑到这种两两配对,配对中有没有交错关系的可以考虑异或哈希因为一个数异或两次等于它本身,所以我们可以用异或来实现一个“撤销”操作我们当我......
  • ABC338 题解(A-E)
    前言:F,G后续补充。A题意判断一个字符串,是否满足只有第一位为大写字母,其余为小写字母。Sol字面意思模拟即可。Code#include<bits/stdc++.h>#definelllonglong#defineN200005#defineendl"\n"#definefifirst#definesesecondusingnamespacestd;constll......