首页 > 其他分享 >ZZJC新生组队赛第十一场题解

ZZJC新生组队赛第十一场题解

时间：2024-11-25 21:11:11浏览次数：2  
标签：ZZJC int 题解 ll cin long 组队 tt mod

A 苏醒，浮出梦乡

定义 \(s_n^m\) 为 \(\{a_n\}\) 的 \(m\) 阶前缀和数组第 \(n\) 位上的值

显然 \(s_n^m = s_{n - 1}^m + s_n^{m - 1}\)

自然的，我们可以朴素的进行DP算出 \(s_n^m\) 的最大可能值

然而计算一下复杂度却发现是 \(n^2\)，显然会TLE,不优化的话还会MLE

但是根据输入，易得需要预处理并且 \(O(1)\) 查询的

根据上面的状态转移方程，不难看出，\(s_n^m\) 其实就是 组合数，那么我们预处理阶乘和阶乘的逆元之后，根据组合数公式就可以 \(O(1)\) 算出 \(s_n^m\) 的值了 (预处理阶乘的复杂度是 \(O(n)\))

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 1e9 + 7;
// constexpr int inf = 0x3f3f3f3f;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
constexpr ll maxn = 1000000;
ll fact[maxn + 2];
ll inv[maxn + 2];
auto power(ll a , ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void initfact() {
    fact[0] = 1;
    for (ll i = 1; i <= maxn; ++ i) {
        fact[i] = fact[i - 1] * i % mod;
    }
    inv[maxn] = power(fact[maxn], mod - 2);
    for (ll i = maxn - 1; i >= 1; -- i) {
        inv[i] = inv[i + 1] * (i + 1ll) % mod;
    }
}
ll C(int n, int m) {
    if (m > n) {
        return 0;
    } else if (m == 0) {
        return 1;
    } else {
        return fact[n] * inv[m] % mod * inv[n - m] % mod;
    }
}
ll f(int x, int y) {
    return C(x + y - 1, y - 1);
}
int main() { 
    cin.tie(nullptr)->sync_with_stdio(false);

    initfact();
        
    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n, m, d = 0;
        cin >> n >> m;
        cout << f(m, n) << "\n";
    }
}




B 落雪，浸黑国土

不妨设整个数组的和为 \(s\)

注意到第 \(i\) 种操作可以转化为，对 \(s\) 加或者减 \(i * b_i\)

根据裴蜀定理:

\[\sum\limits_{i = 1}^{n} a_{i} x_{i} = gcd( \{ x_{i} \vert i \in [1 , n] \} ) (a_{i} \in Z) \]

易得

\( ans = \begin{cases} 1, ~~~ q ~ \% ~ gcd( \{ i * b_{i} \vert i \in [1 , n] \} ) == 0 \\ 0, ~~~ q ~ \% ~ gcd( \{ i * b_{i} \vert i \in [1 , n] \} ) != 0 \\ \end{cases} \)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<ll> a(n + 1);
        for (ll i = 1; i <= n; ++ i) {
            ll x; 
            cin >> x;
            a[i] = x * i;
        }
        ll g = a[1];
        for (int i = 2; i <= n; ++ i) {
            g = gcd(g, a[i]);
        }
        ll q;
        cin >> q;
        if (g == 0) {
            if (q == 0) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        } else {
            if (q % g == 0) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        }
    }
}




C 相逢，总是离别

首先，进行分讨

  1. 当图本来不是传递的
    我们只需要计算出当前所有的连通块变成传递的需要多少条边，再减去 \(m\) 即可
  2. 当图本来是传递的
    我们只需要把最小的两个联通块合并成一个，计算需要添加的边即可
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
class DSU {
public:
    int n;
    vector<int> dsu, dsus;
    DSU() {}
    DSU(int n) { init(n); }
    void init(int n) {
        this -> n = n;
        dsu.resize(n + 1);
        dsus.resize(n + 1, 1);
        iota(dsu.begin(), dsu.end(), 0);
    }
    int find(int a) {
        if (a == dsu[a]) {
            return a;
        } else {
            dsu[a] = find(dsu[a]);
            return dsu[a];
        }
    }
    void merge(int a, int b) {
        int x = find(a);
        int y = find(b);
        if (x != y) {
            if (dsus[x] < dsus[y]) {
                swap(x, y);
            }
            dsu[y] = x;
            dsus[x] += dsus[y];
        }
    }
    void reboot() {
        for (int i = 1; i <= n; ++ i) {
            int fa = find(dsu[i]);
            dsu[i] = fa;
            dsus[i] = dsus[fa];
        }
    }
};
ll f(ll x) { return x * (x - 1ll) / 2ll; }
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    DSU a(n);
    a.init(n);
    for (int i = 1; i <= m; ++ i) {
        int u, v;
        cin >> u >> v;
        a.merge(u, v);
    }
    a.reboot();
    priority_queue<ll, vector<ll>, greater<ll>> q; // 升序
    set<int> st;
    for (int i = 1; i <= n; ++ i) { 
        int fa = a.dsu[i];
        if (!st.count(fa)) {
            st.insert(fa);
            q.push(a.dsus[fa]);
        }
    }
    ll ans = -m, s = 0, d = 0;
    int len = q.size();
    for (int i = 1; i <= len; ++ i) {
        ll x = q.top();
        q.pop();
        ans += f(x);
        if (i <= 2) {
            s += x;
            d -= f(x);
        }
    }
    if (ans == 0) ans += f(s) + d;
    cout << ans << "\n";
}




