头像

Cabbage74




离线:1小时前


最近来访(108)
用户头像
AcWing2AK
用户头像
小猪软糖z
用户头像
ZhgDgE
用户头像
也许明夜更灿烂
用户头像
77an
用户头像
Fcy
用户头像
Saury
用户头像
su尔
用户头像
syadream
用户头像
Johnwang
用户头像
隐辰乃
用户头像
Aigrl
用户头像
Pz.Climb
用户头像
fwyize
用户头像
masterpiece
用户头像
acwing_7777
用户头像
呐呐呐呐
用户头像
lmzz
用户头像
njw1123
用户头像
lfm

活动打卡代码 AcWing 1123. 铲雪车

Cabbage74
5小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1192. 奖金

Cabbage74
5小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1191. 家谱树

Cabbage74
5小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 343. 排序

Cabbage74
20小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



原题链接

题目大意

给定一个数组$a$以及$m$个询问
每次询问$[l,r]$间是否存在$i,j$满足$a[i]\bigoplus a[j]=x$

解题思路

十三届蓝桥杯的题
处理出$c$数组,$c[i]$存储$a[i]$右边第一个满足$a[i]\bigoplus a[j]=x$的$a[j]$下标$j$
对$c$数组建线段树维护区间最小值
只要$[l,r]$的$min(c[i])\leq r$就说明$yes$

具体代码

#include <bits/stdc++.h>
const int N = 1e5 + 10;
int n, m, x;
int a[N];
int c[N]; //存储a[i]右边第一个满足a[i]^a[j]=x的a[j]下标j
struct node
{
    int minv;
} tr[N * 4];
node operator+(const node &l, const node &r)
{
    return {std::min(l.minv, r.minv)};
}
void pushup(int id)
{
    tr[id] = tr[id * 2] + tr[id * 2 + 1];
}
void build(int id, int l, int r)
{
    if (l == r)
        tr[id].minv = c[l];
    else
    {
        int mid = l + r >> 1;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        pushup(id);
    }
}
int query(int id, int l, int r, int ql, int qr)
{
    if (l == ql && r == qr)
        return tr[id].minv;
    int mid = l + r >> 1;
    if (qr <= mid)
        return query(id * 2, l, mid, ql, qr);
    else if (ql > mid)
        return query(id * 2 + 1, mid + 1, r, ql, qr);
    else
        return std::min(query(id * 2, l, mid, ql, mid), query(id * 2 + 1, mid + 1, r, mid + 1, qr));
}
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    std::cin >> n >> m >> x;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> a[i];
        c[i] = N;
    }
    std::map<int, int> S;
    for (int i = n; i >= 1; --i)
    {
        if (S.count(a[i] ^ x))
            c[i] = S[a[i] ^ x];
        S[a[i]] = i;
    }
    /*
    for (int i = 1; i <= n; ++i)
        std::cout << c[i] << ' ';
    */
    build(1, 1, n); //对c[i]建立维护区间最小值的线段树
    while (m--)
    {
        int l, r;
        std::cin >> l >> r;
        if (query(1, 1, n, l, r) <= r)
            std::cout << "yes" << '\n';
        else
            std::cout << "no" << '\n';
    }
    return 0;
}



原题链接

题目大意

定义一个整数数组的子序列$s$的价值$v$为:
$v=min(max(s_1,s_3,s_5,…),max(s_2,s_4,s_6,…))$
问长度为$k$的子序列的最小价值是多少

解题思路

利用二分将问题转换为判定性问题,类似的题有数列分段II
每次$check$的是:对于给定的$x$,是否有一个长度至少为$k$的子序列,这个子序列的偶数下标的元素值都$\leq x$或者这个子序列的奇数下标的元素值都$\leq x$
考虑偶数下标时,奇数元素就都取上一个选择的元素的恰好下一个
考虑奇数下标时同理

具体代码

