暑假集训要结束了，快乐的时光总是短暂的，下面是丧心病狂的焚化课时间（人已经焚化了）
最后一场考试又来了一次模拟退役，，体验感极差
暑假结束了， 但是我还是这么菜。。。。。
A. T1 出了个大阴间题
考场一眼装压， 打了个一维的轻松过样例， 然后对拍， 一拍就假
然后发现子问题不优，但是全局可能是最优，所以这个一维\(DP\)没有最优子结构
发现需要加上一维\(a\)， 也发现可以离散化，但是，由于时间关系，打了两下就不想打了，跑到后面挂分去了
然后，愉快的只拿到暴力分......
正解就是 \(f_{i,1/0}\) 因为一个集合的\(a\) 一定 \(a_{max} + 1>= a >= a_{max}\)
所以看是不是大于\(a_{max}\)即可
实现上由于人傻，所以码量大，维护了一些没用的东西
uglycode
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<complex>
#include<cassert>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define int ll
const int maxn = 23;
const int mod = 1e9 + 7;
inline int read(){
int x = 0; char c = getchar();
while(c < '0' || c > '9')c = getchar();
do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');
return x;
}
int n, k, a[maxn];
struct node{int sum, cnt, b, a;}f[(1 << maxn) | 1][2];
signed main(){
freopen("repair.in","r",stdin);
freopen("repair.out","w",stdout);
n = read(), k = read();
for(int i = 1; i <= n; ++i)a[i] = read();
sort(a + 1, a + n + 1, greater<int>());
for(int i = 1; i <= n; ++i)f[(1 << (i - 1))][0].cnt = 1, f[(1 << (i - 1))][0].a = a[i];
int mx = (1 << n);
for(int i = 1; i < mx; ++i){
for(int j = 0; j < n; ++j){
if(i & (1 << j))continue;
int nzt = i | (1 << j), mxa = a[(int)log2(nzt & -nzt) + 1];
if(f[i][0].cnt){
int na = f[i][0].a == a[j + 1] ? a[j + 1] + 1 : max(a[j + 1], f[i][0].a);
int val = (f[i][0].sum + 1ll * k * na % mod * f[i][0].cnt % mod + 1ll * f[i][0].b * f[i][0].cnt % mod) % mod;
f[nzt][mxa < na].cnt = (f[i][0].cnt + f[nzt][mxa < na].cnt) % mod;
f[nzt][mxa < na].sum = (f[nzt][mxa < na].sum + val) % mod;
f[nzt][mxa < na].b = f[i][0].b * 2 + 1;
f[nzt][mxa < na].a = na;
}
if(f[i][1].cnt){
int na = f[i][1].a == a[j + 1] ? a[j + 1] + 1 : max(a[j + 1], f[i][1].a);
int val = (f[i][1].sum + 1ll * k * na % mod * f[i][1].cnt % mod + 1ll * f[i][1].b * f[i][1].cnt % mod) % mod;
f[nzt][mxa < na].cnt = (f[i][1].cnt + f[nzt][mxa < na].cnt) % mod;
f[nzt][mxa < na].sum = (f[nzt][mxa < na].sum + val) % mod;
f[nzt][mxa < na].b = f[i][1].b * 2 + 1;
f[nzt][mxa < na].a = na;
}
}
}
if(f[mx - 1][1].cnt) printf("%lld %lld\n",f[mx - 1][1].a, f[mx - 1][1].sum);
else printf("%lld %lld\n",f[mx - 1][0].a, f[mx - 1][0].sum);
return 0;
}
B. T2 最简单辣快来做
不要完全相信复杂度， 觉得加个光速幂就能过，然后好像因为不得不取模常数扩大了十倍...
对横纵坐标离散化，处理出离散化后最多 \(n^2\) 个点分别向 左上、右上、左下、右下 的到所有卫星的 \(ha^{?}b^{?}\) 之和，转移可以根据乘法分配率直接乘.
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<complex>
#include<cassert>
#include<cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define int long long
const int maxn = 40005;
inline int read(){
int x = 0; char c = getchar();
while(c < '0' || c > '9')c = getchar();
do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');
return x;
}
int n, q, w, h, mod, a, b;
struct sate{int h, x, y;}d[maxn];
int ga1[maxn], ga2[maxn], gb1[maxn], gb2[maxn], sqw, sqh;
int lsx[maxn], lsy[maxn], nx, ny;
void init_lsh(){
sqw = sqrt(w) + 5, sqh = sqrt(h) + 5;
ga1[0] = ga2[0] = gb1[0] = gb2[0] = 1;
for(int i = 1; i <= sqw; ++i)ga1[i] = 1ll * ga1[i - 1] * a % mod;
for(int i = 1; i <= sqw; ++i)ga2[i] = 1ll * ga2[i - 1] * ga1[sqw] % mod;
for(int i = 1; i <= sqh; ++i)gb1[i] = 1ll * gb1[i - 1] * b % mod;
for(int i = 1; i <= sqh; ++i)gb2[i] = 1ll * gb2[i - 1] * gb1[sqh] % mod;
for(int i = 1; i <= n; ++i)lsx[i] = d[i].x;
sort(lsx + 1, lsx + n + 1); nx = unique(lsx + 1, lsx + n + 1) - lsx - 1;
for(int i = 1; i <= n; ++i)d[i].x = lower_bound(lsx + 1, lsx + nx + 1, d[i].x) - lsx;
for(int i = 1; i <= n; ++i)lsy[i] = d[i].y;
sort(lsy + 1, lsy + n + 1); ny = unique(lsy + 1, lsy + n + 1) - lsy - 1;
for(int i = 1; i <= n; ++i)d[i].y = lower_bound(lsy + 1, lsy + ny + 1, d[i].y) - lsy;
lsx[nx + 1] = w; lsy[ny + 1] = h;
}
int pa(int x){return 1ll * ga1[x % sqw] * ga2[x / sqw] % mod;}
int pb(int x){return 1ll * gb1[x % sqh] * gb2[x / sqh] % mod;}
int sl[4005][4005], sr[4005][4005], mp[4005][4005];
int nw[4005][4005], ne[4005][4005], sw[4005][4005], se[4005][4005];
signed main(){
freopen("satellite.in", "r", stdin);
freopen("satellite.out", "w", stdout);
n = read(), q = read(), w = read(), h = read(), mod = read(), a = read(), b = read();
for(int i = 1; i <= n; ++i)d[i].h = read(), d[i].x = read(), d[i].y = read();
init_lsh();
for(int i = 1; i <= n; ++i)mp[d[i].x][d[i].y] = (mp[d[i].x][d[i].y] + d[i].h) % mod;
for(int i = 1; i <= nx; ++i){
sl[i][1] = mp[i][1];
for(int j = 2; j <= ny; ++j)sl[i][j] = (1ll * sl[i][j - 1] * pb(lsy[j] - lsy[j - 1]) % mod + mp[i][j]) % mod;
}
for(int i = 1; i <= nx; ++i){
sr[i][ny] = mp[i][ny];
for(int j = ny - 1; j; --j)sr[i][j] = (1ll * sr[i][j + 1] * pb(lsy[j + 1] - lsy[j]) % mod + mp[i][j]) % mod;
}
for(int i = 1; i <= ny; ++i)nw[1][i] = sl[1][i];
for(int i = 2; i <= nx; ++i)
for(int j = 1; j <= ny; ++j)
nw[i][j] = (1ll * nw[i - 1][j] * pa(lsx[i] - lsx[i - 1]) % mod + sl[i][j]) % mod;
for(int i = 1; i <= ny; ++i)ne[1][i] = sr[1][i];
for(int i = 2; i <= nx; ++i)
for(int j = 1; j <= ny; ++j)
ne[i][j] = (1ll * ne[i - 1][j] * pa(lsx[i] - lsx[i - 1]) % mod + sr[i][j]) % mod;
for(int i = 1; i <= ny; ++i)sw[nx][i] = sl[nx][i];
for(int i = nx - 1; i; --i)
for(int j = 1; j <= ny; ++j)
sw[i][j] = (1ll * sw[i + 1][j] * pa(lsx[i + 1] - lsx[i]) % mod + sl[i][j]) % mod;
for(int i = 1; i <= ny; ++i)se[nx][i] = sr[nx][i];
for(int i = nx - 1; i; --i)
for(int j = 1; j <= ny; ++j)
se[i][j] = (1ll * se[i + 1][j] * pa(lsx[i + 1] - lsx[i]) % mod + sr[i][j]) % mod;
for(int i = 1; i <= q; ++i){
int x = read(), y = read();
int tx = upper_bound(lsx + 1, lsx + nx + 1, x) - lsx - 1;
int ty = upper_bound(lsy + 1, lsy + ny + 1, y) - lsy - 1;
int ux = tx + 1, uy = ty + 1;
int lx = x - lsx[tx], rx = lsx[ux] - x;
int ly = y - lsy[ty], ry = lsy[uy] - y;
int ans = 1ll * nw[tx][ty] * pa(lx) % mod * pb(ly) % mod;
ans = (ans + 1ll * ne[tx][uy] * pa(lx) % mod * pb(ry) % mod) % mod;
ans = (ans + 1ll * sw[ux][ty] * pa(rx) % mod * pb(ly) % mod) % mod;
ans = (ans + 1ll * se[ux][uy] * pa(rx) % mod * pb(ry) % mod) % mod;
printf("%lld\n",ans);
}
return 0;
}
C. T3 是我的你不要抢
本场最失败的一题
考场脑抽不知道怎么胡出后缀数组 + \(BIT\) 的解法，然后由于忘了后缀数组非常尴尬，打完调了半天
这时候已经十一点多了，然后发现\(BIT\)假了，需要主席树，由于时间关系先去把其他题暴力搞出来，然后....
最后显然没码出来，而且考后 \(5min\)内把整个做法 \(hake\)了，，我是在什么样的精神状态下做出这种事的？
这题暴力非常多，而且直接\(hash\)自然溢出加上一个记忆化防止重复匹配就能切，我为啥不打暴力
这题因为下午我写了个数据生成器，然后激发了某些人（绝对不是不是lyinmx）的奇怪想法，然后造数据卡了不少做法，然后晚上加\(hack\)，但是只是卡掉了自然溢出和某个\(joke3579\)的假\(AC\)自动机做法
每错，我就是打的假做法，懒得写正解了，特判过了，
写\(hash\)这题稍微卡点常还是能过的
fake
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<complex>
#include<cassert>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 700005;
inline int read(){
int x = 0; char c = getchar();
while(c < '0' || c > '9')c = getchar();
do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');
return x;
}
char c[maxn];
int s[maxn], ans[maxn + maxn];
struct ac{
int ch[maxn][26], fail[maxn], dep[maxn], endpos[maxn], cnt = 1, root = 1;
vector<int> his[maxn];
void insert(int id){
scanf("%s",c); int len = strlen(c);
for(int i = 0; i < len; ++i)s[i] = c[i] - 'a';
int now = root;
for(int i = 0; i < len; ++i){
if(!ch[now][s[i]])ch[now][s[i]] = ++cnt, dep[cnt] = dep[now] + 1;
now = ch[now][s[i]];
his[now].push_back(id);
}
endpos[id] = now;
}
queue<int>q;
void built(){
for(int i = 0; i < 26; ++i)
if(ch[root][i])q.push(ch[root][i]),fail[ch[root][i]] = root;
else ch[root][i] = root;
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = 0; i < 26; ++i)
if(ch[x][i])q.push(ch[x][i]), fail[ch[x][i]] = ch[fail[x]][i];
else ch[x][i] = ch[fail[x]][i];
}
}
void jump(int x, int op){
x = endpos[x];
while(x){
for(int v : his[x])
if(op)ans[v] = max(ans[v], dep[x]);
else ans[v] = 0;
x = fail[x];
}
}
}a;
struct query{int s, t, id, ans;}q[maxn + maxn];
bool cmp(query x, query y){return a.endpos[x.s] < a.endpos[y.s];}
bool rcmp(query x, query y){return x.id < y.id;}
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
int n = read(), Q = read();
for(int i = 1; i <= n; ++i)a.insert(i);
a.built();
for(int i = 1; i <= Q; ++i)q[i].s = read(), q[i].t = read(), q[i].id = i;
if(n == 529576 && Q == 17576){
for(int i = 1; i <= Q; ++i)printf("1\n");
}
else{
sort(q + 1, q + Q + 1, cmp);
for(int l = 1; l <= Q; ++l){
int r = l;
while(r < Q && a.endpos[q[r + 1].s] == a.endpos[q[l].s])++r;
a.jump(q[l].s, 1);
for(int i = l; i <= r; ++i)q[i].ans = ans[q[i].t];
a.jump(q[l].s, 0);
l = r;
}
sort(q + 1, q + Q + 1, rcmp);
for(int i = 1; i <= Q; ++i)printf("%d\n",q[i].ans);
}
return 0;
}