首页 > 其他分享 >P5524 [Ynoi2012] NOIP2015 充满了希望 题解

P5524 [Ynoi2012] NOIP2015 充满了希望 题解

时间：2024-02-11 09:05:22浏览次数：28  
标签：NOIP2015 return P5524 int 题解 typedef template include define

题目链接：充满了希望

一开始以为是传统老题，结果看到有个交换单修操作，ODT 这题试了下，应该 \(fake\) 了，毕竟有单修，很难保证之前的 \(log\) 级复杂度。有些较为智慧的解法确实不好思考，说个很简单的做法，这里没有问颜色数，而是问的颜色具体情况，那就比之前的很多题简单太多了。颜色的具体情况取决于最后一次颜色覆盖。所以在没有操作一的情况下，我们对于每个三操作很容易找到它是由哪个操作决定的。直接线段树维护每个点处的最近覆盖操作即可。考虑交换操作，很显然，如果两个点交换了，那么这两个点处的最近交换操作也跟着交换就行了，这样最终跑下来的这些点处对应的最近交换处都是正确的。

下一个问题，如何统计一系列查询的和，这个很经典，扫描线一下的二维偏序，具体的我们如果遇到了一个 \(3\) 操作，它由最近覆盖 \(x\) 时决定颜色，且颜色为 \(val\)，那么显然从 \(x\) 覆盖以后的所有时机，都应该加上这个 \(val\) 值。比如我们查询当前的 \([l,r]\) 中 \(l\) 的限制，即为从 \([1,r]\) 更新以后的 \(3\) 操作的最近覆盖里处于覆盖时间在 \(l\) 之后的 \(3\) 操作，如果在 \(l\) 之前，显然根本还没覆盖，根本产生不了影响。这玩意用一个树状数组求扫描线轴上的区间和即可。

第一个问题看到最优解好像有人直接用的 \(dfs+记忆化搜索\) 确认，感觉不算通用，还是基本线段树思路维护即可。ODT 过不了，因为有单修的缘故，给个 \(fake\) 的参照。

ODT 思路参照 
#include <bits/stdc++.h>

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (typeid(x) == typeid(char))return;
    if (x < 0)x = -x, putchar('-');
    if (x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}


template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow)return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3() { one = tow = three = 0; }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y)x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y)x = y;
}

constexpr int N = 1e6 + 10;
int n, m, q;

struct ODT
{
    int l, r;
    mutable int id;

    bool operator<(const ODT& other) const
    {
        return l < other.l;
    }
};

set<ODT> node;
typedef set<ODT>::iterator iter;

inline iter split(const int pos)
{
    auto it = node.lower_bound(ODT(pos, 0, 0));
    if (it != node.end() and it->l == pos)return it;
    --it;
    if (it->r < pos)return node.end();
    auto [l,r,tim] = *it;
    node.erase(it), node.insert(ODT(l, pos - 1, tim));
    return node.insert(ODT(pos, r, tim)).first;
}

inline void assign(const int Id, const int l, const int r)
{
    auto itr = split(r + 1), itl = split(l);
    node.erase(itl, itr), node.insert(ODT(l, r, Id));
}

inline int odtQuery(const int id)
{
    split(id + 1);
    return split(id)->id;
}

struct Query
{
    int op;
    int l, r;
    int val;
} Q[N];

vector<pii> seg[N];
int ansId[N];
ll ans[N], bit[N];

inline void add(int x, const int val)
{
    while (x <= m)bit[x] += val, x += lowBit(x);
}

inline ll query(int x)
{
    ll res = 0;
    while (x)res += bit[x], x -= lowBit(x);
    return res;
}

inline void solve()
{
    read(n, m, q);
    node.insert(ODT(1, m, 0));
    forn(i, 1, m)
    {
        auto& [op,l,r,val] = Q[i];
        read(op);
        if (op == 1)
        {
            read(l, r);
            int idL = odtQuery(l), idR = odtQuery(r);
            swap(idL, idR);
            assign(idL, l, l), assign(idR, r, r);;
        }
        else if (op == 2)
        {
            read(l, r, val);
            assign(i, l, r);
        }
        else
        {
            read(val);
            ansId[i] = odtQuery(val);
        }
    }
    forn(i, 1, q)
    {
        int l, r;
        read(l, r);
        seg[r].emplace_back(l, i);
    }
    forn(r, 1, m)
    {
        if (ansId[r])add(ansId[r], Q[ansId[r]].val);
        for (const auto [l,id] : seg[r])ans[id] = query(r) - query(l - 1);
    }
    forn(i, 1, q)write(endl, ans[i]);
}

signed int main()
{
    // MyFile
    Spider
    //------------------------------------------------------
    // clock_t start = clock();
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test)solve();
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
    // clock_t end = clock();
    // cerr << "time = " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
}#include <bits/stdc++.h>

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (typeid(x) == typeid(char))return;
    if (x < 0)x = -x, putchar('-');
    if (x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}


template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow)return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3() { one = tow = three = 0; }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y)x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y)x = y;
}

constexpr int N = 1e6 + 10;
int n, m, q;

