第十三届蓝桥杯大赛软件赛省赛C/C++ 大学 A 组

lyrrr / 2024-09-13 / 原文

之前没接触过oi赛制打了一下心态小崩。。以为会了五题写出来对了两题，我就是纯纯小丑哈哈。
只打了两个小时也不能算正经vp把，就当是一个补题

2.灭鼠先锋

推必败必胜局面即可。具体的我就是乱推的，对于必胜的可能要稍微多想一会，对于必败的只要找出一种必败情况那显然就是必败了。但是因为看错题所以写反了。
~~（这题也要放代码？）~~

#include <iostream>
using namespace std;
int main()
{
  cout<<"LLLV"<<endl;
  return 0;
}

4.选数异或

思路：通过预处理找到每个l右边最小可行的r，然后查询就是O(1)。注意要处理两遍，第一遍先找到两个数异或等于x的最小r（显然是选每个数a右边第一个x^a)，第二遍遍历lmin进一步缩小范围。

不知道为啥wa了（真是败给oi赛制了牛魔的）。后面重新写了一下分类讨论过了

#include<bits/stdc++.h>
using namespace std;
const int maxn=2097152;
int a[maxn];
int lmin[maxn];bool vis[maxn];
vector<int>E[maxn];
set<int>st;
int main()
{
  int n,m,x;cin>>n>>m>>x;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    E[a[i]].push_back(i);
    st.insert(a[i]);
  }
  for(int i=1;i<=n+1;i++)lmin[i]=0x3f3f3f3f;
  for(int i:st){
    if(vis[i])continue;
    int tmp=x^i;vis[i]=1;vis[tmp]=1;
    if(tmp==i){
    	for(int j=E[i].size()-1;j>0;j--){
    		lmin[E[i][j-1]]=E[i][j];
		}
	}
	else{
		int len1=E[tmp].size(),len2=E[i].size();
		int li=0,lj=0;
		while(li<len2&&lj<len1){
			int xi=E[i][li],xj=E[tmp][lj];
			if(xi>xj){
				lmin[xj]=xi;lj++;
			}
			else{
				lmin[xi]=xj;li++;
			}
		}	
	}
  }
  for(int i=n;i>=1;i--){
  	lmin[i]=min(lmin[i],lmin[i+1]);
  	//cout<<lmin[i]<<' ';
  } 
  while(m--){
    int l,r;cin>>l>>r;
    if(r>=lmin[l])cout<<"yes"<<endl;
    else cout<<"no"<<endl;
  }
  return 0;
}

5.爬树的甲壳虫

不会概率。

6.青蛙过河

我看到nlogn的复杂度又可以二分第一时间想的是二分+dp结果直接假了。。甚至写成了贪心（所以还是要多考虑一下思路正确性）

其实是结论题（佬说别的方法做不了的时候可能就是缺结论）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
#define pb push_back
const int maxn = 1e5+10;
int h[maxn],f[maxn],x,n,pre[maxn];
bool jud(int mid){
	bool q=1;
  for(int i=mid;i<n;i++){
  	if(pre[i]-pre[i-mid]<x)q=0;
  }
  if(q)return 1;
  else return 0;
}
signed main(){
  cin>>n>>x;
  x*=2;
  int l=1,r=n;bool xqq=1;
  for(int i=1;i<n;i++){
    cin>>h[i];pre[i]=pre[i-1]+h[i];
  }
  int mid=(l+r)>>1;
  while(l<r){
    if(jud(mid))r=mid;
    else l=mid+1;
    mid=(l+r)>>1;
    //cout<<mid<<endl;
  }
  cout<<mid<<endl;
}