有毒的粽子

公告

Codeforces Round #603 (Div. 2)

A. Sweet Problem

簡單題，排個序判斷a+b與c的關系，＜就是a+b＞是（a+b+c）/2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[3];
int main()
{
    int t;
    scanf("%d",&t);
 
    for(int i=1;i<=t;++i)
    {
        scanf("%d%d%d",&a[0],&a[1],&a[2]);
        sort(a,a+3);
        ll ans=0;
        if(a[0]+a[1]<=a[2])ans=a[0]+a[1];
        else ans+=a[2]+(a[0]+a[1]-a[2])/2;
        printf("%lld\n",ans);
    }
    return 0;
}

View Code

B. PIN Codes

簡單題，將不超過10個相同的數改動最少位使之全部不同。顯然即使10個相同最多也只用改變一位，用桶排序判斷該數出現次數，改變數字隨便遍歷一位求解即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[100];
int b[10000];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(b,0,sizeof(b));
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i]);
            b[a[i]]++;
        }
        int ans=0;
        for(int i=0;i<10000;++i)
        {
            if(b[i]>1)ans+=b[i]-1;
        }
        printf("%d\n",ans);
        for(int i=1;i<=n;++i)
        {
            if(b[a[i]]==1)printf("%04d\n",a[i]);
            else
            {
                for(int j=1;j<=9;++j)
                {
                    if(a[i]%10+j>9)
                    {
                        if(b[a[i]+j-10]==0)
                        {
                            printf("%04d\n",a[i]+j-10);
                            b[a[i]+j-10]=1;
                            break;
                        }
                    }
                    else
                    {
                        if(b[a[i]+j]==0)
                        {
                            printf("%04d\n",a[i]+j);
                            b[a[i]+j]=1;
                            break;
                        }
                    }
                }
                b[a[i]]--;
            }
        }
    }
    return 0;
}

View Code

C. Everyone is a Winner!

題意是讓你輸出n除以n+1到1的數，輸出不重復的數字。數據范圍給到了1e9，寫了一個直接模擬的做法，可以發現sqrt（n）之前的數一定不同。所以可以直接輸出0-sqrt（n）的數，后面的在模擬即可。復雜度降到O（sqrt（n））。統計個數的時候最初用了sqrt（n）*2。發現會有一點誤差。所以是模擬算了一遍在輸出。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[100];
int b[10000];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int p=-1;
        int ans=sqrt(n)+1;
        for(int i=sqrt(n);i>=1;--i)
        {
            if(n/i==i)continue;
            ans++;
        }
        printf("%d\n0",ans);
        for(int i=1;i<=sqrt(n);++i)printf(" %d",i);
        for(int i=sqrt(n);i>=1;--i)
        {
            if(n/i==i)continue;
            printf(" %d",(n/i));
        }
        printf("\n");
    }
    return 0;
}

View Code

D. Secret Passwords

題意是給出若干組字符串，不同組字符串如果有相同元素，就可以合并起來，求合并后還剩幾組。應該是并查集的題目。由題意可知最多也只有26組。對于每組數據都讓他們向最小的字母合并，最后判斷該字母有沒有出現和并查集等于自身的個數即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
char s[N];
int b[30];
int f[30];
int c[30];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<30;++i)f[i]=i;
    for(int i=1;i<=n;++i)
    {
        scanf("%s",s);
        int len=strlen(s);
        for(int i=0;i<26;++i)b[i]=0;
        for(int j=0;j<len;++j)
        {
            b[s[j]-'a']++;
            c[s[j]-'a']++;
        }
        int flag=0;
        int t=0;
        for(int i=0;i<26;++i)
        {
            if(b[i])
            {
                if(flag==0)
                {
                    flag=1;
                    t=i;
                }
                else
                {
                    f[i]=t;
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<26;++i)if(c[i])ans++;
    for(int i=0;i<26;++i)
    {
        if(c[i]&&f[i]!=i)ans--;
    }
    printf("%d\n",ans);
    return 0;
}

View Code

posted on 2019-11-30 13:35 有毒的粽子閱讀(135) 評論(0) 收藏舉報

刷新頁面返回頂部