首页 > 其他分享 >海亮02/15杂题

海亮02/15杂题

时间：2024-02-15 18:44:41浏览次数：24  
标签：02 tmp ch int 海亮 dep maxn push 杂题

海亮02/15杂题

个人题单

T2

link

题意

给定一个 \(n\) 个点，\(m\) 条边的仙人掌，每条边至多存在于一个环。你可以进行如下操作：

  • 选择一个度数为奇数的点，把与其相连的边全部删去。
  • 创建一个新的图，新图有 \(2n\) 个点。假如原图的编号为 \(1\sim n\) ，则若原图中 \(u,v\) 有边，则新图中连边 \(u,v\) 。同时，\(\forall i\in [1,n]\) ，连边 \(u+n,v+n\)。然后用新图替换原图。

你可以以任意顺序执行第一种操作若干次以及第二种操作至多一次，求是否可以把图操作至只有孤立点，你需要构造方案。

\(n\le 3\times 10^5,n - 1\le m\le \frac{3(n-1)}{2}\)

题解

首先先尽可能的用操作 \(1\)，然后发现剩下的一定是若干个环相交。

然后用一次操作 \(2\)。

先转化成圆方树，方便描述（和coding）

我们依次考虑“叶子”上的环，尝试减除所有除了与父节点相连的点。

然后发现，对于每个点 \(i\) 和复制出来的点 \(i+n\)，依次操作 \(1,2+n,3\dots\)（除了那个需要保留的父节点），然后分环大小奇偶性讨论：

  • 大小是偶数：操作最左的复制点和最右的复制点。
  • 大小是奇数：操作最左的复制点和最右的原始点。

然后你就惊喜的发现做完了。

代码

#include<bits/stdc++.h>
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e6 + 10;
int n, m;
vector<int> edg[maxn], ans;
bool deg[maxn], dl[maxn];
inline void op(int x){ans.push_back(x);}
inline void del(int x){
    op(x);deg[x] = 0;dl[x] = 1;
    for(int v : edg[x])if(!dl[v])deg[v] ^= 1;
    for(int v : edg[x])if(!dl[v] && deg[v])del(v);
}
int idx, dfn[maxn], low[maxn], cnt;
stack<int> stk;
vector<int> e2[maxn];//建立一颗圆方树方便找答案
void dfs(int u){
    dfn[u] = low[u] = ++idx;stk.push(u);
    for(int v : edg[u]){
        if(!dfn[v]){
            dfs(v);
            if(low[v] >= dfn[u]){
                cnt++;int w = stk.top();
                do{
                    w = stk.top();stk.pop();
                    e2[w].push_back(cnt);e2[cnt].push_back(w);
                }while(w != v);
                e2[u].push_back(cnt);e2[cnt].push_back(u);
            }
            else low[u] = min(low[v],low[u]);
        }
        else low[u] = min(dfn[v],low[u]);
    }
}
bool vis[maxn];
void work(int u,int pre){
    vis[u] = 1;
    for(int v : e2[u])if(v != pre)work(v, u);
    if(u <= n){if(!pre)op(u);return;}//特判一下最后一个环
    int pos = 0;//找与其他环相邻的那个点p。
    for(int j = 0;j < e2[u].size();j++)if(e2[u][j] == pre)pos = j;

    vector<int> a;a.clear();//以p为开始将整个环展开
    for(int j = 0;j < e2[u].size();j++){a.push_back(e2[u][(j + pos) % e2[u].size()]);}
    
    int m = a.size() - 1;
    for(int j = 1;j <= m;j++)op(a[j] + ((j & 1) == 0) * n);
    op(a[m] + (m & 1) * n);op(a[1] + n);
}
void main(){
    n = read(); m = read();int u, v;cnt = n;
    for(int i = 1;i <= m;i++){
        u = read(), v = read();
        deg[u] ^= 1;deg[v] ^= 1;
        edg[u].push_back(v);edg[v].push_back(u);
    }
    for(int i = 1;i <= n;i++)if(deg[i])del(i);
    for(int i = 1;i <= n;i++)
        if(!dl[i]){
            vector<int> tmp;tmp.clear();
            for(int v : edg[i])if(!dl[v]){tmp.push_back(v);}
            edg[i] = tmp;
        }
        else edg[i].clear();
    ans.push_back(0);
    for(int i = 1;i <= n;i++)if(!dfn[i])dfs(i);
    for(int i = 1;i <= n;i++)if(!vis[i])work(i,0);
    printf("0 %d\n",(int)ans.size());
    for(int i : ans){
        if(i)printf("1 %d\n",i);
        else puts("2");
    }
    return;
}
};
bool edmemory;
signed main(){
    auto stclock = clock();
    Call_me_Eric::main();
    auto edclock = clock();
    cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
    cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
    return 0;
}
/*
7 7
1 2
1 3
2 3
2 4
2 5
3 6
3 7
*/

