Logo zrl123456 的博客

博客

招财猫专题比赛题解

...
zrl123456
2025-12-01 12:51:26
我咋啥也不会/ll

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-16 18:40:32

招财猫专题比赛题解

A 招财猫做数学题

考察内容：欧几里得定理。
题目简述：求 $\gcd(a,b,a+b)$ 和 $lcm(a,b,a+b)$。

众所周知： $$\gcd(a,b)=\gcd(b,a\bmod b)$$ $$lcm(a,b)=a\times b\div\gcd(a,b)$$ $$\gcd(a,b,c)=\gcd(a,\gcd(b,c))$$ $$lcm(a,b,c)=lcm(a,lcm(b,c))$$ 那么我们得到： $$\begin{aligned}lcm(a,b,c)&=lcm(a,b\times c\div \gcd(b,c))\&=a\times b\times c\div\gcd(b,c)\div\gcd(a,b\times c\div\gcd(b,c))\end{aligned}$$ 结束。

代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
int a,b; 
signed main(){
	FAST;
	cin>>a>>b;
	cout<<__gcd(a+b,__gcd(a,b))<<' '<<a*b\/__gcd(a,b)*(a+b)\/__gcd(a*b\/__gcd(a,b),a+b);
    return 0;
}

B 最大数字

考察内容：字符串，高精度。
题意简述：求字符串中最大的数字所在的位置，最大数字 $\le 10^{100}$。

高精度比较：

  • 先比较位数，位数多的数就大。
  • 从最高位开始，比较每一位，直到比较出大小。

这就是一个模拟题。
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
string s,mx="0",x;
int mxa,l=0;
inl bool compare(string a,string b){
	if(a.size()<b.size()) return 1;
	if(a.size()>b.size()) return 0;
	rep(i,0,a.size()-1){
		if(a[i]<b[i]) return 1;
		if(a[i]>b[i]) return 0;
	}
	return 0;
}
signed main(){
	FAST;
	cin>>s;
	rep(i,0,s.size()-1)
		if(isdigit(s[i])){
			if(!l) l=i+1;
			x+=s[i];
		}else if(x!=""){
			if(compare(mx,x)){
				mx=x;
				mxa=l;
			}
			x="";
			l=0;
		}
	if(x!=""&&compare(mx,x)) cout<<l;
	else cout<<mxa;
    return 0;
}

C emo 的招财猫

考察内容：01 背包。
题目简述：求 $c_{1\dots n}$，使 $c_i\in\{0,1\}$，$\sum_{i=1}^nc_i\times v_i\le m$，$\sum_{i=1}^nw_i\times c_i$ 最大。

01 背包板子题。当然我知道有人不会背包
第一层循环正序枚举 $i$（意思是选前 $i$ 个物品），第二层循环枚举 $j$（意思是背包的容量为 $j$），那么对于每一个 $i,j$，第 $i$ 个物品可以选，可以不选，那么可以得到：
$$f_{i,j}=\min(f_{i-1,j-v_i}+w_i,f_{i-1,j})$$ 由于每一个 $f_{i,j}$ 只与 $f_{i-1,j}$ 有关，所以第一维可以压掉，但 $j$ 要倒序枚举，因为 $f_{i,j}$ 只跟 $f_{i-1,j-x}(x\ge 0)$ 有关。

代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=6e3+5,M=8e4+5;
int n,m,v[N],w[N],f[M],ans;
signed main(){
	FAST;
	cin>>n>>m;
	rep(i,1,n) cin>>v[i]>>w[i];
	rep(i,1,n)
		per(j,m,v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);
	rep(i,0,m) ans=max(ans,f[i]);
	cout<<ans;
    return 0;
}

D [WFZ7789] 最近的质数（简易版）

逆天数据

考察内容：埃氏筛。
题目大意：$n$ 次询问，每次给出一个 $k$，求 $\min_{x\in prime}(|x-k|)$。

首先进行埃氏筛（他的思路就是筛去每一个质数的倍数），他的复杂度约为 $O(n\log_2\log_2n)$。
筛到多少合适呢？
我们可以筛到 $\max_{i=1}^n(a_i)+25$，因为一个数是质数的几率是 $\frac{1}{log_2x}$，于是多开 $25$。
然后对于每一个 $k$，我们循环查找即可，不需二分，还是因为质数的密度较大。

