Magolor 首页文章幻灯片归档标签
Codeforces Round #573(Div.2) 做题题解 (Python 3和C++)
|OIPython
字数总计: 4.6k|阅读时长: 22 分钟

Python 3刚入门。来用Python 3做一场比赛看看。

求Python大佬指点。


Codeforces 1191A Tokitsukaze and Enhancement

题目大意: 一个数字mod  4\mod 4的余数为1最优，其次为3，再其次为2，为0最差。给定一个数，可以加上0,1或2，就加几以后这个数最优？最优是多少？


直接做就完了。复杂度名副其实的O(1)O(1)。

搞了半天憋出了我正经学Python后的第一个用来解决问题的正经程序。

1
2
3
4
5
6
7
8
9
# Python
t = int(input())&3
a = [1,3,2,0]
for i in range(4):
    d = (a[i]-t+4)&3
    if d < 3:
        print(d,chr(65+i))
        break
}

Python将会根治我的代码压行病，当然，前提是我不参加Python Code Golf。

想了半天感觉代码就只能做到这样了，不能再化简了，点开最短代码一看突然笑出声，然后照着改出Python 3代码，43个字符就够了(注释不算):

1
2
3
# Python
x=int(input())&3
print('1012'[x],'AABA'[x])

没错我应该是个ZZ了。喂！不要Code Golf啊！

C++代码放不放都无所谓了。

1
2
3
4
5
6
7
// C++
#include <bits/stdc++.h>
using namespace std;

#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int main(){int x=rf()&3;return !printf("%c %c","1012"[x],"AABA"[x]);}

Codeforces 1191B Tokitsukaze and Mahjong

题目大意: 给定三张牌(牌有三种花色，1~9九个面值)。求至少多拿几张牌可以得到一个三同花顺子或三张相同。


答案显然不超过2，枚举一张牌和其他牌凑一凑。例如顺子判断有没有x,x+1,x+2或者有没有x-1,x,x+1就行了。时间复杂度还是名副其实的O(1)O(1)。

Python的字符串str类型居然不支持单点修改，而且Python的字符和ASCII码转换需要用chr()和ord()函数，真的诡异。

1
2
3
4
5
6
7
8
# Python
a = input().split()
r = 2
for x in a:
    r = min(r,3-a.count(x))
    r = min(r,(not x.replace(x[0],chr(ord(x[0])+1),1) in a)+(not x.replace(x[0],chr(ord(x[0])+2),1) in a))
    r = min(r,(not x.replace(x[0],chr(ord(x[0])-1),1) in a)+(not x.replace(x[0],chr(ord(x[0])+1),1) in a))
print(r)

这里是不需要特判边界的，因为超了边界(面值大于9的ASCII码)在a里面一定是找不到的。

为了避免replace这一长串尴尬的代码，可以枚举牌面而不是枚举这三张牌:

1
2
3
4
5
6
7
8
# Python
a = input().split()
r = 2
for i in range(48,58):
    for c in "mps":
        r = min(r,3-a.count(chr(i)+c))
        r = min(r,3-(chr(i-1)+c in a)-(chr(i)+c in a)-(chr(i+1)+c in a))
print(r)

这里的48和58代表'0'和'9'+1，因为range()是左闭右开区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// C++
#include <bits/stdc++.h>
using namespace std;

#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
string a, b, c, f = "mps", i = "xx"; int r = 2;
int main()
{
    cin >> a >> b >> c;
    for(i[0] = '0'; i[0] <= '9'; i[0]++)
        for(int j = 0, t; j < 3; j++)
            i[1] = f[j], r = min(r,3-(a==i)-(b==i)-(c==i)), t = 3,
            t -= (a==i)||(b==i)||(c==i), i[0]++,
            t -= (a==i)||(b==i)||(c==i), i[0]++,
            t -= (a==i)||(b==i)||(c==i), i[0] -= 2, r = min(r,t);
    return !printf("%d\n",r);
}

Codeforces 1191C Tokitsukaze and Discard Items

