A、小A买彩票
直接On^2跑出全部价格的组合方案数，在n张牌里面。
把3n到4n的方案数累加起来。
总方案数就是4^n去掉最大公约数在特判下就行了。
最坑在于0，不买就永远不亏……我枯了。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,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)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define pii pair<int, int>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pll pair<long long, long long>
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; 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]); }
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); }
ll dp[35][150];
int main() {
ll n = read();
if (n == 0) return puts("1/1"), 0;
dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1;
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= 4 * n; ++j)
for (int k = 1; k <= 4; ++k)
if (j - k >= 0) dp[i][j] += dp[i - 1][j - k];
ll up = 0, down = qpow(4, n);
for (int i = 3 * n; i <= 4 * n; ++i) up += dp[n][i];
ll tmp = gcd(up, down);
up /= tmp, down /= tmp;
if (!up) puts("0/1");
else if (up == down) puts("1/1");
else write(up), putchar('/'), write(down);
return 0;
}
B、「金」点石成金
dfs的裸题，不愧是被选上NC周练的题目
对于每个物品，存在题目给得两种操作，记得操作之后回溯，变负数了改成0。
也不需要减枝就可以A。直接跑就行了。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,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)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define pii pair<int, int>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pll pair<long long, long long>
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; 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]); }
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 N = 20;
int a[N], b[N], c[N], d[N];
ll ans, sum1, sum2;
int n;
void dfs(int x) {
if (x > n) {
if (sum1 * sum2 > ans) ans = sum1 * sum2;
return;
}
for (int i = 1; i <= 2; ++i) {
ll temp1 = sum1;
ll temp2 = sum2;
if (i & 1) {
sum1 += a[x];
sum2 -= b[x];
if (sum2 < 0) sum2 = 0;
}
else {
sum2 += c[x];
sum1 -= d[x];
if (sum1 < 0) sum1 = 0;
}
dfs(x + 1);
sum1 = temp1;
sum2 = temp2;
}
}
int main() {
n = read();
for (int i = 1; i <= n; ++i)
a[i] = read(), b[i] = read(), c[i] = read(), d[i] = read();
dfs(1);
printf("%lld\n", ans);
return 0;
}
E、Board
对于每个要求解得点，你会发现在整个地图来看，是存在相关性的。
如果不是第一行或第一列，直接把该行该列的第一行第一列元素一加，之前第一列和第一行累加的会累计到[1,1]去
那么类比第一行或者第一列的，把地图反转一下，去求[n,n]也是同样的。可以体会一下，精髓就是整个地图存在相关性。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,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)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define pii pair<int, int>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pll pair<long long, long long>
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; 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]); }
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 N = 1e3 + 7;
int mp[N][N];
int x, y;
int main() {
int n = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
mp[i][j] = read();
if (mp[i][j] == -1) {
x = i, y = j;
continue;
}
}
int ans = 0;
if (x == 1 || y == 1) ans = mp[x][n] + mp[n][y] - mp[n][n];
else ans = mp[1][y] + mp[x][1] - mp[1][1];
write(ans), putchar(10);
return 0;
}
京公网安备 11010502036488号