期末考试讲解（欢迎吐槽）

不说了
先上结果

链接

[基础后期-期末-T1]素数题目描述

小 A 在学习埃拉托色尼筛法。

该算法的步骤如下：

写下 2 2 2 到 n n n 之间的所有整数（包括 2 2 2 和 n n n）。
找到尚未删除的最小数，并将其命名为 p p p；则 p p p 是素数。
划掉 p p p 及其所有尚未划掉的倍数。
如果尚有数未被划掉，请转到步骤 2 2 2。

小 A 为了能够更好地理解这个筛法，他希望你能为他编写一个程序，能够按照被删除的先后顺序输出每一个被删除的数字。

输入格式

输入一个正整数 n n n。

输出格式

输出 n − 1 n-1 n−1 个正整数，含义如题目所述，注意每个数字之间以一个空格隔开。

样例 #1 样例输入 #1

样例输出 #1

2 4 6 8 10 3 9 5 7

提示

对于 20 % 20% 20% 的数据， 3 ≤ n ≤ 5 3 leq n leq 5 3≤n≤5。

对于 70 % 70% 70% 的数据， 3 ≤ n ≤ 5 × 1 0 5 3 leq n leq 5 times 10^5 3≤n≤5×105。

对于所有数据， 3 ≤ n ≤ 5 × 1 0 6 3 leq n leq 5 times 10^6 3≤n≤5×106。

题解

埃拉托色尼筛法，没什么好说的

上代码：

#include
using namespace std;
int n;
bool xx[5000007];
signed main(){
   scanf("%d",&n);
   for(int i=2;i<=n;i++){
   	if(xx[i])
   	    continue;
   	for(int j=1;j<=n/i;j++){
   		if(xx[j*i])
   		    continue;
   	    printf("%d ",i*j);
   		xx[i*j]=1;
   	}
   }
   return 0;
}

然而残忍的 T L E TLE TLE告诉我，不要莽撞行事！！！
时间复杂度：
O ( n ) ! ! ! O(n)!!! O(n)!!!
放心了

结果

AC color{green}text{AC} AC

链接

[基础后期-期末-T2]和树题目描述

小 A 现在有一棵根节点为 1 1 1 的一共有 n n n 个节点的树，每个节点 i i i 都有一个点权 v i v_i vi。他希望知道，从根节点出发，一共有多少条路径（路径可以只包含根节点），使得路径上经过的所有节点（含根节点）的点权之和大于等于 v a l val val。路径要求树的每条边最多走一次。

输入格式

第一行输入两个正整数 n , v a l n,val n,val，分别表示树一共有 n n n 个节点，以及题面所述的 v a l val val。

第二行 n n n 个正整数，用一个空格分隔，第 i i i 个正整数 v i v_i vi 代表节点 i i i 的权值。

接下来 n − 1 n-1 n−1 行，每行两个正整数 u , v u,v u,v，表示节点 u , v u,v u,v 之间有一条边相连。保证最后所得的树连通。

输出格式

输出一个整数，表示符合题面要求的路径条数。

样例 #1 样例输入 #1

7 3
2 6 6 8 10 7 3
1 2
1 6
2 3
2 7
3 4
4 5

样例输出 #1

提示

【样例解释】

所画出的树如下，棕色的数字为点权，圈内的数字是节点编号。

对于 60 % 60 % 60% 的数据， 5 ≤ n ≤ 3000 5 leq n leq 3000 5≤n≤3000；

对于所有数据， 5 ≤ n ≤ 1 0 6 5 leq n leq 10^6 5≤n≤106， 1 ≤ u i , v i ≤ n 1 leq u_i,v_i leq n 1≤ui,vi≤n， 1 ≤ v a l , v i ≤ 1 0 9 1 leq val,v_i leq 10^9 1≤val,vi≤109。

题解1

听上去一个 d f s dfs dfs就能搞定，但我用实践告诉你不是！！！ color{red}text{不是！！！} 不是！！！

看看我的代码

