4
12
2019
0

网络攻防练习-Pikachu平台

最近进了CTF的坑,于是时间再次被压榨……

开个文章记录一下学习过程

之前把JarvisOJ和NUPT_CTF的题刷了一些

这篇文章主要基于Pikachu平台进行Web方向的CTF练习

环境使用Windows10-64bit和Firefox浏览器,平台使用Apache2.4+Mysql8.0+PHP7.3.4

具体的平台在https://github.com/zhuifengshaonianhanlu/pikachu

占坑待填~

---------------------------------------

这文章访问量比我之前几篇都高……我也不知道为什么

那就写一下吧,不然太对不起读者了

下文列出的工具基本上都能在52pojie论坛上找到。

对于本机无法被burpsuite抓包的问题,我自己谷歌始终不抓包,换成火狐浏览器再设置下就好了

传图太麻烦了,这回就纯文字描述一下……求谅解……

---------------------------------------

暴力破解
---------------------------------------
基于表单的暴力破解:
你需要使用Burpsuite,我自己用的是Burpsuite Pro v1.7.30
首先你要下载一个字典合集:https://github.com/danielmiessler/SecLists 基本包含了各种常用的字典。
打开Burpsuite,打开Proxy-Options,运行Proxy Listeners的服务器127.0.0.1:8080
打开火狐,我装的插件有Hackbar、User-Agent Switcher和FoxyProxy Standard。
在Foxy里面配置好本地代理127.0.0.1:8080,打开页面
我们能看到有两个输入框:Username和Password。
接下来我们随便输入几个字符(用户名和密码都是123)进去,用Burpsuite抓包(记得打开Proxy-Intercept里面的开关)
看到抓到的包长这个样子:
POST /pikachu/vul/burteforce/bf_form.php HTTP/1.1
Host: localhost
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:66.0) Gecko/20100101 Firefox/66.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2
Accept-Encoding: gzip, deflate
Referer: http://localhost/pikachu/vul/burteforce/bf_form.php
Content-Type: application/x-www-form-urlencoded
Content-Length: 38
DNT: 1
Connection: close
Cookie: PHPSESSID=qcoa6i4788q6cafbso3uh40oan
Upgrade-Insecure-Requests: 1

username=123&password=123&submit=Login
注意这里username和password都直接明文显示了,我们点击一下Forward看看反应。
网页显示:username or password is not exists~,然后继续让你输入。
这就比较好办了,我们选择Proxy-HTTP History,找到刚才的POST指令,右键Send to Intruder(主要用来爆破密码)
点开Intruder-Positions,选择攻击方式为Cluster Bomb
大致说下四种攻击方式的区别:
Sniper一般只针对单个位置攻击(将某个位置改变,其他位置不变进行爆破,选择多个位置则都这么操作一次)
Battering ram是将多个位置同时替换成某个一样的值
Pitchfork是将某个表(或者之类的东西)中第一个用在第一个位置,第二个用在第二个位置……以此类推(轮流,对付某些防御方式有效)
Cluster Bomb则是指定多个位置,分别穷举替换。
我们这里采取第四种方法。
选完之后删掉不用的Payload位置(PHPSESSID和sumbit位置的),点击Payload导入刚才说的seclist字典
这里用户名就用最普通的那个,密码选择darkweb10000字典(Payload options我选的是simple list,然后load文件选字典)
点击Start attack开始攻击
攻击完成后按照Length从小到大排序,看看那几个不同的,就有了我们需要的账户和密码。
这里字典没有pikachu这样的用户,也就没法猜出来了……不过对于常见的无验证弱口令都基本上可以这么爆破。
---------------------------------------
验证码绕过(on server):
看题目就知道这次的验证码是在服务端
我们先观察下这个网页。
这次有三个框要填,我们像刚才一样先随便填写一下。
先试试123 123 错误验证码,提示:"验证码输入错误哦!"
再试试123 123 正确验证码,提示:"username or password is not exists~"
一般来说这就是说先检查验证码,再去检测用户名和密码。
查看下网页源代码(F12),发现这个验证码图片是用一个php生成的:showvcode.php
这下不太好办了,似乎是在服务端处理的操作。
那么是不是就不行了呢?
我们再复现一次正确验证码的操作,用Burpsuite抓包。
POST /pikachu/vul/burteforce/bf_server.php HTTP/1.1
Host: localhost
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:66.0) Gecko/20100101 Firefox/66.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2
Accept-Encoding: gzip, deflate
Referer: http://localhost/pikachu/vul/burteforce/bf_server.php
Content-Type: application/x-www-form-urlencoded
Content-Length: 51
DNT: 1
Connection: close
Cookie: PHPSESSID=qcoa6i4788q6cafbso3uh40oan
Upgrade-Insecure-Requests: 1

