浙江机电职业技术大学第九届程序设计竞赛 个人题解

验后 除四星倍增、五星dp没写 感觉

Easy：T1、T2、T3、T10、T12、T9

Mid: T4、T5、T6、T7

Hard:T11、T8

T1.阿兔与拼好饭

知识点： 贪心

简要题意 ： 每次拼团需凑满恰好 3 个人，每次配送为 3 份饭，每位参与者可以选择参与他人发起的拼团或者发起拼团，每个人两种操作只能各执行一次，问 n 个人能享用多少份饭？

思路：考虑贪心，手玩小样例会发现

C++参考代码：

#include <bits/stdc++.h>

using i64 = long long ;

void solve() {
	int n ;
	std::cin >> n ;
	if ( n <= 2 ) {
		std::cout << 0 << '\n' ;
	} else if ( n == 3 ) {
		std::cout << 3 << '\n' ;
	} else if ( n == 4 ) {
		std::cout << 6 << '\n' ;
	} else {
		std::cout << 6 + (i64)(n - 4) / 2 * 3 << '\n' ;
	}
}

int main()
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;

    int t ;
    std::cin >> t ;
    while ( t-- ) {
        solve() ;
    }

    return 0 ; 
}

T2.阿兔与转经筒

知识点： 前缀和、二分

简要题意 ： 给定长度为 的数组 ，有 次询问，每次询问给定一个正整数 ，表示取 轮数组内的非零数，每取一轮后每个数减 ，问 轮后结果是多少？

思路：首先对数组升序后，预处理出两个前缀和数组，其中 表示数组前 个元素和， 表示数组前 个元素每个元素为 的和。对于每个询问二分出第一个大于 的下标 ，显然对于下标 内的每个数的贡献均是 因此此部分的贡献为 , 对于下标 部分我们根据简单的容斥得到贡献为 。

C++参考代码 :

#include <bits/stdc++.h>

using i64 = long long ;

const int mod = 1000000007 ;
const int N = 2e5 + 10 ;

int n , q , a[N] , pre[N] , b[N] ;

int qpow(int a,int b) {
	int ret = 1 ;
	while ( b ) {
		if ( b & 1 ) ret = (i64) ret * a % mod ;
		a = (i64) a * a % mod ;
		b >>= 1 ;
	}
	return ret ;
}
int inv(int x) {
	return qpow(x , mod - 2) ;
}

void solve() {
    std::cin >> n >> q;
    for(int i = 1 ; i <= n ; ++ i) {
    	std::cin >> a[i] ;
    }
    std::sort(a + 1 , a + n + 1) ;
    for(int i = 1 ; i <= n ; ++ i) {
    	pre[i] = ((i64)pre[i - 1] + a[i]) % mod ;
    	b[i] = (b[i - 1] + (__int128)a[i] * (a[i] + 1) * inv(2) % mod) % mod ;
	}
    for(int _ = 1 , r ; _ <= q ; ++ _) {
    	std::cin >> r ;
    	auto x = std::upper_bound(a + 1 , a + n + 1 , r - 1) - a - 1 ;

    	int y1 = (i64)(pre[n] - pre[x]) * r % mod ;
    	int y2 = b[x] ;
    	int y3 = ((__int128)(n - x) * r * (r - 1) * inv(2) % mod) ;
		std::cout << ((y1 + y2 - y3) % mod + mod) % mod << '\n' ;
    }
}

int main()
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;

    int t = 1 ;
    // std::cin >> t ;
    while ( t-- ) {
        solve() ;
    }

    return 0 ; 
}

T3.阿兔与璀璨宝石

知识点 贪心

简要题意 ：有三种卡牌，每种卡牌有两个属性(价格 and 颜色)，每种卡牌所对应的颜色可作为购买卡牌时抵消对应颜色的道具，初始时没有任何颜色的宝石，给定 张卡牌问能获取最多的卡牌数是多少 ？

思路：贪心，设手中当前三种颜色的卡牌数量为 ，有一个显然的贪心策略对卡牌按照所需各个颜色宝石之和升序排列之和依次尝试能不能减免到 0 即白嫖到，注意若此时 成立则可以break了后面是不可能白嫖的。

C++参考代码：

#include <bits/stdc++.h>

using i64 = long long ;

const int N = 2e5 + 10 ;

