洛谷 ⑨ 月月赛 I & Cnoi2020作战日志

人均AK,被吊打,没有人权 /kk 14:00 开赛。直接开 T1,“出现次数最多的非空子串的出现次数”,显然是个模拟。发现数据不大,果断暴力。 int main() { char ch; while ((ch = getchar()) != EOF) ++cnt[ch – ‘a’]; for (int i = 0; i < 26; ++i) ans = max(ans, cnt[i]); printf(“%d\n”, ans); return 0; } 感觉人均AC,开T2。 14:30 感觉平淡。看着题面感觉没什么思路,但是图片提示了搜索有关思想。感觉就是个搜索。 首先,如果中间有分流然后合起来的情况(环),走一边肯定更优。然后一个块就不会走多次了。这道题就是从一个点到其余三个点的最短路之和了。DFS裸题。 火速切。 inline void dfs(int x,int y,int t){ for(int i=1;i<=N;i++) Read more…

Solution P3401洛谷树

本题有一个弱化版本:GDKOI2016魔卡少女。 弱化版大致题意是:询问一个区间的子区间异或和。具体方法是拆开二进制的每一位,然后用线段树维护异或前缀和中 0,1 的个数,个数相乘后再加权即为答案。这样正确的原因是:对于一个有贡献的区间 [L,R],它一定会被 sum[L-1] 和 sum[R] 算到且仅一次。 然后这题只要把序列的问题搬到树链剖分上就行了,细节处理比较多(而且麻烦)。 代码: #include<bits/stdc++.h> #define mid ((L+R)>>1) #define lc (id<<1) #define rc (td<<1|1) typedef long long LL; using namespace std; const int maxk=10,maxn=3e4+5; struct edge { int obj,len; edge *Next; }e[maxn<<1]; struct data { int sum,num0,num1; }tree[maxk][maxn<<2]; edge *head[maxn]; int cur=-1; data Read more…

Solution [PA2009]Circular Game

令先手为 A,后手为 B,将相邻同色棋子合并成块,首先特判一些情况: 如果所有格子都是满的,那么显然????必败。 否则如果所有块都只有一个棋子,那么显然平局。 枚举????的第一步操作,如果可以使得B无法操作,那么显然????必胜。 无视所有大小为 1 的块,考虑剩下块里相邻两块,它们往外扩张比往内缩更优: 如果是形如 [A_A]___B__A__BA____B___[AA_A],两边同色,所以中间这些块(包括位置)可以删除,不影响游戏结果。 如果是形如 [A_A]___B__A__B_A__[BB_B],两边异色,那么相邻两块相互靠近更优,可以等效替代成 [A_A]___[BB][AA]__[BB][AA]__[BB_B]。 经过上述转化后,不再存在大小为 1 的块,当存在大小至少为 3 且内部存在空隙的自由块时,该块显然可以永远操作下去。假设不存在自由块,那么显然不会平局,游戏等价于每堆石子数为相邻两块间距的 \texttt{Nim} 游戏。 我们可以分以下情况讨论: A 可以通过至多一步操作得到自由块,且可以阻止 B 得到自由块,此时结果为 A 胜。 A,B 一开始都没有自由块,但都可以通过一步得到,A 先堵 B,B 再堵 A 后双方都没有自由块,但是此时 \texttt{Nim} 游戏 A 胜,则最终 A 胜。 A,B 都没法通过一步操作得到自由块,但是此时 \texttt{Nim} 游戏 A 胜,则最终 A 胜。 A Read more…