题目大意: 一张[0,n−1][0,n-1]的正整数表，给定mm个特殊数，每次执行一个操作: 找到最小的特殊数xx，删除正整数表中所有[k⌊xk⌋,k(⌊xk⌋+1))\left[k\left\lfloor\frac{x}{k}\right\rfloor,k(\left\lfloor\frac{x}{k}\right\rfloor+1)\right)内的所有数。然后重新编号。求删除所有mm个特殊数的最小操作次数。1≤k≤n≤1018,1≤m≤1051 \le k \le n \le 10^{18},1 \le m \le 10^5


输入的mm个特殊数已经排好序了，概括一下这个操作就是: 删除一段前缀，后缀减去删去的数字数目。

因为前缀都删掉了不会再访问了，后缀减自然就等于整体减，于是用一个标记就完成了，寻找满足条件的前缀就是一个二分或者单调指针。二分O(mlog⁡m)O(m \log m)，单点指针O(m)O(m)。

下面是二分程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Python O(m log m)
n,m,k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
c = 1
i = 0
A = 0
while i < len(p):
    R = ((p[i]-c)//k+1)*k+c
    lef = i+1
    rig = len(p)
    while lef < rig:
        mid = (lef+rig)//2
        if p[mid] < R:
            lef = mid+1
        else:
            rig = mid
    c += lef-i
    i = lef
    A += 1
print(A)

~~辣鸡Python这都能TLE。~~所以还是要写一个单调指针:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Python O(m)
n,m,k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
c = 1
i = 0
A = 0
while i < m:
    R = ((p[i]-c)//k+1)*k+c
    j = i+1
    while j < m and p[j] < R:
        j += 1
    c += j-i
    i = j
    A += 1
print(A)

这个运行速度大约是280ms280\text{ms}。我们来看看C++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// C++ O(m log m)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rint register int
inline ll rf(){ll r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
ll p[100005], c = 1, A, m, k;
int main()
{
    rf(); m = rf(); k = rf(); generate(p+1,p+m+1,rf);
    for(rint i = 1, j; i <= m; c += j-i, i = j, A++)
        j = lower_bound(p+i+1,p+m+1,((p[i]-c)/k+1)*k+c)-p;
    return !printf("%d\n",A);
}

大约是46ms46\text{ms}！C的O(mlog⁡m)O(m \log m)竟然都比Python的O(m)O(m)快这么多！！！最后放上C的O(m)O(m):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// C++ O(m)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rint register int
inline ll rf(){ll r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
ll p[100005], c = 1, A, m, k, R;
int main()
{
    rf(); m = rf(); k = rf(); generate(p+1,p+m+1,rf);
    for(rint i = 1, j; i <= m; c += j-i, i = j, A++)
        for(j = i+1, R = ((p[i]-c)/k+1)*k+c; j <= m && p[j] < R; j++);
    return !printf("%d\n",A);
}

31ms31\text{ms}。


Codeforces 1191D Tokitsukaze, CSL and Stone Game

题目大意: 有nn堆石子，两个人轮流一次取一个石子，任何一个玩家取走石子后不能有两堆石子数目相同。给定一个局面求获胜方。注意00个石子的石子堆也是石子堆，不能数目相同，注意初始条件下可以有两堆石子数目相同，只要第一次移动后不同即可。n≤105,0≤ai≤109n \le 10^5, 0 \le a_i \le 10^9


分类讨论下:

  • 初始局面合法

    结束局面一定是0,1,2,3,...,n−10,1,2,3,...,n-1: 反证法，如果有别的结束局面，排序后第ii项不是ii，那么一定可以操作。因此只需要统计初始局面总石子数减去结束局面总石子数的奇偶性就行了。

  • 初始局面不合法

    • 有三个相同数目或者多个两对数目相同

      先手就凉了，输出cslnb。

    • 只有一个两堆

      • 第一步操作不能消除掉这两堆

        • 两堆00。

          先手也凉了，输出cslnb。

        • 形如x−1,x,xx-1,x,x。

          先手还是凉了，输出cslnb。

      • 第一步操作可以可以消除掉这两堆

        "转化为初始局面合法"的情况。

所以就做完了。这是一个根本没有决策而且游戏复杂度是O(n)O(n)的无聊游戏。

在边缘试探发现Codeforces允许使用Python标准模块。因此可以用sys.exit(0)来提前退出程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Python
import sys
n = int(input())
a = sorted([int(i) for i in input().split()])
t = 0
for i in range(1,n):
    t += a[i]==a[i-1]
if t >= 2:
    print("cslnb")
    sys.exit(0)
if t:
    for i in range(n):
        if a[i]==a[i+1]:
            if a[i] and a[i]!=a[i-1]+1:
                a[i] -= 1
                break
            else:
                print("cslnb")
                sys.exit(0)
print(["cslnb","sjfnb"][(sum(a)-t-n*(n-1)//2)&1])

这么长一坨居然是最短代码。

然后贴下C++代码，注意puts()返回值本来就是是0。

1
2
3
4
5
6
7
8
9
10
11
12
13
// C++
#include <bits/stdc++.h>
using namespace std;

#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int n, t; long long a[100005]; char Ans[2][6] = {"cslnb","sjfnb"};
int main()
{
    n = rf(); generate(a+1,a+n+1,rf); sort(a+1,a+n+1); for(rint i = 2; i <= n; t += a[i]==a[i-1], i++); if(t>=2) return puts("cslnb");
    a[0] = -2; if(t) for(rint i = 1; i <= n; i++) if(a[i]==a[i+1]){if(a[i]&&a[i]!=a[i-1]+1){a[i]--; break;} else return puts("cslnb");}
    return puts(Ans[(accumulate(a+1,a+n+1,0ll)-t-n*(n-1ll)/2)&1]);
}

发现Python不用考虑long long还是蛮舒服的。注意一下C++程序要考虑特判a[0]，防止误将a[0]当做石子堆，但是Python中因为数组循环访问，a[-1]是最大值，要么是0提前结束，要么不会影响判断。


Codeforces 1191E Tokitsukaze and Duel

题目大意: 长度为nn的01序列。两人轮流每次给一段长度恰好为kk的区间染色，染成同色者胜。求获胜方或平局(无限循环)。1≤k≤n≤1051 \le k \le n \le 10^5。


看上去是个挺复杂的问题，手动操作一下试一试。(假设先手玩家为A，后手玩家为B)第一步正常，第二步正常，问题出现在第三步。

假设在第三步，A经过操作获胜了。那么第二步，B就是必输状态，但是B完全可以重复A在第一步的操作从而把相同的状态转移给第三步的A，第三步的A就是必输状态，这个假设矛盾。

然后同理B也不可能在第四步胜利，因为A可以将第三步的状态原封不动传给第四步的B。以此类推，只要第二步游戏没结束，就结束不了了。

第一步A能不能一步胜利很好判断: 就是枚举长为kk的区间，如果存在一个区间外的前缀和后缀都是相同的，那么就可以胜利。这个过程是O(n)O(n)的。

显然，如果第一步A不能胜利。枚举第一步A的操作，判断第二步B能不能一步胜利，可以得到一个O(n2)O(n^2)的算法。考虑优化。

判断一步胜利的方法，如果已经预处理出最长前缀和最长后缀，只需要判断两者长度和+kk是不是大于序列总长度即可。那么枚举第一步A的选择后，如果已经对于每个位置求出这个位置向右延伸的最长距离，就可以O(1)O(1)更新最长前缀和最长后缀。就做完了。

复杂度O(n)O(n)。Python的边界处理真的难受，所以还是搞成数组下标从1开始了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Python
import sys
def Check():
    for j in [0,1]:
        if R[j][1] + L[j][n] + k >= n:
            return 1
    return 0
n,k = [int(i) for i in input().split()]
S = [int(i) for i in input()]
R = [[0]*(n+2),[0]*(n+2)]
L = [[0]*(n+2),[0]*(n+2)]
for j in [0,1]:
    for i in range(n):
        if S[i]==j:
            L[j][i+1] = L[j][i]+1
    for i in range(n-1,-1,-1):
        if S[i]==j:
            R[j][i+1] = R[j][i+2]+1
if Check():
    print("tokitsukaze")
    sys.exit(0)
for j in [0,1]:
    for r in range(k,n+1):
        l = r-k+1
        t = [R[j][1],L[j][n],R[j^1][1],L[j^1][n]]
        if R[j][1] >= l-1:
            R[j][1] = r+R[j][r+1]
        if L[j][n] >= n-r:
            L[j][n] = n-l+1+L[j][l-1]
        if R[j^1][1] > l-1:
            R[j^1][1] = l-1
        if L[j^1][n] > n-r:
            L[j^1][n] = n-r
        if not Check():
            print("once again")
            sys.exit(0)
        R[j][1],L[j][n],R[j^1][1],L[j^1][n] = t
print("quailty")

639ms639\text{ms}。下面来看C++，C++代码的边界处理就很舒服了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// C++
#include <bits/stdc++.h>
using namespace std;

#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int n, k, S[100005], R[2][100005], L[2][100005]; string s; bool Check(){for(int j = 0; j < 2; j++) if(R[j][1]+L[j][n]+k>=n) return 1; return 0;}
int main()
{
    n = rf(); k = rf(); cin >> s; for(rint i = 1; i <= n; S[i] = s[i-1]-'0', i++);
    for(rint j = 0, i; j < 2; j++) for(i = 1; i <= n; S[i]^j?:L[j][i]=L[j][i-1]+1, i++);
    for(rint j = 0, i; j < 2; j++) for(i = n; i >= 1; S[i]^j?:R[j][i]=R[j][i+1]+1, i--);
    if(Check()) return puts("tokitsukaze");
    for(rint j = 0, l, r, a, b, c, d; j < 2; j++) for(l = 1, r = k; r <= n; l++, r++)
        if(a = R[j][1], b = L[j][n], c = R[j^1][1], d = L[j^1][n],
        R[j][1]<l-1?:R[j][1]=r+R[j][r+1], L[j][n]<n-r?:L[j][n]=n-l+1+L[j][l-1],
        R[j^1][1]<l-1?:R[j^1][1]=l-1, L[j^1][n]<n-r?:L[j^1][n]=n-r, !Check())
            return puts("once again");
        else R[j][1] = a, L[j][n] = b, R[j^1][1] = c, L[j^1][n] = d;
    return puts("quailty");
}

46ms46\text{ms}。没啥好说的。


Codeforces 1191F Tokitsukaze and Strange Rectangle

题目大意: 给定平面上nn个点，每次可以用x∈[l,r],y∈[a,+∞)x \in [l,r],y \in [a,+\infty)作为限制条件来得到一个点集。求能得到多少种不同的点集。n≤105,x,y≤109n \le 10^5, x,y \le 10^9


冷静一下: 如果xx和yy互不相同，那么任何一个点集由下端点、左端点和右端点唯一确定，且左右端点高于下端点。那么就有一个很简单的做法，对于每个点统计其左上方点数ll和右上方点数rr，以这个点为下顶点的点集就有(l+1)∗(r+1)(l+1)*(r+1)个。统计一个点一侧的点数就是个二维数点，扫描线+离散化+树状数组就行了。O(nlog⁡n)O(n \log n)。

现在有相同的xx和yy。发现相同的yy好处理，因为根本不需要处理，相同的yy对答案没啥影响。相同的xx就会出现重复问题: 例如，假设某个xx值有若干个点，枚举第ii个点作为下端点的时候，其左端点就不能在第i−1i-1个点左侧，因为那样第i−1i-1个点也就成为下端点了。

具体地，枚举第i−1i-1个点作为下端点计算完，枚举第ii个点的时候要统计所有以ii为下端点且不包含i−1i-1的点，就需要l[i] -= l[i-1]。

时间复杂度O(nlog⁡n)O(n \log n)。担心Python过不去先写了个C++版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// C++
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200000
#define pii pair<int,int>
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int c[MAXN+5], _[MAXN+5], n; struct Pt{int x,y,l,r;}p[MAXN+5]; long long Ans;
inline void Add(int i, int v){i = n-i+1; for(; i <= n; c[i] += v, i += i&-i);}
inline int Sum(int i, int ans=0){i = n-i+1; for(; i; ans += c[i], i -= i&-i); return ans;}
bool cmpy(const Pt &a, const Pt &b){return a.y^b.y?a.y<b.y:a.x<b.x;}
bool cmpx1(const Pt &a, const Pt &b){return a.x^b.x?a.x<b.x:a.y<b.y;}
bool cmpx2(const Pt &a, const Pt &b){return a.x^b.x?a.x<b.x:a.y>b.y;}
int main()
{
    n = rf(); for(rint i = 1; i <= n; p[i].x = rf(), p[i].y = rf(), i++); sort(p+1,p+n+1,cmpy);
    for(rint i = 1; i <= n; _[i] = p[i].y, p[i].y = p[i-1].y+(_[i]!=_[i-1]), i++); sort(p+1,p+n+1,cmpx1);
    for(rint i = 1; i <= n; p[i].x==p[i-1].x?Add(p[i-1].y,-1),0:0, Add(p[i].y,1), p[i].l = Sum(p[i].y), i++); sort(p+1,p+n+1,cmpx2); memset(c+1,0,n<<2);
    for(rint i = n; i >= 1; p[i].x==p[i+1].x?Add(p[i+1].y,-1),0:0, Add(p[i].y,1), p[i].r = Sum(p[i].y), i--); sort(p+1,p+n+1,cmpy);
    for(rint i = 1; i <= n; p[i].y^p[i+1].y?:p[i].r-=p[i+1].r, i++);
    for(rint i = 1; i <= n; Ans += 1ll*p[i].l*p[i].r, i++); printf("%lld\n",Ans); return 0;
}

C++版本140ms140\text{ms}，时限是3000ms3000\text{ms}，即使Python慢20倍也够了。于是大胆进行Python实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# Python TLE
import sys
def Add(i,v):
    i = n-i+1
    while i <= n:
        c[i] += v
        i += i&-i
def Sum(i):
    r = 0
    i = n-i+1
    while i:
        r += c[i]
        i -= i&-i
    return r
n = int(input())
a = []
for i in sys.stdin:
    x,y = map(int,i.split())
    a.append((x,y,0,0))
a.sort(key=lambda x:x[1])
t = [a[0][1]]
a[0][1] = 1
for i in range(1,n):
    t.append(a[i][1])
    a[i][1] = a[i-1][1]+(t[i]!=t[i-1])
a.sort(key=lambda x:(x[0],x[1]))
c = [0] * (n+1)
for i in range(n):
    if i and a[i][0]==a[i-1][0]:
        Add(a[i-1][1],-1)
    Add(a[i][1],1)
    a[i][2] = Sum(a[i][1])
a.sort(key=lambda x:(-x[0],x[1]))
c = [0] * (n+1)
for i in range(n):
    if i and a[i][0]==a[i-1][0]:
        Add(a[i-1][1],-1)
    Add(a[i][1],1)
    a[i][3] = Sum(a[i][1])
a.sort(key=lambda x:(x[1],x[0]))
for i in range(n-1):
    if a[i][1]==a[i+1][1]:
        a[i][3] -= a[i+1][3]
print(sum([v[2]*v[3] for v in a]))

然后就TLE了！！！


体验

Python在列表的批量处理上有很大的优势。Python的任意长度整数型和通用类型也是加分项。

但是Python的不可更改对象对C++选手来说感觉不太友好。强制起始下标为0的做法更不友好(难以处理递推式的边界条件)。

可能问题在于我的代码不够Pythonic吧。

对Python运行速度已经失去希望。

最后的最后，我还是要说一句话:

没有for(;;);和?:压行的语言就没有灵魂

(手动滑稽.gif)


扫描二维码即可在手机上查看这篇文章，或者转发二维码来分享这篇文章:


文章作者: Magolor
文章链接: https://magolor.cn/2019/07/14/2019-07-14-blog-02/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Magolor！
CodeforcesOI资源树状数组单调指针二分Python
扫描二维码在手机上查看或转发二维码以分享Magolor的博客