TJUACM 2024暑期集训（一）7.8-7.14

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
int a[2001][2001], h[2001][2001], l[2001], r[2001];
int count(int i)
{
    stack<int> s;
    int ans = 0;
    for (int j = 1; j <= m; j++)
    {
        while (!s.empty() && h[i][j] < h[i][s.top()])
            r[s.top()] = j, s.pop();
        s.push(j);
    }
    while (!s.empty())
        r[s.top()] = m + 1, s.pop();
    for (int j = m; j >= 1; j--)
    {
        while (!s.empty() && h[i][j] < h[i][s.top()])
            l[s.top()] = j, s.pop();
        s.push(j);
    }
    while (!s.empty())
        l[s.top()] = 0, s.pop();
    for (int j = 1; j <= m; j++)
    {
        ans = max(ans, (r[j] - l[j] - 1) * h[i][j]);
    }
    return ans;
}
int main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
    {

        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                cin >> a[i][j];
                if (a[i][j] >= a[i - 1][j])
                    h[i][j] = h[i - 1][j] + 1;
                else
                    h[i][j] = 1;
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            ans = max(ans, count(i));
        }
        cout << ans << endl;
    }
}

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;
const int M = 5e5 + 10;
int fa[N];
int n, m, k, t;
struct edge
{
    int u, v, w;
    bool operator<(const edge &p) const
    {
        return w < p.w;
    }
} a[M];
int find(int x)
{
    if (fa[x] != x)
    {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}
void solve()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
        cin >> a[i].u >> a[i].v >> a[i].w;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    sort(a + 1, a + m + 1);
    int sum = n, d = 0;
    for (int i = 1; i <= m; i++)
    {
        if (sum < k)
            break;
        if (sum == k && a[i].w != a[i - 1].w)
            break;
        if (find(a[i].u) == find(a[i].v))
            continue;
        fa[find(a[i].u)] = fa[find(a[i].v)];
        d = a[i].w;
        sum--;
    }

    if (sum == k)
        cout << d << endl;
    else
        cout << -1 << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--)
    {
        solve();
    }
}

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
int n, t, sum, x;
int pri[N], f;
bool vis[N];
vector<int> q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cin >> x;
        q.push_back(x);
        n = max(x, n);
    }
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
            vis[i] = 1, pri[++f] = i;
        for (int j = 1; j <= f && i * pri[j] <= n; j++)
        {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0)
                break;
        }
    } // pri存了1-n的质数
    for (auto i : q)
    {
        if (i == 2)
        {
            cout << 0 << endl;
            continue;
        }
        sum = ((3 + i) * (i - 2)) / 2;
        // cout<<sum<<endl;
        for (int j = 2; j <= f; j++)
        {
            if (pri[j] <= i)
                sum += pri[j];
            else
                break;
        }
        cout << sum << endl;
    }
}

// #pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
#define IOS                      \
    ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);       \
    std::cout.tie(nullptr);
#define int long long
const int INF = 1e18;
const int mod = 998244353;
const int N = 3e6 + 9;
int Trie[N][2];
int rem[N];
int tot = 1;
void insert(int x, int r)
{
    int u = 1;
    for (int i = 29; i >= 0; i--)
    {
        int flag = (x >> i) & 1LL;
        if (!Trie[u][flag])
        {
            Trie[u][flag] = ++tot;
            Trie[tot][0] = Trie[tot][1] = 0;
            rem[tot] = 0;
        }
        u = Trie[u][flag];
        rem[u] = max(rem[u], r);
    }
}
int check(int pos, int tar, int k)
{
    int u = 1;
    int ans = 0;
    for (int i = 29; i >= 0; i--)
    {
        int bittar = (tar >> i) & 1LL;
        int bitk = (k >> i) & 1LL;
        if (bitk)
        {
            u = Trie[u][bittar ^ 1];
        }
        else
        {
            if (Trie[u][bittar ^ 1])
            {
                ans = max(ans, rem[Trie[u][bittar ^ 1]]);
            }
            u = Trie[u][bittar];
        }
        if (!u)
            return ans;
    }
    ans = max(ans, rem[u]);
    return ans;
}

