shicj's blog

我的方法使用了动态规划和树状数组，可能并不简洁，但题解太简略了，我暂时也不清楚怎么简单地维护题解里的 uuu 和 vvv，其他部分是原题解的详细版本。 首先分析一下操作（方便描述，标了个号）： 将 aaa 循环左移一位。若在进行操作前 a1≠0a_1\neq 0a1​​=0，则消耗 xxx 点代价。 将 aaa 循环右移一位。若在进行操作前 a1≠0a_1\neq 0a1​​=0，则消耗 yyy 点代价。 交换 x,yx,yx,y。消耗 zzz 点代价。 若 a1=b1a_1=b_1a1​=b1​，将 bbb 循环左移一位，同时令 a1=0a_1=0a1​=0。不消耗代价。 题目中出现了大量的循环位移操作，实际上可以对其进行简化分析，因为题目要求把 aaa 清空，那么我们将每一个 444 操作当作一个阶段，于是，题目要求按照 bbb 数组的顺序完成 nnn 个阶段的操作，每个阶段消掉一个数字，消掉数字的顺序就是 bbb 数组的顺序（这样，操作 444 中的循环移位解决掉了）。 移动整个数组并不好处理，因此可以理解为移动环上的指针。于是转化 111 和 222...

本次比赛难度为入门至提高+/省选。 但是没有入门。 首先考虑最小值，如果只有一只羊感染，那么它传染边上任何一个位置，然后两只羊互相传染就行了，最小值是 222 只。如果有更多的羊感染，它们只要紧挨着排列，每一只都传染给边上已经感染的，最小值是 xxx 只。于是有： ansmin⁡=max⁡{2,x}ans_{\min}=\max\{2,x\} ansmin​=max{2,x} 然后是最大值，先从一只羊开始扩展（这是不让羊挨在一起总是不劣的），如下： TTT 传染情况 000 X\green{X}X 111 XX\green{X}\red{X}XX 222 XXXX\red{X}\green{XX}\red{X}XXXX 333 XXXXXX\red{X}\green{XXXX}\red{X}XXXXXX ⋯\cdots⋯ ⋯\cdots⋯ 感染总数是 2T2T2T。 把每 2T2T2T 只当一个块，共有 xxx 个块，注意不要超过...

...

