NEUQ-ACM第七届图灵杯题解（超级详细版）

ゝ一世哀愁。 2021-09-07 06:03 220阅读 0赞

# 溜圈圈+Thursday out+爱做笔记的Awen+Awen的一卡通+Iris天下第一+我的梦想是世界和平！+跳格子+计分板 #

> 出自acm一组。

### 文章目录 ###

*  溜圈圈+Thursday out+爱做笔记的Awen+Awen的一卡通+Iris天下第一+我的梦想是世界和平！+跳格子+计分板
 *   *  A.溜圈圈
     *   *  1.题目描述
         *  2.题目分析
         *  3.具体代码
     *  B.Thursday out
     *   *  1.题目描述
         *  2.题目分析
         *  3.具体代码
     *  C.爱做笔记的Awen
     *   *  1.题目描述
         *  2.题目分析
         *  3.具体代码
     *  D.Awen的一卡通
     *   *  1.题目描述
         *  2.题目分析
         *  3.具体代码
     *  E.Iris天下第一
     *   *  1.题目描述
         *  2.题目分析
         *  3.具体代码
     *  F.我的梦想是世界和平！
     *   *  1.题目描述
         *  2.题目分析
         *  3.具体代码
     *  G.跳格子
     *   *  1.题目描述
         *  2.题目分析
         *  3.具体代码
     *  H.计分板
     *   *  1.题目描述
         *  2.题目分析
         *  3.具体代码

## A.溜圈圈 ##

### 1.题目描述 ###

