首页 > 其他分享 >Codeforces Round #838 (Div. 2) A--C

Codeforces Round #838 (Div. 2) A--C

时间:2023-01-03 18:32:00浏览次数:56  
标签:cout -- 838 cin long int ans Div define


​https://codeforces.com/contest/1762​


A. Divide and Conquer

分析:

数组所有元素和为偶数则为good。那么肯定要考虑奇偶性问题。

1.如果和直接==偶数,那cout << 0;

2.但是一个数除2向下取整是不明确除几次的(因为一个数可以表示成Codeforces Round #838 (Div. 2) A--C_2最近的倍数约数 数学),因此对所有数分别除2,尝试每次都更新次数最小值即可。



ac代码:

#include <bits/stdc++.h>

#define endl '\n'
using namespace std;

const int N = 2e5 + 5, INF = 0x3f3f3f3f;

void s(){
int n;
cin >> n;
vector<int> a(n + 1);
long long sum = 0;
for(int i = 1; i <= n; i ++) cin >>a[i], sum += a[i];

int ans = INF;
if(sum % 2 == 0){
cout << 0 << endl;
return;
}else{

for(int i = 1; i <= n; i ++){
int cnt = 0;
if(a[i] % 2 == 0){
while(a[i] % 2 == 0){
a[i] /= 2;
cnt ++;
}
}else {
while(a[i] % 2 == 1){
a[i] /= 2;
cnt ++;
}
}
ans = min(ans, cnt);
}
}
cout << ans << endl;

}

int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);

int t;
cin >> t;
while(t--) s();


return 0;
}









B.Make Array Good

大意:数组中任意两元素可以整除。

分析:要将所有的数变到某个数的倍数上。如果数学思维敏锐的话,可以每个数发觉变到离它最近的Codeforces Round #838 (Div. 2) A--C_3组合数学_02最好,因为这是最小的倍数梯度,任何一个数都可以落在2的x次方到x+1次方之间,仅仅增加一次可以变成2的倍数。



ac代码:

#include <bits/stdc++.h>

#define endl '\n'
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;


int beishu[505], tt;

void s(){
int n;
cin >> n;
vector<int> a(n);
for(auto &i:a) cin >> i;


int times = 0;
vector<pair<int, long long>> ans;
for(int i = 0; i < n; i ++){
long long big = 0;
for(int j = 0; j < tt; j ++) {
if(beishu[j] >= a[i]) {
big = beishu[j];
break;
}
}
while(a[i] < big) {
if(a[i] + a[i] <= big) ans.push_back({i + 1, a[i]}) , a[i] += a[i];
else ans.push_back({i + 1, big - a[i]}), a[i] = big;
times ++;
}
}

cout << times << endl;
for(auto i : ans) {
cout << i.first << " " << i.second << endl;
}

}


void get(){
long long num = 1;
beishu[0] = 1;tt = 1;
while(num <= 1e18) beishu[tt ++] = (num *= 2);
}

int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);

get();

int t;
cin >> t;
while(t--) s();

return 0;
}







C. Binary Strings are Fun

大意:

定义good规则:对于每个奇数(2m-1)下标,该下标对应的字符在当前下标前出现的次数必须>=m.    例如:1001011 and 1101001

Codeforces Round #838 (Div. 2) A--C_2最近的倍数约数 数学_03

都是1001的good子串,因为下标1对应字符‘1’在此之前出现次数是1;下标3对应字符‘0’在此之前出现的次数是2;下标5对应字符‘0’在此之前出现次数是3;下标7对应字符‘1’在此之前出现次数是4。

对于每个前缀二进制子串,将它拉开,两两之间留个空位可以穿插0或1.询问所有的子串可能的情况数量总和。

每一个子串的答案是:len是后缀相等字符个数。

Codeforces Round #838 (Div. 2) A--C_2最近的倍数约数 数学_04

简单来说

Codeforces Round #838 (Div. 2) A--C_2最近的倍数约数 数学_05

这个样例手动模拟的时候发现后面四个1就是2倍变化。

前面10101交替的时候,为了保证子串good数组一定至少有1个数,那肯定会导致在结尾0变1或1变0的时候会把前面穿插的元素变成与最后一个元素对应的数,会限制成1次。



ac代码:

#include <bits/stdc++.h>

#define endl '\n'
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5, INF = 0x3f3f3f3f, mod = 998244353;
//函数内初始化数组={}

long long qmi(long long a, long long b, long long mod){
long long ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b /= 2;
}
return ans;
}

void solve(){
int n;
cin >> n;
string a;
cin >> a;

vector<long long> suffix(n + 1);
int len = 0;
for(int i = n - 1, j = n - 1; i >= 0; i --){
if(i == j) {
while(a[j] == a[i]) j --;
}
len = i - j;
suffix[i] = qmi(2, len - 1, mod);
}
long long ans = 0;
for(int i = 0; i < n; i ++){
ans = (ans + suffix[i]) % mod;
}
cout << ans << endl;
}

int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);

int t;
cin >> t ;
while(t--) solve();


return 0;
}




标签:cout,--,838,cin,long,int,ans,Div,define
From: https://blog.51cto.com/u_15389271/5986280

相关文章

  • [答疑]电影院里电影票和座位号的关系
    电影院里电影票和座位号的关系......
  • 打破冬季单调 柯罗芭KLOVA在东方美学和摩登时尚间找寻平衡
    在衣着厚重的冬日,为了御寒舍弃了很多“漂亮的衣服”,但智慧的女人总能在保暖之余还留有一隅浪漫,放大服装的力量,展示个人魅力。随着冬季衣橱换新,柯罗芭KLOVA带来诚意......
  • m基于matlab的协作mimo分布式空时编码技术的仿真
    1.算法描述基于matlab的协作mimo分布式空时编码技术的仿真,包括规则LDPC级联D-STBC,ML,ZF,DFE均衡,Fincke-Pohst-MAP算法检测。将规则LDPC加入这个协作MIMO的D-STBC里,......
  • CentOS7源码安装redis6
    CentOS7源码安装redis61.下载源码包[root@localhost~]#wgethttps://download.redis.io/releases/redis-6.2.8.tar.gz2.安装依赖 redis6需要gcc高版本[root@lo......
  • 24.Java程序员的经典错误
    1.使用Objects.equals比较对象是JDK7提供的一种方法,可以快速实现对象的比较,有效避免烦人的空指针检查。但是这种方法很容易用错,例如:1LonglongValue=123L;2System......
  • 12 列表渲染-列表过滤
    <html>  <head>    <title>列表过滤</title>    <scripttype="text/javascript"src="../js/vue.js"></script>  </head>  <body> ......
  • systemd的程序自启动脚本编写
    以FreeSWITCH的自启动脚本为例。一、编写freeswitch.service文件1[Unit]2Description=FreeSWITCH3After=syslog.targetnetwork.target4After=postgresql.......
  • Mysql主从同步配置
    一、主数据库的配置1.my.cnf(Linux)/my.ini(Windows)在配置文件参数选项[mysqld]下面添加如下内容log_bin=mysql-binserver_id=1innodb_flush_log_at_trx_commit=......
  • Html - 目录
    Html-标题标签,段落标签,换行标签,文本格式化标签,盒子标签div,span,图像标签,超链接标签,表格,列表Html-表单form,input的type属性与其它属性Html-lable增加用户体验,下拉框,......
  • 了解协程
    新入门skynet系列视频b站网址https://www.bilibili.com/video/BV19d4y1678Xskynet框架实现中用到了协程。特别是lua应用层在消息调度的时候。基本概念skynet的协程......