Q779’s Blog

Vijos1659 河蟹王国 题解 题目链接：Vijos1659 河蟹王国 题意：维护一个数据结构，支持区间最大值查询、区间加操作 一看就线段树水题 我们在建树时将最大值搞好查询就好了 那么区间加怎么办？ 显然区间加操作会将影响到的最大值增加同一个值，而改变后的最大值在上传时进行更新即可 等于就把线段树板子搬过来改一改就过了… 因为基本原理差不多 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define R register #define INF 0x3f3f3f3f3f3f3f3f #define MAXN (int)(1e5+5) template<typename T>inline void read(R T &k) { R char ch=getchar();R T x=0,f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigi...

UVA1121 Subsequence 题解 题目链接：UVA1121 Subsequence 题意：给定数组，找最短连续子序列使其和大于 \(S\) ，多组数据 解法一 对于区间 \([l,r]\) ，若 \(\sum_{i=l}^{r}a[i]\ge S\) ，那么 \(\forall r'>r (r' \le n)\) 该条件均成立 那么我们只要枚举左端点，二分查找满足条件的最左的右端点，然后找个最小值就行了 区间和用前缀和优化即可 时间复杂度 \(O(n\log n)\) 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define R register #define MAXN (int)(1e5+5) #define INF 0x3f3f3f3f3f3f3f3f int n,k; int sum[MAXN]; void proc() { R int mn=INF; for(R int l=1; sum[l]+k<=su...

ubuntu 无法连接至ibus 解决方法 在终端中输入以下指令 ibus-daemon -r -d -x 大概的意思就是把原来的进程杀掉然后启动ibus 然后ibus它就回来了 这篇文章好短啊（

