Codeforces Round #576 (Div. 1)

A.MP3

题面:

给你n数,然后让你乱搞…

分析:

乱搞

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=4e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,k,x[N],ha[N],ans,zz;
int sum[N],num[N];
signed main()
{
    read(n),read(k);
    for(int i=1;i<=n;i++) read(x[i]);
    int ned=(k*8)/n;
    if(ned>21) return 0*puts("0");
    ned=(1<<ned);
    sort(x+1,x+n+1);
    for(int i=1;i<=n;i++) ha[i]=x[i];
    int len=unique(x+1,x+n+1)-x-1;
    for(int i=1;i<=n;i++) ha[i]=lower_bound(x+1,x+len+1,ha[i])-x;
//  for(int i=1;i<=n;i++) printf("%d ",ha[i]);puts("");
    if(len<=ned) return 0*puts("0");
    for(int i=1;i<=n;i++)
        num[ha[i]]++;
    for(int i=1;i<=len;i++)
        sum[i]=sum[i-1]+num[i];
    ans=zz=sum[len]-sum[ned];
    for(int i=ned+1;i<=n;i++)
    {
        zz+=num[i-ned]-num[i];
        ans=min(ans,zz);
    }
    printf("%d\n",ans);
    return 0;
}
 

B.Welfare State

题面:

给你n个数然后给你一些操作
1. 单点修改
2. 把所有小于k个数字变成k

分析:

