BestCoder Round 75

题目链接：传送门

HDU 5640-5644

题目描述是复制的，有些乱码，大致意思能看懂。

King's Cake

Accepts: 960

Submissions: 1572

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

阅兵式前一天，是国王的生日，大臣们为他准备了一个

输入描述

第一行一个整数表示测试组数：

输出描述

共

输入样例

2
2 3
2 5

输出样例

3
4

Hint

对于第一组数据，可切出一个

#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
int main()
{
    int t,n,m,a,ans=0;
    cin>>t;
    while(t--)
    {
        ans=0;
        cin>>n>>m;
        if(n>m)
        swap(n,m);
        while(m%n)
        {
            ans+=m/n;
            a=n;
            n=m%n;
            m=a;
        }
        ans+=m/n;
        cout<<ans<<endl;
    }
    return 0;
}

King's Phone

Accepts: 310

Submissions: 2980

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

阅兵式上，国王见到了很多新奇东西，包括一台安卓手机。他很快对手机的图形解锁产生了兴趣。

解锁界面是一个  $s_1 s_2...s_k(0le s_i < INT\_MAX)s​1​​s​2​​...s​k​​(0≤s​i​​<INT_MAX)，他想知道这个密码序列是否合法，这个问题交给了你。$

输入描述

第一行一个整数表示测试组数： $s_1s_2...s_ks​1​​s​2​​...s​k​​。$

输出描述

共

输入样例

输出样例

invalid
valid
valid

Hint

对于第一组数据，

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
int vis[15];
int judge(int a,int b)
{
    if(a>b) swap(a,b);
    int c=b-a;
    if(c==2&&(a==1||a==4||a==7)&&!vis[(a+b)/2]) return 0;
    if(c==4&&a==3&&!vis[(a+b)/2]) return 0;
    //这里注意运算符运算顺序 逻辑与高于逻辑或 加括号
    if((c==6||c==8)&&!vis[(a+b)/2]) return 0;
    return 1;
}
int main()
{
    int t,k,a[15];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&k);
        int flag=1;
        if(k<4||k>9) flag=0;
        for(int i=0; i<k; i++)
        {
            scanf("%d",&a[i]);
            if(a[i]<1||a[i]>9) flag=0;
        }
        if(flag==0)
        {
            puts("invalid");
            continue;
        }
        memset(vis,0,sizeof(vis));
        vis[a[0]]=1;
        for(int i=1; i<k; i++)
        {
            vis[a[i]]++;
            if(!judge(a[i],a[i-1])||vis[a[i]]>1) flag=0;
            //if(!judge(a[i],a[i-1])) printf("%d
",i);
        }
        if(flag) puts("valid");
        else puts("invalid");
    }
    return 0;
}

King's Order

Accepts: 381

Submissions: 1361

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

国王演讲后士气大增，但此时战争还没有结束，国王时不时要下发命令。

由于国王的口吃并没有治愈，所以传令中可能出现：“让第三军-军-军，到前线去” 这样的命令。由于大洋国在军队中安插了间谍 ， 战事紧急，很多时候前线的指挥官不能分清哪些命令真正来自国王。但国王的命令有一个特点，他每次连续重复的字符最多

输入描述

第一行一个整数表示测试组数：

输出描述

共

输入样例

2
2
4

输出样例

676
456950

Hint

两个中没有不符合要求的，所以答案为  $26^4-26 = 45695026​4​​−26=456950$ 

这个题可以看做是数位DP：传送门。看成是斜着向右下传递。
也可以用递推做，a[i]=(a[i-1]+a[i-2]+a[i-3])*25;
a[i-k]表示结尾有长度为k个相同字符的序列,比如当i=4的时候 k=1,2,3就分别对应着数位DP中的dp[i][k]。
口口口C 
口口CC
口CCC
就是这个意思。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll a[2005];
void  get()
{
    memset(a,0,sizeof(a));
    for(int i=0; i<4; i++)
    {
        if(i>0) a[i]=a[i-1]*26;
        else a[i]=1;
    }
    for(int i=4; i<=2000;i++)
        a[i]=(a[i-1]+a[i-2]+a[i-3])*25%mod;
    }
int main()
{
    get();
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%lld
",a[n]);
    }
    return 0;
}

King's Game

Accepts: 249

Submissions: 671

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

为了铭记历史，国王准备在阅兵的间隙玩约瑟夫游戏。它召来了

输入描述

第一行一个整数表示测试组数：

输出描述

共

输入样例

2
2
3

输出样例

2
2

Hint

对于第一组数据，一开始报到

 约瑟夫环的简单变形，注意是从终态向始态递推，附上一个约瑟夫环的链接：传送门。

#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
    int ans,n,k,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        ans=0;
        //分析过程 约瑟夫环下标要倒着加回来 所以先加n-1再依次加n-2
        //i只是取余用的 实际上是从干掉最后一个人一直递归到干掉一个人之前的状态
        //所以是先加大的 最后加小的
        for(int i=2;i<=n;i++)
        ans=(ans+((n+1)-i))%i;
        printf("%d
",ans+1);
    }
    return 0;
}