牛客网 - 2019黑龙江大学程序设计竞赛

Problem A Find the Nth Character

题目链接:https://ac.nowcoder.com/acm/contest/877/A

题意:定义一个字符串，求第n个字符是什么.
思路:模拟一下就行了，把前缀都减去,求出Si串，然后就判断是哪一个字符就行了。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i < n; i++)
            n -= i;
        n = (n - 1) % 26;
        printf("%c\n", n + 'a');
    }
    return 0;
}

Problem B Help Me

题目链接:https://ac.nowcoder.com/acm/contest/877/B

题意:计算下式:

思路:
完全平方公式，拆分，合并。对于ai的平方各有n-1个，-2aiaj各1个，即:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t, n;
    long long x, ans1, ans2;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        ans1 = ans2 = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &x);
            ans1 += x;
            ans2 += x * x;
        }
        printf("%lld\n", 1ll * n * ans2 - ans1 * ans1);
    }
    return 0;
}

Problem C Challenge IQ

题目链接:https://ac.nowcoder.com/acm/contest/877/C

题意:在n的所有全排列数组中相邻互质对数最多有几对。
题解:互质环，直接构造一个从1排列到n的环即可，因为相邻两个数互质，1与任何数互质，所以输入一个n，输出一个n。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("%d\n", n);
    }
    return 0;
}

Problem D Schedules

题目链接:https://ac.nowcoder.com/acm/contest/877/D

题意:有n个任务，有固定的开始和结束时间，同一个机器不能同时进行两个任务，求至少需要几台机器。
思路:求出某一时刻，需要的最多机器数就行了。

#include <bits/stdc++.h>
using namespace std;
int vis[100005];
int main() {
    int n, l, r, maxx = 0, max_ = 0;
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &l, &r);
        max_ = max(max_, r);
        vis[l]++;
        vis[r]--;
    }
    for (int i = 1; i <= max_; i++) {
        vis[i] += vis[i - 1];
        maxx = max(maxx, vis[i]);
    }
    printf("%d\n", maxx);
}

Problem E Pig-Palindromic

题目链接:https://ac.nowcoder.com/acm/contest/877/E

题意:求一个长度为偶数，而且对称位置分别为大写小写字母或者小写大写字母的子字符串的长度
思路:枚举相邻两点，向两边推。

#include <bits/stdc++.h>
using namespace std;
int main() {
    char str[5005];
    int cnt, len, max_ = 0;
    scanf("%s", str);
    len = strlen(str);
    for (int i = 0; i < len; i++) {
        cnt = 0;
        int l = i, r = i + 1;
        while (l >= 0 && r < len) {
            if (str[l] + 32 == str[r] || str[l] - 32 == str[r])
                cnt += 2;
            else break;
            l--, r++;
        }
        max_ = max(max_, cnt);
    }
    printf("%d", max_);
    return 0;
}

Problem F GCD Problem

题目链接:https://ac.nowcoder.com/acm/contest/877/F

题意:有两种操作:0代表将[l, r]之间的数变成√ai, 1代表求出[l, r]中所有数的最大公约数。
思路:线段数，因为1开根号还是1，故可以把结果为1的标记上，避免无用的计算。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
struct edge {
    bool Mark;
    long long val;
}segTree[MAXN << 2];
void Create(int root, int left, int right) {
    segTree[root].Mark = 0;
    if (left == right) {
        scanf("%lld", &segTree[root].val);
        return ;
    }
    int mid = left + ((right - left) >> 1);
    Create(root << 1, left, mid);
    Create(root << 1 | 1, mid + 1, right);
    segTree[root].Mark = segTree[root << 1].Mark && segTree[root << 1 | 1].Mark;
    segTree[root].val = __gcd(segTree[root << 1].val, segTree[root << 1 | 1].val);
}
void Update(int root, int Q_left, int Q_right, int left, int right) {
    if (segTree[root].Mark)
        return ;
    if (left == right) {
        segTree[root].val = sqrt(segTree[root].val);
        if (segTree[root].val == 1)
            segTree[root].Mark = 1;
        return ;
    }
    int mid = left + ((right - left) >> 1);
    if (Q_right <= mid)
        Update(root << 1, Q_left, Q_right, left, mid);
    else if (Q_left > mid)
        Update(root << 1 | 1, Q_left, Q_right, mid + 1, right);
    else {
        Update(root << 1, Q_left, mid, left, mid);
        Update(root << 1 | 1, mid + 1, Q_right, mid + 1, right);
    }
    segTree[root].Mark = segTree[root << 1].Mark && segTree[root << 1 | 1].Mark;
    segTree[root].val = __gcd(segTree[root << 1].val, segTree[root << 1 | 1].val);
}
long long Query_(int root, int Q_left, int Q_right, int left, int right) {
    if (Q_left <= left && Q_right >= right)
        return segTree[root].val;
    int mid = left + ((right - left) >> 1);
    if (Q_right <= mid)
        return Query_(root << 1, Q_left, Q_right, left, mid);
    else if (Q_left > mid)
        return Query_(root << 1 | 1, Q_left, Q_right, mid + 1, right);
    else return __gcd(Query_(root << 1, Q_left, mid, left, mid),
            Query_(root << 1 | 1, mid + 1, Q_right, mid + 1, right));
}
int main() {
    int n, m, left, right, Judge;
    scanf("%d", &n);
    Create(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        scanf("%d%d%d", &Judge, &left, &right);
        if (Judge)
            printf("%lld\n", Query_(1, left, right, 1, n));
        else Update(1, left, right, 1, n);
    }
    return 0;
}

