最便宜的网站建设,网站备案负责人幕布照,网站建设技术入股合同,网站建设与管理试题与答案[acwing周赛复盘] 第 90 场周赛20230211 补 一、本周周赛总结二、 4806. 首字母大写1. 题目描述2. 思路分析3. 代码实现三、4807. 找数字1. 题目描述2. 思路分析3. 代码实现四、4808. 构造字符串1. 题目描述2. 思路分析3. 代码实现六、参考链接一、本周周赛总结
T1 模拟T2 模拟…
[acwing周赛复盘] 第 90 场周赛20230211 补 一、本周周赛总结二、 4806. 首字母大写1. 题目描述2. 思路分析3. 代码实现三、4807. 找数字1. 题目描述2. 思路分析3. 代码实现四、4808. 构造字符串1. 题目描述2. 思路分析3. 代码实现六、参考链接一、本周周赛总结
T1 模拟T2 模拟T3 前缀函数不会写直接暴力。
二、 4806. 首字母大写
链接: 4806. 首字母大写
1. 题目描述 2. 思路分析
试图title但是不对。 只好模拟。
3. 代码实现
# Problem: 首字母大写
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4809/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sys
import bisect
import random
import io, os
from bisect import *
from collections import *
from contextlib import redirect_stdout
from itertools import *
from array import *
from functools import lru_cache
from types import GeneratorType
from heapq import *
from math import sqrt, gcd, inf
if sys.version 3.8: # ACW没有combfrom math import combRI lambda: map(int, sys.stdin.buffer.readline().split())
RS lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST lambda: list(RI())
DEBUG lambda *x: sys.stderr.write(f{str(x)}\n)MOD 10**9 7# ms
def solve():s, RS()print(s[0].upper() s[1:])if __name__ __main__:solve()
三、4807. 找数字
链接: 4807. 找数字
1. 题目描述 2. 思路分析
wa麻了。建立长度m的数组作为m位试图给所有位置贪心的填上数最大好办从左到右优先填9。小的其实就是把mx转过来但是第一位不能是0因此找最后一位不是0的位置借一个1过来填到最后一位。注意s0的情况m可以是1.
3. 代码实现
# Problem: 找数字
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4810/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sys
import bisect
import random
import io, os
from bisect import *
from collections import *
from contextlib import redirect_stdout
from itertools import *
from array import *
from functools import lru_cache
from types import GeneratorType
from heapq import *
from math import sqrt, gcd, infif sys.version 3.8: # ACW没有combfrom math import combRI lambda: map(int, sys.stdin.buffer.readline().split())
RS lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST lambda: list(RI())
DEBUG lambda *x: sys.stderr.write(f{str(x)}\n)MOD 10 ** 9 7# ms
def solve():m, s RI()if s 0 and m 1:return print(0 0)if s 1 or 9 * m s:return print(-1 -1)t sa [0] * mi 0while t:x min(t, 9)a[i] xt - xi 1mx .join(map(str, a))if a[-1] 0:for i in range(m - 1, -1, -1):if a[i]:a[-1] 1a[i] - 1breakprint(.join(map(str, a[::-1])), mx)if __name__ __main__:solve()四、4808. 构造字符串
链接: 4808. 构造字符串
1. 题目描述 2. 思路分析
读完题立刻想到前缀函数/next数组但我不会写。
好在这题数据量小可以暴力。后缀数组可以求出每个前缀是否能和后缀匹配的最大长度。即如果前缀是xs[:x]是否s[-x:]。只要相同就可以无限在后边追加后半部分(包括中间部分)即可。比如形如aba的串(其中ab均代表一段)只需要往后添加ba,变成ababababa…准备记个前缀函数模板。 代码里两种方法都能过。
3. 代码实现
# Problem: 构造字符串
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4811/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sys
import bisect
import random
import io, os
from bisect import *
from collections import *
from contextlib import redirect_stdout
from itertools import *
from array import *
from functools import lru_cache
from types import GeneratorType
from heapq import *
from math import sqrt, gcd, infif sys.version 3.8: # ACW没有combfrom math import combRI lambda: map(int, sys.stdin.buffer.readline().split())
RS lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST lambda: list(RI())
DEBUG lambda *x: sys.stderr.write(f{str(x)}\n)MOD 10 ** 9 7def prefix_function(s):计算s的前缀函数,复杂度o(n)n len(s)pi [0] * nfor i in range(1, n):j pi[i - 1]while j 0 and s[i] ! s[j]:j pi[j - 1]if s[i] s[j]:j 1pi[i] jreturn pi
# ms
def solve1():n, k RI()t, RS()mx 0for i in range(1, n):if t[:i] t[-i:]:mx iif mx 0:return print(t * k)suf t[mx:]print(t suf * (k - 1))
# ms
def solve():n, k RI()t, RS()mx prefix_function(t)[-1]if mx 0:return print(t * k)suf t[mx:]print(t suf * (k - 1))if __name__ __main__:solve()六、参考链接
无