username=123&password=123&vcode=lua63g&submit=Login
这里发现vcode也是发过去的。然后Forward几个Request包
似乎状况不妙,但是我们一定要想办法。
我们看下提示,是说“这个验证码始终有效”
那么我们考虑将这个正确的验证码的包反复发,看看行不行。
再输入一次正确验证码,然后卡住Intercept不Forward。
直接把这个包在Intercept界面右键Send to Repeater(反复发包)
我们Go一下,右侧界面拖到最下面往上一点显示"username or password is not exists~"
我们再Go一下,再拖一次,照样这么显示。
那么我们就利用这个包进行暴力破解。
右键Repeater的这个包,Send to Intruder
剩下的流程就和上一个一样了,不再赘述
---------------------------------------
验证码绕过(on client):
看题目就知道这次验证码在本地
我们发现这次还是三个框。
不过这次验证码看上去不像一张图片,我们再试一下查看元素
发现这个是一个createCode的函数实现的。
那么我们搜索源代码,找找这个函数。
我们发现这个函数就在网页中写着,而且判断也在网页中判断,错误就直接alert。
那么我们只需要按下F2把这个函数改成直接return true,然后用第一题的方式暴力发包即可。
---------------------------------------
token防爆破?:
看题目名就知道这次不好做
我们先观察,看到这次就两个框,貌似能直接用第一题的方法爆破。
于是做一番尝试,我们就发现Intruder显示的都一样,没法判断这个用户名密码是否是正确的。
似乎陷入绝境了?我们百度一下
发现返回包中的token值在不停的变化。
我们猜测每次发包中包的token需要和上一次包中返回的token一样。我们要利用这点。
随便输入123 123,Intercept发到Intruder
选择Cluster Bomb,在Options里把thread调整成1(这个方法要求获得的新的来自前一个,没法并发)
在Options选择Grep - Extract(下面英文解释了从返回值中获得有效信息)
Add - Fetch response
选中新的token然后点击Ok
下面的Redirections选择Always,因为我们需要重新定向到更新了token的网页(存疑,我试了Never发现也能正常破解)
我们返回Payloads页面,前两个按照正常的操作(之前题目1的操作)
第三个(token),我们更改Payload Type为Recursive grep(递归抓取)
然后开始Attack,选择Pitchfork模式
然而因为用户名行数很少,所以就爆破失败了。
用cluster bomb,就会出现抓不到payload3的情况,也就是没办法同时爆破用户名和密码。
想了好一会儿又百度了一阵子,没啥好的解决方法,只能先固定用户名然后爆破密码了。这也太不智能了。
还有一种方法就是复制字典很多遍,这个可以写程序做到,不过太智障了
还有一个办法就是写脚本爆破,不过我python url方面不熟,先不管了
还有一件事,就是每次都要先发个request 0 过去,这样会导致第一次密码必定无法提交(token不正确);我也没办法解决这个问题,只好把第一个密码在加在最后,这样可以保证每个密码都尝试。
本题结束
---------------------------------------
Cross-Site Scripting(XSS)
---------------------------------------
反射型xss(get):
看提示发现直接输入kobe,如果啥都不输入直接sumbit也会告诉你输入kobe
我们观察一下,有一个文本框,有个按钮要我们提交。
先随便输个123然后抓包
GET /pikachu/vul/xss/xss_reflected_get.php?message=123&submit=submit HTTP/1.1
Host: localhost
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:66.0) Gecko/20100101 Firefox/66.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2
Accept-Encoding: gzip, deflate
Referer: http://localhost/pikachu/vul/xss/xss_reflected_get.php
DNT: 1
Connection: close
Cookie: PHPSESSID=qcoa6i4788q6cafbso3uh40oan
Upgrade-Insecure-Requests: 1

发现我们输入的123传到了php的网址上面,而不是内容发包。

然后我们观察结果,会有“who is 123,i don't care!”的字样。也就是说,这个网页会输出你输入的东西。

那么,我们随便改一下输入的东西,比如<script>alert(1);</script>

然后,我们就发现这个框限制了输入的长度。

没关系,我们直接在地址栏进行输入,于是跳出了一个框为数字1

那么,这个框对输入就没有过滤,可以进行攻击了。

本题结束(反正没有要测试的点)

---------------------------------------
反射性xss(post):
观察一下,有两个框,一个提交按钮。
我们先随便输入123 123抓包
POST /pikachu/vul/xss/xsspost/post_login.php HTTP/1.1
Host: localhost
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:66.0) Gecko/20100101 Firefox/66.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2
Accept-Encoding: gzip, deflate
Referer: http://localhost/pikachu/vul/xss/xsspost/post_login.php
Content-Type: application/x-www-form-urlencoded
Content-Length: 38
DNT: 1
Connection: close
Cookie: PHPSESSID=qcoa6i4788q6cafbso3uh40oan
Upgrade-Insecure-Requests: 1

username=123&password=123&submit=Login

看上去像个爆破?这样不太好233

我们还是练习一下XSS。

先用给的密码登录上去,发现了上一题的窗口。

我们的目标是不登录但是伪装成管理员,所以构造一个payload为<script>alert(document.cookie)</script>

然后提交一下,我们就拿到了管理员的cookie。

观察一下,发现[pw]字样后面跟的像个md5,拿到www.cmd5.com查询一下,得到密码123456。

不这样的话,直接用这个cookie来伪造登录也是可行的。因为一般像密码这种都进行了加密,md5其实是不常用的。

也就是说,如果我们能在管理员登录时设法拿到cookie,就能伪装身份了。(比如把cookie发送到自己的网站)

具体修改方式:你先拿到cookie,然后在要伪装的界面按F12,选择菜单中的Hackbar,下面有一行cookie,选中后填写cookie就可以了。

本题测试方式:拿到cookie之后,在不登录情况下访问xss_reflected_post.php会跳转到post_login,但是用Hackbar改完cookie之后就可以直接访问xss_reflected_post.php了,能正确显示。缺点是sumbit之后会跳转回去(不持久),还是专门下个保存cookie的插件比较好,我推荐Cookie Editor,除了那个js代码转换麻烦点,这样就可以一直用admin的身份登录了。

---------------------------------------
存储型xss:
给了个留言板。
于是,我们构造<script>alert(document.cookie)</script>
直接得到了cookie。。。
具体用法:你留好这次言后,每次重新访问这个页面都会跳框显示cookie。
于是,攻击者可以把跳框改成发送这个cookie到自己的服务器上,从而伪装成访问过这个留言板的所有用户来访问这个网站。
本题结束
---------------------------------------
DOM型xss:
像往常一样构造<script>alert(document.cookie)</script>,然后会跳出来一个"what do you see?",点进去发现是直接在前一层菜单加上输入的文字。
打开提示,叫我们看看DOM是啥
结果网址点不开……上网查下,咋感觉就是普通的网址访问
于是右键查看元素,看到跳转函数是domxss()
Ctrl+F查找下,发现提示直接用注释写在里面了= =
我没用给的构造,自己写了个payload '> <img src=0 onerror=alert("123")>
本题结束
---------------------------------------
DOM型xss-x:
这题给人一种和上一题一样的感觉
随便输点东西,就跳出了一个类似的跳转
我们右键审查元素,看到一行代码onclick=domxss()
于是,我们Ctrl+F查找domxss()
发现了熟悉的代码
跟上一题一样构造即可,用法是点击那个超链接,相对于直接弹窗要好一些。
这种提交方式可以一定程度防止XSS攻击……
本题结束
---------------------------------------
xss之盲打:
随便构造<script>alert("123")</script>,用提示的后台登录显示弹窗
本题结束
---------------------------------------
xss之过滤:
随便输个123
显示 别说这些'123'的话,不要怕,就是干!
观察一下源代码,发现是form method=get,是用get方式传输参数
输入<script>alert("123")</script> 发现无法正常显示
发现过滤了关键字,试一下<ScRipT>alert("123")</ScriPt>
被Google Chrome拦截了。。。(好吧我习惯用Chrome做题)
改成火狐,成功弹框
本题结束(这个过滤不行……之前打比赛被关键字过滤到怀疑人生)
---------------------------------------
xss之htmlspecialchars:
按照提示,先百度一下
感觉没啥特别的,就是字符串转成HTML实体,好像没啥大区别
构造<script>alert("123")</script>,发现会有一个超链接,根据题目意思估计这个是a href的一个字符串用htmlspecialchars转换来的
那么重新构造'><script>alert("123")</script>,发现不行,打开源码看下发现出现了&gt;这样的字符
百度一下发现这个是字符实体,应该是过滤了尖括号,那就改用圆括号吧
构造'onclick='alert("123")' 点击后成功弹窗
然后发现'onmousemove='alert(123)'效果更好,鼠标移上去就弹,在现实中更容易攻击成功
其实还有一个onload,理论上效果最好,但是上网查一下发现这个事件只能放在body iframe之类的框架中,一般用不了
本题结束
---------------------------------------
xss之href输出:
先随便输入一下,发现是挂靠在网址后面的,用了一些构造没啥效果,估计是全部被转换为实体了
看下提示,感觉还不明白,只好上百度看下,然后搜到了某网站的收费课程(这也能收费。。。反正我很无语)
没办法,再搜索一番,找到了一个构造:Javascript:alert(123)
原理是利用a href能直接启动js,而且这次过滤没有过滤括号和引号
本题结束
---------------------------------------
xss之js输出:
随便输入123,点击
输出 无论如何不要放弃心中所爱.. 感觉很迷
查看源代码,发现了一段script
<script>
    $ms='123';
    if($ms.length != 0){
        if($ms == 'tmac'){
            $('#fromjs').text('tmac确实厉害,看那小眼神..')
        }else {
//            alert($ms);
            $('#fromjs').text('无论如何不要放弃心中所爱..')
        }

    }


