突然6道题。有点慌。比赛写了五个。罚时爆炸。最后一个时间不太够+没敢写就放弃了。

两道题奇奇怪怪的WJ和20/20。今天的评测机是怎么了。

 

A Changing a Character

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

const int N = 100;
char s[N];

int main() {
    int n = read(), k = read();
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++) {
        if (i == k) putchar(s[i] + 'a' - 'A');
        else putchar(s[i]);
    }  
    puts("");
    return 0;
}

View Code

 

B YYMM or MMYY

因为写了 a>=0 WA了两发。

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

const int N = 1e5 + 10;
char s[5];


int main() {
    cin >> s;
    int ret = 0;
    int a = (s[0] - '0') * 10 + s[1] - '0';
    if (a <= 12 && a > 0) ret++;
    a = (s[2] - '0') * 10 + s[3] - '0';
    if (a <= 12 && a > 0) ret += 2;
    if (ret == 0) puts("NA");
    if (ret == 1) puts("MMYY");
    if (ret == 2) puts("YYMM");
    if (ret == 3) puts("AMBIGUOUS");
    return 0;       
}

View Code

 

C Dice and Coin

第一次在这上面写概率题。

精度要求居然到了1e-9！

果断long double 但发现就是过不了第二个样例 最后答案-1e-10就好了

题意：有$n$种取值(1到$n$)，每次有1/2的概率能使这个值乘以2，问最后值大于等于$K$的概率

思路：$bin\left[i\right]$表示2的i次，然后从后往前找到第一个$i\times bin\left[ j\right] <k$的 这样$2^{j+1}$必定大于等于$K$了 到这里的概率就是$\dfrac {1}{2^{j+1}}$

对于$i\geq k$的部分 对答案的贡献就是1

最后答案除以$n$再减去1e-10就ok了

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int bin[30];

int main() {
    bin[0] = 1;
    for (int i = 1; i < 30; i++) bin[i] = bin[i - 1] * 2;
    int n = read(), k = read();
    long double ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 28; j >= 0; j--) {
            if (1LL * bin[j] * i < 1LL * k) {
                ans += (long double)1 / (long double)bin[j + 1];
                cout << j + 1 << '\n';
                break;
            }
        }
    }
    if (n >= k) ans += (long double)(n - k + 1);
    printf("%.10Lf\n", (ans / (long double)n - 1e-10));
    return 0; 
}

View Code

 

D Even Relation

题意：对一棵树上的节点染成黑或白色，所有相同颜色的点对，他们之间的距离必须为偶数

思路：直接DFS，距离为偶数就涂成一样的，为奇数就涂成相反的，这样的结果一定是对的，因为偶数+偶数结果还是偶数，这样三个结点会被涂成一样的，奇数+奇数=偶数 会被涂成0 1 0 这样结果还是对的

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

const int N = 1e5 + 10;
bool vis[N];
int n, head[N], cnt, ans[N];
struct Edge { int v, next, w; } edge[N * 2];
inline void add(int u, int v, int w) {
    edge[++cnt].v = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt;
    edge[++cnt].v = u; edge[cnt].w = w; edge[cnt].next = head[v]; head[v] = cnt;    
}

void dfs(int u, int c) {
    ans[u] = c;
    vis[u] = 1;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (vis[v]) continue;
        if (edge[i].w & 1) dfs(v, c ^ 1);
        else dfs(v, c);
    }
}

int main() {
    n = read();   
    for (int i = 0; i < n - 1; i++) {
        int u = read(), v = read(), w = read();
        add(u, v, w);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}

View Code

 

E 1 or 2

题意：有n个数，要不为1要不为2，现在有m对关系 $a_{i} + b_{i} + z_{i}$是偶数，问最少要知道几个数，能知道所有的数。

思路：其实就是问这些数组成了几个连通块，一个连通块里面知道一个数之后其他的数就都能知道了，画个图就知道了。DFS即可

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

const int N = 1e5 + 10;
struct Edge { int v, next;} edge[N * 4];
bool vis[N];
int n, m, cnt, head[N];
inline void add(int u, int v) {
    edge[++cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt++;
    edge[++cnt].v = u; edge[cnt].next = head[v]; head[v] = cnt++;
}
void dfs(int u) {
    vis[u] = 1;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (!vis[v]) dfs(v);
    }
}

int main() {
    n = read(), m = read();
    for (int i = 0; i < m; i++) {
        int a = read(), b = read(); int c = read();
        add(a, b);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            ans++;
            dfs(i);
        }
    }
    printf("%d\n", ans);
    return 0;
}

View Code

 

F XOR Matching

题意：给一个数n和k，问能不能构造出一个序列 满足 :

数字0到$2^{n} - 1$每个数出现两次且每对相同数字之间的区间异或和为k

思路：又是区间异或和的题。ABC121的D也是区间异或和的题 传送门

结论 n % 4 == 3时 $f(n)$ = 0 $f(n)$表示区间[0,n]的异或和

所以n = 1的时候需要特判 因为$2^{n} - 1$ = 1 1模4不等于3

k = 0的时候可以粘一下样例 不等于0的时候输出-1就行了

因为两个1之间的异或和肯定是0

当 $k\geq 2^{n}$的时候，不可能有几个数的异或和为k 因为k的最高位比$2^{n}-1$要高一位

所以输出-1

其他情况下

构造性出序列

0 1 2 ... k $2^{n} - 1$ ... 2 1 0 k

对于这个序列中除了k的所有相同的数对

中间均为2个相同的数和一个k 所以异或和为k

而对于k和另一个k 中间是 0 ~ $2 ^{n} - 1$少了k

又因为$f(2^{n}-1)$ = 0 所以少了一个k 区间异或和也为k

所以这样的构造是对的(表示想不到。)

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main() {
    int n = read(), k = read();
    if (k >= (1 << n)) {
        puts("-1");
        return 0;
    }
    if (n == 1) {
        if (k != 0) puts("-1");
        else puts("0 1 1 0");
        return 0;
    }
    for (int i = 0; i < (1 << n); i++) if (i != k) printf("%d ", i);
    printf("%d ", k);
    for (int i = (1 << n) - 1; i >= 0; i--) if (i != k) printf("%d ", i);
    printf("%d", k);
    puts("");
    return 0;
}

View Code