struct ODT
{
    int l, r;
    mutable int id;

    bool operator<(const ODT& other) const
    {
        return l < other.l;
    }
};

set<ODT> node;
typedef set<ODT>::iterator iter;

inline iter split(const int pos)
{
    auto it = node.lower_bound(ODT(pos, 0, 0));
    if (it != node.end() and it->l == pos)return it;
    --it;
    if (it->r < pos)return node.end();
    auto [l,r,tim] = *it;
    node.erase(it), node.insert(ODT(l, pos - 1, tim));
    return node.insert(ODT(pos, r, tim)).first;
}

inline void assign(const int Id, const int l, const int r)
{
    auto itr = split(r + 1), itl = split(l);
    node.erase(itl, itr), node.insert(ODT(l, r, Id));
}

inline int odtQuery(const int id)
{
    split(id + 1);
    return split(id)->id;
}

struct Query
{
    int op;
    int l, r;
    int val;
} Q[N];

vector<pii> seg[N];
int ansId[N];
ll ans[N], bit[N];

inline void add(int x, const int val)
{
    while (x <= m)bit[x] += val, x += lowBit(x);
}

inline ll query(int x)
{
    ll res = 0;
    while (x)res += bit[x], x -= lowBit(x);
    return res;
}

inline void solve()
{
    read(n, m, q);
    node.insert(ODT(1, m, 0));
    forn(i, 1, m)
    {
        auto& [op,l,r,val] = Q[i];
        read(op);
        if (op == 1)
        {
            read(l, r);
            int idL = odtQuery(l), idR = odtQuery(r);
            swap(idL, idR);
            assign(idL, l, l), assign(idR, r, r);;
        }
        else if (op == 2)
        {
            read(l, r, val);
            assign(i, l, r);
        }
        else
        {
            read(val);
            ansId[i] = odtQuery(val);
        }
    }
    forn(i, 1, q)
    {
        int l, r;
        read(l, r);
        seg[r].emplace_back(l, i);
    }
    forn(r, 1, m)
    {
        if (ansId[r])add(ansId[r], Q[ansId[r]].val);
        for (const auto [l,id] : seg[r])ans[id] = query(r) - query(l - 1);
    }
    forn(i, 1, q)write(endl, ans[i]);
}

signed int main()
{
    // MyFile
    Spider
    //------------------------------------------------------
    // clock_t start = clock();
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test)solve();
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
    // clock_t end = clock();
    // cerr << "time = " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
}

正解改用线段树维护实实在在保证复杂度就行了，读入比较大，可以考虑快读读入，实测 \(cin\) 也没啥问题，这里用快读写：

线段树参照代码 
#include <bits/stdc++.h>

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (typeid(x) == typeid(char))return;
    if (x < 0)x = -x, putchar('-');
    if (x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}


template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow)return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3() { one = tow = three = 0; }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y)x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y)x = y;
}

constexpr int N = 1e6 + 10;

struct Node
{
    int id;
    int cov;
} node[N << 2];

#define cov(x) node[x].cov
#define id(x) node[x].id

inline void push_down(const int curr)
{
    if (cov(curr))
    {
        id(ls(curr)) = id(rs(curr)) = cov(ls(curr)) = cov(rs(curr)) = cov(curr);
        cov(curr) = 0;
    }
}

int n, m, q;

inline void cover(const int curr, const int l, const int r, const int val, const int s = 1, const int e = n)
{
    if (l <= s and e <= r)
    {
        id(curr) = cov(curr) = val;
        return;
    }
    const int mid = s + e >> 1;
    push_down(curr);
    if (l <= mid)cover(ls(curr), l, r, val, s, mid);
    if (r > mid)cover(rs(curr), l, r, val, mid + 1, e);
}

inline int query(const int curr, const int pos, const int l = 1, const int r = n)
{
    if (l == r)return id(curr);
    const int mid = l + r >> 1;
    push_down(curr);
    if (pos <= mid)return query(ls(curr), pos, l, mid);
    return query(rs(curr), pos, mid + 1, r);
}

struct Query
{
    int op;
    int l, r;
    int val;
} Q[N];

vector<pii> seg[N]; //扫描线查询
int ansId[N]; //处理出最近覆盖操作编号
ll ans[N], bit[N]; //区间和

inline void add(int x, const int val)
{
    while (x <= m)bit[x] += val, x += lowBit(x);
}

inline ll query(int x)
{
    ll res = 0;
    while (x)res += bit[x], x -= lowBit(x);
    return res;
}

inline void solve()
{
    read(n, m, q);
    forn(i, 1, m)
    {
        auto& [op,l,r,val] = Q[i];
        read(op);
        if (op == 1)
        {
            read(l, r);
            int idL = query(1, l), idR = query(1, r);
            swap(idL, idR);
            cover(1, l, l, idL), cover(1, r, r, idR);;
        }
        else if (op == 2)
        {
            read(l, r, val);
            cover(1, l, r, i);
        }
        else
        {
            read(val);
            ansId[i] = query(1, val);
        }
    }
    forn(i, 1, q)
    {
        int l, r;
        read(l, r);
        seg[r].emplace_back(l, i);
    }
    forn(r, 1, m)
    {
        if (ansId[r])add(ansId[r], Q[ansId[r]].val);
        for (const auto [l,id] : seg[r])ans[id] = query(r) - query(l - 1);
    }
    forn(i, 1, q)write(endl, ans[i]);
}

