@Dmaxiya 2018-08-17T02:28:48.000000Z 字数 5669 阅读 1772

Codeforces Round #458 (Div. 1 + Div. 2)

Codeforces

Contests 链接：Codeforces Round #458 (Div. 1 + Div. 2)
过题数：2
排名：1691/8398

A. Perfect Squares

题意

给定一个长度为 $n$ 的序列 $a_i$ ，找到这个序列中最大的开方不是整数的数字。

数据范围

$1\leq n\leq1000\\-10^6\leq a_i\leq10^6$

题解

按照题意跑一遍。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int n;
LL tmp;
bool judge(LL x) {
    if(x < 0) {
        return true;
    }
    LL xx = sqrt(x);
    if(xx * xx == x) {
        return false;
    }
    return true;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        LL ans = INT_MIN;
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &tmp);
            if(judge(tmp)) {
                ans = max(ans, tmp);
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

B. Conan and Agasa play a Card Game

题意

柯南和阿笠博士玩一场博弈游戏，给定 $n$ 张卡片，每张卡片上的数字为 $a_i$ ，对于每次操作，一方可以选择一张卡片，然后将其他所有小于该数字的卡片拿掉，最后无法进行操作的一方失败。柯南先手，如果两人都采取最优策略，问谁会获胜。

数据范围

$1\leq n\leq10^5\\1\leq a_i\leq10^5$

题解

如果最大的数字有 $t$ 个，如果 $t$ 为偶数，则先拿最大的数字的人必败，否则必胜，所以如果最大的数字有偶数个，则双方肯定尽量不先拿最大的数字，对于次大的数字也是如此，一直往小了找，如果某个数字出现的次数为奇数，则先拿到这个数字的一方必胜，所以先手一定会直接取这个个数为奇数的数字。所以只要存在个数为奇数的数字，先手必胜，否则必败。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int n, tmp;
bool flag;
map<int, int> mp;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        mp.clear();
        for(int i = 0; i < n; ++i) {
            scanf("%d", &tmp);
            ++mp[tmp];
        }
        flag = false;
        map<int, int>::iterator it;
        for(it = mp.begin(); it != mp.end(); ++it) {
            if(it->second % 2 == 1) {
                flag = true;
                break;
            }
        }
        if(flag) {
            printf("Conan\n");
        } else {
            printf("Agasa\n");
        }
    }
    return 0;
}

C. Travelling Salesman and Special Numbers

题意

定义一个操作，对于数字 $x$ ，进行一次操作后， $x$ 变为 $x$ 对应的二进制数中，数字 $1$ 的个数，例如， $13_{10}=1101_2$ 进行一次操作后变为 $3_{10}=11_2$ ，再进行一次操作后变为 $2$ 。现在，对于数字 $n$ ，询问从 $1$ 到 $n$ 中，最少进行 $k$ 次操作后变为 $1$ 的数字有多少个，输出对 $10^9+7$ 后的答案， $n$ 以二进制形式给出。

数据范围

$1\leq n\leq2^{1000},0\leq k\leq1000$

题解

