The 2014 ACM-ICPC Asia Mudanjiang Regional Contest 【部分题解】

﹏ヽ暗。殇╰゛Y 2022-08-13 03:59 114阅读 0赞

2014牡丹江亚洲区域赛邀请赛

B题：图论题目

[题解][Link 1]：[这里][Link 1]

K题：想法题

分析：两种变化，添加和交换，首先：星号是n的话最少需要的数字是n+1，那么可以首先判断数字够不够，不够的话现在最前面添数字，如果满足的话直接模拟如果数字不够的话把当前的星号和最后一个数字交换即可。

css函数可以不用。

AC代码：

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    int ccs(string s)
    {
        int ans=0,tmp = 0;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='*')
            {
                if(tmp<2)
                {
                    ans+=(2-tmp);
                    tmp = 1;
                    //printf("YES%d\n",i);
                }
                else
                {
                    tmp--;
                    //printf("NO\n");
                }
            }
            else
                tmp++;
        }
        return ans;
    }
    
    int check(string s,int x)
    {
        for(int  i = s.size()-1;i>x;i--)
        {
            if(s[i]!='*')
                return i;
        }
        return 0;
    }
    int solve(string s)
    {
        int len = s.size(),ans=0,tmp = 0;
        for(int i=0;i<len;i++)
        {
            if(s[i]=='*')
                tmp++;
        }
        int pps = 0;
        if((tmp+tmp+1)>len)
        {
            pps = tmp+tmp+1 - len;
            ans+=pps;
        }
        //printf("%d %d %d\n",tmp,ans,pps);
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='*')
            {
                if(pps>=2){
                    pps--;
                }
                else
                {
                    ans++;
                    int f = check(s,i);
                    swap(s[i],s[f]);
                    i--;
                    //cout<<s<<endl;
                }
            }
            else
                pps++;
        }
        return ans;
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int T;
        scanf("%d",&T);
        while(T--)
        {
            string s;
            cin>>s;
            //printf("CCS:%d\n",ccs(s));
            int ans = min(solve(s),ccs(s));
            printf("%d\n",ans);
        }
        return 0;
    }

I题：直接套用给出的第二个公式。

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <cmath>
    using namespace std;
    int n;
    double a[200];
    double solve(int x)
    {
        double ans = 0;
        for(int i=1;i<=n;i++)
        {
            double tmp = 0;
            if(a[i]==0)
                continue;
            if(x==2)
                tmp = a[i]*log2(a[i]);
            else if(x==5)
                tmp = a[i]*log(a[i]);
            else if(x==10)
                tmp = a[i]*log10(a[i]);
            //printf("TMP%lf, %lf\n",tmp, log2(a[i]));
            ans+=tmp;
        }
        return ans;
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int x;
            string s;
            cin>>n>>s;
            for(int i=1;i<=n;i++){
                scanf("%d",&x);
                a[i]=(double)x/100;
            }
            double ans=0;
            if(s=="bit")
                ans = solve(2);
            else if(s=="nat")
                ans = solve(5);
            else
                ans = solve(10);
            printf("%.12lf\n",-ans);
        }
        return 0;
    }

A题：水题。

求出第一个班的平均值 x 和第二个平均值 y ，如果 x 为整数则x -- ，y 变整数之后+1.就是ans

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int n,m;
            scanf("%d%d",&n,&m);
            int sum1=0,sum2=0;
            for(int i=1;i<n;i++)
            {
                int x;scanf("%d",&x);
                sum1+=x;
            }
            for(int i=0;i<m;i++)
            {
                int x;
                scanf("%d",&x);
                sum2+=x;
            }
            double p1 = (double)sum1 / (n-1);
            double p2 = (double)sum2 / m;
            //printf("%.5lf %.5lf\n",p1,p2);
            int mi = p1,ma = (int)p2+1;
            if(mi == p1)
                mi--;
            printf("%d %d\n",min(mi,ma),max(mi,ma));
    
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/y990041769/article/details/40046015