Codeforces ZeptoLab Code Rush 2015

In this problem you will meet the simplified model of game King of Thieves.

In a new ZeptoLab game called "King of Thieves" your aim is to reach a chest with gold by controlling your character, avoiding traps and obstacles on your way.

An interesting feature of the game is that you can design your own levels that will be available to other players. Let's consider the following simple design of a level.

A dungeon consists of n segments located at a same vertical level, each segment is either a platform that character can stand on, or a pit with a trap that makes player lose if he falls into it. All segments have the same length, platforms on the scheme of the level are represented as'*' and pits are represented as '.'.

One of things that affects speedrun characteristics of the level is a possibility to perform a series of consecutive jumps of the same length. More formally, when the character is on the platform numberi₁, he can make a sequence of jumps through the platformsi₁ < i₂ < ... < i_k, ifi₂ - i₁ = i₃ - i₂ = ... = i_k - i_k - 1. Of course, all segments i₁, i₂, ...i_k should be exactly the platforms, not pits.

Let's call a level to be good if you can perform a sequence of four jumps of the same length or in the other words there must be a sequencei₁, i₂, ..., i₅, consisting offive platforms so that the intervals between consecutive platforms are of the same length. Given the scheme of the level, check if it is good.

The first line contains integer n (1 ≤ n ≤ 100) — the number of segments on the level.

Next line contains the scheme of the level represented as a string ofn characters '*' and '.'.

If the level is good, print the word"yes" (without the quotes), otherwise print the word"no" (without the quotes).

In the first sample test you may perform a sequence of jumps through platforms2, 5, 8, 11, 14.

题目大意：给个字符串，问能不能找到连续5个下标成等差数列的位置上字符都为' * '的情况

题目分析：数字小，暴力枚举公差，然后模拟

#include <cstdio>
#include <cstring>
char s[105];
int a[105];

int main()
{
    int len;
    bool flag = false;
    scanf("%d %s", &len, s);
    int d = 1;
    while(d <= len / 4)
    {
        for(int i = 0; i < len; i++)
        {
            if(s[i] == '*' && s[i + d] == '*' && s[i + 2 * d] == '*' && s[i + 3 * d] == '*' && s[i + 4 * d] == '*')
            {
                flag = true;
                break;
            }
        }
        d ++;
        if(flag)
            break;
    }
    if(flag)
        printf("yes\n");
    else
        printf("no\n");
}   

题目大意：一颗满二叉树，每条路上有一个权值表示灯的个数，现在要从根到所有叶子的路径上灯个数总和相同，问至少需要添加多少灯

题目分析：若要相等，显然兄弟到父亲路径上的灯数要一样，因此直接从叶子向上模拟即可，将灯数不断累加给父亲一直到根，每次兄弟到父亲路径上的差值的和就是最少需要补充的灯数

#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[5000];

int main()
{
    int ans = 0;
    scanf("%d", &n);
    for(int i = 2; i <= (1 << (n + 1)) - 1; i++)
        scanf("%d", &a[i]);
    for(int i = (1 << (n + 1)) - 1; i >= 2; i -= 2)
    {
        ans += abs(a[i] - a[i - 1]);
        a[i / 2] += max(a[i], a[i - 1]);
    }
    printf("%d\n", ans);
}

题目大意：红糖有wr克，每克能得到hr的幸福值，蓝糖有wb克，每克能得到hb的幸福值，现在问最多吃c克能得到的最大幸福值

题目分析：这样的数据量显然不能用背包做，采用部分贪心策略，及另lcm为wr和wb的最小公倍数，如果c % lcm == 0且c / lcm >= 2，则对于容量为w1 = c / lcm - 1（这里减1是因为保证结果尽可能的大，如果直接取c/lcm的话不能除尽的部分可能会有很多空余位置）的部分我们可以直接贪心，结果记为sum，sum ＝w1 * max(lcm / wb * hb，lcm / wr * hr)，剩下的部分直接枚举，枚举的时候取min(c / wr，c / wb)作为上界，这样可以防止超时。不妨假设wr比wb大，若wr数值很大，则枚举的时候c / wr就很小，若wr很小，则c ＝ c % lcm后c就很小，则此时c / wr还是很小，由此可得本题部分贪心＋部分暴力的方法是可行的

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std; 