> BigSheep总是喜欢溜圈，但是他有几个原则：
> 
>     只能向左转，且不能在同一个地方多次左转。
>     每次只走不同的圈。
>     每次走圈走遍整个区域，同一个点只去一次，起点不一定需要等于终点。
> 
> 有一天，BigSheep半夜睡不着觉，跑去操场溜圈。我们可以认为操场是一个n×m的网格图，神奇的BigSheep可以把任意一个格子当作自己的起点开始绕圈，对于BigSheep那些奇怪的原则，我们可以抽象成以下几点：
> 
>     BigSheep在起点时可以任意选择自己的朝向。
>     每次只能直走，或者左转后直走，且不能越过边界。
>     每次走圈的路径不能一样，即同一个路径不能走多次（对于两条路径，存在一个格子(x0,y0)(x_0,y_0)(x0,y0)在第一条路径中是第iii个访问的，在第二条路径中是第jjj个访问的，且i̸=ji\not=
>     ji̸=j，我们即可认为这两条路径是不同的）。
>     每次溜圈都需要遍历每一个格子，且每一个格子只能被访问一次，溜圈的起点和终点不需要保证相邻。
>     
>     BigSheep想知道自己最多可以溜多少圈。
> 
> **样例输入**
> 
> 1
> 
> 2 2  
> **样例输出**
> 
> 4  
> **样例解释**
> 
> （因为没法作图，所以只能用文字解释了，我尽量写的清楚明了QAQ
> 
> 我们定义这个网格图的四个格子分别为(1,1),(1,2),(2,1),(2,2)(1,1),(1,2),(2,1),(2,2)(1,1),(1,2),(2,1),(2,2)。(左上角定义为(1,1)(1  
> , 1)(1,1))
> 
> 所以四种方案如下：
> 
> 方案1：
> 
> 从(1,1)(1,1)(1,1)出发，面向(2,1)(2,1)(2,1).
> 
> (1,1)(1 ,1)(1,1)->(2,1)(2,1)(2,1)->(2,2)(2,2)(2,2)->(1,2)(1,2)(1,2)
> 
> 方案2：
> 
> 从(2,1)(2, 1)(2,1)出发，面向(2,2)(2,2)(2,2).
> 
> (2,1)(2 ,1)(2,1)->(2,2)(2,2)(2,2)->(1,2)(1 ,2)(1,2)->(1,1)(1,1)(1,1)
> 
> 方案3：
> 
> 从(2,2)(2,2)(2,2)出发，面向(1,2)(1,2)(1,2).
> 
> (2,2)(2 ,2)(2,2)->(1,2)(1 , 2)(1,2)->(1,1)(1, 1)(1,1)->(2,1)(2,1  
> )(2,1)
> 
> 方案4：
> 
> 从(1,2)(1,2)(1,2)出发，面向(1,1)(1, 1)(1,1).
> 
> (1,2)(1 ,2)(1,2)->(1,1)(1, 1)(1,1)->(2,1)(2, 1 )(2,1)->(2,2)(2  
> ,2)(2,2)  
> **输入描述**
> 
> 先输入一个T(1≤T≤1000)T(1\\leq T\\leq1000)T(1≤T≤1000)表示测试数据组数。
> 
> 接着每一行输入两个整数nnn，m(1≤n,m≤1000)m(1\\leq n,m\\leq  
> 1000)m(1≤n,m≤1000)，分别表示操场的长和宽。  
> **输出描述**
> 
> 输出共TTT行，每行表示一组测试数据的答案。  
> **样例输入**
> 
> 1
> 
> 2 2
> 
> **样例输出**
> 
> 4
> 
> 提示
> 
> 样例解释
> 
> （因为没法作图，所以只能用文字解释了，我尽量写的清楚明了QAQ
> 
> 我们定义这个网格图的四个格子分别为(1,1),(1,2),(2,1),(2,2)(1,1),(1,2),(2,1),(2,2)(1,1),(1,2),(2,1),(2,2)。(左上角定义为(1,1)(1  
> , 1)(1,1))
> 
> 所以四种方案如下：
> 
> 方案1：
> 
> 从(1,1)(1,1)(1,1)出发，面向(2,1)(2,1)(2,1).
> 
> (1,1)(1 ,1)(1,1)->(2,1)(2,1)(2,1)->(2,2)(2,2)(2,2)->(1,2)(1,2)(1,2)
> 
> 方案2：
> 
> 从(2,1)(2, 1)(2,1)出发，面向(2,2)(2,2)(2,2).
> 
> (2,1)(2 ,1)(2,1)->(2,2)(2,2)(2,2)->(1,2)(1 ,2)(1,2)->(1,1)(1,1)(1,1)
> 
> 方案3：
> 
> 从(2,2)(2,2)(2,2)出发，面向(1,2)(1,2)(1,2).
> 
> (2,2)(2 ,2)(2,2)->(1,2)(1 , 2)(1,2)->(1,1)(1, 1)(1,1)->(2,1)(2,1  
> )(2,1)
> 
> 方案4：
> 
> 从(1,2)(1,2)(1,2)出发，面向(1,1)(1, 1)(1,1).
> 
> (1,2)(1 ,2)(1,2)->(1,1)(1, 1)(1,1)->(2,1)(2, 1 )(2,1)->(2,2)(2  
> ,2)(2,2)

### 2.题目分析 ###

这题属于找规律：很容易看出当只有1行或者1列的时候 情况为2，（1\*1时才为1）；如果是2\*x(x>=2)的话，那么意味着，这个图每个点出发都可以满足条件。 其他情况，除去四个角之外，还可以从中间开始到其他节点结束。

### 3.具体代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main()
    { 
        int t,n,m;
        cin>>t;
        while(t--)
        { 
            cin>>n>>m;
            if(n<m) swap(n,m);
            if(m==1)
            { 
                if(n==1)cout<<"1\n";
                else cout<<"2\n";
            }
            else if(m==2) cout<<n*m<<"\n";
            else cout<<2*(n+m-2)<<"\n";
        }
    }

## B.Thursday out ##

### 1.题目描述 ###

