本次是whr和zy出的题，题目质量也挺高，建议把能补的题都补了。
比赛链接
A题最短路问题：
这一题时间是两秒，而且数据范围也不是很大。我直接爆搜过的，也没卡掉，我先提供一个爆搜的代码：
思路：
从起点开始依次遍历每一个能入队的点（可以被更新的点）将其入队，取队头的点更新其他的点，直到队列为空，f[][]数组记录答案，f [ i ] [ j ] 表示 从起点到 ( i , j ) 的最短距离。
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N=1000+3,M=N*2,mod=998244353;
int n,m,x,y;
int mp[N][N];//存地图
int f[N][N];//f[i][j]表示从起点到(i,j)的最短距离
int dx[]={0,1,0,-1};//---用dx和dy从0到3的值分别表示点右，下，左，上的坐标变化。
int dy[]={1,0,-1,0};
queue<pair<int,int>> que;//队列存点
void solve(){
cin>>n>>m>>x>>y;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
cin>>mp[i][j],f[i][j]=1e18;//初始化点到其他店的距离为正无穷
que.push({1,1});//起点入队
f[1][1]=0;//起点到自身的距离为零
while(!que.empty()){
auto t=que.front();que.pop();
int sx=t.first,sy=t.second;//去除队头的两个点
int dic=f[sx][sy];
for(int i=0;i<=3;++i){//依次遍历右下左上四个点
int tx=sx+dx[i],ty=sy+dy[i];//分别表示i从0到3时，起点的右下左上四个点
if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
if(dic+mp[tx][ty]<f[tx][ty]){//如果这个点可以被更新就入队。
f[tx][ty]=dic+mp[tx][ty];//对该点进行更新
que.push({tx,ty});//该点入队
}
}
}
}
cout<<f[x][y]<<'\n';//输出答案
// for(int i=1;i<=n;++i){
// for(int j=1;j<=m;++j)
// cout<<f[i][j]<<" ";
// cout<<'\n';
// }
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _; _=1;
//cin>>_;
while(_--)solve();
}
/*
10 10 3 6
10 10 1 10 10 10 10 10 10 10
1 10 1 10 10 10 10 10 10 10
1 10 1 10 1 1 10 10 10 10
1 10 1 10 1 10 10 10 10 10
1 10 1 1 1 10 10 10 10 10
1 10 1 10 10 10 10 10 10 10
1 10 1 1 1 10 10 10 10 10
1 10 1 10 1 10 10 10 10 10
1 10 1 10 1 10 10 10 10 10
1 1 1 10 1 1 1 1 1 1
*/
这题也可以用堆优化版的dijkstar做，建议先去学一下堆优化版的dijkstar算法再来做这道题，我把一位同学的dijkstar算法做的粘在这里，可以借鉴一下：
#include <bits/stdc++.h>
#define endl "\n"
#define pii pair<int,pair<int,int>>
#define debug(x) cout << #x << ": -----> " << x << endl;
// typedef long long ll;
// typedef unsigned long long ull;
using namespace std;
const int maxn=1100;
int mp[maxn][maxn];
int dis[maxn][maxn];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int n,m,gx,gy;
bool st[maxn][maxn];
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m>>gx>>gy;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
priority_queue<pii,vector<pii>,greater<pii>> pq;
pq.push({0,{1,1}});
memset(dis,0x3f,sizeof dis);
dis[1][1]=0;
while(pq.size()){
auto t=pq.top(); pq.pop();
int x=t.second.first,y=t.second.second;
int dist=t.first;
if(st[x][y]) continue;
st[x][y]=true;
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m) continue;
if(dis[xx][yy]>dist+mp[xx][yy]){
dis[xx][yy]=dist+mp[xx][yy];
pq.push({dis[xx][yy],{xx,yy}});
}
if(xx==gx&&yy==gy){
cout<<dis[xx][yy]<<endl;
return 0;
}
}
}
return 0;
}
B题纯纯签到，没一点坑。略。。。。
C题我是用单调栈做的：
就是每入栈一个元素检查栈头的三个元素是否合法。合法既出栈。
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N=2e5+3,M=N*2,mod=1e9+7;
char stk[N];//栈
int n;
string s;
int cnt,ans;//cnt表示站内有几个元素，既指向栈头,ans记录答案
void solve(){
cin>>n>>s;
int len=s.size();
for(int i=0;i<len;++i){
stk[++cnt]=s[i];
if(stk[cnt]=='c'&&cnt>=3&&stk[cnt-1]=='f'&&stk[cnt-2]=='z')cnt-=3,++ans;
//栈头合法就出栈三个元素并且ans++;
}cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _; _=1;
while(_--)solve();
}
这道题有的同学是直接对原字符串进行处理，不过道理一样，我把这题一血代码粘一下，可以借鉴一下：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
int a = 0;
string s;
cin >> n >> s;
for (int i = 0; i < n; i++)
{
if (s[i] == 'z' && s[i + 1] == 'f' && s[i + 2] == 'c')
{
s.erase(i, 3);
i = i - 3;
a = a + 1;
}
}
cout << a;
return 0;
}
D题我是用二分做的：
思路就是二分答案，看答案是否合法，输出最小值最大的合法答案：
我的做法思路比较简单，但实现对你们来说可能比较难。建议学好二分和前缀和思想后再来自己做一遍这一道题。
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N=1e5+3,M=N*2,mod=1e9+7;
int n,k,a[N],sa[N]; // sa[ ]记录前缀和
vector<int> ve;
bool check(int mid){
int op=lower_bound(ve.begin(),ve.end(),mid)-ve.begin();
if(op*mid-sa[op]<k){
return false;
}else return true;
}
void solve(){
cin>>n>>k;
for(int i=1;i<=n;++i)cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n;++i)sa[i]=sa[i-1]+a[i],ve.push_back(a[i]);
int l=0,r=1e8;
while(l<r){
int mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
int op=lower_bound(ve.begin(),ve.end(),l)-ve.begin();
// cout<<"----"<<op<<'\n';
if(op*l-sa[op]>k)cout<<l-1<<'\n';
else cout<<l<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _; _=1;
//cin>>_;
while(_--)solve();
}```
第二种做法：也是二分加前缀和的做法，但实现不同
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int a[N];
int n,k;
bool cheak(int x){
int res=0;
for(int i=1;i<=n;i++){
res+=(max(0ll,x-a[i]));
}
return res<=k;
}
signed main(){
//ios::sync_with_stdio(false);cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
int l=0,r=1e14;
while(l<r){
int m=l+r+1>>1;
if(cheak(m)) l=m;
else r=m-1;
}
cout<<l;
}
E题比较简单，大部分人都过了，我还是粘一下一个同学的代码吧。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=100;
int n;
vector<string> v[2];
int main()
{
cin >> n;
for(int i=1; i<=n; i++) {
int a;
string name;
cin >> a >> name;
v[a].push_back(name);
}
for(int i=0,j=v[1].size()-1; i<v[0].size(); i++,j--){
cout << v[0][i] << " " << v[1][j] << endl;
}
return 0;
}
F题：
这是去年ccpc河南省赛A题，其实这是一个简单dp题：
（去年这道题是队友签的，我比赛的时候都没看这道题，就赛后看了一眼）
代码及思路如下：
（建议学会01背包和完全背包，理解状态转移之后再来看这一道题）
//dp[i][0]表示前i个事件都没有选择使用技能
//dp[i][1]表示前i个事件已经选择使用技能了
int dp[N][2];
void solve()
{
memset(dp, 0, sizeof dp);
int n; cin >> n;
for (int i = 1; i <= n; i ++ )
{
string op; int val;
cin >> op >> val;
if (op[0] == 'G')//对于get不管有没有使用技能， 金币数都要增加
{
dp[i][0] = dp[i - 1][0] + val;
dp[i][1] = dp[i - 1][1] + val;
}
else
{
//如果前i个事件都没有选择使用技能
dp[i][0] = max(dp[i - 1][0] - val, 0);
//前i-1个事件没有选择使用技能，但是当前选择使用
//前i-1个事件已经使用过技能，当前不可用
//比较两种情况哪一种金币数最多
dp[i][1] = max(dp[i - 1][0], max(dp[i - 1][1] - val, 0));
}
}
cout << max(dp[n][0], dp[n][1]) << "\n";
}
G这道题有点麻烦，就是模拟，模拟，模拟，知道平年，闰年，知道一个月多少天，有耐心就能做出来。
代码如下：（这题我着实不想写，粘的一位同学的代码）
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=100005;
LL s,y,m,d,x,n;
int days[20] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
void slove(){
cin >> s >> x >> n;
y = s/10000;
m = s/100%100;
d = s%100;
int t=n,f=0;
while(n--){
d++;
if(y%4==0 && m==2) f=1;
else f=0;
if(d>days[m]+f) {
d = 1;
if(++m>12) m=1,y++;
}
}
cout << y << (m<10 ? "0":"") << m << (d<10 ? "0":"") << d << ' ';
x--;
cout << (x+t)%7+1 << endl;
}
int main()
{
int t;
cin >> t;
while(t--) slove();
return 0;
}
H题过的人有点少，读懂题就可以做。。。不解释了，好好读题
#include<bits/stdc++.h>
using namespace std;
const int N=101;
int a[N];
int ans[N][11][11];
signed main(){
int mx=0,n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
mx=max(a[i],mx);
}
int pre=0,x=0;
for(int u=1;u<=mx;u++){
for(int k=1;k<=10;k++){
for(int i=1;i<=n;i++){
if(a[i]>=u){
if(pre!=i){
x++;
ans[i][u][k]=x;
}
else{
x+=2;
ans[i][u][k]=x;
}
pre=i;
}
}
}
}
for(int i=1;i<=n;i++){
cout<<"ID"<<i<<"\n";
for(int j=1;j<=a[i];j++){
for(int k=1;k<=10;k++){
cout<<ans[i][j][k]<<" ";
}
cout<<"\n";
}
}
}
综上：
A题：爆搜/堆dijkstar算法
B题：签到
C题：栈
D题：二分+前缀和
E题：签到
F题：dp
G题：模拟，模拟，模拟
H题：模拟，模拟，模拟
A C D F这四道题有能力的一定要全部补了
这次题的质量很高，为出题人点赞。。。