直接上线段树

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,tree[N<<3],tag[N<<3],q;
void pushdown(int now)
{
    if(!tag[now]) return ;
    tree[now<<1]=max(tree[now<<1],tag[now]);
    tree[now<<1|1]=max(tree[now<<1|1],tag[now]);
    tag[now<<1]=max(tag[now<<1],tag[now]);
    tag[now<<1|1]=max(tag[now<<1|1],tag[now]);
    tag[now]=0;
}
void change(int now,int l,int r,int q,int k)
{
    if(l==r) 
    {
        tag[now]=0;
        tree[now]=k;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(now);
    if(q<=mid) change(now<<1,l,mid,q,k);
    else change(now<<1|1,mid+1,r,q,k);
    return;
}
void change(int now,int l,int r,int ql,int qr,int k)
{
    if(ql<=l&&r<=qr)
    {
        tree[now]=max(tree[now],k);
        tag[now]=max(tag[now],k);
        return ;
    }
    if(ql>r||qr<l) return;
    int mid=(l+r)>>1;
    pushdown(now);
    change(now<<1,l,mid,ql,qr,k);
    change(now<<1|1,mid+1,r,ql,qr,k);
}
void print(int now,int l,int r)
{
    if(l==r) 
    {
        printf("%d ",tree[now]);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(now);
    print(now<<1,l,mid);
    print(now<<1|1,mid+1,r);
}
signed main()
{
    read(n);
    for(int i=1,u;i<=n;i++)
    {
        read(u);
        change(1,1,n,i,u);
    }
    read(q);
    for(int cas=1;cas<=q;cas++)
    {
        int opt,x,y;
        read(opt);
        if(opt==1)
        {
            read(x),read(y);
            change(1,1,n,x,y);
        }
        else 
        {
            read(x);
            change(1,1,n,1,n,x);
        }
    }
    print(1,1,n);
    return 0;
}

C. Matching vs Independent Set

题面:

给你3\times n个点和m条边,让你找有n个点或者n条边的独立集…

分析:

我们直接贪心往一个边独立集里面加点,加完以后发现剩在外面的点是一个独立集,两者之中一定有一个大小大于n的输出那个就好了…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=5e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int T,n,m;
int vis[N],num;
vector<int> vec;
int main()
{
    read(T);
    for(int cas=1;cas<=T;cas++)
    {
        read(n),read(m);
        num=0;
        for(int i=1;i<=n*3;i++) vis[i]=0;
        vec.clear();
        for(int i=1,u,v;i<=m;i++)
        {
            read(u),read(v);
            if(!vis[u]&&!vis[v])
                vec.push_back(i),vis[u]=vis[v]=1;
        }
        if(vec.size()>=n)
        {
            puts("Matching");
            for(int i=0;i<n;i++)
                printf("%d ",vec[i]);
        }
        else 
        {
            puts("IndSet");
            for(int i=1;i<=n*3;i++)
            {
                if(!vis[i])
                    printf("%d ",i),num++;
                if(num==n)
                    break;
            }
        }
        puts("");
    }
    return 0;
}

D. Rectangle Painting 1

题面:

给你一个正方形上面有一些黑点,然后让你用一些矩阵覆盖所有点,每个矩阵的代价是长宽中的较大值…让你输出最小代价…

分析:

已知我们取一个矩形没有取一个正方形来的优
取相邻的正方形没有直接取一个正方形来的优
那么也就是说我们如果取了好多小正方形那么他们一定不想临.
那么我们可以美剧枚举正方形之间的分界线,然后记忆化搜索…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,f[55][55][55][55];
char s[55][55];
int sum[55][55];
int num(int a,int b,int x,int y) {return sum[x][y]-sum[a-1][y]-sum[x][b-1]+sum[a-1][b-1];}
int solve(int a,int b,int x,int y)
{
    int &ret=f[a][b][x][y];
    if(ret) return ret;
    else ret=max(x-a+1,y-b+1);
    if(!num(a,b,x,y))
        return ret=0;
    for(int i=a;i<x;i++)
        ret=min(ret,solve(a,b,i,y)+solve(i+1,b,x,y));
    for(int i=b;i<y;i++)
        ret=min(ret,solve(a,b,x,i)+solve(a,i+1,x,y));
    return ret;
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
        for(int j=1;j<=n;j++) 
            sum[i][j]=sum[i][j-1]+(s[i][j]=='#');
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            sum[i][j]+=sum[i-1][j];
    printf("%d\n",solve(1,1,n,n));
    return 0;
}

E. Rectangle Painting 2

题面:

在一个n\times n的超大矩阵上面有一些矩阵,矩阵覆盖的点都是黑点,然后你用一些矩阵去覆盖这些点,然后代价是长宽里小的值,让你输出最小代价…

分析:

已知我们每次要么选一行或者一列取覆盖,那么我们哈希玩以后直接上最小割,一个格子要么被行覆盖,要么被列覆盖…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,s,t;
struct Edge{int next,to,flow;} edge[N];
int head[500],cnt=1,dep[500];
void add(int from,int to,int flow) { edge[++cnt]={head[from],to,flow}; head[from]=cnt;}
void insert(int from,int to,int flow) { add(from,to,flow); add(to,from,0);}
struct Matrix{int a,b,x,y;} M[55];
vector<int> vec1,vec2;
queue<int> q;
bool bfs()
{
    memset(dep,-1,sizeof(dep));
    q.push(s);dep[s]=0;
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=edge[i].next)
        {
            int to=edge[i].to;
            if(!edge[i].flow) continue;
            if(dep[to]==-1)
                dep[to]=dep[now]+1,q.push(to);
        }
    }
    return dep[t]!=-1;
}
int dfs(int now,int flow)
{
    if(now==t||!flow) return flow;
    int used=0;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(dep[to]==dep[now]+1&&edge[i].flow)
        {
            int flag=dfs(to,min(flow-used,edge[i].flow));
            if(flag>0)
            {
                edge[i].flow-=flag;
                edge[i^1].flow+=flag;
                used+=flag;
            }
        }
    }
    return used;
}
int dinic(int ret=0)
{
    while(bfs())
        ret+=dfs(s,inf);
    return ret;
}
int Map[500][500];
int main()
{
    read(n),read(m);
    s=0,t=410;
    for(int i=1;i<=m;i++)
    {
        read(M[i].a),read(M[i].b),read(M[i].x),read(M[i].y);
        M[i].a--,M[i].b--,
        vec1.push_back(M[i].a);
        vec1.push_back(M[i].x);
        vec2.push_back(M[i].b);
        vec2.push_back(M[i].y);   
    }
    sort(vec1.begin(),vec1.end());
    int len=unique(vec1.begin(),vec1.end())-vec1.begin()-1;
    while(vec1.size()>len) vec1.pop_back();
    for(int i=0;i<len;i++)
    // {
        // cout<<vec1[i]<<endl;
        insert(s,i+1,vec1[i+1]-vec1[i]);
        // cout<<s<<"->"<<i+1<<" "<<vec1[i+1]-vec1[i]<<endl;
    // }
    sort(vec2.begin(),vec2.end());
    len=unique(vec2.begin(),vec2.end())-vec2.begin()-1;
    while(vec2.size()>len) vec2.pop_back();
    for(int i=0;i<len;i++)
    // {
        insert(i+201,t,vec2[i+1]-vec2[i]);
    //     cout<<i+101<<"->"<<t<<" "<<vec2[i+1]-vec2[i]<<endl;
    // }
    for(int i=1;i<=m;i++)
    {
        int a=lower_bound(vec1.begin(),vec1.end(),M[i].a)-vec1.begin()+1;
        int x=lower_bound(vec1.begin(),vec1.end(),M[i].x)-vec1.begin()+1;
        int b=lower_bound(vec2.begin(),vec2.end(),M[i].b)-vec2.begin()+1;
        int y=lower_bound(vec2.begin(),vec2.end(),M[i].y)-vec2.begin()+1;
        for(int j=a;j<x;j++)
            for(int k=b;k<y;k++)
                // insert(j,k+200,inf);
                Map[j][k+200]=1;
    }
    for(int i=1;i<=410;i++)
        for(int j=1;j<=410;j++)
            if(Map[i][j])
                insert(i,j,inf);
    // cout<<cnt<<endl;
    printf("%d\n",dinic());
    return 0;
}

F. GCD Groups 2

分析:

我们现在有n个数,然后你要把他们分成两组,让两组的GCD都是1…

分析:

不知道为什么对的随机贪心…
每次随机一个点,如果加到第一堆里可以让GCD减小,就加第一堆,否则第二堆…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,x[N],id[N],Map[N],check,times;
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(x[i]);
    for(int i=1;i<=n;i++) id[i]=i;
    while(times<=100)
    {
        random_shuffle(id+1,id+n+1);
        int p1=-1,p2=-1;
        for(int i=1;i<=n;i++)
        {
            if(p1==-1||(p1!=-1&&__gcd(p1,x[id[i]])<p1))
            {
                Map[id[i]]=1;
                if(p1==-1) p1=x[id[i]];
                else p1=__gcd(p1,x[id[i]]);
            }
            else 
            {
                if(p2==-1)
                    p2=x[id[i]];
                else p2=__gcd(p2,x[id[i]]);
                Map[id[i]]=2;
            }
        }
        if(p1==1&&p2==1)
        {
            check=1;
            break;
        }
        times++;
    }
    if(check==1)
    {
        puts("YES");
        for(int i=1;i<=n;i++) printf("%d ",Map[i]); puts("");
        return 0;
    }
    puts("NO");
    return 0;
}

“`

发表评论

电子邮件地址不会被公开。 必填项已用*标注