卡常狗能不能死一死啊
A. 构造87
bitset 瞎搞
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 50 + 10;
// bool st;
int n;
int a[N];
int x, y, z;
bitset<90> bt[15];
// bool en;
void solve()
{
cin >> x >> y >> z;
rep(i, 0, 10) bt[i].reset();
bt[0][0] = 1;
rep(i, 1, n)
{
if (i == x || i == y || i == z)
continue;
per(j, 9, 0)
{
bt[j + 1] |= (bt[j] << a[i]);
}
}
// rep(i, 1, 10) cerr << bt[i] << endl;
if (bt[10][87])
Yes;
else
No;
}
signed main()
{
freopen("87.in", "r", stdin);
freopen("87.out", "w", stdout);
// cerr<<(&en-&st)/1024.0/1024.0<<endl;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
cin >> n;
rep(i, 1, n) cin >> a[i];
cin >> testcase;
while (testcase--)
solve();
return 0;
}
B. 不休陀螺
容易想到尺取，st表维护区间max，树状数组维护前缀和即可
// bool st;
int n, e;
int a[N], b[N];
int res = 0;
int sum = 0;
int st[N][21];
int tmp = 0;
int pre[N];
vector<int> vec;
int lgg[N];
// bool en;
struct BIT
{
int tr[N];
void add(int x, int v)
{
// cerr << x << endl;
while (x <= n + 10)
{
tr[x] += v;
x += x & -x;
}
}
int sum(int x)
{
int res = 0;
while (x)
{
res += tr[x];
x -= x & -x;
}
return res;
}
} tr;
int get(int l, int r)
{
if (r < l)
return 0;
int t = lgg[r - l + 1];
return max(st[l][t], st[r - (1 << t) + 1][t]);
}
void solve()
{
rep(i, 2, 1e6) lgg[i] = lgg[i / 2] + 1;
io.read(n);
io.read(e);
rep(i, 1, n)
{
io.read(a[i]);
}
rep(i, 1, n)
{
io.read(b[i]);
if (a[i] < b[i])
st[i][0] = a[i];
else
st[i][0] = b[i];
pre[i] = pre[i - 1] - a[i] + b[i];
vec.push_back(pre[i]);
}
vec.push_back(0);
sort(ALL(vec));
vec.resize(unique(ALL(vec)) - vec.begin());
// cerr << vec.size() << endl;
rep(i, 0, n)
{
pre[i] = lower_bound(ALL(vec), pre[i]) - vec.begin() + 1;
// cerr << pre[i] << endl;
}
rep(i, 1, 20)
{
rep(j, 1, n - (1 << i) + 1)
{
st[j][i] = max(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);
}
}
for (int l = 1, r = 0; l <= n; l++)
{
while (r <= n && e - get(l, r) >= 0)
{
r++;
if (r == n + 1)
break;
e += min(0, b[r] - a[r]);
tr.add(pre[r], 1);
// cerr << e << ' ' << l << ' ' << r << ' ' << get(l, r) << ' ' << ge(l, r) << ' ' << pre[r] << endl;
}
// cerr << pre[l - 1] << endl;
// cerr << tr.sum(pre[l - 1]) << ' ';
res += r - l - tr.sum(pre[l - 1] - 1) + (pre[l - 1] > pre[r] && r != n + 1);
// cerr << l << ' ' << r << ' ' << res << endl;
e -= min(0, b[l] - a[l]);
tr.add(pre[l], -1);
}
io.write(res);
}
signed main()
{
// freopen("top.in", "r", stdin);
// freopen("top.out", "w", stdout);
// cerr<<(&en-&st)/1024.0/1024.0<<endl;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
return 0;
}
C. 最大前缀和
枚举组成前缀和的数，要保证前缀和部分的后缀和始终大于 \(0\) ，最大前缀和后面的数的前缀和始终小于 \(0\)
状压dp算方案数 乘贡献
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 998244353;
const int N = 21;
// bool st;
int n;
int a[20];
int sum[1 << 20];
int dp[1 << 20], f[1 << 20], tmp[1 << 20];
// bool en;
void solve()
{
cin >> n;
rep(i, 0, n - 1) cin >> a[i];
rep(msk, 0, (1 << n) - 1)
{
rep(i, 0, n - 1)
{
if (msk & (1 << i))
sum[msk] += a[i];
}
}
dp[0] = f[0] = 1;
int res = 0;
rep(msk, 0, (1 << n) - 1)
{
rep(i, 0, n - 1)
{
if (msk & (1 << i))
{
if (sum[msk] >= 0)
(dp[msk] += dp[msk ^ (1 << i)]) %= MOD;
(tmp[msk] += dp[msk ^ (1 << i)]) %= MOD;
}
}
}
rep(msk, 0, (1 << n) - 1)
{
if (sum[msk] >= 0)
continue;
rep(i, 0, n - 1)
{
if (msk & (1 << i))
(f[msk] += f[msk ^ (1 << i)]) %= MOD;
}
}
rep(msk, 1, (1 << n) - 1)
{
// cerr << dp[msk] << ' ';
(res += tmp[msk] * f[((1 << n) - 1) ^ msk] % MOD * sum[msk] % MOD) %= MOD;
}
cout << (res % MOD + MOD) % MOD << endl;
}
signed main()
{
// freopen("max.in","r",stdin);
// freopen("max.out","w",stdout);
// cerr<<(&en-&st)/1024.0/1024.0<<endl;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
return 0;
}
D. 染色
每次对一个点操作，然后对生成的点和这个点再操作，循环这个过程，进行 \(n\) 次以后等价于只对初始的点操作，对于每个点都这么做即可
// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
// const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e3 + 100;
// bool st;
// #define DEBUG 1 // 调试开关
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
char gc()
{
#if DEBUG // 调试，可显示字符
return getchar();
#endif
if (p1 == p2)
p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
return p1 == p2 ? ' ' : *p1++;
}
bool blank(char ch)
{
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
template <class T>
void read(T &x)
{
double tmp = 1;
bool sign = 0;
x = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-')
sign = 1;
for (; isdigit(ch); ch = gc())
x = x * 10 + (ch - '0');
if (ch == '.')
for (ch = gc(); isdigit(ch); ch = gc())
tmp /= 10.0, x += tmp * (ch - '0');
if (sign)
x = -x;
}
void read(char *s)
{
char ch = gc();
for (; blank(ch); ch = gc())
;
for (; !blank(ch); ch = gc())
*s++ = ch;
*s = 0;
}
void read(char &c)
{
for (c = gc(); blank(c); c = gc())
;
}
void push(const char &c)
{
#if DEBUG // 调试，可显示字符
putchar(c);
#else
if (pp - pbuf == MAXSIZE)
fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <class T>
void write(T x)
{
if (x < 0)
x = -x, push('-'); // 负数输出
static T sta[35];
T top = 0;
do
{
sta[top++] = x % 10, x /= 10;
} while (x);
while (top)
push(sta[--top] + '0');
}
template <class T>
void write(T x, char lastChar)
{
write(x), push(lastChar);
}
} io;
int n;
int a[N][N], b[N][N];
// bool en;
void solve()
{
io.read(n);
// cerr << "flag" << endl;
n = (1 << n);
rep(i, 0, n - 1)
{
rep(j, 0, n - 1)
{
io.read(a[i][j]);
}
}
for (int w = n / 4; w >= 1; w /= 2)
{
rep(i, 0, n - 1) rep(j, 0, n - 1) b[i][j] = 0;
rep(i, 0, n - 1)
{
rep(j, 0, n - 1)
{
if (a[i][j])
{
b[i][j] ^= 1;
b[(i + w) % n][j] ^= 1;
b[i][(j + w) % n] ^= 1;
b[(i - w + n) % n][j] ^= 1;
b[i][(j - w + n) % n] ^= 1;
}
}
}
rep(i, 0, n - 1) rep(j, 0, n - 1) a[i][j] = b[i][j];
}
int res = 0;
rep(i, 0, n - 1)
{
rep(j, 0, n - 1)
{
res += a[i][j];
}
}
io.write(res, '\n');
rep(i, 0, n - 1)
{
rep(j, 0, n - 1)
{
if (a[i][j])
{
io.write(i, ' ');
io.write(j, '\n');
}
}
}
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// cerr<<(&en-&st)/1024.0/1024.0<<endl;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
return 0;
}