A(很简单)

题目

主赛有

c

道题目和

n

个晋级选手

淘汰赛有

d

道题目和

1

个晋级选手

求

n\times m-k

个选手至少要多少道题目

1\leq c,d,n,m,k\leq 100

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

1\leq n,a_i\leq 10^5

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)

开始每次往第一象限方向移动到另一个点，求最多移动几次。

1\leq n\leq 5000,1\leq w_i,h_i\leq 10^6

sol

原题：NOIP1999导弹拦截

暴力DP：

dp[i]=\max_{w_j<w_i\cap h_j<h_i}\{dp[j]+1\}

可以通过本题。时间复杂度

O(n^2)

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

CPP

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

的最小值

1\leq n\leq 3000,1\leq s_i,c_i\leq 10^9

sol

枚举

j

，然后分别枚举

i,k

根据加法原理和乘法原理得时间复杂度为

O(n^2)

当然，可以用类似 C 题的线段树优化达到

O(n\log n)

E(送分)

黑白染色即可。

F(送分)

略

易错点：

n,m

弄反

G(很简单)

题目

在网格图中给出一个联通块，要求去掉

k

个联通块中的格子后依旧保持联通，标记去掉的格子后输出网格。(保证有解)

sol

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

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

H(简单)

题目

给出一个长度为

n

序列，求一种划分，使得划分后每个组内的极差和最大

1\leq n\leq 10^6

sol

注意到：

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

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

k=5

即可

直接暴力DP

O(nk)

I(比较简单)

题目

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

10^9+7

取模

1\leq n\leq 10^5

sol

考虑DP，设计状态

dp_{i,0/1}

表示[

i

所在联通块及其子树交集]有

0/1

个黑色顶点

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

CPP

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;

泉州一中普及组日赛 0708

文章操作