快捷键表 编译与查看：\ll 编译，:copen看日志 快捷编辑 Key = Key = bd \begin{document} ed \end{document} be \begin{enumerate} ee \end{enumerate} bc \begin{cneter} ec \end{center} c \chapter{ s \section{ p \paragraph{ i \item vimrc 1234567891011121314set relativenumber number ts=4 sw=4 autoindent cindent smartindent mouse=a set backspace=indent,eol,start set noexpandtab guifont=Ubuntu\ Mono\ 16syntax oncolorscheme habamaxcall plug#begin('~/.vim/plugged')Plug...

贪心地，依次扫描每一行（列），如果当前格子有球，将它打上标记，如果没有球且之前没有打过标记，直接进入下一行（列），最终统计有没有有球而没有标记的格子，如果有，说明不合法，否则合法。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include<bits/stdc++.h>using namespace std;string mp[100005];int n,m;void solve(){ cin>>n>>m; for(int i=1;i<=n;i++){ string tmp; cin>>mp[i]; mp[i]=" "+mp[i]; } for(int i=1;i<=n;i++){ for(int...

分类讨论。 【111】当 mmm 是奇数时，构造 $ \text{abababab} \cdots$ 的串即可满足题意，于是直接交替输出 111 和 222 凑足 m+1m+1m+1 个即可。 【222】当 mmm 是偶数时： 【2.12.12.1】存在一个点对，来回字母一样，如下图： 这时显然和【111】相同处理即可。 【2.22.22.2】存在三个点，路径上字母相同，如下图： 这时构造一个 ⋯1→2→1→2→3→2→3⋯\cdots 1\rightarrow2\rightarrow\boxed{1\rightarrow2\rightarrow3}\rightarrow2\rightarrow3\cdots⋯1→2→1→2→3​→2→3⋯...

提供一种简单的线段树写法。 首先，给出朴素的 DP，令 dpi,jdp_{i,j}dpi,j​ 表示前 iii 种食物，第 iii 种选择了 jjj 的最小花费，显然得出转移： dpi,j=min⁡(j,k) is OKdpi−1,k+ci,jdp_{i,j}=\min\limits_{\text{(j,k)\ is\ OK}}dp_{i-1,k}+c_{i,j} dpi,j​=(j,k) is OKmin​dpi−1,k​+ci,j​ 边界： dp1,i=c1,idp_{1,i}=c_{1,i} dp1,i​=c1,i​ 接下来将取最小值的枚举优化，一种简单的想法是，以 dpi−1dp_{i-1}dpi−1​ 建立线段树，每次枚举 kkk 时，将所有不符合条件的数字设置为正无穷，处理完这个 jjj 之后再将修改复原，这样的均摊时间复杂度为 O(nlog⁡n)O(n\log...

正难则反，倒序操作，操作的一定是四个同色格子（或者其中有已经完成操作的点，其他同色），可以从此入手进行 DFS。 遍历每一个点，对其进行 DFS，首先检查是否已经完成处理（被标记为 000）、越界或者不符合条件（有杂颜色），如果没有问题，标记这四个格子（改为 000），对其四周的格子进行搜索，具体的，分别是以下 888 个点： 1234dfs(x-1,y);dfs(x-1,y+1);dfs(x+2,y);dfs(x+2,y+1);dfs(x,y-1);dfs(x+1,y-1);dfs(x,y+2);dfs(x+1,y+2); 于是给出代码，注意倒序输出： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include<bits/stdc++.h>using namespace std;int n,m;int...

如果存在 uuu 不在 vvv 的子树内且 wu>wvw_u>w_vwu​>wv​，则最大的 vvv 一定是可行的点。 此时，选择了这个点后，对方将无法选出一个点使得消除后剩下的点大于选择的点，因此可行。如果选择不出这样一个点，则无解。 首先想到枚举 vvv，并要求在 O(log⁡n)O(\log n)O(logn) 时间内完成判断。看到这个时间复杂度以及最大值，我想到的是线段树（BIT 也可以的）。 为了实现查询，要想办法使得区间连续，为了实现这个目标，可以使用 DFS 序，令其为 dfndfndfn，这时查询的最大值可以分成 dfndfndfn 中的两段，前一段是 [1,dfnv][1,dfn_v][1,dfnv​]，为了描述后一段，定义当前节点 vvv 的子树中 dfndfndfn 最大的点的下一个点为 nxtvnxt_vnxtv​，于是第二段为 [nxtv,n][nxt_v,n][nxtv​,n]，nxtnxtnxt 的求法可以在 DFS 中完成，详见代码。 提示：注意可能取到空区间，线段树中注意判断！ code

关于 SuperHacker 当前版本：V1.0 Github Project Link Super Hacker 是一个用于 Codeforces 中同时对多个人进行自动 Hack 的工具，原理是使用类似对拍的方法，随机生成数据后用各个程序运行得出结果，再将程序运行结果进行两两比对，如果不相同，那么其中至少有一个程序被成功 Hack。 Super Hacker 也可以用于对拍，目前虽没有专门开发相关功能，但只需将人数设置为 222 人，分别放置暴力和自己的代码即可。 Super Hacker 使用 GNU 许可协议开源。 功能 自定义数据生成器 自定义输出比对器 支持最多 100100100 份代码对拍（可以改代码增加，但注意效率） 保存所有运行数据和输入输出文件 文件要求 文件放置 12345678910111213141516+SuperHacker|---hacker.exe (主程序)|---checker.exe (自己创建)|---data.exe (自己创建)|--+src (自己创建)| ...