T3

link

题意

给一个没有容量的网络流图，每条边有一个\(g_i\)表示这条边是否有流量。请给每条边一个正容量并计算一种最大流，满足\(g_i=0\)的边流量为\(0\)，\(g_i=1\)的边流量不为\(0\)，且最小化满流边的数量\(k\)。数据保证没有重边自环并且有解，多解输出任意一种。

题解

满流量=割边

然后考虑通过刻画残量网络来确定哪条边是割边。

首先需要知道，最终的残量网络中，源点不能到达汇点。

然后对两种边 \(u\to v\) 分类讨论：

  • 强制没有流量的边：直接连一条 \(u\to v\)，容量为 \(\inf\) 的边，防止被割断。
  • 强制有流量的边：先连一条 \(v\to u\)，容量是 \(\inf\) 的边，表示一定存在流量，然后再连一条 \(u\to v\)，容量是 \(1\) 的边，表示可以通过满流 \(u\to v\) 来断开 \(u\to v\)。

然后跑一遍最小割，你就能得到最少的满流边数量。

然后考虑构造方案。

你先对于每条需要有流量的边，限制流量上下界是 \([1,\inf)\)，然后跑一边上下界最大流。

然后对于你规划好的满流边，容量就是流量，否则给一个极大的容量。

没有流量的边，流量是零，容量极大即可。

然后就做完了。

代码

#include<bits/stdc++.h>
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e5 + 10,INF = 1e6;
int n, m;
int head[maxn], tot = 1;
struct edge{
    int to, nexte, cap, flow;
    edge(int t = 0,int ne = 0,int ca = 0,int fl = 0)
    :to(t),nexte(ne),cap(ca),flow(fl){}
}e[maxn];
void add(int u,int v,int cap){e[++tot] = edge(v,head[u],cap);head[u] = tot;}
void addd(int u,int v,int cap){add(u, v, cap);add(v, u, 0);}
int cur[maxn], dep[maxn];
int dfs(int u,int flow,int T){
    if(u == T || !flow)return flow;
    int res = 0;
    for(int i = cur[u];i;i = e[i].nexte){
        int v = e[i].to;cur[u] = i;
        if(dep[v] == dep[u] + 1 && e[i].cap > e[i].flow){
            int tmp = dfs(v,min(flow,e[i].cap - e[i].flow),T);
            if(!tmp)dep[v] = INF;
            e[i].flow += tmp;e[i ^ 1].flow -= tmp;
            res += tmp;flow -= tmp;
            if(!flow)return res;
        }
    }
    return res;
}
queue<int> que;
bool bfs(int S,int T){
    while(!que.empty())que.pop();
    for(int i = 0;i <= n + 1;i++){cur[i] = 0;dep[i] = INF;}
    que.push(S);cur[S] = head[S];dep[S] = 1;
    while(!que.empty()){
        int u = que.front();que.pop();
        for(int i = head[u];i;i = e[i].nexte){
            int v = e[i].to;
            if(e[i].cap > e[i].flow && dep[v] == INF){
                dep[v] = dep[u] + 1;cur[v] = head[v];
                que.push(v);
            }
        }
    }
    return dep[T] != INF;
}
int Dinic(int S,int T){
    int maxflow = 0;
    while(bfs(S,T))maxflow += dfs(S,INF,T);
    return maxflow;
}
int opt[maxn], from[maxn], to[maxn];
bool vis[maxn];
void dfs1(int u){
    vis[u] = 1;
    for(int i = head[u];i;i = e[i].nexte){
        int v = e[i].to;
        if(e[i].cap > e[i].flow && !vis[v])dfs1(v);
    }
}
int id[maxn];
void main(){
    int S, T;
    n = read(); m = read(); S = read(); T = read();
    int u, v;
    for(int i = 1;i <= m;i++){
        from[i] = u = read();to[i] = v = read(); opt[i] = read();
        if(opt[i] == 1){addd(u,v,1);addd(v, u,INF);}
        else addd(u, v, INF);
    }
    printf("%d\n",Dinic(S,T));
    dfs1(S);
    memset(head,0,sizeof(head));tot = 1;
    memset(e,0,sizeof(e));
    addd(T,S,INF);int ss = 0, tt = n + 1;
    for(int i = 1;i <= m;i++){
        if(opt[i]){
            addd(from[i],to[i],INF - 1);
            addd(ss,to[i],1); addd(from[i],tt,1);
            id[i] = tot - 5;
        }
    }
    for(int i = 1;i <= m;i++){
        if(opt[i]){
            if(vis[from[i]] ^ vis[to[i]])printf("%d %d\n",e[id[i]].flow + 1,e[id[i]].flow + 1);
            else printf("%d 1000000\n",e[id[i]].flow + 1);
        }
        else puts("0 1000000");
    }
    return;
}
};
bool edmemory;
signed main(){
    auto stclock = clock();
    Call_me_Eric::main();
    auto edclock = clock();
    cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
    cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
    return 0;
}

