Yan2u's Blog

题目限制一览 题目 时间限制 空间限制 1. door 1000 MS 128 MB 2. escape 1000 MS 128 MB 3. graze 3000 MS 128 MB 1. 门卫（door.cpp）Description红美玲是红魔馆的门卫。最近红魔馆安保系统使用了新型的数据编码技术base64，可以 将数据转化为大小写字母、数字和+、/、=组成的字符串，具体方法如下： 首先将输入字符三个三个分为一组：如果没有剩余（即字符串长度为3的倍数），则直接调用主过程（见下方描述）；如果剩1个，则加两个“\0”字符（ASCII码为0），使总长度变为3的倍数，调用主过程，并且将主过程转化后的字符串最后两个字符改为“==”；如果剩2个，则加一个“\0”字符，使总长度变为3的倍数，调用主过程，并且将主过程转化后的字符串最后一个字符改为“=”。 主过程：输入一个长度为3k的字符串，输出一个长度为4k的字符串。（k为非负整数。）循环以下过程n次,每次转换三个字符成为四个字符，循环n次转换出的字符串连接起来，即为最终的字符串。 每次将三个字符转化成asc ...

前言上次的项目 LRCEditor 告一段落之后，最近又想到对其进行优化，其实也就是添加一个常用的功能：在线搜索歌词 在 LRCEditor 中的 “帮助” 选项里面有提到如何在网易云音乐的在线界面利用开发者模式获取歌词文件和翻译，但是此方法操作起来会有一定难度，不利于将来准备做的 MusicPlayer 的功能集成，因此想到通过程序自己访问网络获取歌词并显示 在我们平常浏览的播放器网页里面，通常都可以看到歌词，歌曲名称，作者信息和封面信息等等，然而要让程序从网页中像人一样提取出这些信息无疑是非常难的，如何让这些信息以程序能够理解或者解析的格式直接呈现呢，这就要依网页API来实现了 实现（获取歌词）Step1使用网易云提供的 API，根据给定的歌曲名称（设为 Faded）搜索相应信息：http://music.163.com/api/search/get?s=Faded&limit=20&type=1&offset=0 ，必需参数说明： http://music.163.com/api/search/get API接口网址 s：歌曲名称，中文要进行字符编码 ...

题目限制一览 题目 时间限制 空间限制 1. agent 1000 MS 512 MB 2. earth 1000 MS 512 MB 3. aurora 1000 MS 512 MB 1. 彩虹（rainbow.cpp）Description探险队员们跟随两位护法来到了七色虹前。七色虹，就是平面直角坐标系中赤橙黄绿青蓝紫七个半圆，第i座(1<=i<=7)半圆形彩虹的圆心是(xi,0)，半径是ri，半圆上所有点的纵坐标均为非负数。探险队员可以看做一条竖直的、长度等于身高的线段，线段的底端纵坐标为0，最高的一位探险队员的身高为h。 现在探险队员们要从(0,0)到达(x0,0)，穿越彩虹的过程中，探险队员的整个身体必须始终在至少一个半圆形彩虹的内部。由于彩虹的半径ri可能太小了，不足以满足这个条件，因此两位护法决定帮助他们把所有彩虹的半径都增大一个非负实数r。探险队员们想知道，r最小是多少呢？ Input第一行两个实数 h、x0,表示身高和目的地横坐标。 接下来七行每行两个实数 xi、ri,表示七座半圆形彩虹的圆心和半径。 Output输出最小的 ...

