当前位置: 首页 > news >正文

ACWING寒假每日一题python

ACWING寒假每日一题

一、孤独的照片

在这里插入图片描述
一个点一个点的来看,比如对于GHGHG中间的G,找到他的左边的G,以及右边的G的位置,l,r分别等于1,答案就要多加上11
但是如果对于 GHHGHHG 中间的G,我们可以看到l,r等于2,那么就一个中间G的对于他的左半边来说,能拍l-1张照片,右半边也是能拍r-1张,之后左右一起看的话能拍l
r张。
知道这个就好做了,我们只需要把每个G和H点的坐标存起来,然后遍历一编就行了,不过要注意边界,例如对于第一个G点,他的l是等于他的坐标的,那么我们只需要把G[0]设置为-1,这样计算l的时候就会等于G[1](l = g[i] - g[i-1] -1)

具体代码如下

n = int(input())
s = input()
res = 0
g,h = [-1],[-1]  # 第一个点 h[1] - h[1-1]-1 就是h[1]
for i in range(n):if s[i] == 'G':g.append(i)  # 记录G的位置else:h.append(i)  # H的位置
g.append(n)  # 处理右边界, 最后一个点 h[i+1]-h[i]-1 
h.append(n)
for i in range(1,len(g)-1):l = g[i] - g[i-1] - 1 r = g[i+1] - g[i] - 1if l >= 2:res += l-1if r >= 2:res += r-1res += r*l
for i in range(1,len(h)-1):l = h[i] - h[i-1] - 1 r = h[i+1] - h[i] - 1if l >= 2:res += l-1if r >= 2:res += r-1res += r*lprint(res)

二、统计次数

在这里插入图片描述
对于python来说并不难,我们有count函数,其他语言我就不知道了,O(n)时间复杂度

代码如下

n,k = map(int,input().split())
res = 0
for i in range(1,n+1):i = str(i)k = str(k)res += i.count(k)
print(res)

三、上课睡觉

在这里插入图片描述
在这里插入图片描述
对于每组数据,我们从大到小遍历堆数,就是总共要合成成几堆,假设为K堆,那么我们需要的操作就是n-k,因为k从大到小,所以我们找到的一定是操作数最少的。
假设分为k堆,首先要判断总数sum % k 是否等于0,如果不等于代表他不能被k等分,就不行
如果可以的话,因为只有相邻的合并,所以我们从小到大遍历石堆,设置一个遍历m m 去 += w[i],w为石堆,然后如果等于 sum // k 就让m归0,继续往下找,如果m>sum//k 那就肯定不行了,然后最后如果m == 0 代表最后合成的一堆也等于 sum // k ,就成功拉。

PS:可能说的有点乱,总的来说就是需要遍历石堆里的,然后从头到尾合并,都合并成sum//k,如果合并着合并着发现大于sum//k了,那就肯定不行了,因为你如果舍弃掉开头那个,就算你这堆可以等于sum//k,但是你开头那个就没办法和别的石子合并了。因为这堆的开头的那个石子的前面要么没石头,要么它的前面已经合并为sum//k了。

#### 代码如下def solve(w,cnt,totle):if totle % cnt != 0: return False# 如果总数不能除尽堆数,证明这个堆数是不可能的k = totle // cntm = 0for i in range(len(w)):m += w[i]if m > k : return Falseif m == k : m = 0return m == 0    # 如果最后面刚好最后一堆的总和也等于平均数,就返回Trueif __name__ == '__main__':t = int(input())for i in range(t):n = int(input())w = [int(x) for x in input().split()]totle = sum(w)for cnt in range(n,0,-1) : # 遍历堆数 就是要多最多的堆if solve(w,cnt,totle) : print(n - cnt)     # 例如5堆最后分为3堆,就要操作5-2次break

四、学分绩点

在这里插入图片描述
这题也是比较暴力的题,就没什么好说的

代码如下

if __name__ == '__main__':n = int(input())xuefen = [int(x) for x in input().split()]scores = [int(x) for x in input().split()]res = 0for i in range(n):if scores[i] >= 90:res += xuefen[i] * 4.00elif scores[i] >= 85:res += xuefen[i] * 3.7elif scores[i] >= 82:res += xuefen[i] * 3.3elif scores[i] >= 78:res += xuefen[i] * 3.0elif scores[i] >= 75:res += xuefen[i] * 2.7elif scores[i] >= 72:res += xuefen[i] * 2.3elif scores[i] >= 68 :res += xuefen[i] * 2.0elif scores[i] >= 64:res += xuefen[i] * 1.5elif scores[i] >= 60:res += xuefen[i] * 1.0else: res += 0print('{:.2f}'.format(res/sum(xuefen)))

