牛客练习赛67 补题+题解算法

A.牛牛爱字符串
题意:给定字符串，输出当中的数字，注意不能有前导零。
简单模拟题，但格式要求非常严格，最后一个数字后不能有空格。还有一个坑点，如果只有0也是要输出一个0的。
我是用队列模拟，去掉前导零。

#include using namespace std; const int N = 1e5 + 10; string s; queue st[N]; int main() { while (getline(cin, s)) { int len = s.length(); int k = 0; for (int i = 0; i < len; i++) { if (s[i] >= '0' && s[i] <= '9') st[k].push(s[i] - '0'); else { if (st[k].size()) k++; } } for (int i = 0; i <= k; i++) { //int f = 0; while (st[i].size()) { int now = st[i].front(); if (now == 0 && st[i].size() != 1) st[i].pop(); else break; } } int f = 0; if (st[k].size()) f = 1; for (int i = 0; i <= k; i++) {while (st[i].size()) { int now = st[i].front(); st[i].pop(); cout << now; } if (f && i != k) cout << " "; else if (!f && i < k - 1) cout << " "; } cout << endl; } }

B.牛牛爱位运算
题意：任选n个数，要求&起来最大。
已知与只会变小，所以取一个最大值就可以.

#include using namespace std; int T; int main() { scanf("%d", &T); while (T--) { int n, x; int Max = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &x), Max = max(Max, x); printf("%d\n", Max); } }

C 牛牛爱博弈
题意:有n颗石子，要求一次可以拿2^k个，拿到最后一颗的人获胜
我们将2^k % 3, 发现答案是1， 2， 1， 2， 1， 2……
易得如果是3的时候，先手是必输的，可以推出任何3的倍数都是必输的.

#include using namespace std; int main() { int T; scanf("%d", &T); while (T--) { intn; scanf("%d", &n); if (n % 3 == 0) printf("Frame\n"); else printf("Alan\n"); } }

D 牛妹爱数列
题意：
你有一个01串和两种操作，
1.可以任意翻转前n个数
2.单点翻转一个数
问最少操作多少次可以得到一个0串
考虑dp
我们可以用dp1[i]代表将前i个数翻转成1所需的最少次数，
用dp0[i]代表将前i个数翻转成0所需要的最少次数
【牛客练习赛67 补题+题解】如果你想把前i个都变成0串，那么会有两种操作
1.将前i-1个数字都变成0，再将i变成0
2.将前i-1个数字都变成1，再翻转一次变成0

#include using namespace std; const int N = 1e5 + 10; int a[N], dp1[N], dp0[N]; int p[N]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } dp0[1] = (a[1] == 1); dp1[1] = 1 - dp0[1]; for (int i = 2; i <= n; i++) { dp1[i] = min(dp1[i - 1] + (a[i] != 1), dp0[i - 1] + 1); dp0[i] = min(dp0[i - 1] + (a[i] != 0), dp1[i - 1] + 1); } printf("%d\n", dp0[n]); }

E 牛妹游历城市
题意：
给n个城市，每个城市都有一个权值，权值按位与之后不为0的点之间可以连一条权值为lowbit(a[i], a[j])的边。
由于n的范围为1e5，因此不能枚举所有点。
我们考虑将每个点都拆成32位，建立32个超级源点，将每个点向自己的超级源点连一条边权为1<

#include using namespace std; typedef long long ll; const int INF = 1e16; const int N = 2e6 + 10; int T, n, tot; ll a[N], dis[N]; int head[N], vis[N]; inline int lowbit(int x) { return -x & x; }struct edge { int to, next; ll vi; }e[N<<1]; struct node { ll d; int now; bool operator < (const node& x) const { return d > x.d; } }; priority_queue q; void add(int u, int v, ll w) { e[tot].to = v; e[tot].vi = w; e[tot].next = head[u]; head[u] = tot++; } void dij() { for (int i = 1; i <= n; i++) { dis[i] = INF; } dis[1] = 0; q.push(node{ dis[1], 1 }); while (!q.empty()) { node p = q.top(); q.pop(); int u = p.now; if (vis[u]) continue; vis[u] = 1; for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if (dis[u] + e[i].vi < dis[v]) dis[v] = dis[u] + e[i].vi; if (!vis[v]) q.push(node{ dis[v], v }); } } }int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); tot = 0; memset(head, -1, sizeof head); memset(vis, 0, sizeof vis); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); }for (int i = 1; i <= n + 40; i++) dis[i] = INF; for (int i = 0; i < 32; i++) { for (int j = 1; j <= n; j++) { if ((a[j] >> i) & 1) { add(n + i + 1, j, 1ll << i); add(j, n + i + 1, 1ll << i); } } } dij(); if (dis[n] == INF) cout << "Impossible" << endl; else cout << (dis[n] / 2) << endl; } }

F 之后再补
ε=ε=ε=┏(゜ロ゜; )┛