#include
#define N 1000007
using namespace std;
int n,val,xxx[N],x,y,h[N],ans;
struct kkksc03{
	int to,nxt;
}ed[N];
void add(int from,int to,int ct){
	ed[ct].to=to;
	ed[ct].nxt=h[from];
	h[from]=ct;
} 
void dfs(int u,int fa,int sum){
	sum+=xxx[u];
	if(sum>=val)
	    ans++;
    for(int i=h[u];i;i=ed[i].nxt){
    	int v=ed[i].to;
    	if(v!=fa)
    	    dfs(v,u,sum);
	}
}
signed main(){
	scanf("%d %dn",&n,&val);
	for(int i=1;i<=n;i++)
		scanf("%d",xxx+i);
	for(int i=1;i 
结果1 

    
     
      
       
        
         WA
        
        
         
          +
         
         
          
           RE
          
         
        
       
      
      
       color{red}text{WA}color{black}+color{purple}text{RE}
      
     
    WA+RE 
…… 
题解2 
声明，不是我想的
 先要研究为什么失败 

     
      
       
        
         
          RE
         
        
       
       
        color{purple}text{RE}
       
      
     RE
 因为数组不够大

     
      
       
        
         
          WA
         
        
       
       
        color{red}text{WA}
       
      
     WA
 因为没开long long！！！TMD 
完事具备，开始，代码！ 
#include
#define N 10000007
using namespace std;
int n,val,xxx[N],x,y,h[N],ans;
struct kkksc03{
	int to,nxt;
}ed[N];
void add(int from,int to,int ct){
	ed[ct].to=to;
	ed[ct].nxt=h[from];
	h[from]=ct;
} 
void dfs(int u,int fa,long long sum){
	sum+=xxx[u];
	if(sum>=val)
	    ans++;
    for(int i=h[u];i;i=ed[i].nxt){
    	int v=ed[i].to;
    	if(v!=fa)
    	    dfs(v,u,sum);
	}
}
signed main(){
	scanf("%d %dn",&n,&val);
	for(int i=1;i<=n;i++)
		scanf("%d",xxx+i);
	for(int i=1;i 
建议开
    
     
      
       
        O
       
       
        2
       
      
      
       O2
      
     
    O2（链式前向星比vector快很多） 
结果2 

    
     
      
       
        
         AC
        
       
      
      
       color{green}text{AC}
      
     
    AC 
C 
链接 
[基础后期-期末-T3]迷宫 
题目描述 
小 A 在玩某个网游，而在网游之中有个关卡是要求小 A 走迷宫。 
具体而言，迷宫可以被抽象成 
    
     
      
       
        n
       
      
      
       n
      
     
    n 行 
    
     
      
       
        m
       
      
      
       m
      
     
    m 列的一个方阵，由 . 表示可以通行的道路，而用 * 表示无法通行的墙壁。正如很多网游一样，会有道具来破坏一个墙壁，使之变成一个道路，同时扣除手头的一个道具。小 A 现在就有 
    
     
      
       
        k
       
      
      
       k
      
     
    k 个这种道具。 
由于这个网游中会有一些宝箱在迷宫各处生成，包括墙里面也是可能的（要获得它只能通过道具破坏墙壁变成道路），因而为了获得更多的宝箱，小 A 希望知道自己最多能有多少个格点是存在一种破坏墙壁的方案能够到达的。 你可以认为，小 A 永远是从迷宫中最左上方的格点出发，且最左上方的格点永远不会是墙壁。 
输入格式 
第一行输入三个整数 
    
     
      
       
        n
       
       
        ,
       
       
        m
       
       
        ,
       
       
        k
       
      
      
       n,m,k
      
     
    n,m,k，表示迷宫有 
    
     
      
       
        n
       
      
      
       n
      
     
    n 行 
    
     
      
       
        m
       
      
      
       m
      
     
    m 列。
    
     
      
       
        k
       
      
      
       k
      
     
    k 表示道具个数。 
第二行开始，往下 
    
     
      
       
        n
       
      
      
       n
      
     
    n 行，每行一个长度为 
    
     
      
       
        m
       
      
      
       m
      
     
    m 的字符串，仅由 . 或者 * 组成，表示迷宫中道路和墙壁的情况。 
输出格式 
输出一个正整数，表示最多能有多少个格点是能够到达的。 
样例 #1 
样例输入 #1 
5 5 1
..**.
.***.
*....
.**.*
**...
 
样例输出 #1 
17
 
样例 #2 
样例输入 #2 
5 5 2
..**.
.***.
*....
.**.*
**...
 
样例输出 #2 
25
 
提示 
【样例解释】 
样例 
    
     
      
       
        1
       
      
      
       1
      
     
    1 中，如下的格子：
    
     
      
       
        (
       
       
        1
       
       
        ,
       
       
        1
       
       
        )
       
       
        ,
       
       
        (
       
       
        1
       
       
        ,
       
       
        2
       
       
        )
       
       
        ,
       
       
        (
       
       
        1
       
       
        ,
       
       
        3
       
       
        )
       
       
        ,
       
       
        (
       
       
        1
       
       
        ,
       
       
        5
       
       
        )
       
      
      
       (1,1),(1,2),(1,3),(1,5)
      
     
    (1,1),(1,2),(1,3),(1,5)，
    
     
      
       
        (
       
       
        2
       
       
        ,
       
       
        1
       
       
        )
       
       
        ,
       
       
        (
       
       
        2
       
       
        ,
       
       
        2
       
       
        )
       
       
        ,
       
       
        (
       
       
        2
       
       
        ,
       
       
        5
       
       
        )
       
      
      
       (2,1),(2,2),(2,5)
      
     
    (2,1),(2,2),(2,5)，
    
     
      
       
        (
       
       
        3
       
       
        ,
       
       
        1
       
       
        )
       
       
        ,
       
       
        (
       
       
        3
       
       
        ,
       
       
        2
       
       
        )
       
       
        ,
       
       
        (
       
       
        3
       
       
        ,
       
       
        3
       
       
        )
       
       
        ,
       
       
        (
       
       
        3
       
       
        ,
       
       
        4
       
       
        )
       
       
        ,
       
       
        (
       
       
        3
       
       
        ,
       
       
        5
       
       
        )
       
      
      
       (3,1),(3,2),(3,3),(3,4),(3,5)
      
     
    (3,1),(3,2),(3,3),(3,4),(3,5)，
    
     
      
       
        (
       
       
        4
       
       
        ,
       
       
        1
       
       
        )
       
       
        ,
       
       
        (
       
       
        4
       
       
        ,
       
       
        4
       
       
        )
       
      
      
       (4,1),(4,4)
      
     
    (4,1),(4,4)，
    
     
      
       
        (
       
       
        5
       
       
        ,
       
       
        3
       
       
        )
       
       
        ,
       
       
        (
       
       
        5
       
       
        ,
       
       
        4
       
       
        )
       
       
        ,
       
       
        (
       
       
        5
       
       
        ,
       
       
        5
       
       
        )
       
      
      
       (5,3),(5,4),(5,5)
      
     
    (5,3),(5,4),(5,5)，合计 
    
     
      
       
        17
       
      
      
       17
      
     
    17 个格子，是存在一种破坏墙壁的方法可以到达的。 
对于 
    
     
      
       
        30
       
       
        %
       
      
      
       30%
      
     
    30% 的数据，
    
     
      
       
        n
       
       
        =
       
       
        1
       
      
      
       n=1
      
     
    n=1。 
另外有 
    
     
      
       
        40
       
       
        %
       
      
      
       40%
      
     
    40% 的数据，
    
     
      
       
        k
       
       
        =
       
       
        0
       
      
      
       k=0
      
     
    k=0。 
对于所有数据，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        1000
       
       
        ,
       
       
        1
       
       
        ≤
       
       
        m
       
       
        ≤
       
       
        1000
       
       
        ,
       
       
        1
       
       
        ≤
       
       
        k
       
       
        ≤
       
       
        20
       
      
      
       1 leq n leq 1000,1 leq m leq 1000,1 leq k leq 20
      
     
    1≤n≤1000,1≤m≤1000,1≤k≤20。
 悲喜之结合C
 话说结合题目
     
      
       
        
         
          A
         
        
       
       
        color{green}text{A}
       
      
     A与
     
      
       
        
         
          C
         
        
       
       
        color{green}text{C}
       
      
     C就可以
     
      
       
        
         
          AC
         
        
       
       
        color{green}text{AC}
       
      
     AC，然而我却败在了
     
      
       
        
         
          C
         
        
       
       
        color{red}text{C}
       
      
     C上 
解法1 
立刻上手，搞
    
     
      
       
        b
       
       
        f
       
       
        s
       
      
      
       bfs
      
     
    bfs（那是必须的） 
用
    
     
      
       
        v
       
       
        i
       
       
        s
       
      
      
       vis
      
     
    vis记录到没到达，
    
     
      
       
        a
       
       
        n
       
       
        s
       
      
      
       ans
      
     
    ans记录到达的点 
看一下代码 
#include
#define N 1000007
using namespace std;
int n,m,k,ans,dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char aa[1007][1007];
bool vis[1007][1007];
struct oq{
	int sy,x,y;
};
void bfs(){
	queue q;
	q.push({k,0,0});
	while(!q.empty()){
		oq now=q.front();
		q.pop();
		int sy=now.sy,x=now.x,y=now.y;
		if(vis[x][y])
		    continue;
		vis[x][y]=true;
		ans++;
		for(int i=0;i<4;i++){
			int xx=dx[i]+x,yy=dy[i]+y;
			if(xx<0||yy<0||xx>=n||yy>=n)
		    	continue;
		    if(aa[xx][yy]=='.')
		        q.push({sy,xx,yy});
		    else if(sy)
		        q.push({sy-1,xx,yy});
		}
	}
}
signed main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=0;i>aa[i];
	bfs();
	printf("%d",ans);
	return 0;
}
 
结果1 

    
     
      
       
        
         WA
        
       
      
      
       color{red}text{WA}
      
     
    WA了6个点，也就是40分 
解法2 
声明，不是我想的
 问题出在哪？
 给出下面一幅图，就发现问题了 
3 5 1
.****
...*.
**...
 
仔细盯好第
    
     
      
       
        1
       
      
      
       1
      
     
    1行第
    
     
      
       
        5
       
      
      
       5
      
     
    5列的*,问题就在这！
 当机器走到第
    
     
      
       
        2
       
      
      
       2
      
     
    2行第
    
     
      
       
        3
       
      
      
       3
      
     
    3列的.时，他会先把旁边的*给砸掉，到达第
    
     
      
       
        2
       
      
      
       2
      
     
    2行第
    
     
      
       
        5
       
      
      
       5
      
     
    5列，接着，机器便没有道具了
 当机器从下边再到达这里时，便会因为
    
     
      
       
        v
       
       
        i
       
       
        s
       
      
      
       vis
      
     
    vis的记录而退出，然而事实是，除了第
    
     
      
       
        1
       
      
      
       1
      
     
    1行第
    
     
      
       
        4
       
      
      
       4
      
     
    4列的*不能到达，其他都可到达
 那怎么办呢？记录到达这里时剩余的道具！ 
代码 
#include
using namespace std;
int n,m,k,ans,dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char aa[1007][1007];
int vis[1007][1007];
struct oq{
	int sy,x,y;
};
void bfs(){
	queue q;
	int nx=0,ny=0;
	while(aa[nx][ny]=='*'){
		nx++;
		if(nx>=n)
		   nx=0,ny++;
	}
	q.push({k,nx,ny});
	while(!q.empty()){
		oq now=q.front();
		q.pop();
		int sy=now.sy,x=now.x,y=now.y;
		if(vis[x][y]>=sy)
		    continue;
		vis[x][y]=sy;
		for(int i=0;i<4;i++){
			int xx=dx[i]+x,yy=dy[i]+y;
			if(xx<0||yy<0||xx>=n||yy>=m)
		    	continue;
		    if(aa[xx][yy]=='.'&&vis[xx][yy]sy,xx,yy});
		    else if(sy>0&&vis[xx][yy]sy-1,xx,yy});
		}
	}
}
signed main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=0;i>aa[i];
	for(int i=0;i=0)
	            ans++;
	printf("%d",ans);
	return 0;
}
 
