2019ICPC南昌

2019ICPC南昌 重现


C. And and Pair

题意:

给定一个很大的数n的二进制表示s(也就是01串),计算满足条件的数对<i,j>的数量
条件:
0<=j<=i<=n
i&n=i
i&j=0

其中&符号表示位运算与
答案对1e9+7取模

数据范围:|s|<=1e5

解法:

很容易看出可以用数位dp来解
当s[i]=1的时候,i可以为0或者1,i=0时j=0/1,i=1时j=0
当s[i]=0的时候,i只能为0,i=0时j=0/1
当存在最高位限制的时候,i=0时j=0,此时j不能为1
详见代码

需要注意的点是平常数位dp是从高位到低位dp
但是给定的01串高位在左边,低位在右边,需要改一下dp的顺序,或者将串翻转一下。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=1e5+5;
const int mod=1e9+7;
char s[maxm];
int d[maxm];
int dfs(int len,int limit){//limit是i的limit,j不需要limit
    if(!len)return 1;
    if(!limit&&d[len]!=-1)return d[len];
    int ans=0;
    if(s[len]==1){//i可0可1
        if(limit){//10+limit,00+!limit,不能01
            ans+=dfs(len-1,1)+dfs(len-1,0);
        }else{//10,00,01
            ans+=dfs(len-1,0)*3;
        }
    }else{//i只能0
        if(limit){//00+limit,不能01
            ans+=dfs(len-1,1);
        }else{//00,01
            ans+=dfs(len-1,0)*2;
        }
    }
    ans%=mod;
    if(!limit)d[len]=ans;
    return ans;
}
int solve(){
    int len=strlen(s+1);
    reverse(s+1,s+1+len);//翻转一下,否则dp中串的访问顺序就反了
    for(int i=1;i<=len;i++){//init
        d[i]=-1;
        s[i]-='0';
    }
    return dfs(len,1);
}
signed main(){
    int T;cin>>T;
    while(T--){
        scanf("%s",s+1);
        int ans=solve();
        cout<<ans<<endl;
    }
    return 0;
}

E. Bob’s Problem

题意:

给定n个点m条边的无向图,和一个整数k
每条边是黑色或者白色,且每条边有边权
现在你必须在图中选择一些边,最多选择k条白边,
要求选择的边能使得图连通
问选择出的边的最大边权和是多少
如果无解则输出-1

数据范围:n<=5e4,m<=5e5

解法:

要使得边权和最大,因为黑边没有数量限制所以全选,并查集维护一下连通性,把白边存下来

然后白边按边权从大到小排序
遍历白边,如果白边两端不连通则选定且k-=1,否则先不选
如果k次机会选完了还是不连通则无解
如果连通之后k还有剩余,则优先把剩下的边权大的选下来

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=1e6+5;
struct E{
    int x,y,w;
    friend bool operator<(E a,E b){
        return a.w>b.w;
    }
};
vector<E>temp;
int mark[maxm];//表示被选定的白边
int pre[maxm];
int n,m,k;
int ffind(int x){
    return pre[x]==x?x:pre[x]=ffind(pre[x]);
}
signed main(){
    int T;cin>>T;
    while(T--){
        cin>>n>>m>>k;
        temp.clear();
        for(int i=1;i<=n;i++){
            pre[i]=i;
        }
        int ans=0;
        for(int i=1;i<=m;i++){
            int x,y,w,c;cin>>x>>y>>w>>c;
            if(c==0){//黑边全选
                ans+=w;
                pre[ffind(x)]=ffind(y);//并查集维护图的连通性
            }else{//白边存下来
                temp.push_back({x,y,w});
            }
        }
        sort(temp.begin(),temp.end());
        int len=temp.size();
        for(int i=0;i<len;i++){
            mark[i]=0;
        }
        for(int i=0;i<len&&k;i++){
            int x=ffind(temp[i].x);
            int y=ffind(temp[i].y);
            if(x!=y){
                pre[x]=y;
                ans+=temp[i].w;
                mark[i]=1;
                k--;
            }
        }
        if(k){//如果k还有剩余,则贪心的把边权大的未选的选下
            for(int i=0;i<len&&k;i++){
                if(!mark[i]){
                    ans+=temp[i].w;
                    k--;
                }
            }
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(pre[i]==i){
                cnt++;
                if(cnt>1)break;
            }
        }
        if(cnt!=1){
            puts("-1");
        }else{
            cout<<ans<<endl;
        }
    }
    return 0;
}

