heyZzz's OI Blog

题目翻译： 给定 $n$ 个互不相同二元组，现在要从其中选出三个二元组，使得这三个二元组的的前一项互不相同或后一项互不相同。求有几种方案。 思路： 正难则反，先算总数：有 $\Large\frac{n \times (n-1) \times (n-2)}{6}$ 种情况。 不满足的情况是没有一个二元组与另一个二元组元素两两不相同（同一个元素）。 也就是就是一个二元组与另一个二元组元素至少一个相同（也是同一个元素）。 考虑用桶记录，$x_i$ 代表 $a_i$ 的出现个数，$y_i$ 代表 $b_i$ 的出现个数。 第一组固定，第二组有 $x_{a_i}-1$ 种，第三组有 $y_{b_i}-1$ 种。 一共有 $(x_{a_i}-1) \times (y_{b_i}-1)$。 代码楼上楼下都已经写的很明白了，我就不在赘述了。

原题传送门 题目大意： 有一个 $n \times n$ 的棋盘，$m$ 个格子是障碍物，然后移动芯片使它们返回到初始对边位置，不能经过障碍物、重叠或交换位置。问最多可以放置多少个芯片完成游戏。 思路： 本题直接按题意模拟即可： 使用桶记录障碍，$a_i$ 代表第 $i$ 行的芯片个数，同理 $b_i$ 代表第 $i$ 列的芯片个数。 如果第 $i$ 行或第 $j$ 没有芯片，$cnt+1$。 如果相遇，就是 $n$ 为奇数且中间行且列有值，$cnt-1$。 下面是样例 $3$ 的解释： 列1 列2 列3 列4 行1 无芯片 可放芯片 可放芯片 无芯片 行2 放芯片 ______ ______ 放芯片 行3 障碍物 障碍物 障碍物 可放芯片 行4 无芯片 可放芯片 可放芯片 无芯片 行2的两个芯片可以连通，$cnt=1$。 没有相遇情况，输出 $1$。 上代码： 1234567891011121314151617#include<bits/stdc++.h>using namespace std;int n,m,x,y...

回顾 kruskal： 取边权最小的一条边，若两个点在不同连通块（并查集），则连边合并。 我们把以上规则改一下： 如果点 $A$ 的老大的小弟数<点 $B$ 的老大的小弟数，$A$ 成为 $B$ 小弟。 反之，$B$ 成为 $A$ 小弟。 我们定义 $s_i$ 是点 $i$ 的老大的小弟数，$w$ 是 $a$ 到 $b$ 的边权。 贡献和为：$(s_A×s_B−1) \times (w+1)$。 代码楼上楼下都已经写的很明白了，我就不在赘述了。

翻译： 求有多少个区间内的数异或值为 $0$。 思路： 处理出前缀异或数组 $q$。 如果 $q_i=q_j$，则区间是存在的。 代码楼上楼下都已经写的很明白了，我就不在赘述了。

前言： 看到楼上楼下基本上都用三维的 dp 数组，我来介绍一种用二维的 dp 数组的做法。 思路： 我们发现，如果要采 $(a,b)$ 上的矿，那么运输路上（即 $(a,b-1),(a,b-2)…(a,1)$ 或$(a-1,b),(a-2,b)…(1,b)$）的这种矿物都要全采。 得知这一点后，我们考虑是用动归，定义 $f_{i,j}$ 为在以 $(i,j)$ 为右下角的子矩阵中的最大采矿量。 维护两个前缀和数组 $a,b$ (具体是什么见代码），$f_{i,j}=\max(f_{i-1,j}+a_{i,j},f_{i,j-1}+b_{i,j})$。 代码： 123456789101112131415161718192021#include<bits/stdc++.h>#define int long longusing namespace std;int n,m,a[505][505],b[505][505],f[505][505];signed main(){ while(1){ cin>>n>>m; if(n==0...

思路 1： 使用动态规划算法，$f_i$ 是表示喝 $i$ 瓶药的最大值。 可以得出：$f_j=\max(f_j,f_{j-1}+a_j)$。 关键代码： 1234for(int i=1;i<=n;i++) for(int j=i;j;j--) if(f[j-1]+a[i]>=0) f[j]=max(f[j],f[j-1]+a[i]); 时间复杂度：$O(n^2)$。 思路 2： 使用贪心算法+优先队列。 先拼劲全力去喝，如果在这道题中喝药喝死了，我们就要将他把药吐出来。 关键代码： 1234567for(int i=1;i<=n;i++){ sum+=f[i],q.push(-f[i]); if(sum<0){ p=q.top(),q.pop(); p=-p,sum-=p,t++; }} 时间复杂度：$O(n \log_2 n)$。

首先，我们知道 $\operatorname{lcm}(x,y) \times \gcd(x,y)=a \times b$。 之后，就可以构造了： 因为 $a$ 一定要整除 $\operatorname{lcm}(a,b)$。 再枚举 $\operatorname{lcm}(a,b)$ 的因数。 每个因数就判断一下，加入答案。 判断的代码： 1234bool check(int a){ int b=x*y/a; return !(a<l||a>r||b<l||b>r||__gcd(a,b)!=x);} 代码楼上楼下都已经写的很明白了，我就不在赘述了。

思路： 我们发现，如果要采 $(a,b)$ 上的矿，那么运输路上（即 $(a,b-1),(a,b-2)…(a,1)$ 或$(a-1,b),(a-2,b)…(1,b)$）的这种矿物都要全采。 得知这一点后，我们考虑是用动归，定义 $f_{i,j}$ 是为在以 $(i,j)$ 为右下角的子矩阵中的最大采矿量。 维护两个前缀和数组 $a,b$ (具体是什么见代码），$f_{i,j}=\max(f_{i-1,j}+a_{i,j},f_{i,j-1}+b_{i,j})$。 代码： 123456789101112131415161718192021#include<bits/stdc++.h>#define int long longusing namespace std;int n,m,a[505][505],b[505][505],f[505][505];signed main(){ while(1){ cin>>n>>m; if(n==0&&m==0) break; for(int i=1;i<=n;i...

思路： $dp_{i,j,c}$ 它表示在前 $i$ 个字符中使用了 $j$ 次更改操作。 并且最后一个字符是 $c$ 的情况下所能达到的最大美丽度。 状态转移方程： 如果 $m=s[i-1]- \texttt a $：$ dp_{i,j,m}=\max{dp_{i,j,m},dp_{i-1,j,q}+c_{q,m}}$ 如果 $m \ne s[i-1]-\texttt a$：$dp_{i,j,m}=\max{dp_{i,j,m},dp_{i-1,j-1,q}+c_{q,m}}$。 代码： 1234567891011121314151617181920212223242526#include<bits/stdc++.h>#define int long longusing namespace std;int c[26][26],dp[105][105][26],k,n,p,ans=INT_MIN;string s;char x,y;signed main() { cin>>s>>k>>n; for(int i=1;i...

题意： 把给定的区间合并成最简的形式。 思路： 可以用贪心的思想解此题： 将所有给出的区间按小值的值从小到大排序。 如果一个区间可以与上一个区间合并的，合并区间。 特判： 如一个区间为 $[-2{15},2{15}]$ 则输出 true。 如没有合法的区间（即第一个数 $>$ 第一个数）则输出 false。 输出时，省略补全的数字。 代码楼上楼下都已经写的很明白了，我就不赘述了。