结果2 

    
     
      
       
        
         WA
        
       
      
      
       color{red}text{WA}
      
     
    WA了……0个点，也就是100分！ 
D 
链接 
[基础后期-期末-T4]数列 
题目描述 
小 A 有一个正整数数列 
    
     
      
       
        
         a
        
        
         1
        
       
       
        ,
       
       
        
         a
        
        
         2
        
       
       
        ,
       
       
        …
       
       
        ,
       
       
        
         a
        
        
         n
        
       
      
      
       a_1,a_2,dots,a_n
      
     
    a1,a2,…,an。他希望让这些数列中的数字全都变成 
    
     
      
       
        0
       
      
      
       0
      
     
    0。 
为了更有挑战性，他希望用若干次操作将这个数列归零。具体地，对于第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 次操作，小 A 可以任意指定一个实数 
    
     
      
       
        
         c
        
        
         i
        
       
      
      
       c_i
      
     
    ci（
    
     
      
       
        
         c
        
        
         i
        
       
      
      
       c_i
      
     
    ci 可以相等），让数列中的数字全部减去 
    
     
      
       
        
         c
        
        
         i
        
       
      
      
       c_i
      
     
    ci 后，取绝对值。例如：有一个正整数数列 
    
     
      
       
        1
       
       
        ,
       
       
        3
       
       
        ,
       
       
        5
       
       
        ,
       
       
        7
       
      
      
       1,3,5,7
      
     
    1,3,5,7，令 
    
     
      
       
        
         c
        
        
         1
        
       
       
        =
       
       
        2
       
      
      
       c_1=2
      
     
    c1=2，则先让数列中所有数字都减去 
    
     
      
       
        2
       
      
      
       2
      
     
    2，即变成 
    
     
      
       
        −
       
       
        1
       
       
        ,
       
       
        1
       
       
        ,
       
       
        3
       
       
        ,
       
       
        5
       
      
      
       -1,1,3,5
      
     
    −1,1,3,5，再取绝对值，变成了 
    
     
      
       
        1
       
       
        ,
       
       
        1
       
       
        ,
       
       
        3
       
       
        ,
       
       
        5
       
      
      
       1,1,3,5
      
     
    1,1,3,5。 
