文章导读

Jun 28th | Week2 周测总结

DRheEheAM_Garylv229憨毛怪 2026-07-28 22

AI Summary
周测总结：T1因特判错误爆零，T2找连通块最小值，T3二分+LIS求最长子序列。

T1 二进制与一 IV

这道题直接枚举二进制位，容易发现最多枚举 $O(\frac{\log_2x}{2})$ 次。

赛时特判写错直接爆 0 了 ${hanser1_嘤嘤嘤}$

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define szof sizeof
int T;
intl x;
bitset<45> bx;
signed main() {
    // freopen ("test/binary/ex_binary4.in","r",stdin);
    // freopen ("ans.out","w",stdout);
    Cios;
    cin>>T;
    while (T--) {
        cin>>x;
        intl y=0;
        if (x<=1) {
            cout<<0<<"\n";
            continue;
        }
        int cnt=0;
        while (x) {
            bx[cnt]=x%2;
            x>>=1;
            cnt++;
        }
        for (int i=0;i<(cnt>>1);i++) {
            int xi=bx[i],xni=bx[cnt-i-1];
            if (xi!=xni) y+=1<<i;
        }
        cout<<y<<"\n";
    }
    return 0;
}

/*
clang++ -g binary.cpp -o binary -std=c++14 -O2 -Wall
*/

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define szof sizeof
int T;
intl x;
bitset<45> bx;
signed main() {
    // freopen ("test/binary/ex_binary4.in","r",stdin);
    // freopen ("ans.out","w",stdout);
    Cios;
    cin>>T;
    while (T--) {
        cin>>x;
        intl y=0;
        if (x<=1) {
            cout<<0<<"\n";
            continue;
        }
        int cnt=0;
        while (x) {
            bx[cnt]=x%2;
            x>>=1;
            cnt++;
        }
        for (int i=0;i<(cnt>>1);i++) {
            int xi=bx[i],xni=bx[cnt-i-1];
            if (xi!=xni) y+=1<<i;
        }
        cout<<y<<"\n";
    }
    return 0;
}

/*
clang++ -g binary.cpp -o binary -std=c++14 -O2 -Wall
*/

T2 小 L 涂色

考虑每个连通块。

如果为树，发现存在一种构造方式，使得这棵树上仅有最小的点不被染色。显然对于此连通块此方法最优。

如果存在任意一个环，因为对于这个环而言，任意一个点都能被选到。
然后只要我们缩点，将这个连通块缩成一个树，因为至少存在一个环，并且树本身的边能够选 $sz-1$ 个点，所以所有的点一定都能选到。

故我们dfs找环以及连通块最小值即可。

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define szof sizeof
intc N=1e6+10;
vector <int> g[N];
int n,m,a[N],vis[N];
int dfs (int u,int fa) {
    if (vis[u]) return 0;
    vis[u]=1;
    int res=a[u];
    for (int v:g[u]) {
        if (v==fa) continue;
        res=min(res,dfs(v,u));
    }
    return res;
}
signed main() {
    // freopen ("test/color/ex_color5.in","r",stdin);
    // freopen ("ans.out","w",stdout);
    Cios;
    int res=0;
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i=1;i<=n;i++) {
        if (!vis[i]) res+=dfs(i,0);
    }
    cout<<res<<"\n";
    return 0;
}

/*
clang++ -g color.cpp -o color -std=c++14 -O2 -Wall
*/

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define szof sizeof
intc N=1e6+10;
vector <int> g[N];
int n,m,a[N],vis[N];
int dfs (int u,int fa) {
    if (vis[u]) return 0;
    vis[u]=1;
    int res=a[u];
    for (int v:g[u]) {
        if (v==fa) continue;
        res=min(res,dfs(v,u));
    }
    return res;
}
signed main() {
    // freopen ("test/color/ex_color5.in","r",stdin);
    // freopen ("ans.out","w",stdout);
    Cios;
    int res=0;
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i=1;i<=n;i++) {
        if (!vis[i]) res+=dfs(i,0);
    }
    cout<<res<<"\n";
    return 0;
}

/*
clang++ -g color.cpp -o color -std=c++14 -O2 -Wall
*/

T3 删除滚木

考虑二分答案 $x$ 。

移项得到 $|a_{i+1}-a_i|\ge x(p_{i+1}-p_i)$ 。考虑拆绝对值，得到：

