How to AK Codeforces Round 828 (Div. 3)

__vector__ · 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