D 人心，向背无常

这是一题有向图博弈

根据题目给的条件，可以建一颗树

显然，树的叶子结点的 \(SG\) 值为 0 (我们定义0为必胜态)

由于：

\[SG(x) = mex(\{SG(y) \vert y \in adj[x] \}) \]

我们深度优先搜索时求一下每个节点的 \(SG\) 值，最后判断 \((1, 1)\) 的 \(SG\) 值是否是 \(0\) 即可

根据题目的状态转移，不难看出满足 无后效性，即可以倒着直接根据关系进行DP

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int mex(set<int> st) {
    int res = 0;
    for (auto x : st) {
        if (x >= 0) {
            if (res == x) {
                res ++;
            } else {
                return res;
            }
        }
    }
    return res;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> a(n + 1, vector<int>(m + 1, 7));
        vector<vector<int>> sg(n + 2, vector<int>(m + 2, -1));

        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= m; ++ j) {
                cin >> a[i][j];
            }
        }

        for (int i = n; i >= 1; -- i) {
            for (int j = m; j >= 1; -- j) {
                set<int> st;
                if ((a[i][j] >> 0) & 1) st.insert(sg[i + 1][j]);
                if ((a[i][j] >> 1) & 1) st.insert(sg[i][j + 1]);
                if ((a[i][j] >> 2) & 1) st.insert(sg[i + 1][j + 1]);
                sg[i][j] = mex(st);
            }
        }

        if (sg[1][1] == 0) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

https://www.acwing.com/blog/content/13279/





E 厄运，等候已久

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
constexpr ll maxn = 1000000;
ll power(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll fact[maxn + 2];
ll inv[maxn + 2];
void initfact() {
    fact[0] = 1;
    for (ll i = 1; i <= maxn; ++ i) {
        fact[i] = fact[i - 1] * i % mod;
    }
    inv[maxn] = power(fact[maxn], mod - 2);
    for (ll i = maxn - 1; i >= 1; -- i) {
        inv[i] = inv[i + 1] * (i + 1ll) % mod;
    }
}
ll C(int n, int m) {
    if (m > n) {
        return 0;
    } else if (m == 0) {
        return 1;
    } else {
        return fact[n] * inv[m] % mod * inv[n - m] % mod;
    }
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    initfact();

    int tt = 1;
    cin >> tt;
    while (tt--) {
        ll n, m;
        cin >> n >> m;
        ll last = n - m * 5;
        ll t = last / 2ll * 5ll;
        if (t >= m) {
            ll ans = 0;
            ll P = 5ll * power(100, mod - 2) % mod;
            ll Q = 95ll * power(100, mod - 2) % mod;
            ll p = 1, q = power(Q, t);
            for (int k = 0; k < m; ++ k) {
                ans += C(t, k) * p * q;
                ans %= mod;
                p *= P;
                q *= Q;
            }
            ans = mod + 1 - ans;
            ans %= mod;
            cout << ans << "\n";
        } else {
            cout << 0 << "\n";
        }
    }
}




F 战场，蔓延不止

对于每一个曼哈顿圆，只要起点到终点的欧几里得距离小于等于，圆心到终点的曼哈顿距离，就能不被追上

自证不难。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const ll pi = acos(-1);
const ll E = exp(1);
constexpr ll mod = 1e9 + 7;
// constexpr int inf = 0x3f3f3f3f;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
class Point {
public:
    ll x = 0, y = 0;
    Point () {}
    Point (ll x, ll y) : x(x), y(y) {}
    Point operator-(const Point &P) const { return Point(x - P.x, y - P.y); }
    ll operator&(const Point &P) const { return x * P.x + y * P.y; } // 点积 |A||B|cosθ
    friend istream &operator>>(istream &is, Point &rhs) { return is >> rhs.x >> rhs.y; }
    friend ostream &operator<<(ostream &os, const Point &rhs) { return os << '(' << rhs.x << ',' << rhs.y << ')'; }
};
const Point O = {0, 0}; // 原点
ll Len2(const Point &A) { return A & A; } // 向量A长度的平方 
ll Distance2(const Point &A, const Point &B) { return Len2(A - B); } // 两点间距离 
ll ManhattanDistance2(const Point &A, const Point &B) { return (abs(A.x - B.x) + abs(A.y - B.y)) * (abs(A.x - B.x) + abs(A.y - B.y)); } // 两点间曼哈顿距离 
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        bool flag = 1;
        int n;
        cin >> n;
        vector<Point> pl(n + 1);
        for (int i = 1; i <= n; ++i) {
            cin >> pl[i];
        }
        Point ps, pt;
        cin >> ps >> pt;
        ll d2 = Distance2(pt, ps);
        for (int i = 1; i <= n; ++i) {
            ll cur2 = ManhattanDistance2(pt, pl[i]);
            if (cur2 <= d2) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}




G 意志，片缕幻影

根据 \(y = lowbit(x) = ((-x) \& x)\)

可知，题目就是求 \(lowbit(x)\)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        string s, ans = "";
        cin >> s;
        int len = s.size();
        for (int i = len - 1; i >= 0; -- i) {
            ans += s[i];
            if (s[i] == '1') break;
        }
        reverse(ans.begin(), ans.end());
        cout << ans << "\n";
    }
}

