本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-13 23:29:56
上场 AGC 爆零，掉绿了，所以这场只能 Unrated :(
本场打得很烂，2.5h 过 A，还吃了一发罚时（WA 样例）。
A
思路是找出 $n$ 为奇数的方案，然后再把 $n$ 为偶数的情况转化为奇数情况。
__vector__ 的博客
博客
标签
暂无
AGC064
Codeforces Round 893 (Div. 2)
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-16 00:47:11
目前 Pretests passed 了 ABC。
超大罚时选手，得想办法提高代码能力。
若 FST 了将删除题解。
UPD: Passed System Test
A
显然都去抢公共部分。
若 $c$ 为奇数，那么相当于给第一个人增加了一个点的优势。
对于先手，显然点数大于第二个人，才能获胜。
B
直接模拟。
但是细节贼麻烦。。。。。。。
另外出题人的题面是不是用脚写的，读了几遍才看懂。
C
模拟一些例子发现答案是 $\lfloor \frac{n}{2} \rfloor$。
然后构造，可以发现对于每个 $i$，把 $i,2i,4i,\cdots,2^k i$ 都依次加入，一旦出现了之前的 $j \le i-1$ 对应序列访问过的，立刻退出。
D
没做。
E1
没做。
E2
没做。
CF1858D
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-17 15:08:50
本题解作者是一个赛时没看题面，赛后一眼秒掉的小丑。
Sol
我们先扔掉那些乱七八糟的情况，只考虑长度最长的那个连续 $0$ 子串。
我们需要枚举所有可能的最长连续 $0$ 子串。
具体做法是，枚举长度 $l_0$，然后枚举所有 $l,r$ 满足 $r-l+1 = l_0$。
判断 $l$ 到 $r$ 形成的子串能否改造成满足要求的子串。
如果可以，那我们计算当前状态下，$l_1$ 最多是多少。
算出来这个，自然也就可以得知同一个 $l_0$ 对应的最大 $l_1$ 是多少。
本题即迎刃而解。
现在解决这个问题：如何算出当前状态下，$l_1$ 最多是多少。
设 $l$ 到 $r$ 的子串改造费用为 $cost$，那么 $l$ 到 $r$ 以外的字符还有 $k-cost$ 次机会改造。
然后对于前后缀分别 dp，这个是 dp 初学者就会的，不用说了。
Educational Codeforces Round 153 (Rated for Div. 2)
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-18 00:56:17
Pretests Passed ABC，D WA on pretest8
System Test 之后来填坑。
How to AK Codeforces Round 828 (Div. 3)
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-22 14:48:35
__vector__ 成功用 python 完成了本场 Div.3 ！
A
如果同类数字对应位置的字符不同，无解。
# LUOGU_RID: 122214048
import sys
input = sys.stdin.readline
def solve():
n = int(input())
a = list(map(int,input().split()))
a.insert(0,-1)
s=input()
s='_'+s
mp = {}
for i in range(1,n+1):
if mp.get(a[i],-1) ==-1:
mp[a[i]]=s[i]
else:
if mp[a[i]] !=s[i]:
print("NO")
return
print("YES")
if __name__ == '__main__':
t = int(input())
while t>=1:
solve()
t-=1
B
模拟一下就好了。
# LUOGU_RID: 122212838
import sys
input = sys.stdin.readline
def solve():
n,q = map(int,input().split())
a = list(map(int,input().split()))
a.insert(0,-1)
even = 0
odd = 0
cnte=0
cnto=0
for i in range(1,n+1):
if a[i]%2==0:
even+=a[i]
cnte+=1
else:
odd+=a[i]
cnto+=1
while q>=1:
op,x = map(int,input().split())
if op==0:
if x%2==0:
even+=cnte*x
else:
odd+=even+cnte*x
cnto+=cnte
even=0
cnte=0
if op==1:
if x%2 == 0:
odd+=cnto*x
else:
even+=odd+cnto*x
cnte+=cnto
odd=0
cnto=0
print(even+odd)
q-=1
if __name__ == '__main__':
t = int(input())
while t>=1:
solve()
t-=1
C
模拟一下就好了。
# LUOGU_RID: 122209833
import sys
input = sys.stdin.readline
def solve():
n,c = input().split()
n=int(n)
s = ' '+input()
i=1
ans=0
while i<=n:
if s[i]!=c:
i+=1
continue
j=i
cnt=0
while(s[j]!='g'):
cnt+=1
j+=1
if j==n+1:
j=1
ans=max(ans,cnt)
if j<i:
break
i=j+1
print(ans)
if __name__ == '__main__':
t = int(input())
while t >= 1:
solve()
t-=1
D
显然优先添加含 $2$ 因数多的。
# LUOGU_RID: 122203738
import sys
import functools
input = sys.stdin.readline
def solve():
n = int(input())
a = list(map(int,input().split()))
a.insert(0,-1)
count = {}
cnt = 0
ans = 0
count[-1]=0;
for i in range(1,n+1):
x = a[i]
while x % 2==0:
cnt+=1
x\/=2
a[i]=i
x = a[i]
count[a[i]]=0
while x % 2==0:
count[a[i]]+=1
x\/=2
# print(a)
a.sort(key=lambda x:-count[x])
# print(a)
for i in range(0,n+1):
if cnt>=n:
break
cnt+=count[a[i]]
# print("count[%d] = %d"%(a[i],count[a[i]]))
ans+=1
if cnt<n:
print("-1")
else:
print("%d"%(ans))
if __name__ == "__main__":
t = int(input())
while t:
solve()
t=t-1
E1
枚举 $x$，那么 $y$ 是 $\frac{ab}{\gcd(ab,x)}$ 的倍数。
复杂度 $O((c - a) \log \min(ab,x))$。
E2
不用枚举所有的 $x$，显然 $x$ 有效的部分是 $\gcd(ab,x)$，所以只需要枚举 $ab$ 的因数作为 $x$。
自己 vp 的时候，脑抽了，误以为 1e9 范围的因子数量至少 $10^5$，就没敢写。。。。。。
然后题解说只有 $10^3$ 量级，这下 $ab$ 的因子数量就是 $10^6$ 量级，可以直接枚举。
另外注意 $x,y$ 的范围限制，这个部分调整一下就行了，小细节得注意。
注意以下两份代码都必须是 pypy3 才能过，python 提交会 TLE。
自己写的丑陋又跑得慢的代码。
# LUOGU_RID: 122153835
# LUOGU_RID: 122151983
import sys
import math
input = sys.stdin.readline
def great_sqrt(x):
_ = int(math.sqrt(x))
while _*_ < x:
_+=1
while _*_ > x:
_-=1
return _
if __name__ == "__main__":
t = int(input())
while t!=0:
a,b,c,d=map(int,input().split())
_divs=[]
_divs2=[]
for i in range(1,great_sqrt(a)+1):
if a%i==0:
_divs.append(i)
if a\/i != i:
_divs.append(a\/i)
for i in range(1,great_sqrt(b)+1):
if b%i==0:
_divs2.append(i)
if b\/i != i:
_divs2.append(b\/i)
ok=0
mp = {}
for div in _divs:
for div2 in _divs2:
x = div*div2
if(mp.get(x,-1)!=-1):
continue
mp[x]=1
x_tmp = x
if (a-1)\/\/x_tmp != c\/\/x_tmp:
x = ((a-1)\/\/x_tmp)*x_tmp + x_tmp
# print("tempy = %d"%(y))
if x+x_tmp <= c:
x=x+x_tmp
if x <= a or x > c:
continue
if x<=a or x > c:
continue
# print("x = %d"%(x))
# print("y_tmp = %d"%(y_tmp))
y_tmp = a*b\/math.gcd(a*b,int(x))
if (b-1)\/\/y_tmp != d\/\/y_tmp:
y = ((b-1)\/\/y_tmp)*y_tmp + y_tmp
# print("tempy = %d"%(y))
if y+y_tmp <= d:
y=y+y_tmp
if y <= b or y > d:
continue
print("%d %d"%(x,y),end='\n')
ok=1
break
if ok:
break
if ok==0:
print("-1 -1",end='\n')
# print("=====================")
t-=1
_andyli 大佬优化的跑得飞快的代码
import math
def solve():
a, b, c, d = map(int, input().split())
_divs = []
_divs2 = []
for i in range(1, int(a**.5) + 1):
if a % i == 0:
_divs.append(i)
if a \/\/ i != i:
_divs.append(a \/\/ i)
for i in range(1, int(b**.5) + 1):
if b % i == 0:
_divs2.append(i)
if b \/\/ i != i:
_divs2.append(b \/\/ i)
for div in _divs:
for div2 in _divs2:
x = div * div2
x_tmp = x
if (a-1) \/\/ x_tmp != c \/\/ x_tmp:
x = ((a-1) \/\/ x_tmp)*x_tmp + x_tmp
if x+x_tmp <= c:
x = x+x_tmp
if x <= a or x > c:
continue
if x <= a or x > c:
continue
y_tmp = a * b \/\/ math.gcd(a * b, x)
if (b - 1) \/\/ y_tmp != d \/\/ y_tmp:
y = ((b - 1) \/\/ y_tmp)*y_tmp + y_tmp
if y + y_tmp <= d:
y = y + y_tmp
if y <= b or y > d:
continue
print(x, y)
return
while True:
x = c
x_tmp = x
if (a-1) \/\/ x_tmp != c \/\/ x_tmp:
x = ((a - 1) \/\/ x_tmp) * x_tmp + x_tmp
if x + x_tmp <= c:
x += x_tmp
if x <= a or x > c:
break
if x <= a or x > c:
break
y_tmp = a * b \/\/ math.gcd(a * b, x)
if (b - 1) \/\/ y_tmp != d \/\/ y_tmp:
y = ((b - 1) \/\/ y_tmp)*y_tmp + y_tmp
if y + y_tmp <= d:
y = y + y_tmp
if y <= b or y > d:
break
print(x, y)
return
break
print('-1 -1')
for _ in range(int(input())):
solve()
F
不知道为啥评 *2000，反正是秒了。
显然满足要求的区间从 $0$ 到 $\lfloor \frac{len+1}{2} \rfloor -1$ 所有数字都必须存在。
然后从 $1$ 到 $n$ 枚举 $len$ 就行了，记录 $l,r$ 代表当前 len 下，必须存在的所有数字最靠左的位置和最靠右的位置，剩余 $len - (r-l+1)$ 的部分自由支配，计算方案数就行了。
复杂度 $O(n)$。
import sys
import math
input = sys.stdin.readline
t = int(input())
while t:
n=int(input())
p = list(map(int,input().split()))
p.insert(0,-1);
pos = [0]*(n+1)
for i in range(1,n+1):
pos[p[i]]=i;
l=n
r=1
ans=0
for len in range(1,n+1):
mid=(len+1)\/\/2-1
l=min(l,pos[mid])
r=max(r,pos[mid])
surp=len-(r-l+1)
up=min(surp,n-r);
dw=max(0,surp-(l-1))
ans+=max(0,up-dw+1)
# print("len = %d l = %d r = %d up = %d dw = %d mid = %d surp = %d"%(len,l,r,up,dw,mid+1,surp));
print(ans,end='\n')
t=t-1
Codeforces Round 894 (Div. 3) 赛后AK
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-25 01:13:09
F 以为是个 n 乘值域的做法，没想到是 n 方乘值域的做法，对着 n 乘值域的做法想了半天。
最后还是写了个 n 方乘值域，加 bitset 优化。
然后因为把 sum（值域）打成 n，赛时没调出来。
紫砂了，要不是这个破事我就能改个签了。
当年 pt 似乎也是关键场次的 Div.3
Codeforces Round 894 (Div. 3)全部题目题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-25 12:14:56
错失了千载难逢的 AK 良机，死亡过程如下：
A 读错题，10min 进去了，然后多测清空写挂，吃一发罚时。
C 题没搞懂题意，10min 进去了。
D 题题意搞错，20min 进去了。
E 题读错题，40min 进去了（真的是 40min）
时间不多，想 F,以为是个 1e6 复杂度做法，想了会，没思路。
然后开始摆，到最后 10min 决定冲一发 bitset 优化 dp，复杂度 1e8 / w。
然后，因为把 sum 打成 n，没调出来，赛后 AC，跑得飞快。
G 题最后也没看。
第二天在学校，20min 在草稿纸上把 G 做了出来。
题解
A
贪心匹配子序列就行了。
B
依次枚举，如果 当前数小于上一个数，那就在中间插入 $1$（因为 $1$ 是最小数）
C
显然如果竖着的最高高度不是 $n$，无解。
剩余匹配就行了。
D
二分就行。
E
显然可以枚举最后一个电影，贪心算就行了。
F
枚举分给火系技能的怪物实力总和，bitset 优化可行性 dp 就可以搞定。
然后直接算就行了。
G
一次操作的本质是让相邻两数的差距减一。
所以一次操作前，如果一个数比前一个数大 $1$，那么操作后它一定会被干掉。
梳理一下。
第一次先排序，并去重。
显然，之后每一次操作结束后，所有数字相对顺序不会变，因为操作前没有重复数字。
所以我们只需要预先排序去重，然后忽略掉操作中的排序，之后所有内容都默认预先执行了操作。
每次操作都是把所有相邻数差距减少 $1$，然后所有与前一个数差距为 $0$ 的数都会在下一轮前被干掉。
由于每次操作后相对顺序不变，我们只需要关心第一个元素每次加上多少。
我们把操作前相邻数的差值都算出来，现在考虑每个差值的贡献。
显然，第 $i$ 次操作之前，所有初始状态下比前一个数大至少 $i$ 的数（包括最小的数，这里指第一个数）得以保留，第一个数的值将加上它们的数量总和。
显然可得，一个数对答案的贡献是这个数减去前一个数，最后贡献总和还要加上第一个数初始值，以及相邻两数最大的差值（显然这个是操作次数）。
现在，我们得出了快速计算一个序列答案的方法。
有修改修改操作也很简单，算一下减少的差值和新出现的差值的贡献，搞定。
COMPFEST 15 - Preliminary Online Mirror 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-09-04 01:08:39
开个坑，以后来更新。
Codeforces Round 895 (Div. 3)
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-09-08 20:39:48
F 题是缩点+拓扑排序板子，但是赛时没写完，悲。
A
贪心。
B
枚举 $k$ 就行了。
C
$a+b = 1,2,3$ 都是无解，$l$ 先对 $4$ 取 max。
若区间长度小于 $1$，无解。
若区间长度等于 $1$
- 若 $l$ 是质数，无解。
- 否则，设 $x$ 是 $l$ 的一个因数（除了 $1$ 和 $l$ 本身），$a = \frac{l}{x},b = a(x-1)$ 是一组解。
- 若区间长度大于等于 $2$。
- 若 $l$ 是偶数，设 $x$ 是 $l$ 的一个因数（除了 $1$ 和 $l$ 本身），$a = \frac{l}{x},b = a(x-1)$ 是一组解。
- 否则，设 $x$ 是 $l+1$ 的一个因数（除了 $1$ 和 $l+1$ 本身），$a = \frac{l+1}{x},b = a(x-1)$ 是一组解。
D
贪心一下就好了。
E
线段树板子。
F
$i$ 向 $a_i$ 连边。
如果没有环，显然按照拓扑序最优。
对于环，可以缩点，环内顺序可以贪心确定。
G
乘积足够大（比如说达到 $2n$），则最优做法是全部乘起来。
否则，意味着大于 $1$ 的位置数量只有几十个，暴力计算就行。
公开赠送 Hornex 账号
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-18 12:58:59
6 个 Ultra。
分别是 Bone,Gas,Web,Light，Leaf,Beetle Egg。
lvl 156，12 槽。
Mythic 一堆。
我不知道怎么赠送，想要的得告诉我赠送方式。
如过不能同时赠送多人，1 day 之后，在想要的人里面随机赠送
共 320 篇博客
鲁ICP备2025150228号