前言
去年参加过14届的c/c++组,荣幸获得省四(doge),其实当时还是挺失望的,一是没想到连个省三也没混上,然后指望水个奖来挽救一下英语挂科,最后在英语补考和准备比赛两件事上都没抓住哈哈哈,可能是低估去年的难度了,填空一个没对,大题只暴力了一个,分数大概是个位数。
所以,今年我跑来Python组了,说到底我还是比较讨厌算法的,抱着水一水的态度来到了Python组,结果居然拿到了省一。。。。。。
比赛过程
今年似乎沈理校赛免报名费的名额比去年少了,不过我还是白嫖到了300报名费(和去年一样哈哈)。
A.穿越时空之门 √100%
签到题,直接按题里给的要求来,可能考察了一下进制转换,我用的来回除的方法,最大2024直接暴力算,答案63。
def T(n,nu):
arr = []
while n >= nu:
tmp = n%nu
arr.append(tmp)
n //=nu
arr.append(n)
arr.reverse()
return arr
cnt = 0
for i in range(1,2025):
if sum(T(i,2)) == sum(T(i,4)):
cnt+=1
print(cnt)
B.数字串个数 ×
考察排列组合,这玩意我高中的时候就没学明白,第一个思路是拿Excel直接挑两个位置放3,7 然后算A(10000,2)然后成剩下每位×9,当然肯定错了,情况考虑少了,直接错!
base = 49995000
s = 9**(10000-2)
print((base*s)%(10**9+7))
C.连连看 √50% ?
这题思路比较简单,直接按照题里面要求暴力算了,当然最好的解法是以每个对角线来遍历,我写的只能过一半把大概。
n,m = map(int,input().split())
arr = []
for i in range(n):
tmp = list(map(int,input().split()))
arr.append(tmp)
def solve1():
cnt = 0
maxw = min(n,m)
for i in range(n):
for j in range(m):
if arr[i][j] == 0:
break
for k in range(1,maxw):
if i-k >= 0 and j+k <m and arr[i-k][j+k] == arr[i][j]:
arr[i][j] == 0
arr[i-k][j+k] == 0
cnt +=1
if i-k >= 0 and j-k >=0 and arr[i-k][j-k] == arr[i][j]:
arr[i][j] == 0
arr[i-k][j-k] == 0
cnt +=1
if i+k < n and j+k <m and arr[i+k][j+k] == arr[i][j]:
arr[i][j] == 0
arr[i+k][j+k] == 0
cnt +=1
if i+k < n and j-k >=0 and arr[i+k][j-k] == arr[i][j]:
arr[i][j] == 0
arr[i+k][j-k] == 0
cnt +=1
print(cnt)
if n<=50 and m<=50:
solve1()
else:
solve1()
D.神奇闹钟 √100%
考察datetime库的使用?哈哈,还好考试前用过这这个库搞开发,不过怎么把字符串解析为datatime对象我在考场上没想起来,所以就手动解析了。思路是计算当前时间距离纪元时间的时差再对x取余,当前时间减去这个余数即为所求。
import datetime
t = int(input())
for i in range(t):
date,time,x = map(str,input().split())
year,month,day = map(int,date.split('-'))
h,m,s = map(int,time.split(':'))
starttime = datetime.datetime(year=1970,month=1,day=1)
nowtime = datetime.datetime(year=year,month=month,day=day,hour=h,minute=m)
allo = nowtime - starttime
_time = datetime.timedelta(minutes= ((allo.days * 24 * 60 ) + allo.seconds//60)%int(x))
print(nowtime-_time)
E.蓝桥村的真相 ×
考察找规律,不过我理解错了一部分地方,也就是断言的意思,我的错误理解是如果是假话那么在他之后的任何情况都有可能,但是正确意思是在他之后的情况一定不是断言的这种情况,导致我找规律出错,不过无妨,就算我找对了,我还是用的dfs暴搜,也拿不到几分哈哈,这题数据范围10的18次幂,我居然都没想到答案是n的线性关系。。。。。。
t = int(input())
cnt = 0
def check(s):
if s[0] == 0 and s[1] == 0 and (s[2]==1 or s[2]==0):
return True
elif s == [1,0,1]:
return True
elif s[0:2] == [0,1] and (s[2] == 0 or s[2] == 1):
return True
elif s == [1,1,0]:
return True
else:
return False
def dfs(arr,i,n,num):
global cnt
if i == n:
if check([arr[n-2],arr[n-1],arr[0]]) and check([arr[n-1],arr[0],arr[1]]):
cnt += num
print(arr)
return
sertwo = arr[i-2:i+1]
if sertwo == [0,0] or sertwo == [0,1]:
arr.append(1)
dfs(arr,i+1,n,num)
arr.pop()
arr.append(0)
dfs(arr,i+1,n,num+1)
arr.pop()
elif sertwo == [1,0]:
arr.append(1)
dfs(arr,i+1,n,num)
arr.pop()
elif sertwo == [1,1]:
arr.append(0)
dfs(arr,i+1,n,num+1)
arr.pop()
for i in range(t):
n = int(input())
arr1 = [0,0]
arr2 = [1,0]
arr3 = [0,1]
arr4 = [1,1]
dfs(arr1,2,n,2)
dfs(arr2,2,n,1)
dfs(arr3,2,n,1)
dfs(arr4,2,n,0)
print(cnt)
cnt = 0
F.魔法巡游 ×
完全不会,跳过!
print(5)
G.缴纳过路费 ×
完全不会,跳过!
print(5)
H.纯职业小组 √ 1% ?
这题是 贪心?
思路是先从最多的小队里面里找,再一个一个挑,挑到组数大于K为止,当然是错的,在dotcpp只过了一个测试点。。。。
t = int(input())
for _ in range(t):
n,k = map(int,input().split())
arr = {}
tmp = {}
man = 0
cnt = 0
for _ in range(n):
a,b = map(int,input().split())
if arr.get(a)== None:
arr[a] = b
else:
arr[a] += b
arr = {k: v for k, v in sorted(arr.items(), key=lambda item: item[1])}
for i in arr.keys():
if arr[i]<3:
if tmp.get(i) == None:
tmp[i] = arr[i]
man += arr[i]
else:
tmp[i] += arr[i]
man += arr[i]
for i in arr.keys():
if arr[i] >= 3:
if tmp.get(i) == None:
tmp[i] = 2
man += 2
else:
tmp[i] += 2
man += 2
for i in arr.keys():
if tmp.get(i) == None:
tmp[i] = 1
man += 1
else:
tmp[i] += 1
man += 1
if tmp[i] >=3:
cnt+=1
if cnt>=k:
break
if cnt>=k:
print(man)
else:
print(-1)
写在最后
如你所见,我大概只拿了20分出头,在辽宁省python B组居然排第九,可见py组水分之大,如果你不想深耕算法竞赛,对开发更感兴趣,我相信python组和java组更适合你!