NOIP 2017 解题报告

古城微笑少年丶 2021-11-26 20:26 228阅读 0赞

\---恢复内容开始---

NOIP 2017 的题真的很难啊，怪不得当年我这个萌新爆零了（当然现在也是萌新）越学越觉得自己什么都不会。

想要成为强者要把这些好题都弄懂弄透 至少现在6道题我都比较陌生 都是以前写的现在再复习一遍吧。

Day1 T1

![1485523-20190423212715207-1694927321.png][]

这是哪门子题啊好难 怎么算啊 好了我感觉我要爆零了。。很难拿分。

考虑暴力 考虑我眼看可以看出答案<=a\*b 也就是两数的最大公约数当然这也是猜结论然后在这个范围内枚举某个数字看其能否被拼成我们只需枚举其中一个看看另一个...检验一下就好了期望得分30~45左右。

考虑正解 貌似是exgcd 再复习一下吧 对于一个最大不能找出来的数字w 一定有ax+by=w+1;

考虑如何求出 w=ax+by; 1=ax0+by0; w-1=a(x-x0)+b(y-y0); 由于此数字不能被表示出来则必然有 x-x0<0||y-y0<0

那么则有 x<x0||y<y0 再看这个式子 1=ax0+by0 这个是一定成立的 因为a,b互质 所以有 gcd(a,b)=1 则有

裴蜀定理 ax+by=gcd(a,b); 考虑再证明一下裴蜀定理吧 对于这个式子 ax+by=gcd(a,b);

如果b==0 则必然有x==1,y==0 使这个式子成立 当处于一般情况b>0 ax+by=gcd(a,b) 我们知道的 gcd(a,b)=gcd(b,a%b)

然后则有 bx1+(a%b)y1=gcd(b,a%b) a%b=a-(a/b)\*b; bx1+(a-a/b\*b)\*y1=gcd(b,a%b); ay1+b(x1-a/by1)=gcd(b,a%b);

于是则有 x=y1 y=x1-a/by1 这样不断递归下去一定会有一解然后返上来然后得证。

然后接着上面的那个问题 考虑x-x0<0||y-y0<0 那么由于观察 ax0+by0=1 由于a,b>0 那么x0,y0 一定异号

好了我不证了 我TM就是个SB

转载于:https://www.cnblogs.com/chdy/p/10764470.html

[1485523-20190423212715207-1694927321.png]: /images/20211126/117a6d93cec7447ca8aedb5e4318ac2b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，228人围观）

还没有评论，来说两句吧...

相关阅读

相关 NOIP 2009 普及组初赛试题解题报告、题解及选择题思路，高质量

[洛谷题目测试链接][Link 1] 单项选择题 <table> <thead> <tr> <th>1</th> <th>2</th>

心已赠人/ 2022年11月14日 10:17/ 0 赞/ 141 阅读

相关 NOIP 2008 普及组初赛试题解题报告、题解及选择题思路，高质量

做题：[https://ti.luogu.com.cn/problemset/1003][https_ti.luogu.com.cn_problemset_1003] 选择

深碍√TFBOYSˉ_/ 2022年10月22日 09:17/ 0 赞/ 153 阅读

相关 POJ1009解题报告

保送之后都是项目的事情，一直没有时间写acm题，今天刚好礼拜六尝试着继续之前的工作，争取以后每周能够写上1-2个poj。很久没写算法题感觉自己的智商已经完全不够用了。说说这

港控/mmm°/ 2022年08月13日 17:43/ 0 赞/ 274 阅读

相关 POJ1007解题报告

其实就是求线性代数里面所谓的逆序数，既然是逆序数那肯定从后往前计数，通过计算每个字符的逆序数最终算出整个字符串的逆序数。用switch进行条件判断，比如CAGT，直观上看这

素颜马尾好姑娘i/ 2022年08月10日 20:00/ 0 赞/ 323 阅读

相关 3Sum——解题报告

【题目】 Given an array S of n integers, are there elements a, b, c in S such that a

ゞ浴缸里的玫瑰/ 2022年08月08日 06:12/ 0 赞/ 238 阅读

相关 windows画图（解题报告）

计蒜之道2017复赛题在 Windows 的“画图”工具里，可以绘制各种各样的图案。可以把画图当做一个标准的二维平面，在其上先后绘制了 nnn 条颜色互不相

超、凢脫俗/ 2022年06月14日 05:10/ 0 赞/ 264 阅读

相关 NOIP 2017普及组复赛C/C++详细题解报告

一、题目 https://wenku.baidu.com/view/f3fe5a326ad97f192279168884868762cbaebb71.html?from=

我会带着你远行/ 2022年05月08日 08:48/ 0 赞/ 447 阅读

相关 [解题报告]Feynman

题目大意题目原文：[http://uva.onlinejudge.org/external/121/12149.pdf][http_uva.onlinejudge

女爷i/ 2022年01月07日 12:51/ 0 赞/ 294 阅读

相关 [NOIP2017] 宝藏

[题目链接][Link 1] 题意　　题面过长，自行传送... 分析　　乍一看就是个搜索剪枝，然而正解是状压DP 　　我们用二进制表示可以到达的点的集合，设 $d

迈不过友情╰/ 2021年12月19日 04:59/ 0 赞/ 196 阅读

相关 NOIP 2017 解题报告

\---恢复内容开始--- 　　NOIP 2017 的题真的很难啊，怪不得当年我这个萌新爆零了（当然现在也是萌新）越学越觉得自己什么都不会。想要成为强者要把这些好题都弄懂

古城微笑少年丶/ 2021年11月26日 20:26/ 0 赞/ 229 阅读