洛谷P1006 [NOIP2008 提高组] 传纸条 题目链接：P1006 [NOIP2008 提高组] 传纸条 题意：网格图， \((1,1)\) 到 \((n,m)\) 找两条不重合的路径，最大价值 注：原题是 \((m,n)\) ，但我不习惯，所以就用 \((n,m)\) 替代（即 \(n\) 行 \(m\) 列）！ 解法一 最烂解法 ，但是能通过此题 设 \(dp[i][j][k][l]\) 表示第一条路径到 \((i,j)\) 的位置，第二条路径到 \((k,l)\) 的位置，能获得的最大价值 由于两条路径正着走反着走都一样，所以我们可以看作从 \((1,1)\) 到 \((n,m)\) 的两条不重合的路径 那么显然 \(dp[i][j][k][l] = \\ \max\{dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]\}+a[i][j]+a[k][l]\) 因为不重复，所以当 \(i=k,j=l\) 时要减去 \(a[i][j]\) 时间复杂度 \(O(n^4)...

UVA10006 Carmichael Numbers 题目链接：UVA10006 Carmichael Numbers 题意：若 \(\forall x (1<x<n) ,x^n\equiv x \mod n\) ，且 \(n\) 为合数，则称 \(n\) 为Carmichael Numbers，多组数据判断 \(n\) 是否是这种数 数据范围 \(2<n<65000\) 合数好处理，直接 \(O(\sqrt{n})\) 暴力判断即可 那么 \(x^n\) 怎么处理呢？ 如果我们去一个一个乘，时间复杂度 \(O(n^2)\) ，直接TLE 因此，我们要用到快速幂 对于 \(x^k\) ，根据整数的唯一分解定理和常识，\(k\) 可以写成唯一的二进制形式 则 \(x^k\) 可以被分解为它二进制位上每一个 \(1\) 的幂的乘积 例如： \(x^{(5)_{10}} = x^{(101)_2} = x^{(100)_2} \times x^{(1)_2} = x^{(4)_{10}} \times x^{(1)_{10}}\) 那么我们只需要把 \(k...

note[0] 某个学MO的朋友给我看的题 这题似乎是1994年国家数学集训队选拔考试D1T1 怪不得我做了好久（ upd.20220513 害，他半途而废退役了 题面： 求四个所有的由四个自然数 \(a,b,c,d\) 组成的数组，使数组中任意三个数的乘积除以剩下的一个数余数为 \(1\) 题解： （注：我写的可能有点不太正式，毕竟我只是个OIer） 由题意可得 \(abc \equiv 1 \mod d\) \(abd \equiv 1 \mod c\) \(acd \equiv 1 \mod b\) \(bcd \equiv 1 \mod a\) 可化为 \(d\mid (abc-1)\) \(c\mid (abd-1)\) \(b\mid (acd-1)\) \(a\mid (bcd-1)\) \(\therefore ab\mid (acd-1)(bcd-1) \Rightarrow ab\mid (abc^2d^2-acd-bcd+1)\) \(\therefore ab\mid (acd+bcd-1)\) 同理 \(cd\mid (abc+abd-1)\) \(\...

洛谷P4878 [USACO05DEC]Layout G 题解 题目链接：P4878 [USACO05DEC]Layout G 题意：按编号排了 \(n\) 只奶牛，有的奶牛间必须相距小于等于一个距离，有的奶牛间必须相距大于等于一个距离，问 \(1\) 到 \(n\) 的距离最大值 我们可以发现题目给的数据本质上就是 \(v-u\ge d_i\) 或 \(v-u \le d_i\) 这是什么？差分约束！ 差分约束：根据三角不等式 \(d_u + w(u,v) \ge d_v\) 的构成，我们可以把形如 \(v-u\ge d_i\) 的不等式转化为 \(v-d_i\ge u\) （可以看作 \(v\) 向 \(u\) 连了一条边权为 \(-d_i\) 的有向边），同理 \(v-u \le d_i\) 转化为 \(u+d_i \ge v\) 这里不过多讲解差分约束了 那么为什么差分约束后求最短路就是最大值呢？ 因为求最短路是由无穷大向下不断约束得到的，因此得到的是最大值（同理求最长路就是最小值） 那我们只要按题意建图就行了 要注意的是，每个奶牛 \(i\) 满足 \(d_{i-1...

POJ3723 Conscription 题解 题目链接：POJ3723 Conscription 题意：要招 \(n\) 个女的， \(m\) 个男的，原价 \(10000\)，如果招了关系亲密的（男女）人可以降价，求最小花费 首先，题目给出的格式 \(x_i\ y_i\ d_i\) 很像图论题 我们可以把每个人看作一个结点，为了防止男女编号相同的人搞混了，我们可以让女的编号为 \(1 \sim n\) ，男的编号为 \(n+1 \sim m\) ，显然这题要我们选出所有的结点且花费最小 我们可以发现答案如果存在环则会产生矛盾，例如：a招了b，b招了c，c招了a，这说不通 那是最小生成树吗？不一定 我们可以发现给定的这张图不一定是连通图，而我们要求的是花费最小的树型结构（感性理解下），那么这就是最大权森林问题，同样可以用最小生成树来求解（注：边权设为 \(-d_i\)） 由于不一定是树，所以不需要记录连了多少边 代码如下 #include <cstdio> #include <vector> #include <iostream> #include <...

洛谷P2865 [USACO06NOV]Roadblocks G 题解 题目链接：P2865 [USACO06NOV]Roadblocks G 题意：求结点 \(1\) 到结点 \(n\) 的次短路，所有边有非负权重，边可以重复经过，无向图 如果是求最短路，那么一个dijkstra直接搞定 但是这题要求的是次短路，同样也可以dijkstra解决 我们观察 \(1\) 到 \(v\) 的一条次短路 \(p\) 要么存在 \(1\) 到 \(u\) 的一条最短路 \(k_1\) ，使得 \(k_1\) 加上 \((u,v)\) 等于 \(p\) 要么存在 \(1\) 到 \(u\) 的一条次短路 \(k_2\) ，使得 \(k_2\) 加上 \((u,v)\) 等于 \(p\) 因此我们只需要记录每个结点的最短距离和次短距离即可 （注：由于最短路径可能有多条，但是并不影响结果，因此我们假设只有一条路径） 由于每个结点都可以访问多次，那么怎么防止死循环呢？ 显然对于一个结点，如果在我们的优先队列中将它取出时，我们只要判断它的距离是否大于它的结点的次短距离，如果大于，一定不是次短路 ...

洛谷P1581 A+B Problem（升级版）题解 题目链接：P1581 A+B Problem（升级版） 题意：每一位进制不同，第一位进制为 \(2\) ，第二位进制为 \(3\) ，第 \(i\) 位进制为第 \(i\) 个质数，求A+B 本题就是以普通的高精度加法为基础，改了一下进位的方式而已 这里我用的vector<int>写的高精度 我们可以把每一位的进制打个表，在进位的时候取模就行了 代码如下 #include<bits/stdc++.h> using namespace std; #define int long long #define R register int mod[]={2,3,5,7,11,13,17,19,22}; int t,f=0,len1,len2; vector<int> num1,num2; char ch; signed main() { while(~scanf("%lld%c",&t,&ch)) { if(!f)num...

洛谷P1047 [NOIP2005 普及组] 校门外的树 题解 前言 如何把一道入门题写成省选题？（手动滑稽） 本题解是我在练习分块时突发奇想写的，真就把入门题写成省选题的感觉（ 才发现原来这些简单题这么有趣（ 题目链接： P1047 [NOIP2005 普及组] 校门外的树 题意：马路上砍树，问砍了 \(m\) 次还有几棵树 一、模拟解法（正常解法） 我们只要把每次砍掉的树标记一下，最后统计未标记的数量即可 注意下标从 \(0\) 开始，共 \(n+1\) 个数 代码如下： #include <bits/stdc++.h> using namespace std; #define int long long #define R register #define MAXN (int)(1e4+5) int n,m,ans; bool a[MAXN]; signed main() { scanf("%lld%lld",&n,&m); for(R int i=1,l,r; i<=m; i++) { scanf("%lld...

浅谈珂朵莉树(ODT) 前言 珂学家狂喜（ 一、珂朵莉树来源 珂朵莉树，原名老司机树（Old Driver Tree），在某场CF比赛中提出 因为题目背景是《末日时在做什么？有没有空？可以来拯救吗？》中的珂朵莉，所以就叫珂朵莉树了 二、珂朵莉树 题目链接：CF896C Willem, Chtholly and Seniorious 题目要求维护一种数据结构，支持以下操作 将 \([l,r]\) 区间内所有数加上 \(x\) 将 \([l,r]\) 区间内所有数改成 \(x\) 求 \([l,r]\) 区间第 \(k\) 小的数 求 \([l,r]\) 区间内所有数的 \(x\) 次方的和取模 \(y\) 值得注意的是，数据为随机数据，说明没有故意构造卡的数据 1.珂朵莉树有什么用？ 最主要的就是区间内的推平操作了，即本题中的操作 \(2\) 当然还有别的操作，那就不是最主要的了 2.原理是什么？ 写在前面：这个数据结构唯一前置知识就只有set a.存储 我们可以把区间看作若干个结点，每个结点都有自己的左端点 \(l\) 、右端点 \(r\) 以及值 \(v\) 显然，一开...