目录
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()
{
IOS
int _ = 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()
{
IOS
int _ = 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()
{
IOS
int _ = 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()
{
IOS
int _ = 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()
{
IOS
int _ = 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 5
int 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()
{
IOS
int _ = 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()
{
IOS
int _ = 1;
cin >> _;
while(_ --) solve();
return 0;
}G2. Division + LCP (hard version)
后面再补