首页 > 其他分享 >2023年暑假集训总结/7.1

2023年暑假集训总结/7.1

时间：2023-07-03 20:03:57浏览次数：45  
标签：std write int 2023 rd 7.1 ans 集训 define

6-26

T1多米诺骨牌

　　Hades 与 Dionysus 在狂饮后玩起了多米诺骨牌的小游戏。 现在桌上有 n 块多米诺骨牌，每块多米诺骨牌上半部分和下半部分上都有一 个整数。每次翻转可让一块多米诺骨牌上下翻转，即上下部分数交换。 Hades 想 让 n 块骨牌上半部分的数加起来是一个偶数，而 Dionysus 想让这 n 块骨牌下半 部分的数加起来是一个偶数。喝醉的两人都不肯退让，非要达到自己的目的。路 过的 Hephaestus 在扫了一眼桌上的骨牌后瞬间给出了一个让两人都满意且翻转 次数最少的方案，便转身离去，留下呆滞的二人。 可这还没完，喝得烂醉的二人很快忘记了 Hephaestus 所说的方案， Hades 说 他还记得最少的翻转次数， Dionysus 不愿被比下去，只好来请教你了。

　　发现了以下性质：

　　　　 -对于上下都是偶数或都是奇数的骨牌，交换它是没有意义的。

　　　　 -对于上下一奇一偶的骨牌，翻转它能使总和从两个奇数变为两个偶数。

　　　　-对于目前总和为一奇一偶的情况无论怎么翻转都无法达成目标。

　　std:

#include <bits/stdc++.h>
typedef long long ll;
using std::min; using std::max;
#define INF 1e18
#define pE() puts("")
#define W(x) write(x)
#define rd() read<ll>()
#define lowbit(x) -x & x
#define pS() putchar(' ')
#define E(i, l, r) for (int i = l; i <= r; ++ i)
template <typename T>
inline T read() {
    T x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x / 10) write(x / 10);
    putchar((x % 10) ^ 48);
}
const int N = 1e4 + 5;
int n, a[N], b[N];
ll sumx, sumy;
int main() {
    freopen("domino.in", "r", stdin);
    freopen("domino.out", "w", stdout);
    n = rd();
    E(i, 1, n) {
        a[i] = rd();
        b[i] = rd();
        sumx += a[i];
        sumy += b[i];
    }
    sumx %= 2; sumy %= 2;
    if (sumx + sumy == 1)
        W(-1);
    else if (sumx == 0 && sumy == 0)
        W(0);
    else {
        bool flag = 0;
        E(i, 1, n)
            if ((a[i] % 2) ^ (b[i] % 2)) {
                W(1);
                flag = 1;    
                break;
            }
        if (!flag)
            W(-1);
    }
    return 0;
}

 

T2队列

　　N 个学生排队站在食堂的面包窗口前，在面包没有准备好之前，这个队伍发 生了一些变化。 若第 i 个位置上是一个男生，而他后面(i+1 的位置)是一个女生，出于某种目 的，他会与这位女生交换位置，使她能更接近窗口。这样的交换需要 1 秒的时间。 这样的位置交换会一直持续到无法再交换为止。即所有的女生都在男生前面。 问这样的交换会持续多久。

　　假设现在已经知道前一个女孩到达指定地点的时间记为 ans 对于当前的一个女孩，存在两种情况： --她到达前一个女孩初始位置后一位时，那个女孩还没有走掉，如： MFFFFFFMMF 那么这个女孩所需的时间为 ans+1。 --她到达前一个女孩初始位置后一位时，那个女孩已经走掉了，如： MFMMMF 发现此时在前一个女孩的牺牲‘铺垫’下，这个女孩可以一直走到她 最终的位置， 即她所需的时间为‘初始位置-最终位置’。 两者取 max 即为当前女孩到达最终位置所需的时间。

　　std：

