首页 > 其他分享 >#18搞OI不要会证明

#18搞OI不要会证明

时间：2023-11-06 17:12:42浏览次数：31  
标签：ch OI int 18 void long 证明 write define

Karen and Cards

题面

设符合条件的三元组为 \((x,y,z)\)。枚举 \(x\)，可以将 \(n\) 个三元组分为两类：\(a_i\ge x\) 和 \(a_i<x\)。对于 \(i\in [1,n],a_i\ge x\)，需要满足的条件为 \(b_i<y\) 且 \(c_i<z\)；对于 \(i\in [1,n],a_i<x\)，需要满足的条件为 \(b_i<y\) 或者 \(c_i<z\)。

令 \(smx_y\) 表示 \(b_i\ge y\) 三元组中最大的 \(c_i\)，\(mxc\) 表示 \(a_i\ge x\) 三元组中最大的 \(c_i\)，\(z\) 的方案数为 \(r-\max(smax_j,mxc)\)，因为对于 \(a_i\ge x\) 和 \(b_i\ge y\) 的三元组都需要满足 \(z>c_i\)。令 \(mxb\) 表示 \(a_i\ge x\) 的三元组中最大的 \(b_i\)，枚举 \(y\in(mxb,q]\)，对于每一个 \((x,y)\) 二元组计算答案。因为要求 \(mxb,mxc\)，所以倒序枚举 \(x\)，复杂度 \(O(n^2)\)。

