【马蹄集】— 百度之星 2023

在这里插入图片描述

BD202301·公园

可以先 $b f s$ 统计一下 $t, f$ 到达每个点的距离，还有 $n$ 到达其他点的距离即其他点到达 $n$ 的距离然后枚举每个点直接计算得到最小值即可
注意特判有人无法到达 $n$ 的情况

code:


#include<bits/stdc++.h>
#define endl '\n'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define F first
#define S second
#define lowbit(x) ((x) & (-x))
#define _ int _T; _T = 1; while(_T --) 
#define int long long
#define no cout << "NO" << endl
#define yes cout << "YES" << endl

using namespace std;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int N = 4e4 + 7;
const int mod = 998244353;
int t,f,n,m;
int te,fe,s;
vector<int> g[N];
int d1[N],d2[N],d3[N];

void bfs(){
    queue<int> q1,q2,q3;
    q1.push(t);
    q2.push(f);
    q3.push(n);
    vector<int> st1(n + 1,0),st2(n + 1,0),st3(n + 1,0);
    st1[t] = 1,st2[f] = 1,st3[n] = 1;
    for(int i = 1;i <= n;i ++){
        d1[i] = 500000;
        d2[i] = 500000;
        d3[i] = 500000;
    }
    d1[t] = 0,d2[f] = 0,d3[n] = 0;
    while(q1.size()){
        auto x = q1.front();
        q1.pop();
        for(auto son : g[x]){
            if(st1[son]) continue;
            st1[son] = 1;
            q1.push(son);
            d1[son] = min(d1[son],d1[x] + 1);
        }
    }
    while(q2.size()){
        auto x = q2.front();
        q2.pop();
        for(auto son : g[x]){
            if(st2[son]) continue;
            st2[son] = 1;
            q2.push(son);
            d2[son] = min(d2[son],d2[x] + 1);
        }
    }
    while(q3.size()){
        auto x = q3.front();
        q3.pop();
        for(auto son : g[x]){
            if(st3[son]) continue;
            st3[son] = 1;
            q3.push(son);
            d3[son] = min(d3[son],d3[x] + 1);
        }
    }
}