#include <bits/stdc++.h>
typedef long long ll;
using std::min; using std::max;
#define INF 1e18
#define pE() puts("")
#define W(x) write(x)
#define rd() read<ll>()
#define lowbit(x) -x & x
#define pS() putchar(' ')
#define E(i, l, r) for (int i = l; i <= r; ++ i)
template <typename T>
inline T read() {
    T x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x / 10) write(x / 10);
    putchar((x % 10) ^ 48);
}
const int N = 1e6 + 5;
int n;
int ans, cnt, cntm;
char inp;
bool flag;
int main() {
    freopen("queue.in", "r", stdin);
    freopen("queue.out", "w", stdout);
    while ((inp = getchar()) == 'M' || inp == 'F')
    if (inp == 'M') {
      if (cnt)
        cnt--;
      cntm++, flag = 1;
    } else if (flag)
  ans = cntm + cnt++;
  W(ans);
    return 0;
}

T3可持久化数组

　　Motto 有一个长为 n 可持久化数组，在初始时刻(t=0)，第 i 个位置上的数为 ai，他会对这个可持久化数组进行 m 个操作或询问。 Motto 在每个整数时刻 t(1<=t<=m)会问你一个问题，或者对这个数组作一个 修改：

  1. 0 a b 将第 a 个位置上的数改成 b，且这一时刻第 a 个位置上的数视为 b。

  2. 1 a b 询问第 a 个位置上时刻为 b(t=b)时的数值。

　　开 n 个 vector，每个 vector 维护这个位置曾经的版本，和曾经这个位置为 该版本的最早时间和最晚时间。修改直接 push_back，查询的话可以在 vector 上二分查找。

　　std：

#include <bits/stdc++.h>
typedef long long ll;
using std::min; using std::max;
#define INF 1e18
#define pE() puts("")
#define W(x) write(x)
#define rd() read<ll>()
#define lowbit(x) -x & x
#define pS() putchar(' ')
#define E(i, l, r) for (int i = l; i <= r; ++ i)
template <typename T>
inline T read() {
    T x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x / 10) write(x / 10);
    putchar((x % 10) ^ 48);
}
const int N = 1e5 + 5;
struct Node {
    int data;
    int id;
};
int n, m;
std::vector<Node> V[N];
int main() {
    freopen("array.in", "r", stdin);
    freopen("array.out", "w", stdout);
    n = rd();
    m = rd();
    E(i, 1, n) {
        int x = rd();
        V[i].push_back({x, 0});
    }
    E(i, 1, m) {
        int opt = rd();
        int x, y;
        x = rd(); y = rd();
        if (opt == 0)
            V[x].push_back({y, i});
        else {
            int l = 0, r = V[x].size() - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (V[x][mid].id <= y)
                    l = mid;
                else
                    r = mid - 1;
            }
            W(V[x][l].data); pE();
        }
    }
    return 0;
}

T4毒瘤 hzq

　由于 hzq 出了大量的毒瘤题，机房里的同志们开始商量如何针对 hzq 搞事情。 某同志提出了一个建议：在校园里堵住他。 一中的校园非常大，为了将问题简单化，我们将校园看作一个 n 个点， m 条 边的无向连通图。 然而 hzq 知道了自己即将被搞事情，他对校园里的每条边定义了一个危险值， 他每天一定且仅会在某棵关于危险值的最小生成树的所有树边上出现至少一次。 刚才提出意见的同学根据自己对 hzq 的了解，猜测到了他每天会在满足什么 样的条件的边上出现，可是校园这么大， hzq 每天会在哪些边上出现呢？ 其实刚才提出意见的同学就是你，请你告诉机房里的同志们，在一天的时间 里，对于每一条道路， hzq 一定会出现，还是一定不会出现，还是可能会出现。

　　将边按权值从小到大排序，对于相同权值的所有边，将 所有不必要的边(即连接的两点可以通过更小权值的边连通的边)的答案标记为 ‚No‛ ，将剩下的边单独拎出来，用 tarjan 求割边，割边的答案为‚Yes‛ ，其 余边的答案为‚I AM NOT SURE!!!‛

　　std：

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second

mt19937_64 gen(time(0));

using u64 = unsigned long long;

int n, m;
struct edge {
    int u, v, w, ans, id;
    bool is;
} e[300005];

int b[100005];
int find(int x) {
    if (b[x] == x) return x;
    return b[x] = find(b[x]);
}

