当前位置:网站首页>Codeforce:c. sum of substrings
Codeforce:c. sum of substrings
2022-07-04 14:27:00 【White speed Dragon King's review】
analysis
We want to make f Minimum
Boundary situation : No, 1 The answer is always 0
Then each 1, If in the middle, the contribution must be 1 + 10 = 11
The only way to reduce the contribution is to put it on one end
Put it on your head : Contribution becomes 10
Put at the end : Sharing becomes 1
So we count s all 1 The closest distance from the head and tail d1 and d2
Then go to the end first
Judge k Whether the value of is greater than or equal to d1 + d2, d2, d1 It is divided into four states
Specially , If only one 1 Under the circumstances , It's impossible to go head and tail again
So this situation should be greater than or equal to d1 + d2 Just go to d2 that will do
ac code
import sys
input = sys.stdin.readline
for _ in range(int(input())):
n, k = list(map(int, input().split()))
s = input()
cnt_1 = 0
for c in s:
if c == '1':
cnt_1 += 1
if cnt_1 == 0:
print(0)
continue
d1, d2 = 0, 0 # d1 from head, d2 from tail
for i in range(n):
if s[i] == '1':
d1 = i
break
for i in range(n):
if s[n - 1 - i] == '1':
d2 = i
break
# 1: not change
# 2: go to head
# 3: go to tail
# 10: go to tail and head
# we are delighted to go to tail first, and secondly go to head
flag = 1
if k >= d1 + d2:
flag = 10
elif k >= d2:
flag = 3
elif k >= d1:
flag = 2
else:
flag = 1
# different cases
ans = 0
if flag == 10:
if cnt_1 >= 2:
ans = 1 + 10 + 11 * (cnt_1 - 2) # cnt_1 >= 2
else:
ans = 1
elif flag == 3:
ans = 1 + 11 * (cnt_1 - 1)
elif flag == 2:
ans = 10 + 11 * (cnt_1 - 1)
else:
ans = 11 * cnt_1
print(ans)
summary
thinking + contribution + Boundary treatment
边栏推荐
- Opencv3.2 and opencv2.4 installation
- Some problems and ideas of data embedding point
- flink sql-client.sh 使用教程
- R language uses dplyr package group_ The by function and the summarize function calculate the mean and standard deviation of the target variables based on the grouped variables
- Common content type correspondence table
- 统计php程序运行时间及设置PHP最长运行时间
- Leetcode t49: grouping of alphabetic words
- The font of markdown grammar is marked in red
- 迅为IMX6Q开发板QT系统移植tinyplay
- sql优化之explain
猜你喜欢
Digi重启XBee-Pro S2C生产,有些差别需要注意
[FAQ] summary of common causes and solutions of Huawei account service error 907135701
docker-compose公网部署redis哨兵模式
Data warehouse interview question preparation
Innovation and development of independent industrial software
The implementation of OSD on rk1126 platform supports color translucency and multi-channel support for Chinese
gin集成支付宝支付
Nowcoder rearrange linked list
Supprimer les lettres dupliquées [avidité + pile monotone (maintenir la séquence monotone avec un tableau + Len)]
商业智能BI财务分析,狭义的财务分析和广义的财务分析有何不同?
随机推荐
Excel quickly merges multiple rows of data
Migration from go vendor project to mod project
10.(地图数据篇)离线地形数据处理(供Cesium使用)
Leetcode T49: 字母异位词分组
软件测试之测试评估
R语言ggplot2可视化:gganimate包创建动画图(gif)、使用anim_save函数保存gif可视化动图
MySQL的存储过程练习题
商業智能BI財務分析,狹義的財務分析和廣義的財務分析有何不同?
第十七章 进程内存
R language uses bwplot function in lattice package to visualize box plot and par Settings parameter custom theme mode
学内核之三:使用GDB跟踪内核调用链
Use of arouter
[FAQ] summary of common causes and solutions of Huawei account service error 907135701
利用Shap值进行异常值检测
2022 game going to sea practical release strategy
R语言ggplot2可视化:gganimate包创建动态折线图动画(gif)、使用transition_reveal函数在动画中沿给定维度逐步显示数据
Ws2818m is packaged in cpc8. It is a special circuit for three channel LED drive control. External IC full-color double signal 5v32 lamp programmable LED lamp with outdoor engineering
【MySQL从入门到精通】【高级篇】(四)MySQL权限管理与控制
R语言使用epiDisplay包的dotplot函数通过点图的形式可视化不同区间数据点的频率、使用by参数指定分组参数可视化不同分组的点图分布
为什么图片传输要使用base64编码