struct node
{
	char color ;
	int x , y , z ;
	bool operator < (const node &p) const {
		return x + y + z < p.x + p.y + p.z ;
	}
} a[N] ;

void solve() {
    int n ;
    std::cin >> n ;

    for(int i = 1 ; i <= n ; ++ i) {
    	std::cin >> a[i].color >> a[i].x >> a[i].y >> a[i].z ;
    }

    std::sort(a + 1 , a + 1 + n) ;

    int x = 0 , y = 0 , z = 0 , result = 0 ;

    std::set<int> S;

    for(int i = 1 ; i <= n ; ++ i) {
    	if ( x >= a[i].x && y >= a[i].y && z >= a[i].z ) {
    		if ( a[i].color == 'R' ) {
    			++x ;
    		} else if ( a[i].color == 'G' ) {
    			++y ;
    		} else {
    			++z ;
    		}
    		++ result ;
    	} else {
    		S.insert(i) ;
    	}

    	std::set<int> del ;
    	for(auto &p : S) {
    		if (x >= a[p].x && y >= a[p].y && z >= a[p].z ) {
    			if (a[p].color == 'R') {
    				++ x ;
    			} else if ( a[p].color == 'G' ) {
    				++ y ;
    			} else {
    				++ z ;
    			}
    			++ result ;
    			del.insert(p) ;
    		}
    	}
    	for(auto &p : del) {
    		S.erase(p) ;
    	}

    	if (i > 1 && a[i].x + a[i].y + a[i].z - x - y - z > 1) {
    		break ;
    	}
    }

    std::cout << result << '\n' ;
}

int main()
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;

    int t = 1 ;
    // std::cin >> t ;
    while ( t-- ) {
        solve() ;
    }

    return 0 ; 
}

T4.阿兔与战局

知识点：DS、中位数定理

中位数定理 : 如果有一个数轴，数轴上有若干个点。要在数轴上找一点，使得它到各个点的距离之和最短。中位数就是最优解。中位数有这样的性质 ：所有数与中位数的绝对差之和最小。中位数是数列中间的那个数，或者是中间的那两个数之一。

简要题意 ：三种操作单点加、单点删、查询 。

思路：显然根据中位数定理可知 x 取到当前数组中的中位数是最优的即答案。则该题即涉及到单点修改+区间查询。

C++参考代码：

#include <bits/stdc++.h>

using i64 = long long ;

#define ls ( x << 1 )
#define rs ( x << 1 | 1 )

const int N = 2e5 + 10 ;

int n , bin[N] ;
struct Q {
	std::string opt ;
	int val , num ;
} a[N] ;
i64 sum[N << 2] ;
int cnt[N << 2] ;
void update(int x) {
	sum[x] = sum[ls] + sum[rs] ;
	cnt[x] = cnt[ls] + cnt[rs] ;
}
void modify(int pos,int v,int p,int l,int r,int x) {
	if ( l == r ) {
		sum[x] = std::max(0ll , sum[x] + v);
		cnt[x] = std::max(0 , cnt[x] + p);
		return ;
	}
	int mid = (l + r) >> 1 ;
	if ( pos <= mid ) modify(pos , v , p , l , mid , ls) ;
	else modify(pos , v , p , mid + 1 , r , rs) ;
	update(x) ;
}
i64 query(int A,int B,int l,int r,int x) {
	if ( A > B ) return 0 ;
	if ( A <= l && r <= B ) return sum[x] ;
	int mid = (l + r) >> 1 ;
	i64 ans = 0 ;
	if ( A <= mid ) ans += query(A , B , l , mid , ls) ;
	if ( mid < B ) ans += query(A , B , mid + 1 , r , rs) ;
	return ans ;
}
int get(int A,int B,int l,int r,int x) {
	if ( A > B ) return 0 ;
	if ( A <= l && r <= B ) return cnt[x] ;
	int mid = (l + r) >> 1 , ans = 0 ;
	if ( A <= mid ) ans += get(A , B , l , mid , ls) ;
	if ( mid < B ) ans += get(A , B , mid + 1 , r , rs) ;
	return ans ;
}
int get_mid(int A,int B,int k,int l,int r,int x) {
	if ( l == r ) return l ;
	int mid = (l + r) >> 1 ;
	if ( cnt[ls] >= k ) {
		return get_mid(A , B , k , l , mid , ls) ;
	}
	if ( cnt[ls] < k ) {
		return get_mid(A , B , k - cnt[ls] , mid + 1 , r , rs) ;
	}
	return 0 ;
}

