招财猫专题比赛题解

zrl123456 · 2024-04-16 18:40:32 · 题解

招财猫专题比赛题解

A 招财猫做数学题

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

众所周知：

那么我们得到：

结束。

代码：

#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} 只与 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) 的。

（平方和公式见 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] 区间内的数的和。