CCPC-2018-桂林

D.Bits Reverse

标签：

位运算，模拟

题意：

给定两个数a和b，对于a的二进制形式对于相隔一位的位置可以交换，问我们是否可以通过这些操作让a=b，可以的话求出最小操作次数。

题解：

对于这道题可以奇偶位分开考虑，如果两个数的奇数位置和偶数位置的1个数相等，那么就可以化到相等，对于最小操作次数，只要记录下相邻最近的1的位置进行交换，就能贪心地得到最小值。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N=1e6+10;

void solve(){
    int x,y;
	cin>>x>>y;
	vector<int>idx(100,0),idy(100,0);
	auto check=[&](int flag)->int{
		int cnt0=0,cnt1=0;
		ll tmp=x,res=0;

		for(int i=1;tmp;i++,tmp>>=1){
			if(i%2==flag&&tmp%2==1)idx[++cnt0]=i;
		}

		tmp=y;
		for(int i=1;tmp;i++,tmp>>=1){
			if(i%2==flag&&tmp%2==1)idy[++cnt1]=i;
		}
		if(cnt0!=cnt1)return -1;
		for(int i=1;i<=cnt0;i++){
			res+=abs(idx[i]-idy[i])/2;
		}
		return res;
	};

	if(check(0)==-1||check(1)==-1)cout<< -1<<endl;
	else cout<<(check(0)+check(1))<<endl;
}   

signed main(){
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++){
        cout<<"Case "<<i<<": ";
        solve();
    }
    return 0;
}

H. Hamming Distance

标签：

贪心，思维

题意：

给定两个字符串，问我们构造出字典序最小的长度和给定字符串相等的字符串，两个字符串的Hamming距离相等。（一个字符串和另外一个字符串不相等的字符数量）

题解：

1. 对两个串进行考虑，如果两个串某个位置的字符相等，那么直接填为’a’
2. 对于不相等的尽量填‘a’，但是可能在原串出现’a’，那么会导致两次不相等，那么如果后面可以填入其他数来满足，那么这个位置就能填入‘a’
3. 从后到前记录不同的位置的数量，这些就是可以松弛的地方
4. 记录一个cnt，与是是s1不相同那么cnt++，与s2不相同那么cnt–，那么最后就是cnt=0。
5. 那么对于每个位置，循环26个字母，对于这个字母填完后面可以满足cnt=0，那么就填入，贪心地填就是答案。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N=1e6+10;

void solve(){
    string s1,s2;
    cin>>s1>>s2;
    int n=s1.size(),cnt=0;
    vector<int>dp(n+1,0);
    for(int i=n-1;i>=0;i--){
        dp[i]=dp[i+1]+(s1[i]!=s2[i]);
    }
    auto check=[&](char c,int idx){
        int tmp=cnt;
        if(c!=s1[idx])tmp++;
        if(c!=s2[idx])tmp--;
        return abs(tmp)<=dp[idx+1];

    };
    for(int i=0;i<n;i++){
        if(s1[i]==s2[i]){
            cout<<'a';
            continue;
        }
        for(char c='a';c<='z';c++){
            if(check(c,i)){
                cout<<c;
                if(c!=s1[i])cnt++;
                if(c!=s2[i])cnt--;
                break;
            }
        }
    }
    cout<<endl;
}   

signed main(){
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++){
        cout<<"Case "<<i<<": ";
        solve();
    }
    return 0;
}

G. Greatest Common Divisor

标签：

数论，差分，gcd

题意：

给定一个数组，每次操作可以把整个数组加一，问我们最少可以通过多少次操作让这个数组 gcd > 1，无解的话输出-1。

题解：

对于一个数组的 gcd，可以转化为第一个元素和后面元素差分数组的gcd，然后对数组加一，那么差分数组的值不会变化，只会变化第一个数，对gcd进行因数分解，再判断与第一个数相差最小并且 gcd > 1 的最小值，需要分多钟情况，和判断的先后顺序。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N=1e6+10;

void solve(){
    int n,cnt=0;
    cin>>n;
    vector<int>a(n+1,0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]%2==0)cnt=1;
    }
    sort(a.begin(),a.end());

    int res=0;
    for(int i=1;i<=n;i++){
        res=__gcd(res,a[i]);
    }
    if(res>1){
        cout<<0<<endl;
        return;
    }
    if(!cnt){
        cout<<1<<endl;return;
    }
    

    res=0;
    for(int i=n;i>1;i--){
        res=__gcd(res,a[i]-a[i-1]);
    }
    if(res==1){
        cout<< -1<<endl;
        return;
    }
    int ans=1e18;
    for(int i=2;i*i<=res;i++){
        if(res%i==0){
            int x=(i-a[1]%i)%i,y=(res/i-a[1]%(res/i))%(res/i);
            ans=min({ans,x,y});
        }
    }
    ans=min(ans,(res-a[1]%res)%res);
    cout<<ans<<endl;
}   

signed main(){
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++){
        cout<<"Case "<<i<<": ";
        solve();
    }
    return 0;
}

J.Stone Game

标签：

拓扑排序+博弈

题意：

给定一些石堆，相邻石堆之间有大小关系，每次操作可以把其中一颗石头丢掉，但是不能改变相邻之间的大小关系，谁无法操作那么谁就输了，Alice先手，问谁能赢。

题解：

1. 对于相邻的大小关系，可以建立有向边，那么对于这些关系，可以建成一个DAG
2. 对于这题可以确认最终状态，那么可以操作的次数就是总数减去最终态
3. 如果结果是奇数，那么先手必胜，偶数后手必胜
4. 对于构成的DAG可以用dp转移，得到最终态的数量

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
const int N=1e6+10;

void solve(){
    int n;
    cin>>n;
    vector<int>a(n+1,0),in(n+1,0),ans(n+1,0);
    vector<int>e[n+1];
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=2;i<=n;i++){
        if(a[i]>a[i-1])e[i-1].push_back(i),in[i]++;
        else e[i].push_back(i-1),in[i-1]++;
    }

    queue<int>Q;
    for(int i=1;i<=n;i++){
        if(in[i]==0)Q.push(i);
    }
    while(!Q.empty()){
        auto u=Q.front();
        Q.pop();

        for(auto v:e[u]){
            ans[v]=max(ans[u]+1,ans[v]);
            in[v]--;
            if(in[v]==0)Q.push(v);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        res+=a[i]-ans[i];
    }
    if(res%2!=0)cout<<"Alice\n";
    else cout<<"Bob\n";
}   

signed main(){
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++){
        cout<<"Case "<<i<<": ";
        solve();
    }
    return 0;
}