Skip to content

2020 牛客国庆集训派对 Day5

Contents

Contest Info

Practice Link

Solved A B C D E F G H I J K
6/11 - O O O Ø - - O - - O
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

Problem A. Kingdom Reunion

Upsolved By -.

题意

思路

Problem B. Hyperdrome

Solved By Dup4. 01:51(+1)

题意

给出一个字符串，找出有多少个子串满足重新排列后是一个回文串。

思路

题意的要求就是找有多少个子串，使得最多只有一种字符出现的次数为奇数。

我们考虑维护一个前缀字符出现信息 f_i，0 表示出现偶数次，1 表示出现奇数次，那么任意一个子串 [l_i, r_i]，只要满足 f_r \oplus f_{l - 1} 中最多只有一位为 1 就可以了。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 3e5 + 10;
constexpr int M = 52;
int n;
char s[N];
ll f[N];

unordered_map<ll, int> mp;

void run() {
    rd(n);
    cin >> (s + 1);
    memset(f, 0, sizeof f);
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1];
        int c = s[i];
        if (c >= 'a' && c <= 'z')
            c -= 'a';
        else
            c = c - 'A' + 26;
        f[i] = f[i] ^ (1ll << c);
    }
    mp.clear();
    mp[0] = 1;
    ll res = 0;
    for (int i = 1; i <= n; ++i) {
        res += mp[f[i]];
        for (int j = 0; j < 52; ++j) {
            ll x = f[i] ^ (1ll << j);
            if (mp.count(x))
                res += mp[x];
        }
        ++mp[f[i]];
    }
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem C. Great Deceiver

Solved By Dup4. 02:21(+)

题意

给出一个 n 和 k，要求十进制中小于等于 n 的数中，在 +k 进制和 -k 进制下相等的数有多少个。

思路

在 +k 进制下 和 -k 进制下相等，即表明奇数次幂上的值全都为 0 即可。 那么我们去掉奇数次幂，贪心出最大值，即为最多的数。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
ll n;
int K;

ll getMax(ll n, int K) {
    ll base = 1;
    int cnt = 0;
    while (base * K <= n && base * K * K <= n) {
        base *= K;
        base *= K;
        ++cnt;
    }
    //	dbg(base);
    // vector <int> vec(cnt + 1);
    ll act = 0;
    ll res = 0;
    for (int i = cnt; i >= 0; --i) {
        ll now = (n - act) / base;
        now = min(now, 1ll * K - 1);
        act += now * base;
        //	dbg(i, now, base);
        base /= K;
        base /= K;
        res = res * K + now;
    }
    return res + 1;
}