void solve() {
	std::cin >> n ;

	for(int i = 1 ; i <= n ; ++ i) {
		std::cin >> a[i].opt ;
		if (a[i].opt == "query") {
			a[i].val = 0 ;
		} else {
			std::cin >> a[i].val ;
		}
		bin[i] = a[i].val ;
	}
	std::sort(bin + 1 , bin + 1 + n) ;
	int m = std::unique(bin + 1 , bin + 1 + n) - bin - 1 ;

	for(int i = 1 ; i <= n ; ++ i) {
		int val = std::lower_bound(bin + 1 , bin + 1 + m , a[i].val) - bin ;
		if ( a[i].opt == "add" ) {
			modify(val , a[i].val , 1 , 1 , m , 1) ;
		} else if ( a[i].opt == "remove" ) {
			modify(val , -a[i].val , -1 , 1 , m , 1) ;
		} else {
			a[i].num = cnt[1] ;
			val = get_mid(1 , m ,(a[i].num + 1) / 2 , 1 , m , 1) ;
			std::cout << query(val , m , 1 , m , 1) - query(1 , val - 1 , 1 , m , 1) + (get(1 , val - 1 , 1 , m , 1) - get(val , m , 1 , m , 1)) * bin[val] << '\n' ;  
		}
	}
}

int main()
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;

    int t = 1 ;
    // std::cin >> t ;
    while ( t-- ) {
        solve() ;
    }
    return 0 ; 
}

T5.阿兔与兔子洞

知识点：树上差分

简要题意：树上差分模板题

C++参考代码：

#include <bits/stdc++.h>

using i64 = long long ;

const int N = 2e5 + 10 ;

std::vector<std::pair<int , int>> edges[N] ;
int n , q , root , depth[N] ;
int fa[21][N] ;
int sum[N] ;
void bfs() {
	std::memset(depth , 0x3f , sizeof depth) ;
	std::queue<int> que ;
	que.push(root) ;
	depth[root] = 1 , depth[0] = 0 ;
	while ( !que.empty() ) {
		auto v = que.front() ; que.pop() ;

		for(auto u : edges[v]) {
			if ( depth[u.first] > depth[v] + 1 ) {
				depth[u.first] = depth[v] + 1 ;
				fa[0][u.first] = v ;
				que.push(u.first) ;
				for(int i = 1 ; i <= 20 ; ++ i) {
					fa[i][u.first] = fa[i - 1][fa[i - 1][u.first]] ;
				}
			}
		}
	}
}
inline int lca(int a,int b) {
	if ( depth[a] < depth[b] ) std::swap(a, b) ;
	for(int i = 20 ; i >= 0 ; -- i) {
		if ( depth[fa[i][a]] >= depth[b] ) {
			a = fa[i][a] ;
		}
	}
	if ( a == b ) return a; 
	for(int i = 20 ; i >= 0 ; -- i) {
		if ( fa[i][a] != fa[i][b] ) {
			a = fa[i][a] ;
			b = fa[i][b] ;
		}
	}
	return fa[0][a] ;
}

i64 dfs(int v,int f) {
	i64 ans = 0 ;
	for(auto u : edges[v]) {
		if ( u.first != f ) {
			ans += dfs(u.first , v) ;
			sum[v] += sum[u.first] ;
			
			i64 c = sum[u.first] , prek = u.second ;
			while ( c >= prek && prek > 1 ) {
				++ ans ;
				c -= prek ;
				prek = (prek + 1) / 2 ;
			}
			if ( c >= prek ) {
				ans += c ;
			}
		}
	}
	return ans ;
}
void solve() {
    std::cin >> n >> q;
    root = 1;
    for(int i = 1 ; i < n ; ++ i) {
    	int u , v , w ;
    	std::cin >> u >> v >> w ;
    	edges[u].push_back({v , w}) ;
    	edges[v].push_back({u , w}) ;
    }
    bfs() ;
    for(int i = 1 ; i <= q ; ++ i) {
    	int u , v ;
    	std::cin >> u >> v ;

    	int l = lca(u , v) ;

    	sum[u] ++ ;
    	sum[v] ++ ;
    	sum[l] -= 2 ;
    }
   	std::cout << dfs(1 , 0) << '\n' ;
}

