威风镰鼬

题解

/ 注册

全部文章 / 题解（共151篇）

题解 | #挖沟#

思路与<15108道路建设>同解，Kruskal硬过就行了。代码 #include<bits/stdc++.h> using namespace std; const int maxn=100005,maxm=1000005; struct E{ int fro...

普及组最短路 Kruskal 图论

2021-06-12

1 477

题解 | #道路建设#

思路最小生成树板子题，用Kruskal硬过就行了。算法流程：初始设点在集合A，无连边；将图中的边按照权值从小到大排序，然后从最小的边开始连接（使用并查集）；将边的两端点加入集合B，如果当前边的两个端点不都在集合A，则进行连接；选择m-1条边的时候刚好将m个点连上，此时判断权值之和是否大于c。代码...

最小生成树 Kruskal NOIP

2021-06-12

1 430

题解 | #回文串#

回文串思路这道题我先写了马拉车（不会的可以去学一学，能以O(n)复杂度求最长回文串长度），A了之后看数据范围，发现暴力也是能过的。需要注意点一些细节：（我被坑过的点）马拉车记得在要在字符串前面加多一个字符防止越界。暴力算法不要列举区间再判断是否回文，先列举中心点再求回文长度更快。同时注意字符串长...

回文普及组马拉车 NOIP

2021-06-11

1 526

题解 | #兔子的序列#

兔子的序列思路打表记录1~1000内所有完全平方数，然后在输入序列的时候剔除掉，那么最大的一个数就是答案。代码 #include<bits/stdc++.h> using namespace std; int main(){ int n,i,ans=0,a[1005],b...

2021-06-11

1 571

题解 | #[NOIP2016]回文日期#

[NOIP回文日期] 思路纯模拟题，前面几发没看到范围写错了没过，总的来说还是很简单的。最快的方式是打表，挑出回文日期然后判断每一个回文日期是否在起末日期之间就行了。暴力也是可以过的（估计数据强一点就不一定了），当然要打表就得暴力嘛……如何判断回文？日期是八位整数，使用取模和除法运算就能判断，不建...

回文日期 NOIP

2021-06-10

2 662

题解 | #[NOIP2005]校门外的树#

[NOIP2005]校门外的树思路一开始有l+1棵树，刨去所给范围合并所得后所得的树的个数就是结果。用一个vis数组来记录刨去树的区间（是一个闭区间），数据范围很小，暴力可解。代码 #include<bits/stdc++.h> using namespace std; typed...

普及组

2021-06-10

1 707

题解 | #[NOIP2006]明明的随机数#

#[NOIP2006]明明的随机数# 思路去重+排序=>计数排序看一眼数据范围完全够用。代码 #include<bits/stdc++.h> using namespace std; int n,a,cnt=0,mp[1005]={0}; int main(){ s...

排序普及组

2021-06-10

1 464

题解 | #[NOIP2014]寻找道路#

[NOIP2014]寻找道路思路首先要把一些不满足条件的点剔除掉，然后就是求最短路的事情了。要找不满足条件的点，可以反向建边，然后从终点出发，标记每一个经过的点。那么剩下没有走过的点就可以去掉了。代码 #include<bits/stdc++.h> using namespace ...

最短路提高组图论 NOIP bfs

2021-06-09

1 694

题解 | #栗酱的连通图#

#栗酱的连通图# 思路每个点权都是偶数，所以每条边权值是整数，数据全用整数型就好了。注意到每两个点之间都有边，所以要求最大的权值之和，只需求最大点到其他点的边权之和就好了。代码 #include using namespace std; int t,n,ans,a[1005]; int ...

2021-06-09

2 439

题解 | #[NOIP2017]图书管理员#

[NOIP2017]图书管理员思路先给书本编号从小到大排序如何判断每本书编号后缀是否有询问的数x?一个直观且快速的办法：书本编号－x之后，后面几位都会变成0所以只要判断减去之后的数是否有len个0就好了（取模）如果用字符串做会很麻烦复杂度O(nq),数据可过代码 #include<bit...

排序

2021-06-09

3 814