> 11月17日，Zsmj，BigSheep和PerpEternal决定退役了，但是生活需要仪式感，所以他们决定一起去吃顿好的，作为纪念。
> 
>   
> 三个人在街头找到了一家自助餐厅，刚进餐厅，PerpEternal和Zsmj就摊在椅子上，并指使BigSheep去拿吃的，BigSheep也想摊在椅子上，但是因为队内地位实在是太低，所以只能屈服于淫威，老老实实的去拿吃的，餐厅提供的食物可以当做一个序列，每个食物拥有一个营养值aia\_iai，BigSheep知道仨人的食量至少需要营养值为xxx的食物才能吃饱，但是BigSheep也不想多次去拿食物，所以他打算一次拿把一个区间的食物全部拿了，当BigSheep把食物带回到位置上时，PerpEternal突然发问：你俩曾经身为一个ACM选手，能不能算出有多少种方案能够让咱们仨吃饱。但是BigSheep和Zsmj太饿了，所以只好打电话求助亲爱的参赛选手，你能帮帮他俩吗，PerpEternal说了，算不出来不让他俩吃饭。  
> **输入描述**
> 
> 输入一个整数T(1≤T≤10)T(1\\leq T \\leq 10)T(1≤T≤10)表示测试数据组数。
> 
> 每组测试数据先输入两个整数n,x(1≤n≤105,1≤x≤1000)n,x(1\\leq n\\leq10^5,1\\leq x\\leq  
> 1000)n,x(1≤n≤105,1≤x≤1000)分别表示食物的总数和需要的最小营养值。
> 
> 接着一行输入nnn个数，表示每个食物的营养值。  
> **输出描述**
> 
> 输出一个整数表示方案数，因为方案数比较多，所以我们需要对答案进行取模，最后输出的答案需要对100000000710000000071000000007进行取模。
> 
> （若最终答案是100000000810000000081000000008的话，我们只需要输出111即可）  
> **样例输入**
> 
> 2
> 
> 5 5
> 
> 1 1 1 1 1
> 
> 5 2
> 
> 1 1 1 1 1
> 
> **样例输出**
> 
> 1
> 
> 10
> 
> **提示**
> 
> 对于样例1，只有全部吃了才能满足，所以方案只有1种。
> 
> 对于样例2，10种方案如下：(1,2),(1,2,3),(1,2,3,4),(1,2,3,4,5),(2,3),(2,3,4),(2,3,4,5),(3,4),(3,4,5),(4,5)(1,2),(1,2,3),(1,2,3,4),(1,2,3,4,5),(2,3),(2,3,4),(2,3,4,5),(3,4),(3,4,5),(4,5)(1,2),(1,2,3),(1,2,3,4),(1,2,3,4,5),(2,3),(2,3,4),(2,3,4,5),(3,4),(3,4,5),(4,5)

### 2.题目分析 ###

通过输出的答案需要对1000000007进行取模得知，测试数据可能会很大，暴力循环是不可取的。通过求区间和想到通过利用前缀和求出区间和，由于前缀和是单调序列，故可用二分依次定位满足能量需求的区间右端点最小值，从而通过尺度法求得方案数。

### 3.具体代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main()
    { 
    	int t,x,n;
    	long long a[100099]={ };
    	long long sum[100099]={ };
    	long long ans[15];
    	cin>>t;
    	for(int o=1;o<=t;o++)
    	{ 
    		ans[o]=0;
    		cin>>n>>x;
    		for(int i=1;i<=n;i++)  		
            { 
    			cin>>a[i];
    			sum[i]=a[i]+sum[i-1];//求前缀和的预处理
    		}
    		for(int i=1;i<=n;++i)    //二分
    		{ 
                int l=i,r=n+1,tmp=n+1,mid;
                while(l<r)
    			{ 
                    mid=(l+r)/2;
                    if(sum[mid]-sum[i-1]>=x)
    				   r=mid,tmp=mid;
                    else l=mid+1;
                }
                ans[o]=(n-tmp+1+ans[o])%1000000007;
            }
    	}
    	for(int i=1;i<t;i++) cout<<ans[i]<<endl;
    	cout<<ans[t];
    	return 0;
    }

## C.爱做笔记的Awen ##

### 1.题目描述 ###