int main()
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;

    int t = 1 ;
    // std::cin >> t ;
    while ( t-- ) {
        solve() ;
    }

    return 0 ; 
}

T6.阿兔与语言之塔(旧版)

知识点：字符串hash

简要题意：给定一系列模板串， 个询问串，对于每个询问串求出有多少个模板串要么开头是以该询问串，要么结尾是。

思路：字符串哈希处理匹配，怕被卡就上双hash再不济三哈希 : )。

C++参考代码：

#include <bits/stdc++.h>

using i64 = long long ;

const int N = 2e5 + 10 ;
const int mod1 = 998244353 ;
const int mod2 = 43112609 ;
const int base1 = 13331 ;
const int base2 = 233 ;

int n , q ;
std::map<std::pair<i64 , i64> , int> L , R , LR ;

i64 h1[N] , h2[N] , P1[N] , P2[N] ;
i64 get1(int l,int r) {
	return (h1[r] - h1[l - 1] * P1[r - l + 1] % mod1 + mod1) % mod1 ;
}
i64 get2(int l,int r) {
	return (h2[r] - h2[l - 1] * P2[r - l + 1] % mod2 + mod2) % mod2 ;
}

void solve() {
	std::cin >> n >> q ;

	for(int i = 1 ; i <= n ; ++ i) {
		std::string str ;
		std::cin >> str ;
		h1[0] = h2[0] = 0 ;
		P1[0] = P2[0] = 1 ;
		std::set<std::pair<i64 , i64>> S ;
		for(int j = 1 ; j <= (int)str.size() ; ++ j) {
			P1[j] = P1[j - 1] * base1 % mod1;
			P2[j] = P2[j - 1] * base2 % mod2;
			h1[j] = ((__int128)h1[j - 1] * base1 + str[j - 1]) % mod1 ;
			h2[j] = ((__int128)h2[j - 1] * base2 + str[j - 1]) % mod2 ;
			L[{h1[j] , h2[j]}] ++ ;
			S.insert({h1[j] , h2[j]}) ;
		}
		for(int j = (int)str.size() ; j >= 1 ; -- j) {
			i64 x = get1(j , str.size()) , y = get2(j , str.size()) ;
			R[{x , y}] ++ ;
			if ( S.count({x , y}) ) {
				LR[{x , y}] ++ ;
			}
		}
	}	

	for(int i = 1 ; i <= q ; ++ i) {
		std::string str ;
		std::cin >> str ;
		i64 x = 0 , y = 0 ;
		for(int j = 1 ; j <= (int)str.size() ; ++ j) {
			x = ((__int128)x * base1 + str[j - 1]) % mod1 ;
			y = ((__int128)y * base2 + str[j - 1]) % mod2 ;
		}
		i64 ans = 0 ;
		if (L.count({x , y})) ans += L[{x , y}] ;
		if (R.count({x , y})) ans += R[{x , y}] ;
		if (LR.count({x , y})) ans -= LR[{x , y}] ; 
		std::cout << ans << '\n' ;
	}
    
}

int main()
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;

    int t = 1 ;
    // std::cin >> t ;
    while ( t-- ) {
        solve() ;
    }

    return 0 ; 
}

T6.阿兔与瑕疵回文串

知识点：字符串hash、二分

思路：分奇偶处理，两次二分找到最长回文字符串。

时间复杂度

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
using namespace std ;
using i64 = long long ;
const int mod = 998244353 ;
const int base = 13331 ;
const int N = 2e5 + 10 ;

int n , p[N] , h[N] , hr[N] ;
string str , rstr ;

int get(int l,int r) {
	return ((i64)h[r] - (i64)h[l - 1] * p[r - l + 1] % mod + mod)% mod;
}
int getr(int l,int r) {
	return ((i64)hr[r] - (i64)hr[l - 1] * p[r - l + 1] % mod + mod)% mod;
}


