ThinkofBlank

题解

未归档(4) 论文(10) 题单(1)

/ 注册

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

题解 P3792 【由乃与大母神原型和偶像崇拜】

这题，主要是维护平方和来判断区间是否连续，但这里任然有两个问题： 1.值域为1e9，极限下，long long是一定会爆炸的 2.正如讨论区的，平方和可以被hack 那么该如何解决这个问题呢？我的想法是——离散化！离散化后，值域的极限就在1e6，假设这5e5个数，每...

数据结构题解

2018-12-23

1 702

题解 P1168 【中位数】

看了此题,发现是求中位数,自然而然的想到了求kth 求kth有多种,我用的是权值线段树,即记录x的个数,但,我们看题，发现a[i]可以高达1e9,一个数组是开不完的, 不过万幸的是n只到了1e5,而求kth只需要知道大小关系就行,不需要知道具体的值,所以,我们可以用离散化来搞定它！ ...

2018-12-19

0 519

题解 CF47A 【Triangular numbers】

这题其实就是高斯求和问题，即1+...+x=x（x+1）/2。由此，我们就可以用递推的思想来解决问题： include<bits/stdc++.h> using namespace std; int main() { //freopen("ask.in",...

2018-12-19

0 467

题解 P4994 【终于结束的起点】

这道题,发现暴力能过时,喷了3k的血。。。本人花了近半小时打表找规律。。。然后真找出来一些了。。。 1.f[x^n]=f[x]*(x^(n-1)) 2.设x,y为不相同的质数,则f[x^a*y^b]=lcm(f[x^a],f[y^b])。 3.对于一个质数x,他的f[x]极小(似乎...

2018-12-19

0 0

题解 P1286 【两数之和】

提供一个新思路这题,我们假设n个数分别为a1,a2,a3,a4,a5...an,且对于任意 1<=i<j<=n满足ai<aj 而他们两两之和即为输入的各数字,从中,我们不难推出对于输入的数字中(我们把它们按从小到大排序,分别设为m1,m2...) 一...

2018-12-19

0 699

题解 P2340 【奶牛会展】

此题搜索可以过！！！看到此题,第一想法,是01背包,然而,作为一个蒟蒻,我怎么会打正解呢？,于是就开始打dfs！想要完成此题,普通的搜索肯定是过不了的(不然要dp干嘛),所以,我们要考虑剪枝比较容易的,我们可以轻松想出来剪枝: (不吐槽名字我们还是好朋友。。。)...

2018-12-19

0 513

题解 CF450B Jzzhu and Sequences

作为首A的人(?)我来发布下这道大水题的题解了~ 首先题目给出了f[i]=f[i-1]+f[i+1]，我们移下项: f[i+1]=f[i]-f[i-1]，所以我们可以知道：第i项等于它前两项之差！即: f[i]=f[i-1]-f[i-2],同时,f[i-1]=f[i-2]-f[i-3...

2018-12-19

0 502

题解 P1470 【最长前缀 Longest Prefix】

首先看题，题目要求我们求最长匹配的长度，我们不妨如下思考：对于字符串S，我们从第y位开始搜索（保证前y-1位一定可以是匹配）从第y位开始生成字符串，若此时生成的字符串在P中出现过，则证明此时的字符串可以被匹配到y+i的位置，我们再从y+i+1开始搜索便好了！而问题的答案...

2018-12-19

0 718

题解 P2532 【[AHOI2012]树屋阶梯】

此题就是一个卡兰特数列，用个高精就行 = = #include<bits/stdc++.h> #define me(a) memset(a,0,sizeof(a)) using namespace std; string h[501...

2018-12-19

0 546

题解 P1008 【三连击】

#include<bits/stdc++.h> usingnamespacestd; int main() { 　　int a,b,c,d,e,f,g,h,i; 　　for(int i1=100;i1...

2018-12-19

0 575