T4

link

题意

给定 \(n\) 个绿洲，第 \(i\) 个绿洲的坐标为 \(x_i\) ，保证 \(-10^{9}\le x_1<x_2...<x_n\le 10^9\)

现在有一个人在沙漠中进行旅行，他初始的背包的水容积为 \(V\) 升，同时他初始拥有 \(V\) 升水 ，每次到达一个绿洲时，他拥有的水的量将自动重置为容积上限（可以使用多次）。他现在可以选择两个操作来进行旅行：

\(1.\) 走路，行走距离为 \(d\) 时，需要消耗 \(d\) 升水。清注意，任意时刻你拥有的水的数量不能为负数。

\(2.\) 跳跃，令 \(v\) 为你当前拥有的水量，若 \(v>0\)，则你可以跳跃至任意一个绿洲，然后重置容积上界和所拥有的水量为 \(v/2\) （向下取整）。

对于每一个 \(i\) 满足 \(1\le i\le n\) ，你需要求解，当你在第 \(i\) 个绿洲作为起点时，你能否依次遍历其他所有绿洲。如果可以，输出 Possible，否则输出 Impossible。

题解

首先想到，可能用到的 \(V\) 有 \(\log n\) 个。

然后想到，将问题转化为，用 \(\log n\) 个长度分别为 \(V,\frac{V}{2},\frac{V}{4},\dots\) 的线段覆盖所有的 \([1,n]\)，但是第一条线段 \(V\) 已经安排好位置。

然后想到状压，考虑预处理 \(l_{sta},r_{sta}\) 分别表示在使用线段状态是 \(sta\) 的时候，从 \(n\) 开始向左/从 \(1\) 开始向右 最远能够到达的位置。

然后发现可以预处理每个位置在只使用 \(V\) 的前提下能够到达的最大范围。

然后发现，可以根据这个将整个数轴划分为 \(cnt\) 个不相交的线段。

显然可以发现，如果 \(cnt>\log n\)，那么显然无法覆盖所有位置，那么全都无解。

然后只考虑线段数量少于 \(cnt\) 个的情况。

不难发现，对于每条线段，只需要找到能够同时到达其左边和右边的状态，即为有解，否则无解。

然后就没了。

代码

#include<bits/stdc++.h>
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 4e5 + 10, INF = 0x3f3f3f3f;
int n, V;
int x[maxn];
pair<int,int> seg[maxn];
int cntseg, dep;
int L[21][maxn], R[21][maxn];//在v = V>>i时，u能够到达的最左最右点是[L[i][u],R[i][u]]
int l[maxn * 5], r[maxn * 5];//在状态是sta时，从n出发能够跳到最左点l[sta],从1出发能够跳到最右点r[sta]
bool ans[maxn];
void main(){
    n = read(); V = read();x[0] = -INF;x[n + 1] = INF;
    for(int i = 1;i <= n;i++)x[i] = read();
    for(int v = V;v >= 0;v >>= 1,dep++){
        R[dep][n + 1] = n + 1;
        for(int i = 1;i <= n;i++)L[dep][i] = (x[i] - x[i - 1] <= v) ? L[dep][i - 1] : i;
        for(int i = n;i >= 1;i--)R[dep][i] = (x[i + 1] - x[i] <= v) ? R[dep][i + 1] : i;
        if(v == 0){dep++;break;}
    }
    for(int i = 1;i <= n;i++){seg[i] = make_pair(L[0][i],R[0][i]);}
    sort(seg + 1,seg + 1 + n);
    cntseg = unique(seg + 1,seg + 1 + n) - seg - 1;
    if(cntseg > dep){//保证最多只有log n条线段，再多就一定无法覆盖
        for(int i = 1;i <= n;i++)puts("Impossible");
        return;
    }
    for(int i = 0;i < (1 << dep);i++)l[i] = n + 1;
    for(int sta = 0;sta < (1 << dep);sta += 2){//sta += 2是因为不能用v=V
        for(int i = 0;i < dep;i++){
            if(sta & (1 << i)){
                l[sta] = min(l[sta],L[i][l[sta ^ (1 << i)] - 1]);
                r[sta] = max(r[sta],R[i][r[sta ^ (1 << i)] + 1]);
            }
        }
    }
    for(int i = 1;i <= cntseg;i++){
        // printf("[%d,%d]\n",seg[i].first,seg[i].second);
        for(int sta = 0;sta < (1 << dep);sta += 2){//仍然不让用v=V
            if(seg[i].first - 1 <= r[sta] && l[(1 << dep) - 1 - sta - 1] <= seg[i].second + 1){
                // printf("sta = %d,l[] = %d,r[] = %d\n",sta,l[(1 << dep) - 1 - sta - 1],r[sta]);
                for(int j = seg[i].first;j <= seg[i].second;j++){ans[j] = true;}
                break;
            }
        }
    }
    for(int i = 1;i <= n;i++)puts(ans[i] ? "Possible" : "Impossible");
    return;
}
};
bool edmemory;
signed main(){
    auto stclock = clock();
    Call_me_Eric::main();
    auto edclock = clock();
    cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
    cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
    return 0;
}