> 众所周知，Awen非常喜欢写一些心得笔记。这一天他又在写笔记了。已知他可进行如下操作：
> 
> Add x y\[1\]y\[2\]y\[3\]…y\[n\] 在笔记最后添加x个字符，它们分别是y\[1\]y\[2\]y\[3\]…y\[n\]  
> (每一个y\[i\]都是一个小写英文字母)； Del x 删除掉笔记中最后写的x个字符； Copy 复制当前写的所有笔记； Paste  
> 将当前复制的所有文字粘贴在笔记最后。
> 
> 在写完笔记之后，Awen想知道自己究竟写下了什么，你能帮帮他吗？  
> **输入描述**
> 
> 第一行输入一个整数n(0<=n<=100),代表操作的个数。 之后的n行里，每一行输入下面四种操作中的一种： Add x  
> y\[1\]y\[2\]y\[3\]…y\[n\] (1<=x<=100) Del x (1<=x<=100) Copy Paste  
> **输出描述**
> 
> 一串由小写英文字母构成的序列，代表awen最后所写的笔记。  
> **样例输入**
> 
> 6 Add 3 nnb Copy Del 3 Add 6 awennn Del 3 Paste
> 
> **样例输出**
> 
> awennb
> 
> 提示
> 
> 题目保证每次删除的字符数一定不会超过当前所写的字符数。写笔记的过程中字符总数不会超过100000。Awen最开始的笔记是没有字符的。  
> 每一次复制会清空你的剪贴板，比如当笔记内容为awen的时候进行一次复制，当笔记内容变为aaa的时候再进行一次复制。则粘贴在笔记最后的文字是aaa。复制的文字可以被多次粘贴。

### 2.题目分析 ###

直接按照题目要求写那4种操作，a\[10005\]用来记录现有笔记，b\[10005\]用来复制a，c用来确定该执行哪项操作，k用来记录笔记长度，m用来记录复制笔记长度，其他中规中矩，慢慢做即可。

### 3.具体代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main(){ 
    	int n,k=0,m=0;
    	cin>>n;
    	char a[10005],b[10005]={ };
    	while(n--){ 
    		char c[10];
    		cin>>c;
    		if(c[0]=='A'){ 
    			int t;
    			cin>>t;
    			for(int i=k;i<(k+t);i++) cin>>a[i];
    			k+=t;
    		}
    		if(c[0]=='C'){ 
    			for(int i=0;i<k;i++) b[i]=a[i];
    			m=k;
    		}
    		if(c[0]=='D'){ 
    			int t;
    			cin>>t;
    			k-=t;
    		}
    		if(c[0]=='P'){ 
    			int j=0;
    			for(int i=k;i<k+m;i++){ 
    				a[i]=b[j++];
    			}
    			k+=m;
    		}
    	}
    	for(int i=0;i<k;i++) cout<<a[i];
    	cout<<endl;
    	return 0;
    }

## D.Awen的一卡通 ##

### 1.题目描述 ###

> Awen是个很粗心的人，这天他在买饭的时候，发现他的校园一卡通不见了。虽然他知道自己的一卡通应该落在了综合楼，但因为他实在太饿了，想赶紧吃到饭，所以他也可以去行政楼再补办一张一卡通。但他不知道自己究竟是去行政楼再回到原地更快，还是去综合楼再回到原地更快。不过因为补卡需要时间，如果他去选择行政楼的话，还需要在行政楼额外花费a分钟办理补卡。  
> **输入描述**
> 
> 第一行输入两个整数n和m(2<=n,m<=100)，表示行数和列数，代表学校由n行m列的单元格组成。  
> 接下来输入n行数据，每一行包含m个字符。其中字符’.‘表示该单元格为空地，字符’\*'表示该单元格为障碍，字符’s’代表Awen当前的位置，字符’z’代表综合楼的位置，字符’x’代表行政楼的位置。  
> 最后输入一个整数a(0<a<=100000000)，代表Awen如果选择去行政楼，需要花费a分钟办理补卡。  
> **输出描述**
> 
> 输出包含一个字符，如果Awen去综合楼再回到原地的时间更短，输出"wo tu  
> le"，如果Awen去行政楼办卡再回到原地的时间更短，输出"ying ying ying",如果两个时间相同，输出"awennb"。  
> 输出内容不包含双引号。  
> **样例输入**
> 
> 3 3 s.x .\*\* …z 5
> 
> **样例输出**
> 
> wo tu le
> 
> 提示
> 
> Awen在每一个单元格内都可以沿上、下、左、右四个方向移动。但注意障碍是不能走的，Awen也不能移动到学校之外。Awen每次从一个单元格移动到另一个相邻的可移动的单元格都会花费1分钟的时间  
> 题目保证地图中必定有且仅有一个s、x、z，且一定存在路径使Awen从起点移动到综合楼和行政楼。

