Codeforces Round 943 (Div. 3) (A-G1) C++题解

ops/2024/10/11 5:25:07/

目录

比赛链接 : 

A. Maximize?

B. Prefiquence

C. Assembly via Remainders

 D. Permutation Game

E. Cells Arrangement

F. Equal XOR Segments

G1. Division + LCP (easy version)

G2. Division + LCP (hard version)

比赛链接 : 

Dashboard - Codeforces Round 943 (Div. 3) - Codeforces

A. Maximize?

数据范围小，随便搞，遍历即可 : 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}inline void solve(){int x ; cin >> x ;int ans  = 0 ,res;for(int i=1;i<x;i++){int t = gcd(i,x) + i ;if(t>ans){ans = t ;res = i ;	}}cout << res << endl ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

B. Prefiquence

简单贪心，先设a的遍历下标l为0,在b中遇到一个b[i]==a[l],那么l++,ans++;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;using namespace std;inline void solve() {int n , m ; cin >> n >> m ;string a , b ; cin >> a >> b ;int ans = 0 ;int l = 0 ;for(int i=0;i<m;i++){if(b[i]==a[l]){l ++ ;ans ++ ;}}cout << ans << endl ;
}signed main()
{IOSint _ = 1;cin >> _;while (_--) solve();return 0;
}

C. Assembly via Remainders

只要满足a[1]>x[2]的任意一个值，然后后面递推即可 : 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;using namespace std;inline void solve(){int n ; cin >> n ;vector<int> x(n+1) , a(n+1) ;for(int i=2;i<=n;i++) cin >> x[i] ;a[1] = 1001 ;for(int i=2;i<=n;i++) a[i] = a[i-1] + x[i] ;for(int i=1;i<=n;i++) cout << a[i] << " " ;cout << endl ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

 D. Permutation Game

首先我们可以先找到a数组的最大值ma ；

  • 如果BodYa和Sasha有可能能够到达ma的话，在k足够大的情况下，一定优先到达ma处，保存这一条路径上的a值 ;
  • 如果不能到达，也就是形成了一个死循环，也可以找出这一条路径的a值,遇到之前遍历过的店，就结束寻找 ，这里用set记录；
  • 路径上的a值分别保存在B和S数组中 ;

那么求出B和S数组的前缀和，分别保存在Bs,Ss数组中；

分别求出可能得到的最大分数 : 

  • 对于BodYa和Sasha两个人，都可以停留在之前获取路径上的任意一点，然后这点下标为i ;
  • 这里分数分两部分，1LL * (k-i) * S[i] 和 1LL * Ss[i],其中对BodYa也一样，遍历求出最大值即可;

.......................

表达能力有限，还是看代码吧，写的很清楚 : 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
typedef long long LL;
const int N = 2e5+10;
using namespace std;int n , k , pb , ps ;
int p[N] , a[N]  , B[N] , S[N] ;
LL Bs[N] , Ss[N] ;inline void solve(){cin >> n >> k >> pb >> ps ;int ma = 0 ;for(int i=1;i<=n;i++) cin >> p[i] ;for(int i=1;i<=n;i++) {cin >> a[i] ;if(a[i]>ma) ma = a[i] ;}int lb = 0 , ls = 0 ;set<int> stb , sts ;bool tb = false , ts = false ;while(a[pb]!=ma){if(stb.find(pb)!=stb.end()) {tb = true ;break ;}B[lb++] = a[pb] ;stb.insert(pb);pb = p[pb] ;}if(!tb) B[lb++] = ma ; while(a[ps]!=ma){if(sts.find(ps)!=sts.end()){ts = true ;break ;}S[ls++] = a[ps] ;sts.insert(ps) ;ps=p[ps];}if(!ts) S[ls++] = ma ; LL mb = 0 , ms = 0 ;// 记录最终分数 for(int i=0;i<lb;i++) Bs[i+1] = B[i] + Bs[i] ;for(int i=0;i<ls;i++) Ss[i+1] = S[i] + Ss[i] ;LL res = 0 ;for(int i=0;i<lb;i++){if(k>=i+1) res = 1LL * (k-i)*B[i] + 1LL * Bs[i] ;else break ;mb = max(mb , res) ;}res = 0 ;for(int i=0;i<ls;i++){if(k>=i+1) res = 1LL * (k-i) * S[i] + 1LL * Ss[i] ;else break ;ms = max(ms,res) ;}if(mb>ms) cout << "Bodya" << endl ;else if(mb==ms) cout << "Draw" << endl ;else cout << "Sasha" << endl ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

E. Cells Arrangement

这就是一个guess题，首先可能想到的是全按对角线排布，但是只能够获得全是偶数的H集合；

那么挑出一个(2,2)改为(1,2),就可以获得0,1,2,3,4,...2*(n-1)这么多，且这是最多的;

大概也就是这个样子 : 

 

代码 ： 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;using namespace std;inline void solve(){int n ; cin >> n ;cout << "1 1" << endl ;cout << "1 2" << endl ;for(int i=3;i<=n;i++) cout << i << " " << i << endl ;cout << endl ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

F. Equal XOR Segments

二分 + 位运算

首先要知道的一点是 : 异或(^)是具有前缀和性质的，我们用一个s数组来记录前缀异或和，但是这里a后面也没啥用，直接原地前缀和即可 

[注] : 要求[l,r]的异或 , 直接返回a[r] ^ a[l-1]即可 

如果a[r] ^ a[l-1] == 0,那么一定可以满足题目条件，因为[l,r]中一定存在l<m<r满足a[m]^a[l-1] == a[r]^a[m-1] == v ;

如果a[r]^a[l-1]!=0,设为v,那么如果要满足题目条件，k一定为奇数且一定可以找到三个异或和为v的区间(因为多出来的偶数个会互相抵消) : 

那么题目也就转换成[l,r]能划分为3个异或和为v的区间 : 

这里我们可以用map<int,vector<int>>存下每个前缀异或和的下标；

分两步 : 

1 . 找到最小的i>l使s[i]=s[r],找不到则无解

2 . 找到最小的j>i使s[j]=s[l-1]

如果i<j && j<r则输出yes,否则输出no;

详细请看代码 ： 

 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;//1
//5 1
//1 1 2 3 0
//1 5int a[N] ;inline void solve(){int n , q ; cin >> n >> q ;map<int,vector<int>> mp ;mp[0].push_back(0) ;for(int i=1;i<=n;i++) {cin >> a[i] ;a[i] ^= a[i-1] ;mp[a[i]].push_back(i) ;}while(q--){int l , r ; cin >> l >> r ;int x = a[r] ^ a[l-1] ;if(x==0) {cout << "YES" << endl ; continue ; }// v!=0 : k一定为奇数(k>=3)，且一定能划3段异或和为v的区间// 1 . 找到最小的i>l使s[i]=s[r],找不到则无解auto i = lower_bound(mp[a[r]].begin(),mp[a[r]].end(),l) ;// cout << *i << endl ;if(i==mp[a[r]].end()||*i>=r){cout << "No" << endl ;continue  ;}// 2 . 找到最小的j>i使s[j]=s[l-1]auto j = upper_bound(mp[a[l-1]].begin(),mp[a[l-1]].end(),*i) ;// cout << *j << endl ;if(j==mp[a[l-1]].end()){cout << "No" << endl ;continue ;}// cout << *i << " " << *j << endl ;if(*i<*j &&*j<r) cout << "Yes" << endl ;else cout << "No" << endl ;} cout << endl ;return ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

G1. Division + LCP (easy version)

二分 + kmp

也可以Hash做

对前缀长度m进行二分,str = s.substr(0,m) ,用kmp判断是否s中满足能够匹配的数量tmp>=k,那么m合法，反之不合法;

这里KMP直接套模板即可 : 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;int n,Yss1206,k;
string s ;bool pd(int m){if(m == 0) return 1;string t = s.substr(0, m);vector<int> ne(m + 1, 0);ne[0] = -1;for (int i = 1, j = -1; i < m; i ++ ) {while (j >= 0 && t[j + 1] != t[i]) j = ne[j];if (t[j + 1] == t[i]) j ++ ;ne[i] = j;}int tmp = 0;for (int i = 0, j = -1; i < n; i ++ ) {while (j != -1 && s[i] != t[j + 1]) j = ne[j];if (s[i] == t[j + 1]) j ++ ;if (j == m - 1) {++ tmp;j = -1;}}return tmp >= k;
}inline void solve(){cin>>n>>Yss1206>>k;cin >> s ;int l = 0 , r = n/k ;while(l<r){int mid = l + r + 1 >> 1 ;if(pd(mid)) l = mid ;else r = mid - 1 ; }cout << l << endl ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

G2. Division + LCP (hard version)

后面再补


http://www.ppmy.cn/ops/39126.html

相关文章

stm32_HAL_RTC_闹钟函数（F1只有一个闹钟）

stm32_HAL_RTC_闹钟函数（F1只有一个闹钟）

HAL_RTC_SetAlarm: 功能&#xff1a;设置RTC闹钟。 参数&#xff1a; hrtc&#xff1a;指向RTC句柄结构的指针。sAlarm&#xff1a;指向包含闹钟配置的结构体的指针。Format&#xff1a;指定日期和时间的格式&#xff08;12小时或24小时制&#xff09;。返回值&#xff1a;状态…
阅读更多...
ADS基础教程11 - TouchStone文件的导出及导入

ADS基础教程11 - TouchStone文件的导出及导入

目录 一、 T o u c h S t o n e 介绍 \color{#4285f4}{ \mathbf{ 一、TouchStone介绍}} 一、TouchStone介绍 二、文件导出、导入方式 \color{#4285f4}{ \mathbf{ 二、文件导出、导入方式}} 二、文件导出、导入方式1.原理图操作1&#xff09;原理图中导出2.原理图中导入 3.DDW中…
阅读更多...
kafka日志存储

kafka日志存储

前言 kafka的主题(topic)可以对应多个分区(partition)&#xff0c;而每个分区(partition)可以有多个副本(replica)&#xff0c;我们提生产工单创建topic的时候也是要预设这些参数的。但是它究竟是如何存储的呢&#xff1f;我们在使用kafka发送消息时&#xff0c;实际表现是提交…
阅读更多...
【Git】Github创建远程仓库并与本地互联

【Git】Github创建远程仓库并与本地互联

创建仓库 点击生成新的仓库 创建成功后会生成一个这样的文件 拉取到本地 首先先确保本地安装了git 可以通过终端使用 git --version来查看是否安装好了git 如果显示了版本信息&#xff0c;说明已经安装好了git&#xff0c;这时候我们就可以进入我们想要clone到问目标文件夹 …
阅读更多...
网络安全基础

网络安全基础

目录 概述 1. 需求 2. 密码学 3. 保密 4. 数字签名 5. 身份认证 6. 对称密钥分配及管理 7. 公钥认证及PKI 8. 网络安全协议标准 结语 概述 在当今数字化时代&#xff0c;网络安全是任何组织和个人都必须重视的重要问题。从个人隐私到商业机密&#xff0c;网络安全的基…
阅读更多...
建发弘爱 X 袋鼠云：加速提升精细化、数字化医疗健康服务能力

建发弘爱 X 袋鼠云：加速提升精细化、数字化医疗健康服务能力

厦门建发弘爱医疗集团有限公司&#xff08;简称“建发弘爱”&#xff09;创立于2022年&#xff0c;是厦门建发医疗健康投资有限公司的全资子公司&#xff0c;专业从事医疗健康领域的医疗服务。 建发弘爱通过医疗、健康及产业服务三大板块&#xff0c;为百姓提供医疗和健康全生…
阅读更多...
luceda ipkiss教程 69：导出器件或者线路的三维模型

luceda ipkiss教程 69：导出器件或者线路的三维模型

ipkiss 3.12版加入write_obj函数&#xff0c;可以直接输出器件的三维模型。 如&#xff0c;输出自定义的mmi的三维模型&#xff1a; 代码如下&#xff1a; from si_fab import all as pdk from ipkiss3 import all as i3class MMI1x2(i3.PCell):"""MMI with …
阅读更多...
web页面与原生android通信，调用原生android方法

web页面与原生android通信，调用原生android方法

注册初始化方法JsBridge //JS注册事件监听 function connectWebViewJavascriptBridge(callback) {if (window.WebViewJavascriptBridge) {callback(WebViewJavascriptBridge)} else {document.addEventListener(WebViewJavascriptBridgeReady,function() {callback(WebViewJav…
阅读更多...
最新文章

Copyright @ 2022~2023