小 A 经过了一段时间的尝试之后，他发现有下面两个问题比较有趣，希望你能帮他解答一下： 
问题 
    
     
      
       
        1
       
      
      
       1
      
     
    1：小 A 有一个长度为 
    
     
      
       
        n
       
      
      
       n
      
     
    n 的任意正整数数列，希望你能用不超过 
    
     
      
       
        n
       
      
      
       n
      
     
    n 次操作，将数列全部归零。 
问题 
    
     
      
       
        2
       
      
      
       2
      
     
    2：小 A 有一个长度为 
    
     
      
       
        n
       
      
      
       n
      
     
    n 的数列，且保证 
    
     
      
       
        1
       
       
        ∼
       
       
        n
       
      
      
       1sim n
      
     
    1∼n 在数列中仅仅出现 
    
     
      
       
        1
       
      
      
       1
      
     
    1 次，希望你能用不超过 
    
     
      
       
        min
       
       
        ⁡
       
       
        {
       
       
        n
       
       
        −
       
       
        1
       
       
        ,
       
       
        3022
       
       
        }
       
      
      
       min{n-1,3022}
      
     
    min{n−1,3022} 次操作，将数列全部归零。 
因为符合条件的方法可能有很多，你只需要输出任意一组符合要求的 
    
     
      
       
        
         c
        
        
         i
        
       
      
      
       c_i
      
     
    ci 即可。也就是说，您的答案不必与标准答案或者样例输出一致。 
输入格式 
第一行输入两个正整数，分别为 
    
     
      
       
        n
       
      
      
       n
      
     
    n 和 
    
     
      
       
        t
       
       
        y
       
       
        p
       
       
        e
       
      
      
       type
      
     
    type，用一个空格隔开。其中，
    
     
      
       
        t
       
       
        y
       
       
        p
       
       
        e
       
       
        =
       
       
        1
       
      
      
       type=1
      
     
    type=1 回答的是第一个问题，而 
    
     
      
       
        t
       
       
        y
       
       
        p
       
       
        e
       
       
        =
       
       
        2
       
      
      
       type=2
      
     
    type=2 回答的是第二个问题。 
第二行，输入 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个正整数 
    
     
      
       
        
         a
        
        
         1
        
       
       
        ,
       
       
        
         a
        
        
         2
        
       
       
        ,
       
       
        …
       
       
        ,
       
       
        
         a
        
        
         n
        
       
      
      
       a_1,a_2,dots,a_n
      
     
    a1,a2,…,an，数与数之间以一个空格隔开。 
输出格式 
第一行输出一个正整数 
    
     
      
       
        s
       
       
        t
       
       
        e
       
       
        p
       
      
      
       step
      
     
    step，表示用了 
    
     
      
       
        s
       
       
        t
       
       
        e
       
       
        p
       
      
      
       step
      
     
    step 次操作完成。 
第二行，输出 
    
     
      
       
        s
       
       
        t
       
       
        e
       
       
        p
       
      
      
       step
      
     
    step 个实数 
    
     
      
       
        
         c
        
        
         i
        
       
      
      
       c_i
      
     
    ci，表示你每次操作时指定的数。为了确保能够正常评测，不建议使得 
     
      
       
        
         
          c
         
         
          i
         
        
       
       
        c_i
       
      
     ci 的小数点后有 
     
      
       
        
         4
        
       
       
        4
       
      
     4 位或者以上，同时确保 
     
      
       
        
         
          c
         
         
          i
         
        
       
       
        c_i
       
      
     ci 的个数与 
     
      
       
        
         s
        
        
         t
        
        
         e
        
        
         p
        
       
       
        step
       
      
     step 相一致。 