#include <bits/stdc++.h>
const int N = 2e5 + 10;
int n, k;
int a[N];
bool check(int x, int cur)
{
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (!cur)
        {
            ++cnt;
            cur ^= 1; 
        }
        else
        {
            if (a[i] <= x)
            {
                ++cnt;
                cur ^= 1;
            }
        }
    }
    return cnt >= k;
}
int main()
{
    std::cin >> n >> k;
    int l = 1, r = 1e9;
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid, 0) || check(mid, 1))
            r = mid;
        else
            l = mid + 1;
    }
    std::cout << l << '\n';
    return 0;
}



原题链接

题目大意

对于给定的每个数$x$,可以进行两种操作
第一种操作:令$x=(x+1)\ mod\ 32768$
第二种操作:令$x=(x\times 2)\ mod\ 32768$
问最少操作几次将$x$变成$0$

解题思路

第一眼是经典的$BFS$最少步数题,用$dp$什么的应该也可以
类似的有什么把一个数通过减一或者乘二变成另一个数,求最小步数(可能记错了?原题在哪也忘了)
但是这题的模数有点特殊,因为$32768=2^{15}$
所以答案最多是$15$(无脑做$15$次第二种操作就能得到$0$)
所以暴力枚举两种操作的次数就可以了

具体代码

#include <bits/stdc++.h>
int n;
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int T;
    std::cin >> T;
    while (T--)
    {
        std::cin >> n;
        int ans = 15;
        for (int i = 0; i <= 15; ++i)
            for (int j = 0; j <= 15 - i; ++j)
                if (((n + i) * (int)std::pow(2, j)) % 32768 == 0)
                    ans = std::min(i + j, ans);
        std::cout << ans << ' ';
    }
    return 0;
}



Codeforces Round #812 (Div. 2)

A.Traveling Salesman Problem

题目大意

有一些在$x$轴,$y$轴上的点,现要求你从原点出发经过所有点并最后返回原点,求最小步数

解题思路

签到题

具体代码

#include <bits/stdc++.h>
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int T;
    std::cin >> T;
    while (T--)
    {
        int n;
        std::cin >> n;
        int l = 0, r = 0, u = 0, d = 0;
        while (n--)
        {
            int x, y;
            std::cin >> x >> y;
            if (x == 0 && y > 0)
                u = std::max(u, y);
            else if (x == 0 && y < 0)
                d = std::max(d, -y);
            else if (y == 0 && x > 0)
                r = std::max(r, x);
            else if (y == 0 && x < 0)
                l = std::max(l, -x);
        }
        std::cout << 2 * (u + d + r + l) << '\n';
    }
    return 0;
}

B.Optimal Reduction

题目大意

给定一个正整数数组$a$,你可进行无限次操作,每次选择一段连续区间使其中所有数减一
定义$f(a)$为将$a$中所有元素变为零的最少操作数
对于$a$的任意排列$b$,判断是否有$f(a)\leq f(b)$,有则输出$YES$

解题思路

在任意排列中,把数组按升序或降序排序得到的排列$b$显然有最小的$f(b)$
但也可以发现样例给的$2,3,5,4$也是$YES$
容易想到$2,3,5,4,6$就不行了,因为$4$比$5$和$6$先到$0$,阻断了$5$和$6$继续变零
因此判断原数组$a$是否是单峰的即可
第一眼因为给的样例,想的是判断是否有一个数的左右两边都有比它大的数,所以写了个单调栈
其实可以写的简单点

具体代码

