https://ac.nowcoder.com/acm/contest/22904/1027开了ll还见祖宗注意x^2+y2算完之后先判断有没有超4r2的范围，没有的话再计算z^2，算是对longlong溢出的特判#include<bits/stdc++.h>typedeflonglongll;usingnamespacestd;classUnionFind{public:UnionFind(ll

P3952[NOIP2017提高组]时间复杂度我们把循环的嵌套关系看做树形结构，梳理一下\(3\)种情况：直接跳过当前子树：\(x,y\in\mathbb{N}\)，且\(x>y\)。\(x=\tt{"n"},y\in\mathbb{N}\)。不跳过，并在处理完所有子节点后追加\(n\)的时间复杂度：\(x\in\mathbb{N},y=\tt{"n"}\)。

P3959[NOIP2017提高组]宝藏题解搜索魅力时刻怎么说，四种做法比较？？的模拟退火跑得快但是正确性有问题的状压DP跑得慢但是一定正确的状压DP时间复杂度很玄学的DFS+剪枝我就选择了搜索的做法先打个暴搜，70pts点击查看暴搜代码#include<bits/stdc++.h>usingna

题目背景NOIP2017提高组D2T1题目描述现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 z=0，奶酪的上表面为 z=h。现在，奶酪的下表面有一只小老鼠Jerry，

题目背景NOIP2017普及组T1题目描述牛牛最近学习了C++入门课程，这门课程的总成绩计算方法是：总成绩=作业成绩x20%+小测成绩x30%+期末考试成绩x50%牛牛想知道，这门课程自己最终能得到多少分。输入格式三个非负整数A,B,C，分别表示牛牛的作业成绩、小测成绩和期末考试成绩

[NOIP2017普及组]棋盘题目背景NOIP2017普及组T3题目描述有一个\(m\timesm\)的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右

思路：考虑状态压缩动态规划。定义\(dp_{i,j,S}\)表示点\(j\)离起点\(i\)的距离，且从点\(j\)开始打通的点集为\(S\)的最小代价（注意\(S\)不能包含\(j\)）。考虑枚举\(S\)一个一个子集\(S'\)，同时枚举一个\(k\)，需要满足\(k\inS'\)，即我们可以先打通\(j\tok\)，然后

思路：首先发现单调性，灵活性增加\(x+1\)的答案肯定不会比增加\(x\)的答案更劣。那么可以二分求\(g\)，则机器人每次可以移动\([\max(d-mid,1),d+mid]\)这个区间内的距离，为了方便，设为\([l,r]\)。考虑动态规划求得能走到的最大分数，令\(dp_i\)表示走到第\(i\)个格子的最大

题目题目描述图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。小D刚刚当上图书馆的管理员，她

https://www.luogu.com.cn/problem/P3957https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=337显然，但是维护滑动窗口有技巧，不能每次插入一个值，因为维护\(x\)不方便。所以考虑一个\(cur\)，每次对于新的\(i\)不能跳过时移动\(cur\)，然后队

本文由Jzwalliser原创，发布在CSDN平台上，遵循CC4.0BY-SA协议。因此，若需转载/引用本文，请注明作者并附原文链接，且禁止删除/修改本段文字。违者必究，谢谢配合。个人主页：blog.csdn.net/jzwalliser题目洛谷P3954[NOIP2017普及组]成绩[NOIP2017普及组]成绩题目背景

原题链接：https://www.luogu.com.cn/problem/P3957题意解读：有n个格子，每个格子有不同的距离和分数，从起点，每次可跳距离为d，用g金币后可跳距离范围可以变成max(d-g,1)~d+g，求最小的g，使得可跳跃得分不少于k。解题思路：1、单调性分析：如果g越大，可跳跃的范围就越大，理论上能得的分数越