本题的样例仅供理解题意之用，可能存在多解，只要结果是合理的都会被视作正确，不必担心输出和样例不一致。 
样例 #1 
样例输入 #1 
4 1
1 3 5 7
 
样例输出 #1 
4
2
2
2
1
 
样例 #2 
样例输入 #2 
4 2
3 4 1 2
 
样例输出 #2 
3
2.5
1
0.5
 
提示 
【样例解释】 
对于样例 
    
     
      
       
        1
       
      
      
       1
      
     
    1：
    
     
      
       
        1 3 5 7
       
       
        
         →
        
        
         
          
           
            c
           
           
            1
           
          
          
           =
          
          
           2
          
         
        
       
       
        1 1 3 5
       
       
        
         →
        
        
         
          
           
            c
           
           
            2
           
          
          
           =
          
          
           2
          
         
        
       
       
        1 1 1 3
       
       
        
         →
        
        
         
          
           
            c
           
           
            3
           
          
          
           =
          
          
           2
          
         
        
       
       
        1 1 1 1
       
       
        
         →
        
        
         
          
           
            c
           
           
            4
           
          
          
           =
          
          
           1
          
         
        
       
       
        0 0 0 0
       
      
      
       text{1 3 5 7} xrightarrow{c_1=2} text{1 1 3 5} xrightarrow{c_2=2} text{1 1 1 3} xrightarrow{c_3=2} text{1 1 1 1} xrightarrow{c_4=1} text{0 0 0 0}
      
     
    1 3 5 7c1=2
           1 1 3 5c2=2
           1 1 1 3c3=2
           1 1 1 1c4=1
           0 0 0 0，共 
    
     
      
       
        4
       
      
      
       4
      
     
    4 次。 
对于样例 
    
     
      
       
        2
       
      
      
       2
      
     
    2：
    
     
      
       
        3 4 1 2
       
       
        
         →
        
        
         
          
           
            c
           
           
            1
           
          
          
           =
          
          
           2.5
          
         
        
       
       
        0.5 1.5 1.5 0.5
       
       
        
         →
        
        
         
          
           
            c
           
           
            2
           
          
          
           =
          
          
           1
          
         
        
       
       
        0.5 0.5 0.5 0.5
       
       
        
         →
        
        
         
          
           
            c
           
           
            3
           
          
          
           =
          
          
           0.5
          
         
        
       
       
        0 0 0 0
       
      
      
       text{3 4 1 2} xrightarrow{c_1=2.5} text{0.5 1.5 1.5 0.5} xrightarrow{c_2=1} text{0.5 0.5 0.5 0.5} xrightarrow{c_3=0.5} text{0 0 0 0}
      
     
    3 4 1 2c1=2.5
           0.5 1.5 1.5 0.5c2=1
           0.5 0.5 0.5 0.5c3=0.5
           0 0 0 0，共 
    
     
      
       
        3
       
      
      
       3
      
     
    3 次。 
【数据范围】 
数据点编号 
       
        
         
          
           t
          
          
           y
          
          
           p
          
          
           e
          
         
         
          type
         
        
       type 
       
        
         
          
           n
          
         
         
          n
         
        
       n

       
        
         
          
           1
          
         
         
          1
         
        
       1 
       
        
         
          
           1
          
         
         
          1
         
        
       1 
       
        
         
          
           n
          
          
           ≤
          
          
           10
          
         
         
          n leq 10
         
        
       n≤10

       
        
         
          
           2
          
         
         
          2
         
        
       2 
       
        
         
          
           1
          
         
         
          1
         
        
       1 
       
        
         
          
           n
          
          
           ≤
          
          
           100
          
         
         
          n leq 100
         
        
       n≤100

       
        
         
          
           3
          
         
         
          3
         
        
       3 
       
        
         
          
           1
          
         
         
          1
         
        
       1 
       
        
         
          
           n
          
          
           ≤
          
          
           6000
          
         
         
          n leq 6000
         
        
       n≤6000

       
        
         
          
           4
          
          
           ∼
          
          
           5
          
         
         
          4 sim 5
         
        
       4∼5 
       
        
         
          
           2
          
         
         
          2
         
        
       2 
       
        
         
          
           n
          
          
           ≤
          
          
           10
          
         
         
          n leq 10
         
        
       n≤10

       
        
         
          
           6
          
          
           ∼
          
          
           7
          
         
         
          6sim 7
         
        
       6∼7 
       
        
         
          
           2
          
         
         
          2
         
        
       2 
       
        
         
          
           n
          
          
           ≤
          
          
           100
          
         
         
          n leq 100
         
        
       n≤100

       
        
         
          
           8
          
          
           ∼
          
          
           10
          
         
         
          8 sim 10
         
        
       8∼10 
       
        
         
          
           2
          
         
         
          2
         
        
       2 
       
        
         
          
           n
          
          
           ≤
          
          
           6000
          
         
         
          n leq 6000
         
        
       n≤6000
