金字塔
套路，二分答案，将最底下一层，大于二分值的置为 1，小于的置为 0，我们就得到了一个 01串，
手玩几组样例可以发现，如果串为0101……，那么它上边的一层相当于对它取反，如果为 00，或者 11，
那么 0 或者 1 是会一直存在的，不断的向中间偏移。如果出现了00 或者 11，那么追顶层一定是 0 或者
1。如果同时出现，则里中间最近的成为顶部。
由于 1 代表的是大于 当前二分出的答案， 0表示小于 当前二分出的答案。当顶部为 1 时，就可以调小，当顶部为 0 时，就可以调大，所以是可以二分的。
/*
Date:2021.8.22
Source:模拟赛
konwledge: 二分答案 大于置1，小于置0
*/
#include <iostream>
#include <cstdio>
#define orz cout << "AK IOI" << "\n"
using namespace std;
const int maxn = 2e6 + 10;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, a[maxn], d[maxn], ans;
bool check(int mid)
{
for(int i = 1; i <= 2 * n - 1; i++) d[i] = a[i] > mid;
int l = -1, r = -1;
for(int i = n - 1; i; i--)//寻找 11 00
{
if(d[i] ^ d[i + 1]) continue;
l = i; break;
}
for(int i = n - 1; i <= 2 * n - 1; i++)
{
if(d[i] ^ d[i + 1]) continue;
r = i; break;
}
if((!~l) && (!~r)) return d[n] ^ (n - 1 & 1);//全都是01
if((!~l)) return d[r];//只找到了 00 或 01
if((!~r)) return d[l];
return (n - l) > (r - n) ? d[r] : d[l]; //都找到了
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n = read();
for(int i = 1; i < 2 * n; i++) a[i] = read();
int l = 1, r = 2 * n - 1;
while(l <= r)
{
int mid = (l + r) >> 1;
if(check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
print(l);
return 0;
}
演讲
蒟蒻不会，那就摘一下隔壁大佬的博文吧！
相邻两行之间进行异或,得到一个新的矩阵。
在这个新的矩阵里找最大的全 0 或全 1 矩阵即为答案。
为什么可以这样做？并不是很清楚。 但是通过手玩了不少数据之后， 发现确实是对的。
BS 的理解为：若是相邻的 0 或 1 异或之后是不影响答案的，若是 01 相间则是可以通过画若干个十字的方法进行调整构造出全 0 或全 1 矩阵。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
namespace INPUT {
const int L = 1 << 15;
char _buf[L], *S, *T, c; int n;
#define _gc (S == T ? (T = (S = _buf) + fread (_buf, 1, L, stdin), (S == T ? EOF : (*S++))) : (*S++))
void readi (int &X) {
for (c = _gc; c < '0' || c > '9'; c = _gc); X = c & 15;
for (c = _gc; c >= '0' && c <= '9'; X = X * 10 + (c & 15), c = _gc);
}
void reads (char *s) {
for (c = _gc; c != '#' && c != '.'; c = _gc); s[n = 1] = c;
for (c = _gc; c == '#' || c == '.'; s[++n] = c, c = _gc);
}
}
using INPUT :: readi;
using INPUT :: reads;
const int Maxn = 2005;
int N, M;
char a[Maxn][Maxn];
int st[Maxn], len[Maxn];
int Ans;
int main() {
//freopen ("speech.in", "r", stdin),
//freopen ("speech.out", "w", stdout);
readi (N), readi (M);
for (int i = 1; i <= N; i++) {
reads (a[i]);
for (int j = 1; j <= M; ++j)
a[i][j] = (a[i][j] == '#' ? 1 : 0);
}
Ans = max (N, M); //后面的方法统计不到。
for (int i = 1; i <= N; i++) {
for (int j = 1; j < M; j++) {
if (i > 1 && !(a[i - 1][j] ^ a[i][j] ^ a[i - 1][j + 1] ^ a[i][j + 1]))
len[j]++;
else
len[j] = 1;
}
int tp = 0;
for (int j = 1; j <= M; j++) {
while (tp && len[st[tp - 1]] >= len[j]) {
int x = st[--tp];
if (!tp)
Ans = max(Ans, j * len[x]);
else
Ans = max(Ans, (j - st[tp - 1]) * len[x]);
}
st[tp++] = j;
}
}
printf ("%d\n", Ans);
return 0;
}
这代码一看就不是 \(YCC\) 写的。
迷宫
二维树状数组版题！！！
/*
Date:2021.8.22
Source:
konwledge:二维树状数组
*/
#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#define orz cout << "AK IOI" << "\n"
#define lowbit(x) x & (-x)
using namespace std;
const int maxn = 2510;
const int mod = 1e9 + 7;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, m, Q;
int t[maxn][maxn];
map<int, map<int, map<int, map<int, int> > > > mp;
void add(int x, int y, int col)
{
for(int i = y; i <= m; i += lowbit(i)) t[x][i] += col;
}
int query(int x, int y)
{
int ans = 0;
for(int i = y; i >= 1; i -= lowbit(i)) ans += t[x][i];
return ans;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n = read(), m = read(), Q = read();
for(int i = 1; i <= Q; i++)
{
int opt = read();
int x1 = read() % mod, y1 = read(), x2 = read(), y2 = read();
if(opt == 1)
{
int col = rand();
for(int i = min(x1, x2); i <= max(x1, x2); i++)
{
add(i, y1, col);
add(i, y2 + 1, -col);
}
mp[x1][y1][x2][y2] = col;
}
if(opt == 2)
{
for(int i = min(x1, x2); i <= max(x1, x2); i++)
{
add(i, y1, -mp[x1][y1][x2][y2]);
add(i, y2 + 1, mp[x1][y1][x2][y2]);
}
}
if(opt == 3)
{
int ans1 = query(x1, y1), ans2 = query(x2, y2);
if(ans1 == ans2) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
count
枚举 \([1, p)\) 记录 \(i ^2 ≡ 1(\mod p)\) 的数为 \(cnt\)。
$ ans = \lfloor \frac{\phi(p) - cnt}2 \rfloor + cnt $
对于 $$x y ≡ 1 \pmod p$$ 这是个逆元。
当 \(x\) 与 \(p\) 互质的时候，\(x\) 在模 \(p\) 意义下的逆元唯一存在，由于 \(p\) 不一定是质数，所以就相当于求与 \(p\) 互质的数的个数。
题目要求无序，所以还要求开头的 \(cnt\)。
/*
Date:2021.8.23
Source:
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#define orz cout << "AK IOI" << "\n"
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int p, ans;
/*int cnt, vis[maxn], phi[maxn], prime[maxn];
void ol()
{
prime[1] = 1, phi[1] = 1;
for(int i = 2; i <= maxn; i++)
{
if(!vis[i]) {prime[++cnt] = i; phi[i] = i - 1;}
for(int j = 1; i * prime[j] <= maxn && j <= cnt; j++)
{
vis[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}*/
inline int Euler(int n)
{
int res = n, a = n;
for(int i = 2; i * i <= a; i++)
{
if(a % i == 0)
{
res = res / i * (i - 1);
while(a % i == 0) a /= i;
}
}
if(a > 1) res = res / a * (a - 1);
return res;
}
signed main()
{
//freopen("count.in","r",stdin);
//freopen("count.out","w",stdout);
p = read();
//ol();
ans += Euler(p);
for(int i = 1; i < p; i++) if(i * i % p == 1) ans++;
printf("%lld", ans >> 1);
return 0;
}
color
正解是数学归纳法和带加删边的欧拉回路。
说一下亲民的乱搞做法。
因为不同颜色的点只能相差一个，所以当有奇数个点的时候，会剩下一个，偶数个点的时候，每种颜色的数量相等。
对于 \(x\)相同的坐标，强行将他们两两配对，连一条边, 对于 \(y\) 相同的点也两两配对进行连边。
进行染色，能染则说明有解，否则无解。
/*
Date:2021.8.23
Source:CF547D + 模拟赛
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define orz cout << "AK IOI" << "\n"
using namespace std;
const int maxn = 5e5 + 10;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, col[maxn], lastu[maxn], lastv[maxn];
struct node{
int u, v, nxt;
}e[maxn << 1];
int js, head[maxn];
void add(int u, int v)
{
e[++js] = (node){u, v, head[u]};
head[u] = js;
}
void dfs(int u, int color)
{
col[u] = color;
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if(col[v] == -1) dfs(v, color ^ 1);
}
}
int main()
{
//freopen("color.in","r",stdin);
//freopen("color.out","w",stdout);
n = read();
for(int i = 1; i <= n; i++) col[i] = -1;
for(int i = 1; i <= n; i++)
{
int x = read(), y = read();
if(lastu[x])
{
add(lastu[x], i), add(i, lastu[x]);
lastu[x] = 0;
}
else lastu[x] = i;
if(lastv[y])
{
add(lastv[y], i), add(i, lastv[y]);
lastv[y] = 0;
}
else lastv[y] = i;
}
for(int i = 1; i <= n; i++) if(col[i] == -1) dfs(i, 0);
for(int i = 1; i <= n; i++) putchar((col[i]) ? 'r' : 'b');
return 0;
}
Sequence
分治的诡异代码。
取 \(mid\) , 维护前缀最小值，前缀最大值， 后缀最小值，后缀最大值。
枚举左侧每个位置，
while(p1 <= r && minn[p1] > minn[i]) p1++;
while(p2 <= r && maxx[p2] < maxx[i]) p2++;
将右边的区间分为三段。
利用上面维护的各种东西就可以 O(1) 的算出右端点在右边区间内的价值和。
/*
Date:2021.8.23
Source:
konwledge:分治
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#define orz cout << "AK IOI" << "\n"
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 1e7 + 10;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, ans, a[maxn], minn[maxn], maxx[maxn], s1[maxn], s2[maxn], s3[maxn];
void work(int l, int r)
{
if(l == r)
{
ans = (ans + a[l] * a[l] % mod) % mod;
return ;
}
int mid = (l + r) >> 1;
maxx[mid] = a[mid], minn[mid] = a[mid];
for(int i = mid - 1; i >= l; i--) maxx[i] = max(maxx[i + 1], a[i]);//前缀最大值
for(int i = mid - 1; i >= l; i--) minn[i] = min(minn[i + 1], a[i]);
maxx[mid + 1] = a[mid + 1], minn[mid + 1] = a[mid + 1];
for(int i = mid + 2; i <= r; i++) maxx[i] = max(maxx[i - 1], a[i]);//后缀最大值
for(int i = mid + 2; i <= r; i++) minn[i] = min(minn[i - 1], a[i]);
s1[mid] = 0;
for(int i = mid + 1; i <= r; i++) s1[i] = (s1[i - 1] + minn[i]) % mod;
s2[mid] = 0;
for(int i = mid + 1; i <= r; i++) s2[i] = (s2[i - 1] + maxx[i]) % mod;
s3[mid] = 0;
for(int i = mid + 1; i <= r; i++) s3[i] = (s3[i - 1] + minn[i] * maxx[i] % mod) % mod;
int p1 = mid + 1; int p2 = mid + 1;
for(int i = mid; i >= l; i--)
{
while(p1 <= r && minn[p1] > minn[i]) p1++;//找到分界点 ？？？？？！！！！
while(p2 <= r && maxx[p2] < maxx[i]) p2++;
if(p1 < p2)
{
ans = (ans + minn[i] * maxx[i] % mod * (p1 - mid - 1) % mod) % mod;
ans = (ans + maxx[i] * (s1[p2 - 1] - s1[p1 - 1] + mod) % mod) % mod;
ans = (ans + (s3[r] - s3[p2 - 1] + mod) % mod) % mod;
}
else
{
ans = (ans + minn[i] * maxx[i] % mod * (p2 - mid - 1) % mod) % mod;
ans = (ans + minn[i] * (s2[p1 - 1] - s2[p2 - 1] + mod) % mod) % mod;
ans = (ans + (s3[r] - s3[p1 - 1] + mod) % mod) % mod;
}
}
work(l, mid), work(mid + 1, r);
}
signed main()
{
//freopen("sequence.in","r",stdin);
//freopen("sequence.out","w",stdout);
n = read();
for(int i = 1; i <= n; i++) a[i] = read();
work(1, n);
printf("%lld", ans);
return 0;
}
monitor
貌似是 AC 自动机的版题，但是我写了 \(KMP\)，重点是我没清空，华丽的 \(re\) 了，而且试后看不出来，调不出来。
最后选择了 Hash。
/*
Date:2021.8.24
Source:模拟赛
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#define orz cout << "AK IOI" << "\n"
using namespace std;
const int maxn = 1e4 + 10;
const int maxl = 1e5 + 10;
const int mod1 = 1e9 + 9;
const int mod2 = 1e9 + 7;
const int base = 13131;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int l, n, m;
char s[30], S[maxl];
map<int, bool> m1, m2;
void get_ha(char s[])
{
int ans = 1;
for(int i = 1; i <= m; i++) ans = (ans * base % mod1 + (s[i] - 'a' + 1)) % mod1;
if(!m1[ans]) m1[ans] = 1;
ans = 1;
for(int i = 1; i <= m; i++) ans = (ans * base % mod2 + (s[i] - 'a' + 1)) % mod2;
if(!m2[ans]) m2[ans] = 1;
}
int main()
{
//freopen("monitor.in","r",stdin);
//freopen("monitor.out","w",stdout);
l = read(), n = read(), m = read();
for(int i = 1; i <= n; i++)
{
cin >> s + 1;
get_ha(s);
}
cin >> S;
int Ans = maxl;
for(int i = 1, j = i + m - 1; i <= l && j <= l; i++, j++)
{
int ans1 = 1, ans2 = 1;
for(int k = i; k <= j; k++)
{
ans1 = (ans1 * base % mod1 + (S[k] - 'a' + 1)) % mod1;
ans2 = (ans2 * base % mod2 + (S[k] - 'a' + 1)) % mod2;
}
if(m1[ans1] && m2[ans2]) {printf("%d", i + 1); return 0;}
}
printf("no");
return 0;
}
lab
这看起来以为是个图论题，其实是个数学题。
因为一条路径，正着走和到着走的路径是相反的，所以对环上的路径是没有影响的，设两点之间的树上距离为 dis 环长为 len 的话 那么在只有一个环的时候 u 到 v 的路径长度就是 \(dis_{u,v}+k \times len\).
显然这个结论可以推广到若干个环,
\(Disu,v=disu,v+\sum_{i = 1}^n K_i ×len_i\)
对于所有的 k 其取值都为任意整数 那么可以找到一个 K 使得上式为:
\(Disu,v=disu,v+K×gcd_{i=1}^m(len_i)\)
设 \(g=gcd_m^i=1(len_i)\) 题目相当于要求我们判断 是否有:
\(disu,v+K×g=t\)
那个 K 是不确定的 但是这个式子的形式很容易启发我们将其转化为同余式 即:
\(disu,v≡t(\mod g)\)
/*
Date:
Source:
konwledge:
*/
#include <iostream>
#include <cstdio>
#define orz cout << "AK IOI" << "\n"
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
inline ll read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
ll n, Q, g;
struct node{
ll u, v, w, nxt;
}e[maxn << 1];
ll js, head[maxn];
void add(ll u, ll v, ll w)
{
e[++js] = (node){u, v, w, head[u]};
head[u] = js;
}
ll sum[maxn];
ll siz[maxn], son[maxn], fa[maxn], dep[maxn];
void dfs1(ll u, ll f)
{
fa[u] = f;
dep[u] = dep[f] + 1;
siz[u] = 1;
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if(v == f) continue;
sum[v] = sum[u] + e[i].w;
dfs1(v, u);
siz[u] += siz[v];
if(!son[u] || siz[son[u]] < siz[v]) son[u] = v;
}
}
int top[maxn];
void dfs2(ll u, ll f)
{
top[u] = f;
if(son[u] == 0) return ;
dfs2(son[u], f);
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
ll lca(ll u, ll v)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
ll gcd(ll a, ll b)
{
if(!b) return a;
return gcd(b, a % b);
}
signed main()
{
//freopen("lab.in","r",stdin);
//freopen("lab.out","w",stdout);
n = read(), Q = read();
for(int i = 1; i <= n - 1; i++)
{
ll x = read(), y = read(), w = read();
add(x, y, w), add(y, x, -w);
}
dfs1(1, 0), dfs2(1, 1);
for(int i = 1; i <= Q; i++)
{
ll opt = read(), x = read(), y = read(), p = lca(x, y);
int z = read();
ll Dis = (-(sum[x] - sum[p]) + (sum[y] - sum[p]) - z);
if(opt == 0) g = gcd(g, Dis);
else
{
if(!g) {if(!Dis) puts("yes"); else puts("no");}
else
{
Dis = (Dis % g + g) % g;
if(!Dis) puts("yes"); else puts("no");
}
}
}
return 0;
}
civilization
换根dp
设 \(f_{u,1|0}\) 表示以u为根的子树内到u点路径长度为奇数|偶数所有路径的长度和。
\(sizu_{1|0}\) 表示以 u 为根的子树内到u点路径长度为奇数|偶数所有点的个数。
先算出一点，然后进行换根。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define ll long long
#define rg register
using namespace std;
const int MAXN = 2e5 + 5;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int n, q, siz[2][MAXN], siz2[2][MAXN];
ll f[2][MAXN], ans[2][MAXN];
struct edge{int v, nxt, w;}e[MAXN];
int E, head[MAXN];
void add_edge(int u, int v, int w) {
e[++E] = (edge){v, head[u], w};
head[u] = E;
}
void dfs(int x, int fa) {
siz[0][x] = 1;
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v, w = e[i].w;
if (v == fa) continue;
dfs(v, x);
if(w & 1) {
siz[0][x] += siz[1][v], siz[1][x] += siz[0][v];
f[1][x] += f[0][v] + siz[0][v] * w;
f[0][x] += f[1][v] + siz[1][v] * w;
}
else {
siz[0][x] += siz[0][v], siz[1][x] += siz[1][v];
f[1][x] += f[1][v] + siz[1][v] * w;
f[0][x] += f[0][v] + siz[0][v] * w;
}
}
}
void dfs2(int x, int fa) {
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v, w = e[i].w;
if (v == fa) continue;
if (w & 1) {
siz2[0][v] = siz2[1][x], siz2[1][v] = siz2[0][x];
ans[0][v] = f[0][v] + ans[1][x] - (f[0][v] + w * siz[0][v]) + w * (siz2[1][x] - siz[0][v]);
ans[1][v] = f[1][v] + ans[0][x] - (f[1][v] + w * siz[1][v]) + w * (siz2[0][x] - siz[1][v]);
}
else {
siz2[0][v] = siz2[0][x], siz2[1][v] = siz2[1][x];
ans[0][v] = f[0][v] + ans[0][x] -(f[0][v] + w * siz[0][v]) + w * (siz2[0][x] - siz[0][v]);
ans[1][v] = f[1][v] + ans[1][x] - (f[1][v] + w * siz[1][v]) + w * (siz2[1][x] - siz[1][v]);
}
dfs2(v, x);
}
}
int main(){
n = read(), q = read();
for (int i = 1, u, v, w; i < n; i++) {
u = read(), v = read(), w = read();
add_edge(u, v, w), add_edge(v, u, w);
}
dfs(1, 0);
ans[0][1] = f[0][1], ans[1][1] = f[1][1];
siz2[0][1] = siz[0][1], siz2[1][1] = siz[1][1];
dfs2(1, 0);
for (int i = 1; i <= q; i++) {
int x = read();
printf("%lld %lld\n", ans[1][x], ans[0][x]);
}
puts("");
return 0;
}
吃鱼 (fish)
用优先队列维护，每次把猫下一次吃鱼的时间和猫吃鱼用的时间放入，可以发现其实是有一段时间什么事情都没干的。把这段时间跳过。
/*
Date:2021.8.26
Source:模拟赛
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define orz cout << "AK IOI" << "\n"
#define pi pair<int,int>
using namespace std;
const int maxn = 1e5 + 10;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, m, x, ans;
priority_queue<pi, vector<pi>, greater<pi> > q; //从小到大
int main()
{
//freopen("fish.in","r",stdin);
//freopen("fish.out","w",stdout);
m = read(), n = read(), x = read();
for(int i = 1; i <= n; i++)
{
int x = read();
q.push(make_pair(x, x));
m--;
}
int now = 1;
for( ; now < x && m; now++)
{
while(!q.empty())
{
pi t = q.top();
if(t.first > now)
{
now = t.first - 1;
break;
}
q.pop();
q.push(make_pair(t.second + now, t.second));
m--;
if(!m) break;
}
}
while(!q.empty()) ans += q.top().first > x, q.pop();
printf("%d %d", m, ans);
return 0;
}
/*
8 3 10
1 3 4
*/
bag
奇怪的排序方法。
wxy聚聚的博文说：觉得这题一定要排序，所以试了很多种排序方法，然后过了大样例。对考试骗分有了新的启示？
/*
Date:2021.8.26
Source:
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define orz cout << "AK IOI" << "\n"
using namespace std;
const int maxn = 1010;
const int maxm = 5010;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, m, ans, f[maxm];
struct node{
int p, q, v;
}a[maxn];
bool cmp(node a, node b)
{
return a.q - a.p < b.q - b.p;
}
int main()
{
//freopen("bag.in","r",stdin);
//freopen("bag.out","w",stdout);
n = read(), m = read();
for(int i = 1; i <= n; i++) a[i].p = read(), a[i].q = read(), a[i].v = read();
sort(a + 1, a + n + 1, cmp);
for(int i = 1; i <= n; i++)
{
for(int j = m; j >= a[i].q; j--)
f[j] = max(f[j], f[j - a[i].p] + a[i].v);
}
for(int i = 0; i <= m; i++) ans = max(f[i], ans);
printf("%d", ans);
return 0;
}
beng
对于前70分，直接模拟就行了。
将走过的位置标记一下，然后从外部bfs一遍。标记过的点不入队。
bfs不到的点就是答案了。剩下的三十分离散化一下。
Date:2021.8.26
Source:
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <queue>
#define orz cout << "AK IOI" << "\n"
using namespace std;
const int maxk = 1100;
const int maxn = 2010;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int k, X, Y, map[maxn + 10][maxn + 10];
queue <pair<int, int> > q;
int bfs()
{
int ans = 0;
q.push(make_pair(1, 1));
map[1][1] = 1;
ans++;
while(!q.empty())
{
int x = q.front().first, y = q.front().second;
q.pop();
for(int i = 0; i < 4; i++)
{
int xx = x + dx[i], yy = y + dy[i];
if(xx >= 1 && xx <= maxn && yy >= 1 && yy <= maxn && !map[xx][yy])
{
ans++;
map[xx][yy] = 1;
q.push(make_pair(xx, yy));
}
}
}
return ans;
}
int main()
{
k = read();
X = 1005, Y = 1005;
map[X][Y] = 1;
char s;
for(int i = 1; i <= k; i++)
{
cin >> s;
int a = read();
if(s == 'L')
{
int to = Y - a;
for(int j = to; j <= Y; j++) map[X][j] = 1;
Y = to;
}
if(s == 'R')
{
int to = Y + a;
for(int j = Y; j <= to; j++) map[X][j] = 1;
Y = to;
}
if(s == 'U')
{
int to = X - a;
for(int j = to; j <= X; j++) map[j][Y] = 1;
X = to;
}
if(s == 'D')
{
int to = X + a;
for(int j = X; j <= to; j++) map[j][Y] = 1;
X = to;
}
}
printf("%d", maxn * maxn - bfs());
return 0;
}
数列
对数列做一个异或前缀。
发现当 \(sum[i] == sum[j]\) 时，\(i \sim j\)的异或值为 0, 那么我们就对相同的值异或，使相同的数尽可能的少。然后就是组合数的问题了。
当序列中有 \(x\) 个数异或为 0，那么就会对答案产生 \(C_x ^2\) 的减少的贡献。
当一个数异或成另一个数的时候，如果另一个是已经存在，可以发现，当两个数的数目相近时，比一个大一个小的情况是更优的。所以放心的更改就好了！
/*
Date:2021.8.27
Source:模拟赛
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <map>
#define orz cout << "AK IOI" << "\n"
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, k, js, ans, a[maxn], sum[maxn];
map<int, int> mp;
map<int, bool> vis;
int C2(int a) {return a * (a - 1) >> 1;}
signed main()
{
//freopen("seq.in","r",stdin);
//freopen("seq.out","w",stdout);
n = read(), k = read();
js = (1 << k) - 1;
mp[0] = 1;
for(int i = 1; i <= n; i++)
a[i] = read(), sum[i] = sum[i - 1] ^ a[i], mp[sum[i]]++;
for(int i = 1; i <= n; i++)
{
int flag = sum[i] ^ js;
if(mp[sum[i]] > 1 && mp[flag] + 1 < mp[sum[i]]) mp[sum[i]]--, mp[flag]++, sum[i] ^= js;
}
ans = n * (n + 1) >> 1;
for(int i = 0; i <= n; i++)//从l-1开始算，所以从0开始
if(!vis[sum[i]]) vis[sum[i]] = 1, ans -= C2(mp[sum[i]]);
printf("%lld", ans);
return 0;
}
/*
6 3
1 4 4 7 3 4
*/
最短路
有一个比较显然的贪心，就是每次找小的。可以写搜索。
正解是 DP。
设 \(f_{i, j}\) 表示从（1， 1）走到 （i，j）全部走 a，至少要改变几个字母。
然后，把所有 放 \(f[i][j] \leq k\) 的点找出来，找出走得最远的点所需的步数\(maxx\)，作为接下来\(bfs\)的起点。
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
const int maxn = 2002;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
char a[maxn][maxn];
int dp[maxn][maxn], vis[maxn][maxn];
int main()
{
int n, k;
n = read(), k = read();
for(int i = 0; i < n; i++) cin >> a[i];
int ms = 0;
vis[0][0] = 1;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i == 0 && j == 0) dp[i][j] = 0;
else if (i == 0)
dp[i][j] = dp[i][j - 1];
else if (j == 0)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
dp[i][j] += (a[i][j] != 'a' ? 1 : 0);
if (dp[i][j] <= k) {
ms = max(ms, i + j + 1);
if (i < n - 1)
vis[i + 1][j] = 1;
if (j < n - 1)
vis[i][j + 1] = 1;
}
}
}
string ans(ms, 'a');
for (int i = ms; i < 2 * n - 1; i++)
{
char mc = 'z';
for (int j = 0; j < n; j++)
if (0 <= i - j && i - j < n && vis[j][i - j])
mc = min(mc, a[j][i - j]);
for (int j = 0; j < n; j++)
if (0 <= i - j && i - j < n && vis[j][i - j] && a[j][i - j] == mc) {
if (j + 1 < n) vis[j + 1][i - j] = 1;
if (i - j + 1 < n) vis[j][i - j + 1] = 1;
}
ans.push_back(mc);
}
cout << ans;
return 0;
}
公交车
dp
\(f_i\)表示到 \(i\) 的最晚出发时间。
\(g_i\) 表示要赶上第 i 趟车要出发的最晚时间，
对汽车按出发时间排序
对一个点 到达该点的最晚出发时间为赶上这条线的最晚出发时间中的最晚时间
对一条线 赶上的最晚出发时间为到达该线出发点的最晚出发时间与该线发车时间中的较早时间
特别的 如果一条线的终点为 n 号点 统计该线的到达时间以及赶上该线的最晚出发时间
按照到达时间排序后 如果一条线的到达时间早于另一条线 且前者的的出发时间更晚 显然可以以前者的出发时间替换后者的出发时间
以此进行答案的更新 使其满足单调性
最后对每次询问进行二分查找 在能到达终点的所有线中找到达时间
智商锁
好名字，数学题。
构造方案，先向左边到
\(\frac{L + 1}{2}\),向右边到 \(\frac {L + 3} 2\)，然后左边到2，右边到2， 是最优的。
所以最后的结论是
\(\lfloor \frac{R - L - 2}2 \rfloor\) + 2。
/*
Date:2021.8.28
Source:
konwledge:
*/
#include <iostream>
#include <cstdio>
#define orz cout << "AK IOI" << "\n"
#define int long long
using namespace std;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int l, r;
signed main()
{
//freopen("lock.in","r",stdin);
//freopen("lock.out","w",stdout);
l = read(), r = read();
if((l == 1 && r == 1)) {puts("0"); return 0;}
if((l == 2 && r == 2) || (l == 1 && r == 2)) {puts("1"); return 0;}
if(l == 1 && r == 5) {puts("3"); return 0;}
if(l == r || r - l == 1) {puts("2"); return 0;}
printf("%lld", (r - l) / 2 + 1);
return 0;
}
LYK 与序列
单调队列 + 双指针。
首先 d 的长度是肯定要取满的，答案可能不会变优，但是一定不会变劣质。
维护一个前缀和，再维护一个数组表示从当前点到前 d 个点的长度，放入单调队列中。
/*
Date:8.28
Source: 模拟赛
konwledge:
*/
#include <iostream>
#include <cstdio>
#define orz cout << "AK IOI" << "\n"
#define int long long
using namespace std;
const int maxn = 2e6 + 10;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, p, d, a[maxn], sum[maxn], num[maxn], q[maxn];
/*
40分代码
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
{
int flag = sum[j] - sum[i - 1] - p;
for(int k = i; k <= j; k++)
{
if(k + d - 1 > j) continue;
int ff = sum[k + d - 1] - sum[k - 1];
if(ff >= flag) ans = max(ans, j - i + 1);
}
}
printf("%lld", ans);
*/
signed main()
{
//freopen("sequence.in","r",stdin);
//freopen("sequence.out","w",stdout);
n = read(), p = read(), d = read();
for(int i = 1; i <= n; i++)
num[i] = read(), sum[i] = sum[i - 1] + num[i];
for(int i = 1; i <= n; i++) a[i] = sum[i] - sum[max(0ll, i - d)];//处理消除的b段
int head = 1, tail = 0, ans = -1, l = 0;
for(int i = 1; i <= n; i++)
{
while(a[q[tail]] <= a[i] && head <= tail) tail--;
q[++tail] = i;
while(sum[i] - sum[l] - a[q[head]] > p && l < i)
{
l++;
while(head <= tail && l + d > q[head]) head++;
}
if(sum[i] - sum[l] - a[q[head]] <= p) ans = max(ans, i - l);
}
printf("%lld", ans);
return 0;
}
打架
认真审题后可以发现，连边以及翻转操作与 \(s_i\) 的数值无关，只与 \(s_i\) 之间的大小关系有关，可以将 \(s_i\) 进行离散化，将数值的范围缩小到 \(1 - n\)。
将操作按照 \(l\) 和 \(r\)小到大分别排序，很容易可以发现，一个区间翻转了两次就相当于没有翻转。
运用双指针，
然后我们考虑如何求满足条件的三元组个数？
满足条件的三元环的个数可以用所有的三元组，减去所有构成不合法三元环的的组合来求得。
/*
Date:2021.8.28
Source:模拟赛
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define orz cout << "AK IOI" << "\n"
#define lson rt << 1
#define rson rt << 1 | 1
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, m, a[maxn];
pair <int, int> aa[maxn], bb[maxn];
struct tree{
int l, r, lazy, sum;
}t[maxn << 2];
void build(int rt, int l, int r)
{
t[rt].l = l, t[rt].r = r;
if(l == r) return ;
int mid = (l + r) >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
}
void f(int rt)
{
t[rt].sum = t[rt].r - t[rt].l + 1 - t[rt].sum;//区间去反
t[rt].lazy ^= 1;
}
void push_down(int rt)
{
f(lson), f(rson);
t[rt].lazy = 0;
}
void updata(int rt, int l, int r)
{
if(l <= t[rt].l && t[rt].r <= r)
{
t[rt].sum = t[rt].r - t[rt].l + 1 - t[rt].sum;//区间去反
t[rt].lazy ^= 1;
return ;
}
if(t[rt].lazy) push_down(rt);
int mid = (t[rt].l + t[rt].r) >> 1;
if(l <= mid) updata(lson, l, r);
if(r > mid) updata(rson, l, r);
t[rt].sum = t[lson].sum + t[rson].sum;
}
int query(int rt, int l, int r, bool opt)
{
if(l > r) return 0;
if(l <= t[rt].l && t[rt].r <= r) return opt ? t[rt].sum : t[rt].r - t[rt].l + 1 - t[rt].sum;
if(t[rt].lazy) push_down(rt);
int mid = (t[rt].l + t[rt].r) >> 1;
if(l <= mid)
{
if(r > mid) return query(lson, l, r, opt) + query(rson, l, r, opt);
else return query(lson, l, r, opt);
}
else return query(rson, l, r, opt);
}
signed main()
{
//freopen("fight.in","r",stdin);
//freopen("fight.out","w",stdout);
n = read(), m = read();
for(int i = 1; i <= n; i++) a[i] = read();
if(m == 0) {puts("0"); return 0;}
sort(a + 1, a + n + 1);
int tot = unique(a + 1, a + n + 1) - a - 1;//离散化
build(1, 1, n);
for(int i = 1; i <= m; i++)
{
int l = read(), r = read();
l = std::lower_bound(a + 1, a + 1 + tot, l) - a;
r = std::upper_bound(a + 1, a + 1 + tot, r) - a - 1;// 离散化？？？？？？
aa[i] = make_pair(l, r);
bb[i] = make_pair(r, l);
}
sort(aa + 1, aa + m + 1), sort(bb + 1, bb + m + 1);//分别按l和r进行排序
int ans = n * (n - 1) * (n - 2) / 6;
for(int i = 1, j = 1, k = 1; i <= n; i++) //双指针操作 ？？
{
while(j <= m && aa[j].first == i) updata(1, aa[j].first, aa[j].second), j++;
int x = query(1, 1, i - 1, 0) + query(1, i + 1, n, 1);
ans -= x * (x - 1) / 2;
while(k <= m && bb[k].first == i) updata(1, bb[k].second, bb[k].first), ++k;
}
printf("%lld", ans);
return 0;
}
divide
维护一个前缀和，每次枚举前缀和，然后因为每一段是相同的，所以每次都增加这个枚举的长度，最后注意第一个数是0的情况要特判，不然会re。
/*
Date:2021.8.29
Source:模拟赛
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define orz cout << "AK IOI" << "\n"
#define int long long
using namespace std;
const int maxl = 1e5 + 10;
const int maxn = 10000000;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int T, b[maxl], sum[maxl], len, ans;
char a[maxl];
bool vis[maxn];
bool check(int x)
{
if(x == 0 && sum[len] == 0) return 1;
if(x == 0) return 0;
if(sum[len] % x) return 0;
int num = 0;
for(int i = 2 * x; i <= sum[len]; i += x)
{
num++;
if(!vis[i]) return 0;
}
if(num) return 1;
return 0;
}
signed main()
{
//freopen("divide.in","r",stdin);
//freopen("divide.out","w",stdout);
T = read();
while(T--)
{
memset(vis, 0, sizeof vis);
memset(sum, 0, sizeof sum);
cin >> a + 1;
len = strlen(a + 1);
for(int i = 1; i <= len; i++)
b[i] = a[i] - '0', sum[i] = sum[i - 1] + b[i], vis[sum[i]] = 1;
int flag = 0;
for(int i = 1; i <= len; i++)
if(check(sum[i])) {puts("YES"); flag = 1; break;}
if(flag == 0) puts("NO");
}
return 0;
}
/*
5
73452
1248
00
555
00020200
*/
count
依旧是dp
g[i]表示 i个节点没连通的方案数
f[i]表示 i个节点连通的方案数
h[i]表示i个节点的总方案数
h[i] = g[i] + f[i]
/*
Date:2021.8.29
Source: 模拟赛
konwledge:
*/
#include <iostream>
#include <cstdio>
#define orz cout << "AK IOI" << "\n"
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 5010;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, c[maxn][maxn], f[maxn], g[maxn], h[maxn];
void init()
{
c[0][0] = 1;
c[1][0] = c[1][1] = 1;
for(int i = 2; i <= maxn; i++)
{
c[i][0] = 1;
for(int j = 1; j <= i; j++)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
signed main()
{
//freopen("count.in","r",stdin);
//freopen("count.out","w",stdout);
n = read();
init();
int t = 1;
f[1] = 1, g[1] = 0, h[1] = 1;
for(int i = 2; i <= maxn; i++)
{
for(int j = 1; j <= i - 1; j++)
g[i] = (g[i] + (c[i - 1][j - 1] * f[j]) % mod * h[i - j]) % mod;
t = (2 * t) % mod;
h[i] = (t * h[i - 1]) % mod;
f[i] = (h[i] - g[i] + mod) % mod;
}
printf("%lld", f[n]);
return 0;
}
几点教训：
- 不要着急做题，题目至少读三遍。
- 通读题目，看好部分分，先打暴力，再写能写出来的正解。
- 读题目时，思考做法，看那些可做，那些不可做，想好要写什么对整场考试有个大体的安排。
- 合理分配时间，当一道题分配的时间用完时，不要挣扎，抓紧时间做下边的题目，除非剩下的不会做。
- 平心静气，少焦虑，少受影响！