BestCoder Round #75 解题报告

1.King's Cake

#include<stdio.h>
#include<iostream>
using namespace std;
int ans;
void solve(int l,int w)
{
    if(weight == 0||weight == 0)
        return 0;
    int t,tl,tw;
    t = l/w;
    ans += t;
    tw = w;
    w = l%w;
    l = tw;
    solve(l,w);
}
int main(void)
{
    int length,weight,cas;
    cin >> cas;

    while(cas--)
    {
        int t;
        ans = 0;
        cin >> length >> weigth;
        t = length;
        if(length < weight){
            length = weight;
            weight = t;
        }
        solve(length,weigth);
        cout >> ans >> endl;
    }
    return 0;
}

2.King's Phone

#include <iostream>
#include<string.h>
#include<stdio.h>

using namespace std;
int M[10],a[3][3];
void Init()
{
    int i,j;
    for(i = 0;i < 3;i ++)
        for(j = 0;j < 3;j ++)
            a[i][j] = 0;
}
int  Judge(int len)
{
    int i,j;
    for(i = 2;i <= len;i ++)
        for(j = i+1;j <= len;j ++){
              if((M[i]-1)/3 == (M[i-1]-1)/3)
                {
                    if((M[i]-1)/3 == (M[j]-1)/3&&(  (M[i]-M[j])*(M[i-1]-M[j])  < 0))
                        return 0;
              }
              else
              {
                  if(  ((M[i]-1)/3-(M[j]-1)/3)*((M[i-1]-1)/3-(M[j]/3-1))  < 0)
                   return 0;
              }
        }
        return 1;
}
int main()
{
    int cas;
    char m[18];
    cin >> cas;
    getchar();
    while(cas --){
        cin.get(m,18);
        getchar();
        //cout << m << endl;
        Init();
        int len = strlen(m);
        //cout << "len=" << len << endl;
        //cout << len << endl;
        int j = 1;
        for(int i=0;i < len;i += 2){
            M[j ++] = m[i] - '0';
        }
        int ans = Judge(len/2+1);
        if(ans)
            cout << "valid" << endl;
        else
            cout <<"invalid" <<endl;
    }
}

3.King's Order

#include <iostream>
using namespace std;
long long dp[2001][26][4];    //dp[i][j][k]表示第i位为第'a' + j末位重复k次的方案数
void init()
{
    int i,j,k;
    for(i = 1;i <= 26;i ++)
    {
        for(j = 0;j < 26;j ++)
        {
            for(k = 1;k < 4;k ++)
                dp[i][j][k] = 0;
        }
    }
    for(i = 0;i < 26;i ++){
        dp[1][i][1] = 1;
        dp[1][i][2] = dp[1][i][3] = 0;
    }
}
int main()
{
    int cas,n;
    int i,j,k;
    long long ans;
    cin >>cas;
    while(cas --)
    {
        ans = 0;
        cin >> n;
        int i;
        init();
        for(i = 2;i <= n;i ++)
        {
            for(j = 0;j < 26;j ++)
            {
                for(k = 0;k < 26;k ++)
                {
                    if(k!=j)
                        dp[i][j][1] = (dp[i][j][1] + dp[i-1][k][1] + dp[i-1][k][2] + dp[i-1][k][3])%1000000007;
                    else if(k == j){
                        dp[i][j][2] = dp[i-1][k][1]%1000000007;
                        dp[i][j][3] = dp[i-1][k][2]%1000000007;
                    }
                }
                //cout << dp[i][j][1] << endl;
            }
        }
        for(i = 0;i < 26;i ++)
            ans = (ans + dp[n][i][1] + dp[n][i][2] + dp[n][i][3])%1000000007;
        cout << ans << endl;
    }
    return 0;
}