数据保证：
    
     
      
       
        4
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        6000
       
       
        ,
       
       
        1
       
       
        ≤
       
       
        
         a
        
        
         i
        
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         9
        
       
      
      
       4 leq n leq 6000,1 leq a_i leq 10^9
      
     
    4≤n≤6000,1≤ai≤109，
    
     
      
       
        t
       
       
        y
       
       
        p
       
       
        e
       
      
      
       type
      
     
    type 不是 
    
     
      
       
        1
       
      
      
       1
      
     
    1 就是 
    
     
      
       
        2
       
      
      
       2
      
     
    2。 
如果你是在赛后练习本题，以下有几种可能的测试点返回状态，只需将鼠标光标移动到测试点上即可看到。 
The step is too much!：不符合小 A 要求的步数限制。 
The step does not fit.：输出的 
    
     
      
       
        
         c
        
        
         i
        
       
      
      
       c_i
      
     
    ci 个数与 
    
     
      
       
        s
       
       
        t
       
       
        e
       
       
        p
       
      
      
       step
      
     
    step 不一致。 
The sequence is not completely zero.：操作结束之后，数列并未全都归零。 
You are correct.：你的回答是正确的。 
你知不知道，这道题有个别名叫重灾区 
机器：nan 
解法1 
我真的怀疑比赛时脑子进水了
 居然是用
    
     
      
       
        d
       
       
        f
       
       
        s
       
      
      
       dfs
      
     
    dfs！！！
 果然，残忍的
    
     
      
       
        T
       
       
        L
       
       
        E
       
      
      
       TLE
      
     
    TLE大杀四方 
代码 （还要看吗） 
#include
#define N 1000007
using namespace std;
int n,type,step,yqq;
double a[6007],c[6007];
void dfs(int step,double c[6007],double a[6007]){
	double mn=0x3f3f3f3f;
	bool yq=1;
	for(int i=1;i<=n;i++){
	    if(a[i]!=a[i-1]&&i!=1)
	        yq=0;
	    mn=min(a[i],mn);
	}
	if(step>=yqq)
	    return;
	mn*=2;
	if(yq){
		printf("%dn",step+1);
		for(int i=1;i<=step;i++)
		    printf("%.1lfn",c[i]);
		printf("%.1lf",a[n]);
		exit(0);
	}
	double k[6007];
	for(int i=1;i<=n;i++)
	    k[i]=abs(a[i]-mn);
	c[++step]=mn;
	dfs(step,c,k);
	for(int i=1;i<=n;i++)
	    k[i]=abs(a[i]-mn-0.5);
	c[step]=mn+0.5;
	dfs(step,c,k);
}
signed main(){
	scanf("%d %d",&n,&type);
	for(int i=1;i<=n;i++)
	    scanf("%lf",a+i);
	yqq=(type==1)?n:min(n-1,3022);
	dfs(0,c,a);
	return 0;
}
 
…… 
结果1 

    
     
      
       
        
         AC
        
       
      
      
       color{green}text{AC}
      
     
    AC两点+
    
     
      
       
        
         TLE
        
       
      
      
       color{black}text{TLE}
      
     
    TLE七点+
    
     
      
       
        
         WA
        
       
      
      
       color{red}text{WA}
      
     
    WA一点 
好了，无了 
解法2 
声明，不是我想的
 怎么办呢 
先看问题2与问题1的最大区别
 且保证 
     
      
       
        
         1
        
        
         ∼
        
        
         n
        
       
       
        1sim n
       
      
     1∼n 在数列中仅仅出现 1 次
 因此，要分开来看 
问题1 
我们可以一个一个去搞
 先把
    
     
      
       
        
         a
        
        
         1
        
       
      
      
       a_1
      
     
    a1和
    
     
      
       
        
         a
        
        
         2
        
       
      
      
       a_2
      
     
    a2弄成一样的
 那么 
    
     
      
       
        ∣
       
       
        a
       
       
        −
       
       
        c
       
       
        ∣
       
       
        =
       
       
        ∣
       
       
        b
       
       
        −
       
       
        c
       
       
        ∣
       
      
      
       |a-c|=|b-c|
      
     
    ∣a−c∣=∣b−c∣就转化为
    
     
      
       
        c
       
       
        =
       
       
        (
       
       
        a
       
       
        +
       
       
        b
       
       
        )
       
       
        ÷
       
       
        2
       
      
      
       c=(a+b)div2
      
     
    c=(a+b)÷2
 于是乎，简单了
 
    
     
      
       
        
         ∑
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        
         c
        
        
         i
        
       
       
        =
       
       
        
         
          
           (
          
          
           
            a
           
           
            i
           
          
          
           +
          
          
           
            a
           
           
            
             i
            
            
             +
            
            
             1
            
           
          
          
           )
          
         
         
          2.0
         
        
       
      
      
       sumlimits_{i=1}^{n-1}c_i=dfrac{(a_i+a_{i+1})}{2.0}
      
     
    i=1∑n−1ci=2.0(ai+ai+1)，
 最后
    
     
      
       
        
         c
        
        
         n
        
       
       
        =
       
       
        
         a
        
        
         1
        
       
      
      
       c_n=a_1
      
     
    cn=a1 
代码 
if(type==1){
	for(int i=1;i<=n-1;i++){
		c[i]=(a[i+1]+a[i])/2.0;
		for(int j=1;j<=n;j++)
		    a[j]=abs(a[j]-c[i]);
	}
	c[n]=a[1];
	printf("%dn",n);
	for(int i=1;i<=n;i++)
	    printf("%.1lfn",c[i]);
}
 