标签：02,tmp,ch,int,海亮,dep,maxn,push,杂题
From： https://www.cnblogs.com/Call-me-Eric/p/18016468

相关文章

  • P8786 [蓝桥杯 2022 省 B] 李白打酒加强版
    原题链接题解根据样例，观察到李白总共走\(n+m\)次，每一次不是遇到酒馆就是遇到花故我们可以设\(dp[i][0/1]\)代表第\(i\)次遇到酒馆或花的方案数但是我们发现这样的状态不好转移故我们可以设\(dp[i][0/1][k]\)代表第\(i\)次遇到酒馆或花，还剩下\(k\)斗酒的方案数但......
  • 南外集训 2024.2.15 T3
    题目描述还能有错的？\(T\)组询问，每次给定\(n,k\)，问：如果一个\(2n\)个数的排列所有偶数位置构成的子序列是单调递增的，那么说这个排列是好的。将一个好的排列按照顺序拆分成若干组，每一组个数都是偶数，形成的结构叫做一个城市。一个城市的价值是每个组内部的逆序对个数的乘积。求......
  • 洛谷 P9912 [COCI 2023/2024 #2] Zatopljenje 题解
    首先发现区间中的个数等于\(\texttt{高度大于x的位置的个数}-\texttt{连续两个位置都是大于x的位置的个数}\)。具体令\(H_i=\min(h_i,h_{i+1})(i\in[1,n-1])\)，那么对于一次询问答案\(ans=\sum\limits_{i=l}^{r}[h_i>x]-\sum\limits_{i=l}^{r-1}[H_i>x]\)，其......
  • HGAME2024-WEB WP
    WEEK12048*16直接把前端全部扒下来，自己搭建一个本地的环境，我这里用vscode搭建了一个。然后看下js代码，这里混淆了一堆，实在是难看，就找关键的地方，题目所说的32768找到了上面这个算式，他的结果就算32768，所以我们只需要将这里修改:然后本地起服务，随便玩几下，即可得到flag:Bypas......
  • 【2023年10月多校联训B层联赛2】 珠子 &&【October 2023 Multi-School League B Tier
    第一次用英语，见谅。为什么用英语？```Dev里懒得换输入法。```Link\(\textbf{gxyzoj\#3358}\)\(\textbf{LuoguU406794}\)DescriptionFhas\(n\)beadsarrangedinasequence,eachofwhichhasacolor,andatotalof\(m\)colors,numbered\(1,2,3,\cdots,......
  • 02 \| 为HTTP穿上盔甲：HTTPS
    作者:四火完成时间:总结时间:你好，我是四火。在上一讲中，我介绍了互联网最重要的HTTP协议。可是随着互联网的发展，你会发现HTTP越来越无法满足复杂的需求，比如数据加密传输的安全性需求，再比如服务器消息即时推送的交互模式的需求，而这些不适性是由HTTP的基本特性所造成的......
  • 【无评级杂题】DP/贪心
    题目这题后来看了看网上的思路，发现贪心就能做，亏我还写了个O(2*N)的DP...浪费时间了属于是my-code#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<cstdlib>#include<algorithm>#include<stack>#include<queue>......
  • P8783 [蓝桥杯 2022 省 B] 统计子矩阵
    原题链接题解1.当存在某个矩阵符合题意时，所有小于该矩阵的矩阵都符合题意这是我们就可以想到用双指针code#include<bits/stdc++.h>usingnamespacestd;inta[505][505]={0},sum[505][505]={0};intn,m,k;intcheck(intdown,intright,intup,intleft){returnsu......
  • 20240214打卡
    在Android中，可以通过定义drawable文件来创建自定义的图形、形状、背景等，然后在布局文件中应用这些drawable文件作为背景或者图标。同时，也可以通过定义样式（style）来设定布局以及控件的样式，从而实现一致的外观和风格。下面展示如何定义drawable文件以及样式，并将其应用到布局和控件中......
  • 20240215打卡
    使用MPAndroidChart第三方框架绘制柱状图：1.**在build.gradle文件中添加依赖项**（低版本可以导入jar包）：打开您的项目的build.gradle文件，然后在dependencies部分添加MPAndroidChart的依赖项。```groovydependencies{implementation'com.github.PhilJay:MPAndroidCh......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99