[TOC]

Codeforces Round 919 (Div2)

Problem - A - Codeforces

题目翻译：

亚历克斯正在解决一个问题。他对整数 的值有 个约束。有三种类型的约束：

1. 必须大于或等于某个整数 ；
2. 必须小于或等于某个整数 ；
3. 必须不等于某个整数 。

帮助亚历克斯找出满足所有 约束条件的整数 的个数。保证答案是有限的(存在至少一个 类型的约束和至少一个 类型的约束)。同时，保证没有两个约束条件是完全相同的。

比较简单，直接上代码：

import sys

def solve():
    n = int(sys.stdin.readline())
    l,r = 1,int(1e9)
    ls = []
    for _ in range(n):
        a,x = map(int, sys.stdin.readline().split())
        if a == 3: ls.append(x)
        elif a == 2: r = min(r,x)
        else: l = max(x,l)
    if r < l:
        print(0)
        return
    ans = r-l+1
    for x in ls:
        if x <= r and x >= l: ans -= 1
    print(ans)
    # print(ls)
    # print(l,r)

for _ in range(int(input())):
    solve()

Problem - B - Codeforces

题目翻译：

爱丽丝和鲍勃正在玩一个游戏。他们有一个数组 。游戏包括两个步骤：

• 首先，爱丽丝将从数组中移除最多 个元素。
• 第二步，鲍勃将数组中最多个 元素乘以 。

爱丽丝希望最大化数组元素之和，而鲍勃希望最小化数组元素之和。如果双方都以最佳方式进行游戏，请找出游戏结束后数组元素的总和。

题目分析：

这是一个博弈的问题，我们很容易想到的最优做法就是把还在数组中的最大的个数乘-1.

那么对于 肯定也是考虑去掉最大的，不然无意义，那是否意味着去掉越多越好呢，显然不是，反例如下： 去掉1000显然比去掉更优.

那我们考虑维护一个前缀和，暴力枚举每一个前缀，再取最优解即可。时间复杂度为.

python3 code:

import sys

def solve():
    n,k,x = map(int, sys.stdin.readline().split())
    ls = list(map(int, sys.stdin.readline().split()))
    ls.sort(reverse=True)
    ls.append(0)

    res,idx = 0,x
    tmp = 0
    for i in range(k):
        if idx < n:
            tmp += ls[i]-2*ls[idx]
            res = max(tmp,res)
            idx += 1
        else:
            tmp += ls[i]
            res = max(tmp,res)
    for i in range(x):
        ls[i] = -ls[i]
    print(sum(ls)+res)

for i in range(int(input())):
    solve()

Problem - C - Codeforces

题目翻译：

艾伦有一个数组 。对于每个是 除数的正整数 ，艾伦都会做如下运算：

• 他将数组分割成长度为 的 个互不相交的子数组。换句话说，他将数组划分为以下子数组：

  $$[a_1,a_2,...,a_k],[a_{k+1}, a_{k+2},...,a_{2k}],...,[a_{n-k+1},a_{n-k+2},..,a_{n}]$$

• 如果存在某个正整数 ( )，使得他将数组中的每个元素除以 后的余数都替换为该元素，则所有子数组都相同，则艾伦得一分。

帮助艾伦找出他将获得的分数。

题目分析及思路历程：

很有意思的一道题，我们来捋一遍思路。

1、首先，看题目是我们得先知道个子区间相同，子区间之间应该满足什么？我们不防先想想当每个子区间都是一个数的时候，它们在哪个 下相等（modulo ）？

我们很容易想到两个数同余意味着他们的差 满足 .也就是说m被差整除。

2、这时候我们再来考虑一下怎么解决区间的问题，由上述说明可知不同区间相同，当且仅当对应位置上的数之间的差值都能被 整除，这就是差值的 。

