牛客寒假营5

B题智乃的瓷砖

考点：暴力

思路：判断i,j的奇偶性即可。

import sys
import math
input=sys.stdin.readline

n,m=map(int,input().split())
a=[['' for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
if i%2==0:
if j%2==0:
a[i][j]='/'
else:
a[i][j]='\\\\'
else:
if j%2==0:
a[i][j]='\\\\'
else:
a[i][j]='/'

for i in range(n):
for j in range(m):
print(a[i][j],end='')
print()

D题智乃的果子

考点：优先队列，贪心

思路：读题可想到肯定是从小往大合并会比较优。我们先用优先队列记录一下果子的重量和数量，每次都取最轻的处理，把其中的一半两两合并；如果这一组只有一个果子，我们就再取一组与它合并。

import sys
from collections import deque
input=sys.stdin.readline
mod=10**9+7
n=int(input())
#读入并按重量统计数量
mp={}
total=0
for _ in range(n):
c,w=map(int,input().split())
mp[w]=mp.get(w,0)+c
total+=c
#建两个队列A和B
item=sorted(mp.items())
a=deque(sorted(mp.items()))
b=deque()

def clean():
#队头里的(w,c)如果c==0说明这个重量的堆已经被取光了
while a and a[0][1]==0:
a.popleft()
while b and b[0][1]==0:
b.popleft()

def pop():
clean()
#从a和b的队头中选更小的那个重量，取走1
if not b or (a and a[0][0]<=b[0][0]):
w,c=a[0]
if c==1:
a.popleft()
else:
a[0]=(w,c-1)
return w
else:
w,c=b[0]
if c==1:
b.popleft()
else:
b[0]=(w,c-1)
return w
def pop_all():
clean()
if not b or (a and a[0][0]<b[0][0]):
w=a[0][0]
else:
w=b[0][0]

c=0
if a and a[0][0]==w:
c+=a[0][1]
a.popleft()
if b and b[0][0]==w:
c+=b[0][1]
b.popleft()
return w,c
#把新堆放进b中
def push(w,c):
if c<=0:
return
if b and b[-1][0]==w:
b[-1]=(w,b[-1][1]+c)
else:
b.append((w,c))
#做Huffman合并
ans=0
while total>1:
w,c=pop_all()
k=c//2
if k:
ans=(ans+(k%mod)*((2*w)%mod))%mod
total-=k
push(2*w,k)
if c&1:
x=pop()
s=w+x
ans=(ans+s)%mod
total-=1
push(s,1)
print(ans%mod)

E题智乃的最大子段和取模

考点：前缀和，二分，贪心

思路：先对数组求前缀和，然后固定右端为x，左端记为y，有两种情况：

最后再用坐标压缩+树状数组实现动态维护前缀和数组。

复杂度：O()

import sys
input=sys.stdin.readline
class BIT:
def __init__(self,n):
self.n=n
self.bit=[0]*(n+1)
#add是用来插入一个值的
def add(self,i,d):
while i<=self.n:
self.bit[i]+=d
i+=i&-i
#统计<=pos的数量
def sum(self,i):
s=0
while i>0:
s+=self.bit[i]
i-=i&-i
return s
#找到第k小的元素rank
def kth(self,k):
#返回最小的idx
idx=0
bitm=1<<(self.n.bit_length()-1)
while bitm:
nxt=idx+bitm
if nxt<=self.n and self.bit[nxt]<k:
k-=self.bit[nxt]
idx=nxt
bitm>>=1
return idx+1
n,p=map(int,input().split())
a=list(map(int,input().split()))
#p=1时所有子段mod1都是0，随便输出一个合法的就行
if p==1:
print(0,0,0)
exit()
#前缀和取模
pre=[0]*(n+1)
for j in range(1,n+1):
pre[j]=(pre[j-1]+a[j-1])%p
#坐标压缩
#目的是把值域(0到p-1)压缩到1到m中，方便维护
val=sorted(set(pre))
m=len(val)
rk={v:i+1 for i,v in enumerate(val)}
bit=BIT(m)
#first记录第一次出现的前缀下标i
first=[-1]*(m+1)
#先把pre[0]=0插入结构，作为可选左端点
r0=rk[0]
bit.add(r0,1)
first[r0]=0
total=1#已插入的前缀和个数

#枚举右端点前缀下标j，对应子段右端r=j-1
best=-1
bestl=0
bestr=0

for j in range(1,n+1):
x=pre[j]
rx=rk[x]
#1.选i=0
if x>best:
best=x
bestl=0
bestr=j-1
#2.找第一个>x的pre[i],记为y
cnt_l=bit.sum(rx)
if total>cnt_l:
s_r=bit.kth(cnt_l+1)#第一个>x的rank
y=val[s_r-1] #取到实际值
i=first[s_r] #取到y对应的某个前缀位置

cand=x-y+p
if cand>best:
best=cand
bestl=i
bestr=j-1
#把当前前缀pre[j]加入结构，供后面左端点用
if first[rx]==-1:
first[rx]=j
bit.add(rx,1)
total+=1
print(bestl,bestr,best)

F题智乃的算法竞赛群友

考点：贪心，dp，字符串

思路：设dp[i]表示长度恰好为i的字符串能获得的最大快乐值。

但是，直接从1推到n做线性dp会超时。

于是我们先全部用qcjjkktd这个长度为8的字符，看能有多少组，然后再用dp求剩余的字符是用qcjjkkt连接还是td连接利益最大，最后将两部分求和就是最优收益。

复杂度：O(t)

import sys
input=sys.stdin.readline
def bestr(rem,a,b):
pmax=rem//7 #最多可以放7块A
#先考虑全是B，不用a，B的长度为2，最多放rem//2
best=(rem//2)*b
#求最大偶数
pe=pmax if (pmax&1)==0 else pmax-1
if pe>=0:
best=max(best,pe*a+((rem-7*pe)//2)*b)
#最小奇数是1
if pmax>=1:
best=max(best,a+((rem-7)//2)*b)
#求最大奇数
po=pmax if (pmax&1)==1 else pmax-1
if po>=1:
best=max(best,po*a+((rem-7*po)//2)*b)
return best
t=int(input())
for _ in range(t):
n,a,b=map(int,input().split())
k=n//8 #最多能放多少个
c=set()
c.update(range(0,min(k,6)+1)) #靠近0的7个
c.update(range(max(0,k-6),k+1))#靠近k的7个

ans=0
for kk in c:
#放k个C后剩余的长度
rem=n-8*kk
#求总收益k*(a+b)+在rem内用A（7,a）,B（2，b）的最优收益
ans=max(ans,kk*(a+b)+bestr(rem,a,b))
print(ans)

G题智乃的箭头魔术

考点：模拟

思路：按题目描述模拟即可。

H题智乃的矩阵

考点：找规律

思路：在这种2*2的方格里选两条不重叠的相邻边，一条+1，一条-1，本质是黑白守恒+行列奇偶守恒。必须满足的条件是：

总和能够平均：s%(n*n)==0，并且目标值要x=s/n^2。

每行和，每列和的奇偶要匹配最终的n*x。

交错和要匹配：n为偶数时要求为0，n为奇数的时候要求等于x。

复杂度：

import sys
input=sys.stdin.readline
def pd(a):
n=len(a)
row=[0]*n
col=[0]*n
s=0
c=0
for i in range(n):
res=0
for j,v in enumerate(a[i]):
res+=v
col[j]+=v
if ((i+j)&1)==0:
c+=v
else:
c-=v
row[i]=res
s+=res
nn=n*n
if s%nn!=0:
return False
x=s//nn
nx=n*x
for i in range(n):
if ((row[i]-nx)&1)!=0:
return False
for j in range(n):
if ((col[j]-nx)&1)!=0:
return False
if n%2==0:
return c==0
else:
return c==x
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
print("Yes" if pd(a) else "No")

I题智乃挖坑

考点：差分，二分

思路：因为是否挖穿的操作次数是单调的，所以可以用二分查找最早挖穿的那个位置。这题恶心的地方在于不是区间常数，是一个顶尖三角形。我们可以把顶尖三角形拆分成左右两个部分：

• 左半边当的时候。
• 右半边当的时候。

也就是(系数-1)*x+常数*(f+p)

所以我们可以维护两个差分数组：

• d1：记录x的系数在各位置的累加
• d2:记录常数项在各位置的累加

于是，最后扫一遍是否存在zh[x]>h即可得到答案。

复杂度：

import sys
input=sys.stdin.readline

n,m,h=map(int,input().split())
p=[0]*(m+1)
f=[0]*(m+1)

for i in range(m):
pr,fr=map(int,input().split())
p[i]=pr
f[i]=fr

def check(k):
dp=[0]*(n+2)
df=[0]*(n+2)
def add(l,r,p,f):
if l>r:
return
dp[l]+=p
dp[r+1]-=p
df[l]+=f
df[r+1]-=f
for i in range(k):
pr,fr=p[i],f[i]
l=pr-fr+1
if l<1:
l=1
r=pr+fr-1
if r>n:
r=n
add(l,pr,1,fr-pr)
add(pr+1,r,-1,fr+pr)
a=0
b=0
for x in range(1,n+1):
a+=dp[x]
b+=df[x]
if a*x+b>h:
return True
return False
if not check(m):
print("No")
exit()
l,r=1,m
while l<r:
mid=(l+r)//2
if check(mid):
r=mid
else:
l=mid+1
print("Yes")
print(l)

J题智乃的幻方

考点：暴力 

思路：按题意模拟即可。

import sys
import math
input=sys.stdin.readline
a=[]
b=[0]*10
ok=True
for _ in range(3):
a1,a2,a3=map(int,input().split())
if a1<1 or a1>9 or a2<1 or a2>9 or a3<1 or a3>9:
ok=False
b[a1]+=1
b[a2]+=1
b[a3]+=1
if b[a1]>1 or b[a2]>1 or b[a3]>1:
ok=False

a.append([a1,a2,a3])
if ok:
if a[0][0]+a[0][1]+a[0][2]==a[1][0]+a[1][1]+a[1][2]==a[2][0]+a[2][1]+a[2][2]==a[0][0]+a[1][0]+a[2][0]==a[0][1]+a[1][1]+a[2][1]==a[0][2]+a[1][2]+a[2][2]==a[0][0]+a[1][1]+a[2][2]==a[0][2]+a[1][1]+a[2][0]:
print("Yes")
else:
print("No")
else:
print("No")