void solve(){
    cin >> te >> fe >> s;
    cin >> t >> f >> n >> m;
    for(int i = 0;i < m;i ++){
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs();
    if(d3[t] == 500000 || d3[f] == 500000){
        cout << -1 << endl;
        return;
    }
    int mn = d3[t] * te + d3[f] * fe;
    for(int i = 1;i <= n;i ++){
        int cnt1 = d1[i] * te;
        int cnt2 = d2[i] * fe;
        int cnt3 = d3[i] * (te + fe - s);
        mn = min(mn,cnt1 + cnt2 + cnt3);
    }
    cout << mn << endl;
}

signed main(){
    fast();
    _
    solve();
    return 0;
}

BD202303·第五维度

首先特判下如果 $v$ 不为零的人 $\leq$ 1 那么就是 -1
其他二分算一下能完成多少然后减去最大的然后 return 判断即可

code：


#include<bits/stdc++.h>
#define endl '\n'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define F first
#define S second
#define lowbit(x) ((x) & (-x))
#define _ int _T; _T = 1; while(_T --) 
#define int long long
#define no cout << "NO" << endl
#define yes cout << "YES" << endl

using namespace std;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int N = 1e5 + 7;
const int mod = 998244353;
int n,m;

struct node{
    int s;
    int v;
} a[N];

int check(int x){
    __int128 sum = 0;
    vector<int> v;
    for(int i = 0;i < n;i ++){
        int cnt;
        if(x <= a[i].s) cnt = 0;
        else cnt = (x - a[i].s) * a[i].v;
        v.push_back(cnt);
        sum += cnt;
    }
    int mx = *max_element(v.begin(),v.end());
    sum -= mx;
    return sum <= m;
}

void solve(){
    cin >> n >> m;
    for(int i = 0;i < n;i ++) cin >> a[i].s >> a[i].v;
    int cnt = 0;
    for(int i = 0;i < n;i ++){
        if(a[i].v) cnt ++;
    }
    if(cnt < 2){
        cout << -1 << endl;
        return;
    }
    int l = 0,r = 5e9;
    while(l + 1 != r){
        int mid = l + r >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << r << endl;
}

signed main(){
    fast();
    _
    solve();
    return 0;
}

BD202305·糖果促销

首先第一种方法很明显的二分去特判下 p = 1 即可
第二种则直接计算显然想吃 $k$ 块糖就会产生 $k$ 个糖纸最后一个吃的糖肯定不参与糖纸的置换所以参与糖纸置换的仅有 $k - 1$ 个糖纸那么答案即 $k - (k - 1) / p$

code1:


#include<bits/stdc++.h>
#define endl '\n'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define F first
#define S second
#define lowbit(x) ((x) & (-x))
#define _ int _T; cin >> _T; while(_T --) 
#define int long long
#define no cout << "NO" << endl
#define yes cout << "YES" << endl

using namespace std;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int N = 3e5 + 7;
const int mod = 998244353;
int p,k;

int check(int x){
    int sum = x;
    while(x / p){
        sum += x / p;
        x = x / p + x % p;
    }
    return sum < k;
}

void solve(){
    cin >> p >> k;
    if(!k){
        cout << 0 << endl;
        return;
    }
    if(p == 1){
        cout << 1 << endl;
        return;
    }
    int l = 0,r = k;
    while(l + 1 != r){
        int mid = l + r >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << r << endl;
}

signed main(){
    fast();
    _
    solve();
    return 0;
}

code2:


#include<bits/stdc++.h>
#define endl '\n'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define F first
#define S second
#define lowbit(x) ((x) & (-x))
#define _ int _T; cin >> _T; while(_T --) 
#define int long long
#define no cout << "NO" << endl
#define yes cout << "YES" << endl

using namespace std;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int N = 3e5 + 7;
const int mod = 998244353;
int p,k;

void solve(){
    cin >> p >> k;
    if(!k){
        cout << k << endl;
        return; 
    }
    int ans = k - (k - 1) / p;
    cout << ans << endl;
}

signed main(){
    fast();
    _
    solve();
    return 0;
}

BD202321·新材料

直接遇到出现过得数就与上一次出现的位置距离看是否小于等于 $k$ 即可

code:


#include<bits/stdc++.h>
#define endl '\n'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define F first
#define S second
#define lowbit(x) ((x) & (-x))
#define _ int _T; _T = 1; while(_T --) 
#define int long long
#define no cout << "NO" << endl
#define yes cout << "YES" << endl

using namespace std;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int N = 1e5 + 7;
const int mod = 998244353;
int n,k;

void solve(){
    cin >> n >> k;
    map<int,int> mp;
    map<int,int> mp2;
    int ans = 0;
    for(int i = 1;i <= n;i ++){
        int x; cin >> x;
        if(!mp[x]) mp[x] = i;
        else{
            if(i - mp[x] <= k){
                if(mp2[x]) continue;
                mp2[x] = 1;
                ans ^= x;
            } else{
                mp[x] = i;
            }
        }
    }
    cout << ans << endl;
}

signed main(){
    fast();
    _
    solve();
    return 0;
}

BD202319·新的阶乘

筛一下质数然后暴力跑质数的倍数去统计倍数中含有此质数的指数
~~#define int long long 等于喜提 tle~~

code：


#include<bits/stdc++.h>
#define endl '\n'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define F first
#define S second
#define lowbit(x) ((x) & (-x))
#define _ int _T; _T = 1; while(_T --) 
#define no cout << "NO" << endl
#define yes cout << "YES" << endl

using namespace std;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int N = 1e7 + 7;
const int mod = 998244353;
int st[N];
int x;
int prime[N];
int cnt;

void get_prime(int n){
    for(int i = 2;i <= n;i ++){
        if(st[i]) continue;
        prime[cnt ++] = i;
        for(int j = i + i;j <= n;j += i) st[j] = 1; 
    }
}

void solve(){
    int x; cin >> x;
    get_prime(x);
    cout << "f(" << x << ")=";
    for(int i = 0;i < cnt;i ++){
        int nw = prime[i];
        long long sum = x - (nw - 1);
        for(int j = nw + nw;j <= x;j += nw){
            int k = j;
            int sb = 0;
            while(k % nw == 0){
                sb ++;
                k /= nw;
            }
            sum += sb * (x - (j - 1));
        }
        cout << nw;
        if(sum > 1) cout << "^" << sum;
        if(i != cnt - 1) cout << "*";
    }
}

signed main(){
    fast();
    _
    solve();
    return 0;
}