真捐款去了，好長時間沒練了，感覺腦子和手都不轉悠了。$BF$ 賽時都寫假了，$G$ 也只寫了爆搜。

題解其實隊友都寫好了，我就粘一下自己的代碼，稍微提點個人的理解水一篇題解

隊友題解

---

B

思路：

我是直接枚舉八個段是否填 $0$，確定哪些段填 $0$ 后，縮寫形式也就唯一確定了。接下來我們只需要確定填非 $0$ 的段的長度和可能數。

確定填 $0$ 段和冒號的長度重點在于確定縮寫的位置，無外乎三種情況：

1. 開頭或結尾的連續 $0$ 段縮寫
2. 中間的連續 $0$ 段縮寫
3. 不縮寫（其實只要縮寫就一定不差于不縮寫）

假設總共有 $n$ 段（其實就是 $8$），總共有 $num0$ 個 $0$，開頭或結尾的最長連續 $0$ 段長度為 $ans1$，中間的最長連續 $0$ 段長度為 $ans2$，那么三種情況的答案分別是：

1. 除縮寫部分的剩余部分長度為 $n?ans1$，需要 $n?ans1?1$ 個冒號分割。縮寫需要 $2$ 個冒號。剩余未被縮寫的 $0$ 的個數為 $num0?ans1$，因此總長度為 $(n?ans1?1)+2+(num0?ans1)$
2. 除縮寫部分的剩余部分總長度為 $n?ans2$，需要 $n?ans2?2$ 個冒號分割（因為是左右兩個部分）。縮寫需要 $2$ 個冒號。剩余未被縮寫的 $0$ 的個數為 $num0?ans2$，因此總長度為 $(n?ans2?2)+2+(num0?ans2)$
3. $n?1+num0$

非零段長度變化時，以外的部分（填 $0$ 段和冒號）的長度是不變的，假設這個填 $0$ 段和冒號總長度是 $len$。接下來需要確定非 $0$ 的段的所有情況的總長度，這個部分我們直接爆搜，假設有 $pos$ 個非零段，每個段分別有 $16^1?16^0=15,16^2?16^1=240,16^3?16^2=3840,16^4?16^3=61440$ 種情況，長度分別為 $1,2,3,4$，這樣爆搜的次數是 $4^{pos}\le 4^8=65536$ 次，可以跑得動。

