防止同学们直接复制粘贴,题解只给出python代码,请自行写出C++代码

方形字符串

  • 如果字符串长度为奇数,直接输出NO

  • 如果字符串长度为偶数

    • 方法一(C++):通过s.substr(0,s.size()/2)获取前一半字符串,通过s.substr(s.size()/2,s.size()/2)获取后一半字符串直接比较即可。
    • 方法二(通用):枚举下标0到s.size()/2-1,比较s[i]==s[i+s.size()/2]是否都成立即可
case = int(input())
for T in range(case):
    s = input()
    n = int(len(s))
    flag = 0
    if n%2!=0 : flag = 1
    for i in range (n//2):
        if s[i] != s[i+n//2]:
            flag = 1
    if flag == 0 : print("Yes")
    else : print("No")

净化字符串

枚举字符串中的每个字符s[i],如果s[i]==c,判断左右两边的字符数量是否都是偶数,如果是则说明答案是YES,否则是NO

case = int(input())
for T in range(case):
    s = input()
    n = len(s)
    c = input()
    flag = 0
    for i in range(n):
        if s[i]==c[0] :
            if i%2==0 and (n-i-1)%2==0 :
                flag = 1
    if flag == 1 : print("YES")
    else : print("NO")

波利卡和子序列之和

题目说输出的aa数组的顺序随意,那我们就假设aa数组是从小到大排好序的,也就是a[1]<a[2]<a[3]a[1]<a[2]<a[3]

显然b[1]=a[1]b[1]=a[1]

紧接着会发现,不存在其他数比a[1]a[1]大但比a[2]a[2]小了(因为其他数要么是a[3]a[3]要么是某两个数的和,都比a[2]a[2]大),所以b[2]=a[2]b[2]=a[2]

显然b[7]=a[1]+a[2]+a[3]b[7]=a[1]+a[2]+a[3]

所以a[3]=b[7]b[1]b[2]a[3]=b[7]-b[1]-b[2]

cas = int(input())
for T in range(cas):
    b = input().split(' ')
    sum = 0
    for i in range(7):
        x = int(b[i])
        if i==0 or i==1 :
            print(x,end=" ")
            sum = sum+x
        elif i==6:
            print(x-sum,end=" ")
    print("")

平方和立方

nn以内的平方数有n1/2n^{1/2}(向下取整)个,因为最大的平方数是n1/2n^{1/2}(向下取整)的平方

nn以内的立方数有n1/3n^{1/3}(向下取整)个,因为最大的立方数是n1/3n^{1/3}(向下取整)的立方

但是有一部分数既是平方数又是立方数,也就是x6x^6这种数,显然这样的数有n1/6n^{1/6}

所以根据小学的容斥原理得到:n1/2(向下取整)+n1/3(向下取整)n1/6(向下取整)n^{1/2}(向下取整)+n^{1/3}(向下取整)-n^{1/6}(向下取整)

但是直接用powpow函数算这些东西会有误差,可以暴力算,以求n1/3n^{1/3}为例:

int j = 1;
while((j+1)*(j+1)*(j+1)<=n)j++;

这样循环结束的时候,jj就是n1/3n^{1/3}

cas = int(input())
for T in range(cas):
    n = int(input())
    x = int(pow(n,0.5))
    y = 1
    while (y+1)**3<=n : y = y+1
    z = 1
    while (z+1)**6<=n : z = z+1
    print(x+y-z)

消失的音节

随便举个例子:

假设原串是abbaaba,那么在擦除之前写在白板的是:ab bb ba aa ab ba,前一个字符串的末尾等于后一个字符串的开头。

所以如果擦除掉的是中间的某个字符串,那么就会出现有某两个相邻字符串,前一个的末尾不等于后一个的开头,通过这种方法就能判断出来被擦除的是谁了。

如果没有这样的相邻字符串,可以认为擦除的是开头或者末尾的那个,随便添加一个字符到开头或者末尾就行了。

cas = int(input())
for T in range(cas):
    n = int(input())
    s = input().split(' ')
    ans = s[0]
    flag = 0
    for i in range(1,n-2):   
        if s[i][0]==s[i-1][1]:
            ans = ans+s[i][1]
        else :
            ans = ans+s[i]
            flag = 1
    if flag == 0 : ans = ans+"b"
    print(ans)

DIV+MOD

这题和2021年的CSP-J/S入门组第一题非常像,但比那个题要难一点。

首先考虑式子的后半部分x mod a

  • 如果l%a+(rl)>=a1l\%a + (r-l) >= a-1,那么说明这部分一定能取到最大值a1a-1
    • 接下来的任务就是让这部分最大的同时,使得x/a\lfloor x/a\rfloor最大
    • 根据取余运算的性质知道,在xx增大的过程中,余数在00a1a-1之间循环变化,每过一个循环周期(也就是余数从a1a-1变成00时)x/a\lfloor x/a\rfloor增加11,所以只要找到余数为a1a-1的最大的xx即可。
    • 先让now=(a1l%a)+lnow = (a-1-l\%a)+l,这样nownow就是最小的余数为a1a-1的数,这时(rnow)/a(r-now)/a就是还能增大的周期数,所以能使得余数为a1a-1的最大的xxnow+(rnow)/aanow+(r-now)/a*a
  • 否则直接输出r/a+r%ar/a+r\%a即可
cas = int(input())
for T in range(cas):
    l,r,a = input().split()
    l = int(l)
    r = int(r)
    a = int(a)
    t = l%a
    if t+(r-l)<a-1:
        print(r//a+r%a)
    else :
        now = (a-1-t)+l
        now += (r-now)//a*a
        print(now//a+now%a)

1 条评论

  • 1