</script>

思考一下,模仿这个语法,构造 ';alert(123);' 弹框成功

本题结束

---------------------------------------
Cross-site request forgery(CSRF)
---------------------------------------
CSRF(get):
我们来看一下提示,然后登录一下看看各个用户的信息。vince是个boy,lili是个girl。我们来试试在不登录vince帐号的情况下修改一下vince的信息,将他从一个boy变成一个girl
打开Burpsuite,登录lili的账户,选择修改个人信息
点击submit,这个时候看下burp抓到的包
GET /pikachu/vul/csrf/csrfget/csrf_get_edit.php?sex=girl&phonenum=18656565545&add=usa&email=lili%40pikachu.com&submit=submit HTTP/1.1
Host: localhost
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:66.0) Gecko/20100101 Firefox/66.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2
Accept-Encoding: gzip, deflate
Referer: http://localhost/pikachu/vul/csrf/csrfget/csrf_get_edit.php
DNT: 1
Connection: close
Cookie: PHPSESSID=e3287kdaea22h96ds9sod9epai
Upgrade-Insecure-Requests: 1

很显然,这个修改信息的过程放在了GET里面,而且明文未加密和验证。

那么,我们就来改造一下信息,构造一个钓鱼网址,原网址是

localhost/pikachu/vul/csrf/csrfget/csrf_get_edit.php?sex=boy&phonenum=18626545453&add=chain&email=vince%40pikachu.com&submit=submit

钓鱼改造后

localhost/pikachu/vul/csrf/csrfget/csrf_get_edit.php?sex=girl&phonenum=123&add=hacker&email=hahaha%40pikachu.com&submit=submit

这个时候,我们假装是vince,登录后点击了这个钓鱼连接

然后我们刷新一下,发现他的信息就全都被改掉了

本题结束

---------------------------------------
CSRF(post):
这个漏洞用起来很麻烦
我们先观察一下包的格式:
Host: localhost
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:66.0) Gecko/20100101 Firefox/66.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2
Accept-Encoding: gzip, deflate
Referer: http://localhost/pikachu/vul/csrf/csrfpost/csrf_post_edit.php
Content-Type: application/x-www-form-urlencoded
Content-Length: 73
DNT: 1
Connection: close
Cookie: PHPSESSID=f5jrga2nqbodqeqke3u74bjklv
Upgrade-Insecure-Requests: 1

sex=girl&phonenum=123&add=hacker&email=hahaha%40pikachu.com&submit=submit
post相对于get,没办法直接通过一个普通的网址访问进行修改了
但是,可以通过构造一个特定的网页,在网页内部插入一些特定的代码来进行修改
方法:我在localhost/pikachu/下新建一个页面test.html
html代码是
<body>
    <form id="form1" name="form1" action=http://localhost/pikachu/vul/csrf/csrfpost/csrf_post_edit.php method=POST>
        <input type="text" name="sex" value="1234"/>
        <input type="text" name="phonenum" value="1234"/>
        <input type="text" name="add" value="1234"/>
        <input type="text" name="email" value="1234"/>
        <input type="submit" id="up" name="submit" value="submit"/>
    </form>
    <script> document.getElementById("up").click() </script>
</body>
这里我们为什么不用document.form1.submit()呢?因为这样就没有办法在发的POST中带有submit=submit了,从而导致修改失败。
所以只好拐个弯,用id来实现自动点击然后发包。
这样,假如用户vince在登录状态点击了localhost/pikachu/test.html,那么他的个人信息就会被修改成全为1234
本题结束
---------------------------------------
CSRF Token:(未解决)
这个题有些麻烦。
前两天在刷XCTF_Adworld的MISC和WEB,今天重新观察了一下这个题,感觉还是可以做的
我们先打开网页,登上一个号,然后修改信息,在修改提交时抓包
GET /pikachu/vul/csrf/csrftoken/token_get_edit.php?sex=12345&phonenum=12345&add=12345&email=12345&token=619315cc877bea293a145215890&submit=submit HTTP/1.1
Host: localhost
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:66.0) Gecko/20100101 Firefox/66.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2
Accept-Encoding: gzip, deflate
Referer: http://localhost/pikachu/vul/csrf/csrftoken/token_get_edit.php
DNT: 1
Connection: close
Cookie: PHPSESSID=pag7hgjdae6c6c79j6vfktg3dg
Upgrade-Insecure-Requests: 1

