2022 ICPC Gran Premio de Mexico 1ra Fecha(一)

这篇具有很好参考价值的文章主要介绍了2022 ICPC Gran Premio de Mexico 1ra Fecha(一)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

今天大部分时间都花在了上一场沈阳站的L题上了,一个树上背包+容斥原理,看了好久才理解,就不硬敲上了,再想几天在写题解。然后今天自己写了场ICPC墨西哥站的

ICPC Gran Premio de Mexico 1ra Fecha

H. Hog Fencing
签到题,考察了基本不等式这个小知识点。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+5;
const int inf=1e18;
const int mod=1e9+7;
/*
int fac[40];
int qpow(int a,int b){
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}*/
double n;

void solve()
{
    cin>>n;
    double g=(floor(n*n/16));
    int k=(int)sqrt(g);
    if(k*(k+1)<=g)
        cout<<k*(k+1)<<endl;
    else
        cout<<k*k<<endl;
}
signed main()
{
    ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}


I. Isabel’s Divisions
签到题,stoi可将字符串转化为10进制数,真是个好工具。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+5;
const int inf=1e18;
const int mod=1e9+7;
/*
int fac[40];
int qpow(int a,int b){
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}*/
int n;
string s;

void solve()
{
    cin>>s;
    int g=stoi(s);
    n=s.length();s=" "+s;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='0') continue;
        if(g%(s[i]-'0')==0)
            ans++;
    }
    cout<<ans<<endl;
}
signed main()
{
    ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}


J. Jeffrey’s ambition
第一个想法是用二分图去写,看了下时限0.3秒,但还是想用带时间戳的二分图试一下,不出意外,tle了,但是!!!问题出现在longlong上,关掉就可以过。

#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e6+5;
const int inf=1e18;
const int mod=998244353;
/*
int fac[40];
int qpow(int a,int b){
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}*/
int n,m,cnt,head[10005],link[10005],used[10005],ans,now;
struct node
{
    int to,nxt;
}e[N];
void add(int u,int v)
{
    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
int dfs(int u)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(used[v]!=now)
        {
            used[v]=now;
            if(link[v]==-1||dfs(link[v]))
            {
                link[v]=u;return 1;
            }
        }
    }
    return 0;
}
void hungary()
{
    for(int i=0;i<=m;i++) link[i]=-1;
    for(int i=1;i<=n;i++)
    {
        now++;
        if(dfs(i)) ans++;
    }
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int k;cin>>k;
        for(int j=1;j<=k;j++)
        {
            int v;cin>>v;add(i,v);
        }
    }
    hungary();
    int g=0;
    for(int i=1;i<=m;i++)
        if(link[i]==-1) g++;
    cout<<g<<endl;
}
signed main()
{
    ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}


最大流写法:核心在与建图

#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+5;
const int inf=1e18;
const int mod=998244353;
/*
int fac[40];
int qpow(int a,int b){
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}*/
struct edge
{
    int to,c,nxt;
}e[N*10];
int n,m,r[N],c[N],s,t,sum;
int head[N],idx=1;
int d[N],cur[N];
void add(int a,int b,int c)
{
    e[++idx]={b,c,head[a]};
    head[a]=idx;
}
bool bfs()
{
    memset(d,0,sizeof d);
    queue<int>q;
    q.push(s);
    d[s]=1;
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int f=dfs(v,min(mf,e[i].c));
            e[i].c-=f;
            e[i^1].c+=f;
            sum+=f;
            mf-=f;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof head);
        flow+=dfs(s,inf);
    }
    return flow;
}
void solve()
{
    cin>>n>>m;
    s=0,t=n+m+1;
    for(int i=1;i<=n;i++)
        add(0,i,1),add(i,0,0);
    for(int i=1;i<=m;i++)
        add(i+n,t,1),add(t,i+n,0);
    for(int i=1;i<=n;i++)
    {
        int k;cin>>k;
        for(int j=1;j<=k;j++)
        {
            int v;cin>>v;
            add(i,n+v,1),add(n+v,i,0);
        }
    }
    int ans=dinic();
    cout<<m-ans<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}



K. Kilo Waste

一个完全背包,预处理出1~50000中的数字,判断每个数能否到达。
有一点读错了,低了假题,wa了一次。需要注意的是,浪费是指买多了,如果米买少了,不是浪费,此处理解错了。文章来源地址https://www.toymoban.com/news/detail-451925.html

