2024河南省赛vp补题

按题目难度递增，补了部分题 ABHLM

B 贪心

一开始感觉是dp，但是WA5

void solve()
{int n;cin>>n;vector<int>c(n+1);vector<int>dp(n+1,0);forr(i,1,n){cin>>c[i];}forr(i,1,n){forr(a,1,i/c[i]){if(i<c[i]*a)break;dp[i]=max(dp[i],dp[i-a*c[i]]+a);}}int ans=0;forr(i,1,n)ans=max(dp[i],ans);cout<<ans<<endl;
}

看了题解发现都用的是贪心

• 最优子结构：每次选择花费最小的，买的最多
• 买了本次最小的，找之后子数组里下一个最小的去买

void solve()
{int n;cin>>n;vector<int>minn(n+1),c(n+1);forr(i,1,n)cin>>c[i];minn[n]=c[n];reforr(i,1,n-1){minn[i]=min(minn[i+1],c[i]);//从后往前找最小值 从前往后看就是上个最小值之后子数组的最小值}// forr(i,1,n)cout<<minn[i]<<endl;int cnt=0,ans=0;forr(i,1,n){cnt++;if(c[i]==minn[i]&&cnt>=c[i]){ans+=(cnt/c[i]);cnt%=c[i];}}cout<<ans<<endl;
}

M 二分查找

$a_i-k{b}_i\le x\le a_i-k{b}_i$
找让x的区间存在的最小k值

const int N=3e5+10;//vp时跟神经病一样开小了 但是报的是TLE
int a[N],b[N],n;
bool check(int k){int mn=1e9+10,mx=-1e9-10;forr(i,1,n){mn=min(mn,a[i]+k*b[i]);mx=max(mx,a[i]-k*b[i]);if(mx>mn)return false;}return mn>=mx;
}
void solve()
{cin>>n;forr(i,1,n)cin>>a[i];forr(i,1,n)cin>>b[i];int l=0,r=1e9;while (l<r){int mid=(l+r)>>1;if(check(mid)){r=mid;}else l=mid+1;}cout<<l<<endl;
}

L dp

• 两个时间：运行时间$a_i$、debug时间 有x个bug就是$x^4$
• $d{p}_i=min(d{p}_{i-x}+a_i+x^4),1\le x\le 22$
• 因为22^4=234,256>2e5，所以x最大枚举到22

inline int pw(int t){return t*t*t*t;
}
void solve()
{int n,m;cin>>n>>m;vector<int>a(m+1);vector<int>dp(m+1);forr(i,1,m){cin>>a[i];}int ans=0;// dp[1]=a[1]+1;forr(i,1,m){dp[i]=dp[i-1]+a[i]+1;forr(j,2,22){if(i-j<0)break;dp[i]=min(dp[i],dp[i-j]+a[i]+pw(j));}// cout<<dp[i]<<' ';}cout<<dp[m]<<endl;
}

H 逆元 思维 模拟

通过这道题发现对取模和乘法运算的运算顺序不熟悉… %和* /优先级相同

• 最后的递增数列顺序一定是放进去的数列从小到大排序
• 按照排序后的顺序，模拟操作顺序，去找概率
• 本次取出序列中这个数的概率=$\frac{当前栈中这个数的个数}{当前栈总大小}$
• 如果当前栈中没这个数，就不可能实现，概率=0

const int M=998244353;
int fpow(int a,int  b){int res=1;while (b){if(b&1)res=(res*a)%M;b>>=1;a=(a*a)%M;/* 注意以下不一样a=4a*=a%3; a先%3再*a 相当于a=a*(a%3)  =4a=(a*a)%3; 先a*a 再%3 =1*/ }return res%M;
}
int inv(int a){return fpow(a,M-2);
}
void solve()
{int n;cin>>n;vector<int>a(2*n+1),s;forr(i,1,2*n){cin>>a[i];if(a[i]!=-1)s.push_back(a[i]);}sort(s.begin(),s.end());map<int,int>mp;int sz=0,id=0,nm=1,dnm=1;int ans=1;forr(i,1,2*n){if(a[i]!=-1)mp[a[i]]++,sz++;else{if(id>=n)break;if(mp[s[id]]<=0){return cout<<0<<endl,void();}ans=(ans*mp[s[id]])%M;ans=(ans*inv(sz))%M;//ans=(ans*mp[s[id]]*inv(sz))%M; 会爆longlongmp[s[id]]--;sz--;id++;}}cout<<ans<<endl;
}

A 构造

题意：给出一个数n(<=1e8)、幸运数d，找$n\cdot k=N$，N中包含1~9和至少2个d，求k
构造方法：

• $N^{\prime }=123456789d$是保底能满足N的数字，但是不一定能被n整除
• 如何能让n整除N？如果n=233
  • 继续在123456789d后面添加n的数位个数个0，给n腾出位置，不会进位影响前面构造好的数，变成$1000N^{\prime }=123456789d000$
  • 补上$n-1000N^{\prime }\%n$，构造成能被n整除的数$N=1000N^{\prime }+n-1000N^{\prime }\%n$

合法性：
n最多9位，n的数位个数为$\lceil \lg n\rceil$，$\frac{N}{n}=\frac{10^{\lceil \lg n\rceil }{N}^{\prime }}{n}\le 2\cdot 10^9\cdot \frac{10^{\lceil \lg n\rceil }}{n}\le 2\cdot 10^{10}$ 符合题意

const int M=1234567890;
void solve()
{int n,d;cin>>n>>d;int Np=M+d,tp=n;while (tp)tp/=10,Np*=10;int m=Np%n;int ans=Np+n-m;// cout<<ans%n<<endl;cout<<(int)(ans/n)<<endl;
}

K

学习中，待施工…