2023CCPC河南省赛 VP记录

感觉现在的xcpc，风格越来越像CF，不是很喜欢，还是更喜欢多点算法题的比赛

VP银了，VP银也是银

感觉省赛都是思维题，几乎没有算法题，感觉像打了场大型的CF

B题很简单没开出来，一直搞到最后，后来发现原来是卡常了....换种写法就过了

队名是偶像yinwuxx，杭电一队著名选手QwQ

话说好像很快就要篮球被了，我去，什么都不会了，一直在写CF的S b题

怎么办，感觉真的要没了

m d，别到时候区域赛名额没搞出来，篮球被没奖，直接亏损最大化了

 Dashboard - 2023 CCPC Henan Provincial Collegiate Programming Contest - Codeforces

简略写一下思路吧：

A：

 思路：签到，一开始还想字符串哈希判回文，结果只需要n^2判几次就好了

Code：队友写的
 

#include<bits/stdc++.h>
using namespace std;
const int mxv=2e5+9;
#define int long long
char s[mxv];
map<char,int> mp;
void solve(){cin>>s,mp.clear();int len=strlen(s)-1;if(len==0){cout<<"NaN\n";return;}int flag=1;for(int i=0;i<=len;i++){if(s[len]==s[i]){flag=1;for(int j=i,k=len;j<=k;j++,k--)if(s[j]!=s[k]){flag=0;break;}if(flag==1){cout<<"HE\n";return;}}if(mp[s[i]]==0) mp[s[i]]=1;else break;}cout<<"NaN\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--) solve();return 0;
}

B:

 思路：

一开始的想法是二分K，然后在check函数里面把所有段的RMQ搞出来，如果存在这一段的最小值小于前一段的最大值就是False，否则就是True

然后T14了....因为线段树的RMQ复杂度多了个log....

然后就换了ST表，然后第二维开成33，MLE了....

事实上N是1e6的数据范围，开成22就够了

注意到不需要二分，直接枚举复杂度也是够的，于是换成了枚举

然后是莫名其妙的RE，到最后也是RE，也不知道为什么

事实上check函数里面不把RMQ扔进vector里面，直接扫一遍，记录上一次的最大值然后判就过了，被卡了好几小时....

Code：

#include <bits/stdc++.h>//#define int long longusing namespace std;const int mxn=1e6+10;
const int mxe=1e6+10;
const int mxv=1e3+10;
const int mod=1e9+7;int N;
int a[mxn];
int F_min[mxn][22],F_mx[mxn][22];
int lg[mxn];void ST_init(){for(int j=1;j<=22;j++){for(int i=1;i+(1<<(j-1))<=N;i++){F_min[i][j]=min(F_min[i][j-1],F_min[i+(1<<(j-1))][j-1]);F_mx[i][j]=max(F_mx[i][j-1],F_mx[i+(1<<(j-1))][j-1]);}}
}
void L_init(){lg[1]=0;for(int i=2;i<mxn;i++) lg[i]=lg[i>>1]+1;
}
int query_mi(int l,int r){int k=lg[r-l+1]; return min(F_min[l][k],F_min[r-(1<<k)+1][k]);
}
int query_mx(int l,int r){int k=lg[r-l+1]; return max(F_mx[l][k],F_mx[r-(1<<k)+1][k]);
}
void solve(){cin>>N;L_init();for(int i=1;i<=N;i++){cin>>a[i];F_min[i][0]=F_mx[i][0]=a[i];}if(is_sorted(a+1,a+1+N)){cout<<N<<'\n';return;}ST_init();int ans=0;for(int k=1;k<=N;k++){int last=0,ok=1;for(int l=1;l<=N;l+=k){int r=min(l+k-1,N);if(query_mi(l,r)<last){ok=0;break;}last=query_mx(l,r);}ans+=ok;}cout<<ans<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}

C：

思路：

猜了个结论就过了，很奇怪，这种题还是第一次碰到

#include <bits/stdc++.h>//#define int long longusing namespace std;const int mxn=1e6+10;
const int mxe=1e6+10;
const int mxv=1e3+10;
const int mod=1e9+7;string s1;void solve(){cin>>s1;string s2=s1.substr(0,1000);s1.erase(0,1000);if(s1.find(s2)!=-1) cout<<"No"<<'\n';else cout<<"Yes"<<'\n';   
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}

 

D题图论难题，会不了一点

E：

思路：

一开始队友写的DFS，然后T了，换成DP然后MLE了

是个很篮球杯风格的DP，但是开了三维MLE

换成vector也MLE，关掉define也是MLE

这件事告诉我们，正式比赛一般是不卡这种东西的

我滚了一下数组就AC了

Code：

