对没错下面的代码全部是python 3（除了E的那个multiset）

题目链接：https://codeforces.com/contest/1157

A. Reachable Numbers

按位算贡献，一位数的贡献直接算即可

n=int(input())

ans=0

while (n>=10):

    tmp=n%10

    tmp=10-tmp

    ans+=tmp

    n+=tmp

    while (n>0) and (n%10==0):

        n//=10

ans+=9

print(ans)

B. Long Number

贪心，肯定是优先变最高位

import sys

import os

n=int(input())

a=input()

f=list(map(int,input().split()))

#print(f)

ans=""

pos=0

while (pos<n):

    now=ord(a[pos])-48

    if (a[pos]>=chr(f[now-1]+48)):

        ans=ans+a[pos]

        pos+=1

    else:

        while (pos<n) and (a[pos]<=chr(f[now-1]+48)):

            ans=ans+chr(f[now-1]+48)

            pos+=1

            if (pos<n) :

                now=ord(a[pos])-48

        print(pos)

        for i in range (pos,n):

            ans=ans+a[i]

        pos=n

        break

print(ans)

C1&C2 Increasing Subsequence

建立两个指针\(l\)和\(r\)，同时记录上一次的答案，暴力扫描即可

注意\(a_l==a_r\)时很明显决策是只会从一端开始取数，直接做完

n=int(input())

ans=[]

a=list(map(int,input().split()))

l=-0

r=n-1

now=0

while l<=r:

    #print(l,r,now,a[l],a[r])

    if a[l]<a[r] and a[l]>now:

        now=a[l]

        l+=1

        ans.append('L')

    elif a[r]<a[l] and a[r]>now:

        now=a[r]

        r-=1

        ans.append('R')

    elif a[r]<a[l] and a[l]>now:

        now=a[l]

        l+=1

        ans.append('L')

    elif a[l]<a[r] and a[r]>now:

        now=a[r]

        r-=1

        ans.append('R')

    elif a[l]==a[r]:

        #print(l,r,now)

        if a[l]<=now:

            break

        nowl=now

        nowr=now

        pos=l

        cnt1=0

        cnt2=0

        while pos<=r and a[pos]>nowl:

            nowl=a[pos]

            pos+=1

            cnt1+=1

        pos=r

        while l<=pos and a[pos]>nowr:

            nowr=a[pos]

            pos-=1

            cnt2+=1

        if (cnt1>cnt2):

            for i in range(0,cnt1):

                ans.append('L')

        else:

            for i in range(0,cnt2):

                ans.append('R')

        break

    else:

        break

print(len(ans))

for i in ans:

    print(i,end="")

D.N Problems During K Days

人民群众喜闻乐见的构造题

先把这个序列设定为\([x,x+1,\cdots,x+k-1]\)之后再进行调整

对于每一个位置\(i\)考虑在\([i,n]\)中所有的数都加上某个相同的数，这个可以直接得到，同时要和\(a_{i-1}*2-a_i\)取\(min\)

最后看\(n\)是否还有剩余

import sys

n,k=map(int,input().split())

a=[0]*(k+2)

if k*(k+1)>n*2:

    print("NO")

    sys.exit()

for i in range(1,k+1):

    a[i]=i

n-=k*(k+1)//2

rest=n//k

n-=rest*k

a[1]+=rest

for i in range(2,k+1):

    a[i]=a[i-1]+1

    rest=n//(k-i+1)

    tmp=min(rest,a[i-1]*2-a[i])

    a[i]+=tmp

    n-=(k-i+1)*tmp

if n>0:

    print("NO")

    sys.exit()

print("YES")

for i in range(1,k+1):

    print(a[i],end=" ")

E. Minimum Array

简单题

对于\(a_i\)，你期望找到一个\(b_i\)，使得\(a_i+b_i=n\)，如果找不到，那你就希望找一个大于\(b_i\)的又和\(b_i\)最接近的

这不是lower_bound这是什么

把\(b\)丢到multiset中，每次对\(a_i\)lower_bound一下

当然万一找不到的话还是要找最小的\(b_i\)，比较一下即可

使用c++实现

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000000007

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

int n,a[200200],b[200200];

multiset<int> s;

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

int main()

{

	n=read();

	rep(i,1,n) a[i]=read();

	rep(i,1,n) {b[i]=read();s.insert(b[i]);}

	multiset<int>::iterator it;

	rep(i,1,n)

	{

		int tmp=(n-a[i])%n;

		it=s.lower_bound(tmp);

		if (it==s.end()) it--;

		int st=*(s.begin()),now=*it;

		if ((now+a[i])%n>(st+a[i])%n) now=st;

		s.erase(s.lower_bound(now));

		printf("%d ",(now+a[i])%n);

	}

	return 0;

}

F. Maximum Balanced Circle

又是构造题

