2015多校3

多校

K-Work

题意

给定n(1<=n<=100)个结点的一棵树，求树上结点的子节点数为k(0<=k<n)的数目

思路

dfs 水题

AC代码

const int maxn = 105;
vector <int> edge[maxn];
int n, k;
int num[maxn];
int dfs(int x) {
    num[x] += edge[x].size();
    for (int i = 0; i < edge[x].size(); i ++) {
        num[x] += dfs(edge[x][i]);
    }
    return num[x];
}
int main() {
    while (~scanf("%d %d", &n, &k)) {
        for (int i = 1; i <= n; i ++) edge[i].clear();
        memset(num, 0, sizeof(num));
        for (int i = 1; i < n; i ++) {
            int u, v;
            scanf("%d %d", &u, &v);
            edge[u].push_back(v);
        }
        dfs(1);
        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            if (num[i] == k) ans ++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

D-Painter

题意

给定n*m的图，两种刷子，'R'表示红色，方向'\'，'B'表示蓝色，方向'/'，'G'表示绿色，是红色和蓝色叠加后的颜色，'R''B'表示的方格只能被刷一次，'G'则只能刷两次

思路

只要记录'R'方格左上角是否为'R'或'G'，如果不是，则一定需要从这个点开始用红刷子多刷一次，同理，判断'B'方格右下角是否'B'或'G'，需要注意'G'的情况。
这题没有给出m，需要根据读入得到m，恰好样例都是4*4的，实在是太坑了，以为是n*n的图，WA了一次。认真读题啊！！！

AC代码

const int maxn = 55;
char mp[maxn][maxn];
int main() {
    int T;
    scanf("%d", &T);
    while (T --) {
        int n, m;
        scanf("%d", &n);
        memset(mp, '.', sizeof(mp));
        for (int i = 1; i <= n; i ++) scanf("%s", &mp[i][1]);
        m = strlen(&mp[1][1]);
        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                if (mp[i][j] == 'R') {
                    if (mp[i-1][j-1] != 'R' && mp[i-1][j-1] != 'G') ans ++;
                } else if (mp[i][j] == 'B') {
                    if (mp[i+1][j-1] != 'B' && mp[i+1][j-1] != 'G') ans ++;
                } else if (mp[i][j] == 'G') {
                    if (mp[i-1][j-1] == '.' || mp[i-1][j-1] == 'B') ans ++;
                    if (mp[i+1][j-1] == '.' || mp[i+1][j-1] == 'R') ans ++;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B-RGCDQ

题意

定义F(i)：i不同的素数因子的个数，求区间[L,R]内max GCD(F(i), F(j)) (L <= i < j <= R)

思路