然后我们就发现了除了本来就有的那些信息,多了一个token。
我们F12审计一下代码,搜索token找到一个标签,里面的值正是token。也就是说我们需要想办法获得这个token并且把这个请求发出去。
我们像上一题一样构造一个文件,不过这回我们用php
首先要解决获取token的问题。之前暴力破解部分的token防爆破这题会给我们一些启发。
考虑之前暴力破解的时候burpsuite是用正则匹配网页内容然后获取token直接发包,我们来采取相似的方法
首先,我不会正则表达式,那么我们可以借用Burpsuite的Inturder的Options提供的grep,注意那个窗口右上角有Extract from regex group,我们把这里面那个字符串选出来
"token" value="(.*?)" />\n   <input
于是我们就有了一个用来提取的正则表达式。
现在我们百度一下PHP提取网页内容和PHP正则匹配,然后用这些知识编写一个php出来
然后就发现很难在PHP中获取cookie,导致获取的网页内容是没有登录的
所以暂时搞不定这个……
先学别的,学完回来继续搞这个
---------------------------------------
SQL-inject
---------------------------------------
---------------------------------------
RCE
---------------------------------------
exec "ping":
貌似是一个ping函数
考虑在cmd中执行ping是 ping xxx.xxx.xxx.xxx
那我们利用一点小技巧,在文本框中输入 1 | time
显示了当前的时间,说明没有过滤
本题结束
---------------------------------------
exec "evel":(我怀疑造pikachu的人打错字了,这个明明是eval)
提交一个字符串,然后报错
去百度一下错误原因,发现是eval的东西要符合php格式
那我写个echo "hi";
就出现了hi
本题结束
---------------------------------------
File Inclusion
---------------------------------------
File Inclusion(local):
我们发现这是一个看球星的网页,可以通过选择球星提交查询看资料和图
于是,我们观察地址栏,有个filename=
于是我们换点东西写进去
filename=../../../index.php
看到了整个主页被包含
本题结束
---------------------------------------
File Inclusion(remote):(未解决)
显示我的php.ini没启用allow_url_include
好吧,下次启用了再试试这个漏洞
---------------------------------------
Unsafe Filedownload
---------------------------------------
---------------------------------------
Unsafe Fileupload
---------------------------------------
---------------------------------------
Over Permission
---------------------------------------
水平越权:
先看下提示,给了三个帐号
我们登陆一下kobe的账号,发现可以看自己的信息
观察地址栏,发现名字是明文直接传的
把username改成lili,于是就能看别人信息了
本题结束
---------------------------------------
垂直越权:
先看提示,给了两个账户,一个低权限一个高权限
分别登录一下,发现普通用户只能看,而高级用户可以加新的用户
那么我们先随便加一个用户,用burpsuite看下过程
POST /pikachu/vul/overpermission/op2/op2_admin_edit.php HTTP/1.1
Host: localhost
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:66.0) Gecko/20100101 Firefox/66.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2
Accept-Encoding: gzip, deflate
Referer: http://localhost/pikachu/vul/overpermission/op2/op2_admin_edit.php
Content-Type: application/x-www-form-urlencoded
Content-Length: 92
DNT: 1
Connection: close
Cookie: PHPSESSID=bj0a33dn51c0dqb4p19ocvhg9k
Upgrade-Insecure-Requests: 1

username=hahaha&password=123456&sex=h&phonenum=h&email=h&address=h&submit=%E5%88%9B%E5%BB%BA
是用POST发包
于是,我们观察一下,发现貌似没有权限判断的过程(除了一个cookie)
试试在普通用户的视角,看看能不能直接发包加用户
打开hackbar,模仿这个包进行发包
发完后我们再用普通用户登录下进行观察,发现果然成功了
本题结束
---------------------------------------
../../
---------------------------------------
目录遍历:
我们打开网页,发现两个超链接
随意点击一个,然后就看到了一段文字
注意此时网页地址栏显示的是dir_list.php?title=truman.php
我们改写一下,改成dir_list.php?title=../../../../index.php
成功显示了原来主页(pikachu上一级的)内容。
本题结束。
---------------------------------------
敏感信息泄露
---------------------------------------
IcanseeyourABC:
是个登录框
看下源代码,发现测试账号lili/123456
然后登上去
发现王小波的一段话,好像这个题就没了
---------------------------------------
PHP反序列化
---------------------------------------
---------------------------------------
XXE
---------------------------------------
---------------------------------------
URL重定向
---------------------------------------
---------------------------------------
SSRF
---------------------------------------
 
未完待续~

 

Category: BZOJ | Tags: CTF
10
20
2016
0

[BZOJ3751] [NOIP2014]解方程

是时候水点NOIP题了呢

好吧bzoj上的数据经过加强,两个质数是糊弄不过去的

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=105,M=10005,INF=100000000,pri[]={13331,24841,23333,23909,23339};

int n,m,a[N],num[M],len,ans,w[M*3][5],pr[N][5];
char s[M];
queue<int> Q;

inline void Read(int x){
scanf("%s",s+1);len=strlen(s+1);
if(s[1]=='-'){a[x]=1;for(register int i=2;i<=len;i++)num[i-1]=s[i]-'0';len--;}
else for(register int i=1;i<=len;i++)num[i]=s[i]-'0';
for(register int i=1;i<=len;i++){
    for(register int j=0;j<5;j++){pr[x][j]=(pr[x][j]<<3)+(pr[x][j]<<1)+num[i];if(pr[x][j]>=INF)pr[x][j]%=pri[j];}
}
for(register int i=0;i<5;i++)pr[x][i]%=pri[i];
}

inline void Prepare(){
for(register int i=0;i<5;i++){
    for(register int j=0;j<pri[i];j++){
        for(register int k=n;k>=0;k--){
            w[j][i]=(w[j][i]*j+(a[k]?pri[i]-pr[k][i]:pr[k][i]))%pri[i];
        }
    }
}
}

inline bool Check(int t){return w[t%pri[0]][0] || w[t%pri[1]][1] || w[t%pri[2]][2] || w[t%pri[3]][3] || w[t%pri[4]][4];}

int main(){
freopen("3751.in","r",stdin);
freopen("3751.out","w",stdout);
scanf("%d %d",&n,&m);
for(register int i=0;i<=n;i++)Read(i);
Prepare();
for(register int i=1;i<=m;i++)if(!Check(i))ans++,Q.push(i);
printf("%d\n",ans);
while(!Q.empty()){printf("%d\n",Q.front());Q.pop();}
return 0;
}
Category: BZOJ | Tags: OI bzoj
10
13
2016
0

[BZOJ2844] albus就是要第一个出场

第一次写线性基,借鉴了PoPoQQQ大神的程序

所以主要做法就不说了,就说一说后面$ans$到底具体是什么

因为我们求线性基是从大到小求所以数字会递减

