泉州一中普及组日赛 0708

fresh_snow · 2025-07-08 14:35:26 · 题解

A(很简单)

题目

主赛有 c 道题目和 n 个晋级选手

淘汰赛有 d 道题目和 1 个晋级选手

求 n\times m-k 个选手至少要多少道题目

sol

简单的完全背包，两个物品，一个主赛，一个淘汰赛。

注意从程序上要特判 n\times m-k<0 的情况。(不过实际上没有这样的测试数据)

易错点：写反重量和价值

B(简单)

题目

给出一个 n 位的二进制数 m ,每一个二进制位有一个权重 a_i , 求 x=(s_{n-1}\dots s_1s_0)_2\leq m 使得 f(x)=\sum a_i s_i \rightarrow \max

sol

数位贪心，考虑直接枚举所有的 x

不难注意到，\forall x,y\leq m\ \ s.t.y\subseteq x 有 f(x)\geq f(y) 所以我们只需要统计 1 最多的那些 x 就可以，而这些 x 一共只有至多 \log_2m 个

例如：样例二，m=(11010)_2

我们只需要考虑

• (01111)_2
• (10111)_2
• (11001)_2
• (11010)_2

易错点：进制位混乱

C(简单)

题目

在二维平面上给出 n 个点(坐标均为整数)，从 (w_0,h_0) 开始每次往第一象限方向移动到另一个点，求最多移动几次。

sol

原题：NOIP1999导弹拦截

暴力DP：dp[i]=\max_{w_j<w_i\cap h_j<h_i}\{dp[j]+1\} 可以通过本题。时间复杂度 O(n^2)

此外，一起来欣赏一份经典错误代码

for(int i=1; i<=n; ++i)
  for(int j=1; j<=m; ++j) 
    if( w[i]>w[j] && h[i]>h[j] )
      dp[i] = max ( dp[i], dp[j]+1 );

此外，该转移可以通过线段树优化，达到 O(n\log h)

易错点：严格大于做成不严格，初始没有从 (w_0,h_0) 开始

D(送分)

题目

给出两个长度为 n 的序列 s_i,c_i ，求所有满足 i<j<k\ \cap\ s_i<s_j<s_k 的三元组 (i,j,k) 中 c_i+c_j+c_k 的最小值

sol

枚举 j ，然后分别枚举 i,k

根据加法原理和乘法原理得时间复杂度为 O(n^2)

当然，可以用类似 C 题的线段树优化达到 O(n\log n)

E(送分)

黑白染色即可。

F(送分)

略

易错点： n,m 弄反

G(很简单)

题目

在网格图中给出一个联通块，要求去掉 k 个联通块中的格子后依旧保持联通，标记去掉的格子后输出网格。(保证有解)

sol

dfs 之后，联通块可以标记成一个树

每次去掉任意一个叶子即可。

H(简单)

题目

给出一个长度为 n 序列，求一种划分，使得划分后每个组内的极差和最大

sol

注意到：

• 对于一个不单调的序列，不会划分很长的一段
• 对于单调的序列，中间不会划分

所以将单调的部分中间直接砍掉只留首尾两个，并且每次划分长度不超过 k=5 即可

直接 暴力DP O(nk)

I(比较简单)

题目

给出一个树，有若干个顶点被染黑，求有多少种分割树的方案使得每个子树恰好有一个黑色顶点，答案对 10^9+7 取模

sol

考虑DP，设计状态 dp_{i,0/1} 表示[ i 所在联通块及其子树交集]有 0/1 个黑色顶点

在转移过程中，要保证：每个联通块恰好一个黑色节点，于是由划分与不划分有转移方程：

int f[2]={dp[u][0],dp[u][1]};
dp[u][0]=f[0]*(dp[v][0]+dp[v][1])%mod;
dp[u][1]=f[0]*(dp[v][1])%mod+f[1]*(dp[v][0]+dp[v][1])%mod;