2022年13届蓝桥杯省赛c/c++A组练习
发布时间
阅读量：
阅读量
1.裁纸刀
题解
经分析可知，
边缘部分需进行4次裁剪操作。
其中，
内部裁剪过程包含两种不同的方式：
首先，
先处理行再处理列：
横向方向上的总操作次数为【 行数-1
根据上述计算可知，在一个具有n行m列的二维码中
#include <iostream>
using namespace std;
int main()
{
cout<<"443"<<endl;
return 0;
}
cpp2.灭鼠先锋
题解
#include <iostream>
using namespace std;
int main()
{
/* * 对于只有一行的情况
* 如果只有1个位置，先手输
* 2个位置，后手输（先手1，后手1）
* 3个位置，后手输（先手2，后手1）
* 4个位置，共有以下几种情况（题目中第一行）
* XOOO: （剩余3个空位）先手输
* XXOO: （剩余2个空位）先手输
* OXOO: 先手输
* OXXO: 先手输
* * 由上可知，先开始下第二行的人将输掉比赛
* 对于以下四种情况
* XOOO: 后手通过使棋局变成 XOXO 可保证自己赢得比赛
* XXOO: 后手赢
* OXOO: 后手赢（下一步：OXOX）
* OXXO: 先手赢
*/
cout << "LLLV" << endl;
return 0;
}
cpp
3.选数异或
题解
#include <iostream>
#include<map>
#include<cmath>
using namespace std;
int main()
{
int n, m, x;
cin>>n>>m>>x;
int Rightest[100005]; //在区间[1,i]中，使得[j,i]区间存在a^b=x的最大的j的取值
map<int, int> LastPosition; //某个值出现的最右的位置
for(int i = 1; i <=n; i++)
{
int a;
cin>>a;
Rightest[i] = max(Rightest[i-1],LastPosition[a^x]);
LastPosition[a] = i;
}
while(m--)
{
int l, r;
cin>>l>>r;
if(Rightest[r] >= l) cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
return 0;
}
cpp
4.爬树的甲壳虫
题解
题解区的代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
const int N = 1e5+9;
ll n,x[N],y[N];
ll qsm(ll q,ll m){
ll ans=1;
while(m){
if(m&1)ans=ans*q%mod;
q=q*q%mod;m>>=1;
}
return ans;
}
ll inv(ll q){return qsm(q,mod-2);}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
ll a=x[n]*inv(y[n])%mod,b=1;
for(int i=n-1;i>0;i--){
ll p=x[i]*inv(y[i])%mod,q=(y[i]-x[i])*inv(y[i])%mod;
a=(p+q*a%mod)%mod,b=(q*b%mod+1)%mod;
//a=x[i]*inv(y[i])+(y[i]-x[i])*inv(y[i])*a;
//b=(y[i]-x[i])*inv(y[i])*b+1;
}
cout<<((-b*inv(a-1))%mod+mod)%mod;
}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
cpp
5.最长不下降子序列
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+9;
int n,k,m,a[N],b[N],dp[N],t[N<<2];
void updata(int o,int l,int r,int pos,int val){
t[o]=max(t[o],val);
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)updata(2*o,l,mid,pos,val);
else updata(2*o+1,mid+1,r,pos,val);
}
int getmax(int o,int l,int r,int nl,int nr){
if(l==nl&&r==nr)return t[o];
int mid=(l+r)>>1;
if(mid>=nr)return getmax(2*o,l,mid,nl,nr);
else if(mid<nl)return getmax(2*o+1,mid+1,r,nl,nr);
else return max(getmax(2*o,l,mid,nl,mid),getmax(2*o+1,mid+1,r,mid+1,nr));
}
// 1 2 3 4 5 6 7 8
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
// 离散化
sort(b+1,b+n+1);
m=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+m+1,a[i])-b;
for(int i=1;i<=n;i++){
dp[i]=getmax(1,1,m,1,a[i])+1;
updata(1,1,m,a[i],dp[i]);
}
int ans=0;
memset(t,0,sizeof t);
for(int i=n;i>k;i--){
ans=max(ans,dp[i-k]+k-1+getmax(1,1,m,a[i-k],m)+1);
int tem=getmax(1,1,m,a[i],m)+1;
updata(1,1,m,a[i],tem);
}
ans=max(ans,k+getmax(1,1,m,a[k+1],m));
cout<<ans<<'\n';
}
// 1 2 3 ... i-k i-k+1 i-k+2 i-k+3 ... i ...
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int q=1;
//cin>>q;
while(q--){
solve();
}
return 0;
}
cpp
6.扫描游戏
7.数的拆分
题解
题解区题解
//本题是一道数学思维题,需要找到将x拆分为x=q1^y1*q2^y2的本质
//由唯一分解定理,x=p1^k1*p2^k2*...*pn^kn,即x必然能分解成若干个质因子的幂次之和
//此外我们还知道,任意一个大于1的数都可以分解成若干个2和3的和
//因此可以用分解质因子的思想,先分解质因子再讨论它们的幂次能否合并成2k1+3k2的形式
//假设x的质因子列表为(p1,k1),(p1,k2),...,(pn,kn),前者为因子后者为幂次
//可以发现对于每个质因子p,只要其幂次k大于1,就一定能表示成k=2k1+3k2的形式(可自行举例验证)
//然后将k1的部分合并到y1中,k2的部分合并到y2中,即符合题意
//若某个质因子的幂次为1,则无法进行如上合并,即不符合题意
//此外还要注意x本身是平方数或立方数,必然符合题意(q2=1即可)
//例:x=2^2 * 3^13 * 7^8,则2=2*1+3*0(k1=1,k2=0),13=2*2+3*3(k1=2,k2=3),8=2*4+3*0(k1=4,k2=0)
//可分解为x=(2*3^2*7^4)^2 * (3^3)^3,即x1=(2*3^2*7^4),x2=9,y1=2,y2=3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5000;
bool vis[N];//埃氏筛法的标记数组
int prime[N];//保存所有的质数(5000以内即可)
int t=0;//质数的总数
bool check1(ll x)//验证x是否为平方数
{
ll y=sqrt(x);
if(y*y==x)return true;
return false;
}
bool check2(ll x)//验证x是否为立方数
{
ll y=pow(x,1.0/3);//此处存在精度问题,保险起见用while循环验证一下
while(y*y*y<=x)
{
if(y*y*y==x)return true;
y++;
}
return false;
}
void sieve()//埃氏筛法筛质数
{
vis[1]=1;
for(int i=2;i<N;i++)
{
if(vis[i]==0)
{
prime[t++]=i;
for(int j=i+i;j<N;j=j+i)
{
vis[j]=1;
}
}
}
}
void solve()
{
ll x;scanf("%lld",&x);
if(check1(x)||check2(x))//x本身是平方数或立方数,必然符合题意
{
printf("yes\n");
return ;
}
for(int i=0;i<t;i++)//枚举所有的质数
{
if(x%prime[i])continue;//不是质因子,跳过
int cnt=0;//记录该质因子的幂次
while(x%prime[i]==0)//是质因子
{
cnt++;//记录其幂次
x=x/prime[i];//不断除以该质因子
}
if(cnt==1)//幂次为1,无法合并成2k1+3k2的形式
{
printf("no\n");
return ;
}
}
if(check1(x)||check2(x))printf("yes\n");
//此时x要么为1,要么是一个更大的质因子或平方数/立方数
//如果剩下的x是平方数或立方数(含1),必然符合题意,如果是一个更大的质因子(幂次为1),则不符合题意
else printf("no\n");
}
int main()
{
sieve();
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
cpp
8.推导部分和
题解
//带权并查集
//以一个根结点为参照，l-1到根结点的距离为d[l-1] r到根结点的距离为d[r]
//根据前缀和原理 [l, r] 区间和为 d[r] - d[l - 1]
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = (int) 2e5 + 10;
//并查集
int p[N];
//到根的权重
LL d[N];
int n, m, q;
int find(int x)
{
if (p[x] != x)
{
int t = p[x];
p[x] = find(p[x]);
d[x] += d[t];
}
return p[x];
}
int main()
{
cin >> n >> m >> q;
//初始化并查集
for (int i = 1; i <= n; i++) p[i] = i;
while (m-- > 0)
{
LL l, r, s;
cin >> l >> r >> s;
//找根结点
int pl = find(l - 1), pr = find(r);
//合并
p[pl] = pr;
d[pl] = d[r] - d[l - 1] - s;
}
//查询
//如果l, r都在同一个集合，则存在结果
while (q-- > 0)
{
int l, r;
cin >> l >> r;
int pl = find(l - 1), pr = find(r);
if (pl != pr) cout << "UNKNOWN" << endl;
else cout << d[r] - d[l - 1] << endl;
}
return 0;
}
cpp
9.青蛙过河
题解
#include <iostream>
using namespace std;
int n, x;
int s[100005]; //前n项和
bool check(int k)
{
for (int i = 1; i <= n - k; i++)
if (s[i + k - 1] - s[i - 1] < 2 * x)
return false;
return true;
}
int main()
{
cin >> n >> x;
for (int i = 1; i < n; i++)
{
int a;
cin >> a;
s[i] = s[i - 1] + a;
}
int l = 1, r = n;
while (l < r)
{
if (check((l + r) / 2))
r = (l + r) / 2;
else
l = (l + r) / 2 + 1;
}
cout << l;
return 0;
}
cpp
10.求和
题解
#include <iostream>
using namespace std;
int main()
{
long long sum = 0; //注意需用long long
for(int i = 1; i <= 20230408; i++){
sum += i;
}
cout<<sum<<endl;
return 0;
}
cpp
全部评论 (0)
还没有任何评论哟~