Codeforces Round #666 (Div. 2)A~C题解

发布于 2020-08-31  0 次阅读


A. Juggling Letters

题目大意:

给你n个字符串,让你移动任意次后判断能否让每个字符串相等

思路:

直接统计每个字符串中出现的字符串的个数和,判断和是否为n的倍数

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1009;
int n, vis[30];
string s[N];
void solve(){
    cin>>n;
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<=n; i++){
        cin>>s[i];
        for(int j=0; j<s[i].length(); j++){
            vis[s[i][j]-'a']++;
        }
    }
    int flag=0;
    for(int i=0; i<27; i++){
        if(vis[i]!=0 && vis[i]%n!=0) flag=1;
    }
    if(flag)    cout<<"NO"<<endl;
    else        cout<<"YES"<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

B. Power Sequence

题目大意:

给你一个长度为n的数组a,下标从0 到n − 1 ,你可以重新排列数组a的顺序,然后对数组中的任意一个元素+1或者-1,其花费都是1,求最小花费,使得ai = ci

思路:

枚举C的取值,当代价开始增加时退出,增加前的代价即为最小代价

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e5 +9;
int n, a[N];

void solve(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    sort(a+1, a+1+n);
    int ans=INF, tep;
    for(int c=1; 1; c++){
		tep=a[1]-1;
		int mj=c;
        for(int j=2; j<=n; j++){
			tep+=abs(a[j]-mj);
            if(tep>ans)  break;
			mj*=c;
		}
        if(tep>ans)  break;
        ans=tep;
    }
	cout<<ans<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

C. Multiples of Length

题目大意:

给你一个长度为n的数组,需要使用三步将数组中的每个元素变为0
每步的操作为,选择一个区间,对区间中的值进行加减k的操作,但是k必须为区间的长度的倍数

思路:

当n=1的时候很简单,直接第一步减到0即可,后两次操作0
不为0时
很明显不会让你一步就完成,所以可以操作前n-1个
可以考虑第一步操作前n-1个数使其变成整个数组的倍数
第二步操作第n个数使其变成0
第三步选择整个区间变成0
对前面n-1个数操作为ai + k ( n − 1 ) ,即为kn + ai− k ,所以可以直接k取ai ,使得每位都为n的倍数

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e5 +9;
int n, a[N];
void solve(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    if(n==1){
        cout<<"1 1"<<endl;
        cout<<-a[1]<<endl;
        for(int i=2; i<=3; i++){
            cout<<"1 1"<<endl;
            cout<<"0"<<endl;
        }
        return ;
    }
    cout<<"1 "<<n-1<<endl;
    for(int i=1; i<=n-1; i++){
        cout<<a[i]*(n-1)<<" ";
        a[i]+=(n-1)*a[i];
    }
    cout<<endl;
    cout<<n<<" "<<n<<endl;
    cout<<-a[n]<<endl;
    cout<<"1 "<<n<<endl;
    for(int i=1; i<=n-1; i++){
        cout<<-a[i]<<" ";
    }
    cout<<"0"<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

平平无奇的在校大学生