void run() {
    rd(n, K);
    ll Max = getMax(n, K);
    pt(Max);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem D. Exact Measurement

Solved By Dup4 & groggy_. 04:35(+1)

题意

给出 n 个箱子，每个箱子有 10^{k_i} 的砝码有 q_i 个，现在要取最少的箱子，使得有一种方案取出这些箱子中的砝码使得重量和等于 x。 即箱子中的砝码可以不全取出来。

思路

低位的砝码不能满足更低位的需求，但是能够满足高位的需求。 那么我们从地位到高位贪心，每次遍历到一位，都会解锁若干箱子，然后丢进最大堆，每次取盒子砝码总重量大的即可。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
using pLI = pair<ll, int>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int n;
ll x, ten[20];

void run() {
    rd(x, n);
    vector<pLI> vec[20];
    int k;
    ll q;
    for (int i = 1; i <= n; ++i) {
        rd(k, q);
        vec[k].push_back(pLI(q * ten[k], i));
    }
    priority_queue<pLI> pq;
    ll sum = 0;
    ll need = 0;
    ll base = 1;
    vector<int> res;
    for (int i = 0; i <= 18; ++i) {
        for (auto &it : vec[i]) {
            pq.push(it);
        }
        need += base * (x % 10);
        base *= 10;
        x /= 10;
        while (sum < need) {
            if (pq.empty())
                return pt(-1);
            sum += pq.top().fi;
            res.push_back(pq.top().se);
            pq.pop();
        }
    }
    sort(all(res));
    pt(SZ(res));
    pt(res);
}

int main() {
    ten[0] = 1;
    for (int i = 1; i <= 18; ++i) ten[i] = ten[i - 1] * 10;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem E. Caravan Robbers

Upsolved By Dup4.

题意

给出 n 个线段 [a_i, b_i]，满足 i \leq j, 有 a_i \leq a_j, b_i \leq b_j, 现在要找出最长的长度 len，满足每条线段都能取出那么长的子段，并且 n 条线段不相交。

思路

  • 如果有两个重叠的线段，那么可以取平均值。但是要跟各自的本身的线段长度取 Min。
  • 那么对于 x 个重叠的线段，答案应该是任意连续个线段的平均值的最小值。
  • 但是这么做复杂度是 \mathcal{O}(n^2)。
  • 那么我们考虑二分，然后贪心判断。
  • 但是答案要分数，我们考虑小数如何化分数。
    • 考虑分数 \displaystyle \frac{p}{q} = d, 有 \displaystyle p = qd。
    • 所以我们枚举分母 q，此处根据前面的分析，显然当所有线段挤在一起的时候，分数最大为 n。
    • 通过控制误差去得到更精确的值。
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = long double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
constexpr db eps = 1e-11;
int n;
pII a[N];

int sgn(db x) {
    if (fabs(x) < eps)
        return 0;
    return x < 0 ? -1 : 1;
}

bool ok(db x) {
    db st = 0;
    for (int i = 1; i <= n; ++i) {
        st = max(st, (db)1.0 * a[i].fi);
        db ed = st + x;
        if (sgn(ed - a[i].se) > 0)
            return false;
        st = ed;
    }
    return true;
}

void run() {
    rd(n);
    for (int i = 1; i <= n; ++i) {
        rd(a[i].fi, a[i].se);
    }
    sort(a + 1, a + 1 + n, [&](pII a, pII b) {
        if (a.fi == b.fi)
            return a.se < b.se;
        return a.fi < b.fi;
    });
    db l = 0, r = a[n].se;
    while (r - l > eps) {
        db mid = (l + r) / 2;
        if (ok(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    db Min = 0x3f3f3f3f;
    int p, q;
    for (int i = 1; i <= N; ++i) {
        for (auto &j : {floor(l * i), ceil(l * i)}) {
            if (fabs(j * 1.0 / i - l) < Min) {
                p = j;
                q = i;
                Min = fabs(j * 1.0 / i - l);
            }
        }
    }
    cout << p << "/" << q << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem F. Kabaleo Lite

Upsolved By -.

题意

思路

Problem G. Hack Protection

Upsolved By -.

题意

思路

Problem H. Fraud Busters

Solved By groggy_. 00:34(+)

题意

配出字符串，求有多少个匹配

思路

暴力匹配

Code 
#include <iostream>
#include <vector>

#define maxn 1005
using namespace std;

string s, t;
vector<string> v;

void solve(string a, string b) {
    int flag = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i] && a[i] != '*') {
            flag = 1;
            break;
        }
    }
    if (!flag)
        v.push_back(b);
}

int main() {
    cin >> s;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t;
        solve(s, t);
    }

    cout << v.size() << endl;
    for (int i = 0; i < v.size(); i++) cout << v[i] << endl;
}

Problem I. Cactus Automorphisms

Upsolved By -.

题意

思路

Problem J. Bonus Cards

Upsolved By -.

题意

思路

Problem K. Knockout Racing

Solved By groggy_. 00:25(+1)

题意

每辆车在 a 和 b 之间来回移动。 求 t 时刻，x 和 y 区间内有多少辆车。

思路

计算查询时刻的每个车位置

Code 
#include <iostream>

#define maxn 1005
using namespace std;

int n, m;
int a[maxn], b[maxn];

int calc(int index, int t) {
    t %= 2 * (b[index] - a[index]);

    if (t <= b[index] - a[index])
        return a[index] + t;
    else
        return 2 * b[index] - a[index] - t;
}

void solve(int x, int y, int t) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int dis = calc(i, t);
        //		cout<<dis<<endl;
        if (dis >= x && dis <= y)
            cnt++;
    }
    printf("%d\n", cnt);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a[i], &b[i]);
    }

    int x, y, t;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &x, &y, &t);
        solve(x, y, t);
    }
}
Last update: March 24, 2022
Created: March 23, 2022
Back to top