2013 ACM/ICPC 成都网络赛解题报告

时间：2022-04-03 09:24:33

第三题：HDU 4730 We Love MOE Girls

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4730

水题~~~

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

using namespace std;

typedef __int64 xiaohao;

typedef long long LL;

const int N=1090;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

const double eps=1e-7;

char s[N];

char ss[10]="nanodesu";

int main()

{

    int T,se=0;

    scanf("%d",&T);

    while(T--)

    {

        int m, n;

        scanf("%s",s);

        int len=strlen(s);

        printf("Case #%d: ", ++se);

        if(len<4)

        {

            printf("%s%s\n",s,ss);

            continue;

        }

        if(s[len-1]=='u'&&s[len-2]=='s'&&s[len-3]=='e'&&s[len-4]=='d')

        {

            for(int i=0;i<len-4;i++)

                printf("%c",s[i]);

            printf("%s\n",ss);

            continue;

        }

        printf("%s%s\n",s,ss);

    }

    return 0;

}

第四题：HDU 4731 Minimum palindrome

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4731

题解：规律题，我们可以发现当m大于等于3时，abcabcabc……这个串的回文为1，并且字典数最小，

m等以1时，直接输出n个a，

现在要解决的就是m=2的情况：

通过自己再纸上面写可以得出当n大于等于9时，最大的回文为4，要字典数最小，所以前四个都为a，后面也可以找到一个最小循环结：babbaa

但是还要讨论最后还剩余几个，如果是小于等于两个，那么添加2个a，否则按循环结添加。

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

using namespace std;

typedef __int64 xiaohao;

typedef long long LL;

const int N=100090;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

const double eps=1e-7;

const char tab[8][20] =

{ "a", "ab", "aab", "aabb", "aaaba", "aaabab", "aaababb", "aaababbb"};

int main()

{

    int T,se=0;

    scanf("%d",&T);

    while(T--)

    {

        int m, n;

        scanf("%d%d",&m,&n);

        printf("Case #%d: ", ++se);

        if(m>2)

        {

            int a = n / 3;

            int b = n % 3;

            for(int i=0;i<a;i++)

                printf("abc");

            for(int i=0;i<b;i++)

                printf("%c",'a'+i);

            printf("\n");

        }

        else if(m == 1)

        {

            for(int i=0;i<n;i++)

                putchar('a');

            printf("\n");

        }

        else

        {

            if(n < 9)

            {

                printf("%s\n", tab[n-1]);

            }

            else

            {

                char t[] = "babbaa";

                printf("aaaa");

                int a = (n-4) / 6;

                int b = (n-4) % 6;

                for(int i=0;i<a;i++) printf("babbaa");

                if(b <= 2) for(int i=0;i<b;i++) putchar('a');

                else for(int i=0;i<b;i++) putchar(t[i]);

                printf("\n");

            }

        }

    }

    return 0;

}

第七题：HDU 4734 F(x)

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4734

数位DP。

用dp[i][j][k] 表示第i位用j时f(x)=k的时候的个数，然后需要预处理下小于k的和，然后就很容易想了

dp[i+1][j][k+(1<<i)]=dp[i][j1][k];(0<=j1<=j1)

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

using namespace std;

typedef __int64 xiaohao;

typedef long long LL;

const int N=7000;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

const double eps=1e-7;

int dp[12][12][N];

int tsum[12][12][N];

int w[20];

void init()

{

    memset(dp,0,sizeof(dp));

    dp[0][0][0]=1;

    int n=10;

    for(int i=0;i<12;i++)

    {

        for(int j=0;j<n;j++)

        {

            for(int k=0;k<N-1;k++)

            {

                for(int k1=0;k1<n;k1++)

                {

                    int t1=k+k1*(1<<i);

                    dp[i+1][k1][t1]+=dp[i][j][k];

                }

            }

        }

    }

    memset(tsum,0,sizeof(tsum));

    for(int i=1;i<12;i++)

    {

        for(int j=0;j<n;j++)

        {

            for(int k=0;k<N-1;k++)

            {

                tsum[i][j][k]=tsum[i][j][k-1]+dp[i][j][k];

            }

        }

    }

}

int f(int x,int fa)

{

    if(x==0) return 0;

    int len=0;

    int flag=0;

    while(x)

    {

        w[++len]=x%10;

        x/=10;

    }

    int tsum1=0;

    for(int i=len;i>=1;i--)

    {

        for(int k=0;k<w[i];k++)

        {

            tsum1+=tsum[i][k][fa-flag];

        }

        flag+=(w[i])*(1<<(i-1));

        if(fa<flag)

            break;

    }

    return tsum1;

}

int main()

{

    init();

    int cas;

    while(~scanf("%d",&cas))

    {

        for(int q=1;q<=cas;q++)

        {

            int a,b;scanf("%d%d",&a,&b);

            int len=0;

            int fa=0;

            while(a)

            {

                int t1=a%10;

                fa+=(1<<(len))*t1;

                len++;

                a/=10;

            }

            int ans=f(b+1,fa);

            printf("Case #%d: %d\n",q,ans);

        }

    }

    return 0;

}

第十题：HDU 4737  A Bit Fun

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4737

水题，直接暴力~~~~

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

using namespace std;

typedef __int64 xiaohao;

typedef long long LL;

const int N=100090;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

const double eps=1e-7;

#define Maxn 110000

int sa[Maxn];

int main()

{

    int t,n,m;

    scanf("%d",&t);

    for(int ca=1;ca<=t;ca++)

    {

        int ans=0;

        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++)

            scanf("%d",&sa[i]);

        for(int i=1;i<=n;i++)

        {

            int ba=0;

            for(int j=i;j<=n;j++)

            {

                ba|=sa[j];

                if(ba>=m)

                    break;

                ans++;

            }

        }

        printf("Case #%d: %d\n",ca,ans);

    }

   return 0;

}

相关文章