2024 暑假友谊赛-热身2

标签：BA int XA 热身 2024 solve ans 友谊赛 BX

CodeForces 1265E

思路：期望dp，f[i]表示走到i的期望天数，有f[i] = p[i]/100 * (f[i - 1] + 1) + (100 - p[i]) / 100 * (f[i - 1] + 1 + f[i])，

得到f[i] = 100 / p[i] * (f[i - 1] + 1)

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define PII pair<int, int>

const int N = 1e5 + 5, mod = 998244353;

int ksm(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void solve() {
    int n;
    cin >> n;
    vector<int> f(n + 1), p(n + 1);
    for (int i = 1; i <= n; ++i) cin >> p[i];
    for (int i = 1; i <= n; ++i) {
        f[i] = (f[i - 1] + 1) * 100 % mod * ksm(p[i], mod - 2) % mod;
    }
    cout << f[n];
}

signed main() {
    ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

CodeForces 911F

思路：贪心，首先确定树的直径uv，先对非直径路径的点进行操作，得到的贡献是该点到u或到v的最大距离，最后只剩下直径，贡献就是直径长度*（直径长度-1）/2。还有一点是要先处理叶子节点，按dfs输出即可

CodeForces 1870E

AtCoder tenka1_2017_c

思路：暴力

首先推下公式有abcn = 4 * ( bc + ac + ab)

abc的范围都是3500，可以枚举ab的值，再判断c是否合法


void solve() {
    int n;
    cin >> n;
    for (int a = 1; a <= 3500; ++a) {
        for (int b = 1; b <= 3500; ++b) {
            int x = a * b * n, y = 4 * a * b - b * n - a * n;
            if (y <= 0) continue;
            if (x % y == 0) {
                cout << a << ' ' << b << ' ' << x / y ;
                int c = x / y;
//                if (4 * a * b * c == n * (b * c + a * c + a * b)) cout << "YES";


                return ;
            }
        }
    }
}

AtCoder diverta2019_b

思路：暴力

已知n，枚举r、g，判断b是否合法

void solve() {
    int n, a, b, c;
    cin >> a >> b >> c >> n;
    int ans = 0;
    for (int i = 0; i <= 3000; ++i) {
        for (int j = 0; j <= 3000; ++j) {
            int s = i * a + j * b;
            if (s > n) continue;
            s = n - s;
            if (s % c == 0) ans ++;
        }
    }
    cout << ans;
}

AtCoder diverta2019_c

思路：首先把所有串内的AB统计了，然后只统计首尾为XA、BA、BX的串的个数（X为任意字符）

现在问题就在于怎么分配顺序

XA+BA=XA

BA+BX=BX

XA+BX=XX

BA+BA=BA

可以看到BA和任何串匹配还能产生有效的串

考虑以得到贡献最多的方式，如果XA+BA+BA+...+BA+BX，相比于XA+BX和BA+BA+...+BA分别带来的贡献是更优的，将BA放进XA和BX中间能保证BA的贡献最大化

剩下就分类讨论所有情况

当XA和BX都存在时，首先保证每对XA和BX中间有一个BA，若还剩下BA，则全部打包给一对XA和BX，即min（XA，BX）+ BA

当XA或BX只存在一方时，就用XA+BA=XA，BA+BX=BX的方式，保证每个XA或BX都匹配一个BA，若还剩下BA，则全部打包给一个XA或BX，即BA

当XA和BX都不存在时，就用BA+BA+...+BA的方式，即BA - 1



void solve() {
    int n;
    cin >> n;
    int bx, ba, xa;
    bx = ba = xa = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size() - 1; ++j) {
            if (s[j] == 'A' && s[j + 1] == 'B') ans ++;
        }
        if (s[0] == 'B' && s.back() == 'A') ba ++;
        else if (s[0] == 'B') bx ++;
        else if (s.back() == 'A') xa++;
    }
    if (xa > 0 && bx > 0) {
        ans += ba + 1 + min(xa, bx) - 1;
    } else if (xa > 0) {
        ans += ba;
    } else if (bx > 0) {
        ans += ba;
    } else if (ba > 1) {
        ans += ba - 1;
    }
    cout << ans;
}

