Codeforces Round 764 (Div. 3)

比赛链接

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

题意：

你可以选择多个数字，将其加1。上述操作你可以执行多次。
最终使得数组里的数全部相等
请输出最少操作次数

题解：

需要加最多次的是最小的数到最大的数，所以直接$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

题意：

给你一个$a,b,c$。你可以将三个中的任意一个数乘上正整数$m$,如果最后能形成等差数列，那么就输出"YES"，否则输出"NO"

题解：

分别考虑$a\ast m,b,c$和$a,b\ast m,c$和$a,b,c\ast m$的情况
等差数列就是前两项的差和后两项的差相等情况
就可以得到关于$m=f(a,b,c)$的关系式子，我们只需要判断$m$是否是正整数即可

#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&&check((2*b-c)/a))endif((a+c)/(2*b)>0&&check((a+c)/(2*b))) endif((2*b-a)/c>0&&check((2*b-a)/c)) endcout<<"NO\n";
}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

题意：

给你一个数组，你可以多次将数组里的一个数字除二，向下取整，问最终能不能得到一个$1-n$的排列

题解：

先将数组排序（从大到小），然后大的先降，因为是$1-n$，所以大于n都需要缩小到$n$以内，还需要记录$1-n$的数字出现情况，如果出现过就继续除二，如果最后出现数字变成$0$了，就说明这个数组变不成。

#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])endcout<<"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
eatoohd
3 1
llw
6 2
bfvfbv

output

3
2
1
1
1
5
1
1
3
3

题意：

给出长度为$n$字符串，你可以将其中的若干个字符挑选出来并分成 $k$ 组，使每组字符串均为回文串，且这$k$组字符串中最短的字符串尽可能长。

题解：

记录每个字母出现的次数，然后计算成对出现的和剩余的，因为回文串相当于对称，所以成对出现的就可以有效的增加回文串的长度。
剩下的加上没有用上的配对（成对），如果能大于$k$组，那就可以增加一个长度（相当于放在回文串的中间！）

#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

54 8
12340219
20215601
56782022
12300678
123456782 3
134
126
1231 4
1210
12214 3
251
064
859
957
0544 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

题意：

给出$n$,$m$，表示有$n$个长度为$m$的字符串
再给出一个字符串$s$
题目是按照电话的记忆来讲的，实际上就是：
你可以在$n$个字符串里面截取多个长度大于2的字串，将字串拼接能合成为字符串$s$
输出截取字串个数和字串位置($l,r,i$（$i$表示在哪一个字符串，$[l,r]$表示位置左端点和右端点）)
如果不能输出-1

当场写的：

#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});//lastgo_end=1;break;}else {//还原string1_i--;flag=0;continue;}}}else if(flag){last=j-1;//inputif(last-first>=1)v.push_back({first+1,last+1,i});else {//还原string1_i--;flag=0;continue;}flag=0;j=0;//i=1; //不加，最后一个测试没过，加了 需要判的 -1 全错//ok //缘由:每个这样的段必须有长度至少2i=1;}}if(go_end)break;}if(string1_i!=string1.size()) endelse{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;
}

感觉是还原那边有点问题，如果另一个地方有长度大于2的字串还包含了现在判断的字符，那么其实就需要还原多个了。。。

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] && 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\n";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() << '\n';reverse(ans.begin(), ans.end());for (auto [l,r,i] : ans) cout << l+1 << ' ' << r+1 << ' ' << i+1 << '\n';
}int main() {int t;cin >> t;for (int tt = 0; tt < t; tt++) {solve();}
}