原题链接：https://www.luogu.com.cn/problem/P3956题意解读：计算从(1,1)走到(m,m)的最小花费，有几个限定：同色格子可以走，花费为0；不同色格子可以走，花费为1；有色格子可以走到无色格子，花费为2，且用将无色格子临时染色；无色格子不能走到无色格子。解题思路：可以采用DFS来暴搜所有路径，需

原题链接：https://www.luogu.com.cn/problem/P3955题意解读：给出n个图书编号，q个需求码，找到后缀与需求码匹配的最小图书编号，没有输出-1。解题思路：先对图书编号排序，用枚举法遍历每一个图书编号，看后缀是否与需求码相同。100分代码：#include<bits/stdc++.h>usingnamespacestd;c

题2：图书管理员【题目描述】图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。小

P3953[NOIP2017提高组]逛公园求有向图中\(1\)到\(n\)的路径中长度小于等于\(dis(1,n)+k\)的方案数。\(dis(1,n)\)表示最短路。\(k\le50\)。部分分\(k=0\)，直接最短路计数即可。我们发现有向图中存在后效性，不好动态规划，但我们仔细思考后，在不存在\(0\)边的情况下，设

/*这题本身不难,但是我写难了就是一个bfs,没了但是我的写法恰好犯了一个错误hark数据35110211311220330答案是4而我能输出30-1-110-11-10原因是我先走到了(2,2)这时候

原题链接题解dijkstra算法的应用。相同颜色权值为0；不同颜色权值为1；有颜色到无颜色权值为2。其中不能连续两步走无颜色结点，即该情况需要特别考虑。code #include<bits/stdc++.h>usingnamespacestd;constintMAX=1e9;inta[105][105],dis[105][105],vis[105][105];int

这肯定是学证明了，看这篇文章补充一下细节首先，\(m\)的范围应该是\([0,b-1]\)然后，当\(m\)取不同值的时候，\(ma\)%\(b\)一定为不同值（这个性质确实有点奇特，可以记下来）反证，如果\(m_1a\equivm_2a\:(mod\:b)\)且\(0≤m_1＜m_2≤b-1\)，那么就有\(b|(m_2-m_1)a\)，题目给出了\(a,b\)互质，

原题链接题解二分加动态维护区间最大值注意设立变量的含义，改变变量值的规则code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llsum[500005]={0};structunit{llx,v;booloperator<(constunit&b)const{returnb.v>v;}//}room[5000

原题链接思路并查集然后看看是否存在上表面联通的洞与下表面联通的洞位于同一集合code#include<bits/stdc++.h>usingnamespacestd;doublen,h,r;intfa[1005];vector<int>up,down;struct{doublex,y,z;}hole[1005];doubledis(inti,intj){returnpo

50分代码1//P3957[NOIP2017普及组]跳房子2#include<iostream>3#include<queue>4#include<cstring>5#include<cmath>6usingnamespacestd;7typedeflonglongll;8intn,d,k;9inta[500010][2];10llf[500010],sum=0;11boo

Description策策同学特别喜欢逛公园。公园可以看成一张\(N\)个点\(M\)条边构成的有向图，且没有自环和重边。其中\(1\)号点是公园的入口，\(N\)号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。策策每天都会去逛公园，他总是从\(1\)号点进去，从\(N\)

传送门P3956[NOIP2017普及组]棋盘不清楚曾师为什么把这个神奇的题目放在搜索\(search\)专栏，反正我用\(dijkstra\)水过去了，虽然\(dijkstra\)严格来说也是一种能够解决一般性最短路问题的算法。然后考虑这道题的建图。这道题来看首先是去除魔法的部分，一般地，任意一个点只

 8.由四个不同的点构成的简单无向连通图的个数是（）A.32 B.35 C.38 D.41错误原因：数重了正解：分情况计算，6条边的有1种，5条边的有C(6,1)=6种，4条边的有C(6,4)=15种，3条边，要分度数，2+2+1+1的有12种，3+1+1+1的有4种，共38种 10.若 f0​=0,f1​=1,fn+1​=（fn​+fn−1）/2​​，则随着