首页 > 其他分享 >CF1198 Div1做题记录

CF1198 Div1做题记录

时间：2023-05-09 15:25:26浏览次数：50  
标签：ch int void long write 做题 CF1198 Div1 define

A

CF题面

排序，前缀和统计 \(\left[1,i\right]\) 内有多少不同数字，枚举 \(l\)，二分 \(r\)，显然的是 \(l,r\) 等于某一个数字最好，所以可以得到对于每个 \(l\)，最多有多少数字不被修改。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
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=4e5+10;
int n,x,a[N],ans,s[N];
void solve(){
    read(n),read(x);
    x*=8;
    ans=n;
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    sort(a+1,a+n+1);
    s[1]=1;
    for(int i=2;i<=n;i++){
        s[i]=s[i-1];
        if(a[i]!=a[i-1]){
            s[i]++;
        }
    }
    for(int i=1;i<=n;i++){
        int l=i,r=n,pos=n+1;
        while(l<=r){
            int mid=(l+r)>>1;
            double y=ceil(log2(s[mid]-s[i]+1));
            if(y*n<=x){
                pos=mid;
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        ans=min(ans,n-(pos-i+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;
}

B

CF题面

正着模拟不好处理，考虑反过来。

假设当前正在处理第 \(i\) 次操作，令它为操作 \(1\)。显然当后面有操作 \(1\) 时，该操作为无效操作。后面操作 \(2\) 的值的 \(\max\) 值 \(mx\) 会影响当前位置最终赋的值，所以将当前位置的值赋为 \(\max(mx,x)\)，并打上标记。对于到最后还没有被进行过操作 \(1\) 的位置，将值与 \(mx\) 取 \(\max\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
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=2e5+10;
int n,Q,a[N],tag[N];
struct node{
    int opt,p,x;
}q[N];
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    read(Q);
    for(int i=1;i<=Q;i++){
        read(q[i].opt);;
        if(q[i].opt==1){
            read(q[i].p),read(q[i].x);
        }
        else{
            read(q[i].x);
        }
    }
    int mn=0;
    for(int i=Q;i;i--){
        if(q[i].opt==1){
            if(!tag[q[i].p]){
                tag[q[i].p]=1;
                a[q[i].p]=max(q[i].x,mn);
            }
        }
        else{
            mn=max(mn,q[i].x);
        }
    }
    for(int i=1;i<=n;i++){
        if(!tag[i]){
            a[i]=max(a[i],mn);
        }
        write_space(a[i]);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

C

CF题面

对于一条边，如果两个端点都还没选，那么选择这条边和两个端点。被选择的边代表一个匹配，不被选择的点代表一个独立集。根据操作过程可知，其中必有一个大小大于等于 \(n\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
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;
int n,m;
void solve(){
    read(n),read(m);
    set<int>s1,s2;
    for(int i=1;i<=n*3;i++){
        s1.insert(i);
    }
    for(int i=1,u,v;i<=m;i++){
        read(u),read(v);
        if(s1.count(u)&&s1.count(v)){
            s1.erase(u),s1.erase(v);
            s2.insert(i);
        }
    }
    if(s1.size()>=n){
        puts("IndSet");
        int s=0;
        while(s<n){
            write_space(*s1.begin());
            s1.erase(s1.begin());
            s++;
        }
    }
    else{
        puts("Matching");
        int s=0;
        while(s<n){
            write_space(*s2.begin());
            s2.erase(s2.begin());
            s++;
        }
    }
    putchar('\n');
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

D

CF题面

记 \(f_{xl,yl,xr,yr}\) 表示左上角为 \((xl,yl)\)，右下角为 \((xr,yr)\) 的矩形的答案，记忆化搜索即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
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=60,inf=0x3f3f3f3f;
int n,f[N][N][N][N];
char ch[N][N];
int dfs(int xl,int yl,int xr,int yr){
    if(f[xl][yl][xr][yr]!=inf){
        return f[xl][yl][xr][yr];
    }
    if(xl==xr&&yl==yr){
        f[xl][yl][xr][yr]=(ch[xl][yl]=='#');
        return f[xl][yl][xr][yr];
    }
    for(int i=xl;i<xr;i++){
        f[xl][yl][xr][yr]=min(f[xl][yl][xr][yr],dfs(xl,yl,i,yr)+dfs(i+1,yl,xr,yr));
    }
    for(int i=yl;i<yr;i++){
        f[xl][yl][xr][yr]=min(f[xl][yl][xr][yr],dfs(xl,yl,xr,i)+dfs(xl,i+1,xr,yr));
    }
    f[xl][yl][xr][yr]=min(f[xl][yl][xr][yr],max(xr-xl+1,yr-yl+1));
    return f[xl][yl][xr][yr];
}
void solve(){
    memset(f,inf,sizeof(f));
    read(n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ch[i][j]=getchar();
            while(ch[i][j]!='.'&&ch[i][j]!='#'){
                ch[i][j]=getchar();
            }
        }
    }
    write_endl(dfs(1,1,n,n));
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

E

CF题面

第一下看错了题，以为和D是一样的题意，只是放大了数据，仔细一看发现贡献从矩形两边的最大值变成了最小值。这样，每次选择的矩形变成了 \(1\times \infty\) 或 \(\infty\times 1\)。题意变成了可以选择一些行和一些列，覆盖到所有矩形，并使所选行和列的数量之和最少。对于一个矩形，它要么选择所有的行，要么选择所有的列，将行和列之间连边，就变成了二分图最大匹配问题了。

但这不够，考虑离散化，将矩形的右边界和下边界拓宽一格，这时矩形被表示为了 \([xl,xr),[yl,yr)\)。令离散化后的直线 \(x_i,y_i\) 表示 \([x_i,x_{i+1}),[y_i,y_{i+1})\) 这个区间。很容易发现这和原来的二分图匹配仍然等价，因为一个区间里直线要么全选，要么全不选。将原来在一个矩形里的两条线连边，跑网络流即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
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=210,inf=1e9,M=2e5+10;
int x[N],y[N],n,m,cntx,cnty;
struct node{
    int xl,xr,yl,yr;
}mat[N];
int head[N],S,T,tot=1,dep[N],cur[N];
struct edge{
    int v,w,nxt;
}e[M];
void add(int u,int v,int w){
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
bool bfs(int S,int T){
    for(int i=1;i<=T;i++){
        dep[i]=0;
    }
    queue<int>q;
    q.push(S);
    dep[S]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(w&&!dep[v]){
                dep[v]=dep[u]+1;
                if(v==T){
                    return 1;
                }
                q.push(v);
            }
        }
    }
    return 0;
}
int dfs(int u,int flow,int T){
    if(u==T){
        return flow;
    }
    int s=0;
    for(int i=cur[u];i;i=e[i].nxt){
        int v=e[i].v,w=e[i].w;
        if(w&&dep[v]==dep[u]+1){
            int res=dfs(v,min(flow,w),T);
            e[i].w-=res;
            e[i^1].w+=res;
            s+=res;
            flow-=res;
        }
        if(!flow){
            break;
        }
    }
    if(!s){
        dep[u]=0;
    }
    return s;
}
int dinic(int S,int T){
    int sum=0;
    while(bfs(S,T)){
        for(int i=1;i<=T;i++){
            cur[i]=head[i];
        }
        sum+=dfs(S,inf,T);
    }
    return sum;
}
void solve(){
    read(n),read(m);
    for(int i=1;i<=m;i++){
        read(mat[i].xl),read(mat[i].yl),read(mat[i].xr),read(mat[i].yr);
        mat[i].xr++,mat[i].yr++;
        x[++cntx]=mat[i].xl,x[++cntx]=mat[i].xr;
        y[++cnty]=mat[i].yl,y[++cnty]=mat[i].yr;
    }
    sort(x+1,x+cntx+1);
    sort(y+1,y+cnty+1);
    cntx=unique(x+1,x+cntx+1)-x-1;
    cnty=unique(y+1,y+cnty+1)-y-1;
    for(int i=1;i<=m;i++){
        mat[i].xl=lower_bound(x+1,x+cntx+1,mat[i].xl)-x;
        mat[i].xr=lower_bound(x+1,x+cntx+1,mat[i].xr)-x;
        mat[i].yl=lower_bound(y+1,y+cnty+1,mat[i].yl)-y;
        mat[i].yr=lower_bound(y+1,y+cnty+1,mat[i].yr)-y;
        for(int j=mat[i].xl;j<mat[i].xr;j++){
            for(int k=mat[i].yl;k<mat[i].yr;k++){
                add(j,k+cntx,inf);
                add(k+cntx,j,0);
            }
        }
    }
    S=cntx+cnty+1,T=cntx+cnty+2;
    for(int i=1;i<cntx;i++){
        add(S,i,x[i+1]-x[i]);
        add(i,S,0);
    }
    for(int i=1;i<cnty;i++){
        add(i+cntx,T,y[i+1]-y[i]);
        add(T,i+cntx,0);
    }
    write_endl(dinic(S,T));
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

F

CF题面

令两组的 \(\gcd\) 分别为 \(g_1,g_2\)。
先假设已知放数的顺序，怎么放是最优的。有一个贪心的想法，假如 \(g_1\) 是 \(a_i\) 的因子，那么放到第一组里肯定不会是 \(g_1\) 变小，所以将 \(a_i\) 放到第二组后肯定不劣于放到第一组。
所以我们随机放数顺序，当随机一定多组后还不行，则答案为NO。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
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=1e5+10;
int n,a[N],id[N],g[2],ans[N];
bool work(){
    ans[id[1]]=1;
    g[1]=a[id[1]];
    ans[id[2]]=2;
    g[2]=a[id[2]];
    for(int i=3;i<=n;i++){
        if(a[id[i]]%g[1]){
            ans[id[i]]=1;
            g[1]=__gcd(a[id[i]],g[1]);
        }
        else{
            ans[id[i]]=2;
            g[2]=__gcd(a[id[i]],g[2]);
        }
    }
    return (g[1]==1)&&(g[2]==1);
}
void solve(){
    srand((unsigned)time(NULL));
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        id[i]=i;
    }
    int T=min(500,10000000/n/2);
    while(T--){
        random_shuffle(id+1,id+n+1);
        if(work()){
            puts("YES");
            for(int i=1;i<=n;i++){
                write_space(ans[i]);
            }
            return;
        }
    }
    puts("NO");
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

标签：ch,int,void,long,write,做题,CF1198,Div1,define
From： https://www.cnblogs.com/luoshen0/p/17372662.html

相关文章

  • 2023.4 做题笔记
    出于一些原因，只有4.21往后的题。LOJ6481VisualPython++考虑贪心。非常容易想到，从左往右扫，每次扫到一个右下角时就匹配一个在它上面但是高度差最小的左上角，如果有多个同一高度的可以不用考虑顺序，因为边界重合的情况是不合法的。对于一种匹配方案，怎么判断它合不合法呢？我们同......
  • codeforces div1A
    A.CircularLocalMiniMax题目翻译：给我们一个数组（循环的也就是1和n是相邻的），我们可以对数组进行任意调序，对于每个数b[i]要求满足b[i]<b[i-1]&&b[i]<b[i+1]或者满足b[i]>b[i-1]&&b[i]>b[i+1]。如果存在就输出yes并且输出构造的序列，否则输出no。思路：我们考虑......
  • Luogu P1298 最接近的分数 做题记录
    算是水紫，不过也学到一些有用的东西。题意给定正小数\(N\)。求分子不大于\(n\)，分母不大于\(m\)的分数\(\dfrac{n}{m}\)，使得\(\dfrac{n}{m}\)的值与\(N\)最接近（这里的最接近指的是\(|\dfrac{n}{m}-N|\)最小）。分析首先，大部分人都可以想到一个暴力：枚举\(i\in[1,......
  • 【做题笔记】洛谷 P7987 [USACO21DEC] Paired Up G
    在我的个人博客获得更好的阅读体验Problem洛谷P7987[USACO21DEC]PairedUpG题目大意：有\(n\)个点，其中第\(i\)个点位置为\(x_i\)，权值为\(y_i\)。若两个点\(i,j\)满足\(|x_i-x_j|\lek\)，则这两个点之间有一条边。求一个匹配，在满足其为极大匹配的情况下匹配点的......
  • 做题整理 4.25
    字符串P3538[POI2012]OKR-AHorriblePoem给定字符串，多次询问其子串的最小循环节长度。由于循环节长度\(len\)一定是子串长度的约数，我们可以不断试除\(len\)的最小质因子，并判断是否合法，更新\(ans\)的最小值。线性筛预处理所有数（\(\le5\times10^5\)）的最小质因子；判断是......
  • CF1479 Div1 VP记录
    战况：别的不说，这个B1WA3发是真的精髓。A略B我们设此时在第一队队尾的为las0，在第二队队尾的为las1，要放的数为x。先考虑B1：显然有：如果las0等于x，放在第二队，如果las1等于x，放在第一队。考虑两边都不同的情况，我们想要这个x后面尽快跟上一个不同的数，依此来创造新的......
  • vulstack2 靶场做题笔记
    环境配置DCIP：10.10.10.10OS：Windows2012WEB默认初始密码登陆不进去，利用de1ay/1qaz@WSX登陆IP1：10.10.10.80IP2：192.168.111.80OS：Windows2008pcIP1：10.10.10.201IP2：192.168.111.201OS：Windows7攻击机kaliip:192.168.111.130内网网段:10.10.10.0/24......
  • 往年 NOI 做题记录
    一个新坑，先把真题都刷一下大概就知道会考什么和难度怎么样了。2013向量内积给定一个\(n\)个\(m\)维向量，求出一组不同的向量\(p,q\)使其内积（点乘）在模\(k\)意义下为\(0\)。\(k=2,1\len\le2\times10^4,1\lem\le100\)或\(k=3,1\len\le10^5,1\lem\le30.\)......
  • 蓝桥杯历年省赛真题做题记录（A组）（2022年第十三届）
    D题：选数异或考虑到异或的一个很好的性质，$A^B=x$等价于$A^x=B$。用$flag$数组记录一下数字$A[i]$是否出现过，出现过则$flag[A[i]]不等于0$。类似DP中分配任务模型的思想，这样我们只需要对每次$L,R$询问，判断之中有没有这样一对$(l,r)$数对使得$A[l]^A[r]==x$。因此设$d[i]$......
  • 2023/4 做题记录 #1
    2023/4/5P5601小D与笔试https://www.luogu.com.cn/problem/P5601读题\(1\)min,码代码\(1\)min,调代码\(7\)min。注意读入时如果发现了答案不要break掉。#include<bits/stdc++.h>usingnamespacestd;intn,q;map<string,string>x;intmain(){ scanf("%d%d"......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99