时间原因 快速水了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备注:
如果没有解题思路，可以算一下前几项看看。
#includeusing namespace std;#define int long long #define fp(i,a,b) for(int i=a;i<=b;++i)#define PII pairconst 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 33 1 2 3 3 2输出
3
#includeusing namespace std;#define int long long #define fp(i,a,b) for(int i=a;i<=b;++i)#define PII pairconst 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=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 33 1 2 3 3 2输出
1 1 0示例2
输入
6 3 43 1 2 3 3 2输出
1 0 -1
#includeusing namespace std;#define int long long #define fp(i,a,b) for(int i=a;i<=b;++i)#define PII pairconst 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、
#includeusing namespace std;#define int long long #define fp(i,a,b) for(int i=a;i<=b;++i)#define PII pairconst 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>x,a[x]++;for(int i=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>1;if(calc(mid,i)<=k)r=mid;else l=mid+1;}cout<<l<<" ";}return 0;} O(nlogn) 后缀优化+二分