G. Eating Plan

题意:

给定长度为n的排列a,其中a[i]=k表示第i个盘子中的食物重量为(k的阶乘)

你的胃很奇怪,当吃了重量为x的食物的时候,剩下的食物质量为x%998857459

现在有m次询问,每次询问给出一个整数k,(保证1<=k<998857459)
你只能吃一个连续区间[L,R]的盘子中的食物,问使得胃中剩下的食物大于等于k的最短区间长度是多少

数据范围:n<=1e5,m<=1e4

解法:

一个简单的想法是枚举区间,计算区间和(用前缀和做),然后对同一区间长度能保留的最大重量取max,
如果存在区间长度为len1,最多保留v1,区间长度len2,最多保留v2,
如果len1<len2且v1>=v2,那么区间len1肯定更优,跳过区间len2
从1到n枚举区间长度,同时记录前缀max,将没有被跳过的区间存到数组e中,显然e[]的区间长度len和值v都是单调递增的
离线记录询问,对询问按k值从小到大排序,用离线算法计算答案就行了(具体操作见代码)

但是n的大小最大1e5,枚举区间不可行
这题的关键信息是模数998857459是一个合数(如果没发现的话,这题直接凉了)
因此当fac[x]中的x到达一定大小的时候会变为0,那么fac[x+1]=fac[x]*(x+1)也会变成0
也就是说x到达某个数之后,后面的阶乘取模之后都是0,打表发现当x>=2803的时候,都是0
那么枚举区间端点的时候,没必要枚举0的位置,
因为给定的a[]是一个排列,那么非0的位置最多2802个,这个大小可以直接O(n2)枚举
解决了区间枚举问题之后,其他的按照前面说的做法做就行了

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=1e5+5;
const int mod=998857459;
int fac[maxm];//阶乘
int sum[maxm];//a[i]前缀和
int pos[maxm];//存非0的位置
int ma[maxm];//ma[i]表示模mod意义下,长度为i的区间能吃出的最大值
int ans[maxm];
int a[maxm];
int n,m;
struct Q{//离线存询问
    int k,id;
    friend bool operator<(Q a,Q b){
        return a.k<b.k;
    }
}q[maxm];
struct E{//存区间
    int v,len;
}e[maxm];
signed main(){
    fac[0]=1;
    for(int i=1;i<maxm;i++){//fac[>=2803]=0
        fac[i]=fac[i-1]*i%mod;
    }
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=fac[a[i]];
        if(a[i]){
            pos[++cnt]=i;
        }
    }
    for(int i=1;i<=n;i++){//前缀和
        sum[i]=(sum[i-1]+a[i])%mod;
    }
    for(int i=1;i<=cnt;i++){//cnt<=2802
        for(int j=i;j<=cnt;j++){
            int t=((sum[pos[j]]-sum[pos[i]-1])%mod+mod)%mod;//[pos[i],pos[j]]的和%mod
            int len=pos[j]-pos[i]+1;
            ma[len]=max(ma[len],t);//更新长度为len的区间所能吃到的最大值
        }
    }
    //预处理最优区间
    int lene=0;
    int maa=0;
    for(int i=1;i<=n;i++){
        if(ma[i]<=maa)continue;//如果ma[i]<=maa,那么选长度小的区间更优,因此直接跳过
        maa=ma[i];
        e[++lene]={ma[i],i};
    }
    for(int i=1;i<=m;i++){//离线存询问
        int k;cin>>k;
        q[i]={k,i};
    }
    sort(q+1,q+1+m);//对询问按k从小到大排序
    //
    int k=1;
    for(int i=1;i<=m;i++){
        while(k<=lene&&e[k].v<q[i].k){
            k++;
        }
        if(k>lene){
            ans[q[i].id]=-1;
        }else{
            ans[q[i].id]=e[k].len;
        }
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}

L.Who is the Champion

题意:

