首页 > 其他分享 >AtCoder Beginner Contest 338

AtCoder Beginner Contest 338

时间:2024-01-28 11:45:10浏览次数:49  
标签:AtCoder 338 Beginner cin flag ans inf e1 e2

基本情况:

A和B直接秒了,C题没写出来大致是思路的问题,下面就讲一下C自己的思路和题解

C - Leftover Recipes

题目概述,先输入一个数字代表有多少中配料,然后依次输入A菜每种配料所需的量,然后输入B菜每种配料所需的量,最后输出最多可以做多少盘菜

样例: 2
800 300
100 100
200 10 输出为5

自己的想法:看到这个的时候先在草稿纸上假设A菜做x盘,B菜做y盘,然后就列了两个不等式100x+200y<=800和100x+10y<=300然后根据这两个不等式来判断x+y的最大值,一开始以为可以用高中的数学判断极值的方法拉格朗日数乘,但是后面发现给的条件是带有不等号的貌似不能用,因为拉格朗日数乘需要的是等号条件之后再分别求导(可能后面比赛会用到这个)。发现不行后想线性规划,之后就想直接算出每当个不等式取等号的时候于x轴的交点,然后依次判断获取最小的与x轴交点的值。然后通过for循环依次判断当x=0到那个交点范围内所有整数x的值,最后把x值代入不等式获取y(这个过程需要带到每个不等式然后获取最小的y),之后x和y相加再判断最大值

题解:先固定一边(x或y)之后再循环判断每个x值时y的取值,后再判断哪个时候最大,当然x固定后,也要固定y。确保所有情况都考虑到(感觉其实和自己的挺像的,但自己的思路是通过找到最大值x来循环y,其实这样循环次数反而增加了,倒不如就像题解一样,把所有x值都取然后判断y)

`#include <bits/stdc++.h>
using namespace std;
const int inf =INT_MAX,N=20;
int n,i,e1,e2,x,y,ans,flag,q[N],a[N],b[N],f[N];
int main(){
cin>>n;e1=e2=inf;ans=-inf;y=inf;flag=0;
for( i=1;i<=n;i++){
cin>>q[i];
}
for(i =1;i<=n;i++){
cin>>a[i];
if(a[i]>0)e1=min(e1,q[i]/a[i]);
}
for(i =1;i<=n;i++){
cin>>b[i];
if(b[i]>0)e2=min(e2,q[i]/b[i]);
}
for(x=0;x<=e1;x++){
if(flag)break;
for(i=1;i<=n;i++)f[i]=q[i]-a[i]x;
for(i=1;i<=n;i++){
if(f[i]<0){flag=1;break;}
if(b[i]<0){y=min(y,f[i]/b[i]);}
}
ans =max(ans,x+y);
}
flag=0;
for(y=0;y<=e2;y++){
if(flag)break;
for(i=1;i<=n;i++)f[i]=q[i]-a[i]
y;
for(i=1;i<=n;i++){
if(f[i]<0){flag=1;break;}
if(a[i]<0){x=min(x,f[i]/a[i]);}
}
ans =max(ans,x+y);
}
cout<<ans;

}`

有二分做法,过一会学了补充

标签:AtCoder,338,Beginner,cin,flag,ans,inf,e1,e2
From: https://www.cnblogs.com/sixsix666/p/17992426

相关文章

  • 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......
  • AtCoder Beginner Contest 338
    AtCoderBeginnerContest338ABC切ABC,什么实力。C-LeftoverRecipesProblemStatementYourrefrigeratorhas\(N\)kindsofingredients.Letuscallthemingredient\(1\),\(\dots\),ingredient\(N\).Youhave\(Q_i\)gramsofingredient\(i\).......
  • AtCoder Beginner Contest 338
    AtCoderBeginnerContest338A-Capitalized?代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingi128=__int128_t;voidsolve(){strings;cin&......
  • AtCoder abc336 A-D题代码
    A题:#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;cout<<"L"<<string(n,'o')<<"ng"<<endl;return0;}B题:#include<bits/stdc++......
  • AtCoder Beginner Contest 336
    所有代码都在如下模板中运行#include<bits/stdc++.h>usingnamespacestd;namespacegza{ #defineintlonglong #definepbpush_back #defineMTintTTT=R;while(TTT--) #definepcputchar #defineRread() #definefo(i,a,b)for(inti=a;i<=b;i++) #definerep(......
  • P4338 历史笔记
    神题啊!神题(赞叹)题意形式化题意:给定一棵\(n\)个点的树,第\(i\)个点有点权\(a_i\)。且每个点都有颜色,初始时颜色都为\(1\),第\(i\)个点的颜色是\(c_i\)。你可以对一个点\(x\)进行一次操作:计数有多少\(v\),满足\(v\)在\(x\to1\)的路径(包含\(x\)和\(1\))上,且......
  • P3389 【模板】高斯消元法
    #include<bits/stdc++.h>usingnamespacestd;doublemax(doublea,doubleb){ if(a>=b)returna; if(a<b)returnb;}intn;doublea[1010][1010];doublea1[1010][1010];intmain(){ scanf("%d",&n); for(inti=1;i<=n;i++) { ......
  • AtCoder ABC 266 复盘
    AMiddleLetter水沝淼㵘纯模拟题。根据题意,易得答案。ACCodeBModuloNumber模拟(+数学?)。先\(N\leftarrowN\bmod998244353\),然后\(N\leftarrowN+998244353\(N<0)\),最后输出\(N\)。ACCodeCConvexQuadrilateral数学。有一个公式判断(名字我忘了)可以判断。详见ACC......