另外因為全 $0$ 段的時候比較特殊，所以單獨計數。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;int get_len(string s){//得到簡化后的冒號和0位置的總長度 int n=s.length();int ans1=0,ans2=0,num0=0;for(int i=0;i<n;i++)if(s[i]=='0')num0++;for(int i=0;i<n;i++)if(s[i]!='0'){ans1=max(ans1,i);break;}for(int i=n-1;i>=0;i--)if(s[i]!='0'){ans1=max(ans1,n-i-1);break;}for(int l=1,r=0;l<n-1;l=r+1){r++;while(s[r]=='0' && r<n-1)r++;ans2=max(ans2,r-l);}
//	cout<<ans1<<" "<<ans2<<" "<<num0<<endl;return min(min(n-ans1-1+2+(num0-ans1),n-ans2-2+2+(num0-ans2)),n-1+num0);
}ll tm[]={15,240,3840,61440};
ll len;//某種選取情況的長度 
vector<ll> take;//某種選取情況 
ll tot;//所有情況的總長度 
void dfs(int pos){if(pos<=0){ll t=1;for(auto x:take)t=t*x%mod;//這種選取情況下的情況數 tot=(tot+t*len%mod)%mod;return;}for(int i=0;i<4;i++){len+=i+1;take.push_back(tm[i]);dfs(pos-1);take.pop_back();len-=i+1;}
}signed main(){ll ans=2; for(int i=1;i<(1<<8);i++){string s;for(int j=0;j<8;j++)s += "01"[(i>>j)&1];len=get_len(s);int num1=0;for(int i=0;i<s.length();i++)if(s[i]=='1')num1++;dfs(num1);ans=(ans+tot)%mod;tot=0;
//		cout<<s<<" "<<get_len(s)<<" "<<num1<<" "<<tot<<endl;
//		cout<<ans<<endl;}cout<<ans;return 0;
} 

---

C

code：

import sys
input = sys.stdin.readlineh, w = map(int, input().split())
s = "2025" * 1145
for i in range(h):print(s[i:i+w])

---

D

思路：

$python$ 的 $sort$ 只能指定按照某個位置的值進行排序，不能對兩個數做操作來確定大小。

為了解決這個問題可以用 functools 的 cmp_to_key，或者重寫類的 __lt__ 方法。

code：

from functools import cmp_to_keyn = int(input())
s = [bin(x)[2:] for x in range(1, n+1)]def cmp(a: str, b: str)-> int:if a+b < b+a:return -1elif a+b == b+a:return 0else:return 1s.sort(key=cmp_to_key(cmp), reverse=True)
print(int("".join(s), 2))

---

E

思路：

隊友寫假了，這個水是不能往前面的位置倒的，所以就不能求平均數了。

這個題正解是二分答案，很板。

大體思路就是二分答案，對一個需要驗證的答案，如果一個位置的水量高于答案，就把多余的部分都給后面。如果這個位置水量不夠答案，就說明通過前面的努力是不夠填滿它的，這個答案就不成立。

如果不會寫整數二分，可以在 $l,r$ 范圍縮到足夠小時，對小范圍進行暴力枚舉驗證。

code：

import copy
import sys
input = sys.stdin.readline
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))def check(height):t = copy.deepcopy(a)for i in range(n):if t[i] < height:return Falseif i + k < n:t[i + k] += t[i] - heightreturn Truel, r = 1, 10**20
while l < r:mid = (l + r + 1) // 2if check(mid):l = midelse:r = mid - 1print(l)"""
8 3
5 6 4 8 3 4 1 9"""

---

F

思路：

賽時寫完發現想假了，不過沒時間了就直接交了。思路和隊友是一樣的，直接看他的講解吧。

這題 $n=1000$ 還能暴力啊……

不怎么會寫暴搜，暴力杯吃大虧。

code：

n = int(input())
cnt = [0]*7
for x in input().split():cnt[min(6, x.count("6"))] += 1# n = 1000
# cnt = [200 for _ in range(7)]visit = dict()
ans, cur = 0, 0def dfs(status):# status狀態下的最大值global ans, curif len(tuple(x for x in status if x < 0)) > 0:returnif visit.get(tuple(status)):return visit.get(tuple(status))if sum(status) // 2 + cur <= ans:returnif sum([i*x for i, x in enumerate(status, start=1)]) // 6 + cur <= ans:return# print(status)ans = max(ans, cur)for i in range(1, 6):for j in range(max(6-i, i), 6):status[i - 1] -= 1status[j - 1] -= 1cur += 1dfs(status)cur -= 1status[i - 1] += 1status[j - 1] += 1for i in range(1, 6):for j in range(i, 6):for k in range(max(6-i-j, j), 6):status[i - 1] -= 1status[j - 1] -= 1status[k - 1] -= 1cur += 1dfs(status)cur -= 1status[i - 1] += 1status[j - 1] += 1status[k - 1] += 1visit[tuple(status)] = curdfs(cnt[1:6])print(ans + cnt[6])"""
8
666666 666 666 666 66 6 6 6"""

---

G

思路：

隊友說是染色，其實就是并查集合并連通塊，并額外處理一個連通塊內所有點的最大高度（因為一個連通塊內是互相可達的）

假設我們處理前面一段高度，得到了若干組，你會發現這些組的值域互不覆蓋，且位置越靠后，值越大。

當我們加入一個更高高度的點時（比前面所有高度都高），因為不能到達前面任何一個點，它就會成為新的組。

當我們加入一個低于前面若干高度的點時，它就會和前面所有存在高于它的點的組進行合并，成為一個組。

發現我們其實只需要知道每個組的最大高度就可以了，所以我們可以用單調棧來維護每個組的最大值，并從頂到底按照從大到小的順序放好。

之后每一行跑一遍，每一列跑一遍就好了。

code：

原代碼的下標映射有些混亂，所以改成了從 $(0,0)$ 到 $(n?1,m?1)$

n, m = map(int, input().split())mp = [[0] * m for _ in range(n)]
for i in range(n):mp[i][:] = map(int, input().split())f = [0] * (n*m)
maxh = [0] * (n*m)
for i in range(n*m):f[i] = imaxh[i] = mp[i // m][i % m]def to_idx(x, y):return x*m+ydef findf(x):if f[x] == x:return xelse:f[x] = findf(f[x])return f[x]def merge(u, v):fu, fv = findf(u), findf(v)maxh[fu] = max(maxh[fu], maxh[fv])f[fv] = fufor i in range(n):stack = list()  # 高度 并查集位置for j in range(m):idx = to_idx(i, j)maxx = mp[i][j]while stack and stack[-1][0] > mp[i][j]:maxx = max(maxx, stack[-1][0])merge(stack[-1][1], idx)stack.pop()stack.append((maxx, idx))for j in range(m):stack = list()  # 高度 并查集位置for i in range(n):idx = to_idx(i, j)maxx = mp[i][j]while stack and stack[-1][0] > mp[i][j]:maxx = max(maxx, stack[-1][0])merge(stack[-1][1], idx)stack.pop()stack.append((maxx, idx))ans = 0
for i in range(n):for j in range(m):fa = findf(to_idx(i, j))ans += maxh[fa]print("{:.6f}".format(ans/(n*m)))"""
2 2
1 4
4 32 3
2 4 1
4 2 3"""

---

H

思路：

感覺 $H<F<G$，這題是個標準的反悔貪心。

優先隊列還是前一天晚上臨時看的。

感覺沒什么好寫的，就丟個類似的題吧 你是銀狼