突然6道题。有点慌。比赛写了五个。罚时爆炸。最后一个时间不太够+没敢写就放弃了。
两道题奇奇怪怪的WJ和20/20。今天的评测机是怎么了。
#include <bits/stdc++.h>
using namespace std; inline int read() {
int x = , f = ; char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }
while (ch >= '' && ch <= '') { x = x * + ch - ; ch = getchar(); }
return x * f;
} const int N = ;
char s[N]; int main() {
int n = read(), k = read();
scanf("%s", s + );
for (int i = ; i <= n; i++) {
if (i == k) putchar(s[i] + 'a' - 'A');
else putchar(s[i]);
}
puts("");
return ;
}
因为写了 a>=0 WA了两发。
#include <bits/stdc++.h>
using namespace std; inline int read() {
int x = , f = ; char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }
while (ch >= '' && ch <= '') { x = x * + ch - ; ch = getchar(); }
return x * f;
} const int N = 1e5 + ;
char s[]; int main() {
cin >> s;
int ret = ;
int a = (s[] - '') * + s[] - '';
if (a <= && a > ) ret++;
a = (s[] - '') * + s[] - '';
if (a <= && a > ) ret += ;
if (ret == ) puts("NA");
if (ret == ) puts("MMYY");
if (ret == ) puts("YYMM");
if (ret == ) puts("AMBIGUOUS");
return ;
}
第一次在这上面写概率题。
精度要求居然到了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 = , f = ; char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }
while (ch >= '' && ch <= '') { x = x * + ch - ; ch = getchar(); }
return x * f;
} int bin[]; int main() {
bin[] = ;
for (int i = ; i < ; i++) bin[i] = bin[i - ] * ;
int n = read(), k = read();
long double ans = ;
for (int i = ; i <= n; i++) {
for (int j = ; j >= ; j--) {
if (1LL * bin[j] * i < 1LL * k) {
ans += (long double) / (long double)bin[j + ];
cout << j + << '\n';
break;
}
}
}
if (n >= k) ans += (long double)(n - k + );
printf("%.10Lf\n", (ans / (long double)n - 1e-));
return ;
}
题意：对一棵树上的节点染成黑或白色，所有相同颜色的点对，他们之间的距离必须为偶数
思路：直接DFS，距离为偶数就涂成一样的，为奇数就涂成相反的，这样的结果一定是对的，因为偶数+偶数结果还是偶数，这样三个结点会被涂成一样的，奇数+奇数=偶数 会被涂成0 1 0 这样结果还是对的
#include <bits/stdc++.h>
using namespace std; inline int read() {
int x = , f = ; char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }
while (ch >= '' && ch <= '') { x = x * + ch - ; ch = getchar(); }
return x * f;
} const int N = 1e5 + ;
bool vis[N];
int n, head[N], cnt, ans[N];
struct Edge { int v, next, w; } edge[N * ];
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] = ;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (vis[v]) continue;
if (edge[i].w & ) dfs(v, c ^ );
else dfs(v, c);
}
} int main() {
n = read();
for (int i = ; i < n - ; i++) {
int u = read(), v = read(), w = read();
add(u, v, w);
}
dfs(, );
for (int i = ; i <= n; i++) printf("%d\n", ans[i]);
return ;
}
题意：有n个数，要不为1要不为2，现在有m对关系 $a_{i} + b_{i} + z_{i}$是偶数，问最少要知道几个数，能知道所有的数。
思路：其实就是问这些数组成了几个连通块，一个连通块里面知道一个数之后其他的数就都能知道了，画个图就知道了。DFS即可
#include <bits/stdc++.h>
using namespace std; inline int read() {
int x = , f = ; char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }
while (ch >= '' && ch <= '') { x = x * + ch - ; ch = getchar(); }
return x * f;
} const int N = 1e5 + ;
struct Edge { int v, next;} edge[N * ];
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] = ;
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 = ; i < m; i++) {
int a = read(), b = read(); int c = read();
add(a, b);
}
int ans = ;
for (int i = ; i <= n; i++) {
if (!vis[i]) {
ans++;
dfs(i);
}
}
printf("%d\n", ans);
return ;
}
题意：给一个数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 = , f = ; char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }
while (ch >= '' && ch <= '') { x = x * + ch - ; ch = getchar(); }
return x * f;
} int main() {
int n = read(), k = read();
if (k >= ( << n)) {
puts("-1");
return ;
}
if (n == ) {
if (k != ) puts("-1");
else puts("0 1 1 0");
return ;
}
for (int i = ; i < ( << n); i++) if (i != k) printf("%d ", i);
printf("%d ", k);
for (int i = ( << n) - ; i >= ; i--) if (i != k) printf("%d ", i);
printf("%d", k);
puts("");
return ;
}