AtCoder diverta2019_d

思路：令n = am + b，根据式子其实就是求满足a=b时的m，再进一步将a=b带入得到n = a * (m + 1)，相当于就是求n的因子，暴力的统计所有满足式子的因子即可

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 2e5 + 5, mod = 998244353;

int ksm(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int x = n / i;
//            cout << i << ' ' << x << '\n';
            if (i - 1 > 0) {
                int m = i - 1;
                if ((n / m == (n % m))) {
//                    cout << "NO:" << i << '\n';
                    ans += i - 1;
                }
            }
            if (x != i && x - 1 > 0) {
                int m = x - 1;
                if ((n / m == (n % m))) {
//                    cout << "NO:" << i << '\n';
                    ans += x - 1;
                }
            }
        }
    }
    if (n - 1 > 1) {
        int m = n - 1;
        if ((n / m == n % m)) {
//                    cout << "NO:" << i << '\n';
            ans += n - 1;
        }
    }
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

AtCoder abl_d

思路：首先暴力的想n²的dp是可以解决这道题的，f[i]表示前i个数中的最大序列个数，有f[i] = f[j] + 1，其中j<i，且abs(a[i] - b[j]) <= k

考虑怎么优化，如何更快的找到最大的f[j]，且满足abs(a[i] - a[j]) <= k，这里可以用线段树维护区间最大值，将a[i]的值看作是下标，f[i]当作值，每次查询[a[i] - k, a[i] + k]区间内的最大值，即为要找到的f[j]，找到后再给a[i]这个位置加上值f[i] + 1

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define PII pair<int, int>

const int N = 1e5 + 5, mod = 998244353;


const int MXN = 3e5+5;
int a[MXN];
int t[4*MXN],lazy[4*MXN]; //t是树，lazy是懒标记
int n;

int lc(int x){return x<<1;}  //左儿子
int rc(int x){return x<<1|1;}//右儿子

void up(int p)  //向上更新树
{
    t[p]=max(t[lc(p)],t[rc(p)]);
}
void build(int p,int l,int r)   //建树
{
    if(l==r){
        t[p]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(lc(p),l,mid);
    build(rc(p),mid+1,r);
    up(p);
}
void update(int xl,int xr,int x,int p,int l,int r)
{//xl,xr为要修改的区间
    //x为要修改成的值
    //p为当前节点编号
    //l,r为当前区间
    if(xl<=l && xr>=r){
        t[p]=x;
        return ;
    }
    int mid=(l+r)>>1;
    if(xl<=mid) update(xl,xr,x,lc(p),l,mid);
    if(xr>mid) update(xl,xr,x,rc(p),mid+1,r);
    up(p);
}
int query(int xl,int xr,int l,int r,int p)
{//xl,xr为要修改的区间
    //l,r为当前区间
    //p为当前节点编号
    if(xl<=l && r<=xr) return t[p];
    int mid=(l+r)>>1;
    int ans=0;
    if(xl<=mid) ans=max(query(xl,xr,l,mid,lc(p)),ans);
    if(xr>mid) ans=max(query(xl,xr,mid+1,r,rc(p)),ans);
    return ans;
}
void solve() {
    int k, m;
    cin >> m >> k;
    n = 3e5 + 1;
    build(1, 1, n);
    vector<int> ve(m + 1);
    for (int i = 1; i <= m; ++i) cin >> ve[i];
    for (int i = 1; i <= m; ++i) {
        int l = max(0ll, ve[i] - k + 1), r = min(ve[i] + k + 1, n);
        int s = query(l, r, 1, n, 1);
        update(ve[i] + 1, ve[i] + 1, s + 1,  1, 1, n);
    }
    cout << query(1, n, 1, n, 1);
}

signed main() {
    ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

标签：BA,int,XA,热身,2024,solve,ans,友谊赛,BX
From： https://www.cnblogs.com/bible-/p/18299577