Ying

codeforces Contest 535

 
  • Apr 26, 2015

题目链接在这里

A. Tavas and Nafas

题意： 给定一个[0,99]的数，输出其英文表示

分析： 分情况输出即可

int main()
{
    ios::sync_with_stdio(0);
    string s1[] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    string s2[] = {"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
    string s3[] = {"twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
    int s;
    cin >> s;
    if (s < 10) {
        cout << s1[s] << endl;
    } else if (s < 20) {
        cout << s2[s - 10] << endl;
    } else {
        int d1 = s/10 - 2;
        int d2 = s%10;
        string r = s3[d1];
        if (d2 != 0) {
            r += "-";
            r += s1[d2];
        }
        cout << r << endl;
    }
    return 0;
}

B. Tavas and SaDDas

题意： lucky number只包含两个数字:4 7.给定一个已知是lucky number的数字，求出其所在的位置.

分析： 注意到个位数是2个，十位数是4个，百位数是8个，其实就是前面的数字列表按递增顺序末尾补上4,7，结果序列仍满足递增。例如4474，容易计算的是20 + 21 + 22，然后就是需要知道在4位数里的位置。将4444看成二进制0000,4447→0001，4474→0010，即再加上对应的二进制+1。

int main()
{
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    int m = n;
    int index = 1, digit_number = 0;
    while (n) {
        int b = n % 10;
        b = (b == 4 ? 0 : 1);
        index += b * qpow(2, digit_number);
        n /= 10;
        digit_number++;
    }
    for (int i = 1; i < digit_number; ++i) {
        index += qpow(2, i);
    }

    cout << index << endl;
    return 0;
}

C. Tavas and Karafs

题意： 下标为1高度递增的序列，高度定义为si=A + (i - 1)·B.定义m-bite operation为对任意最多m个不同元素，执行高度-1的操作。现在给定A，B，同时给n个queries。每个query包括(l, m, t)，要求不超过t次m-bite operation的情况下,将[l, r]的范围高度减为0，求这个最大的r。

分析：因为m-bite operation可以对任意元素操作，假设对范围[l,r]，只要满足高度和≤m·B，sr≤t即可。同时注意范围:1≤A,B≤106,1≤n≤105,1≤l,t,m≤106，如果对每个query，从l向右搜索找到最后一个满足条件的r，复杂度是O(n·l or r)，可能超时，因此采用二分查找。

LL A, B, n;
LL l, t, m, sl;
int r[100000] = {0};

bool f(LL s)
{
    LL smid = B * (s - 1) + A;
    LL sum = (s - l + 1) * (smid + sl) / 2;
    return sum <= m * t && smid <= t;
}

int main()
{
    ios::sync_with_stdio(0);
    cin >> A >> B >> n;
    for (int i=0; i<n; ++i) {
        cin >> l >> t >> m;
        LL left = l, right = 1000000;
        sl = B * (l - 1) + A;
        while (left < right) {
            LL mid = (left + right + 1) >> 1;
            if (f(mid))  {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        r[i] = f(left) ? left : -1;
    }

    for (int i=0; i<n; ++i) {
        cout << r[i] << endl;
    }
    return 0;
}

D. Tavas and Malekas

题意： 已知字符串p，p是s的子串，以及p在s中出现的所有位置的子序列，p s都只有小写英文字母组成，s的长度已知，求所有可能的s的个数。

分析： 对子序列迭代可以求出所有s中固定字母的位置，因为这些位置都需要匹配p。根据这两种情况：

  1. 如果前后两个位置没有重叠,那么前一个位置之后len(p)长度填充为p，固定字母.
  2. 如果前后两个位置重叠,那么需要确认下是否可以重叠,如果可以占用多少长度.
    举例说明2,假设p为”ababab”,yi为1,那么接下来yi+1可以为3,也可以为5,但不能是其他数字.
1 2 3 4 5 6 7 8 9 . . .
a b a b a b
    a b a b a b
        a b a b a b

其中L3,L4都可以,需要填充的长度分别为2,4.
于是想到KMP的next数组:
由next[6] = 4可以推出可以推进长度2得到L3 = 2.
由next[4] = 2可以推进长度2,加上之前的长度可以得到L4 = 4.

LL M = 1000000007;
const int len = 1000000;

int main()
{
    ios::sync_with_stdio(0);
    LL n, m, u = 0, r = 0, v_len = 1;
    char p[len] = {0}, s[len] = {0};
    int next[len] = {0}, y[len] = {0}, v[len] = {0};
    cin >> n >> m;
    cin >> p;
    //求KMP的next数组
    int i = 0, j = -1, len = strlen(p);
    next[i] = j;
    while (i < len) {
        while (j >= 0 && p[i] != p[j])
            j = next[j];
        ++i;
        ++j;
        next[i] = j;
    }
    //当有重叠部分时可以跳的长度,[1, v_len)
    while (i >= 1) {
        v[v_len] = v[v_len - 1] + i - next[i];
        ++v_len;
        i = next[i];
    }
    for (i = 0; i < m; ++i) {
        cin >> y[i];
    }
    //通过遍历p在s中出现的位置，计算s哪些位置字母需要固定
    for (i = 0; i < m; ++i) {
        //如果与上个位置没有重叠部分，i之后p长度的字母需要固定
        int delta = i > 0 ? y[i] - y[i - 1] : len;
        if (delta >= len) {
            u += len;
        } else {
            //如果与上个位置重叠，二分查找是否可用
            int index = -1, left = 1, right = v_len - 1;
            while (left <= right) {
                int mid = (left + right) >> 1;
                if (v[mid] > delta) {
                    right = mid - 1;
                } else if (v[mid] < delta) {
                    left = mid + 1;
                } else {
                    index = mid;
                    break;
                }
            }
            //重叠的位置不可用
            if (index == -1) {
                cout << 0 << endl;
                return 0;
            } else {
                u += v[index];
            }
        }
    }

    //n-u为s里可以自由选择字母的位置,powmod为指数求模.
    cout << powmod(26, n - u, M) << endl;

    return 0;
}
Search