Codeforces Round #716 (Div. 2)_n×k的二进制隶属矩阵-程序员宅基地

技术标签: CodeForces  算法  

Codeforces Round #716 (Div. 2)

A.Perfectly Imperfect Array

题意:有一个长度为n的数组,问能不能找一个子数组,使得他们的乘积不是一个平方数

思路:平方数*平方数=平方数,因此要找到一个乘积不是平方数的子数组,需要找一个不是平方的数。

代码:

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

void solve()
{
    
    int n;
    scanf("%d", &n);
    int flag = 0;
    for(int i = 1; i <= n; i++)
    {
    
        int num;
        scanf("%d", &num);
        if((int)(sqrt(num)) * (int)(sqrt(num)) != num)
        {
    
            flag = 1;
        }
    }

    if(flag)
        printf("YES\n");
    else
        printf("NO\n");

}

int main()
{
    
    int t;
    scanf("%d", &t);
    while(t--)
        solve();
    return 0;
}
/*
2
3
1 5 4
2
100 10000

*/

B. AND 0, Sum Big

题意:给你n,k,计算出满足下面3个条件的长度为n的数组有多少个

1.所有元素的范围取值为0~2k-1

2.所有元素进行and操作之后为0

3.元素的和尽可能大

思路:每个数的范围从0~2k-1 这意味着这个数可以用k位2进制来表达的。有n个数,那就可以用n*k的二进制矩阵来表示所有的数。要使所有元素进行and操作之后为0,还要满足和尽可能大,这就是说每个二进制位有且仅有一位为0,最高位的n个数中只有一个为0,其他都为1,最低位的n个数中只有一个为0,其他为1。那么答案就为n^k

代码:

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll mod = 1e9 + 7;

void solve()
{
    
    int n, k;
    scanf("%d%d", &n, &k);
    ll ans = 1ll;
    for(int i = 1; i <= k; i++){
    
        ans = ans * n % mod;
    }
    printf("%lld\n", ans);
}

int main()
{
    
    int t;
    scanf("%d", &t);
    while(t--)
        solve();
    return 0;
}

C.Product 1 Modulo N

题意:给你一个数n,请你在[1,2,…,n-1]中找一个最长的子序列,使得积模n等于1

思路:显然当无论n怎么取,1%n = 1.我们知道gcd(ai, n) = gcd(ai, n % ai),如n与ai不互质,那么乘积模n不可能为1,所以我们先取所有不与n互质的元素,当然n-1要特判,若前面的已经选中的数能被n模完为1就不要了。

代码:

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    
    int n;
    scanf("%d", &n);

    ll product = 1ll;
    queue<int>q;
    for(int i = 1; i < n - 1; i++){
    
        if(__gcd(i, n) == 1){
    
            q.push(i);
            product = product * i % n;
        }
    }

    if(product * (n - 1) % n == 1ll)
        q.push(n-1);
    printf("%d\n", q.size());

    while(!q.empty()){
    
        printf("%d%c", q.front(), " \n"[q.size()==1]);
        q.pop();
    }

    return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Steve_Liu12399/article/details/113193559

智能推荐

#list 标签获取下标_<#list>-程序员宅基地

文章浏览阅读5.3k次。<#list>标签<#list>能是CMS里面的标签。<#list>获取下标,怎么获取下标 ${c_index}获取下标 例子: [#list tag_list as c] ======> ${c_index} [#list tag_list as a] ======> ${a_index}代码例子:<div class="tabs fn-clear"> [@cms_conten_<#list>

Python可视化matplotlib&seborn14-普通热力图heatmap_python matplotlib 热力图浅色-程序员宅基地

文章浏览阅读2.1k次,点赞2次,收藏21次。详细介绍python seaborn绘制热图。_python matplotlib 热力图浅色

最好的产品经理社区或者讨论圈有哪几个?_软件产品经理交流社区-程序员宅基地

文章浏览阅读1.8k次。本文将从社区、公众号(产品分析、深度互联网评论)、大佬博客、科技媒体、豆瓣书单等多个方面来阐述目前国内产品经理最好的一些讨论圈和内容,欢迎收藏~产品社区人人都是产品经理官网: http://www.woshipm.com“人人都是产品经理”应该是产品经理日常逛得最多的垂直社区,它里面的内容也主要以产品和运营为主,很多知名的产品经理KOL都会在上面发布文章。职景的学员也经常会把自己的产品分析报告上传发布到“人人都是产品经理”上。这中间也有一些有趣的事,比如两个人上传同一篇文章,只是因为排版格式的_软件产品经理交流社区

西门子PLC与IFIX软件以太网通讯_ifix与西门子plc连接-程序员宅基地

文章浏览阅读4.9k次,点赞2次,收藏16次。摘要IFX组态监控软件与西门子S7-200、S7-300系列PLC通讯,通常采用以太网通讯方式,IFIX软件中,采用S7A驱动的S7TCP/IP的通讯方式。西门子PLC采用第三方工业通讯桥接器实现以太网通讯。方案实施介绍本文以S7 TCP驱动(S7A)连接1台S7300,1台S7200为例:一、配置以太网通讯桥接器的参数用西门子S7TCP驱动来通讯,需要注意参数“S7TCP目标PLC地址”,需要填入PLC的站地址。例:S7-300,IP地址:192...._ifix与西门子plc连接