/**
 *    title:  b2.cpp
 *    author:  Proaes Meluam
 *    created:  2024-11-19 19:46:54
**/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h" 
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double pi = acos(-1);
const double E = exp(1);
constexpr ll mod = 1e9 + 7;
// constexpr int inf = 0x3f3f3f3f;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        string s;
        cin >> s;
        int len = s.size();
        vector<int> a(len);
        for (int i = 0; i < len; ++ i) {
            a[i] = s[i] - '0';
        }
        reverse(a.begin(), a.end());

        vector<int> b = a;
        for (int i = 0; i < len; ++ i) {
            a[i] ^= 1;
        }
        a[0]++;
        int carry = 0;
        for (int i = 0; i < len; ++ i) {
            carry += a[i];
            a[i] = carry % 2;
            carry /= 2;
        }
        vector<int> ans(len);
        for (int i = 0; i < len; ++ i) {
            ans[i] = a[i] & b[i];
        }
        reverse(ans.begin(), ans.end());
        int be = 0;
        for (int i = 0; i < len; ++ i) {
            if (ans[i] == 1) be = i;
        }
        string sans = "";
        for (int i = be; i < len; ++ i) {
            char c = ans[i] + '0';
            sans += c;
        }
        cout << sans << "\n";
    }
}




H 失语，产自多言

#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h" 
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<ll> v(n + 1);
        vector<ll> dp(n + 1, inf);
        for (int i = 1; i <= n; ++ i) cin >> v[i];
        if (n == 1) {
            cout << v[n] << "\n";
        } else {
            vector<int> f(n + 1); // f[i] 存 i 的最大因子
            for (int k = 1; k <= n; ++ k) {
                for (int i = k + k; i <= n; i += k) {
                    f[i] = max(f[i], k);
                }
            }
            vector<vector<ll>> adj(n + 1, vector<ll>());
            for (int i = 2; i <= n; ++ i) {
                adj[f[i]].emplace_back(i);
            }
            for (int i = 1; i <= n; ++ i) {
                // 预处理，把叶子结点存进dp数组，显然叶子节点只能减，存进后就是当前节点的最大值
                if ((int)adj[i].size() == 0) { 
                    dp[i] = v[i];
                }
            }
            auto transition = [&](int child, int father) {
                if (dp[child] > v[father]) {
                    dp[father] = min(dp[father], (v[father] + dp[child]) / 2ll);
                } else {
                    dp[father] = min(dp[father], dp[child]);
                }
            };
            auto dfs = [&](auto self , int cur , int father) -> void {
                for (auto child : adj[cur]) {
                    if (child == father) continue; // 防止往回遍历
                    self(self, child, cur);
                    if (cur != 1) { // 特判根节点，因为根节点只能无需保证小于等于他的子树
                        transition(child, cur);
                    }
                }
            };
            dfs(dfs, 1, 0);
            // 特判根节点，此时特别的，dp[1]表示的不是节点1的最大值，而是节点1的最大增加值，所以最后要加上v[1]
            for (auto child : adj[1]) {
                dp[1] = min(dp[1], dp[child]);
            }
            // debug(dp);
            // 当dp[1]没有增加时，要把dp[1]置 0
            if (dp[1] == inf) dp[1] = 0;
            // 由于dp[1]表示的不是节点1的最大值，而是节点1的最大增加值，所以最后要加上w[1]
            ll ans = dp[1] + v[1];
            cout << ans << "\n";
        }
        
    }
}