#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+5;
const int inf=1e18;
const int mod=998244353;
/*
int fac[40];
int qpow(int a,int b){
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}*/
int k,p,a[N],f[N];
void solve()
{
    cin>>k>>p;
    int mi=inf;
    for(int i=1;i<=p;i++)
        cin>>a[i],mi=min(mi,a[i]);
    f[0]=1;
    for(int i=1;i<=p;i++)
    {
        for(int j=a[i];j<=50000+mi;j++)
            f[j]=max(f[j],f[j-a[i]]);
    }
    while(k--)
    {
        int x;cin>>x;
        int g=0,s=0;
        while(g<=mi&&f[x+g]==0) g++;
        cout<<g<<endl;
    }
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

到了这里,关于2022 ICPC Gran Premio de Mexico 1ra Fecha(一)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【ICPC2022济南站】【树形dp】【删物品背包dp】C.DFS Order 2

    题目链接:https://codeforces.com/gym/104076/problem/C 简要题意:给定一棵n个点的有根树,对于所有的二元组 ( i , j ) (i,j) ( i , j ) 求这颗树所有可能的dfs序中有多少个dfs序满足第 i i i 个点出现在dfs序第 j j j 个位置。 赛场上假了无数次以后,我终于才理清楚了这题的dp思路。 状态定义

    2024年02月13日
    浏览(31)
  • 【开发工具】今天让你知道什么是Adobe 2022 全家桶系列到底香不香

    🚀 个人主页 极客小俊 ✍🏻 作者简介:web开发者、设计师、技术分享博主 🐋 希望大家多多支持一下, 我们一起进步!😄 🏅 如果文章对你有帮助的话,欢迎评论 💬点赞👍🏻 收藏 📂加关注 概述 : Adobe 2022 全家桶来了,新增超多黑科技! ​ Adobe全家桶 也就是 Adobe系列软件

    2024年02月10日
    浏览(50)
  • 墨西哥小区广播CELL BROADCAST MEXICO 2023

    CB MEXICO 2023 GC Emergency broadcast is requested by Movistar MEXICO in a regulated standard named CBMexico. The implementation of this standar is MANDATORY to get approval. RULE 1: The title of the message must change depending on the channel. (check complete table) Function Primary channels: Title of the messages. Can be turned OFF Level 1 4370, 4383 Mens

    2023年04月21日
    浏览(36)
  • Unity编辑器基础 EditorGUILayout (大部分用法)

    如图 关于效果图最后它的代码我隐藏掉了如何想看看可以自行打开

    2024年02月11日
    浏览(56)
  • 结对编程 --- 大部分程序员喜欢的编程方式

    一、介绍 结对编程起源时间可以追溯到 1990 年代早期。这种编程方法最初由 Jim Highsmith 和 Alistair Cockburn 等人提出。后来,Kent Beck 和 Ward Cunningham 等人将其发展成为一种敏捷开发方法,被称为“极限编程”(Extreme Programming,简称 XP)。结对编程是 XP 中的一种核心实践,也是

    2024年02月06日
    浏览(52)
  • 1200 + AI工具大收录,58个分类,支持大部分行业

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、使用步骤 总结 随着人工智能技术的不断发展,越来越多的AI工具涌现出来,它们在各个领域中得到了广泛的应用。除了常用的文本、图片、视频AI工具,还有普通办公、设计、编程、

    2024年02月16日
    浏览(36)
  • 低代码产品如何分类,大部分人都没有搞清楚

    最近许多技术峰会都出现了低代码这个名词,可以说,低代码是中台之后,又一个热门话题和名词了。 低代码平台是 无需编码或通过少量代码 就可以快速生成应用程序的开发平台。也是一款图形化、拖拉拽方式快速实现企业数字化转型中的创新应用、支持用少量代码扩展实

    2023年04月20日
    浏览(59)
  • 用Matlab实现车牌分割(可识别大部分蓝色、绿色车牌)

          最近学习了数字图像处理的腐蚀、膨胀、闭运算、开运算等内容,于是想进行实践。车牌分割是一个不错的选择,里面涉及到了很多知识点。       这里先简述一下车牌分割的思路和流程(这里以绿色车牌为例): 1.定位绿色车牌区域 2.车牌矫正(如果图像中车牌是倾

    2024年02月12日
    浏览(43)
  • 安全清理大部分的C盘内存(一般10GB以上)

     如果感觉有用请 关注,点赞,收藏!  下次分享更有用的干货~ 欢迎转载,请注明出处! 用360清理发现, windows search日志 占用了70多个G空间,先清除!    该日志文件有撒用呢?  如果没有这个日志文件,我们在文件系统进行搜索的时候就会比较慢了,而且还会出现这样的

    2023年04月15日
    浏览(52)
  • MySQL 字段为 NULL 的5大坑,大部分人踩过

    在验证问题之前,我们先建一张测试表及测试数据。   构建的测试数据,如下图所示:   有了上面的表及数据之后,我们就来看当列中存在 NULL 值时,究竟会导致哪些问题? 我们都知道, count 是用来计数的,当表中某个字段存在 NULL 值时,就会造成 count 计算出来的数据丢

    2024年02月05日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包