### 2.题目分析 ###

核心思路是设计一个bfs函数来计算Awen绕过障碍物的前提下到两楼的最短距离，然后再进行比较，其中运用了stl中的队列，比较有难度，属于中档难度题。

### 3.具体代码 ###

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=105;
    typedef pair<int,int> pa;
    int pos[4][2]={ { 1,0},{ -1,0},{ 0,1},{ 0,-1}};
    int n,m,a;
    char b[maxn][maxn],ch;
    int step[maxn][maxn];
    int sx,sy,xx,xy,zx,zy;
    queue<pa>q;
    void bfs(){ 
        int nx,x,y,ny;
        q.push(pa(sx,sy));
        while(!q.empty()){ 
            x=q.front().first;
            y=q.front().second;
            q.pop();
            for(int i=0;i<4;++i){ 
                nx=x+pos[i][0];
                ny=y+pos[i][1];
                if(nx<0||nx>=n||ny<0||ny>=m)continue;
                if(step[nx][ny]==-1&&b[nx][ny]!='*'){ 
                    step[nx][ny]=step[x][y]+1;
                    q.push(pa(nx,ny));
                }
            }
        }
    }
    int main(){ 
        std::ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>n>>m;
        for(int i=0;i<n;++i){ 
            for(int j=0;j<m;++j){ 
                cin>>ch;
                if(ch=='s')sx=i,sy=j;
                else if(ch=='x')xx=i,xy=j;
                else if(ch=='z')zx=i,zy=j;
                b[i][j]=ch;
                step[i][j]=-1;
            }
        }
        bfs();
        cin>>a;
        if(step[xx][xy]*2+a<step[zx][zy]*2)cout<<"ying ying ying\n";
        else if(step[xx][xy]*2+a>step[zx][zy]*2)cout<<"wo tu le\n";
        else cout<<"awennb\n";
    }

## E.Iris天下第一 ##

### 1.题目描述 ###

> Iris今年20岁了，她认为自己有至少20个男朋友是合情合理的。然而世上帅哥千千万，Iris纵有心网罗天下帅哥，可却没有那么多精力去维护她的后宫安宁。因此，Iris为了备战将要到来的面向对象程序设计期末考试，决定抛弃她的一些帅哥。
> 
> 已知Iris的后宫中有n个帅哥，而每天可以用来和帅哥聊天的精力为m。对于每个帅哥，有固定的帅气值和每天与其聊天所需要的花费精力值。请你帮Iris算一下，在抛弃掉一些帅哥以保证每天的精力值够用的情况下（也可能精力过剩而没有抛弃），她的后宫的帅气值总和最大时多少。  
> **输入描述**
> 
> 第一行给出空格隔开的两个正整数n（1 ≤\\leq≤ n ≤\\leq≤ 100000）和m（1 ≤\\leq≤ m ≤\\leq≤  
> 300000），分别表示Iris目前的后宫人数和Iris每天可以用来和帅哥聊天的精力值。
> 
> 接下来的n行中，第i行给出空格隔开的两个正整数s（1 ≤\\leq≤ s ≤\\leq≤ 3）和c（1 ≤\\leq≤ c ≤\\leq≤ 10  
> 9^99）,分别表示与第i个帅哥每天聊天需要花费的精力值和该帅哥的帅气值。  
> **输出描述**
> 
> 共一行，包括一个正整数，表示Iris在精力够用的情况下，后宫最大的帅气值总和。  
> **样例输入**
> 
> 2 2 1 3 2 2
> 
> **样例输出**
> 
> 3

