首页 > 其他分享 >[ICPC2024 Xi‘an I] ICPC2024 邀请赛西安站(7/8/13)

[ICPC2024 Xi‘an I] ICPC2024 邀请赛西安站(7/8/13)

时间:2024-06-03 15:30:05浏览次数:25  
标签:13 Xi ICPC2024 int rep typedef long include define

心得

[ICPC2024 Xi'an I] ICPC2024 邀请赛西安站重现赛 - 比赛详情 - 洛谷

7表示赛时ac了7个,8表示含补题总共ac数,13表示题目总数

题目

M. Chained Lights

打表,发现只有k=1是YES

//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e6+10;
int t,n,k,fac[N],sum[N],light[N];
void press(int x)
{
    light[x]^=1;
    for (int y=x+x;y<=n;y+=x) press(y);
}
int main(){
    sci(t);
    while(t--){
        sci(n),sci(k);
        puts(k==1?"YES":"NO");
    }
    return 0;
}

J. Triangle

数三角形,手玩发现一些规律,

比如:n=3,m=9实际是15,然后发现和gcd有关

//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e6+10;
int a,b;
ll gcd(ll a,ll b){
    return !b?a:gcd(b,a%b);
}
int main(){
    sci(a),sci(b);
    // if(a==b){
    //     printf("%lld\n",1ll*a*(a+1)/2);
    // }
    // else{
    ll v=gcd(a,b);
    ptlle((1ll*a*b-1ll*v*(a/v)*(b/v))/2+1ll*((a/v)*(b/v)+1)/2*v);
    //}
    return 0;
}
/*
3 9 = 15
*/

D. Make Them Straight

枚举k,根据ai-i*k确定能在同一个序列里的子序列,子序列里的是不改的

首项得是正的,后面i*k>1e6说明一定要改

剪枝一下复杂度是可接受的O(klogn)

//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=2e5+10;
int n,a[N],b[N];
map<ll,ll>mp;
ll sum,ans;
int main(){
    sci(n);
    rep(i,0,n-1)sci(a[i]);
    rep(i,0,n-1){
        sci(b[i]);
        sum+=b[i];
    }
    ans=sum;
    rep(k,0,1000000){
        mp.clear();
        ll res=0;
        rep(i,0,n-1){
            ll v=a[i]-1ll*i*k;
            if(1ll*i*k>1000000)break;
            if(v<0)continue;
            mp[v]+=b[i];
            res=max(res,mp[v]);
            //if(mp[v]==9)printf("i:%d v:%lld mp:%lld\n",i,v,mp[v]);
        }
        ans=min(ans,sum-res);
    }
    ptlle(ans);
    return 0;
}
/*
3 9 = 15
*/

L. Rubbish Sorting

二进制子集枚举一下,大概sosdp的思想,因为|s|<=5

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=2e5+10,M=2e7+10,INF=0x3f3f3f3f;
int q,n,op,x,y,bs[8];
char s[N];
int val[M],now=INF;
int main(){
    memset(val,INF,sizeof val);
    bs[0]=1;
    rep(i,1,6)bs[i]=bs[i-1]*28;
    sci(q);
    while(q--){
        sci(op);
        scanf("%s",s);
        n=strlen(s);
        if(op==1){
            sci(y);
            int w=0;
            rep(i,0,n-1){
                int v=s[i]-'a'+1;
                w+=v*bs[i];
            }
            val[w]=min(val[w],y);
            now=min(now,y);
            rep(p,1,n){
                int up=(1<<p)-1;
                rep(i,0,up-1){
                    int w=0;
                    rep(j,0,p-1){
                        int z=i>>j&1,v=0;
                        if(z)v=27;
                        else v=(s[j]-'a'+1);
                        w+=v*bs[j];
                    }
                    val[w]=min(val[w],y);
                }
            }
        }
        else{
            int w=0;
            rep(i,0,n-1){
                int v=s[i]-'a'+1;
                w+=v*bs[i];
            }
            if(val[w]!=INF){
                pte(val[w]);
                continue;
            }
            vector<int>mn(n+1,INF);
            mn[n]=now;
            rep(p,1,n){
                int up=(1<<p)-1;
                rep(i,0,up-1){
                    int w=0,tot=0;
                    rep(j,0,p-1){
                        int z=i>>j&1,v=0;
                        if(z)v=27,tot++;
                        else v=(s[j]-'a'+1);
                        w+=v*bs[j];
                    }
                    mn[tot+n-p]=min(mn[tot+n-p],val[w]);
                }
            }
            rep(i,0,n){
                if(mn[i]!=INF){
                    //printf("i:%d mn:%d\n",i,mn[i]);
                    pte(mn[i]);
                    break;
                }
            }
        }
    }
    return 0;
}
/*
3 9 = 15
*/

B. Turn Off The Lights(构造)

最终一定是和某一列完全相同/完全相反的,

不妨和第i列完全相同,全是01011,那么再把这三列的1按列取消掉就可以了

所以枚举和哪列相同,bitset加速统计,复杂度O(n^3/64)

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e3+10;
int n,k,a[N][N],sum[N];
bitset<1005>b[2][N];
bool flip[N];
bool ck(int i){
    int sum=0;
    rep(j,1,n){
        if(j==i)continue;
        int s1=(b[1][i]^b[0][j]).count(),s2=(b[0][i]^b[0][j]).count();
        if(s1<s2)flip[j]=1;
        else flip[j]=0;
        sum+=min(s1,s2);
    }
    return sum<=k;
}
void out(int i){
    //printf("i:%d\n",i);
    vector<P>ans;
    rep(j,1,n){
        if(j==i)continue;
        if(flip[j])ans.pb(P(j,0));
        rep(x,1,n){
            if(flip[j]){
                if(a[j][x]!=(a[i][x]^1))ans.pb(P(j,x));
            }
            else{
                if(a[j][x]!=a[i][x])ans.pb(P(j,x));
            }
        }
    }
    rep(x,1,n){
        if(a[i][x])ans.pb(P(0,x));
    }
    pte(SZ(ans));
    for(auto x:ans){
        printf("%d %d\n",x.fi,x.se);
    }
}
int main(){
    sci(n),sci(k);
    rep(i,1,n){
        rep(j,1,n){
            sci(a[i][j]);
            if(a[i][j])b[0][i].set(j);
            else b[1][i].set(j);
        }
    }
    rep(i,1,n){
        rep(x,0,1){
            if(ck(i)){
                out(i);
                return 0;
            }
        }
    }
    puts("-1");
    return 0;
}
/*
3 9 = 15
*/

F. XOR Game(博弈)

先从大到小考虑ai=1的值,z是0的个数算最小的数

因为操作一次就可以获得收益/ban掉对应收益,所以alice和bob会先抢这部分

剩下的局面,尽可能避免2的出现, 全是2的情况,谁先操作谁就输了,

所以判一下剩下局面的奇偶性,奇数alice全取,偶数bob全ban

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e5+10;
int k,z,a[N],b[N],c;
int main(){
    sci(k);sci(z);
    rep(i,0,k-1){
        sci(a[i]);
    }
    per(i,k-1,0){
        if(a[i]==1){
            c++;
            if(c&1)b[i]=1;
            a[i]=0;
        }
    }
    per(i,k-1,0){
        if(a[i]&1)c++;
    }
    c+=(z&1);
    per(i,k-1,0){
        if(!a[i])continue;
        if(c&1)b[i]=1;
    }
    per(i,k-1,0){
        printf("%1d",b[i]);
    }
    puts("");
    return 0;
}
/*
3 9 = 15
*/

I. Smart Quality Inspector(状压dp+区间dp)

避免后效性,肯定是从大到小考虑max值,

被前面的最大值覆盖了的区间,再选最大值时就没有贡献了

dp[S]表示当前最大值已经覆盖的状态是S时的最大代价和

b[i][l][r]表示区间包含第i位且被[l,r]完整包含的区间的数量

新增一位时,往左往右拓展0的区域找到最左最右,这一段的b值对应的区间都是有贡献的

复杂度O(n^5+n*2^n)

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=25,M=(1<<20)+5,INF=0x3f3f3f3f;
int n,k,m,l,r,a[N][N],b[N][N][N],dp[M];
void upd(int &x,int y){
    x=min(x,y);
}
int main(){
    sci(n),sci(k),sci(m);
    rep(i,1,m){
        sci(l),sci(r);
        a[l][r]++;
    }
    rep(i,1,n){
        rep(l,1,i){
            rep(r,i,n){
                rep(x,l,i){
                    rep(y,i,r){
                        b[i][l][r]+=a[x][y];
                    }
                }
            }
        }
    }
    memset(dp,INF,sizeof dp);
    dp[0]=0;
    int up=(1<<n)-1;
    rep(i,0,up){
        vector<int>pre(n,-1),suf(n,n);
        int now=-1,bit=0;
        rep(j,0,n-1){
            int v=i>>j&1;
            if(v==1)now=j,bit++;
            else pre[j]=now+1;
        }
        now=n;
        per(j,n-1,0){
            int v=i>>j&1;
            if(v==1)now=j;
            else{
                suf[j]=now-1;
                int x=j+1,y=pre[j]+1,z=suf[j]+1;
                upd(dp[i|(1<<j)],dp[i]+b[x][y][z]*max(k-bit,0));
            }
        }
    }
    pte(dp[up]);
    return 0;
}

赛后补题

G. The Last Cumulonimbus Cloud(拓扑排序好题)

任意非空子图都有一个度不超过10的点=可以把度>10的点的贡献都归到这些不超过10的点上

拓扑排序每删掉一个度数不足10的点就会多出一个不足10的点

最后图可以化成一个联通且每个点出度均不超过10的dag

u加的时候把贡献推到u的下游

u算的时候上游已经推给过u,只需要再加上u的所有下游的贡献

标签:13,Xi,ICPC2024,int,rep,typedef,long,include,define
From: https://blog.csdn.net/Code92007/article/details/139412630

相关文章

  • MySQL从入门到高级 --- 12.事务 && 13.锁机制 && 14.日志
    文章目录第十二章&&第十三章&&第十四章:12.事务12.1特性12.2隔离级别13.锁机制13.1各存储引擎对锁的支持状况:13.2锁特性13.3MyISAM表锁13.3.1加表锁13.4InnoDB行锁13.4.1行锁特点13.4.2行锁模式14.日志14.1错误日志14.2二进制日志14.2.1日志格式14.3......
  • ESXi常用Esxcli的指令
    前言使用Esxcli命令可获取有关vSAN的信息,以及对您的vSAN环境进行故障排除。可用命令如下:命令描述esxclivsannetworklist确认哪些VMkernel适配器可用于vSAN通信。esxclivsanstoragelist列出由vSAN声明的存储磁盘。esxclivsanclusterget......
  • ZCMU-1133
    emm就直接看的前辈的了。唉#include<stdio.h>#include<string.h>#include<algorithm>//我不成熟的想法是两成遍历//但感觉会时间超限,但没有先想到深度搜索usingnamespacestd;intn,t;intnum[101];//存放输入情况intr[101];//记录可能情况boolflag;v......
  • 1319:【例6.1】排队接水
    题目网址:信息学奥赛一本通(C++版)在线评测系统题目介绍:1319:【例6.1】排队接水时间限制:1000ms      内存限制:65536KB提交数:45180   通过数: 22285【题目描述】有n�个人在一个水龙头前排队接水,假如每个人接水的时间为Ti��,请编程找出这n�个人排队的一种顺......
  • 《计算机网络微课堂》实验13 静态路由配置错误导致的路由环路问题
    下面我们来进行一个仿真实验,本仿真实验的目的在于验证静态路由配置错误所导致的路由环路问题。我已经在软件中构建好了我们理论课讲解时所用到的网络拓扑,并且给网络中的各设备都配置了相应的IP地址和地址掩码。对于网络中的各个主机,我还为他们指定了默认网关,对于网络中的各个......
  • ProgGen: Generating Named Entity Recognition Datasets Step by step with Self Ref
    本文是LLM系列文章,针对《ProgGen:GeneratingNamedEntityRecognitionDatasetsStepbystepwithSelfReflexiveLargeLanguageModels》的翻译。ProgGen:使用自反射大型语言模型逐步生成命名实体识别数据集摘要1引言2相关工作3方法4实验5结论6局限性......
  • C语言练习题之——从简单到烧脑(13)(每日两道)
    打印爱心1.1:普通输出爱心#include<stdio.h>intmain(){ printf("******************\n");//7(代表边上的空格) printf("******************************\n");//4 printf("************************************\n&quo......
  • CSP历年复赛题-P1981 [NOIP2013 普及组] 表达式求值
    原题链接:https://www.luogu.com.cn/problem/P1981题意解读:中缀表达式求值,只有+,*,没有括号,保留后4位。解题思路:中缀表达式求值的典型应用,采用两个栈:符号栈、数字栈,对于没有括号的情况,只需要如下步骤:1、遍历表达式每一个字符2、如果遇到数字,则持续提取数字,保存整数到数字栈3、......
  • 【并发程序设计】13.信号机制
    13.信号机制概念:信号机制是Unix、类Unix以及其他POSIX兼容的操作系统中的一种进程间通讯方式,它允许进程在发生特定事件时接收通知。信号机制是操作系统中的一个重要概念,它提供了一种异步的通知机制,用于在进程之间传递消息。信号可以被看作是一种软中断,它们可以在任何时间......
  • 二维码生成器 ZXing.Net 组件应用
    c#二维码生成器(ZXing.Net)实现安装组件CodeusingSunny.UI;usingSystem;usingSystem.Collections.Generic;usingSystem.Drawing;usingSystem.Drawing.Imaging;usingSystem.Windows.Forms;usingZXing;usingZXing.Common;usingZXing.QrCode.Internal;namespace......