结束。
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=5e6+5,M=1e5+5;
int cnt,n,k[M],mx;
bool vis[N];
inl void init(int x){
	rep(i,2,x)
		if(!vis[i])
			rep(j,2,x\/i) vis[j*i]=1;
}
signed main(){
	FAST;
	cin>>n;
	rep(i,1,n){
		cin>>k[i];
		mx=max(mx,k[i]);
	}
	init(mx+25);
	rep(i,1,n){
		if(!vis[k[i]]) cout<<0<<endl;
		else{
			int mx=0,mn=0;
			while(vis[mx+k[i]]) ++mx;
			while(vis[k[i]-mn]) ++mn;
			cout<<min(mx,mn)<<endl;
		}
	}
    return 0;
}

E 草方块

考察：递推。
题目简述：给定一个 $n\times m$ 的格子图，求里面的长方形和正方形数量。

$O(n^4)$ 做法：

暴力枚举矩形的左上坐标和右下坐标，复杂度为 $O(n^4)$。

$O(n^2)$ 做法：

暴力枚举矩形的长和宽，复杂度为 $O(n^2)$。

$O(n)$ 做法：

我们考虑到，取一个矩形是在格子图的长和宽上取一条线段，他们的可能性分别有 $\displaystyle\frac{n(n+1)}{2}$ 和 $\displaystyle\frac{m(m+1)}{2}$ 种，那么一共就有 $\displaystyle(\frac{n(n+1)}{2})(\frac{m(m+1)}{2})$ 种。
然后我们只需枚举正方形的边长即可。

$O(1)$ 做法：

正方形的个数是 $\displaystyle\sum_{i=1}^{\min(n,m)}(n-i+1)(m-i+1)$，我们要把它变成 $O(1)$ 的。 $$\begin{aligned}\sum_{i=1}^{\min(n,m)}(n-i+1)(m-i+1)&=\sum_{i=1}^{\min(n,m)}(\min(n,m)-i+1)(\min(n,m)-i+1)+(\min(n,m)-i+1)(\max(n,m)-\min(n,m))\&=\sum_{i=1}^{\min(n,m)}i^2+i(\max(n,m)-\min(n,m))\&=(\sum_{i=1}^{\min(n,m)}i^2)+(\max(n,m)-\min(n,m))(\sum_{i=1}^{\min(n,m)}i)\&=\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}(\max(n,m)-\min(n,m))\end{aligned}$$ （平方和公式见 P2669 [NOIP2015 普及组] 金币 讲解）。

代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int MOD=1e9+7;
int n,m,inv2,ans,ans1,inv3;
inl int poww(int a,int b){
	int num=a,ans=1;
	while(b){
		if(b&1) (ans*=num)%=MOD;
		(num*=num)%=MOD;
		b>>=1;
	}
	return ans;
}
signed main(){
	FAST;
	cin>>n>>m;
	if(n<m) swap(n,m);
	n%=MOD;
	m%=MOD;
	inv2=poww(2,MOD-2);
	inv3=poww(3,MOD-2);
	ans=((n*(n+1)%MOD*inv2%MOD*m%MOD*(m+1)%MOD*inv2%MOD)%MOD+MOD)%MOD;
\/\/	cout<<ans<<endl;
	ans1=((m*(m+1)%MOD*(m<<1|1)%MOD*inv2%MOD*inv3%MOD+(n-m)*m%MOD*(m+1)%MOD*inv2%MOD)%MOD+MOD)%MOD;
	ans=((ans-ans1)%MOD+MOD)%MOD;
	cout<<ans1<<' '<<ans<<endl;
    return 0;
}
\/\/5*3+4*2+3*1
\/\/3*3+2*2+1*1
\/\/2*(3+2+1)

F 招财猫

考察：线段树。
题意简述：给你一个序列 $a_{1,2,\dots,n}$，有以下三种操作：

  1. 将 $[l,r]$ 区间内的数增加 $v$。
  2. 将 $[l,r]$ 区间内的数减少 $v$。
  3. 求 $[l,r]$ 区间内的数的和。

$n^2$ 暴力想必都会写，那么如何降低复杂度？
我们应引入一个高级数据结构：线段树。

