A、牛牛和牛可乐的赌约
正面不容易直接得到答案，那就 1 - 反面的答案。如果我们求得不是他输的概率而是赢的概率的话，那就十分好求答案就是，我们直接拿1减掉，再通过费马小定理，逆元运算求得MOD下的值即可。
#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 main() {
int T = read();
while (T--) {
ll a = read(), b = read();
ll ans = (qpow(a, b, MOD) - 1) * qpow(qpow(a, b, MOD), MOD - 2, MOD) % MOD;
print(ans);
}
return 0;
}
B、牛牛和牛可乐的赌约2
规律打表题，贴出我的Excel表格图就可以发现规律，当下标（i - j） % 3 = 0时先手就是输的。
#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 main() {
int T = read();
while (T--) {
ll n = read(), m = read();
if (abs(n - m) % 3)
puts("yyds");
else
puts("awsl");
}
return 0;
} C、单词记忆方法
括号递归处理，使用全局下标进行字符串遍历，依次对括号进行递归计算，再统计即可，注意开启long long。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
char s[N];
int i;
ll solve() {
ll ans = 0, tmp = 0;
for (; s[i]; ++i) {
int num = 0;
while (s[i] and isdigit(s[i])) {
num = num * 10 + s[i] - '0';
++i;
}
ans += tmp * (num ? num : 1);
tmp = 0;
if (isalpha(s[i]))
tmp = s[i] - 'A' + 1;
else if (s[i] == '(')
++i, tmp = solve();
else
break;
}
return ans + tmp;
}
int main() {
scanf("%s", s);
printf("%lld\n", solve());
return 0;
}
D、位运算之谜
#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;
// a = 9
// b = 1
// 10,1
// a = 1001
// b = 0001
// 11
// 01
// 01
// 11
// 111
// 001
int main() {
int T = read();
while (T--) {
ll n = read(), m = read();
n -= m * 2;
if (n < 0 or (n & m)) {
print(-1);
continue;
}
print(n);
}
return 0;
} G、牛牛和字符串的日常
std中string的用法以及二分。
对于每次输入的字符串，通过二分去查找前缀是否存在，累加计数即可。
#include <bits/stdc++.h>
using namespace std;
int main () {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string a,b;
cin >> a;
int T;
cin >> T;
int ans = 0;
while(T--){
cin >> b;
int l=1,r=b.size(),tmp=0;
while(l<=r){
int mid=l+r>>1;
if(b.find(a.substr(0,mid))!=b.npos)
tmp = mid, l = mid + 1;
else
r=mid-1;
}
ans += tmp;
}
cout<<ans<<'\n';
return 0;
}
H、上学要迟到了
建图思维+dijkstra最短路算法
最短路不难，这题主要思考如何建图出来，因为车子只会在起点开始，终点结束，说明每辆车都最多只有2个站台，但是人却可以往前往后走路前进，这时候我们把地图中的全部站台相邻两个之间通过无向图建立联系，时间花费就是走路的花费。并且记录当前下标处来的车是什么，如果这是第二次出现，说明到了终点站了，建立起点到终点之间的一条有向路。到此建图完毕，跑一边最短路算法即可得到最终答案。
#include <bits/stdc++.h>
using namespace std;
#define pai pair<int,int>
const int N = 2e5 + 7;
struct Node {
int v, w;
int next;
}edge[N << 1];
bool vis[N];
int head[N], dis[N], tot;
void add(int u, int v, int w) {
++tot;
edge[tot].v = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot;
}
void dijkstra(int s, int t) {
memset(vis, 0, sizeof vis);
memset(dis, 0x3f, sizeof dis);
priority_queue<pai, vector<pai>, greater<pai>> pq;
pq.push({ 0,s });
dis[s] = 0;
while (pq.size()) {
pai now = pq.top(); pq.pop();
int u = now.second;
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v, w = edge[i].w;
if (vis[v]) continue;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pq.push({ dis[v],v });
}
}
}
}
unordered_map<int, int> pre;
int a[N];
int main() {
int n, m, s, t, T;
scanf("%d %d %d %d %d", &n, &m, &s, &t, &T);
for (int i = 1; i <= m; ++i)
scanf("%d", a + i);
int x;
scanf("%d", &x);
pre[x] = 1;
for (int i = 2; i <= n; ++i) {
add(i - 1, i, T);
add(i, i - 1, T);
scanf("%d", &x);
if (pre[x]) add(pre[x], i, a[x]);
pre[x] = i;
}
dijkstra(s, t);
printf("%d\n", dis[t]);
return 0;
} I、迷宫
首先观察数据范围，
先试试，1e8的bool数组下随便测一下会不会MLE，发现不会！那就要把思维从BFS转变为递推了。
我们开启一个 dp[n][m][MOD]的三维数组，如果dp[i][j][c] = 1，说明在i,j处花费为c的情况可以被走到。
这样的话就变成一个动态规划问题，枚举各个点，再枚举一下c的取值，如果他上面某个点加上当前枚举的点花费刚好等于枚举的c，而且上方的点取值已经没确定是1的情况下，当前点的c值也赋值成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 = 1e4 + 7;
const int INF = 0x3f3f3f3f;
const int N = 100 + 7;
bool dp[N][N][MOD];
int a[N][N];
int main() {
int n = read(), m = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
a[i][j] = read();
dp[1][1][a[1][1] % MOD] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (i == 1 and j == 1) continue;
for (int k = 0; k < MOD; ++k) {
int c = ((k - a[i][j]) % MOD + MOD) % MOD;
if (dp[i - 1][j][c] or dp[i][j - 1][c])
dp[i][j][k] = 1;
}
}
int cnt = 0;
for (int i = 0; i < MOD; ++i)
cnt += dp[n][m][i];
print(cnt);
return 0;
}
J、树上行走
并查集，连通块维护。
维护一下每个连通块的大小，再合并的时候观察是不是同一个颜色的，还有最后注意大小等于最大的连通块全部都要输出。
#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 = 2e5 + 7; //节点数
const int M = 2e5 + 7; //路径数
int head[N], tot = 0;//前向星变量
struct Node {
int u; //起点
//int w; //权值
int v;
}edge[N];
int ans = 1;
int a[N];
int fa[N], sz[N];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int u, int v) {
int fu = find(u), fv = find(v);
fa[fv] = fu;
sz[fu] += sz[fv];
if (ans < sz[fu])
ans = sz[fu];
}
int main() {
int n = read();
for (int i = 1; i <= n; ++i) {
fa[i] = i, sz[i] = 1;
a[i] = read();
}
for (int i = 1; i < n; ++i) {
edge[i].u = read(), edge[i].v = read();
if (a[edge[i].u] != a[edge[i].v])
continue;
merge(edge[i].u, edge[i].v);
}
vector<int> res;
for (int i = 1; i <= n; ++i) {
if (sz[find(i)] == ans)
res.push_back(i);
}
print(res.size());
for (auto it : res)
print(it, 32);
return 0;
}
京公网安备 11010502036488号