HZNU 2019 Summer training 2

A - Digits Sequence Dividing

CodeForces - 1107A

题意：一串字符分成两串，第一串比第二串小

题解：长度大于2和等于2考虑

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
using namespace std;
#define ll long long

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        string s;
        scanf("%d",&n);
        cin>>s;
        if(n == 2)
        {
            if(s[0] >= s[1])
                puts("NO");
            else
            {
                puts("YES");
                printf("2
");
                printf("%c %c
",s[0],s[1]);
            }
        }
        else
        {
            puts("YES");
            puts("2");
            printf("%c ",s[0]);
            for(int i=1;i<s.size();i++)
                printf("%c",s[i]);
            cout<<endl;
        }
    }
}

View Code

B - Digital root

CodeForces - 1107B

题意：求第K个数位和为X的数字是多少

题解：找规律

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
using namespace std;
#define ll long long

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll k,x;
        scanf("%lld %lld",&k,&x);
        printf("%lld
",(k - 1) * 9 + x);
    }
}

View Code

C - Brutality

CodeForces - 1107C

题意：给n个数和一个值k，有一个26个字符的键盘，每个键不能连续按超过k次，现在给你一个按键序列和对于每次按键可以得到的权值，问最后可以得到的总权值是多少（注意如果按了k个a后按一个b的话又可以再按k次a）

题解：相同字段提取出来，累加上前k大

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
using namespace std;
#define ll long long

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;

int n,k;
int a[maxn];
int b[maxn];
char s[maxn];
queue<int>q;
bool cmp(int x,int y)
{
    return x > y;
}
ll sum = 0;
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;++i)
        scanf("%d",&a[i]);
    scanf("%s",s);
    int tot = 0;
    for(int i=0;i<n;)
    {

        char tmp = s[i];

        while(s[i] == tmp)
        {
            tot++;
            i++;
        }
        q.push(tot);

        tot = 0;
    }

    int id = 0;
    while(q.size())
    {
        //printf("%d**
",q.front());
        int ans = q.front();
        int m = ans;
        q.pop();
        int pos = 0;
        while(m--)
        {
            b[pos++] = a[id++];
        }
        sort(b,b+ans,cmp);
//        for(int i=0;i<ans;i++)
//            printf("%d ",b[i]);
//        cout<<endl;
        if(k >= ans)
        {
            for(int i=0;i<ans;i++)
                sum += b[i];
        }
        else
        {
            for(int i=0;i<k;i++)
                sum += b[i];
        }
    }
    printf("%lld
",sum);
}

View Code

D - Compression

CodeForces - 1107D

题意：十六进制的矩阵转换为二进制的矩阵，之后用x压缩矩阵，要求x整除n，并且原来矩阵中对应压缩后的矩阵的地方必须相等，求x

题解：矩阵转换之后按照每一行每一列的连续的1或者0分开，开始gcd，最后gcd的结果就是所求的x

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
using namespace std;
#define ll long long

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 5210;
int a,b,c,d;
void change(char ch)
{
    int tmp;
    if('0' <= ch && ch <='9')
    {
        tmp = ch - '0';
    }
    else
    {
        tmp = 10 + ch - 'A';
    }

    if(tmp >= 8)
    {
        a = 1;
        tmp -= 8;
    }
    else a = 0;

    if(tmp >= 4)
    {
        b = 1;
        tmp -= 4;
    }
    else b = 0;

    if(tmp >= 2)
    {
        c = 1;
        tmp -= 2;
    }
    else c = 0;

    if(tmp >= 1)
    {
        d = 1;
        tmp -= 1;
    }
    else d = 0;
}
int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b,a % b);
}
char s[maxn][maxn];
char str[maxn];
queue<int>que;
int main()
{
    int n;
    scanf("%d",&n);

    for(int i=0;i<n;i++)
    {
        scanf("%s",str);

        int pos = 0;
        for(int len=0;len<n/4;len++)
        {
            change(str[len]);
            s[i][pos++] = a;
            s[i][pos++] = b;
            s[i][pos++] = c;
            s[i][pos++] = d;
        }
    }

//    for(int i=0;i<n;i++)
//    {
//        for(int j=0;j<n;j++)
//            printf("%d",s[i][j]);
//        cout<<endl;
//    }

    for(int i=0;i<n;i++)
    {
        int tmp = s[i][0];
        int tot = 0;
        for(int j=0;j<n;j++)
        {
            if(tmp == s[i][j])
                tot++;
            else {
                tmp = s[i][j];
                que.push(tot);
                tot = 1;
            }
        }
        que.push(tot);
    }

    for(int j=0;j<n;j++)
    {
        int tmp = s[0][j];
        int tot = 0;
        for(int i=0;i<n;i++)
        {
            if(tmp == s[i][j])
                tot++;
            else
            {
                tmp = s[i][j];
                que.push(tot);
                tot = 1;
            }
        }
        que.push(tot);
    }
    int minn =  que.front();
    que.pop();
    while(!que.empty())
    {
       minn = gcd(minn,que.front());
       que.pop();
    }
    printf("%d
",minn);
}

View Code

E - Vasya and Binary String

CodeForces - 1107E

题意：一个长为n的01串，每次可以消去长度为 $l e n $

题解：记忆化搜索可以更好的体现转移方程

点击此处题解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string.h>
using namespace std;
#define ll long long
#define mem(a, b) memset(a, b, sizeof(a))
const int maxn = 1e2 + 10;
const int INF = 0x3f3f3f3f;

ll dp[maxn][maxn][maxn];
string s;
int a[maxn];

ll dfs(int l,int r,int k)
{
    if(l > r) return 0;
    if(l == r) return a[k + 1];
    if(dp[l][r][k] > 0) return dp[l][r][k];
    dp[l][r][k] = dfs(l,r - 1,0) + a[k + 1];
    for(int i = l; i < r; i++)
    {
        if(s[i] == s[r])
        {
            dp[l][r][k] = max(dp[l][r][k],dfs(l,i,k + 1) + dfs(i + 1,r - 1,0));
        }
    }
    return dp[l][r][k];
}
int main()
{
    int n;
    scanf("%d",&n);
    cin >> s;
    for(int i = 1; i <= n; i++)
        scanf("%d",&a[i]);
    memset(dp,-1,sizeof dp);
    //dfs(0,n - 1,0);
    cout << dfs(0,n - 1,0) <<endl;
}

View Code