A、牛牛爱字符串
提取全部的数字并且去掉前导0，我是写的python正则表达式re库和int。很方便而且正则用的也比较简单
import re
#浓浓的爬虫味...
findNumber = re.compile(r'.*?(\d+).*?')
while True:
try:
s = input()
list = re.findall(findNumber,s)
for item in list:
print(int(item), end=' ')
print()
except:
break B、牛牛爱位运算
选取一些数出来按位与，个数谁你挑
按照与的性质，只有1&1=1，所以你与的越多只会越来越小不可能变大
所以直接找出最大的哪个数就行了
T = int(input())
for _ in range(T):
a = list(map(int,input().split()))[1:]
print(max(a)) C、牛牛爱博弈
牛牛先手拿石子，牛妹后手，总石子个数给出是n，每次可以拿1,2,4,8,...2^k
问给出的石子总数n，每个人都最优选择下谁会赢得比赛
参考官方题解做法：
观察每次可拿石子在模3下的意义，你会发现1,2,1,2,1,2,1,2...
这样你会发现如果给出的n是3的倍数，每次先手取一个数，后手都可以取一个对应的数，让他模3仍为0，因为先手要么拿1要么拿2，后手一定有对应的数来拿。所以后手一定赢。
那么与之对应如果不是三的倍数，先手一定赢，先手可以拿掉n模3下的余数，让他变成3的倍数，与上方同理了。
T = int(input())
for _ in range(T):
n = int(input())
if n % 3 == 0:
print('Frame')
else:
print('Alan')
D、牛妹爱数列
给出长度为n的一组数，1e5的数据范围
每个数都是0或者1，你可以进行两种操作，把下标为x的数取非运算操作，第二种是把1~x下标全部取非运算操作。
问你最少变成全部变成0的操作数是多少？
考虑dp写法dp[i][0/1]代表前i个数都是0/1的最少方法数
那么可以找到状态转移方程
第一种情况：
当前位是0，dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1); //前一位都是0，或者前一位都是1，翻转1-(x-1)一次，次数+1
dp[i][1] = min(dp[i - 1][1] + 1, dp[i - 1][0] + 1); //前i-1个数是1，把i下标取反，前i-1个数都是0，把1-i全部取反
当前位是1，dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + 1); //与上方相同于此类推
dp[i][0] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1);
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;
int dp[N][2], a[N];
int main() {
int n = read();
for (int i = 1; i <= n; ++i) a[i] = read();
ms(dp, 0x3f); //可做可不做
dp[0][0] = dp[0][1] = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] == 0) {
dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1);
dp[i][1] = min(dp[i - 1][1] + 1, dp[i - 1][0] + 1);
}
else {
dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + 1);
dp[i][0] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1);
}
}
print(dp[n][0]);
return 0;
} E、牛妹游历城市
题目意思挺容易理解，选出两个下标如果值按位与不为0说明有边连，边权为lowbit下按位与，可看题目
坑点可能就在于范围是2^32，int最大只有2^31-1,要么开long long，要么注意unsigned int
那么题目很明确说明了要从1-n最短路，没有负权边，dijkstra几乎成为待考虑的算法。
而且边权链接是在按位与下，那么我们按照按位的操作下去吧32位分隔下同为1的连边在一起。
再跑一遍dijkstra就行了，在dijkstra里面从1开始往后面位连接的点跑，注意跑完一位1之后把这一位去掉。
防止下一个数又跑这一位，重复数据一直往堆里插东西，爆栈了。宝哥np！
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<ll, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline ll lowbit(ll x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 7;
ll a[N], dis[N];
bool vis[N];
vector<int> g[35];
int main() {
int T = read();
while (T--) {
for (int i = 0; i < 35; ++i) g[i].clear();
int n = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
for (int j = 0; j <= 32; ++j)
if (a[i] & (1ll << j))
g[j].push_back(i);
}
ms(dis, 0x3f), ms(vis, 0);
priority_queue<pai, vector<pai>, greater<pai>> pq;
pq.push({ 0,1 });
dis[1] = 0;
while (pq.size()) {
pai u = pq.top(); pq.pop();
if (vis[u.second]) continue;
vis[u.second] = true;
for (int i = 0; i <= 32; ++i) {
if ((a[u.second] & (1ll << i)) == 0) continue;
for (int j = 0; j < g[i].size(); ++j) {
int v = g[i][j];
if (v == u.second) continue;
ll w = lowbit(a[u.second] & a[v]);
if (u.first + w < dis[v]) {
dis[v] = u.first + w;
pq.push({ dis[v],v });
}
}
g[i].clear(); //看过一次之后就把该位链接的边都看过了，清除加快时间以及防止爆栈
}
}
if (dis[n] == INF) puts("Impossible");
else print(dis[n]);
}
return 0;
} 
京公网安备 11010502036488号