heyZzz's OI Blog

线性 DP。 不难想到 $dp_{i,j}$ 代表在 $a$ 中前 $i$ 个数和 $b$ 中前 $j$ 个数满足要求。 状态转移方程是： 边界： 如果 $i=m$，$dp_{i,j+1}=\min{dp_{i,j}}$。 如果 $j=n$，$dp_{i+1,j}=\min{dp_{i,j}}$。 之后： $a_{i+1}=b_{j+1}$ 或者 $a_{i+1}=1$ 或者 $b_{j+1}=1$，$dp_{i+1,j+1}=\min{dp_{i,j}}$。 最后 $dp_{i+1,j}=\min{dp_{i,j}+1},dp_{i,j+1}=\min{dp_{i,j}+1}$。 代码楼上楼下都已经写的很明白了，我就不在赘述了。

思路： 使用二分答案。 二分答案分为两部分：check 函数和二分。 二分楼上楼下都讲的很清楚了。 本题解只讲 check 函数。 首先： 先给 $a,b$ 数组排序。 总共有 $\Large \frac{a_i}{b_j}$ $>$ $\Large \frac{a_i}{b_{j+1}}$ 和 $\Large \frac{a_i}{b_j}$ $<$ $\Large \frac{a_i+1}{b_{j}}$。 最后双指针维护即可。 下放部分代码： 1234567bool check(double k){ int j=0,sum=0; for(int i=1;i<=n;i++){ while(a[j+1]<k*b[i]&&j<n)j++; sum+=j; }return sum>=q;}

思路： 注意到树有这样的性质：每个点的度数和为 $2(n−1)$。 于是我们给每个点 $1$ 的度数，然后分配剩下的 $2(n-1)-n=n-2$ 个数。 之后用贪心算法，对当前最优的点进行操作，对答案的为 $a(2d+1)$。 维护一个优先队列，存入 $a(2d+1)$。 每次取出堆顶，最后将每一个点的累加即可。 代码楼上楼下都已经写的很明白了，我就不赘述了。

比较烦的中模拟。 注意事项： 猎人死时必须带走一个人。 女巫只有一份毒药和解药。 在同一晚，同一位女巫只能做一次操作。 如果错误撤回当晚所有操作。 操作： 我们维护十个数组： $die$，所有死亡的记录。 $nw1$，女巫的毒药操作。 $nw2$，女巫的解药操作。 $nd$，当晚死亡人数。 $nnw$，当晚女巫的操作。 $lr$，当晚狼人的操作。 $er$，猎人带走的操作。 $die1$，$die$ 的副本。 $nw1_1$，$nw1$ 的副本。 $nw2_1$，$nw2$ 的副本。 然后，几个 $\texttt {if}$ 判断一下： 判断是否出界。 判断是否死亡。 如果是猎人或女巫，要判断是否当晚死亡。 如果是狼人或女巫，要判断是否当晚用。 接着，记录死亡，是否用技能： 12345678910111213141516if(op==0){ //狼人 if(a[x]==1&&!die[x]&&!die[y]&&!lr[x]&&x<=n&&x&&y<...

并查集板子。 思路 一条边如果没有我们所关注的点，可以直接不管，因为这些边不会影响我们需要的点。直接丢到并查集里维护即可。 剩下的边贪心，能加的都要加。 代码解释 首先，$u_i>k$ 且 $v_i>k$ 的边一定要选，用并查集维护即可。 12345for(int i=1;i<=m;i++){ cin>>u[i]>>v[i]; if(u[i]>v[i]) swap(u[i],v[i]); if(u[i]>k&&v[i]>k) f[fd(u[i])]=fd(v[i]);} 然后，剩下 $u_i \le k$ 或 $v_i \le k$ 的边看情况选： 如果他们不在一个集合里（不会出现简单环），选并合并。 如果他们在一个集合里，不选并计入答案。 123456for(int i=1;i<=m;i++){ if(u[i]<=k||v[i]<=k){ if(fd(u[i])!=fd(v[i])) f[fd(u[i])...

题目就是求 $s$ 是否可以一笔画。 像这样（样例）： 12BWBBWBBBBBBB 走法： 123B W B--B W B| | | |B--B--B B--B--B 我们发现如果上面或下面没有走过且可以走，是一定要走。 如果上面或下面都走过了，就向后走。 另外形如： 12BBBW 就要特判是开始是第一行还是第二行，我的做法是都枚举一遍。 最后放上超长代码： 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include<bits/stdc++.h>#define int long longusing namespace std;int T,n,fg,as,x,y,vis[200005][2]; char s[200005][2];signed main(){ cin>>T; while(T--){ cin>>n,fg=as=0; for(int...

题意 给定两个排列 $p$ 和 $d$，第 $1 \le i \le n$ 次将 $p_{d_i}$ 设为 0。 然后进行操作，一次操作定义为指定一个 $i$，将 $a_i = i$，问最少多少次操作能将它复原为一个排列（可能与原排列相同）。 思路 我一看，每次 $p_{i}$ 一定要做一次操作 $p_i=i$，那么 $p_{p_i}$ 也要操作，以此类推，直到 $p_k$ 等于 $k$。 那就好办了，每次讲 $p_i$ 和 $i$ 连在一起，分成几个联通块，每次的答案就是联通块的大小。 code 123456789101112131415161718192021222324#include<bits/stdc++.h>#define int long longusing namespace std;int T,n,p[100005],d[100005],f[100005],sz[100005],fg[100005],ans;int fd(int x){ if(f[x]==x) return x; return f[x]=fd(f[x]);&#...

题意： 给定一个没有任何三个及以上的对角线交于一点的凸多边形。 问对角线交点个数。 思路： 我们注意到任意两个对角线一定可以确定一个点。 那么只要求出对角线数量就行了！ 解法： 确定两个对角线就是找到四个点。 即在 $n$ 个点中选 $4$ 个点。 所以答案就是 $C^4_n$。

前言 这个应该小学生都可以看懂吧（本题解没有用到任何较难的知识）。 好像我也是小学生唉。 前置小知识 $a\bmod b=c$ 代表取模，即 $a$ 除 $b$ 的余数是 $c$。 题意 求 $ 2{(3{(4^{(\ldots ^{2023})})})} \bmod2023$。 思路 因为这个式子过于复杂，所以要简化一下。 根据小学的知识，找规律！！！ 但是手算是不行的，写个程序： 123456int s=3,sum=0,vis[2025]={};while(!vis[s]){ vis[s]=1; s=(s*3)%2023; sum++;}cout<<sum; 得出每 $408$ 个数为一个周期。 之后我们还需要知道指数在周期外的个数（即$ 3{(4{(\ldots ^{2023})})}\bmod 408$）。 一样，还是找规律： 123456int s=3,sum=0,vis[2025]={};while(!vis[s]){ vis[s]=1; s=(s*3)%2...

记忆化搜索+剪枝。 记忆化，记录： 目前到的点 $(x,y)$。 天数 $day$。 四个角的降雨量。 剪枝： 如果活动时下雨，直接剪掉。 如果四个角没有下雨 $\ge 7$ 天，直接剪掉。因为四个角地方被覆盖的情况是最少的。 代码: 12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;int n,a[405][5][5],f[5][5][405][8][8][8][8];int dx[]={-1,0,-2,0,2,0,1,0,0},dy[]={0,-1,0,-2,0,2,0,1,0};int dfs(int x,int y,int day,int ex,int sx,int ey,int sy){ if(f[x][y][day][ex][sx][ey][sy]!=-1) return f[x][y][day][ex][sx][ey][sy]; for(int...