\begin{aligned} a_{i+1}-a_i\ge x(p_{i+1}-p_i) \\ a_i-a_{i+1}\ge x(p_{i+1}-p_i) \end{aligned}

之后，我们继续拆项并且移项，得到：

\begin{aligned} a_{i+1}-xp_{i+1} & \ge& a_i-xp_i \\ a_i+xp_i &\ge& a_{i+1}+xp_{i+1} \end{aligned}

于是我们设 $c_i=a_i-xp_i\ , \ d_i=a_i+xp_i$ ，原式转换为：

\begin{aligned} c_{i+1} & \ge& c_i \\ d_i &\ge& d_{i+1} \end{aligned}

并且我们虽然同时有 $p_i< p_{i+1}$ 的需求，但是容易发现以上两个条件是下面这个条件的充分条件。

所以问题转换为满足如上偏序关系的最长子序列长度是否不小于 $n-k$ 。

考虑按照 $c_i$ 排序后对 $d_i$ 做最长不下降子序列dp。

发现朴素最长不下降子序列dp复杂度为 $O(n^2)$ ，考虑二分优化。

记 $d_i$ 为长度为 $i$ 的最长不下降子序列的最小的最后元素。容易发现， $d$ 具有单调性。考虑二分。

总时间复杂度 $O(n\log_2n\log_2V)$

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define double long double
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define szof sizeof
constexpr double eps=1e-9;
intc N=5e5+10;
struct node {
    double c,d;
    bool operator < (const node &p) const {
        if (abs(c-p.c)<=eps) return d<p.d;
        return c>p.c;
    }
}p[N];
int n,k,a[N];
double d[N];
bool solve (double x) {
    for (int i=1;i<=n;i++) p[i]={a[i]-x*i,a[i]+x*i};
    sort(p+1,p+1+n);
    d[1]=p[1].d;
    int len=1;
    for (int i=2;i<=n;i++) {
        if (p[i].d>=d[len]) d[++len]=p[i].d;
        else {
            int j=upper_bound(d+1,d+1+len,p[i].d)-d;
            d[j]=p[i].d;
        }
    }
    return len>=n-k;
}
signed main() {
    Cios;
    cin>>n>>k;
    for (int i=1;i<=n;i++) cin>>a[i];
    double l=0,r=1e9+10,res=0;
    for (int i=1;i<=75;i++) {
        double mid=(l+r)/2;
        if (solve(mid)) res=mid,r=mid;
        else l=mid;
    }
    cout<<fixed<<setprecision(9)<<res<<"\n";
    return 0;
}

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define double long double
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define szof sizeof
constexpr double eps=1e-9;
intc N=5e5+10;
struct node {
    double c,d;
    bool operator < (const node &p) const {
        if (abs(c-p.c)<=eps) return d<p.d;
        return c>p.c;
    }
}p[N];
int n,k,a[N];
double d[N];
bool solve (double x) {
    for (int i=1;i<=n;i++) p[i]={a[i]-x*i,a[i]+x*i};
    sort(p+1,p+1+n);
    d[1]=p[1].d;
    int len=1;
    for (int i=2;i<=n;i++) {
        if (p[i].d>=d[len]) d[++len]=p[i].d;
        else {
            int j=upper_bound(d+1,d+1+len,p[i].d)-d;
            d[j]=p[i].d;
        }
    }
    return len>=n-k;
}
signed main() {
    Cios;
    cin>>n>>k;
    for (int i=1;i<=n;i++) cin>>a[i];
    double l=0,r=1e9+10,res=0;
    for (int i=1;i<=75;i++) {
        double mid=(l+r)/2;
        if (solve(mid)) res=mid,r=mid;
        else l=mid;
    }
    cout<<fixed<<setprecision(9)<<res<<"\n";
    return 0;
}

查看评论列表

暂无评论

发表评论取消回复

访客未填写邮箱

[登录后可以评论]

用户登录

Hello! 欢迎来到DRheEheAM的blog！

加载中

Jun 28th | Week2 周测总结

T1 二进制与一 IV

T2 小 L 涂色

T3 删除滚木

评论（0）

发表评论取消回复

DRheEheAM_Gary Blog

Hello! 欢迎来到DRheEheAM的blog！

加载中

Jun 28th | Week2 周测总结

T1 二进制与一 IV

T2 小 L 涂色

T3 删除滚木

评论（0）

发表评论 取消回复

DRheEheAM_Gary Blog

发表评论取消回复