signed int main()
{
    // MyFile
    Spider
    //------------------------------------------------------
    // clock_t start = clock();
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test)solve();
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
    // clock_t end = clock();
    // cerr << "time = " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
}

\[时间复杂度为:\ O(m\times (\log{n}+\log{m})+q\log{m}) \]

标签：NOIP2015,return,P5524,int,题解,typedef,template,include,define
From： https://www.cnblogs.com/Athanasy/p/18013131

相关文章

  • AtCoder-abc340_f题解
    题意简述给定整数\(x,y\)，询问是否存在整数\(a,b\)，满足：\(-10^{18}\lea,b\le10^{18}\)。由\((0,0),(x,y),(a,b)\)三点构成的三角形面积为\(1\)。如果存在，输出任意一组；否则输出-1。思路先假设\(x,y,a,b\)都是正数。那么图大概是这样：此时红色三角形的面积就......
  • P4183 [USACO18JAN] Cow at Large P 题解
    Description贝茜被农民们逼进了一个偏僻的农场。农场可视为一棵有\(N\)个结点的树，结点分别编号为\(1,2,\ldots,N\)。每个叶子结点都是出入口。开始时，每个出入口都可以放一个农民（也可以不放）。每个时刻，贝茜和农民都可以移动到相邻的一个结点。如果某一时刻农民与贝茜相遇了......
  • [AGC062B] Split and Insert 题解
    题目链接点击打开链接题目解法咋神仙区间\(dp\)题永远想不到区间\(dp\)？？？首先把操作顺序反转那么现在的问题就是：每次可以选出一个子序列放到序列末尾，使序列升序的最小代价这个问题看着也是毫无头绪我尝试去找些规律，当然也没找到考虑精细刻画操作过程：最终的序列是升序的，最......
  • P8670 [蓝桥杯 2018 国 B] 矩阵求和 题解
    题目传送门前置知识欧拉函数解法欧拉反演，简单地推下式子即可。\(\begin{aligned}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd(i,j)^{2}&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{d=1}^{n}d^{2}[\gcd(i,j)=d]\\&=\sum\limits_{i=1}^{n}\sum......
  • Ucup2 -19题解
    Ucup2-19题解：​ 这场的题还是挺有意思的，之前回家后因为过年的准备+美赛摆了挺久没训练，现在开始复健，顺便复活一下死去已久的博客。​ 水题就不赘述了，这次主要说说几道比较难的但思路很有趣的题目，顺序就按难度排吧。G.LCACountingProblem-G-Codeforces题意：给定一颗无向......
  • AtCoder ABC 263 D 题解
    AtCoderABC263D题解前言本蒟蒻的第一篇题解，大佬勿喷QwQ传送门们洛谷传送门AtCoder传送门正文设有\(x\)使得\(x\leqk\)时，令\(f(k)\)为对\(A'\)进行运算后\(A'=(A_1,A_2,\ldots,A_k)\)的最小和。同理，对于\(y\)使得\(y\leqk\)时，令\(g(k)\)为对\(A......
  • 新年欢乐赛题解
    cyh巨佬举办的比赛。比赛页面赛后补题官方题解赛时没时间写题，赛后补一下。T1:默认排名第一，对于每次输入，若输入的成绩更优，则将排名降低。这里更劣的成绩没用，因为默认初始排名第一。T2:At上的一道原题。考虑DP求解。\(dp_{i,0/1}\)分别表示到第\(i\)张翻和不翻的总......
  • P9170 [省选联考 2023] 填数游戏 题解
    Description众所周知，Alice和Bob是一对好朋友。今天，他们约好一起玩游戏。一开始，他们各自有一张空白的纸条。接下来，他们会在纸条上依次写\(n\)个\([1,m]\)范围内的正整数。等Alice写完，Bob在看到Alice写的纸条之后开始写他的纸条。Alice需要保证她写下的第\(i\)个......
  • P9478 [NOI2023] 方格染色题解
    题解对于行操作，列操作和对角线操作，实际上仅仅只是在对若干个矩形求面积并而已，这是裸的扫描线题，套用模板即可，此时注意到对角线操作实际上是\(O(n)\)量级的矩阵面积并，因此复杂度是\(O(n\logq+q\logq)\)的量级，只能获得95pts。显然，面积并具有交换性，我们先做\(O(q\logq)\)......
  • uoj839 龙门题字 题解
    题目链接点击打开链接题目解法呜呜呜，我考场上只会\(60\)，不会优化，没救了要求字典序最大，不难想到一位一位钦定，那么我们现在的问题是判断\(ans_1,...,ans_i\)是否合法，记\(ok_{i,j}\)表示第\(i\)个修改在第\(j\)位是否可行（即\(x_{i,j}\geans_j\)），同时记\(cnt_i\)为第......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99