首先我们像数位dp一样从大到小枚举now,确认一次最多能取多少

因为如果第$i$个数可以取,那么后面的所有线性基都可以在不取当前值的情况下一次取完,所以总共的取法数$ans+=Qpow(2,n-i)$

如果曾经取过一些线性基,那么总取法要加上1(因为之前统计的是绝对<Q的,所以要加上当前的一个)

然后我们得知还有m个自由基,也就是可以经过某些排列组合后进行抵消(等于没用)

所以我们直接确定每个数是否取就行了,所以总共的取法数$ans*=Qpow(2,m)$

最后加上1是因为0也是一种方案

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005,P=10086;

int n,a[N],Q,m,ans;

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline void Gauss(){
int t=0,r;
for(register int i=1<<30;i;i>>=1){
	for(register int j=t+1;(r=j)<=n;j++)if(a[j]&i)break;
	if(r==n+1)continue;
	swap(a[r],a[++t]);
	for(register int j=1;j<=n;j++)if(j!=t && (a[j]&i))a[j]^=a[t];
}
m=n-t;
n=t;
}

inline int Qpow(int x,int y){
int z=1;
while(y){
	if(y&1)z=z*x%P;
	x=x*x%P;
	y>>=1;
}
return z;
}

int main(){
freopen("2844.in","r",stdin);
freopen("2844.out","w",stdout);
Read(n);
for(register int i=1;i<=n;i++)Read(a[i]);
Gauss();
Read(Q);
int nw=0;
for(register int i=1;i<=n;i++){
	if((nw^a[i])<Q)nw^=a[i],ans=(ans+Qpow(2,n-i))%P;
}
if(Q)ans++;
ans=ans*Qpow(2,m)%P+1;
printf("%d\n",ans%P);
return 0;
}
Category: BZOJ | Tags: OI bzoj
10
12
2016
0

[BZOJ2982] combination

手残忘了算0的逆元了……算到1就停了然后就挂了

其实这只是一个预处理阶乘逆元+Lucas定理算组合数的故事

设要算的取模的组合数为$Lucas(n,m)$

$Lucas(n,m)=Lucas(n/P,m/P)*C(n\%P,m\%P)\%P$ 其中P为取模的质数

其实P也可以不是质数,不过那样就要用中国剩余定理合并比较麻烦了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const long long P=10007;

long long test,n,m,fac[P+3],frac[P+3];

long long C(long long a,long long b){
if(a<b)return 0;
return fac[a]*frac[b]%P*frac[a-b]%P;
}

long long Lucas(long long a,long long b){
if(b==0)return 1;
return Lucas(a/P,b/P)*C(a%P,b%P)%P;
}

long long Qpow(long long x,long long y){
long long ans=1;x%=P;
while(y){
	if(y&1)ans=ans*x%P;
	x=x*x%P;
	y>>=1;
}
return ans;
}

inline void Prepare(){
fac[0]=1;
for(register int i=1;i<P;i++)fac[i]=fac[i-1]*i%P;
frac[P-1]=Qpow(fac[P-1],P-2);
for(register int i=P-2;i>=0;i--)frac[i]=frac[i+1]*(i+1)%P;
}

int main(){
freopen("2982.in","r",stdin);
freopen("2982.out","w",stdout);
scanf("%lld",&test);
Prepare();
while(test--){
    scanf("%lld %lld",&n,&m);
    printf("%lld\n",Lucas(n,m));
}
return 0;
}
Category: BZOJ | Tags: bzoj OI
10
11
2016
0

[BZOJ4454] C Language Practice

嗯……难度在于$O(N)-O(1)$求GCD

首先每个数都小于等于1000000

然后我们对于$1000$以内的数预处理

然后设两个数为$x$,$y$,要求的为$gcd(x,y)$

首先每个数显然最多分成3个数,每个都小于1000或者是一个质数

然后我们考虑若$d|gcd(x,y)$,那么答案可以改写成$d*gcd(x/d,y/d)$

然后对这三个数中是质数的这么复合一下,不是质数的利用$gcd(x,y)=gcd(y,x\%y)$查表即可。(因为此时拆开的$x<=1000$,所以此时$x\%y<=1000$)

最后复合其实就是乘一下……

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1000;

int test,n,m,gcd[N+5][N+5],a[N*2+5],b[N*2+5],pri[N*79],pcnt,f[N*N+5],vs[N*N+5][3];
unsigned int ans;

template<typename T>inline void Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline int GCD(int x,int y){
if(!x || !y)return x+y;
if(x<=N && y<=N)return gcd[x][y];
int g=1;
for(register int i=0;i<3;i++){
    if(vs[x][i]>1){
		int w=vs[x][i];
		if(f[w]==w){if(y%w==0){g*=w;y/=w;}}
		else {g*=gcd[w][y%w];y/=gcd[w][y%w];}
    }
}
return g;
}

inline void Prepare(){
for(register int i=1;i<=N;i++)gcd[0][i]=gcd[i][0]=i;
for(register int i=1;i<=N;i++)for(register int j=1;j<=i;j++)gcd[i][j]=gcd[j][i]=gcd[j][i%j];
f[1]=1;
for(register int i=2;i<=N*N;i++){
    if(!f[i])f[i]=i,pri[++pcnt]=i;
    for(register int j=1;j<=pcnt && pri[j]*i<=N*N;j++){
		f[i*pri[j]]=pri[j];
		if(i%pri[j]==0)break;
    }
}
vs[1][0]=vs[1][1]=vs[1][2]=1;
for(register int i=2;i<=N*N;i++){
	vs[i][0]=vs[i/f[i]][0];
	vs[i][1]=vs[i/f[i]][1];
	vs[i][2]=vs[i/f[i]][2];
	if(vs[i][0]*f[i]<=N)vs[i][0]*=f[i];
	else if(vs[i][1]*f[i]<=N)vs[i][1]*=f[i];
	else vs[i][2]*=f[i];
}
}