vector <pair <int, int>> G[100005];
int f[100005][17], g[100005][17], dep[100005], dfn[100005], timer = 0, sz[100005];

void dfs(int u, int ff) {
    dfn[u] = ++timer, sz[u] = 1;
    f[u][0] = ff, dep[u] = dep[ff] + 1;
    for (int i = 1; i <= 16; ++i) {
        f[u][i] = f[ f[u][ i - 1 ] ][ i - 1 ];
        g[u][i] = max(g[u][ i - 1 ], g[ f[u][ i - 1 ] ][ i - 1 ]);
    }
    for (auto v : G[u]) if (v.fi != ff) {
        g[ v.fi ][0] = v.se;
        dfs(v.fi, u);
        sz[u] += sz[ v.fi ];
    }
}

int qry_max(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int ans = 0;
    for (int i = 16; ~i; --i) {
        if (dep[ f[x][i] ] >= dep[y]) {
            ans = max(ans, g[x][i]);
            x = f[x][i];
        }
        if (x == y) return ans;
    }
    for (int i = 16; ~i; --i) {
        if (f[x][i] != f[y][i]) {
            ans = max({ans, g[x][i], g[y][i]});
            x = f[x][i], y = f[y][i];
        }
    }
    ans = max({ans, g[x][0], g[y][0]});
    return ans;
}

map <int, vector <int>> E, Q;

u64 t[100005], h[300005];
void add(int x, u64 v) {
    for (; x <= n; x += x & -x) t[x] ^= v;
}
u64 qry(int x) {
    u64 ans = 0;
    for (; x; x -= x & -x) ans ^= t[x];
    return ans;
}

int main() {
    freopen("hzq.in", "r", stdin), freopen("hzq.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].id = i, e[i].is = false;
    }
    sort(e + 1, e + m + 1, [&] (edge a, edge b) {
        return a.w < b.w;
    });
    iota(b + 1, b + n + 1, 1);
    for (int i = 1; i <= m; ++i) {
        int fx = find(e[i].u), fy = find(e[i].v);
        if (fx != fy) {
            b[fx] = fy, e[i].is = true;
            G[ e[i].u ].emplace_back(e[i].v, e[i].w);
            G[ e[i].v ].emplace_back(e[i].u, e[i].w);
        }
    }
    dfs(1, 0);
    for (int i = 1; i <= m; ++i) if (!e[i].is) {
        int now = qry_max(e[i].u, e[i].v);
        if (e[i].w > now) e[i].ans = -1;
        else if (e[i].w == now) e[i].ans = 0;
    }
    for (int i = 1; i <= m; ++i) if (e[i].is) {
        Q[ e[i].w ].push_back(i);
    } else E[ e[i].w ].push_back(i);
    vector <int> V;
    for (int i = 1; i <= m; ++i) V.push_back(e[i].w);
    for (int i = 1; i <= m; ++i) h[i] = gen();
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());
    for (auto w : V) {
        for (auto i : E[w]) {
            int u = e[i].u, v = e[i].v;
            u64 val = h[ e[i].id ];
            add(dfn[u], val), add(dfn[v], val);
        }
        for (auto i : Q[w]) {
            int u = e[i].u, v = e[i].v;
            if (dep[u] < dep[v]) swap(u, v);
            if (qry(dfn[u] - 1) == qry(dfn[u] + sz[u] - 1)) e[i].ans = 1;
            else e[i].ans = 0;
        }
        for (auto i : E[w]) {
            int u = e[i].u, v = e[i].v;
            u64 val = h[ e[i].id ];
            add(dfn[u], val), add(dfn[v], val);
        }
    }
    sort(e + 1, e + m + 1, [&] (edge a, edge b) {
        return a.id < b.id;
    });
    for (int i = 1; i <= m; ++i) {
        if (e[i].ans == 1) cout << "Yes\n";
        else if (e[i].ans == 0) cout << "I AM NOT SURE!!!\n";
        else if (e[i].ans == -1) cout << "No\n";
    }
    return 0;
}

 

标签：std,write,int,2023,rd,7.1,ans,集训,define
From： https://www.cnblogs.com/determination/p/17523843.html