void solve() {
	cin >> n >> str ;
	rstr = str ;
	reverse(all(rstr)) ;
	str = '#' + str ;
	rstr = '#' + rstr ;
	p[0] = 1; 
	for(int i = 1 ; i <= n ; ++ i) {
		p[i] = (i64)p[i - 1] * base % mod ;
		h[i] = ((i64)h[i - 1] * base % mod + (i64)str[i])% mod ;
		hr[i] = ((i64)hr[i - 1] * base % mod + (i64)rstr[i]) % mod ;
	}
	int ans = 1 ;

	// even : 
	for(int i = 2 ; i <= n; ++ i) {
		// 枚举中间位置为 i 和 i-1 的中间位置
		int l = 1 , r = min(i - 1 ,n - i + 1) , k1 = 0 , k2 = 0 ;
		while ( r >= l ) {
			int mid = (l + r) >> 1 ;
			if ( get(i - mid , i - 1) == getr(n - (i + mid - 1) + 1 , n - i + 1) ) {
				l = mid + 1 ;
				k1 = mid ;
			} else {
				r = mid - 1 ;
			}
		}
		// [i + k1 + 1 , i + k1 + mid ]
		l = 1 , r = min(i - k1 - 2 , n - (i + k1)) ;
		while ( r >= l ) {
			int mid = (l + r) >> 1 ;
			if ( get(i - k1 - 1 - mid , i - k1 - 2) == getr(n - (i + k1 + mid) + 1 , n - (i + k1 + 1) + 1)) {
				l = mid + 1 ;
				k2 = mid ;
			} else {
				r = mid - 1 ;
			}
		}
		ans = max(ans , 2 * (k1 + k2) + (k1 < min(i - 1 , n - i + 1) ? 2 : 0)) ;
	}
	// odd : 
	for(int i = 1 ; i <= n ; ++ i) {
		// 枚举中间位置 i 
		// 二分回文串长度
		int l = 1 , r = min(i - 1 , n - i) , k1 = 0 , k2 = 0 ;
		while ( r >= l ) {
			int mid = (l + r) >> 1 ;
			if ( get(i - mid, i - 1) == getr(n - (i + mid) + 1 , n - (i + 1) + 1)) {
				l = mid + 1 ;
				k1 = mid ;
			} else {
				r = mid - 1 ;
			}
		}
		// [i - k1 , i + k1] 是不经过修改的最长回文串，隔开一个后再次二分找最长回文

		l = 1 , r = min(i - k1 - 2 , n - (i + k1 + 1)) ;

		while ( r >= l ) {
			int mid = (l + r) >> 1 ;
			if ( get(i - k1 - mid - 1 , i - k1 - 2) == getr(n - (i + k1 + 1 + mid) + 1 , n - (i + k1 + 2) + 1)) {
				l = mid + 1 ;
				k2 = mid ;
			} else {
				r = mid - 1 ;
			}
		}
		// cout << i << " : " << k1 << ' ' << k2 << '\n' ;
		// [i - k1 - 2 - mid + 1  , i - k1 - 2] = [i + k1 + 2 , i + k1 + 1 + mid]
		ans = max(ans , 2 * (k1 + k2) + 1 + (k1 < min(i - 1 , n - i) ? 2 : 0)) ;
	}

	cout << ans << '\n' ;
}

int main()
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;

    int t = 1 ;
    // std::cin >> t ;
    while ( t-- ) {
        solve() ;
    }

    return 0 ; 
}

T7.阿兔与兔崽子

知识点 ：贪心

简要题意：有 支兔子每支兔子具有两个属性，攻击力和血量，主人公的攻击力为 ，每次可以选择一个兔子攻击，攻击之前会被所有活着的兔子攻击一次，问最小所受攻击是多大？

思路：Guess，首先我们可以想到一个显然可能可行的贪心策略（依次把攻击力从高到低的兔子灭掉如果攻击力相同的先把血少的干掉）然后喜提 WA，我们再关注改变两个兔子的先后次序影响是什么假设只有两只兔子 A 和 B，要么先把 A 干掉然后把 B干掉 反之一样。那么分别的贡献为 。那么总希望按照 依次干掉那么排序规则就出来了注意。。范围。

C++参考代码：

#include <bits/stdc++.h>

using i64 = long long ;

const int N = 2e5 + 10 ;
const int mod = 1e9 + 7 ;

int n , k ;
struct node
{
	int h , val ;
} a[N] ;

