牛客小白月赛80 A-D

时间原因 快速水了A——D

A、

题目描述

现在给你一个递推公式：
n=0 an=1  ; n=1 an=2  ;n>1 an=2*a(n-1)-a(n-2)
求该数列的第 n 项。由于答案可能过大，你只需要输出答案对 998244353 取模后的值。

输入描述:

一个正整数 n (1≤n≤998244351) 。

输出描述:

一个整数，对应答案。

示例1

输入

1

输出

2

示例2

输入

2

输出

3

备注:

如果没有解题思路，可以算一下前几项看看。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int n;
signed main()
{
    cin>>n;
	cout<<n+1<<"\n";
	
	return 0;
} 
 
 

 B、

题目描述

校园里目前有 N 名学生，这些学生属于 M 个班级。第 i 个人属于第Ai​ 个班级。突然，放学铃声响起，你还没来得及思索，就已经有 K 名学生已经冲出了学校。你不知道已经跑出学校的学生属于哪些班级，但是，你想知道，目前还没出校的学生中，最多有多少学生是属于同一个班级的。

输入描述:

第一行三个正整数 N （1≤N≤10^5）， M（1≤M≤N），K（1≤K≤N）含义如上所述。

第二行 N 个正整数 Ai​（1≤Ai≤M），含义如上所述。

输出描述:

一个整数，表示目前学校里最多有多少同学是属于同一个班级的。

示例1

输入

6 3 3
3 1 2 3 3 2

输出

3

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int n,m,k;
int a[N];
int cnt[N];
signed main()
{
	int mmax=0;
	
    cin>>n>>m>>k;
	
	fp(i,1,n)cin>>a[i],cnt[a[i]]++,mmax=max(mmax,a[i]);
	
    sort(cnt+1,cnt+1+mmax);
	
	int sum=0;
	for(int i=1;i<=mmax-1;i++)
	{
		sum+=cnt[i];
	}	
	if(sum>=k)
	{
		cout<<cnt[mmax];
	}
	else
	{
		cout<<cnt[mmax]-(k-sum);
	}
	
	return 0;
} 
 
 

 C、

题目描述

本题和 D 题的唯一区别是 N 的范围。
校园里目前有 N 名学生，这些学生属于 M 个班级。第 i（i=1,2,...,N）个人属于第Ai​ 个班级。突然，放学铃声响起，你还没来得及思索，就已经有 K 名学生已经冲出了学校。然而，由于某班级的老师还在拖堂，可以确定这个班级目前还没有任何学生离校。现在请你求出，假设恰好只有班级 j（j=1,2,...,M）的老师还在拖堂，在剩下的未拖堂的班级中，还留在学校的人数最多的班级的最少的可能人数是多少。

输入描述:

第一行三个正整数 N（1≤N≤10^2），M（1≤M≤N），K（1≤K≤N）含义如上所述。
第二行 N个正整数 Ai​（1≤Ai≤M），含义如上所述。

输出描述:

M个整数，第 i 个整数表示恰好只有班级 i 的老师还在拖堂，在剩下的未拖堂的班级中，还留在学校的人数最多的班级的最少的可能人数是多少。如果班级 i 拖堂就不可能有 K 名学生冲出学校，则输出 -1。

示例1

输入

6 3 3
3 1 2 3 3 2

输出

1 1 0

示例2

输入

6 3 4
3 1 2 3 3 2

输出

1 0 -1

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int n,m,k;
int a[N];
int cnt[N];
int cnts[N];
signed main()
{
	
    cin>>n>>m>>k; 
	
	fp(i,1,n)cin>>a[i],cnt[a[i]]++;
	
	
	for(int i=1;i<=m;i++)
	{
	    if(n-cnt[i]<k)
	    {
	    	cout<<-1<<" ";
	    	continue;
		}
		for(int j=0;j<=n;j++)
		{
		    int sum=0;
			for(int t=1;t<=m;t++)
			{
				if(t==i)continue;
				sum+=max(0ll,cnt[t]-j);
			}
			if(sum<=k)
			{
			    cout<<j<<" ";
				break;	
			} 	
	    }
	}
	
	return 0;
} 
 
 

 O(n^3)暴力

D、

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e6+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int n,m,k;
int a[N];
int sum1[N],sum2[N];
int calc(int x,int i){
    return (sum2[x]-(a[i]>=x)*a[i])-(sum1[x]-(a[i]>=x))*x;
}
signed main()
{
	
    cin>>n>>m>>k; 
	
	int x;
	for(int i=1;i<=n;i++)cin>>x,a[x]++;
    for(int i=1;i<=m;i++)
        sum1[a[i]]++,sum2[a[i]]+=a[i];
    for(int i=n-1;i>=0;i--)sum1[i]+=sum1[i+1],sum2[i]+=sum2[i+1];
    for(int i=1;i<=m;i++){
        if(n-a[i]<k){
            cout<<-1<<" ";
            continue;
        }
        int l=0,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            if(calc(mid,i)<=k)r=mid;
            else l=mid+1;
        }
        cout<<l<<" ";
    }
	return 0;
} 
 
 

O(nlogn) 后缀优化+二分