问题2 
这个问题难度比问题1难多了
 这道题的入手点是是数据为
    
     
      
       
        1
       
       
        ∼
       
       
        n
       
      
      
       1sim n
      
     
    1∼n
 也就是说，我们可以理解为它已经给你排好序了
 我们来看一下
    
     
      
       
        n
       
       
        =
       
       
        10
       
      
      
       n=10
      
     
    n=10的情况 
10 2
1 2 3 4 5 6 7 8 9 10
 
我们试试看把中间两个变成
    
     
      
       
        0.5
       
      
      
       0.5
      
     
    0.5
 那么全体注意减去5.5就变成了 
4.5 3.5 2.5 1.5 0.5 0.5 1.5 2.5 3.5 4.5  
 
接下来4次，每次减去1
 最后1次，减去0.5
 共6次，满足要求
 代码 
if(type==2){
	printf("%dn",n/2+1+n%2);
	double x=0;
	for(int i=1;i<=n;i++)
		x+=a[i];
	x/=n;
	x+=(n%2*1.0)/2.0;
	printf("%.1lfn",x);
	for(int i=n/2-1+n%2;i;i--)
		printf("1n");
	printf("0.5");
}
 
done！
 整体代码 
#include
#define N 1000007
using namespace std;
int n,type,step,yqq;
double a[6007],c[6007];
signed main(){
	scanf("%d %d",&n,&type);
	for(int i=1;i<=n;i++)
	    scanf("%lf",a+i);
	if(type==1){
		for(int i=1;i<=n-1;i++){
			c[i]=(a[i+1]+a[i])/2.0;
			for(int j=1;j<=n;j++)
			    a[j]=abs(a[j]-c[i]);
		}
		c[n]=a[1];
		printf("%dn",n);
		for(int i=1;i<=n;i++)
		    printf("%.1lfn",c[i]);
	}
	if(type==2){
		printf("%dn",n/2+1+n%2);
		double x=0;
		for(int i=1;i<=n;i++)
		    x+=a[i];
		x/=n;
		x+=(n%2*1.0)/2.0;
		printf("%.1lfn",x);
		for(int i=n/2-1+n%2;i;i--)
		    printf("1n");
		printf("0.5");
	}
	return 0;
}
 
结果2 

    
     
      
       
        
         AC
        
       
      
      
       color{green}text{AC}
      
     
    AC 
E 
链接 
[基础后期-期末-T5]优秀 
题目背景 
请注意本题的较大的时间与空间限制。 
本题开启 -O2 优化，会对你的代码的效率进行显著提升。 
题目描述 
小 A 发现，有一些正整数是优秀的。为了定量衡量一个正整数的优秀程度，他定义，一个正整数的优秀程度，指的是这个正整数末尾 
    
     
      
       
        0
       
      
      
       0
      
     
    0 的个数，例如 
    
     
      
       
        11400
       
      
      
       11400
      
     
    11400 的优秀程度就是 
    
     
      
       
        2
       
      
      
       2
      
     
    2。 
小 A 现在给了你一个长度为 
    
     
      
       
        n
       
      
      
       n
      
     
    n 的正整数数列 
    
     
      
       
        {
       
       
        
         a
        
        
         i
        
       
       
        }
       
      
      
       {a_i}
      
     
    {ai}，他希望你能够从中选择不超过 
    
     
      
       
        k
       
      
      
       k
      
     
    k 个数字，使得这些数字的乘积有着最大的优秀程度。 
显然，选择这些数字的方法可能有很多，小 A 不要求你给出方案，只需你输出最大的优秀程度即可。 
输入格式 
第一行输入两个正整数 
    
     
      
       
        n
       
      
      
       n
      
     
    n 和 
    
     
      
       
        k
       
      
      
       k
      
     
    k，含义如题所述。 
第二行输入 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个正整数 
    
     
      
       
        
         a
        
        
         1
        
       
       
        ,
       
       
        
         a
        
        
         2
        
       
       
        ,
       
       
        …
       
       
        ,
       
       
        
         a
        
        
         n
        
       
      
      
       a_1,a_2,dots,a_n
      
     
    a1,a2,…,an，含义如题所述。 
输出格式 
输出一行，一个正整数，表示最大的优秀程度。 
样例 #1 
样例输入 #1 
6 2
20 25 1 3 5 8
 
样例输出 #1 
2
 
提示 
【样例解释】 
一共只能选择不超过 
    
     
      
       
        2
       
      
      
       2
      
     
    2 个数字。 
若选择 
    
     
      
       
        1
       
      
      
       1
      
     
    1 个数字，则选择 
    
     
      
       
        20
       
      
      
       20
      
     
    20，优秀程度是 
    
     
      
       
        1
       
      
      
       1
      
     
    1。 
若选择 
    
     
      
       
        2
       
      
      
       2
      
     
    2 个数字，选择 
    
     
      
       
        20
       
       
        ×
       
       
        25
       
       
        =
       
       
        500
       
      
      
       20 times 25=500
      
     
    20×25=500，优秀程度是 
    
     
      
       
        2
       
      
      
       2
      
     
    2。 
可见，优秀程度最大是 
    
     
      
       
        2
       
      
      
       2
      
     
    2，而且显然不存在更优秀的数字了。 
【数据范围】 
对于 
    
     
      
       
        10
       
       
        %
       
      
      
       10%
      
     
    10% 的数据，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        10
       
      
      
       1 leq n leq 10
      
     
    1≤n≤10。 
