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;
}