树状数组学习笔记
树状数组是什么 本质上就是一个长得像树的数组，长得很像一个二叉树，like下面的图： 我们拿它干嘛呢？我们可以拿它来单点修改，区间查询。 那就有人说：欸，那线段树功能性比树状数组多，你怎么不用线段树？ 你这么认这个功能性干嘛啊，它会把其他方面给异化掉的懂吗，知不知道什么叫异化跟具体化？ 赛场上可能同一个问题树状数组要写10min，但是线段树要30min，你说你写那个？ 怎么实现树状数组 好奇树状数组是怎么被人想出来的 lowbit 树状数组是通过这个叫lowbit的函数实现的，它主要用来求一个二进制数最低的一位111以及它后面的一堆000组成的数。 说具体点，比如说114114114这个数，它就等于(1110010)2(1110010)_2(1110010)2，那求lowbit后就会变成(10)2(10)_2(10)2，也就是2 那想要求出lowbit函数的值，我们只需要让它返回xxx andandand (−x)(-x)(−x)就可以了 结构 还是那张图片，我们把数组从前往后编号，你会发现深度相同的位置二进制下末尾0的个数是相同的！ ...
Atcoder ABC395游记
写在游记之前 啊哈！福建真好玩！今天拔灯拔得真开心，欸我的手臂怎么弯不下来了 从墩板到广惠宫全程没松手，直接彻底疯狂！！！ 耳鸣手残buff叠加！！！ Atcoder ABC395游记（A~F） A.Strictly Increasing? 题目描述 给你个序列，判断是不是单调递增。 思路 水 代码 12345678910111213141516171819#include<bits/stdc++.h>using namespace std;int main(){ int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 1; i < n; i++) { if (a[i] <= a[i - 1]) { cout << "No"; return 0; ...
Atcoder ABC394游记
fuck Atcoder ABC394游记 A.22222 题目描述 给你一个字符串，把所有非2字符删掉并输出。 思路 感觉不用讲 代码 123456789101112131415#include<bits/stdc++.h>using namespace std;int main(){ string s; int cnt = 0; cin >> s; for (int i = 0; i < s.length(); i++) { cnt += (s[i] == '2'); } while (cnt--) { cout << 2; } return 0;} B.cat 题目描述 给你NNN个字符串，把他们按照长度从小到大排序，然后从前到后拼起来，输出。 思路 感觉不用讲 代码 12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;bool cmp(const string &a1, const...
Atcoder ABC393游记
太爽了 Atcoder ABC393游记（A~F） 比赛链接 A.Poisonous Oyster 题目描述 有四个东西，编号为1 41~41 4，其中有一个有毒，如果吃了有毒的东西就会挂掉。 第一个人吃了编号为1,21,21,2的东西，第二个人吃了编号为1,31,31,3的东西。 现在给你两个字符串S1S_1S1和S2S_2S2，分别代表两个人的状态，如果是sick表示这个人挂了，如果是fine说明还活着。 问你哪个东西有毒？ 思路 没啥好说的 代码 123456789101112131415161718#include<bits/stdc++.h>using namespace std;int main(){ string s1, s2; cin >> s1 >> s2; bool c1 = (s1 == "sick"), c2 = (s2 == "sick"); if (c1 && c2) { cout << 1; } else if (c1 && !c2)...
对拍，但是构造题
对拍是什么？对拍是一种校验程序正确性的方法，通过比较两个程序的同一个测试样例的输出结果，就可以做到判断正确性。 想必各位dalao们都会对拍吧，在oi这种shabi赛制中，对拍就显得尤为重要。 但是，如果你哪天运气不好，遇到了构造题，应该怎么办呢？ 其实说的高大上，这个玩意其实不难，营养并不多，比赛的时候动动小聪明其实也能想到 ...
Tarjan算法笔记
今天是2025年2月12日，这是洛谷的占卜结果： 显然适合学习新算法，今天早上正好学了tarjan，来稍微写一写。 tarjan tarjan求SCC SCC是什么 度娘说了： 有向图强连通分量：在有向图G中，如果两个顶点ViV_iVi,VjV_jVj间（Vi>VjV_i>V_jVi>Vj）有一条从ViV_iVi到VjV_jVj的有向路径，同时还有一条从VjV_jVj到ViV_iVi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图GGG的每两个顶点都强连通，称GGG是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected...
tqq和mmm的神奇冒险
...
Atcoder ABC392游记
Atcoder ABC392游记（A~E） 比赛链接 注：这次比赛因为有事情所以没有打，都是赛后代码，特此说明。 holy shit这次比赛这么简单我怎么没打，qwq A.Shuffled Equation 题目描述 给你一个整数序列A=(A1,A2,A3)A=(A_1,A_2,A_3)A=(A1,A2,A3)。 让B=(B1,B2,B3)B=(B_1,B_2,B_3)B=(B1,B2,B3)为A的任意一个排列。 问你有没有可能B1∗B2=B3B_1*B_2=B_3B1∗B2=B3 思路 你跑一遍全排列也不是不行，不过我们简单一点可以直接从小到大排序判断就欧克了。 代码 12345678910#include<bits/stdc++.h>using namespace std;int main(){ vector<int> a(3); cin >> a[0] >> a[1] >> a[2]; sort(a.begin(), a.end()); cout...
Atcoder ABC391游记
Atcoder ABC390个人游记（A~C,E） 比赛链接 妙啊，比taqingqiu都要苗妙妙 这次比赛是不是有个印度选手用ai三分钟一道f被atcoder封了（ 乐子重开吧 话说你们是不是也不能用deepl了 A - Lucky Direction 问题陈述 您将得到一个字符串 DDD ，表示八个方向（北、东、西、南、东北、西北、东南、西南）中的一个。方向和它们的表示字符串之间的对应关系如下。 -北：‘ N ’ -东：“E” -西方：“W” -南方：“S” -东北：“NE” -西北：“NW” -东南：“SE” 西南：“SW” 打印与 DDD 表示的方向相反的字符串。问题陈述 您将得到一个字符串 DDD ，表示八个方向（北、东、西、南、东北、西北、东南、西南）中的一个。方向和它们的表示字符串之间的对应关系如下。 -北：‘ N ’ -东：“E” -西方：“W” -南方：“S” -东北：“NE” -西北：“NW” -东南：“SE” 西南：“SW” 打印与 DDD 表示的方向相反的字符串。 思路 EASY ...
想要拥有你自己的blog吗？
前言 我们在oi这条路上，总想把发生的事情记录下来。一场比赛甚至是一道有营养的题，都能给你无限的思考。这时候最好的方法当然是写下来，如果你还想让更多人看见，那写blog就是你的最优选择。 很多人认为免费地写blog只能部署在一些平台上，想在自己的域名上又怕花钱。hexo是一个基于node.js的免费、快速、多功能的个人blog模板框架，支持自定义主题和各种扩展插件，markdown和katex也都支持，还可以自动部署到github仓库。github可以把仓库里的内容形成静态网站而且可以自定义域名，全部免费！这种良心的东西，此时不用，更待何时？！ 环境配置 操作系统：windows 10/11 必备内容： nodejs 10.13以上版本且自带npm git 2.47以上版本 已经注册了的github账号 这里配置可以参考网上教程，不再过多赘述。 配置hexo 因为hexo源在国外，速度会非常慢，所以我们要切换国内镜像源再下载，打开cmd并输入这两行代码： 12npm install -g cnpm...