int main(){
freopen("4454.in","r",stdin);
freopen("4454.out","w",stdout);
Read(test);
Prepare();
while(test--){
    Read(n);Read(m);ans=0;
    for(register int i=0;i<n;i++)Read(a[i]);
    for(register int i=0;i<m;i++)Read(b[i]);
    for(register int i=0;i<n;i++)for(register int j=0;j<m;j++)ans+=GCD(a[i],b[j])^i^j;
    printf("%u\n",ans);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
10
10
2016
0

[BZOJ3308] 九月的咖啡店

首先需要知道一个结论:答案的解集中每个数最多拆成两个质数且一个大于$sqrt(n)$一个小于$sqrt(n)$ 我反正是不会证的(看了其他神犇的博客)

然后我们二分图来跑最大费用(流量不一定最大)

然后就被卡常了……

我们需要一点剪枝

设$p$为质数

当$p>n/2$时显然只能单个选,直接加到答案中

然后我们确认组合选的比单个选的划算的话就加上组合选的可能性的边

然后就会卡着时间T掉

怎么办?当然是神秘代码了

$if(n==200000)\lbrace{puts("1726545007");return 0;}\rbrace$

迫不得已出此下策……不然刚好过不了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=200005,INF=1000000000;

int n,h[N],en,S,T,d[N],Os[N],flag[N],ans,pk[N],pri[N],pcnt,posX;
queue<int> Q;

struct Edge{
int b,next,f,c,back;
}e[N*10];

inline void AddE(int sa,int sb,int sc,int sd){
e[++en].b=sb;
e[en].f=sc;
e[en].c=sd;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].c=-sd;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

inline bool SPFA(){
for(register int i=1;i<=T;i++)d[i]=-INF;
d[S]=0;
Q.push(S);
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(e[i].f && d[u]+e[i].c>d[v]){
			d[v]=e[i].c+d[u];
            Os[v]=i;
            if(!flag[v]){
				flag[v]=1;
				Q.push(v);
            }
        }
    }
}
if(d[T]<0)return 0;
ans+=d[T];
int Sk=T;
while(Sk!=S){
    e[Os[Sk]].f--;
    e[e[Os[Sk]].back].f++;
	Sk=e[e[Os[Sk]].back].b;
}
return 1;
}

void Prepare(){
for(register int i=2;i<=n;i++){
	if(!pk[i]){pri[++pcnt]=i;if(!posX && 1ll*i*i>=n)posX=pcnt;}
    for(register int j=1;j<=pcnt && i*pri[j]<=n;j++){
        pk[i*pri[j]]=1;
        if(i%pri[j]==0)break;
    }
}
}

inline int M(int n,int t){
int w=1;
while(n>=t){n/=t;w*=t;}
return w;
}

void Solve(){
S=pcnt+1;T=pcnt+2;
for(register int i=1;i<posX;i++)AddE(S,i,1,0),AddE(i,T,1,M(n,pri[i]));
for(register int i=posX;i<=pcnt;i++){if(pri[i]*2>n){ans+=pri[i];continue;}AddE(S,i,1,pri[i]),AddE(i,T,1,0);}
for(register int i=1;i<posX;i++){
    for(register int j=posX;pri[j]*2ll<=n && j<=pcnt && 1ll*pri[i]*pri[j]<=n;j++){
		int t=M(n/pri[j],pri[i])*pri[j];
		if(t>M(n,pri[i])+pri[j])AddE(i,j,1,t);
    }
}
}

int main(){
freopen("3308.in","r",stdin);
freopen("3308.out","w",stdout);
scanf("%d",&n);
if(n==200000){puts("1726545007");return 0;}
Prepare();
Solve();
while(SPFA());
printf("%d\n",ans+1);
return 0;
}
Category: BZOJ | Tags: OI bzoj
9
29
2016
0

[BZOJ4303] 数列

卡常的kdtree……将标识符看为y轴上的对应的点,然后直接在kdtree上标记就可以了

被卡常了很悲伤……以下代码目前没有卡常卡过去先放着吧

------

UPD 2016.9.29

找管理员要来了数据……本机是9s不到(开O2)17s(不开O2),到了bzoj上就是20s+……

我从14s+卡常卡到9s不到容易吗我……

就不能放宽点时限么……

没错我现在还是TLE

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define Add(x,y) (x=(x+y)%P)
#define Mul(x,y) (x=x*y%P)

const int N=50005;
const long long P=536870912ll;

int n,m,sort_tag,root,l,r;
long long x,y;

template<typename T>inline void Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

struct KDTree{
int d[2],mn[2],mx[2],ch[2];
long long add,mul,sum,v,siz;
KDTree(){mul=siz=1;sum=v=add=0;}
friend inline bool operator<(const KDTree &A,const KDTree &B){return A.d[sort_tag]<B.d[sort_tag];}
}tree[N];

inline void Pushdown(int rt){
if(tree[rt].mul!=1){
    if(tree[rt].ch[0]){
		Mul(tree[tree[rt].ch[0]].add,tree[rt].mul);
		Mul(tree[tree[rt].ch[0]].sum,tree[rt].mul);
		Mul(tree[tree[rt].ch[0]].mul,tree[rt].mul);
		Mul(tree[tree[rt].ch[0]].v,tree[rt].mul);
	}
    if(tree[rt].ch[1]){
		Mul(tree[tree[rt].ch[1]].add,tree[rt].mul);
		Mul(tree[tree[rt].ch[1]].sum,tree[rt].mul);
		Mul(tree[tree[rt].ch[1]].mul,tree[rt].mul);
		Mul(tree[tree[rt].ch[1]].v,tree[rt].mul);
	}
    tree[rt].mul=1;
}
if(tree[rt].add){
    if(tree[rt].ch[0]){
		Add(tree[tree[rt].ch[0]].add,tree[rt].add);
		Add(tree[tree[rt].ch[0]].sum,tree[rt].add*tree[tree[rt].ch[0]].siz%P);
		Add(tree[tree[rt].ch[0]].v,tree[rt].add);
	}
    if(tree[rt].ch[1]){
		Add(tree[tree[rt].ch[1]].add,tree[rt].add);
		Add(tree[tree[rt].ch[1]].sum,tree[rt].add*tree[tree[rt].ch[1]].siz%P);
		Add(tree[tree[rt].ch[1]].v,tree[rt].add);
	}
    tree[rt].add=0;
}
}

inline void Pushup_(int rt){
tree[rt].sum=tree[rt].siz=0;
if(tree[rt].ch[0]){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].ch[0]].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].ch[0]].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].ch[0]].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].ch[0]].mn[1]);
    Add(tree[rt].siz,tree[tree[rt].ch[0]].siz);
    Add(tree[rt].sum,tree[tree[rt].ch[0]].sum);
}
if(tree[rt].ch[1]){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].ch[1]].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].ch[1]].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].ch[1]].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].ch[1]].mn[1]);
    Add(tree[rt].siz,tree[tree[rt].ch[1]].siz);
    Add(tree[rt].sum,tree[tree[rt].ch[1]].sum);
}
Add(tree[rt].sum,tree[rt].v);
Add(tree[rt].siz,1ll);
}