标签：ZZJC,int,题解,ll,cin,long,组队,tt,mod
From： https://www.cnblogs.com/Proaes/p/18568751

相关文章

  • ZZJC新生训练赛第十八场题解
    链接：https://www.nowcoder.com/acm/contest/97429密码：gar615gdsr难度分类题目分值决定A-解题思路除一下比较分数大小即可A-代码实现a,b=map(int,input().split())x,y=map(int,input().split())ifa/b>x/y:print(">")elifa/b==x/y:prin......
  • 【题解】洛谷P5911 :[POI2004] PRZ
    状压dp，先预处理出来所以状态的重量和时间，然后枚举集合，然后枚举子集，子集重量合法的话就可以转移，因为这题是多个集合组成最后的集合。枚举子集。https://oi-wiki.org/math/binary-set/#__tabbed_1_1#include<bits/stdc++.h>#defineintlonglong#definelsp<<1#definersp......
  • easyui combobox 只能选择第一个问题解决
    easyuicombobox只能选择第一个问题解决问题现象在拆分开票的时候，弹出框上面有一个下拉框用于选择需要新增的明细行，但是每次只能选择到第一个选择第二条数据的时候默认选择到第一个了代码如下/*新增发票编辑窗口*/functionaddTicketDialog(){orderIte......
  • CF2023C C+K+S 题解
    前置知识：哈希/KMP题目链接：洛谷、Codeforces。有点牛的一道题。首先，既然两张图所有的环长都是\(k\)的倍数，那么考虑做一个比较厉害的处理：对图染色。令\(u\)的颜色为\(c_u\)，如果有边\(u\rightarrowv\)，那么\(c_v=(c_u+1)\modk\)。这样最多有\(k\)种颜色，范围是\(......
  • AtCoder ABC321F - #(subset sum = K) with Add and Erase 题解 可撤销背包
    题目链接：https://atcoder.jp/contests/abc321/tasks/abc321_f题目大意：给定大小为\(k\)的背包和\(q\)次操作，支持两种操作：插入一个大小为\(x\)的元素；删除一个大小为\(x\)的元素。每次操作后，求装满背包方案数。解题思路：可撤销背包。插入\(x\)时，fori=K->x......
  • 题解 - Game on Sum (Easy Version)
    题目，还是不挂洛谷。Alice镇楼题目大意Alice和Bob又在玩游戏。该种游戏共分为\(n\)轮，每轮中，先有一个数\(x=0\)，Alice将选择\(t\isin[0,t_{max}]\)，而B将会选择将\(x\)增加或减少\(t\)。在全部\(n\)轮中，B应至少有\(m\)次选择减少操作。Alice希望结......
  • 【题解】洛谷P11311、P2943： 漫长的小纸带、Cleaning Up G
    赛时不会去想dp，感觉没法转移，然后去写了贪心，然后直接假掉唐完了。为什么贪心不能做，因为多个数的话还是可能被减，\(3\)个数长度为\(11\)就可以变成\(9\)，非常划算，好像很显然，但是为什么我赛时写了只会有长度\(2\)的区间唐完了。考虑dp，设\(f_i\)表示\(1-i\)的最小代价，枚举......
  • CF2038A - Bonus Project 题解
    题目传送门https://codeforces.com/contest/2038/problem/A先大致捋一下题目的含义一共有n个工程师，每个工程师完成相应的工作都有一定的奖金a，但同时也会消耗成本b，目前一共有k个工作需要做这些工程师对他们的同事很友好，他们能接受自己的总收益为0来增长经验，但不能接受自己为负......
  • 题解：[P11311 漫长的小纸带]
    P11311漫长的小纸带题意：有一个长度\(n\)的序列\(a\)，将\(a\)分成若干段，使得所有段价值和最小，定义价值为一段内元素数量的平方。思路：显然能用动态规划来计算答案，设\(f[i]\)表示到第\(i\)个位置所获得的最小价值，考虑怎么转移。最直接的就是从\(1\)到\(i-1\)枚举断......
  • 读数据质量管理：数据可靠性与数据质量问题解决之道10数据平台
    1.      数据平台1.1.        让你能够从摄取数据到分析数据的整个过程中全面管理数据的技术组合1.2.        数据平台的要求随着业务的变化而变化1.3.        数据栈分为6层1.3.1.          数据摄取1.3.1.1.     ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99