### 2.题目分析 ###

因为最小花费是1-3，所以1-3的LCM最小公倍数是6 ，我们贪心的取，取到只剩下6个的话，开始01背包 。

### 3.具体代码 ###

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    struct ss{ 
    	ll x;
    	ll y;
    	double sum;
    }a[200050];
    ll f[300050];
    bool cmp(ss x,ss y)
    { 
    	return x.sum>y.sum;
    }
    int main()
    { 
    	int n,m;
    	cin>>n>>m;
    	for(int i=0;i<n;i++)
    	{ 
    		ll x,y;
    		cin>>x>>y;
    		a[i].x=x;
    		a[i].y=y;
    		a[i].sum=(double)y/x;
    	}
    	sort(a,a+n,cmp);
    	ll sum=0;
    	int index=-1;
    	ll ans=0;
    	for(int i=0;i<n;i++)  
    	{ 
    		if(sum>=m-9) break;
    		sum+=a[i].x;
    		ans+=a[i].y;
    		index=i;
    	}
    	memset(f,0,sizeof(f));
    	ll temp=0;
    	for(int i=index+1;i<n;i++)
    	{ 
    		for(int j=m;j>=sum+1;j--)
    		{ 
    			int k=j-sum;
    			if(k>=a[i].x)
    				f[k]=max(f[k],f[k-a[i].x]+a[i].y);
    			temp=max(temp,f[k]);
    		}
    	}
    	cout<<ans+temp<<endl;
    	return 0;
     }

## F.我的梦想是世界和平！ ##

### 1.题目描述 ###

> 恭喜FPX获得S9全球总决赛冠军！
> 
> 虽然在征战S9的各大战队中，蓝公主被公认为技术最差的辅助，但是蓝公主凭借姣好的外型，仍然拥有数量可观的妈妈粉。所谓道不同，不相为谋，真正的LPL粉丝并不愿意和妈妈粉一同观看比赛。所幸，梅赛德斯奔驰会展中心提供了三个观战坐席区域，避免双方见面引发冲突。
> 
> 已知今天前往观战的妈妈粉有a人，普通LPL粉丝b人，好斗的LPL粉丝c人，妈妈粉与好斗的LPL粉丝在同一个观战坐席区域相遇会引发冲突，而普通的LPL粉丝无论与妈妈粉还是与好斗的LPL粉丝在一起均可以和平共处。请你帮助主办方计算在不发生冲突的情况下，人数最多的观战坐席区域最少有多少人。  
> **输入描述**
> 
> 第一行给出一个整数t，表示共有t组测试数据。
> 
> 对于每组测试数据，在一行内给出空格隔开的三个整数a，b和c。  
> 1000），分别表示妈妈粉、普通LPL粉丝和好斗的LPL粉丝的人数。  
> **输出描述**
> 
> 对于每组测试数据，在一行内给出一个整数s，表示人数最多的观战坐席区域最少有多少人。 样例输入
> 
> 5 3 5 7 4 8 4 13 10 13 1000 1000 1000 13 22 7
> 
> **样例输出**
> 
> 5 6 13 1000 14

### 2.题目分析 ###

人数最多的观战坐席区域最少有多少人: 在各种的情况下，三个区域中人数最少且大于其他种情况下，区域中人数最少数的这种情况下，区域中人数最多，1.把a和c较大的那个等分了，把b拿出来，2.暴力是对于每个b，往三个台里最小的那个填，3.最后输出三个台最大的，4.这个过程可以直接贪心（xlj）。

### 3.具体代码 ###