珂朵莉树：学习笔记老司机树，ODT(Old Driver Tree)，又名珂朵莉树（Chtholly Tree)。 起源自 CF896C 。因为这是第一道以此树 AC 的题，又是关于动漫角色 珂朵莉 的，故因此得名。 是一种非常暴力的数据结构，时间复杂度不好计算，且取决于数据的随机性，珂朵莉树可以用于带有区间覆盖的问题当中，且当覆盖操作比较多的时候，它能发挥出一定优势，所以珂朵莉树通常用于写不出正统解法时的骗分选择 要保证珂朵莉树的复杂度正确，数据必须随机（也就是出题人不会特意卡），证明 在很多题目中不是正统的解法，但是有些时候却比正统的解法跑得更快…… 核心思想珂朵莉树的核心思想是：把值相同的区间合并成一个结点保存在 set 里面。 因此一个树节点只包含三个信息：左右端点 $L,R$ ，和区间值 $v$，定义时注意值 $v$ 要用 mutable 修饰 12345678struct node{ int L,R; mutable int v; node(int x, int y=-1, int z=0):L(x), R(y), v(z) {
...

整体二分在信息学竞赛中，有一部分题可以使用二分的办法来解决。但是当这种题目有多次询问且每次询问我们对每个查询都直接二分，可能会收获一个 TLE。这时候我们就会用到整体二分。整体二分的主体思路就是把多个查询一起解决，所以这是一个离线算法（摘自 OI Wiki） 适用性可以使用整体二分法解决的问题具有如下性质： 询问的答案具有可二分性 修改对判定答案的贡献互相独立 ，修改之间互不影响效果 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值 贡献满足交换律，结合律，具有可加性 题目允许使用离线算法（显然） 思路或模板一般的二分是对连续某次操作下（操作数为 $mid$ 的操作）进行判定，根据判定结果修改答案值域，值域不断缩小，逼近正确答案的过程，可以看出一般的二分仅对一个询问起作用 而整体二分可以处理一坨询问，自然需要一个存储询问结果的数组，由于一次猜的答案需要拿去同时与多个询问进行判定，整体二分的大致思路如下： 确定处理询问的区间：$[x,\;y]$（即处理第 $x$ 个到第 $y$ 个询问），确定答案值域：$[L,\;R]$ （二分的灵魂） 首先，若进行到 $L ...

题目限制一览 题目 时间限制 空间限制 1. agent 1000 MS 256 MB 2. earth 1000 MS 256 MB 3. aurora 2000 MS 512 MB 1. 特工（agent.cpp）DescriptionIMF(不可能任务小组)有N个Agent，每个Agent的能力值互不相同，现在部长先生想要派出A,B两队Agent去参加特别任务。但是参加大战的两个队伍要满足两个要求： 1. A队中能力最大的Agent的能力值要小于B队能力最弱的Agent的能力值。 2. A,B两队都要有人参加。 并不是所有的Agent都要去参加的，心急的部长先生想知道有多少种安排Agent的方案。由于答案可能很大，所以只需要你求出答案模 $10^9+7$ 的值就可以了。 Input输入仅一行，为一个整数 N Output输出一行一个整数，为方案数模 $10^9+7$ 的值 Sample Input #113 Sample Output #115 Sample Input #216 Sample Output #21129 Hint对于20%的数据 ...

暑期刷题太无聊？来试一下这款弱智小游戏：2048 ！ 参考了网络上经典的 2048 玩法，附加 8×8，16×16 玩法，历时 2 天赶工完成的 2048 小游戏！ 附1：下载链接（解压后，A2048.exe 就是游戏文件，注意 images 文件夹不能丢！） https://github.com/Yan2u/A-2048 附2：比较简陋的游戏界面截图

Polya 定理Redfield-Polya （Pólya enumeration theorem，简称PET）定理是组合数学理论中最重要的定理之一。 其提出者波里亚在众多数学的分支：函数论、变分学、概率论、数论、组合数学以及计算数学和应用数学领域中，都颇有建树，他共发表了200多篇著名论文，以他的名字命名的Polya计数定理，则是近代组合数学的重要工具。波里亚还是杰出的数学教育家，有著丰富的数学教育思想和精湛的数学教学艺术，他对数学思维一般规律的研究，堪称是对人类思想宝库的特殊贡献。 Polya 定理可以用于解决关于集合互异状态的计数问题，是解决此类问题的简洁高效的一个工具 例题引入描述把一个 $2\times 2$ 的方格棋盘用黑白两色涂色，规定经过旋转重合的图案是一种图案，问能涂出多少种不同的图案？ 分析不考虑旋转，所有涂色方案如下图： 可以发现图中共有 16 种涂色方案，但是把经过旋转的 $\begin{Bmatrix} 1&2&3&4 \end{Bmatrix}$，$\begin{Bmatrix} 5&6&7&8 \end{ ...

前言对拍是帮助我们检验算法正确性（或者帮助我们死了用高级算法的心）的极其有效的方式，最近上网查了查对拍器的写法和检验器的写法，放一个比较花哨的对拍与检验器在这，有改进意见的 DALAO 们也可以提出来~ 在开始之前，可能需要了解以下东西： 整个对拍器并没有使用 freopen ，并且在对拍器头文件（以下有说明）里也不允许使用 freopen，因为对拍程序会频繁的在控制台和文件输入输出流之间切换，所以我采用的是 ifstream 和 ofstream ifstream 和 ofstream 是对应输入输出流的数据类型，头文件为 include <fstream>，实例化以后可以用类似 cin 和 cout 的形式往文件里面输入内容或从文件里面读取内容，写入和读取的机制也和 cin 和 cout 相似，例如，往 TEST.txt 写入内容 Hello World! 123ofstream ofile;ofile.open("TEST.txt");ofile<<"Hello World!"; 由于在随机数生成时不需要用到 ...

题目限制一览 题目 时间限制 空间限制 1. traffic $1000$ MS $128$ MB 2. paint $1000$ MS $512$ MB 3. airline $1000$ MS $128$ MB 1. 车流量（traffic.cpp）Description工人打算用一组传感器测量公路上的车流量，每个传感器被用来测量一小段路面上的车流量的数值。不幸的是，某一天装有传感器的盒子进了水，之后它们就不能精确的测量了。现在每个传感器只能输出一个可能结果的范围。例如，一个传感器可能会给出范围[7,13]，表示在这段路面上的车流量不小于7，并且不大于13。 高速路要测量的这一段长N英里，当然高速路都是单向的，从第1英里驶向第N英里。工人想要安装N个传感器——每个监测1英里长的路段。在其中某些路段上，有能够使得车辆进入高速公路的上匝道，在这样的路段上，工人会将传感器装在上匝道上，测量流入的车流量。在某些路段上有能够使得车辆离开高速公路的下匝道，在这样的路段上，工人会将传感器装在下匝道上。每一个路段包含至多一个匝道。如果在公路的一个路段上没有上匝道或下 ...