对于 
    
     
      
       
        20
       
       
        %
       
      
      
       20%
      
     
    20% 的数据，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        20
       
      
      
       1 leq n leq 20
      
     
    1≤n≤20。 
对于 
    
     
      
       
        60
       
       
        %
       
      
      
       60%
      
     
    60% 的数据，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        80
       
      
      
       1 leq n leq 80
      
     
    1≤n≤80。 
对于 
    
     
      
       
        80
       
       
        %
       
      
      
       80%
      
     
    80% 的数据，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        200
       
      
      
       1 leq n leq 200
      
     
    1≤n≤200。 
对于所有数据，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        300
       
      
      
       1 leq n leq 300
      
     
    1≤n≤300，
    
     
      
       
        1
       
       
        ≤
       
       
        k
       
       
        ≤
       
       
        n
       
      
      
       1 leq k leq n
      
     
    1≤k≤n，
    
     
      
       
        1
       
       
        ≤
       
       
        
         a
        
        
         i
        
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         18
        
       
      
      
       1 leq a_i leq 10^{18}
      
     
    1≤ai≤1018。 
似乎是难题 
但会分解质因数的朋友们一定知道，只要集齐两位大神{2,5}，就可以召唤出10（末尾的0） 
解法1 
用的是
    
     
      
       
        d
       
       
        f
       
       
        s
       
      
      
       dfs
      
     
    dfs，最初想用
    
     
      
       
        d
       
       
        p
       
      
      
       dp
      
     
    dp，可不大会（可惜啊）
 于是，代码呼之欲出（其实我已经优化过了，只是数据是在太大了） 
#include
#define N 307
using namespace std;
int n,k,dp[N][2],ans;
long long x;
void dfs(int ui,int a,int b,int nn){
	if(nn==k+1){
		ans=max(ans,min(a,b));
		return;
	}
	for(int i=ui+1;i<=n;i++)
		dfs(i,a+dp[i][0],b+dp[i][1],nn+1);
}
signed main(){
	scanf("%d %d",&n,&k); 
	for(int i=1;i<=n;i++){
		scanf("%lld",&x);
		while(x%2==0){
			dp[i][0]++;
			x/=2;
		}
		while(x%5==0){
			dp[i][1]++;
			x/=5;
		}
	}
	dfs(0,0,0,1);
	printf("%d",ans);
	return 0;
}
 
结果1 

    
     
      
       
        
         AC
        
       
      
      
       color{green}text{AC}
      
     
    AC四点+
    
     
      
       
        
         TLE
        
       
      
      
       color{black}text{TLE}
      
     
    TLE四点 
解法2 

    
     
      
       
        d
       
       
        f
       
       
        s
       
      
      
       dfs
      
     
    dfs败阵下场，
    
     
      
       
        d
       
       
        p
       
      
      
       dp
      
     
    dp上阵！！！
 
    
     
      
       
        d
       
       
        
         p
        
        
         
          a
         
         
          ,
         
         
          b
         
         
          ,
         
         
          c
         
        
       
       
        =
       
      
      
       dp_{a,b,c}=
      
     
    dpa,b,c=使用第
    
     
      
       
        a
       
      
      
       a
      
     
    a个数，使用
    
     
      
       
        b
       
      
      
       b
      
     
    b个数，
    
     
      
       
        
         k
        
        
         c
        
       
      
      
       k_c
      
     
    kc的数量 注：
    
     
      
       
        k
       
       
        =
       
       
        {
       
       
        2
       
       
        ,
       
       
        5
       
       
        }
       
       
         
       
       
        c
       
       
        =
       
       
        0
       
       
        /
       
       
        2
       
      
      
       k={2, 5} c=0/2
      
     
    k={2,5} c=0/2
 答案 
#include
#define N 307
using namespace std;
int n,k,dp[N][N][2],ans;
long long x;
signed main(){
	scanf("%d %d",&n,&k); 
	for(int i=1;i<=n;i++){
		scanf("%lld",&x);
		while(x%2==0){
			dp[i][1][0]++;
			x/=2;
		}
		while(x%5==0){
			dp[i][1][1]++;
			x/=5;
		}
	}
	for(int i=1;i<=n;i++){
		for(int s=i-1;s>=0;s--)//上一个使用第s个数
			for(int j=k;j>=2;j--){//使用j个数
				dp[i][j][0]=max(dp[s][j-1][0]+dp[i][1][0],dp[i][j][0]);
				dp[i][j][1]=max(dp[s][j-1][1]+dp[i][1][1],dp[i][j][1]);
			}
		ans=max(ans,min(dp[i][k][1],dp[i][k][0]));//判断末尾最多有多少0
	}
	printf("%d",ans);
	return 0;
}
 
结果2 

    
     
      
       
        
         AC
        
       
      
      
       color{green}text{AC}
      
     
    AC

数据点编号	t y p e type type	n n n
1 1 1	1 1 1	n ≤ 10 n leq 10 n≤10
2 2 2	1 1 1	n ≤ 100 n leq 100 n≤100
3 3 3	1 1 1	n ≤ 6000 n leq 6000 n≤6000
4 ∼ 5 4 sim 5 4∼5	2 2 2	n ≤ 10 n leq 10 n≤10
6 ∼ 7 6sim 7 6∼7	2 2 2	n ≤ 100 n leq 100 n≤100
8 ∼ 10 8 sim 10 8∼10	2 2 2	n ≤ 6000 n leq 6000 n≤6000

期末考试讲解（欢迎吐槽）

C/C++/C#相关栏目本月热门文章