问题描述 LG2447 BZOJ1923 题解 显然是一个高斯消元，但是求的东西比较奇怪 发现这个方程组只关心奇偶性，于是可以用一个\(\mathrm{bitset}\)进行优化，用xor来进行消元操作。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; void read(int &x){ x=0;char ch=1;int fh; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); ...

问题描述 LG4035 BZOJ1013 题解 设答案为\((p_1,p_2,p_3,...,p_n)\) 因为是一个球体，令其半径为\(r\)，则有 \[\sum_{i=1}^{n}{(a_i-p_i)}^2={\rm dis}^2\] 拆式子可得 \[\sum_{i=1}^{n}a_i^2-2\times\sum_{i=1}^{n}{a_ip_i}=\sum_{i=1}^{n}p_i^2-{\rm dis}^2\] 于是可以构造出新的方程矩阵： \[f_{i,j}=2 \times (a_{i+1,j}-a_{i,j})\] \[f_{i,n+1}=\sum_{j...

问题描述 LG3389 题解 高斯消元，是用来解\(n\)元一次方程组的算法，时间复杂度\(O(n^3)\) 这样就构造出了这个方程组的矩阵 目标就是把这个矩阵左边\(n \times n\)消为单位矩阵 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; void read(int &x){ x=0;char ch=1;int fh; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar...

问题描述 LG4341 BZOJ2251 BZOJ需要权限号 题解 字符串的性质：一个字符串\(s\)所有的字串，等于\(s\)所有后缀的前缀。 枚举这个字符串的每一个后缀，将其插入一个\(\mathrm{Trie}\) 在插入\(\mathrm{Trie}\)的过程中可以非常方便的维护这个后缀的每个前缀。 最后从\(root\)开始对整棵\(\mathrm{Trie}\)进行一次遍历即可。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; void read(int &amp...

问题描述BZOJ1031LG4051 题解发现这是一个环，根据经验，破环为链，于是字符环变为了字符串之后对这个复制之后的字符串求后缀数组。$len$代表原字符串长度，代表复制后的字符串长度最后输出的时候，判断一下，如果$SA_i \le len$，则输出$str_i$。 Code 1 #include<bits/stdc++.h> 2 using namespace std; 3 4 #define maxn 1000007 5 6 void read(int &x){ 7 x=0;char ch=1;int fh; 8 ...

问题描述 LG2444 BZOJ2938 I \(\mathrm{AC}\)自动机 \(\mathrm{AC}\)自动机是一种多模式串匹配算法，本萌新今天刚学了它qwq 约定在构造\(\mathrm{AC}\)自动机的过程中，\(\mathrm{Trie}\)树上的边和由于\(\mathrm{AC}\)自动机中这一句： else ch[x][i]=ch[fail[x]][i]; 所新建的边为实边。 也就是\(x\)到\(ch[x][0]\)和\(ch[x][1]\)的边为实边。 II 危险！ 什么样的字符串是有病毒的？包含了某个模式串的文本串。 这样的文本串一定在...

给一开始座位表顺序中每个老师一个编号，分别为。 再根据打乱后的座位表顺序求出新的编号序列。 显然是求新编号序列中逆序对个数 可以使用归并排序或者树状数组解决。 题解区里没有树状数组，那我就发个树状数组的吧。 code #include<bits/stdc++.h> using namespace std; #define int long long template <typename Tp> void read(Tp &x){ x=0;char ch=1;int fh; while(ch!='-'&&(ch<'0'||...

快速幂运用分治思想 显然有： 每次根据该公式分治计算即可。 #include<iostream> #include<cstdio> using namespace std; long long int b,p,k,ans=1; int main() { scanf("%lld%lld%lld",&b,&p,&k); // printf("%lld^%lld mod %lld=",b,p,k); if(k==1){ puts("0"); return 0; } while(p&g...

显然每次选取两堆重量最小的最好。 主要要介绍的不是这个解法，而是几个奇奇怪怪的东西。 Heap STL中常用的堆是priority_queue（优先队列），但是STL同样支持一个奇怪的东西为heap heap有几个函数：make_heap，pop_heap，push_heap 具体用法右转百度。 向堆中压相反数 不管是priority_queue还是heap都默认大根堆，可以取的相反数压入堆，这样就不用写奇奇怪怪的比较器了。 #include<bits/stdc++.h> using namespace std; int fruit[30005],ans,a,b; in...

本题解同步发布于[本场总题解](https://www.luogu.org/blog/expect/CF580DIV2)，欢迎来踩 B - Make Product Equal One 要让个数乘积为，必须保证这个数列中只有或者，且的个数为偶数个。 考虑贪心，设代表变为的代价，代表变为的代价，优先选择小的一个，同时记录，如果选择的是，令计数器 如果为偶数，则直接输出答案 否则需要且仅需要将一个改为或将一个改为。 对升序排序，答案加上即可。 code: #include<bits/stdc++.h> using namespace std; #define maxn 100005 ...

这是一道交互题。 一共有两次询问机会，第一次询问的100个数二进制后7位下全都为1，第二次询问的100个数二进制前7位都为1. 这样无论系统返回哪个的xor值，都可以推算出这范围内的数。 code： #include<bits/stdc++.h> using namespace std; int aa,bb; int a[107],tota; int b[107],totb; int x; int main(){ for(register int i=1;i<=((1<<14)-1);i++){ if(((i&127)==12...

本题可以使用分治完成。 二维偏序 根据偏序的定义，逆序对是一个二维偏序，但这个二维偏序比较特殊： 以上两种情况都符合这个二维偏序。 三维偏序 但带修改二维偏序怎么做？ 我们将删除操作视为插入操作。 则没有没删除的插入时间为，第个被删除的，插入时间为 将插入时间作为第一维，数列位置为第二维，数值为第三维。 做三维偏序即可。 注意由于逆序对的定义，三维偏序仍是两种情况。 分治 简要介绍一下分治。 分治是一种分治算法（废话），是一个叫做陈丹琪的女选手在（记不清了）年提出的。当时提出时是用于优化一类问题的。后来分治被主要用于解决三维偏序问题。 分治思想类似于归并排序。归并排序每次将区...

洛谷博客欢迎来踩。 摘要 分块，是一种优雅的暴力，它通过对数列分段，完成对数列一些区间操作和区间查询的操作，是一种根号算法。 这篇学习笔记&题解是本萌新在学习分块过程中的一些感悟，希望能够帮助分块零基础的同学学会基础分块。 0 说明 本文中，以下变量有特定的含义： ：块的大小 ：被分块的数列的大小（长度） ：第号块的左边界 ：第号块的右边界 ：块的数量 ：第号元素所属的块 在写作时，由于本萌新的失误，只好提前在这里令与等价。 1 建块 1.1 建块需要完成的任务 在读入数据后，建块需要完成以下几个任务： 确定块的大小 确定块的数量 标记每个块的左右边界 标记每个...

问题描述 LG1393 题解 本题可以使用\(\mathrm{CDQ}\)分治完成。 二维偏序 根据偏序的定义，逆序对是一个二维偏序，但这个二维偏序比较特殊： \(i>j,a_i<a_j\) \(i<j,a_i>a_j\) 以上两种情况都符合这个二维偏序。 三维偏序 但带修改二维偏序怎么做？ 我们将删除操作视为插入操作。 则没有没删除的插入时间为\(1\)，第\(i\)个被删除的，插入时间为\(m-i+2\) 将插入时间作为第一维，数列位置为第二维，数值为第三维。 做三维偏序即可。 注意由于逆序对的定义，三维偏序仍是...