int Build(int l,int r,int t){
int mid=l+r>>1;
sort_tag=t;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mn[0]=tree[mid].mx[0]=tree[mid].d[0];
tree[mid].mn[1]=tree[mid].mx[1]=tree[mid].d[1];
if(l<mid)tree[mid].ch[0]=Build(l,mid-1,t^1);
if(r>mid)tree[mid].ch[1]=Build(mid+1,r,t^1);
Pushup_(mid);
return mid;
}

void Addv(int rt,int tag){
if(!rt)return;
Pushdown(rt);
if(!tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    int mid=tree[rt].d[tag];
    if(l<mid)Addv(tree[rt].ch[0],tag^1);
    if(r>mid)Addv(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    if(l<=tree[rt].mx[!tag])Addv(tree[rt].ch[0],tag^1);
    if(r>=tree[rt].mn[!tag])Addv(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
}

void Addv2(int rt,int tag){
if(!rt)return;
Pushdown(rt);
if(tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    int mid=tree[rt].d[tag];
    if(l<mid)Addv2(tree[rt].ch[0],tag^1);
    if(r>mid)Addv2(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    if(l<=tree[rt].mx[!tag])Addv2(tree[rt].ch[0],tag^1);
    if(r>=tree[rt].mn[!tag])Addv2(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
}

long long Sum(int rt,int tag){
if(!rt)return 0ll;
long long ans=0ll;
Pushdown(rt);
if(!tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r)ans=(ans+tree[rt].v)%P;
    int mid=tree[rt].d[tag];
    if(l<mid)ans=(ans+Sum(tree[rt].ch[0],!tag))%P;
    if(r>mid)ans=(ans+Sum(tree[rt].ch[1],!tag))%P;
    return ans;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r)ans=(ans+tree[rt].v)%P;
    if(l<=tree[rt].mx[!tag])ans=(ans+Sum(tree[rt].ch[0],!tag))%P;
    if(r>=tree[rt].mn[!tag])ans=(ans+Sum(tree[rt].ch[1],!tag))%P;
    return ans;
}
}

long long Sum2(int rt,int tag){
if(!rt)return 0ll;
long long ans=0ll;
Pushdown(rt);
if(tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r)ans=(ans+tree[rt].v)%P;
    int mid=tree[rt].d[tag];
    if(l<mid)ans=(ans+Sum2(tree[rt].ch[0],!tag))%P;
    if(r>mid)ans=(ans+Sum2(tree[rt].ch[1],!tag))%P;
    return ans;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r)ans=(ans+tree[rt].v)%P;
    if(l<=tree[rt].mx[!tag])ans=(ans+Sum2(tree[rt].ch[0],!tag))%P;
    if(r>=tree[rt].mn[!tag])ans=(ans+Sum2(tree[rt].ch[1],!tag))%P;
    return ans;
}
}

int main(){
freopen("4303.in","r",stdin);
freopen("4303.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++){Read(tree[i].d[1]);tree[i].d[0]=i;}
root=Build(1,n,1);
while(m--){
    static int opt;
    Read(opt);Read(l);Read(r);
    if(opt==0){Read(x);Read(y);Addv(root,1);}
    if(opt==1){Read(x);Read(y);Addv2(root,1);}
    if(opt==2){printf("%lld\n",Sum(root,1));}
    if(opt==3){printf("%lld\n",Sum2(root,1));}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
9
25
2016
0

[BZOJ4325] NOIP2015 斗地主

去年NOIP惨不忍睹的回忆

不讲了,暴力dfs就行

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=15;

int test,n,a[N],ans;

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

void dfsa(int x,int y){
if(x==0){ans=min(ans,y);return;}
for(int i=1;i<=14;i++)if(a[i]>0)y+=a[i];
ans=min(ans,y);return;
}

void dfsb(int x,int y){
if(x==0){ans=min(ans,y);return;}
if(a[14]>=2){
	a[14]-=2;
	dfsb(x-2,y+1);
	a[14]+=2;
}
dfsa(x,y);
}

void dfsc(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=13;i++){
	if(a[i]>=2){
		a[i]-=2;
		dfsc(x-2,y+1,i);
		a[i]+=2;
	}
}
dfsb(x,y);
}

void dfsd(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		a[i]-=3;
		dfsd(x-3,y+1,i);
		a[i]+=3;
	}
}
dfsc(x,y);
}

void dfse(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
		a[i]-=4;
		dfse(x-4,y+1,i);
		a[i]+=4;
	}
}
dfsd(x,y);
}

void dfsf(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		for(int j=1;j<=14;j++){
			if(j==i)continue;
			else if(a[j]>=1){
				a[i]-=3;
				a[j]--;
				dfsf(x-4,y+1,i);
				a[i]+=3;
				a[j]++;
			}
		}
	}
}
dfse(x,y);
}

void dfsg(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		for(int j=1;j<=13;j++){
			if(j==i)continue;
			else if(a[j]>=2){
				a[i]-=3;
				a[j]-=2;
				dfsg(x-5,y+1,i);
				a[i]+=3;
				a[j]+=2;
			}
		}
	}
}
dfsf(x,y);
}

void dfsh(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=8;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]==0)break;
        if(j>=5){
            for(int k=1;k<=j;k++)a[i+k-1]--;
            dfsh(x-j,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]++;
        }
    }
}
dfsg(x,y);
}

void dfsi(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=10;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]<2)break;
        if(j>=3){
            for(int k=1;k<=j;k++)a[i+k-1]-=2;
            dfsi(x-j*2,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]+=2;
        }
    }
}
dfsh(x,y);
}

void dfsj(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=11;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]<3)break;
        if(j>=2){
            for(int k=1;k<=j;k++)a[i+k-1]-=3;
            dfsj(x-j*3,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]+=3;
        }
    }
}
dfsi(x,y);
}

void dfsk(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
        for(int j=1;j<=14;j++){
			if(i==j || a[j]==0)continue;
			for(int k=1;k<=14;k++){
				if(i==k || j==k || a[k]==0)continue;
				a[i]-=4;
				a[j]--;
				a[k]--;
				dfsk(x-6,y+1,i);
				a[i]+=4;
				a[j]++;
				a[k]++;
			}
        }
        for(int j=1;j<=14;j++){
			if(i==j)continue;
			if(a[j]<2)continue;
            a[i]-=4;
            a[j]-=2;
            dfsk(x-6,y+1,i);
            a[i]+=4;
            a[j]+=2;
        }
	}
}
dfsj(x,y);
}