#include<bits/stdc++.h>
using namespace std;
const int mxv=5e2+9,mxn=1e3+3;
const int Inf=0x3f3f3f3f;
//#define int long long
int n,m,x;
char s[mxv][mxv];
int dx[]={0,0,1};
int dy[]={0,1,0};
int dp[2][mxv][mxn];
void solve(){cin>>n>>m>>x;//  vector< vector < vector<int> > > dp(2,vector< vector<int> >(m+1,vector<int>(x+1,-Inf)));//dp(i,j,k):到达(i,j)，已经修改了k次的最大价值for(int i=0;i<=1;i++){for(int j=0;j<=m;j++){for(int k=0;k<=x;k++){dp[i][j][k]=-Inf;}}}for(int i=1;i<=n;i++) cin>>s[i]+1;if(s[1][1]=='1') dp[1&1][1][0]=1;else if(s[1][1]=='0') dp[1&1][1][0]=0;else dp[1][1][1]=1,dp[1&1][1][0]=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=0;k<=x;k++){if(i+1<=n){dp[(i+1)&1][j][k]=max(dp[(i+1)&1][j][k],dp[i&1][j][k]);if(s[i+1][j]=='1')dp[(i+1)&1][j][k]=max(dp[i&1][j][k]+1,dp[(i+1)&1][j][k]);				if(s[i+1][j]=='?'&&k-1>=0)dp[(i+1)&1][j][k]=max(dp[i&1][j][k-1]+1,dp[(i+1)&1][j][k]);}if(j+1<=m){dp[i&1][j+1][k]=max(dp[i&1][j+1][k],dp[i&1][j][k]);if(s[i][j+1]=='1')dp[i&1][j+1][k]=max(dp[i&1][j][k]+1,dp[i&1][j+1][k]);				if(s[i][j+1]=='?'&&k-1>=0)dp[i&1][j+1][k]=max(dp[i&1][j][k-1]+1,dp[i&1][j+1][k]);}}}}int ans=0;for(int i=0;i<=x;i++) ans=max(ans,dp[n&1][m][i]);cout<<ans<<"\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) solve();return 0;
}

 F：

思路：

首先显然是要排序，然后选K个元素对应区间长度为K，所以就是滑动窗口滑过去就可以了，维护一下RMQ，统计一下最大的min*max

Code：

#include <bits/stdc++.h>#define int long longusing namespace std;const int mxn=5e5+10;
const int mxe=5e5+10;
const int mxv=1e3+10;
const int mod=1e9+7;struct ty{int mi;
}tree[mxe<<2];int N,K;
int a[mxn],b[mxn];void pushup(int rt){tree[rt].mi=min(tree[rt<<1].mi,tree[rt<<1|1].mi);
}
int query(int rt,int l,int r,int x,int y){if(x<=l&&r<=y){return tree[rt].mi;}int mid=l+r>>1;int res=1e18;if(x<=mid) res=min(res,query(rt<<1,l,mid,x,y));if(y>mid) res=min(res,query(rt<<1|1,mid+1,r,x,y));return res;
}
void build(int rt,int l,int r){if(l==r){tree[rt].mi=b[l];return;}int mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);pushup(rt);
}
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++) b[i]=a[i]-a[i-1];build(1,2,N);//for(int i=1;i<=N;i++) cout<<a[i]<<" \n"[i==N];//for(int i=2;i<=N;i++) cout<<b[i]<<" \n"[i==N];int ans=1e18;for(int l=1;l+K-1<=N;l++){int r=l+K-1;int mx=a[r]-a[l];int mi=query(1,2,N,l+1,r);ans=min(ans,mi*mx);}cout<<ans<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}

 

G题大模拟不想写

H：

思路：

需要对N和2*k进行分类讨论

如果N/k<0.5，那么最小值一定是0，最大值就是0.5,0.5.....这样子放，答案就是N/0.5，因为最后几个一定是0

否则最小值就是0.49,0.49这样子放，答案就是最后剩下的数的上取整，最大值就是0.5,0.5这样放，答案就是K-1个1+最后一个数上取整

Code：

#include<bits/stdc++.h>
//#define int long long
#define rep(i,a,n) for(int i=a; i<=n ;i++)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define sc second
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const double eps=0.5, exs=0.49999999999999999;
void solve(){int n, k;cin>>n>>k;double c=n-(k-1)*exs;//cout<<c<<'\n';if(c<0.5){int ans2=int(n/0.5);cout<<0<<' '<<ans2<<'\n';}else{int ans1=0, ans2=0;ans1=int(c+0.5);double d=n-(k-1)*0.5;ans2=int(d+0.5)+k-1;cout<<ans1<<' '<<ans2<<'\n';}
}
signed main(){ios;int t=1;cin>>t;while(t--){solve();}return 0;
}

I:

直接看这个：【容斥+扫描线】2023CCPC河南省赛 I 数正方形_lamentropetion的博客-CSDN博客

JL都是神秘题，不会QwQ