【LGR-174-Div.2】T2、T3
T2 陌路寻诗礼题目描述帆巨所在的家乡的地图是一张有 $n$ 个节点 $m$ 条有向道路的有向图,每个节点都是一个城市,而帆巨所在的城市是 $1$ 号城市,并且 $1$ 号城市总是可以通过若干道路到达其他任何城市。第 $i$ 条道路从 $x_i$ 号城市出发到达 $y_i$ 号城市,长度为 $z_i$。帆帆现在要从他的 $1$ 号城市前往各个城市面基。精通 spfa 算法的帆帆在面基的过程中自然会按照长度和最短的路径去其他城市。但是帆帆有选择困难症,他希望从 $1$ 号城市到达每一座城市的最短路径都是唯一的,所以他决定施加魔法,改变所有道路的长度,具体地:帆巨施加魔法后,对于每一条道路的长度,都可以 独立地 将其变成一个 $[1,k]$ 范围内的整数,其中 $k$ 是帆巨的魔法等级。但帆巨所在的世界的地图和他的魔法等级一直在变,总共会变 $T$ 次,所以他希望你对 $T$ 次询问都给出一种构造方法使得帆巨不会纠结或者报告无解。
输入格式第一行一个整数 $T$ 表示数据组数。接下来 $T$ 组,每组先是三个整数 $n,m,k$,接着 $m$ 行描述有向道路 $(x_i,y_i)$。不保证 ...
ICPC2023 HangZhou R 签到+铜牌题
The 2nd Universal Cup. Stage 22: Hangzhou结束了,所以可以把题解扔出来了。
题面:
V-Diagram长度为 $n$ 的 $1$ -索引整数序列 $a$ 是V-图,如果 $n \ge 3$ 且存在满足以下条件的索引 $i$ ( $1< i < n$ ):
$a_j > a_{j + 1}$ 用于 $1 \le j < i$
$a_j > a_{j - 1}$ 为 $i <j \le n$ 。
给定V-图 $a$ ,找出具有最大可能平均值的V-图 $b$ ,使得 $b$ 是 $a$ 的连续子序列。序列的连续子序列可以通过从序列的开头和结尾移除一些(可能为零)元素来获得。签到题,题解说二分答案也行,但我做的时候用的是贪心。因为对于一个V图来讲,首先一定要包含最小的那个点,然后就是向左右两边扩展取最大。要求在现行复杂度内通过,所以不能直接暴力解,那么观察性质,由于保证是V图所以这个序列对应的图像的每一段的斜率都大于1,换句话说就是i每次改变1(增加一个数),纵坐标ai变化量至少大于 ...
01字典树
用于接近线性的查询异或相关的问题,如异或前缀和,和别的数的最大异或和等。01字典树是按照二进制下每一位是0还是1将一些数进行分类,每一个结点的左孩子表示当前这一位是0的所有数,右孩子表示当前这一位是1的所有数,这样递归的分下去总可以把所有的数分类完。
如要求每次线性的回答一个数和一个数组中的所有元素的最大异或值,数组范围是2e5:将数组中的所有数类似于哈夫曼树一样·按位建成一棵树,如3(0011),8(1000),5(0101)那么就可以画出一个这样的树:
12345678910 root / \ 0 1 / \ / 0 1 0 \ / / 1 0 0 \ \ / 1 1 0 (3)(5)(8)
那么比如查询这些数和6(0110)异或后的最大值,想要异或完最大,那么就要求每一位都不一样,因为位数越高那么占得权值就越大,所以从前往后贪心,如果树在这个位上有不一样的分支那就往这条分支上走。6的第一位是0,那么要找第一位是1的,查询的时候要选右边的节点,所 ...
根号分治
用来处理一些根号范围以内复杂度高(打表),根号范围以外复杂度低(枚举)的一种暴力思想,一般能做到$O(n\sqrt n)$的复杂度,大多数都是多组数据询问。
P3396 哈希冲突一个长度为n 的序列和m个操作,每次操作可以以下二选一:1 询问下标模x后为y的所有数之和2 修改第x个数n≤150000,m≤150000,元素范围是[1,1000]的整数暴力做法是直接枚举,比如模2后为1的有1,3,5,7…,模10后为1的有11,21,31,41,51…可以发现对于长度为n的,模x后为y的数大概有$\left \lfloor \frac{n}{x} \right \rfloor$个,当x越大那么这个数越小,所以模数越大的可以考虑直接暴力枚举而不会超时,那么问题在于如何处理模数小的询问,当模数小的时候因为余数的范围变小了所以考虑直接先打表预处理出所有的情况,令sum[i][j]表示n个数中下标模i后为j的所有的数的总和,那么可以在O(np)的复杂度内预处理出所有情况,其中p为指定的最大的模数,同时修改也很简单,单次修改的复杂度是O(p):
1234567// 预处理for (int j = ...
hexo+github个人网站开发
23年暑假学git的时候偶然发现github可以托管像hexo这种无后端的博客框架,参考了这个视频BV1st411r7Sj自己搓了个博客。有些东西长久不用就忘记了,写个文档记录一些常用的操作
图片上传像语雀这种存在防盗链机制的文章即使导出的是Markdown格式图片在博客上也是不能显示的,一种简单的方法是在语雀端插入图片的时候不要直接插入,这样图片是放在语雀图床里面的,可以放在别的图床比如https://sm.ms/home/等并将其用图床外链放到语雀写作端就没有问题因为图片并没有存在语雀图床里面。还有一种就是开超级会员获取token,这样就可以不用将语雀上的内容导出就可以在博客上显示。
将博客托管至GitHub参考0成本使用Hexo框架搭建个人博客并托管至Github-Pages/#将博客托管至GitHub
1234cd xxxx.github.iogit add --allgit commit -m "message"git push
pdf文件的插入参考hexo post中pdf文件的插入,下载依赖的时候如果网络原因报错可以加镜像源,参考解决npm下载慢慢慢 ...
关于Linux(Ubuntu)
之前打ICPC用的wf镜像,不适应ubuntu系统的各种操作,其实队伍里面只有我不会。本文记录一些日常使用ubuntu中遇到的一些问题,以后如果上相关的选修课也可以用用
安装软件一些软件给linux系统提供了好几种版本,比如X86,ARM,LoogArch、MIPS等,这四种版本的区别:X86(或x86_64): 适用于大多数个人计算机和服务器的标准桌面和服务器硬件,通常是Intel或AMD处理器。ARM: 适用于基于ARM架构的设备,如某些嵌入式系统、智能手机、平板电脑等。loongArch(龙芯架构): 龙芯是中国的一个处理器架构,适用于支持龙芯架构的硬件。MIPS: 适用于MIPS架构的硬件,这种架构在嵌入式系统和某些网络设备中较为常见。
1234查看ubuntu系统的版本信息lsb_release -a查看硬件架构uname -m
选了架构之后,下载的软件包又分为三种:三个不同的包格式(.rpm、.deb、AppImage)在Linux中用于软件管理,它们有一些基本的区别:.rpm(Red Hat Package Manager): 主要用于基于Red Hat的发行版,如Fe ...
2023ICPC杭州站打铁游记
由于杭州站题目将用作UCup Stage Hangzhou,博客会在24年2月之后再发题解本身就是蒟蒻,本来也没想能有多好的成绩就看能不能拿到铜牌,结果不出意外的打铁了。只能说菜就多练确实技不如人,不过也正常没打过铁都不好意思说自己参加过ICPC。day-1周五下午出发,相比回家而言杭州很快就到了唯一难受的是东站离杭师大太远了乘地铁站了半天才到定的公寓,中途还发现因为比赛用的是Ubuntu系统win下的对拍程序还用不了,晚上临时整了个简陋的linux对拍器,手抄代码准备明天热身赛测试。day0早上七点多起床,去杭师大吃早饭结果精准踩雷吃到了逆天菜包,馅是豆腐+辣椒而且馅还少吃一半实在咽不下去就倒掉了,然后感觉自己又饿又想吐。走到叔同剧场签完到领了队服拍了合照,顺便吐槽了这队服颜色感觉像送外卖的(一黄一蓝的简称美团大战饿了么)。下午2.30开热身赛,开了两题看了眼排名感觉还可以过了铜牌线(当然很多大佬熟悉比赛环境了就懒得打所以排名会靠前一些)。自我感觉明天可以手速铜因为看很多人也是第一次参赛。测试完对拍代码然后润回公寓睡觉了。回到公寓看见群里在发热身赛直播录像,然后发现自己正对着摄像头, ...
ICPC2021 Nanjing R 签到+铜牌题
补题链接:https://codeforces.com/gym/103470或https://www.luogu.com.cn/contest/143839
A.Oops, It’s Yesterday Twice Moren*m的矩阵里面每个格子都有一个袋鼠你可以通过在键盘上按下U、D、L、R按钮来控制袋鼠。袋鼠将根据您按下的按钮同时移动。具体而言,对于位于第i行和第j列的单元格,用(i,j)表示:
按钮U:如果i > 1,则它将移动到(i - 1,j)。否则,它将保持在相同的网格中。
按钮D:如果i < n,则它将移动到(i + 1,j)。否则,它将保持在相同的网格中。
按钮L:如果j > 1,则它将移动到(i,j - 1)。否则,它将保持在相同的网格中。
按钮R:如果j < n,则它将移动到(i,j + 1)。否则,它将保持在相同的网格中。
您需要构建一个仅由字符‘U’、‘D’、‘L’和‘R’组成的操作序列。应用该序列后,您必须确保每只袋鼠都聚集在特定的单元格(a,b)。操作序列的长度不能超过3(n - 1)。
签到题,想到可以在等于2(n-1)的步数 ...
19thZJCPC
补题链接
B. JB Loves Comma 给定字符串 S,在每个 “cjb” 子串后面添加一个逗号 ,就一签到题没什么难度12345678910111213141516171819202122232425262728#include <bits/stdc++.h>#define endl '\n'//#define int long long//#define N 105using namespace std;void solve() { string s ; cin >> s ; for (int i = 0 ; i < (int)s.size() ; i++) { cout << s[i] ; if (i >= 2 && s.substr(i - 2, 3) == "cjb") { cout << "," ; } }}signed main() { cin.tie( ...
缺省源
1234567891011121314151617181920212223242526272829#include <bits/stdc++.h>//#define endl '\n'//#define int long long//#define N 1003#define fi first#define se second#define si(x) (int)(x.size())#define all(x) x.begin(),x.end()#define debug cout<<"*******\n";using namespace std;typedef pair<int, int> PII;void solve() { }signed main() { cin.tie(nullptr), cout.tie(nullptr); ios::sync_with_stdio(false); cout.precision(10); cout << fixed; int ...