void solve()
{
    tot = 1;
    int n, k;
    cin >> n >> k;
    Trie[1][1] = Trie[1][0] = 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (i)
            a[i] ^= a[i - 1];
    }
    int ans = 0;
    insert(a[1], 1);
    pair<int, int> ansf = {INF, INF};
    int len = INF;
    for (int i = 2; i <= n; i++)
    {
        ans = check(i - 1, a[i], k);
        if (ans > 0)
        {
            if (i - ans < len)
            {
                len = i - ans;
                ansf = {ans + 1, i};
            }
            else if (i - ans == len)
            {
                ansf = min(ansf, {ans + 1, i});
            }
        }

        insert(a[i], i);
    }
    if (len == INF)
    {
        cout << -1 << endl;
        return;
    }
    cout << ansf.first << " " << ansf.second << endl;
}
signed main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define int long long
const int INF = 1e18;
const int mod = 998244353;
const int N = 36007; // N 是最大可以存储的元素数量
class Hash
{
private:
    int keys[N];
    int values[N];

public:
    Hash() { memset(values, 0, sizeof(values)); }

    int &operator[](int n)
    {
        int idx = (n % N + N) % N, cnt = 1;
        while (keys[idx] != n && values[idx] != 0)
        {
            idx = (idx + cnt * cnt) % N;
            cnt += 1;
        }
        keys[idx] = n;
        return values[idx];
    }
};
int qpow(int a, int b)
{ // 快速幂
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

int bsgs(int a, int b)
{
    Hash mp;
    if (a % mod == b % mod)
        return 1;
    if (a % mod == 0 && b)
        return -1;

    int unit = (int)ceil(sqrt(mod)), tmp = qpow(a, unit);
    for (int i = 0; i <= unit; ++i)
        mp[b] = i, b = (b * a) % mod;
    b = 1;
    for (int i = 1; i <= unit; ++i)
    {
        b = (b * tmp) % mod;
        if (mp[b])
            return i * unit - mp[b];
    }
    return -1;
}
void solve()
{
    int n, x;
    cin >> n >> x;
    if (x == 1)
    {
        cout << 0 << endl;
        return;
    }
    if (x == 0)
    {
        cout << 1 << endl;
        return;
    }
    int a = n - 1;
    int tt = (n * x + (n - 1));
    int k1 = bsgs(a, tt % mod);
    if (k1 % 2 == 0)
        k1 = -1;
    tt = (n * x - (n - 1)) + mod;
    int k2 = bsgs(a, tt % mod);
    if (k2 & 1)
        k2 = -1;
    if (k1 != -1 && k2 != -1)
        cout << min(k1, k2) << endl;
    else if (k1 != -1 && k2 == -1)
        cout << k1 << endl;
    else if (k2 != -1 && k1 == -1)
        cout << k2 << endl;
    else
        cout << -1 << endl;
    return;
}
signed main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

5
ABCBC
ACAAB

Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA

#include <bits/stdc++.h>
using namespace std;
int n;
string r, c;
vector<string> graph;
map<char, set<string>> mp;
bool flag = 0;
/*      1 1 1 1
        1 1 1 1
        1 1 1 1
        1 1 1 1
        1 1 1 1 高三位表示该列是否检查过，低1位表示对应字母是否占用
*/
int check;
void dfs(int i, int check)
{
    if (flag)
        return;
    if (i == n)
    {
        if (check == 0)
        {
            cout << "Yes" << endl;
            for (auto &nx : graph)
            {
                cout << nx << endl;
            }
            flag = 1;
        }
        return;
    }
    for (auto str : mp[r[i]])
    {
        graph.push_back(str);
        int nowcheck = check;
        bool accepted = 1;
        for (int j = 0; j < n; j++)
        {
            if (str[j] == '.')
                continue;
            int pos = 4 * j + (str[j] - 'A');
            if ((nowcheck & (1 << pos)) == 0)
            {
                accepted = 0;
                break;
            }
            nowcheck ^= (1 << pos);
            if (nowcheck & (1 << (4 * j + 3)))
            {
                if (str[j] != c[j])
                {
                    accepted = 0;
                    break;
                }
                nowcheck ^= (1 << (4 * j + 3));
            }
        }
        if (accepted)
            dfs(i + 1, nowcheck);
        graph.pop_back();
    }
}
int main()
{
    cin >> n >> r >> c;
    vector<int> abc(n);
    iota(abc.begin(), abc.end(), 0);
    // 0-2ABC,3.
    do
    {
        string s;
        char c = 0;
        for (auto p : abc)
        {
            if (p >= 0 && p <= 2)
            {
                s += char('A' + p);
                if (c == 0)
                    c = 'A' + p;
            }
            else
                s += '.';
        }
        mp[c].insert(s);

    } while (next_permutation(abc.begin(), abc.end()));
    check = (1 << (4 * n)) - 1;
    dfs(0, check);
    if (!flag)
        cout << "No" << endl;
    system("pause");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define int long long
const int INF = 1e18;
const int mod = 998244353;
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    multimap<int, int> dist;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        dist.insert({a[i], i});
    }
    vector<int> degree(n);
    int posnow;
    bool flag = 0;
    vector<pair<int, int>> rem;
    int remch = -1;
    queue<int> noww, nextt;
    for (auto [x, y] : dist) // x距离 y节点号
    {
        bool tag = 0;
        if (x - remch > 1)
        {
            cout << "-1" << endl;
            return;
        }
        if (x - remch == 1)
            tag = 1;
        remch = x;
        if (!x)
        {
            if (!flag)
            {
                flag = 1, posnow = y;
                nextt.push(y);
                continue;
            }
            else
            {
                cout << "-1" << endl;
                return;
            }
        }
        if (tag)
        {
            noww = nextt;
            nextt = queue<int>();
            if (noww.empty())
            {
                cout << "-1" << endl;
                return;
            }
            posnow = noww.front();
            noww.pop();
        }
        if (degree[posnow] >= k)
        {
            if (noww.empty())
            {
                cout << "-1" << endl;
                return;
            }
            posnow = noww.front();
            noww.pop();
        }
        degree[posnow]++;
        degree[y]++;
        rem.push_back({posnow, y});
        nextt.push(y);
    }
    cout << rem.size() << endl;
    for (auto [x, y] : rem)
    {
        cout << x + 1 << " " << y + 1 << endl;
    }
    return;
}
signed main()
{
    IOS;
    int t;
    t = 1;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define int long long
const int INF = 1e18;
const int mod = 998244353;
const int N = 1e5 + 5;
vector<vector<int>> connects;
vector<bool> vis;
vector<pair<int, int>> information;
void add_edge(int u, int v)
{
    connects[u].push_back(v);
    connects[v].push_back(u);
}
int ans = 0;
void init(int n)
{
    ans = 0;
    connects = vector<vector<int>>(n + 1);
    vis = vector<bool>(n + 1);
    information = vector<pair<int, int>>(n + 1);
    for (int i = 0; i <= n; i++)
    {
        vis[i] = false;
        information[i] = {0, 0};
    }
}
int dfs(int pos)
{
    vis[pos] = true;
    int res = 0;
    for (auto i : connects[pos])
    {
        if (!vis[i])
        {
            res += dfs(i);
            vis[i] = 0;
        }
    }
    if (!res) // 叶子结点
    {
        ans++;
        return information[pos].second;
    }
    if (res < information[pos].first)
    {
        ans++;
        return information[pos].second;
    }
    if (res > information[pos].second)
    {
        return information[pos].second;
    }
    return res;
}
void solve()
{
    int n;
    cin >> n;
    init(n);
    for (int i = 2; i <= n; i++)
    {
        int u;
        cin >> u;
        add_edge(i, u);
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> information[i].first >> information[i].second;
    }
    dfs(1);
    cout << ans << endl;
}
signed main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    // system("pause");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
vector<vector<int>> connects;
vector<int> dist;
vector<int> degrees;
vector<int> visited;
void init(int n)
{
    n++;
    connects.resize(n, vector<int>());
    dist.resize(n, INF);
    degrees.resize(n, 0);
    visited.resize(n, 0);
}
void add_edge(int u, int v)
{
    connects[u].push_back(v);
    degrees[v]++;
}
int Dijkstra_queue(int st, int ed) // 反向Dijkstra
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, ed});
    dist[ed] = 0;
    while (!q.empty())
    {
        auto [d, u] = q.top();
        q.pop();
        if (visited[u])
            continue;
        visited[u] = true;
        for (auto v : connects[u])
        {
            if (dist[v] > dist[u] + degrees[v])
            {
                dist[v] = dist[u] + degrees[v];
                q.push({dist[v], v});
            }
            degrees[v]--;
        }
    }
    return dist[st];
}
void solve()
{
    int n, m;
    cin >> n >> m;
    init(n);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        add_edge(v, u);
    }
    cout << Dijkstra_queue(1, n) << endl;
    return;
}
signed main()
{
    IOS;
    int t;
    t = 1;
    while (t--)
        solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
const int maxn = 2e5 + 10;
vector<int> connects[maxn];
int s[maxn], k[maxn], degree[maxn], dp[maxn];
int n;
bool vis[maxn];
void add_edge(int u, int v)
{
    connects[u].push_back(v);
}
typedef struct node
{
    int pos;
    int dis;
    bool operator<(const node &x) const
    {
        return x.dis < dis;
    }
} node;
void Dikstra_queue()
{
    priority_queue<node> q;
    for (int i = 1; i <= n; i++)
    {
        q.push({i, dp[i]}); // 初始化，预先把所有的法术伤害作为杀死方式预选择丢进去
        // 如果某个怪物的法术斩杀伤害是最小的，那么这个怪兽必然是使用法术斩杀的，其不可能再去使用物理伤害兜圈
        // 为什么全丢进去，是当某个节点的物理伤害计算发现其比法术斩杀还要大，那这个点就是用法术斩杀打死的
        // 如果最小的法术伤害绕着走了一圈之后没有发生新入队行为，那么就更新不动了，队列变空，
        //则说明如果某些可能度数没有归零的点的怪兽想使用物理伤害杀死，必须使用法术伤害干死的怪兽不止一个
        //答案就错误了，所以必须把所有的都丢进去以初始化才可以
    }
    while (!q.empty())
    {
        auto [pos, dpp] = q.top();
        q.pop();
        if (vis[pos])
            continue;
        vis[pos] = 1;
        dp[pos] = dpp; // 固定杀死方式
        for (auto v : connects[pos])
        {
            if (vis[v]) // 已经固定杀死方式，即dp值已确定
                continue;
            if (s[v] + dpp >= dp[v]) // 还没加完的物理攻击就已经比dp值大，此时不更新
                continue;
            s[v] += dpp;
            degree[v]--;
            if (!degree[v])
            {
                q.push({v, s[v]});
            }
        }
    }
    cout << dp[1] << endl;
}
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
signed main()
{
    IOS;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i] >> k[i] >> degree[i];
        dp[i] = k[i];
        for (int j = 1; j <= degree[i]; j++)
        {
            int x;
            cin >> x;
            add_edge(x, i);
        }
    }
    Dikstra_queue();
    system("pause");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
