P7774 KUTEVI

news/2024/11/24 6:22:47/

虽然这个题想通过不难,但还是值得记录

题意:

题目描述
给定 N 个角(第 i 个角记作 ai ),作为初始角,另给定 M 个角(第 i 个角记作 bi),作为目标角。
请求出对于每个 bi,它是否能被若干个 ai之间的加、减运算得到。
注意同一个 ai可以用多次,也可以不用。
输入格式
第一行两个正整数 N,M
第二行 N 个正整数,第 i 个数为 ai
第三行 M 个正整数,第 i 个数为 bi
输出格式
共 M 行,在第 i 行,如果 bi能被若干个 ai之间的加、减运算得到,输出YES,否则输出NO。

输入
2 1
30 70
40
输出
YES
输入
1 1
100
60
输出
YES //15×100 ∘=1500 ∘ =60 ∘

1、完全背包
重点是转化出这个想法:
你和另一个人都有 n 种物品,每种物品有无数个。你可以将这些物品卖出,也可以买进。判断可否通过买卖这n种物品,使你得到 m块钱。
这样就像是背包了

cin>>n>>m;
for(int i=1;i<=n;i++)
{cin>>a[i];
}
for(int i=1;i<=m;i++)
{cin>>b[i];
}
f[0]=1;
for(int i=1;i<=n;i++)
{for(int j=0;j<=1005;j++){if(j>=a[i]) f[j%360]=max(f[(j-a[i])%360],f[j%360]);//a[i]取或者不取f[j%360]=max(f[(j+a[i])%360],f[j%360]);}
}
for(int i=1;i<=m;i++)
{if(f[b[i]]==1) cout<<"YES"<<endl;else cout<<"NO"<<endl;
}

2、普通做法(因为数据少,所以可行)

把每一个a中的角度都加上他的1-359倍,即把所有情况都存下来(同时取模)
若此时所有情况中有bi,则可以表示
凭感觉,过了,但就是解释不清,重点是上面的完全背包,这个仅供娱乐,所以要勇于尝试?

cin>>n>>m;
x=0;
for(int i=1;i<=n;i++)
{cin>>a[i];for(int j=1;j<=359;j++){f[x++]=a[i]*j%360;}
}
k=0;
for(int i=1;i<=m;i++)
{cin>>b[i];k=0;for(int j=0;j<x;j++){if(b[i]==f[j]) {cout<<"YES"<<endl;k=1;break;}}if(k==0) cout<<"NO"<<endl;
}

http://www.ppmy.cn/news/234224.html

相关文章

2018+黑苹果+vs+Linux,重点更新!完美黑苹果=Z370M+i5+RX590(硬解)10.15

本帖最后由 cbw390179428 于 2020-3-13 21:10 编辑 先来张图给大家解解馋! 配置是 主板:微星Z370M CPU:i5-8600K 显卡:女装大佬RX590 内存:芝棋8G-3000 显示器:戴尔U2417H 经过半年的调整现在完美黑苹果。换了RX590,琢磨了很长时间的硬件解码,最后成功硬解。关于这个问…

hdu2717

/* 分析&#xff1a; 广搜。 2012-07-19 */ #include"stdio.h" #include"string.h" #include"queue" using namespace std;struct node {int x;int step; }; int map[100011]; int s,e;int judge(int x) {if(x<0 || x>100000) return 1;if…

UCC24630DBVT

UCC24630DBVT 规格 产品属性 制造商:Texas Instruments 产品种类:门驱动器 RoHS: 详细信息 产品:MOSFET Gate Drivers 类型:High-Side, Low-Side 安装风格:SMD/SMT 封装 / 箱体:SOT-23-6 激励器数量:1 Driver 输出端数量:1 Output 输出电流:3.33 A 电源电压-比较小:3.6 V 电源电…

台式计算机屏幕扩展,浅谈修图电脑配置(台式/显示器篇)

作者&#xff1a;ETPHOTOS 来源&#xff1a;相机笔记电脑是重要的摄影周边附件。伴随高像素、高速连拍、高清视频的发展&#xff0c;摄影也已成为大家更新电脑的重要推动力。昨天说了一些基础概念&#xff0c;今天说一下台式电脑和显示器。 『主板和机箱』 在台式电脑中&#x…

hdu2147

/* 分析&#xff1a; 博弈。 找必胜必败点。 an-1&#xff0c;bm-1&#xff0c;那么a、b分别可以为奇数、偶数&#xff0c;则有 四种情况&#xff0c;枚举看一下&#xff0c;就出结论了。 2012-09-06 */ #include"stdio.h" int main() {int n,m;while(scanf("%d…

记nuc8的开箱以及安装hackintosh

有人喜欢大塔机箱&#xff0c;各种rgb灯效加成&#xff1b;那么自然就有人喜欢极其迷你的机箱&#xff0c;它很小&#xff0c;比传统的itx还要小&#xff0c;小到这种机箱你可以轻而易举地带着走&#xff0c;把它们优雅地放进你的包里&#xff0c;到达目的地后娴熟地接上电源连…

HC32F460 读取热电偶温度

使用背景 首先感谢华大半导体产商的辛苦努力 &#xff0c;发布了一款高性价比的MCU-HC32F460 系列&#xff0c;它是基于 ARM Cortex-M4 32-bit RISC CPU&#xff0c;最高工作频率200MHz 的高性能 MCU。Cortex-M4 内核集成了浮点运算单元FPU和 DSP&#xff0c;实现单精度浮点算…

pandas库学习笔记

> dataframe与series pandas中有两种常用的数据结构&#xff0c;分别是dataframe和series两种。 dataframe数据结构 import numpy as np import pandas as pd dataframe pd.DataFrame([[1,2,3],[4,5,6],[7,8,9]],index [No.1,No.2,No.3],columns [a,b,c]) dataframeab…