签到题,告诉你球赛的计分规则,要求计算出球赛的冠军,模拟一下就行了

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=1e3+5;
int a[maxm][maxm];
int dif[maxm];
int p[maxm];
signed main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i][j]>a[j][i]){
                p[i]+=3;
            }else if(a[i][j]==a[j][i]){
                p[i]++;
                p[j]++;
            }else{
                p[j]+=3;
            }
            dif[i]+=a[i][j]-a[j][i];
            dif[j]+=a[j][i]-a[i][j];
        }
    }
    int pma=-1;
    for(int i=1;i<=n;i++){
        pma=max(pma,p[i]);
    }
    int ma=-1;
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(p[i]==pma){
            if(ma==-1){
                ma=i;
                cnt=1;
            }else{
                if(dif[i]>dif[ma]){
                    ma=i;
                    cnt=1;
                }else if(dif[i]==dif[ma]){
                    cnt++;
                }
            }
        }
    }
    if(cnt!=1||ma==-1){
        puts("play-offs");
    }else{
        cout<<ma<<endl;
    }
    return 0;
}

热门文章

暂无图片
编程学习 ·

PAT 1161 Merging Linked Lists

原题链接:暂无 关键词:链表 Given two singly linked lists L 1 =a 1 →a 2 →…→a n−1 →a n L1=a1→a2→…→an−1→an and L 2 =b 1 →b 2 →…→b m−1 →b m L2=b1→b2→…→bm−1→bm . If n≥2m n≥2m , you are supposed to reverse and merge the shorter one i…
暂无图片
编程学习 ·

仿element自定义进度条

由于element官网进度条是按百分比显示的 可选值只有0-100;如果是一个量值的显示,如图这样的用element进度条实现起来就比较麻烦,所以就有了下边的自定义进度条 github: https://github.com/Hans-326/ProgressBar
暂无图片
编程学习 ·

自定义注解 通过AOP切面的方式实现所有业务实力类的变更记录

自定义注解 通过AOP切面的方式实现所有业务实力类的变更记录需求:重点难点整体思路:app_changelog 存放变更记录的表自定义注解changeLog自定义注解FieldDescpojo类切面方法切面关键在于通过反射获取对应的类、方法和属性、属性值 需求: 实力类的属性值在修改时变化了 ,…
暂无图片
编程学习 ·

C++单例设计

