在此特别感谢牛客技术和各大高校对本次比赛的大力支持~🤩🤩🤩🥰🥰🥰
本次比赛整体难度符合预期通过率，没有很明显的锅，所以还是比较成功的比赛。
题目的难度是按照升序排列，所以也算是降低了一层难度。
祝贺各位通过选拔的同学进入寒假集训！！！
以下是出题人写的题解，不会的题可以参考一下，由于个人代码风格习惯，并未格式化~
赛题链接：(0条未读通知) 河南科技学院寒假集训选拔赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)
查看密码：20240108
A.ACM？acm？⭐
由于可以重新排列字母，并且不区分大小写，所以只需要统计a和A，c和C，m和M的数量，分别计为a_cnt,c_cnt,m_cnt。然后3个的数的最小值即可，最为签到题，也是很友善。
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int a=0,c=0,m=0;
for(int i=0;i<s.size();i++){
if(s[i]=='a'||s[i]=='A') a++;
else if(s[i]=='c'||s[i]=='C') c++;
else if(s[i]=='m'||s[i]=='M') m++;
}
cout<<min({a,c,m});
return 0;
}
B：Happy or unhappy？ 难度：⭐⭐
关键词：快速幂，快速幂运用或__int128_t
我们可以看到数据的范围很大，n最大到了10^18^,而且还有取模，所以让人很容易想到使用快速幂。这道题的思路其实比较简单:总共有m^n^种方案(每个格子都可以从m种颜色中任意取一种)，让B神喜欢的方案有C(m,1)(m-1)^(n-1)^种(因为第一个格子选了一种后，第二个格子有m-1种选法，第三个格子有m-1种选法……第n个格子有m-1种选法，所以是(m-1)^(n-1)^,而第一个格子有m种选法，所以根据乘法原理，答案是m^n^-m(m-1)^(n-1)^（得到的答案再取模即可）,由于此题取模数特意设置较大，所以可能爆longlong，所以所有相乘的地方需要使用快速幂的加法变换才可以通过.
总时间 复杂度
或者也可以直接使用__int128_t ,时间复杂度，这里由于篇幅限制，不做展示。
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define endl "\n"
const i64 mod=100000000003;
i64 ksm_add(i64 a,i64 b){
i64 res=0;
while(b){
if(b&1) res=(res+a)%mod;
a=(a+a)%mod;
b=b>>1;
}
return res;
}
i64 ksm_mul(i64 a,i64 b){
i64 res=1;
while(b){
if(b&1) res=ksm_add(res,a)%mod;
a=ksm_add(a,a)%mod;
b=b>>1;}
return res;
}
void solve(){
i64 n,m;
cin>>n>>m;
i64 ans=ksm_mul(m,n)%mod-ksm_add(m,ksm_mul(m-1,n-1))%mod+mod;
ans=ans%mod;
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;cin>>t;
while(t--){
solve();
}
return 0;
}
C:TieTie! 难度：⭐⭐
关键词：单调栈
我们可以假设每个位置都需要贴壁画，那么最多需要n张。对于任意两个位置，如果高度不一样，那么必然需要两张壁画，而对于两个相同高度的位置则只需要同一张。故需要找出第i张前面的前i-1张中是否存在a[j]==a[i]（j∈[1,i-1])即可，前提是[j,i）中的山比第i座山都要高才可以，否则必然需要另外一张，因为中途高度降低，无法左右连续。对于存储前i-1个高度，我们可以使用单调栈或者队列，或者数组都可以解决。这样便可以找出重复高度的壁画cnt，最后n-cnt就是答案。
每个山的高度最多被数组和单调栈各遍历一次,所以时间复杂度为
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
int main( )
{
int n;
cin>>n;
vector<i64>w(n+1),h(n+1);
for(int i=1;i<=n;i++){
cin>>w[i]>>h[i];
}
i64 ans=0;
stack<i64>q;
for(int i=1;i<=n;i++){
while(q.size()&&q.top()>=h[i]){
if(q.top()==h[i]) ans++;
q.pop();
}
q.push(h[i]);
}
cout<<n-ans;
return 0;
}
D：Pass the difficulty! 难度：⭐⭐⭐
关键词：BFS,状态更新，最短路
不难看出这是一个BFS的题。只需要从坐标（1，1）开始，然后把（1，1）的初始状态入队列，依次判断其上下左右的状态和当前队首的状态，相同的时候判断+2，不同的时候判断+1，然后进行更新到达（nx，ny）的最短时间，如果下一个位置的最短时间可以更新，则入下一个点的可到达状态(和当前队首相反的状态，因为相反状态才可以到达）。最后终点的最短时间就是终点状态0和1的最小值。
时间复杂度
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
i64 d[1001][1001][2];
void solve(){
int n,m;
cin>>n>>m;
vector<vector<char>>a(n+1,vector<char>(m+1));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cin>>a[i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<2;k++) d[i][j][k]=1e18;
auto bfs=[&](int x,int y)->void{
queue<array<int,3>>q;
q.push({x,y,a[x][y]-'0'});
d[x][y][a[x][y]-'0']=0;
int z;
while(!q.empty()){
auto t=q.front();
q.pop();
int nx,ny;
x=t[0],y=t[1],z=t[2];
//上
nx=x-1,ny=y;
if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
int D=d[x][y][z]+1+(a[nx][ny]-'0'==z?1:0);
if(D<d[nx][ny][(a[nx][ny]-'0'==z)?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]){
q.push({nx,ny,a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')});
d[nx][ny][a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]=D;
}
}
//下
nx=x+1,ny=y;
if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
int D=d[x][y][z]+1+(a[nx][ny]-'0'==z?1:0);
if(D<d[nx][ny][(a[nx][ny]-'0'==z)?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]){
q.push({nx,ny,a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')});
d[nx][ny][a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]=D;
}
}
//左
nx=x,ny=y-1;
if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
int D=d[x][y][z]+1+(a[nx][ny]-'0'==z?1:0);
if(D<d[nx][ny][(a[nx][ny]-'0'==z)?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]){
q.push({nx,ny,a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')});
d[nx][ny][a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]=D;
}
}
//右
nx=x,ny=y+1;
if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
int D=d[x][y][z]+1+(a[nx][ny]-'0'==z?1:0);
if(D<d[nx][ny][(a[nx][ny]-'0'==z)?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]){
q.push({nx,ny,a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')});
d[nx][ny][a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]=D;
}
}
}
};
bfs(1,1);
cout<<min(d[n][m][0],d[n][m][1])<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}
E：How much time？ 难度：⭐⭐⭐
关键词：前缀和，树状数组，离散化，二分
对于区间和
可以转化为sum[r]-sum[l-1]≥x，如果要快速查询以r为结尾的区间有多少满足条件的区间，那么公式可以转化为sum[r]-x≥sum[l-1],这时只需要找出在r的左边 小于等于sum[r]-x的区间前缀和数量即可。由于有负数，所以前缀和不单调，故使用树状数组来维护r左边小于等于sum[r]-x的前缀和数量，统计r左边小于等于sum[r]-x的前缀和出现的次数，同时，前缀和的值可能很大，所以要使用离散化，把数组降为数组可容纳的范围.
总时间复杂度
参考代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
#define i64 long long
#define endl "\n"
int n;
i64 tree[N];
vector<i64>all;
i64 lowbit(i64 x){
return x&-x;
}
void add(int x){
for(int i=x;i<all.size();i+=lowbit(i)) tree[i]++;
}
i64 sum(int x){
i64 ans=0;
for(int i=x;i;i-=lowbit(i)) ans=ans+tree[i];
return ans;
}
i64 find(i64 x){
int l=0,r=all.size()-1;
while(l<r){
int mid=l+r>>1;
if(all[mid]>=x) r=mid;
else l=mid+1;
}
return l+1;
}
void solve(){
i64 x;
cin>>n>>x;
vector<i64>a(n+1),s(n+5);
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
for(int i=0;i<=n;i++){
all.push_back(s[i]-x);
all.push_back(s[i]);
}
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
i64 ans=0;
add(find(0));
for(int i=1;i<=n;i++){
ans=ans+sum(find(s[i]-x));
add(find(s[i]));
}
cout<<ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}
F：Attribute M 难度：⭐⭐⭐
关键词：线性DP
考虑DP。
用数组f[i] [j]表示到第i个数取模之后余数为j的情况。
首先预处理for(int i=1;i<=n;i++) f[i] [a[i]%m]=a[i];
对于每个数只有两种情况，要么不要，要么要。
对于不要的情况可直接f[i] [j]=max(f[i] [j],f[i-1] [j]);
要的情况：分类讨论1.a[i]%m≤j和2.a[i]%m>j的情况。
-
可由上一层的j-a[i]%m最大值转移而来，举例当m=5,a[i]=2,j=4,由上一层的2转移过来，因为（2+2）%5==4，
if(f[i-1] [j-a[i]%m]!=0) f[i] [j]=max({f[i] [j],f[i-1] [j],f[i-1] [j-a[i]%m]+a[i]});
如果f[i-1] [j-a[i]%m]==0，说明上一层的取模数等于j-a[i]%m并没有情况，所以不能更新，只能选择不要此数。
2.可以上一层m+j-a[i]%m转移而来，举例当m=5,a[i]=4,j=2,由上一层的3转移过来，因为（4+3）%5==2，
if(f[i-1] [m+j-a[i]%m]!=0) f[i] [j]=max({f[i] [j],f[i-1] [j],f[i-1] [m+j-a[i]%m]+a[i]});
如果f[i-1] [m+j-a[i]%m]==0，说明上一层的取模数等于m+j-a[i]%m并没有情况，所以不能更新，只能选择不要此数。
时间复杂度
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define endl "\n"
void solve(){
int n,m;
cin>>n>>m;
vector<i64>a(n+1);
vector<vector<i64>>f(n+1,vector<i64>(m+1,0));
for(int i=1;i<=n;i++){
cin>>a[i];
}
f[0][0]=0;
for(int i=1;i<=n;i++) f[i][a[i]%m]=a[i];
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
if(j>=a[i]%m){
if(f[i-1][j-a[i]%m]!=0)
f[i][j]=max({f[i][j],f[i-1][j],f[i-1][j-a[i]%m]+a[i]});
else
f[i][j]=max(f[i][j],f[i-1][j]);
}
else{
if(f[i-1][m+j-a[i]%m]!=0)
f[i][j]=max({f[i][j],f[i-1][j],f[i-1][m+j-a[i]%m]+a[i]});
else
f[i][j]=max(f[i][j],f[i-1][j]);
}
}
}
cout<<f[n][0];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}
G：Transporting watermelons 难度：⭐⭐⭐⭐
关键词：凸多边形，外接圆，抽屉原理，FFT
由切线性质可得，一个凸四边形是圆外切四边形当且仅当该四边形的对边之和相等。故问题转化为所给数列中是否存在四个不同的数 a，b，c，d使得a+b=c+d。这是抽屉原理经典模型，暴力枚举即可。作为选拔赛的中等题，为了让大家有一个友好的参赛体验，FFT也可以通过。
时间复杂度
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
void solve(){
int n;
cin>>n;
vector<i64>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
map<i64,i64>H;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(H[a[i]+a[j]]){
cout<<"YES";
return ;
}
H[a[i]+a[j]]=1;
}
}
cout<<"NO";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}
H：Set 难度：⭐⭐⭐⭐⭐
关键词：GCD，动态规划
此题难度较大，作为挑战题给出思路，代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
const int mod=998244353;
int datas[maxn];
int a[maxn][101],n;
int f[maxn][101][101],C[101][101];
int g[maxn][101][101];
int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1){
res=1ll*res*a%mod;
}
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
cin>>datas[i];
}
sort(datas+1,datas+1+n);
for(int i=1;i<=n;i++){
a[i][0]=1;
for(int j=1;j<=100;j++){
a[i][j]=1ll*a[i][j-1]*datas[i]%mod;
}
}
C[0][0]=1;
for(int i=1;i<=100;i++){
C[i][0]=1;
for(int j=1;j<=i;j++){
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
f[0][0][0]=1;
for(int i=1;i<=n;i++){
for(int x=0;x<=100;x++){
for(int y=0;y<=100;y++){
f[i][x][y]=f[i-1][x][y];
}
}
for(int x=0;x<=100;x++){
int d=gcd(x,a[i][1]);
for(int j=0;j<=100;j++){
for(int p=0;p<=j;p++){
f[i][d][j]+=1ll*C[j][p]*f[i-1][x][p]%mod*a[i][j-p]%mod;
f[i][d][j]%=mod;
}
}
}
}
g[n+1][0][0]=1;
for(int i=n;i>=1;i--){
for(int x=0;x<=100;x++){
for(int y=0;y<=100;y++){
g[i][x][y]=g[i+1][x][y];
}
}
for(int x=0;x<=100;x++){
int d=gcd(x,a[i][1]);
for(int j=0;j<=100;j++){
for(int p=0;p<=j;p++){
g[i][d][j]+=1ll*C[j][p]*g[i+1][x][p]%mod*a[i][j-p]%mod;
g[i][d][j]%=mod;
}
}
}
}
int ans=0;
for(int i=1;i<n;i++){
int res1=0;
for(int x=0;x<=100;x++){
int d=gcd(x,a[i][1]);
for(int p=0;p<=d;p++){
res1+=1ll*C[d][p]*f[i-1][x][p]%mod*a[i][d-p]%mod;
res1%=mod;
}
}
int res2=0;
for(int j=1;j<=100;j++){
res2=(res2+g[i+1][j][j])%mod;
}
ans=(ans+1ll*res1*res2%mod)%mod;
}
cout<<ans<<endl;
return 0;
}
京公网安备 11010502036488号