相关文章

  • [CCO 2023] Line Town
    场上有点降智……其实会了互不相同的sub就可以会第一个sub甚至正解的。题意给定一个序列\(a_i\)，\(|a_i|\leq10^9\)，每次可以选两个相邻元素\(\texttt{swap}\)，然后将两个元素同时取反。问最少操作几次可以使数列不降。做法场上做法考虑\(|a_i|\)互不相同的部分分。我们......
  • 2023最新php goto完全解密系统程序
    PHPGOTO加密代码一度被认为是程序员的一大难题，但随着技术的不断进步，现在有了一款神奇的工具来解决这个问题。这款PHPGOTO解密工具拥有强大的功能，能够轻松解密和还原GOTO语句，让你的程序恢复到最初的状态。完整有效解密还原源码goto解密，基本做到免修复直接可用。Windows电脑版：https......
  • 2023年暑假集训总结/7.3
    2023年暑假集训总结/7.3预估成绩：100+50+40+20=210实际成绩：100+25+24+25=174T1房题意：有n个已知中心和长度且互不重合的区间，问有多少个长度为t的区间恰好与其中一个区间的一个端点相等，且不与所有区间重合思路&做法：签到题，注意到答案上界为2n，只需要依次枚举接在每个区间左右......
  • Cisco Catalyst 8000 Series Edge Platforms, IOS XE Release Dublin-17.11.01a ED
    CiscoCatalyst8000SeriesEdgePlatforms,IOSXEReleaseDublin-17.11.01aEDCiscoCatalyst8000边缘平台系列请访问原文链接：https://sysin.org/blog/cisco-catalyst-8000/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.orgCiscoCatalyst8000：随心所欲访问位于......
  • Cisco Catalyst 9800-CL Wireless Controller for Cloud, Release Dublin-17.11.01 ED
    CiscoCatalyst9800-CLWirelessControllerforCloud,ReleaseDublin-17.11.01ED面向云的思科Catalyst9800-CL无线控制器，专为基于意图的网络全新打造请访问原文链接：https://sysin.org/blog/cisco-catalyst-9800-cl/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.......
  • Cisco Catalyst 9000 Series Switches, IOS-XE Release Dublin-17.11.1 ED
    CiscoCatalyst9000SeriesSwitches,IOS-XEReleaseDublin-17.11.1EDCiscoCatalyst9000交换产品系列请访问原文链接：https://sysin.org/blog/cisco-catalyst-9000/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org接入和核心交换机与Wi-Fi6解决方案的产品组......
  • Cisco ISR 4000 Series IOS XE Release Dublin-17.11.1a ED
    CiscoISR4000SeriesIOSXEReleaseDublin-17.11.1aED思科4000系列集成服务路由器请访问原文链接：https://sysin.org/blog/cisco-isr-4000/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org思科4000系列集成服务路由器让您的分支机构站点为实施全数字化转型......
  • 2023.7.3
    ##输入带空格的字符串~~~c++1.#include<string.h>strings;getline(cin,s);2.#include<cstring>#include<stdio.h>chara[1024];gets(a);intlen=strlen(a);//得到数组的实际长度~~~##填充输入~~~javasetw(intn)//用来控制输出间隔//例：cout<<'s&......
  • Silhouette 2023.0.1 CE 影视后期ROTO跟踪抠像合成软件 支持AE/PR/达芬奇/VEGAS/OFX插
    Silhouette是一款被广泛应用于影视剧中Roto、抠像、擦威亚的特效合成辅助软件，正所谓术业有专攻，它就是为了应对这些脏活累活而诞生的。之前还有一款软件CommotionPro，但是已经停止开发，目前已经被这款Silhouette所替代，目前它也属于BorisFX家族的一员。软件下载Silhouette2023.......
  • day81（2023.7.3）
    1.依赖冲突调解_最短路径优先原则 2.依赖冲突调解_最先声明原则3.依赖冲突调解_排除依赖、锁定版本 4.Maven聚合开发_聚合关系 5.Maven聚合开发_继承关系6.Maven聚合案例_搭建父工程7.Maven聚合案例_搭建dao模块8.Mave......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99