ll Gcd(ll a, ll b)
{
    return b ? Gcd(b, a % b) : a;  
}

ll Lcm(ll a, ll b)
{
    return a * b / Gcd(a, b);
}
int main()
{
    ll c, h1, h2, w1, w2, ans = 0; 
    //scanf("%lld %lld %lld %lld %lld", &c, &w1, &h1, &w2, &h2);
    scanf("%I64d %I64d %I64d %I64d %I64d", &c, &h1, &h2, &w1, &w2);
    ll lcm = Lcm(w1, w2);
    ll tmp = c / lcm;
    c = c % lcm;
    if(tmp)
    { 
        tmp --; 
        c += lcm; 
    } 
    ll sum = tmp * (max(lcm / w1 * h1, lcm / w2 * h2));
    if(w1 < w2)
    {
        swap(w1, w2);
        swap(h1, h2);
    }
    for(int i = 0; i <= c / w1; i++)
        ans = max(ans, i * h1 + (c - i * w1) / w2 * h2);
    ans += sum;
    printf("%I64d\n", ans);
    //printf("%lld\n", ans);
}

题目大意：给一个长为n的字符串，对于其前缀子串，如果满足A+B+A+B+...+这样的形式，并且刚好有k＋1个A和k个B，则对应位置值为1否则为0，注意A和B可能是空串

题目分析：非常纠结的一道题，首先想到的是枚举一个周期的串长，联想到kmp里的next数组的一个性质，即i - next[i]就表示长度为i的前缀串中的周期串的一个周期的串长，先求next数组，注意这里求的next数组和一般kmp里的next数组不太一样，因为这里对任意前缀串它的前后缀子串不能有重叠的部分，比如ababaa，如果在普通next数组里会是-1 0 0 1 2 3，而我们目标的next数组为-1 -1 0 1 2 0

s         a  b   a   b   a   a

i          0  1   2   3   4   5

next  -1  -1  0   1   2   0

len     1   2  2    2  2   5

next里第二个为－1是因为它对应的是当前位置，若是0的话则1-next[1] = 1显然周期串长为2(ab)

得到next数组后，我们要计算几个值，len表示周期串长，num表示周期，t表示周期不能被k整除的部分，可以发现若t==0，则肯定可以找到可行方案，因为整除的话，根据周期的可加性，例如k＝2我们必然可以得到_A_A_这样的串，现在讨论t不等于0时，如果不是一个完整的周期串，t要加1，把周期去掉不能整除的部分再分成k份，若每份的个数小于t，则显然没有可行方案，反之存在可行方案

#include <cstdio>
#include <cstring>
int const MAX = 1e6 + 5;

char s[MAX];  
int next[MAX];  
int n, k;

void get_next()
{ 
    int j = -1; 
    next[0] = -1; 
    for(int i = 1; i < n; i++)
    { 
        while(j != -1 && s[j + 1] != s[i])
            j = next[j]; 
        if(s[j + 1] == s[i] ) 
            j++; 
        next[i] = j; 
    } 
}

int main() 
{
    scanf("%d %d %s", &n, &k, s);
    get_next();
    for(int i = 0; i < n; i++) 
    {
        int len = i - next[i];   
        int num = (i + 1) / len;   
        int t = num % k; 
        if(t == 0)
            printf("1");
        else
        {
            if(len * num != i + 1) 
                t ++;
            if((num - (num % k)) / k >= t) 
                printf("1");
            else 
                printf("0");
        }
    }
    printf("\n");
}