#include <bits/stdc++.h>
const int N = 1e5 + 10;
int a[N];
int s[N];       //单调栈
int l[N], r[N]; // l[i]存a[i]左侧第一个比它大的数,不存在就是-1,r[i]同理
int n;
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int T;
    std::cin >> T;
    while (T--)
    {
        std::cin >> n;
        for (int i = 1; i <= n; ++i)
            std::cin >> a[i];
        memset(s, 0, sizeof s);
        int tt = 0;
        for (int i = 1; i <= n; ++i)
        {
            while (tt && s[tt] <= a[i])
                --tt;
            if (tt)
                l[i] = s[tt];
            else
                l[i] = -1;
            s[++tt] = a[i];
        }
        memset(s, 0, sizeof s);
        tt = 0;
        for (int i = n; i >= 1; --i)
        {
            while (tt && s[tt] <= a[i])
                --tt;
            if (tt)
                r[i] = s[tt];
            else
                r[i] = -1;
            s[++tt] = a[i];
        }
        /*
        for (int i = 1; i <= n; i++)
            std::cout << i << ": " << l[i] << ' ' << r[i] << '\n';
        */
        bool flag = true;
        for (int i = 1; i <= n; i++)
            if (l[i] != -1 && r[i] != -1) //不是单峰就不行
            {
                flag = false;
                break;
            }
        if (flag)
            std::cout << "YES\n";
        else
            std::cout << "NO\n";
    }
    return 0;
}

C.Build Permutation

题目大意

构造一个$0$到$n-1$的排列$p$,使得$p_i+i$是完全平方数

解题思路

根据给的样例其实就能猜这些完全平方数是块状递增的
先给出做法
现考虑构造一个$0$到$12$的满足条件的排列,
黑色的是下标,蓝色的是要填入的数
先找到不小于$12$的最小的完全平方数,是$16$,那么在$12$填入$16-12=4$
9723f8680f5d7c7c42993d6358d648a.png
相应的,在$4$处填入$12$,那么一个块就构造好了
fbcb119df10121ec092e714591bd75e.png
再往前重复,构造这些块,就得到了答案
8c902272cd54c83b95c85f5cc3ed88b.png
再给出证明
我们的做法是对于块的每个右端点$r=x$,找到一个$a^2,(a-1)^2 < x\leq a^2$,让$l=a^2-x$作为左端点
那么只要这样做得到的$l\leq r$恒成立,就说明我们构造的块都一定存在
证明$l\leq r$如下:
2931d7c67ffe967a40d3018bfc9d0ff.png

具体代码

#include <bits/stdc++.h>
const int N = 1e5 + 10;
int n;
int ans[N];
int square[N];
int get(int x) //二分得到不小于x的最小的完全平方数
{
    int l = 0, r = 1000;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (square[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return square[l];
}
void fill(int r)
{
    if (r < 0)
        return;
    int t = get(r);
    int l = t - r;
    fill(l - 1);
    for (int i = l; i <= r; ++i)
        ans[i] = t - i;
}
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    for (int i = 1; i <= 1000; ++i)
        square[i] = i * i;
    int T;
    std::cin >> T;
    while (T--)
    {
        std::cin >> n;
        fill(n - 1);
        for (int i = 0; i < n; ++i)
            std::cout << ans[i] << ' ';
        std::cout << '\n';
    }
    return 0;
}

D.Tournament Countdown

题目大意

交互题,有一个$2^n$个人参加的比赛,这个比赛已经结束了
要求在$\frac{2}{3}\times 2^n$次询问内问出谁是冠军
每次询问能知道两个人谁的获胜次数多

解题思路

每四个人一组,两次询问,问出这四个人里谁晋级了
等比数列求和可以知道这样是不会超过询问次数限制的
$(\frac{1}{2}+\frac{1}{8}+\cdots)\times 2^n$

具体代码

#include <bits/stdc++.h>
int ask(int x, int y)
{
    std::cout << "? " << x << " " << y << std::endl;
    int res;
    std::cin >> res;
    return res;
}
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int T;
    std::cin >> T;
    while (T--)
    {
        int n;
        std::cin >> n;
        n = 1 << n;
        std::vector<int> q;
        for (int i = 1; i <= n; ++i)
            q.push_back(i);
        while (q.size() > 1)
        {
            std::vector<int> t;
            if (q.size() == 2) 
            {
                int res = ask(q[0], q[1]);
                if (res == 1)
                    t.push_back(q[0]);
                else
                    t.push_back(q[1]);
            }
            else
            {
                for (int i = 0; i < q.size(); i += 4)
                {
                    int res1 = ask(q[i], q[i + 2]);
                    if (res1 == 0)
                    {
                        int res2 = ask(q[i + 1], q[i + 3]);
                        if (res2 == 1)
                            t.push_back(q[i + 1]);
                        else
                            t.push_back(q[i + 3]);
                    }
                    else if (res1 == 1)
                    {
                        int res2 = ask(q[i], q[i + 3]);
                        if (res2 == 1)
                            t.push_back(q[i]);
                        else
                            t.push_back(q[i + 3]);
                    }
                    else
                    {
                        int res2 = ask(q[i + 1], q[i + 2]);
                        if (res2 == 1)
                            t.push_back(q[i + 1]);
                        else
                            t.push_back(q[i + 2]);
                    }
                }
            }
            q = t; 
        }
        std::cout << "! " << q[0] << std::endl;
    }
    return 0;
}

