Press "Enter" to skip to content

第一次选拔赛题解

A: 签到

思路

签到题。把两个字符串之间每个字母的差的绝对值相加即可。

#include<bits/stdc++.h>
using namespace std;
int x[30],y[30];
int main()
{
    string a,b;
    int len;
    while(cin>>a>>b)
    {
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        len=0;
        for(int i=0;i<a.length();i++)
            x[a[i]-'a']++;
        for(int i=0;i<b.length();i++)
            y[b[i]-'a']++;
        for(int i=0;i<26;i++)
            len+=abs(x[i]-y[i]);
        cout<<len<<endl;
    }
}

B: 合体进化

思路:

由于每次合体都会算能量,还要求最小,每步贪心地选取最小的两个数相加即可。高中数学也学过从小到大的序列分步和最小。需要注意的是,每次合体之后能量值的更新要加五后再重新入队。数据范围 1e5 ,所以不能使用sort,优先队列即可。

代码:

#include<bits/stdc++.h>
using namespace std;

int main()
{
    long long n,t,sum=0,tmp=0;
    priority_queue<long long,vector<long long>,greater<long long> >q;
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&t);
        q.push(t);
    }
    if(q.size()==1)
        cout<<0;
    else
    {
        int s=q.size();
        for(int i=0;i<s-1;i++)
        {
            tmp=q.top();
            q.pop();
            tmp=tmp+q.top();
            q.pop();
            sum=sum+tmp;
            tmp+=5;
            q.push(tmp);
        }
        cout<<sum;
    }
    return 0;
}

C: 炉石传说

思路:

该题题意不是很好理解,仔细读懂样例之后模拟即可。
在此解读一下,例如:

2
MXXXXX
XXXMMM

对于MXXXXX,XX首先掌握手机控制权,经过一次交易使XX帮MM出一次牌,后XX出牌5次。但如果交换手机控制权,则需要两次交易才能达成。
对于XXXMMM,开始XX出牌3次,经过一次交易后MM获得手机控制权出牌3次,再经过一次交易后XX获得手机控制权。

要注意一下处理最前和最后的手机控制权,因为是XX的手机,所以我们在原字符串前面加上X后面加上XX之后从头到尾进行模拟即可。
模拟部分用ctr表示当前的手机控制权,然后逐步判断当前状态是交易出牌的代价小还是交换控制权的代价小就OK了。

代码

#include<bits/stdc++.h>
using namespace std;
int a[1000100]={0};
void M()
{
    string s;
    string str="X";
    cin>>s;
    str=str+s;
    str=str+"XX";
    bool ctr=1;
    int k=str.size(),i;
    int sum=0;
    for(i=0;i<k;i++)
    {
        if(str[i]=='X')
            a[i]=1;
        if(str[i]=='M')
            a[i]=0;
    }
    for(i=0;i<=k-3;i++)
    {
        if(a[i]==ctr&&a[i+1]!=ctr&&a[i+2]==ctr)
        {
            sum++;
            i++;
            continue; 
        }
        if(a[i]==ctr&&a[i+1]==ctr&&a[i+2]==ctr)
        {
            continue;
        }
        if(a[i+1]!=ctr&&a[i+2]!=ctr)
        {
            sum++;
            ctr=!ctr;
        }
    }
    cout<<sum<<endl;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
        M();
}

D: 瑄瑄发钱啦

思路:

把所有种类纪念币分到A堆和B堆,假设现在所有都在A堆。
假设排个序,先找到一个j 使得:

sum{a[1],…,a[j],a[j+1]} > sum/2
即 sum{a[1],…,a[j]} <= sum/2

把1到j放到B堆
然而我们要尽量将B堆凑到sum/2
剩余的部分:rest = sum/2 – sum{a1…n}
对A堆的a[j+1]….a[n],这里每一部分的大小一定是大于rest的
所以只用一堆a[j+1]我们就可以弥补掉rest使其凑得sum/2(和a[n]同时发出),而a[n]显然不能和a[n]同时发出,所以如果j+1==n的时候 答案为rest
j+1==n的时候 当且仅当 sum/2>=sum-max{a1..n}
这里的sum/2都是向下取整的,所以如果sum为奇数要+1

代码

#include<bits/stdc++.h>
using namespace std;

int t,n,a[1005];
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        int ma=0,sum=0,ans=0;
        for(int i=1;i<=n;++i) {
            scanf("%d",&a[i]);
            sum += a[i];
            if(a[i]>ma) ma=a[i];
        }
        ans = sum/2 - ( sum - ma );
        ans = (ans >= 0 ? ans : 0);
        printf("%d\n",ans*2+(sum&1));
    }
    return 0;
}

E: 时间转换

思路

读入的时候%d不回读完后面的空格 所以要getchar()
然后读入一行再分割,并看一看后面有没有多的空格
用map存一下字符对应的值
分割完将罗马字符串处理成对应的数字,处理原则如描述
小于10的时候前面要加0

代码

#include<bits/stdc++.h>

using namespace std;
int n,n1,n2,n3;
unordered_map<char,int> mp;
int ss[50];
int work(string& s) {
    int len = s.length();
    int res=0;
    for(int i=0;i<len;++i) ss[i] = mp[s[i]];
    for(int i=0;i<len;++i) {
        if(i<len&&ss[i]<ss[i+1]) res-=ss[i];
        else res+=ss[i];
    }
    return res;
}
int main() {
    cin >> n;
    getchar();
    mp['I']=1,mp['V']=5,mp['X']=10,mp['L']=50;
    while(n--) {
        string s;
        getline(cin,s);
        string::size_type p1 = s.find(":"),
            p2=s.rfind(":"),
            p3=s.rfind(" ");
        int f=1;
        if(p3==string::npos) f=0;
        string s1 = s.substr(0,p1),
               s2 = s.substr(p1+1,p2-p1-1),
               s3 = s.substr(p2+1,p3-p2-1);
        n1 = work(s1);
        n2 = work(s2);
        n3 = work(s3);
        if(f==1&&*(s.end()-2)=='P') n1+=12;
        if(n1<10) printf("0");
        printf("%d%s%d%s%d\n",n1,n2<10?":0":":",n2,n3<10?":0":":",n3);
    }
    return 0;
}

F: 神奇的三角形

思路:

水题。只要数出两两相邻的由三个c构成的三角形,不需要数大的三角形,即只需要以当前点为中心,判断当前c点的左、上,上、右,右、下,下、左是否都是c即可。数据只有1000×1000,所以O(n²)遍历即可。

#include<bits/stdc++.h>
using namespace std;

int a[1010][1010];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        for(int j=0;j<m;j++)
        {   
            if(s[j]=='c')
                a[i+1][j+1]=1;
            else
                a[i+1][j+1]=0;
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==1)
            {
                if(a[i][j-1]==1&&a[i-1][j]==1)
                    sum++;
                if(a[i-1][j]==1&&a[i][j+1]==1)
                    sum++;
                if(a[i][j+1]==1&&a[i+1][j]==1)
                    sum++;
                if(a[i+1][j]==1&&a[i][j-1]==1)
                    sum++;

            }
        }
    }
    cout<<sum<<endl;
}

One Comment

  1. wzq wzq 2018-07-20

    good

发表评论

电子邮件地址不会被公开。