linux jstack 分析,使用top和jstack分析高CPU问题-程序员宅基地

文章浏览阅读431次。通常我们所说的 CPU 使用率过高,这里面其实隐含着一个用来比较高与低的基准值,比如 JVM 在峰值负载下的平均 CPU 利用率为 40%,如果 CPU 使用率飙到 80% 就可以被认为是不正常的。典型的 JVM 进程包含多个 Java 线程,其中一些在等待工作,另一些则正在执行任务。在单个 Java 程序的情况下,线程数可以非常低,而对于处理大量并发事务的互联网后台来说,线程数可能会比较高。对于..._对于 cpu 的问题,最重要的是要找到是哪些线程在消耗 cpu,通过线程栈定位到问题代

TypeScript手册翻译系列1-基础类型-程序员宅基地

文章浏览阅读111次。为什么80%的码农都做不了架构师?>>> ..._typescript 文档翻译

随便推点

【VSCode】在Linux下使用VSCode编译调试C/C++环境配置(使用g++作为编译器)_vscode远程登陆linux中运行调试attach to chrome怎么改成build g++-程序员宅基地

文章浏览阅读4k次,点赞5次,收藏29次。【VSCode】在Linux下使用VSCode编译调试C/C++环境配置(使用g++作为编译器)一、安装必要插件二、编译运行程序三、调试环境配置四、调试参考链接1: https://blog.csdn.net/ii0789789789/article/details/95026208.参考链接2: https://blog.csdn.net/qq_37968132/article/detai..._vscode远程登陆linux中运行调试attach to chrome怎么改成build g++

树莓派养成之路 ——esp-01智能开关2(硬件篇)_esp-01原理图-程序员宅基地

文章浏览阅读4.1k次,点赞3次,收藏14次。树莓派养成之路 ——esp-01智能开关2(硬件篇)很久没更新了,继续esp智能开关。本文讲述esp-01智能开关的硬件和原理图(PS:本人不是电子专业,只是开了头不得不去搞,如有误请多包含)硬件材料 设备 价格 esp8266-01 11元 220V转3.3v模块 5元 5V继电器(低电平触发) 8元 洞洞板 1元..._esp-01原理图

JavaScript 禁止鼠标选择事件_js 禁止元素鼠标可用-程序员宅基地

文章浏览阅读1.4k次。1、这是通过CSS样式来实现的禁止用鼠标选择功能:unselectable为IE准备onselectstart为Chrome、Safari准备-moz-user-select是FF的css style:html,body{-moz-user-select: none; -khtml-user-select: none; user-select: none;}2、或者使用下面的方法<div unselectable="on" onselectstart="return false;" s_js 禁止元素鼠标可用

ESP32的学习之路(一),基本知识介绍和了解_esp32工作电压-程序员宅基地

文章浏览阅读4.2w次,点赞25次,收藏206次。(一)ESP32麻雀虽小,但也五脏俱全ESP32是Espressif乐鑫信息科技推出的一块WiFi芯片。拥有40nm工艺、双核32位MCU、2.4GHz双模Wi-Fi和蓝牙芯片、主频高达230MHz,计算能力可达600DMIPS。-涵盖精细分辨时钟门控、省电模式和动态电压调整等特征。-它集成了天线和射频巴伦,功率放大器,低噪声放大器,滤波器和电源管理模块等元器件,性能稳定,易于制造,工作温度范围从-40℃到125℃。-支持多种通信协议,如:I2C. I2S. SPI. UART. CAN_esp32工作电压

window下编译lua源码,编译lua的库文件,编译lua解释器,编译lua编译器_lua库和源码一起编译-程序员宅基地

文章浏览阅读448次。网上有很多博客讲如何在windows下编译lua源文件。两上大概是有两种方案:一种是用VS来编译,一种是自己写批处理文件,直接编译。附上以上两种方法的博客:借助VS开发在src文件夹下写批处理_lua库和源码一起编译

国内外优秀的计算机视觉团队汇总_知乎 大连理工大学李培华-程序员宅基地

文章浏览阅读2.1k次。本帖还在更新中,国内外优秀的计算机视觉团队有很多,我这里只是列举了自己从知乎、CSDN等网站上收集到的,排名不分先后,如有遗漏,还请谅解。同时欢迎小伙伴回帖补充,我会更新到本帖,谢谢~感谢极市平台微信公众号的粉丝Alan、Andy、陈、蓝色格调、亚辉、邵帅、城邑、SuperMAN和知乎好友:Shihua Huang的补充贡献最后更新于2020/7/22,已累计更新 10次国内高校研究团队北京清华大学:龙明盛,黄高,艾海舟,张长水(Big eyes laboratory 大眼睛实验室),._知乎 大连理工大学李培华

推荐文章

热门文章

相关标签