#include <bits/stdc++.h>
    using namespace std;
    
    int t;
    int a, b, c;
    int a_room[3];
    
    int main() 
    { 
    	cin >> t;
    	while (t --) 
    	{ 
    		cin >> a >> b >> c;
    		if (c < a) swap(a, c);
    
    		a_room[0] = c/2;
    		a_room[1] = c - c/2;
    		a_room[2] = a;
    
    		sort(a_room, a_room + 3);
    
    		if (a_room[2] * 3 < a + b + c) 
    		{ 
    			double a1 = a, b1 = b, c1 = c;
    			cout << ceil((a1 + b1 + c1) / 3);
    		} 
    		else 
    		{ 
    			cout << a_room[2];
    		}
    		
    		cout << endl;
    	}
    	return 0;
    }

## G.跳格子 ##

### 1.题目描述 ###

> 从左到右有N个台阶，每个台阶的高度为Hi，开始你可以随意选择一个台阶作为初始起点，每次你可以向右边 移动，当且仅当右边的台阶比你现在所在的台阶高度低，问你最多可以移动多少次。  
> **输入描述**
> 
> 一个整数N(1<=N<=200000) 接下来一行有N个数Hi (1<=Hi<=1000000000) 输出描述
> 
> 输出一个数，表示移动的最大次数。  
> **样例输入**
> 
> 7 4 4 5 6 6 5 4
> 
> **样例输出**
> 
> 2

### 2.题目分析 ###

这是一道经典的动态规划（DP）问题，就是求最大连续下降子序列，详细的证明推荐一篇博客，写的非常清楚。

> https://blog.csdn.net/qq\_50216270/article/details/112933050

### 3.具体代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main()
    { 
        int n;
        cin>>n;
        int a[n+1],dp[n+1];
        a[0]=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)
        { 
            dp[i]=1;
            if(a[i]<a[i-1])dp[i]=dp[i-1]+1;
        }
        int maxdp=1;
        for(int i=1;i<=n;i++)
        { 
            maxdp=max(maxdp,dp[i]);
        }
        cout<<maxdp-1;
    }

## H.计分板 ##

### 1.题目描述 ###

> 一个游戏由N个玩家玩，编号从1到N。在游戏开始时，每个玩家初始分数都为K。 当一个玩家正确地回答了一 个问题，其他N-1个玩家每人都会-1分。 在游戏结束时，得分为0分或更低的玩家将被淘汰，剩下的玩家存活下来。 在一场游戏中，玩家总共给出Q个正确答案，其中第i个答案由玩家Ai给出。 请你编写一个程序来确定这N 个玩家是否能在游戏中幸存下来。  
> **输入描述**
> 
> 第一行输入一个整数N(2<=N<=300000)，代表玩家的数量 第二行输入一个整数K(1<=K<=1000000000)，代表初始的分数  
> 第三行输入一个整数Q(1<=Q<=100000)，代表Q轮游戏 接下来一行有Q个数Ai，代表每一轮游戏中获胜的玩家  
> **输出描述**
> 
> 输出仅一行。对于每一个玩家，如果在最后分数大于0，则输出"Yes"，否则输出"No"  
> **样例输入**
> 
> 6 3 4 3 1 3 2
> 
> **样例输出**
> 
> No No Yes No No No

### 2.题目分析 ###

为了简化计算，把给其他玩家扣分变成给答对的玩家+1分，这样理论上来说，每一位玩家每轮都会-1分，把加分和扣分分开，在加上他们的初始分就是最终分。

### 3.具体代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main()
    { 
        int n,k,q;
        cin>>n>>k>>q;
        int a[n+1];
        memset(a,0,sizeof(a));
        for(int i=0;i<q;i++)
        { 
            int j;
            cin>>j;
            a[j]+=1;
        }
        for(int i=1;i<=n;i++)
        { 
            a[i]-=q;
            a[i]+=k;
            if(a[i]>0)cout<<"Yes ";
            else cout<<"No ";
        }
        return 0;
    }