E.Cross Swapping

题目大意

给定一个矩阵$g$,每次操作可以选择一个$k$进行$move$

void move(int k)
{
    for (int i = 1; i <= n; ++i)
        std::swap(g[i][k], g[k][i]);
}

问操作能得到的最小字典序的矩阵是什么

解题思路

最小字典序,那么多半是要贪心了
根据矩阵字典序的定义,依次考虑矩阵主对角线上方的这些元素
可以发现对于一个元素$g[i][j]$,当$k=i$或$k=j$时,都会交换$g[i][j]$
因此若想交换$g[i][j]$和$g[j][i]$,$i$和$j$只能选一个
若不想交换$g[i][j]$和$g[j][i]$,$i$和$j$要么都选要么都不选
想到这里其实可以发现就是一道带权并查集或者扩展域并查集维护关系的题了
不是很懂并查集维护关系的话或许可以点这里

具体代码

#include <bits/stdc++.h>
const int N = 1010;
int p[N * 2];
int g[N][N];
int n;
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
void move(int k)
{
    for (int i = 1; i <= n; ++i)
        std::swap(g[i][k], g[k][i]);
}
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int T;
    std::cin >> T;
    while (T--)
    {
        std::cin >> n;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                std::cin >> g[i][j];
        for (int i = 1; i < N * 2; ++i)
            p[i] = i;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = i + 1; j <= n; ++j)
            {
                if (g[i][j] > g[j][i]) //根据贪心,应该是尽量换
                {
                    if (find(i) == find(j)) //发现i和j已经是要么都选要么都不选的关系,只能作罢
                        continue;
                    p[find(i)] = find(j + N);
                    p[find(i + N)] = find(j);
                }
                else if (g[i][j] < g[j][i]) //根据贪心,应该是尽量不换
                {
                    if (find(i + N) == find(j)) //发现i和j已经是必须选一个的关系,只能作罢
                        continue;
                    p[find(i)] = find(j);
                    p[find(i + N)] = find(j + N);
                }
            }
        }
        std::set<int> S;
        for (int i = 1; i <= n; ++i)
            if (find(i) == i) //找出所有代表元素
                S.insert(i);
        for (int i = 1; i <= n; ++i)
            if (S.count(find(i)))
                move(i);
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
                std::cout << g[i][j] << ' ';
            std::cout << '\n';
        }
    }
    return 0;
}



原题链接

题目大意

给定一张$n$个顶点,$m$条边的无向图,保证无自环无重边,问图中环的数量
此题中环的定义有点特殊:要求环中每个顶点的度都为$2$

解题思路

对没有访问过的点进行一遍$dfs$判断所在集合是否成环
利用并查集加速$dfs$过程

具体代码