对于 $2^{1000}$ 以内的数字，进行一次操作后，必然变成 $1000$ 以内的数字，所以可以先预处理出 $1000$ 以内的数字，至少进行多少次操作后变为 $1$ ，然后对 $1$ 到 $1000$ 的数字，询问哪些数字最少可以经过 $k-1$ 次操作变为 $1$ ，若数字 $x$ 可以经过 $k-1$ 次操作变为 $1$ ，则用数位 $dp$ 算出从 $1$ 到 $n$ 之间有多少个二进制中含有 $x$ 个 $1$ 的数字，加到答案上。注意特判 $k=0$ 和 $k=1$ 的情况。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
const int MOD = 1000000000 + 7;
char n[maxn];
int k, len, ans;
int step[maxn];
int dp[maxn][maxn][2];
int dfs(int pos, int r, int limit) {
    if(r < 0) {
        return 0;
    }
    if(pos == len) {
        if(r == 0) {
            return 1;
        } else {
            return 0;
        }
    }
    if(!limit && dp[pos][r][limit] != -1) {
        return dp[pos][r][limit];
    }
    int up = limit? (n[pos] - '0'): 1;
    int ans = 0;
    for(int i = 0; i <= up; ++i) {
        if(i == 1) {
            ans += dfs(pos + 1, r - 1, limit && i == n[pos] - '0');
            ans %= MOD;
        } else {
            ans += dfs(pos + 1, r, limit && i == n[pos] - '0');
            ans %= MOD;
        }
    }
    if(!limit) {
        dp[pos][r][limit] = ans;
    }
    return ans;
}
int get_one(int x) {
    int ret = 0;
    while(x != 0) {
        if(x % 2 == 1) {
            ++ret;
        }
        x /= 2;
    }
    return ret;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    step[1] = 0;
    for(int i = 2; i < maxn; ++i) {
        step[i] = step[get_one(i)] + 1;
    }
    while(scanf("%s%d", n, &k) != EOF) {
        if(k == 0) {
            printf("1\n");
            continue;
        }
        ans = 0;
        len = strlen(n);
        memset(dp, -1, sizeof(dp));
        for(int i = 1; i < maxn; ++i) {
            if(step[i] == k - 1) {
                ans += dfs(0, i, 1);
                ans %= MOD;
//                printf("dfs(%d) = %d\n", i, dfs(0, i, 1));
            }
        }
        if(k == 1) {
            --ans;
            ans = (ans + MOD) % MOD;
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Bash and a Tough Math Puzzle

题意

给定 $n$ 个数字的序列 $a_i$ ，进行 $q$ 次操作，每次操作有两种形式：

$1\quad l\quad r\quad x:$ 询问能否在区间 $[l,r]$ 上最多修改一个数字，使得该区间上所有数字都是 $x$ 的倍数；

$2\quad i\quad y:$ 将第 $i$ 个数字修改为 $y$ 。

对于每次询问，输出 $YES$ 或者 $NO$ 。

数据范围

$1\leq n\leq5\times10^5,1\leq q\leq4\times10^5\\ 1\leq a_i\leq10^9,1\leq l\leq r\leq n,1\leq x,y\leq10^9,1\leq i\leq n$

题解

用线段树存区间 $\gcd$ ，对于每次询问，判断区间 $[l,r]$ 上不是 $x$ 的倍数的数字是否多于一个，若多于 $1$ 个，则不是。判断的时候注意剪枝，若左子节点已经有多于两个数字不是 $x$ 的倍数，则不必判断右子节点。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 500000 + 100;
int n, q, command, l, r, x, Index, y;
int ans;
int Gcd[maxn << 2];
int gcd(int x, int y) {
    if(y == 0) {
        return x;
    }
    return gcd(y, x % y);
}
void push_up(int rt) {
    Gcd[rt] = gcd(Gcd[rt << 1], Gcd[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
    if(l == r) {
        scanf("%d", &Gcd[rt]);
        return ;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    push_up(rt);
}
void update(int Index, int tmp, int l, int r, int rt) {
    if(l == r) {
        Gcd[rt] = tmp;
        return ;
    }
    int m = (l + r) >> 1;
    if(Index <= m) {
        update(Index, tmp, l, m, rt << 1);
    } else {
        update(Index, tmp, m + 1, r, rt << 1 | 1);
    }
    push_up(rt);
}
int query(int L, int R, int tmp, int l, int r, int rt) {
    if(L <= l && r <= R) {
        if(Gcd[rt] % tmp == 0) {
            return 0;
        }
    }
    if(l == r) {
        return (Gcd[rt] % tmp != 0);
    }
    int m = (l + r) >> 1;
    int ret = 0;
    if(L <= m) {
        ret += query(L, R, tmp, l, m, rt << 1);
    }
    if(ret >= 2) {
        return 2;
    }
    if(R > m) {
        ret += query(L, R, tmp, m + 1, r, rt << 1 | 1);
    }
    if(ret >= 2) {
        ret = 2;
    }
    return ret;
}
void Print() {
    for(int i = 1; i <= 10; ++i) {
        printf("Gcd[%d] = %d\n", i, Gcd[i]);
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        build(1, n, 1);
        scanf("%d", &q);
        for(int i = 0; i < q; ++i) {
            scanf("%d", &command);
            if(command == 1) {
                scanf("%d%d%d", &l, &r, &x);
//                printf("l = %d  r = %d  x = %d\n", l, r, x);
                ans = query(l, r, x, 1, n, 1);
//                printf("ans = %d\n", ans);
                if(ans <= 1) {
                    printf("YES\n");
                } else {
                    printf("NO\n");
                }
            } else {
                scanf("%d%d", &Index, &y);
                update(Index, y, 1, n, 1);
//                Print();
            }
        }
    }
    return 0;
}

Codeforces Round #458 (Div. 1 + Div. 2)

A. Perfect Squares

题意

数据范围

题解

过题代码

B. Conan and Agasa play a Card Game

题意

数据范围

题解

过题代码

C. Travelling Salesman and Special Numbers

题意

数据范围

题解

过题代码

D. Bash and a Tough Math Puzzle

题意

数据范围

题解

过题代码

内容目录

选择主题