首先你选的数一定是在某一个连续区间内的数，这样你就解决了\(|a_i-a_{i+1}|\leq 1\)

然后就是\(|a_1-a_k|\leq 1\)，你可以把所有的\(a_i\)排成一个先递增后递减的形式（就像山峰一样）

然后出现次数为1的数要么出现在山脚（\(a_1\)），要么出现在山顶（\(max\{a_i\}\)）

然后就做完啦

n=int(input())

a=list(map(int,input().split()))

cnt=[0]*(200005)

for i in range(0,n):

    cnt[a[i]]+=1

ans=0

ansl=0

ansr=0

l=1

N=200001

while (l<=N):

    if cnt[l]==0:

        l+=1

    else:

        r=l

        now=0

        while (r<=N):

            if cnt[r]==0:

                r-=1

                break

            elif cnt[r]==1 and l!=r:

                now+=cnt[r]

                break

            else:

                now+=cnt[r]

                r+=1

        if now>ans:

            ansl=l

            ansr=r

            ans=now

        #print(l,r,now)

        if l==r:

            l=r+1

        else:

            l=r

seq=[]

for i in range(ansl,ansr+1):

    seq.append(i)

    cnt[i]-=1

for i in range(ansr,ansl-1,-1):

    while cnt[i]>0:

        seq.append(i)

        cnt[i]-=1

print(len(seq))

for i in seq:

    print(i,end=" ")

G. Inverse of Rows and Columns

对没错还是构造题

考虑一个合法方案一定至少符合下列两个条件之一：

1）第一行全部为\(0\) 2）最后一行全部为\(1\)

我们枚举当前满足哪一个条件，那么根据当前行中每一个数的情况我们就确定了当前列的翻转情况

接下来我们枚举行，找到中间的断点（由0变成1的地方），以此确定行的反转情况

最后暴力取出所有书\(check\)即可

import sys

n=0

m=0

sq=[[0]*(310)]*(310)

ansx=[]

ansy=[]

tmp=[[0]*(310)]*(310)

def chk():

    val=[]

    for i in range(0,n):

        for j in range(0,m):

            val.append(tmp[i][j])

    Len=len(val)

    for i in range(1,Len):

        if val[i-1]>val[i]:

            return False

    return True

n,m=map(int,input().split())

for i in range(0,n):

    sq[i]=list(map(int,input().split()))

for i in range(0,n):

        tmp[i]=list(sq[i])

for i in range(0,m):

    if tmp[0][i]==1:

        ansy.append(1)

        for j in range (0,n):

            tmp[j][i]=1-tmp[j][i]

    else:

        ansy.append(0)

op=0

for i in range(0,n):

    flag0=0

    flag1=0

    for j in range(0,m):

        if tmp[i][j]==0:

            flag0=1

        else:

            flag1=1

    if flag0==1 and flag1==1:

        op=1

        if tmp[i][0]==1:

            ansx.append(1)

            for j in range (0,m):

                tmp[i][j]=1-tmp[i][j]

        else:

            ansx.append(0)

    elif flag0==1:

        if op==0:

            ansx.append(0)

        elif op==1:

            ansx.append(1)

            for j in range(0,m):

                tmp[i][j]=1-tmp[i][j]

    elif flag1==1:

        if op==0:

            ansx.append(1)

            for j in range(0,m):

                tmp[i][j]=1-tmp[i][j]

        else:

            ansx.append(0)

if chk():

    print("YES")

    for i in range(0,n):

        print(ansx[i],end="")

    print()

    for i in range(0,m):

        print(ansy[i],end="")

    sys.exit()

for i in range(0,n):

    tmp[i]=list(sq[i])

ansx=[]

ansy=[]

for i in range(0,m):

    if (tmp[n-1][i]==1):

        ansy.append(0)

    else:

        ansy.append(1)

        for j in range(0,n):

            tmp[j][i]=1-tmp[j][i]

op=0

for i in range(0,n):

    flag0=0

    flag1=0

    for j in range(0,m):

        if tmp[i][j]==1:

            flag1=1

        else:

            flag0=1

    if flag1==1 and flag0==1:

        op=1

        if tmp[i][0]==1:

            ansx.append(1)

            for j in range(0,m):

                tmp[i][j]=1-tmp[i][j]

        else:

            ansx.append(0)

    elif flag0==1:

        if op==0:

            ansx.append(0)

        else:

            ansx.append(1)

            for j in range(0,m):

                tmp[i][j]=1-tmp[i][j]

    elif flag1==1:

        if op==1:

            ansx.append(0)

        else:

            ansx.append(1)

            for j in range(0,m):

                tmp[i][j]=1-tmp[i][j]

if chk():

    print("YES")

    for i in range(0,n):

        print(ansx[i],end="")

    print()

    for i in range(0,m):

        print(ansy[i],end="")

    sys.exit()

print("NO")