void solve() {
    std::cin >> n >> k ;
    i64 sum = 0 , ans = 0 ;
    for(int i = 1 ; i <= n ; ++ i) {
    	std::cin >> a[i].h >> a[i].val ;
    	sum = (sum + a[i].val) % mod ;
    }

    std::sort(a + 1 , a + 1 + n , [&](const node&x,const node&y) {
    	int p1 = (x.h + k - 1) / k ;
    	int p2 = (y.h + k - 1) / k ;
    	return (__int128)p1 * x.val + (__int128)(p1 + p2) * y.val < (__int128)p2 * y.val + (__int128)(p1 + p2) * x.val ;
    }) ;

    for(int i = 1 ; i <= n ; ++ i) {
    	int t = (a[i].h + k - 1) / k ;
    	ans = (ans + sum * t % mod) % mod ;
    	sum = ((sum - a[i].val) % mod + mod) % mod ;
	}
    std::cout << ans << '\n' ;
}

int main()
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;

    int t = 1 ;
    // std::cin >> t ;
    while ( t-- ) {
        solve() ;
    }

    return 0 ; 
}

T9.阿兔与玫瑰树

知识点：树形dp

C++参考代码：

#include <bits/stdc++.h>

using i64 = long long ;

const int N = 2e5 + 10 ;

int n , q ;
std::vector<int> edges[N] ;
i64 f[N] , size[N] , dp[N] , tot ;
void dfs1(int v,int fa) {
	if ( edges[v].size() == 1 ) {
		size[v] = 1 ;
		++ tot ;
	}
	for(auto u : edges[v]) {
		if (u != fa) {
			dfs1(u , v) ;
			size[v] += size[u] ;
			f[v] += f[u] + size[u] ;
		}
	}
}
void dfs2(int v,int fa) {
	if (!fa) {
		dp[v] = f[v] ;
 	} else {
 		dp[v] = dp[fa] - (f[v] + size[v]) + (tot - size[v]) + f[v] ; 
 	}

	for(auto u : edges[v]) {
		if ( u != fa ) {
			dfs2(u , v) ;
		}
	}
}

void solve() {
	std::cin >> n >> q ;
	for(int i = 1 , u , v ; i < n ; ++ i) {
		std::cin >> u >> v ;
		edges[u].push_back(v) ;
		edges[v].push_back(u) ;
	}    
	dfs1(1 , 0);
	dfs2(1 , 0) ;

	for(int i = 1 , x ; i <= q ; ++ i) {
		std::cin >> x;
		std::cout << dp[x] << '\n' ;
	}
}

int main()
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;

    int t = 1 ;
    // std::cin >> t ;
    while ( t-- ) {
        solve() ;
    }

    return 0 ; 
}

T10.阿兔与种树

知识点：前缀和、差分

模板题

#include <bits/stdc++.h>

using i64 = long long ;

const int N = 2e5 + 10 ;

int n , m ;
i64 b[N] , a[N] ;

void solve() {
    std::cin >> n >> m ;
    for(int i = 1 ; i <= m ; ++ i) {
    	int l , r ;
    	std::cin >> l >> r ;
    	b[l] += l ;
    	b[r + 1] -= l ;
    	a[l] ++ ;
    	a[r + 1] -- ;
    }
    for(int i = 1 ; i <= n ; ++ i) {
    	b[i] += b[i - 1] ;
    	a[i] += a[i - 1] ;
    	std::cout << (i + 1) * a[i] - b[i] << " \n"[i == n] ;
    }
}

int main()
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;

    int t = 1 ;
    //std::cin >> t ;
    while ( t-- ) {
        solve() ;
    }

    return 0 ; 
}

T12.阿兔与网页设计

知识点：观察

题意省略

思路：从后往前求result Min

C++参考代码：

#include <bits/stdc++.h>

using i64 = long long ;

void solve() {
    int n ;
    std::string str; 
    std::cin >> n >> str ;

    int x = 0 , y = 0;
    int ans = 2147483647 ;
    
    for(int i = (int)str.size() - 1 ; i >= 0 ; -- i) {
    	if ( str[i] == '1' ) {
    		++ x ;
    		if ( x > 1 ) {
    			ans = std::min(ans , y / (x - 1)) ;
    		}
    	} else {
    		++ y ;
    	}
    }
    std::cout << ans << '\n' ;
}

int main()
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false) ;

    int t = 1 ;
    // std::cin >> t ;
    while ( t-- ) {
        solve() ;
    }

    return 0 ; 
}