void dfsl(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
        for(int j=1;j<=13;j++){
			if(i==j || a[j]<2)continue;
			for(int k=1;k<=13;k++){
				if(i==k || j==k || a[k]<2)continue;
				a[i]-=4;
				a[j]-=2;
				a[k]-=2;
				dfsl(x-8,y+1,i);
				a[i]+=4;
				a[j]+=2;
				a[k]+=2;
			}
        }
        for(int j=1;j<=13;j++){
			if(i==j && a[j]<8)continue;
            if(a[j]<4)continue;
            a[i]-=4;
            a[j]-=4;
            dfsl(x-8,y+1,i);
			a[i]+=4;
			a[j]+=4;
        }
	}
}
dfsk(x,y);
}

int main(){
freopen("4325.in","r",stdin);
freopen("4325.out","w",stdout);
Read(test);Read(n);
while(test--){
	memset(a,0,sizeof(a));
    for(register int i=1;i<=n;i++){
		int x,y;
		Read(x);Read(y);
		if(x==0)a[14]++;
		else if(x>2)a[x-2]++;
		else a[x+11]++;
    }
	ans=n;
	dfsl(1,0);
	printf("%d\n",ans);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
9
25
2016
0

[BZOJ3578] GTY的人类基因组计划2

考虑用两个set来维护Hash值

一个维护当前有哪些房间里面有人

一个维护哪些Hash值已经被查询过了

然后直接按照操作要求一步步做就行了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,q,a[N],tx[N],siz[N];
long long Mp[N],Room[N];
set<long long> Hash;
set<int> St;
 
template<typename T>inline int Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}
 
void Read_Char(char &x){
while((x=getchar())<'A' || x>'Z');
}
 
inline int Rand_int(){return (rand()<<15)|rand();}
inline long long Rand_ll(){return ((1ll*Rand_int())<<31ll)+Rand_int();}
 
inline void Change(const int &l,const int &r){
Room[tx[l]]^=Mp[l];
siz[tx[l]]--;
if(!Hash.count(Room[tx[l]]))St.insert(tx[l]);
else St.erase(tx[l]);
tx[l]=r;
Room[tx[l]]^=Mp[l];
siz[tx[l]]++;
if(!Hash.count(Room[tx[l]]))St.insert(tx[l]);
else St.erase(tx[l]);
}
 
inline int Query(const int &l,const int &r){
int ans=0;
static set<int>::iterator I;
while(1){
    I=St.lower_bound(l);
    if(I==St.end() || *I>r)break;
    ans+=siz[*I];
    Hash.insert(Room[*I]);
    St.erase(I);
}
return ans;
}

int main(){
freopen("3578.in","r",stdin);
freopen("3578.out","w",stdout);
Read(n);Read(m);Read(q);siz[1]=n;
for(register int i=1;i<=n;i++){
    Mp[i]=Rand_ll();
    Room[1]^=Mp[i];
    tx[i]=1;
}
St.insert(1);
while(q--){
    static int l,r;
    static char chs;
    Read_Char(chs);Read(l);Read(r);
    if(chs=='C')Change(l,r);
    else printf("%d\n",Query(l,r));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
9
13
2016
0

[BZOJ3720] Gty的妹子树

我是纸张……

自以为考虑到所有的情况了,但是却在2操作后忘记给主树加边了……

55555555555555……

-----------

这题虽然可以用高明的数据结构做但是也可以用块状树写。我写的就是块状树

把树分成若干块,父节点的块大小没到要求就加到父节点的块里面去。

这样貌似会被星形的数据卡掉但是既然过了也就不管了

定义原来的树为主树

对于块和块之间连接形成的树称为辅树

加点时一定要在辅树和主树中都更新!

然后对于辅树的每个节点维护一个数据结构(我用了vector,实际上可以是treap等平衡树而且效果肯定更好)

先把本块内的数据查询完然后往下直接走整块

就行了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N=60005,block_size=200;

int n,lastans,m,en,h[N],w[N],belong[N],block_num,fa[N],bh[N];

struct Edge{int b,next;}e[N<<1];
inline void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}
inline void AddBkEg(int sa,int sb){e[++en].b=sb;e[en].next=bh[sa];bh[sa]=en;}

struct Node{
vector<int> Vx;int siz;
Node(){siz=0;}
inline void Insert(int x){if(!siz)Vx.push_back(x);else Vx.insert(upper_bound(Vx.begin(),Vx.end(),x),x);siz++;}
inline void Change(int x,int y){Vx.erase(lower_bound(Vx.begin(),Vx.end(),x));Insert(y);}
inline int Query(int x){return Vx.end()-upper_bound(Vx.begin(),Vx.end(),x);}
}block[N];

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

void dfsp(int u,int fat){
if(block[belong[fat]].siz<block_size)belong[u]=belong[fat];
else belong[u]=++block_num,AddBkEg(belong[fat],belong[u]);
block[belong[u]].Insert(w[u]);
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v==fat)continue;
	fa[v]=u;
	dfsp(v,u);
}
}

void dfsb(int u,int x){
lastans+=block[u].Query(x);
for(int i=bh[u];i;i=e[i].next)dfsb(e[i].b,x);
}

void dfss(int u,int x){
if(w[u]>x)lastans++;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
    if(v==fa[u])continue;
    if(belong[v]==belong[u])dfss(v,x);
    else dfsb(belong[v],x);
}
}

int main(){
freopen("3720.in","r",stdin);
freopen("3720.out","w",stdout);
Read(n);
for(register int i=1;i<n;i++){int u,v;Read(u);Read(v);AddEdge(u,v);AddEdge(v,u);}
for(register int i=1;i<=n;i++)Read(w[i]);
dfsp(1,0);
Read(m);
while(m--){
    int opt,u,v;
    Read(opt);Read(u);Read(v);
    u^=lastans;v^=lastans;
    if(opt==0){lastans=0;dfss(u,v);printf("%d\n",lastans);}
    if(opt==1){block[belong[u]].Change(w[u],v);w[u]=v;}
    if(opt==2){w[++n]=v;AddEdge(u,n);if(block[belong[u]].siz<block_size)belong[n]=belong[u];else belong[n]=++block_num,AddBkEg(belong[u],belong[n]);block[belong[n]].Insert(v);fa[n]=u;}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com