考虑优化贡献过程，将 \(\max(smx_j,mxc)\) 拆开，因为 \(smx_j\) 不升，所以会存在一个 \(k\)，当 \(j\ge k,smx_j\le mxc;j<k,smx_j>mxc\)。维护 \(smx_j\) 的前缀和即可。复杂度 \(O(n)\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?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+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=5e5+10;
int n,p,q,r,mx[N],sum[N],ans;
vector<pii>d[N];
void solve(){
    read(n),read(p),read(q),read(r);
    for(int i=1;i<=n;i++){
        int a,b,c;
        read(a),read(b),read(c);
        a=min(a,p);
        b=min(b,q);
        c=min(c,r);
        d[a].pb(mp(b,c));
        mx[b]=max(mx[b],c);
    }
    for(int i=q;i;i--){
        mx[i]=max(mx[i+1],mx[i]);
    }
    for(int i=1;i<=q;i++){
        sum[i]=sum[i-1]+mx[i];
    }
    int mxb=0,mxc=0,k=q+1;
    for(int a=p;a;a--){
        for(int i=0;i<d[a].size();i++){
            int b=d[a][i].first,c=d[a][i].second;
            mxb=max(mxb,b);
            mxc=max(mxc,c);
            while(k>mxb+1&&mx[k-1]<mxc){
                k--;
            }
        }
        k=max(k,mxb+1);
        ans+=(r-mxc)*(q-k+1)+r*(k-mxb-1)-sum[k-1]+sum[mxb];
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

Foo Fighters

题面

因为负数变正数和正数变负数是等价的，所以若所有数的和为负数，将所有数变为相反数。根据与的性质，会影响结果的只有小于权值为 \(1\) 的最高的位置，可以从小往大考虑每一位选或不选，如果当前位为最高位 \(1\) 的数的权值和为负数，则将所有当前位为 \(1\) 的数的权值取反。因为每一位贪心变小，所以最后结果一定符号会变。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?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+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=3e5+10,Lg=62;
int n,val[N],s[N],mx[N];
int ans=0;
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(val[i]),read(s[i]);
        ans+=val[i];
        for(int j=Lg;j>=0;j--){
            if(s[i]>>j&1){
                mx[i]=j;
                break;
            }
        }
    }
    if(ans<0){
        for(int i=1;i<=n;i++){
            val[i]*=-1;
        }
    }
    ans=0;
    for(int i=0;i<=Lg;i++){
        int res=0;
        for(int j=1;j<=n;j++){
            if((s[j]>>i&1ll)&&(mx[j]==i)){
                res+=val[j];
            }
        }
        if(res>0){
            ans|=1ll<<i;
            for(int j=1;j<=n;j++){
                if(s[j]>>i&1ll){
                    val[j]*=-1;
                }
            }
        }
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

Adam and Tree

题面

对于一个点直接暴力往上跳的时候维护当前点到子树内所有叶子的最大值和次大值，如果更新到的点不能更新则不继续更新了。复杂度为 \(O(n\log n)\)

复杂度证明：假定 \(ans_i\) 表示最终的结果，那么更新次数为 \(\sum\limits_{i=1}^n ans_i\)。将树重链剖分后，并按照剖分结果染色，因为一个点经过的重链条数为 \(O(\log n)\)，所以 \(ans_i\) 的级别是 \(O(\log n)\)，复杂度 \(O(n\log n)\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?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+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e6+10;
int n,fa[N],mx[N],maxi[N],now[N];
bool update(int pos){
    if(mx[fa[pos]]<now[pos]){
        maxi[fa[pos]]=mx[fa[pos]];
        mx[fa[pos]]=now[pos];
    }
    else if(maxi[fa[pos]]<now[pos]){
        maxi[fa[pos]]=now[pos];
    }
    int ans=max(mx[fa[pos]],maxi[fa[pos]]+1);
    if(ans==now[fa[pos]]){
        return 0;
    }
    now[fa[pos]]=ans;
    return 1;
}
void solve(){
    read(n);
    for(int i=2;i<=n+1;i++){
        read(fa[i]);
        now[i]=1;
        int pos=i;
        while(fa[pos]){
            if(!update(pos)){
                break;
            }
            pos=fa[pos];
        }
        write_space(mx[1]);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

Preorder Test

题面

很容易想到换根dp，但实际上不用换根。

二分答案，将权值大于二分的答案的点权值赋为 \(1\)，否则赋为 \(0\)。令 \(f_i\) 表示子树 \(i\) 内选择可以选到的最大的长度。转移 \(f_u=\sum\limits_{f_v=siz_v}f_v+mx_u\)，其中 \(mx_u\) 表示 \(u\) 子树内最大的满足 \(f_v\not=siz_v\) 的 \(f_v\)。我们还可以在剩下的部分中选出一棵子树，连到当前的根，令其的 \(f\) 值为 \(nmx_u\)，答案为 \(\max\{f_u+nmx_u\}\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?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+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10;
int n,a[N],k,val[N],flag[N],f[N],siz[N],ans,rt,rtt;
vector<int>e[N];
void dfs(int u,int fa,int x){
    siz[u]=1;
    int mx=0,maxi=0;
    f[u]=1;
    for(auto v:e[u]){
        if(v==fa){
            continue;
        }
        dfs(v,u,x);
        siz[u]+=siz[v];
        if(f[v]==siz[v]){
            f[u]+=f[v];
            continue;
        }
        if(mx<f[v]){
            maxi=mx;
            mx=f[v];
        }
        else if(maxi<f[v]){
            maxi=f[v];
        }
    }
    if(a[u]<val[x]){
        f[u]=0;
    }
    else{
        f[u]+=mx;
    }
    ans=max(ans,f[u]+maxi);
}
bool check(int x){
    // ans=0;
    // dfs(n,0,x);
    // if(ans>=k){
    //     return 1;
    // }
    // ans=0;
    // dfs(1,0,x);
    // if(ans>=k){
    //     return 1;
    // }
    // ans=0;
    // dfs(rt,0,x);
    // if(ans>=k){
    //     return 1;
    // }
    ans=0;
    dfs(rtt,0,x);
    if(ans>=k){
        return 1;
    }
    return 0;
}
void solve(){
    read(n),read(k);
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(a[i]>a[rt]){
            rt=i;
        }
        if(!rtt||a[i]<a[rtt]){
            rtt=i;
        }
        val[i]=a[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        read(u),read(v);
        e[u].pb(v);
        e[v].pb(u);
    }
    sort(val+1,val+n+1);
    int l=1,r=n,res=1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            l=mid+1;
            res=mid;
        }
        else{
            r=mid-1;
        }
    }
    write_endl(val[res]);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

因为未知原因，该份代码的根只能选到权值最小的点，选 \(1\) 会 wa on 25，如果有知道什么原因的读者可以讲一下。

Maximum Subsequence Value

题面

结论题，选三个是最优的。

证明：首先三个以下肯定不优于三个，此时答案仍为权值或，显然不优于三个。对于四个，令三个的答案为 \(ans\)，若想答案不降，则每个答案的二进制位的 \(1\) 的个数至少为 \(2\)，而增加一个数是怎么也不可能让一个位置 \(1\) 的个数增加 \(2\) 个，所以答案不增，更多同理。

枚举三个数，求三个数或的最大值。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?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+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
int n,a[1010];
void solve(){
    read(n);
    int ans=0;
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                ans=max(ans,a[i]|a[j]|a[k]);
            }
        }
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

最小度限制生成树

题面

令 \(val_u\) 表示 \((u,s)\) 这条边边权最小的边的边权，先忽略所有与 \(s\) 的连边，剩下部分肯定是求最小生成树。但是求最小生成树时，所有边都向 \(val_u\) 小的点合并。

加上与 \(s\) 的连边后，一个连通块中必须要至少与 \(s\) 连一条边，这条边的边权必然是连通块中所有点与 \(s\) 的连边中边权最小的。如果存在连通块无法连边或者连通块数大于 \(k\) 则无解。

增加 \(s\) 的度数，贪心考虑将一条边换为一条与 \(s\) 的相连的边，令 \(lst_u\) 表示 \(u\) 这个点在求最小生成树时合并的边的边权。最后优先修改 \(val_u-lst_u\) 小的点即可，正确性证明可以看 Alex_Wei的题解。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?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+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e6+10,inf=1e18;
int n,m,fa[N],val[N],cnt,s,k;
int getfa(int x){
    if(fa[x]!=x){
        fa[x]=getfa(fa[x]);
    }
    return fa[x];
}
struct edge{
    int u,v,w;
    bool operator <(const edge &rhs)const{
        return w<rhs.w;
    }
}e[N];
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    read(n),read(m),read(s),read(k);
    memset(val,0x7f,sizeof(val));
    for(int i=1;i<=m;i++){
        int u,v,w;
        read(u),read(v),read(w);
        if(u==s){
            val[v]=min(val[v],w);
        }
        else if(v==s){
            val[u]=min(val[u],w);
        }
        else{
            e[++cnt]={u,v,w};
        }
    }
    sort(e+1,e+cnt+1);
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    vector<int>delta;
    int ans=0;
    for(int i=1;i<=cnt;i++){
        int u=getfa(e[i].u),v=getfa(e[i].v);
        if(u==v){
            continue;
        }
        if(val[u]>val[v]){
            swap(u,v);
        }
        fa[v]=u;
        ans+=e[i].w;
        if(val[v]<inf){
            delta.pb(val[v]-e[i].w);
        }
    }
    int deg=0;
    for(int i=1;i<=n;i++){
        if(fa[i]!=i||i==s){
            continue;
        }
        deg++;
        if(val[i]>inf){
            puts("Impossible");
            return 0;
        }
        ans+=val[i];
    }
    if(deg>k||deg+delta.size()<k){
        puts("Impossible");
        return 0;
    }
    sort(delta.begin(),delta.end());
    for(int i=0;i<k-deg;i++){
        ans+=delta[i];
    }
    write_endl(ans);
    // cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
    return 0;
}

标签：ch,OI,int,18,void,long,证明,write,define
From： https://www.cnblogs.com/luoshen0/p/17803597.html

相关文章

  • 执行以下代码，alert的输出结果为hello189
    执行以下代码，alert的输出结果为hello189var msg='hello';for (var i=0; i<10; i++){    var msg='hello'+i*2+i;}alert(msg)在for循环内使用var声明的变量msg并不是局部变量，而是全局变量。在for循环中，每循环一次，变量msg的值就被覆盖一次，最终msg......
  • CF1861F Four Suits【网络流，贪心】
    有\(n\)个人，\(4\)种不同的卡牌，初始第\(i\)个人有\(a_{i,j}\)张第\(j\)种卡牌。你是局外人，手里第\(j\)种卡牌有\(b_j\)个，你现在要把你的卡牌分给这\(n\)个人，使得分完之后每个人手里的卡牌总数相等，保证有解。第\(i\)个人最终的分数是手里每种卡牌的数量的最大值......
  • P3202 [HNOI2009] 通往城堡之路
    考虑将每个支撑点都先设成其下限高度，即\(h_i\getsh_1-(i-1)\timesd\)，这样就只会提高某些支撑点的高度。显然每次提高的是一个后缀。提高某个后缀的贡献是当前高度低于原先高度的支撑点数量减去当前高度不低于原先高度的支撑点数量。选择贡献最大的后缀直到最后一个支撑点的高......
  • Metasploit windows 调试环境搭建
    Metasploitwindows调试环境搭建安装ruby首先确定metasploit的ruby版本metasploit-framework/.ruby-version3.0.5在https://rubyinstaller.org/downloads/archives/下载对应版本的Ruby+DevkitInstallers（x64），默认配置安装即可。输入ruby-v查看是否安装成功安装gem......
  • Halcon使用ROI进行区域内较暗区域面积筛选
    dev_close_window() read_image(Image,'C:/Users/PC/Desktop/kakou/7-1.jpg')get_image_size(Image,Width,Height);dev_open_window(0,0,512,512,'black',WindowHandle)rgb1_to_gray(Image,GrayImage)gen_rectangle1(GrayImage,100,1500,......
  • Metasploit渗透测试框架的基本使用
    一、Metasploit渗透测试框架介绍（1）基础库metasploit基础库文件位于源码根目录路径下的libraries目录中，包括Rex,framework-core和framework-base三部分。Rex是整个框架所依赖的最基础的一些组件，如包装的网络套接字、网络应用协议客户端与服务端实现、日志子系统、渗透攻击支持例......
  • 【洛谷 P1046】[NOIP2005 普及组] 陶陶摘苹果 题解（比较）
    [NOIP2005普及组]陶陶摘苹果题目描述陶陶家的院子里有一棵苹果树，每到秋天树上就会结出个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。现在已知个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的......
  • JUC并发编程学习（十三）ForkJoin
    ForkJoin什么是ForkJoinForkJoin在JDK1.7，并发执行任务！大数据量时提高效率。大数据：MapReduce（把大任务拆分成小任务）ForkJoin特点：工作窃取为什么可以取窃取其他线程的任务呢？因为这里面维护的都是双端队列（即队列的两端都可以取元素）ForkJoin操作在java.util.concurrent......
  • android 系统修改签名：以android13为例
    android系统修改签名：以android13为例修改签名方式修改签名文件使用签名工具（development/tools/）修改签名文件development/tools/make_keyplatform'/C=CN/ST=ShenZhen/L=NanShan/O=Tripod/OU=WCD/CN=demo/[email protected]'  注意：以上两张图片表......
  • [Leetcode] 0118. 杨辉三角
    118.杨辉三角题目描述给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。 示例1:输入:numRows=5输出:[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2:输入:numRows=1输出:[[1]] 提......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99