char ask_one(int i)
{
    cout << "? 1 " << i << endl;
    char c;
    cin >> c;
    fflush(stdout);
    fflush(stdin);
    return c;
}
int ask_line(int l, int r)
{
    cout << "? 2 " << l << " " << r << endl;
    int x;
    cin >> x;
    fflush(stdout);
    fflush(stdin);
    return x;
}
int main()
{
    int n;
    cin >> n;
    fflush(stdout);
    fflush(stdin);
    vector<int> remrangedif;
    string s;
    s += ask_one(1);
    remrangedif.push_back(1);
    for (int i = 1; i < n; i++)
    {
        int size = ask_line(1, i + 1);
        if (size > remrangedif[0])
        {
            s += ask_one(i + 1);
        }
        else
        {
            map<char, int> last;
            for (int j = 0; j < s.size(); j++)
                last[s[j]] = j; // 记录每个字母最后出现的位置
            vector<int> lasts;
            for (auto x : last)
                lasts.push_back(x.second);
            sort(lasts.begin(), lasts.end()); // 最后出现的位置排序
            int l = 0;
            int r = lasts.size();
            while (r - l > 1)
            {
                int m = (l + r) >> 1LL;
                int c = ask_line(lasts[m] + 1, i + 1);
                if (c == remrangedif[lasts[m]])
                    l = m;
                else
                    r = m;
            }
            s += s[lasts[l]];
            remrangedif.push_back({size});
        }
        remrangedif = vector<int>(i + 1);
        map<char, int> q;
        for (int j = i; j >= 0; j--)
        {
            q[s[j]]++;
            remrangedif[j] = q.size();
        }
    }
    cout << "! " << s << endl;
    fflush(stdout);
    fflush(stdin);
    return 0;
}