2023CCPC河南省赛 VP记录

谁践踏了优雅 2024-03-16 13:32 91阅读 0赞

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

**VP银了，VP银也是银**

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

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

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

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

**怎么办，感觉真的要没了**

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

![2c00f1ab3bc34bafbeb0d436757d26dd.png][]

[Dashboard - 2023 CCPC Henan Provincial Collegiate Programming Contest - Codeforces][]

简略写一下思路吧：

A：![1a1e01cbea0144dbbe0a6a0ecf9ce809.png][]

思路：签到，一开始还想字符串哈希判回文，结果只需要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;
    }

![cbf9ba29f274485f9fee9a515b534224.png][]

思路：

一开始的想法是二分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 long
    
    using 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：

![e4e9c87c7181432fb6f0e8815529b984.png][]

思路：

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

#include <bits/stdc++.h>
    
    //#define int long long
    
    using 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：

![89d0ae0830e94f229a55d36c96a88a78.png][]

思路：

一开始队友写的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：

![8a73f365790d408aa31641ebcae4914d.png][]

思路：

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

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using 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：

![9ede36a303424f68883e91aacb1e2ecf.png][]

思路：

需要对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;
    }

![4a4a9bf491eb44d3a14b3f7f5a777097.png][]

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

JL都是神秘题，不会QwQ

[2c00f1ab3bc34bafbeb0d436757d26dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/e510936558ad47e5b87fb31dee957f10.png
[Dashboard - 2023 CCPC Henan Provincial Collegiate Programming Contest - Codeforces]: https://codeforces.com/gym/104354
[1a1e01cbea0144dbbe0a6a0ecf9ce809.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/3d12b3b9230f464d9d5bd1dcb9b8ed71.png
[cbf9ba29f274485f9fee9a515b534224.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/f3644ddb2dcd4ad68f0ea8586db2a95c.png
[e4e9c87c7181432fb6f0e8815529b984.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/cb6904f5f88b4608a5043ad971287b7d.png
[89d0ae0830e94f229a55d36c96a88a78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/77dd2f81da544286a52b2b0d7b2a7785.png
[8a73f365790d408aa31641ebcae4914d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/e87328b07df34244bd64c923eb57ca70.png
[9ede36a303424f68883e91aacb1e2ecf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/e6bfbd6463a24d4b84993d37330173e6.png
[4a4a9bf491eb44d3a14b3f7f5a777097.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/40fe9ce890fb43bbb75ef5f8f3c55e7b.png
[2023CCPC_ I _lamentropetion_-CSDN]: https://blog.csdn.net/weixin_62528401/article/details/131050994?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22131050994%22%2C%22source%22%3A%22weixin_62528401%22%7D