#include <bits/stdc++.h>
const int N = 2e5 + 10;
int n, m;
int h[N], e[2 * N], ne[2 * N], idx, d[N];
std::pair<int, bool> p[N];
bool vis[N];
int ans;
int find(int x) //可能写成pair形式有点丑
{
    if (p[x].first != x)
        p[x].first = find(p[x].first);
    return p[x].first;
}
void add(int a, int b)
{
    d[a]++; // d数组记录顶点的度
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
bool dfs(int u)
{
    vis[u] = true;
    if (d[u] != 2) //如果这个顶点度不为2
    {
        p[find(u)].second = false; //那么这个顶点所在的集合都不用考虑了
        return false;
    }
    if (p[find(u)].second == false) //如果所在的集合在之前已经被判定为不可能成环
        return false;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (vis[j])
            continue;
        if (!dfs(j))
            return false;
    }
    return true;
}
/*
bool st[N]; //用于调试输出
void show(int u)
{
    st[u] = true;
    std::cout << u << ' ';
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
            show(j);
    }
}
*/
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    std::cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++)
        p[i] = {i, true};
    for (int i = 0; i < m; i++)
    {
        int u, v;
        std::cin >> u >> v;
        add(u, v);
        add(v, u);
        p[find(u)].first = find(v); //合并集合
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
        {
            ans += dfs(i) ? 1 : 0;
            /*
            if (dfs(i)) //用于调试输出
            {
                std::cout << "cycle:";
                show(i);
                std::cout << '\n';
            }
            */
        }
    std::cout << ans << '\n';
    return 0;
}



Codeforces Round #811 (Div. 3)

A.Everyone Loves to Sleep

题目大意

给定入睡时间和定的若干个闹钟时间,问最多能睡多久

解题思路

简单模拟

具体代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
int n, H, M;
int h[N], m[N];
PII ans[N];
bool cmp(PII a, PII b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    // T = 1;
    while (T--)
    {
        cin >> n >> H >> M;
        for (int i = 1; i <= n; i++)
            cin >> h[i] >> m[i];
        for (int i = 1; i <= n; i++)
        {
            int hour1, minute1;
            int hour2, minute2;
            int hour, minute;
            hour1 = H, hour2 = h[i], minute1 = M, minute2 = m[i];
            if (minute2 < minute1)
            {
                minute = minute2 + 60 - minute1;
                hour2--;
            }
            else
                minute = minute2 - minute1;
            if (hour2 < hour1)
                hour = hour2 + 24 - hour1;
            else
                hour = hour2 - hour1;
            ans[i] = {hour, minute};
        }
        sort(ans + 1, ans + n + 1, cmp);
        cout << ans[1].first << ' ' << ans[1].second << '\n';
    }
    return 0;
}

B.Remove Prefix

题目大意

给一个数组,最少删除前面多少个数能使剩下数组不含重复数

解题思路

从后往前用$map$记录

具体代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
int n;
int a[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    // T = 1;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        map<int, int> S;
        int t = 0;
        for (int i = n; i >= 1; i--)
        {
            if (S[a[i]] != 0)
            {
                t = i;
                break;
            }
            S[a[i]] = 1;
        }
        cout << t << '\n';
    }
    return 0;
}

C.Minimum Varied Number

题目大意

给定$n$,构造出一个最小的数,这个数每一位都不相同,且每一位上的数字相加的和等于$n$

解题思路

简单贪心,要构造出最小,就是要数字位数尽量少,且小的数字在高位
于是从$9$向$1$枚举,能减则减,减完了以后记录,再从$1$至$9$输出

具体代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10;
const int MOD = 1e9 + 7;
int n;
int c[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    // T = 1;
    while (T--)
    {
        memset(c, 0, sizeof c);
        cin >> n;
        for (int i = 9; i >= 1; i--)
        {
            if (n >= i)
            {
                n -= i;
                c[i]++;
            }
        }
        for (int i = 1; i <= 9; i++)
            if (c[i])
                cout << i;
        cout << '\n';
    }
    return 0;
}