contest link
Codeforces Round 764
- A. Plus One on the Subset
- B. Make AP
- C. Division by Two and Permutation
- D. Palindromes Coloring
- E. Masha-forgetful
A. Plus One on the Subset
Example
input
3 6 3 4 2 4 1 2 3 1000 1002 998 2 12 11
output
3 4 1
Title meaning:
You can select multiple numbers and add 1 to them. You can perform the above operation multiple times.
Finally, the numbers in the array are all equal
Please enter the minimum number of operations
answer:
The number that needs to be added the most is from the smallest number to the largest number, so directly
m
a
x
?
m
i
no
max-min
max?min
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define int long long
#define end(x) {<!-- -->cout<<x<<endl;return;}
using namespace std;
typedef pair<int,int> PII;
const int N = 2*1e5 + 10;
string s;char ch;int n;double d;float f;
int a[N],b[N];
void sove(){<!-- -->
cin>>n;
for(int i=1;i<=n;i + + )cin>>a[i];
sort(a + 1,a + n + 1);
cout<<a[n]-a[1]<<endl;
}
signed main(void){<!-- -->
int_=1;
cin>>_;
while(_--)sove();
return 0;
}
B. Make AP
Example
input
11 10 5 30 30 5 10 1 2 3 1 6 3 2 6 3 1 1 1 1 1 2 1 1 3 1 100000000 1 2 1 1 1 2 2
output
YES YES YES YES NO YES NO YES YES NO YES
Title meaning:
Give you one
a
,
b
,
c
a,b,c
a,b,c. You can multiply any of the three numbers by a positive integer
m
m
m, if the arithmetic sequence can be formed in the end, then output “YES”, otherwise output “NO”
answer:
consider separately
a
?
m
,
b
,
c
a*m,b,c
a?m,b,c and
a
,
b
?
m
,
c
a,b*m,c
a,b?m,c and
a
,
b
,
c
?
m
a,b,c*m
The case of a,b,c?m
Arithmetic sequence is the case where the difference between the first two terms and the difference between the last two terms are equal
you can get aboutm
=
f
(
a
,
b
,
c
)
m=f(a,b,c)
For the relational expression of m=f(a,b,c), we only need to judge
m
m
Whether m is a positive integer or not
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define int long long
#define end {<!-- -->cout<<"YES"<<endl;return;}
using namespace std;
typedef pair<int,int> PII;
const int N = 2*1e5 + 10;
string s;char ch;int n;double d;float f;
int a[N],b[N];
inline bool check(double x){<!-- -->
return x==(int )x;
}
void sove(){<!-- -->
double a,b,c; cin>>a>>b>>c;
if((2*b-c)/a>0 & amp; & amp;check((2*b-c)/a))end
if((a + c)/(2*b)>0 & amp; & amp; check((a + c)/(2*b))) end
if((2*b-a)/c>0 & amp; & amp; check((2*b-a)/c)) end
cout<<"NO\
";
}
signed main(void){<!-- -->
int_=1;
cin>>_;
while(_--)sove();
return 0;
}
C. Division by Two and Permutation
Example
input
6 4 1 8 25 2 2 1 1 9 9 8 3 4 2 7 1 5 6 3 8 2 1 4 24 7 16 7 5 22 6 22 4 22
output
YES NO YES NO NO YES
Title meaning:
Give you an array, you can divide a number in the array by two multiple times, round down, and ask if you can get a
1
?
no
1-n
1?n arrangement
answer:
Sort the array first (from large to small), and then drop the large ones first, because it is
1
?
no
1-n
1?n, so anything larger than n needs to be reduced to
no
no
Within n, also need to record
1
?
no
1-n
If the number of 1?n appears, if it appears, continue to divide by two. If the last number appears, it becomes
0
0
0, it means that the array cannot be changed.
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#define int long long
#define end {<!-- -->cout<<"NO"<<endl;return;}
using namespace std;
typedef pair<int,int> PII;
const int N = 2*1e5 + 10;
string s;char ch;int n;double d;float f;
int a[N];
bool b[N];
void sove(){<!-- -->
cin>>n;
memset(b, false, sizeof(b));
for(int i=1;i<=n;i + + )cin>>a[i];
sort(a + 1,a + n + 1,[ &](int x,int y){<!-- -->return x>y;});
bool flag=true;
for(int i=1;i<=n;i + + ){<!-- -->
while(a[i]>n||b[a[i]])a[i]/=2;
b[a[i]]=true;
if(!a[i])end
}
//for(int i=1;i<=n;i + + )if(!b[i])end
cout<<"YES";
cout<<endl;
}
signed main(void){<!-- -->
std::ios::sync_with_stdio(0);
cin. tie(0);
cout. tie(0);
int_=1;
cin>>_;
while(_--)sove();
return 0;
}
D. Palindromes Coloring
Example
input
10 8 2 bxyaxzay 6 3 aaaaaa 6 1 abcdef 6 6 abcdef 3 2 dxd 11 2 abcabcabcac 6 6 sipkic 7 2 eatohd 3 1 llw 6 2 bfvfbv
output
3 2 1 1 1 5 1 1 3 3
Title meaning:
gives a length of
no
no
n string, you can pick out several characters and divide them into
k
k
k groups, so that each group of strings is a palindrome, and this
k
k
The shortest string in the set of k strings is as long as possible.
answer:
Record the number of occurrences of each letter, and then calculate the paired occurrences and the remaining ones. Because the palindrome string is equivalent to symmetry, the paired occurrence can effectively increase the length of the palindrome string.
The rest plus unused pairs (pairs), if it can be greater thank
k
K group, then you can add a length (equivalent to putting it in the middle of the palindrome string!)
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#define int long long
#define end {<!-- -->cout<<"NO"<<endl;return;}
using namespace std;
typedef pair<int,int> PII;
const int N = 2*1e5 + 10;
string s;char ch;int n;double d;float f;
int a[N];
bool b[N];
void sove(){<!-- -->
int k;
cin>>n>>k>>s;
int num[CHAR_MAX + 1]={<!-- -->0};
for(int i=0;i<s.size();i + + )num[s[i]] + + ;
int dui=0,sheng=0;
for(ch='a';ch<='z';ch ++ ){<!-- -->
dui + =num[ch]/2;
sheng + =num[ch]%2;
}
//cout<<"sheng:"<<sheng<<endl;
cout<<(dui/k)*2 + (sheng + (dui%k)*2>=k)<<endl;
}
signed main(void){<!-- -->
std::ios::sync_with_stdio(0);
cin. tie(0);
cout. tie(0);
int_=1;
cin>>_;
while(_--)sove();
return 0;
}
E. Masha-forgetful
Example
input
5 4 8 12340219 20215601 56782022 12300678 12345678 twenty three 134 126 123 1 4 1210 1221 4 3 251 064 859 957 054 4 7 7968636 9486033 4614224 5454197 9482268
output
3 1 4 1 5 6 2 3 4 3 -1 2 1 2 1 2 3 1 -1 3 1 3 2 5 6 3 3 4 1
Title meaning:
give
no
no
n,
m
m
m, means there is
no
no
n lengths are
m
m
string of m
Given another stringthe s
the s
the s
The topic is based on the memory of the phone, which is actually:
you can atno
no
Intercept multiple strings with a length greater than 2 from n strings, and concatenate the strings to form a string
the s
the s
the s
Output the number of intercepted strings and the string position (l
,
r
,
i
l,r,i
l, r, i (
i
i
i indicates which string is in,
[
l
,
r
]
[l,r]
[l,r] indicates the position left endpoint and right endpoint))
If not output -1
Written on the spot:
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#define int long long
#define end {<!-- -->cout<<-1<<endl;return;}
using namespace std;
typedef pair<int,int> PII;
const int N = 2*1e5 + 10;
string s[N];char ch;int n,m;double d;float f;
//int a[N];
//bool b[N];
void sove(){<!-- -->
cin>>n>>m;
for(int i=1;i<=n;i + + )cin>>s[i];
string string1;cin>>string1;
int ans=0;
vector<tuple<int,int,int>>v;
int string1_i=0;
for(int i=1;i<=n;i + + ){<!-- -->
int flag=0,first=-1,last=-1;
int go_end=0;
for(int j=0;j<s[i].size();j ++ ){<!-- -->
if(s[i][j]==string1[string1_i]){<!-- -->
flag ++ ;
if(flag==1)first=j;
string1_i++;
if(string1_i==string1.size()){<!-- -->
if(j-first>=1)
{<!-- -->
v.push_back({<!-- -->first + 1, j + 1, i});//last
go_end=1;
break;
}
else {<!-- -->
//reduction
string1_i--;
flag=0;
continue;
}
}
}
else if(flag){<!-- -->
last=j-1;
//input
if(last-first>=1)
v.push_back({<!-- -->first + 1,last + 1,i});
else {<!-- -->
//reduction
string1_i--;
flag=0;
continue;
}
flag=0;
j=0;
//i=1; //Not added, the last test failed, added -1 all wrong
//ok //reason: each such segment must have a length of at least 2
i=1;
}
}
if(go_end)break;
}
if(string1_i!=string1. size()) end
else{<!-- -->
ans=(int)v. size();
cout<<ans<<endl;
for(int i=0;i<v. size();i ++ ){<!-- -->
cout<<get<0>(v[i])<<' '<<get<1>(v[i])<<' '<<get<2>(v[i])<<endl;
}
}
}
signed main(void){<!-- -->
std::ios::sync_with_stdio(0);
cin. tie(0);
cout. tie(0);
int_=1;
cin>>_;
while(_--)sove();
return 0;
}
I feel that there is a problem with the restoration. If there is a string with a length greater than 2 in another place that also contains the currently judged characters, then in fact, more than one needs to be restored. . .
offical:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4;
map<string, bool> have;
map<string, tuple<int,int,int>> pos;
void solve() {<!-- -->
int n, m; cin >> n >> m;
vector<bool> dp(m + 1, false);
vector<int> pr(m + 1);
vector<string> cache;
dp[0] = true;
for (int i = 0; i < n; i ++ ) {<!-- -->
string s; cin >> s;
for (int j = 0; j < m; j ++ ) {<!-- -->
string t;
t + = s[j];
for(int k = 1; k <= 2; k ++ ) {<!-- -->
if (k + j >= m) break;
t + = s[j + k];
if (!have[t]) {<!-- -->
have[t] = true;
pos[t] = make_tuple(j, j + k, i);
cache.push_back(t);
}
}
}
}
string s; cin >> s;
for (int i = 0; i < m; i ++ ) {<!-- -->
string t;
t + = s[i];
for (int k = 1; k <= 2; k ++ ) {<!-- -->
if (i - k < 0) break;
t = s[i-k] + t;
if (have[t] & amp; & amp; dp[i-k]) {<!-- -->
dp[i + 1] = true;
pr[i + 1] = i-k;
}
if (dp[i + 1]) break;
}
}
for (string t : cache) {<!-- -->
have[t] = false;
}
if (!dp[m]) {<!-- -->
cout << "-1\
";
return;
}
vector<tuple<int,int,int>> ans;
for (int k = m; k > 0; ) {<!-- -->
int p = pr[k];
string t = s.substr(p, k - p);
ans. emplace_back(pos[t]);
k = p;
}
cout << (int)ans. size() << '\
';
reverse(ans.begin(), ans.end());
for (auto [l,r,i] : ans) cout << l + 1 << ' ' << r + 1 << ' ' << i + 1 << '\
';
}
int main() {<!-- -->
int t;
cin >> t;
for (int tt = 0; tt < t; tt ++ ) {<!-- -->
solve();
}
}