3、我们可以遍历所有可能的 ( 是 的整除数），并求解每个 以得到答案,对于每一个我们可以通过一个 函数返回是否存在这么一个。这样做的时间复杂度为 。请注意，每次遍历数组都需要花费 时间，因为 在每一点上要么减半，要么保持不变。

python3 code:

import sys
from math import sqrt

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def check(x):
    if x == n: return 1
    g = abs(ls[1]-ls[x+1])
    for i in range(1,x+1):
        for j in range(i+x,n+1,x):
            g = gcd(g,abs(ls[i]-ls[j]))
    if g == 1: return 0
    else: return 1

for _ in range(int(input())):
    n = int(sys.stdin.readline())
    ls = [0]+list(map(int, sys.stdin.readline().split()))
    ans = 0
    for i in range(1,int(sqrt(n))+1):
        if n % i == 0:
            if check(i): ans += 1
            if i != n // i:
                if check(n // i): ans += 1
    print(ans)

Problem - D - Codeforces

本题参考官方题解，提供 Python3 实现

题目翻译

杰登有一个数组 ，最初是空的。他必须按照给定的顺序执行两种类型的 操作。

1. 贾登将一个整数 ( ) 追加到数组 的末尾。
2. 杰登将数组 的 个副本追加到数组 的末尾。换句话说，数组 变成了 。可以保证的是，在此之前他至少进行过一次第一种类型的操作。

杰登有 个查询。对于每个查询，你必须告诉他数组 中的 个元素。数组的元素从 开始编号。

输入

每个测试由多个测试用例组成。第一行包含一个整数 ( ) - 测试用例的个数。测试用例说明如下。

每个测试用例的第一行包含两个整数 和 ( )—操作次数和查询次数。

接下来的 行描述操作。每行包含两个整数 和 ( )，其中 表示操作类型。如果是 ，则 ｝( ) 是杰登追加到数组末尾的整数。如果是 ，那么 ( ) 是杰登追加到数组末尾的份数。

每个测试用例的下一行包含 个整数 ( 表示查询，其中 是完成所有 操作后的数组大小。

保证所有测试用例的 和 之和不超过 。

输出

对于每个测试用例，输出 个整数—杰登询问的答案。

题目解析及思路历程：

这显然是一个类似循环节的问题，我们的关键就是怎么追溯到处理第个数的操作

我们来看一个追溯的例子：

假设第 个元素是加粗的 。找到 -th元素等同于找到( )-th元素（除非 是 ）。

之后，让我们预处理一些值：

现在，让我们试着回答某个查询 。如果有 ，那么答案就是 。

否则，让我们找出 的第一个 。这个 将是一个重复操作，我们的答案将位于其中一个重复操作中。此时我们的列表如下

让 -th元素成为最后一次重复中加粗的 。正如你所看到的，找到 -元素等同于找到 -th元素。因此，我们应该做 ，然后重复！但还有一种情况！如果是 ，那么答案就是 。

此时我们有两种方法来解决这个问题：

方法 1

注意，在对第二种类型进行 次操作后，元素数将超过 。因此，我们只需关注第二种类型的前 次操作。因此，反向遍历第二种类型的 次操作，并执行上述案例。这将导致 解或 解，具体取决于实现细节。

方法 2

观察 可以将 减少至少一半。如果我们重复二分查找第一个 ，即 ，然后执行 （如果是其他情况之一，则停止），那么每次查询将耗时 ，因此总时间复杂度为 。

python3 code（方法二）：

import sys

input =  sys.stdin.readline

for _ in range(int(input())):
    n,q = map(int, input().split())
    lst,dp = [0],[0]
    for i in range(1,n+1):
        b,x = map(int, input().split())
        if dp[-1] > 1e18: continue
        if b == 1:
            lst.append(x)
            dp.append(dp[-1]+1)
        else:
            lst.append(lst[-1])
            dp.append(dp[-1]*(x+1) if (x+1) <= 1e18/dp[i-1] else 2e18)

    ls = list(map(int,input().split()))
    ans = [0]*(q)
    for i in range(q):
        k = ls[i]
        while True:
            l, r = 0, len(dp)
            while l < r:
                mid = (l + r) // 2
                if mid >= len(dp) or dp[mid] >= k: r = mid
                else: l = mid + 1
            if dp[r] == k:
                ans[i] = lst[r]
                break
            elif k % dp[r-1] == 0:
                ans[i] = lst[r-1]
                break
            k %= dp[r-1]
    print(*ans)