单例设计模式的单例类主要用于配置文件读写, 整个项目用一个对象就够了。创建单例类class MyClass {private:MyClass(){}; //构造函数私有化private:static MyClass* m_instance;public:static MyClass* GetInstance(){if(m_instance == NULL){m_instance = new MyClass();stat…
暂无图片
编程学习 ·

Hadoop----HDFS的API操作

HDFS文件上传 1、源代码` @Test public void testCopyFromLocalFile() throws IOException,InterruptedException,URISyntaxException{//1、获取文件系统Configuration configuration = new Configuration();configuration.set("dfs.replication","2");//副…
暂无图片
编程学习 ·

AttributeError: ‘list‘ object has no attribute ‘value‘

AttributeError: ‘list’ object has no attribute ‘value’需要注意self.session.run输出的格式,如下代码会报错 precise_summary = self.session.run([ts.precise_summary],{ts.x: xs, ts.y: ys}) writer.add_summary(precise_summary, epoch)AttributeError: ‘list’ ob…
暂无图片
编程学习 ·

Android Studio报错Error while merging dex archives

今天在编译代码时候出现这个报错,首先谈几句关于学习,其实刚开始新手时候什么都不懂,一遇到错误就慌得很,其实严格意义上这些所谓的报错都不是本身的错误,都只是我们不会用或者用错了导致的问题,就好像买了一辆车去水上开,结果沉了,还质问厂家问什么沉了。 所以这种所谓…
暂无图片
编程学习 ·

QT的::和:记录

******1.:一般指继承. Class 派生类 : 基类 (1)表示结构体内 位域的定义(即该变量占几个bit空间) (2)构造函du数后面的冒号起分割作用,是类给成员变量赋值的方法,初始化列表,更适用于成员变量的常量const型。 (3)public:和private:后面的冒号,表示后面定义的所有成员都是…
暂无图片
编程学习 ·

VS不能使用scanf函数的解决方法

在VS创建一个c++项目之后,即使已经#include<stdio.h>仍然不能scanf,会出现下面的情况解决方法:1、点击项目->项目属性,点开属性页面2、点击C/C++ -> 预处理器 -> 预处理器定义 -> 点击右侧的下拉列表 -> 点击下拉列表里的<编辑>3、在预处理器定…
暂无图片
编程学习 ·

新能源汽车车载智能终端T-BOX

新能源汽车车载智能终端T-BOX技术解决方案包括:用户端 + 运营后台系统 + 车辆网平台 + 车载终端等总体架构:“端+网”解决方案智能信TBOX终端硬件,TBOX终端与汽车共享、网约及分时租赁商业应用相结合,实现远程开锁,GPS追踪、动力控制管理、闪灯鸣笛寻车等功能。同时,提供…
暂无图片
编程学习 ·

一文详解:二叉搜索树

这几天一直在刷题,每天都觉得时间不够用,心态上会有波动。争取在9月之前刷到300道题,调整心态,继续前行。 今天我们来复习一下二叉排序树(BST),首先我们先看下定义: 一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点…
暂无图片
编程学习 ·

使用python下载文件

使用requestspython 3.71 下载指定文件 import requestsurl = https://images.jjxsw.la/images/mijjxswcom.gif req = requests.get(url) with open(a.swf, wb) as code:code.write(req.content)
暂无图片
编程学习 ·

jdbcTemplate.queryForObject 没查到抛异常

当结果集合的size为0或者大于1时,就会抛出异常。 解决方法有两个: (1)通过修改数据库:删除数据库中对应名称(column)相同的记录,留下只剩"1"条。 (2)通过更换方法:使用query方法返回list对象(该方法能返回所有查询记录)
暂无图片
编程学习 ·

01:渗透测试及Kali Linux介绍

文章目录kali linux 渗透测试介绍安全问题的根源安全目标渗透测试渗透测试标准渗透测试项目渗透测试误区KALIKALI LINUX 策略 kali linux 渗透测试 介绍 安全问题的根源分层思想的优劣OSI采用了分层的结构化技术,共分七层,物理层、数据链路层、网络层、传输层、会话层、表示层…
暂无图片
编程学习 ·

TabRow + TextView导致文字显示不完全

我们在使用表格布局TabLayout时会出一个现象:TextView显示文字时当超过屏幕换行是最后一个文字显示不完全,这个时候我们可以将Textview改成如下布局即可将android:layout_width="wrap_content"改为android:layout_width="0dp" 同时添加该属性android:lay…
暂无图片
编程学习 ·

rem移动端布局

rem移动端布局: 1、rem是CSS3新增的相对长度单位,是指相对于根元素html的font-size计算值的大小。简单可理解为屏幕宽度的百分比。 2、什么是dpr? dpr是屏幕像素密码比 计算:dpr=液晶屏幕px尺寸 / 物理尺寸(量多少就是多少) 常用的dpr有:dpr = 2,dpr=3 window.devicePi…
暂无图片
编程学习 ·

评估指标:精确率,召回率,F1_score,ROC,AUC

分类算法评估标准详解 分类准确度并不能够评估所有的场景,展示的结果也比较片面,这时候就需要其他的评估方法来进行测量评估。 所以接下来介绍一些其他的评估标准,将从以下5个方面来介绍: 混淆矩阵 精准率和召回率 F1 Score ROC曲线 AUC 一、混淆矩阵(Confusion Matrix) …
暂无图片
编程学习 ·

Java中的递归

Java中的递归(涉及到面试)举个例子: package com.wang.digui; /* 递归*/ public class Demo {public static void main(String[] args) {int calcetor = calcetor(3);System.out.println(calcetor);}//算阶乘的public static int calcetor(int n){if (n == 1){return 1;}els…
暂无图片
编程学习 ·

微信小程序 列表渲染多层嵌套循环

前言入门教程之列表渲染多层嵌套循环,目前官方的文档里,主要是一维数组列表渲染的案例,还是比较简单单一,给刚入门的童鞋还是无从入手的感觉。<view wx:for="{{items}}">{{index}}: {{item.message}} </view>123 还有一个九九乘法表把数据直接写到wx…
暂无图片
编程学习 ·

JAVA中集合的迭代/遍历方法iterator()

JAVA中集合的迭代/遍历方法以下讲解的遍历方式/迭代方式,是所有Collection通用的一种方式在Map集合中不能使用,在所有的Collection以及子类中使用第一步:创建迭代器对象: Iterator it = e.iterator();第二步:通过以上获取的迭代器对象开始迭代/遍历集合 以下两个方法为迭代…