本文章由 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}$，有以下三种操作：
- 将 $[l,r]$ 区间内的数增加 $v$。
- 将 $[l,r]$ 区间内的数减少 $v$。
- 求 $[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;
}
故最后答案为：
鲁ICP备2025150228号