Codeforces Round #710 (Div. 3)
A. Strange Table
题意：给定一个n*m的矩阵，其为列递增现在变为行递增
现在给定一个数x问图一中的x在图2中是什么数字
解题思路：数学计算新生成的坐标，然后输出即可
解题代码:
#include <iostream>
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int max = 2e5+10;
signed main(){
int t,n,m,x;
cin >> t;
while(t--){
cin >> n >> m >> x;
int ta,tb;
ta = x % n;
if(ta==0) ta =n ;
tb = (x-ta)/n+1;
cout << (ta-1)*m + tb <<endl;
}
return 0;
}
B. Partial Replacement
题意：
给定一个由‘x’和’*‘组成的长度为n字符串，将其中的某些’*‘用’x’替代，且要求头尾的’*‘必须被替代为’x’，且两个’x’之间的距离（下标之差）不得超过给定的k
题解：电线杆问题，贪心经典，从第一个变化的符号开始取，差不超过k的都可以拿走
解题代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int t,n,k,ans,npos,fi,la;
string s;
cin>>t;
while(t--){
cin >> n >> k;
cin >> s;
vector<int>vc;
for(int i=0;i<s.length();i++){
if(s[i]=='*'){
vc.push_back(i);
}
}
fi = vc[0];
la = vc.back();
if(fi==la || la-fi<=k){
if(fi==la) cout<<"1\n";
else cout<<"2\n";
continue;
}
ans = 2;
npos = fi;
while(npos+k < la){
if(s[npos+k]=='*')npos += k;
else{
npos += k;
while(s[npos]!='*') npos--;
}
ans++;
}
cout<<ans<<endl;
}
return 0;
}
C. Double-ended Strings
题意：给定两个字符串，可以删除头尾元素，问最少要惊醒多少次操作才能使的两个串相等
解题思路：最长公共子串问题，最终数出的答案为两个串的长度和减去两倍的子串长度
解题代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 120;
int dp[maxn][maxn];
signed main(){
int t;
cin>>t;
int len1,len2,n,ans=0,tres;
while(t--){
ans = tres = 0;
string s1,s2;
cin>>s1>>s2;
len1 = s1.length();
len2 = s2.length();
memset(dp,0,sizeof dp);
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
if(s1[i]==s2[j]) dp[i][j]=1;
}
}
for(int i=0;i<len1;i++){
tres=0;
for(int j=0;j<len2;j++){
if(dp[i+j][j]==1){
tres++;
}else{
tres = 0;
}
ans = max(ans,tres);
}
}
for(int i=0;i<len2;i++){
tres = 0;
for(int j=0;j<len1;j++){
if(dp[j][i+j]==1){
tres++;
}else{
tres = 0;
}
ans = max(ans,tres);
}
}
printf("%d\n",s1.length()+s2.length()-2*ans);
}
return 0;
}
D. Epic Transformation
题意：给定长度为n的数组，可以选择里面不同的两个元素删除，问最后剩下的元素最小个数是多少
题解思路:简单贪心，删除数字只与出现最多的数字的出现次数有关，如果其超过一半，那么最后他会有剩余，如果他不足，那么如果他是偶数，那么最后不会有数字剩下，如果为奇数，那么会剩下的数字为1
解题代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 120;
int dp[maxn][maxn];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t,n;
cin>>t;
while(t--){
cin >> n;
int tnum = -1;
int tleft = 0;
int tmp;
vector<int>vc;
map<int,int>mp;
for(int i = 0;i<n;i++){
cin >> tmp;
if(mp[tmp] == 0){
mp[tmp] =1;
vc.push_back(tmp);
}else{
mp[tmp]+=1;
}
}
int mx = -1;
for(int i = 0;i<vc.size();i++){
mx = max(mx,mp[vc[i]]);
}
if(mx > n-mx){
cout << mx - n + mx << endl;
}else{
if(n%2)cout << 1 << endl;
else cout << 0 << endl;
}
}
return 0;
}
E. Restoring the Permutation
题意：给出一个数列pi表示排列a的前i项（1<=i<=n）的最大值，要求分别求出字典序最大与最小的原排列。
解题思路:
对于字典序最小，其余位置按照剩余数字从小到大填充即可，对于字典序最大，在每一个ai未确定的位置，找出比pi小的数字中没有被使用过且最大的数字填充进去即可。
解题代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--){
int n;
cin >> n;
vector<int> q(n);
for (auto &x : q) cin >> x;
set<int> nums;
for (int i = 1; i <= n; i++) nums.insert(i);
vector<int> per(n);
per[0] = q[0];
nums.erase(q[0]);
for (int i = 1; i < n; i++)
if (q[i] != q[i - 1]) {
per[i] = q[i];
nums.erase(q[i]);
}
}
set<int> numssave = nums;
cout << q[0] << ' ';
for (int i = 1; i < n; i++) {
if (per[i] == 0) {
cout << *nums.begin() << ' ';
nums.erase(nums.begin());
} else {
cout << per[i] << ' ';
}
}
cout << '\n';
nums = numssave;
cout << q[0] << ' ';
for (int i = 1; i < n; i++) {
if (per[i] == 0) {
auto it = --nums.lower_bound(q[i]);
cout << *it << ' ';
nums.erase(it);
} else {
cout << per[i] << ' ';
}
}
cout << '\n';
}
return 0;
}