Problem G Bash Game

题目链接:https://ac.nowcoder.com/acm/contest/877/G

题意:有一拍卖品成交价为P,两人轮流出价,至少加价1,最多加价M,两个人都足够聪明,求最后谁会拍下这个拍卖品.
思路:巴什博奕，当且仅当(n-1)%(m+1)==0时Bob能赢。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t, n, m;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d", &n, &m);
        if ((n - 1) % (m + 1))
            printf("Alice\n");
        else printf("Bob\n");
    }
    return 0;
}

Problem H Pass CET 6

题目链接:https://ac.nowcoder.com/acm/contest/877/H

题意:每天只能背一行或者一列的单词，求一个代表单词的矩阵，其值为这个单词最后背是第几天.
思路:可以申请两个一维数组，来表示第几行第几列是第几天背诵的，然后输出的时候判断一下该单词的行和列哪个是后来背的。

#include <bits/stdc++.h>
using namespace std;
int a[2][100005];
int main() {
    int n, m, t, v, w;
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= t; i++) {
        scanf("%d%d", &v, &w);
        a[v - 1][w] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            printf("%d ", max(a[0][i], a[1][j]));
        printf("\n");
    }
    return 0;
}

Problem I Center Street

题目链接:https://ac.nowcoder.com/acm/contest/877/I

题意：n个仓库，如果两个仓买A,B满足A是B的倍数，则A,B之间可以通一条路,当然这些路是双向的，A可以到B，B可以到A，如果仓买A,B之间通路，则过路费，从1号出发，求到每个仓库的最小花费。
题解：筛法。

#include <bits/stdc++.h>
using namespace std;
long long dp[500005]; // dp[i]代表从1~i的最小花费
int main() {
    int n;
    scanf("%d", &n);
    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + i; j <= n; j += i)
            dp[j] = min(dp[j], dp[i] + 1ll * (j - i) * (j - i));
    }
    for (int i = 1; i <= n; i++)
        printf("%lld ", dp[i]);
    printf("\n");
    return 0;
}

Problem J Special Distance

题目链接:https://ac.nowcoder.com/acm/contest/877/J

题意:求最大FST距离，即.
思路:我们可以令i>j,则上式有两种情况:
=i^2-j^2+Ai^2-Aj^2=i^2+Ai^2-(j^2-Aj^2);
或=i^2-j^2-Ai^2+Aj^2=i^2-Ai^2-(j^2-Aj^2);
故我们只需要分别求出i^2+Ai^2与i^2-Ai^2的最大最小值，然后求出最大最小值差的最大值。

#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int main() {
    int t, n;
    long long A, a, b, c, d, x, y;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        a = b = -INF, c = d = INF;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &A);
            x = 1ll * i * i, y = A * A;
            a = max(a, x + y), b = max(b, x - y);
            c = min(c, x + y), d = min(d, x - y);
        }
        printf("%lld\n", max(a - c, b - d));
    }
    return 0;
}

Problem K Maximum Sum of Digits

题目链接:https://ac.nowcoder.com/acm/contest/877/K

题意:将n分成两个数，使得两个数每一位的数字加起来最大.
思路:将n分离成最高项和其余项两项，然后把最高项的减一，另一项加一，使其出现最多的9。
例如:n=359=300+59=299+60, 则s(299)+s(60)=2+(3-1)*9+6+0=26;其中(3-1)指的是最高位后有多少个9.
n=99=90+9=89+10, 则s(89)+s(10)=8+(2-1)*9+1+0=18;
n=2568=2000+568=1999+569, 则s(1999)+s(569)=1+(4-1)*9+5+6+9=48。

#include <bits/stdc++.h>
using namespace std;
int main() {
    char s[15];
    int ans, len, c, t;
    scanf("%d", &t);
    while (t--) {
        c = 1;
        ans = 0;
        scanf("%s", s);
        len = strlen(s);
        ans += s[0] - '0' + (len - 1) * 9 - 1;
        for (int i = len - 1; i > 0; i--) {
            s[i] += c;
            c = (s[i] - '0') / 10;
            s[i] = (s[i] - '0') % 10 + '0';
            ans += s[i] - '0';
        }
        printf("%d\n", ans + c);
    }
    return 0;
}