线段树是一个像下面这张照片的数据结构：
每一个节点存的是他所对应的 $[l,r]$ 区间的和（其他的也可以），实现方法请参考 线段树讲解。
请系统学习过树状数组的同学可以尝试参考 树状数组做线段树，并尝试解此题。
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=1e5+5;
int n,q,a[N],opt,l,r,v;
struct trees{
	int l,r,lan,sum;
}t[N<<2];
inl void pushup(int x){
	t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
inl void build(int x,int l,int r){
	t[x].l=l;
	t[x].r=r;
	if(l==r){
		t[x].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);
}
inl void pushdown(int x){
	if(t[x].lan==0) return;
	t[x<<1].lan+=t[x].lan;
	t[x<<1|1].lan+=t[x].lan;
	t[x<<1].sum+=(t[x<<1].r-t[x<<1].l+1)*t[x].lan;
	t[x<<1|1].sum+=(t[x<<1|1].r-t[x<<1|1].l+1)*t[x].lan;
	t[x].lan=0;
}
inl void add(int x,int l,int r,int v){
	if(l<=t[x].l&&t[x].r<=r){
		t[x].sum+=(t[x].r-t[x].l+1)*v;
		t[x].lan+=v;
		return;
	}
	pushdown(x);
	int mid=(t[x].l+t[x].r)>>1;
	if(l<=mid) add(x<<1,l,r,v);
	if(r>mid) add(x<<1|1,l,r,v);
	pushup(x);
}
inl int getsum(int x,int l,int r){
	if(l<=t[x].l&&t[x].r<=r) return t[x].sum;
	pushdown(x);
	int mid=(t[x].l+t[x].r)>>1,tmp=0;
	if(l<=mid) tmp+=getsum(x<<1,l,r);
	if(r>mid) tmp+=getsum(x<<1|1,l,r);
	return tmp;
}
signed main(){
	FAST;
	cin>>n>>q;
	rep(i,1,n) cin>>a[i];
	build(1,1,n);
	rep(i,1,q){
		cin>>opt;
		if(opt==1){
			cin>>l>>r>>v;
			add(1,l,r,v);
		}else if(opt==2){
			cin>>l>>r>>v;
			add(1,l,r,-v);
		}else{
			cin>>l>>r;
			cout<<getsum(1,l,r)<<endl;
		}
	}
    return 0;
}

G 招财猫要送红包了！

考察：单调队列，动态规划。
题意简述：在二维平面上，你要去 $n$ 个亲戚家送红包，你的家在 $(x_0,y_0)$，第 $i$ 个亲戚的家在 $(x_i,y_i)$。
你需要从 $1$ 到 $n$ 的顺序去送红包，但你每次最多拿 $k$ 个红包，求走过的最短距离。

$O(nk)$ 做法：

设 $f_i$ 是送完 $i$ 家亲戚，再回到原点所走过的最短距离，$\text{dist}(x,y)$ 是从 $x$ 点到 $y$ 点的距离，$sum_i$ 是距离的前缀和，即 $\displaystyle \sum_{k=1}^{i-1}\text{dist}(k,k+1)$，那么： $$f_i=\min_{j=i-k}^{i-1}(f_j+\text{dist}(0,j+1)+sum_i-sum_{j+1}+\text{dist}(i,0))$$ 时间复杂度为 $O(nk)$，超时。

$O(n\log_2n)$ 做法：

很明显，$f_i$ 只跟 $f_j-sum_{j+1}+\text{dist}(0,j+1)\ (i-k\le j\le i-1)$ 有关，那么这就是区间最小值，我们可以线段树维护，请读者自行编码。

复杂度为 $O(n\log_2n)$，得分 $80$ 分。

$O(n)$ 做法：

我们又想到可以用双端队列来维护滑动窗口，这样复杂度就可以降到 $O(n)$。

代码：

#include<bits\/stdc++.h>
#define m(i,j) sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))
#define ans(i) f[i]+m(i+1,0)-sum[i+1]
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
deque<int>d;
const int MAX=5e5+5;
int n,k,x[MAX],y[MAX];
double sum[MAX],f[MAX];
void que(int l){
	while(!d.empty()&&d.front()+k<=l) d.pop_front();
	while(!d.empty()&&ans(d.back())>ans(l)) d.pop_back();
	d.push_back(l);
	return; 
}
signed main(){
	FAST;
	cin>>n>>k;
	rep(i,0,n) cin>>x[i]>>y[i];
	rep(i,1,n) sum[i]=sum[i-1]+m(i,i-1);
	d.push_back(0);
	rep(i,1,n){
		f[i]=ans(d.front())+m(i,0)+sum[i];
		que(i);
	}
	printf("%.6lf",f[n]);
	return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

鲁ICP备2025150228号

服务器时间: 2026-03-17 23:34:10 | 开源项目