五、奶牛大学

在这里插入图片描述
将每头奶牛愿意出的学费给排序一下,然后一个个去遍历,以第一个,第二个…作为学费,找到最大值,用enumerate就会很方便,例如以第三头牛的愿意出的最大价格做学费,sum = 学费 *(n-i) 。如果有重复的不用担心,例如愿意出的最大价格排好序后是 1 3 3 3 … 那么在计算第一个3的时候,就是学费为3的能赚到钱的最大值,后面两个不会覆盖掉第一个3

代码如下

if __name__ == '__main__':n = int(input())s = [int(x) for x in input().split()]s.sort()maxsum = 0finalmoney = 0for i,money in enumerate(s):sum = money * (n-i)if sum>maxsum:maxsum = sumfinalmoney = moneyprint(maxsum,finalmoney)

六、选数异或

在这里插入图片描述
直接暴力的话肯定会TLE的,我们先预处理一个数组 maxl ,maxl[i] 代表右边界为i, 能容忍的左边界最大是多少,如果最后 l > maxl[r] ,就 say no 了 ,因为你比我能容忍的最大还大。
那要怎么算这个maxl呢,首先如果第i个数的异或x的值假设为b,maxl[i - 1] 表示前一个位置能容忍的最大值,那么maxl[i] 是不是要等于 max( maxl[i-1] , b的最后一个位置)。
那么我们现在只需要算出前面出现过的数的最后一个位置就行了,再建立一个endpos表示每个数的最后一个位置。在遍历的时候让endpos[arr[i]] = i 就行(arr为原数组)
又因为l和r是从1开始的,所以我们的原始数组arr应该也从坐标1开始,在第一个位置上加个-1就行。

具体代码如下

## a ^ b = x  --> a ^ x = b
N = 10**7
if __name__ == '__main__':n,m,x = map(int,input().split())endpos = [-1] * Narr = [-1]+[int(x) for x in input().split()]maxl = [-1] * (n+2)for i in range(1,n+1):# 对于每个位置来说,他能容许的左边的最大值(l 不能比这个再大了,可以在它的左边)是 maxl[i - 1] 或者 它目前这个位置的数异或值的最后一个位置maxl[i] = max(maxl[i-1] , endpos[arr[i]^x])  # arr[i] ^ x 是你这个点想要的那个b arr[i] ^ b = x,endpos[b] 就表示b出现的最后位置endpos[arr[i]] = i  # 记录一下每个数字出现的最后位置,每个重复数字都记录的是后面那个数字的下标for i in range(m):l,r = map(int,input().split())if (l != r and maxl[r] >= l):print('yes')else: print('no')
http://www.lryc.cn/news/7062.html

相关文章:

  • 御黑行动来袭--助力三月重保,构筑安全防线!
  • JavaScript HTML DOM 元素 (节点)
  • mybatis-plus ---2
  • 如何在Qt中设置背景图片,且不覆盖其它控件
  • PMP考前冲刺2.14 | 2023新征程,一举拿证
  • feign进行文件上传报错解决方案及有多个入参时的注意事项
  • java 枚举类型enum的用法详解
  • Java 基础面试题——关键字
  • C++——运算符重载
  • 前端食堂技术周刊第 70 期:Volar 的新开端、Lighthouse 10、良好的组件设计、React 纪录片、2022 大前端总结
  • react路由详解
  • mysql数据库完全备份和增量备份与恢复
  • CF1667E Centroid Probabilities
  • 全网详细总结com.alibaba.fastjson.JSONException: syntax error, position at xxx常见错误方式
  • 快速部署个人导航页:美好的一天从井然有序开始
  • 【Python】如何在 Python 中使用“柯里化”编写干净且可重用的代码
  • ROS笔记(4)——发布者Publisher与订阅者Subscribe的编程实现
  • Linux进程概念(一)
  • Leetcode.1124 表现良好的最长时间段
  • 达梦数据库会话、事务阻塞排查步骤
  • sqlServer 2019 开发版(Developer)下载及安装
  • 使用Arthas定位问题
  • 性能测试之tomcat+nginx负载均衡
  • 【手写 Vuex 源码】第十一篇 - Vuex 插件的开发
  • opencv基础知识和绘图图形
  • 15- 决策回归树, 随机森林, 极限森林 (决策树优化) (算法)
  • Flink相关的记录
  • 配置可视化-基于form-render的无代码配置服务(一)
  • Java 代理模式详解
  • 知识付费小程序怎么做_分享知识付费小程序的作用