csp模拟18[最长反链, 2A + X, No Rest for the Wicked , 暴力题]
T1 最长反链
明确两件事 :
- 位数相同的数不会冲突。
- 一个高位数,会与它各个位上所能组成的数冲突。
- 所以这个东西是有很明显的上下界的,我们考虑一个性质,对于高位\(\geq 2\) 的数字来说,它的下界就是它的量级, \([25, 156]\)这种来说,下界就可以是\(57\)否。
- 考虑一种解法则是有两种来源(eg \(231\)下界是\(100\), \([25, 156]\)这种来说,下界就可以是\(57\))。
- 考虑一种解法
- 对于r,我们可以拆出两个只比它小一位的数,即\(r / 10\) 和 \(r\) 去掉它的最高位组成的数
- 这两个数显然是不能选的, 且比这两个数中较大的数小的数显然可以在与\(r\)位数相同的数中找到, 所以剩下的只有比\(\ max\)(\(l\), \(max\)(\(r\)中选出的数))更大, 比\(r\)更小的数讨论。剩下分讨就行。
here
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define sec second
#define fst first
using namespace std;
namespace kiritokazuto{
// auto read = [](){
// LL x = 0;
// int f = 1;
// char c;
// while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
// do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
// return x * f;
// };
inline char getc(){
static char buf[1<<18],*p1,*p2;
if(p1==p2){p1=buf,p2=buf+fread(buf,1,1<<18,stdin);if(p1==p2)return EOF;}
return *p1++;
}
inline LL read(){
LL x=0;char ch=getc();
while(!isdigit(ch))ch=getc();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getc();
return x;
}
template <typename T> fuc(void, write) (T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);putchar(x % 10 | '0');
}
}
using namespace kiritokazuto;
const int maxn = 3e5 + 10, Inf = 2147483647, Mod = 998244353;
int t;
#define int long long
LL x, y;
fuc(int, getlj)(LL x) {//得到量级
if(x / 1000000000)return 9;
if(x / 100000000)return 8;
if(x / 10000000)return 7;
if(x / 1000000)return 6;
if(x / 100000)return 5;
if(x / 10000)return 4;
if(x / 1000)return 3;
if(x / 100)return 2;
if(x / 10)return 1;
if(x || !x)return 0;
}
fuc(int, get)(LL x) {
if(x < 10)return x;
return get(x / 10) * 10;
}
LL big;
LL ljx, ljy;
LL lj[12] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
signed main(){
t = read();
while(t --) {
x = read(), y = read();
if(getlj(x) == getlj(y)) {
write(y - x + 1);
ki;
continue;
}
ljx = getlj(x) + 1, ljy = getlj(y) + 1;
if(y >= lj[ljy - 1] * 2 - 1) {
write(y - lj[ljy - 1] + 1);
ki;
continue;
}
x = max(x, lj[ljy - 2] );
int l = max(y / 10, y % lj[ljy - 1]) +1;
write(y - max(l, x) + 1);
ki;
}
return 0;
}
/*
3
3 8
3 18
1 1000
6
10
900
*/
T2 2A + X
- 我们只有两种操作,一种是乘二,一种是加一,在不同时刻的加一相当于是\(+1, +2, +4, +8 ...\)不等的操作,我们可以考虑一个事,因为要极差最小,一个很显然的思路就是通过这些操作不断使最小值逼近最大值。
- 我们可以考虑使一个数一直乘二,不断去逼近最大值,并且记录其乘二的次数,通过乘二的次数我们可以推出它能加哪些东西,再次逼近。
- 同时我们还需要考虑一个事情,就是最大值的改变,所以我们维护一个\(nxt\)表示当前的数加上一个它所能加的最小的值超过\(Max\)之后的值,这样最后统计答案时就可以先让它做最小值(排序后),让他变大,让\(i + 1\)做最小值,然后\(O(n)\)推出答案了,
目前我在题库里跑的最快 - 当然还有一些东西,如果一个数已经和最大值一样了,或者乘二超过了最大值,我们把它的\(nxt\)直接改成\(Max\)或者是\(a_{i} \times 2\)就行。
- 还需要特判一些\(0\)的情况,就是差值小于\(x\),则显然可以跟上。
here
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define sec second
#define fst first
using namespace std;
namespace kiritokazuto{
// auto read = [](){
// LL x = 0;
// int f = 1;
// char c;
// while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
// do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
// return x * f;
// };
inline char getc(){
static char buf[1<<18],*p1,*p2;
if(p1==p2){p1=buf,p2=buf+fread(buf,1,1<<18,stdin);if(p1==p2)return EOF;}
return *p1++;
}
inline LL read(){
LL x=0;char ch=getc();
while(!isdigit(ch))ch=getc();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getc();
return x;
}
template <typename T> fuc(void, write) (T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);putchar(x % 10 | '0');
}
}
using namespace kiritokazuto;
const int maxn = 5e5 + 10, Inf = 2147483647, Mod = 1e9 + 7;
int n;
int x;
int a[maxn];
int cnt;
struct Node {
int val , nxt, id;
friend bool operator < (Node A, Node B) {
return A.val < B.val;
}
}b[maxn];
int num;
int Max = -1;
int Mincard = Inf;
int Min;
signed main(){
n = read();
x = read();
fr(i, 1, n)a[i] = read(), Max = max(Max, a[i]);
fr(i ,1 ,n) {
b[i].nxt = cnt = -1;//2 ^ 0 = 1所以从-1存,这里nxt临时存成了几个二
while((a[i] << 1) <= Max) {
cnt++;
a[i] <<= 1;
}
b[i].val = a[i];
b[i].id = i;
// printf("a[%d] = %d cnt = %d\n", i, a[i], cnt);
for(Re j = cnt; ~j; j --) {//枚举出牌
if(b[i].val == Max)continue;
int tmp = Max - b[i].val;
num = min(tmp / (1 << j), x);
b[i].val += num * (1 << j);//因为从-1存,所以这里不减一
if(num != x) b[i].nxt = j;//最小卡
}
}
// fr(i, 1, n) {
// printf("b[%d].val = %d b[%d].nxt = %d a[%d] = %d\n", i, b[i].val, i, b[i].nxt, i, a[i]);
// }
sort(b + 1, b + n + 1);
if(b[n].val - b[1].val < x) {
puts("0");
return 0;
}
Min = Max - b[1].val;
// printf("%d \n", Min);
delfr(i, 1, n) {
if(b[i].val == b[n].val) {b[i].nxt = b[i].val;continue;}
if(~b[i].nxt)b[i].nxt = min(b[i].val + (1 << b[i].nxt), a[b[i].id] << 1);
else {
// if(b[i].val == 12) {
// printf("%d\n", a[b[i].id]);
// }
b[i].nxt = (a[b[i].id] << 1);
}
}
// delfr(i, 1, n) {
// printf("b[%d].val = %d b[%d].nxt = %d\n", i, b[i].val, i, b[i].nxt);
// }
delfr(i, 1, n) {
Max = max(Max, b[i].nxt);
Min = min(Min, Max - b[i + 1].val);
}
write(Min);
return 0;
}
T3 No Rest for the Wicked
- 这个东西就跟着官方题解走呗,我们设\(f(x, v)\)表示从\(v\)出发,最大疫情值是\(x\)的\(ans\),显然我们可以由疫情值小的走到大的,那么小的就可以继承大的的答案,直接不用搜,停止就行。当然,如果仅仅是这样,显然我们可以对\(c_{i}\)排个序,然后\(bfs\)"记忆化”一下,然后就可以获得\(67pts\)的好成绩,不过这样仍然是\(O(n ^ 2)\)的。
- 考虑优化,对于两个点(\(u, v\))
- 如果\(\max(c_{u}, c_{v}) \le x \le \min(t_{v}, t_{u})\)那么显然\(x\)在这两个点之间走的时候是不会更改的,所以他们相当于是一个联通块,答案可以共享。
- 如果\(c_{u} \le x \le \min(t_{u}, c_{v} - 1)\),那么显然我们可以走到\(u\),也可以从\(u\)走到\(v\)。
- 首先考虑\(min\)取到\(c_{v} - 1\), 走到\(v\)之后我们的\(x\)会变大,所以此时建造双向边是无用的,因为我们在针对\(x\)处理,对于这些边是用来更新答案的,从小的疫情值搜到大的疫情值,我们可以直接继承大的的答案,所以显然没有从大的再到小的的必要,建造单向边,双向回来的话是针对\(x\)等于\(c_{v}\)之后,也就是到达\(v\)再考虑的,如果双向边可以建我是会建的(相当于线段树分治板子里时间还未到c_{v}仅仅只到了\(x\))
- 此外如果\(min\)取到\(t_{u}\)显然是回不去了,单向边。
- 考虑上文的边对于不同的\(x\)是可能存在或者消失的,这就符合线段树分治这种十分友好的离线算法了
- 我们可以对\(c\)进行分治,递归到叶子节点时统计答案,维护一个\(val\)和\(ans\)取一个\(max\)即可。
here
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first
using namespace std;
namespace kiritokazuto{
auto read = [](){
LL x = 0;
int f = 1;
char c;
while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
return x * f;
};
template <typename T> fuc(void, write) (T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);putchar(x % 10 | '0');
}
}
using namespace kiritokazuto;
const int maxn = 4e5 + 10, Inf = 0x3f3f3f3f, Mod = 5000007;
#define int long long
struct City {
int c, s, t;
friend bool operator < (City A, City B) {
return A.c > B.c;
}
}ct[maxn];
int n, m, k;
int lsh[maxn], cnt;
struct EDGE{int from, to;}wmx[maxn];
struct STK{int x, y, valf, tim;bool type;}stk[maxn];
//x是爹y是儿子val是爹的val
int top = 0;
int fa[maxn];
vector <int> qr[maxn << 1];
int heigh[maxn];
int ans[maxn], val[maxn];
struct Set_Union {
fuc(void, init)(){fr(i, 1, n)fa[i] = i, heigh[i] = 1, val[i] = ct[i].s, ans[i] = ct[i].s;}
fuc(int , find)(int x) {while(x != fa[x])x = fa[x]; return x;}//不进行路径压缩
fuc(void, merge)(int x, int y) {
x = find(x), y = find(y);
if(x == y)return;
if(heigh[x] < heigh[y])swap(x, y);//按秩合并
fa[y] = x;
heigh[x] += heigh[y];//小的进大的
val[x] = max(val[x], val[y]);
}
fuc(void, add)(int tim, int pos, int type) {
if(type) {
int from = wmx[pos].from, to = wmx[pos].to;
from = find(from), to = find(to);
if(val[from] < ans[to]) {
stk[++top].tim = tim;
stk[top].type = type;
stk[top].x = stk[top].y = from;
stk[top].valf = val[from];
val[from] = ans[to];
}
}else {
int from = wmx[pos].from, to = wmx[pos].to;
from = find(from), to = find(to);
if(from == to)return;
if(heigh[from] < heigh[to])swap(from, to);
stk[++top].x = from;
stk[top].y = to;
stk[top].valf = val[from];
stk[top].type = type;
stk[top].tim = tim;
fa[to] = from;
val[from] = max(val[from], val[to]);
heigh[from] += heigh[to];
}
}
fuc(void, del)(int tim) {
while(top && stk[top].tim == tim) {
if(stk[top].type) {
val[stk[top].y] = stk[top].valf;
}else {
int x = stk[top].x, y = stk[top].y;
heigh[x] -= heigh[y];
fa[y] = y;
val[x] = stk[top].valf;
}
top--;
}
}
}F;
struct Seg_Tree {
#define lsp(rt) (rt << 1)
#define rsp(rt) (rt << 1 | 1)
#define mid ((l + r) >> 1)
struct Tree {
vector <int> sig, Two;
}tr[5000001];
fuc(void, insert)(int rt, int l, int r, int L, int R, int pos, int type) {
if(L <= l && r <= R) {
if(type)tr[rt].sig.pb(pos);
else tr[rt].Two.pb(pos);
return;
}
if(L <= mid)insert(lsp(rt), l, mid, L, R, pos, type);
if(R > mid)insert(rsp(rt), mid + 1, r, L, R, pos, type);
}
fuc(void, query)(int rt, int l, int r) {
for(auto it : tr[rt].sig)F.add(rt, it, 1);
for(auto it : tr[rt].Two)F.add(rt, it, 0);
if(l == r) {//叶子
for(auto it : qr[l])ans[it] = max(ans[it], val[F.find(it)]);
return F.del(rt), void();
}
query(rsp(rt), mid + 1, r);
query(lsp(rt), l, mid);
F.del(rt);
}
}T;
signed main(){
n = read();
m = read();
fr(i, 1, n) ct[i].c = read() ,ct[i].t = read() ,ct[i].s = read(), lsh[++cnt] = ct[i].c, lsh[++cnt] = ct[i].t;
fr(i, 1, m)wmx[i].from = read(), wmx[i].to = read();
sort(lsh + 1, lsh + cnt + 1);
cnt = unique(lsh + 1, lsh + cnt + 1) - lsh - 1;
fr(i, 1, n) {
ct[i].c = lower_bound(lsh + 1, lsh + cnt + 1, ct[i].c) - lsh;
ct[i].t = lower_bound(lsh + 1, lsh + cnt + 1, ct[i].t) - lsh;
qr[ct[i].c].pb(i);
}
fr(i, 1, m) {
int &from = wmx[i].from, &to = wmx[i].to;
if(ct[from].c > ct[to].c)swap(from, to);
T.insert(1, 1, cnt, ct[to].c, min(ct[from].t, ct[to].t), i, 0);
if(ct[from].c <= min(ct[to].c - 1, ct[from].t))T.insert(1, 1, cnt, ct[from].c, min(ct[to].c - 1, ct[from].t), i, 1);
}
F.init();
T.query(1, 1, cnt);
fr(i, 1, n)write(ans[i]), fk;
return 0;
}
T4 暴力题
- 对于题目的柿子我们可以去掉下取整,变为
- 然后就可以权值线段树维护这两个东西了,对于除以\(w\)用乘逆元实现就行。
- 我们设\(f(x)\)表示\(\sum\limits_{i = 1} ^ {n} b_{i} * i^{x}\),最后答案就是\(f(k)\),考虑合并两颗子树\(t, p\),首先对于左子树\(t\)来说\(rk\)是不变的,直接继承,对于右子树来说,排名相当于偏移了一个\(sz(t)\),所以
- 二项式定理展开一下
-
所以就是的原来的\(f(p)\)再乘上一个\(\binom{n}{x} sz(t)^{p - x}\)就行。
-
对于后边的被减项,因为要取模,我们设\(cnt[i][j]\)表示对于\(b_{i} mod \ w = i\),\(i \ mod \ w = j\)的数的个数,这个暴力转移就好了。
here
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first
using namespace std;
namespace kiritokazuto{
// auto read = [](){
// LL x = 0;
// int f = 1;
// char c;
// while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
// do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
// return x * f;
// };
inline char getc(){
static char buf[1<<21],*p1,*p2;
if(p1==p2){p1=buf,p2=buf+fread(buf,1,1<<18,stdin);if(p1==p2)return EOF;}
return *p1++;
}
inline LL read(){
LL x=0;char ch=getc();
while(!isdigit(ch))ch=getc();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getc();
return x;
}
template <typename T> fuc(void, write) (T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);putchar(x % 10 | '0');
}
}
using namespace kiritokazuto;
const int maxn = 5e6 + 10000, Inf = 2147483647, Mod = 998244353, lim = 100000;
fuc(LL, qpow)(LL a, LL b, LL mod) {
LL res = 1;
while (b) {
if (b & 1)res = 1ll * (res * a) % mod;
a = 1ll * (a * a) % mod;
b >>= 1;
}
return res % mod;
}
LL C[6][6];
int a[maxn], K, w;
int n;
int Q;
int inv;
struct Tree {
int cnt[6][6];
int f[6];
int sz;
#define f(rt, x) tr[rt].f[x]
#define cnt(rt, x, y) tr[rt].cnt[x][y]
#define sz(rt) tr[rt].sz
}tr[maxn];
struct Seg_Tree {
#define lsp(rt) (rt << 1)
#define rsp(rt) (rt << 1 | 1)
#define mid ((l + r) >>1)
fuc(void, pushup)(int rt) {
sz(rt) = sz(lsp(rt)) + sz(rsp(rt));
fr(i, 0, K) {
f(rt, i) = f(lsp(rt), i);
fr(j, 0, i) {
f(rt, i) = (f(rt, i) + f(rsp(rt), j) * C[i][j] % Mod * qpow(sz(lsp(rt)), i - j, Mod) % Mod) % Mod ;
}
}
delfr(i, 0, w) delfr(j, 0, w) cnt(rt, i, j) = cnt(lsp(rt), i, j);
delfr(i, 0, w) delfr(j, 0, w) (cnt(rt, i, (j + sz(lsp(rt))) % w)) += cnt(rsp(rt), i, j) %= Mod;
}
fuc(void, insert)(int rt, int l, int r, int pos, int val) {
if(l == r) {
sz(rt) += val;//先加值
fr(i, 0, K) {
f(rt, i) += val * l * qpow(sz(rt) + (val == -1), i, Mod) % Mod;
//val 为 1 或者 -1, 如果为-1,因为我这里的sz是先减过的,所以为了减掉一个贡献,我用的是原来没减的,所以把一补上(rk要原来的)
}
cnt(rt, l % w, ((sz(rt) + (val == -1)) % w)) += val;
return;
}
if(pos <= mid)insert(lsp(rt), l, mid, pos, val);
if(pos > mid)insert(rsp(rt), mid + 1, r, pos, val);
pushup(rt);
}
}T;
signed main() {
fr(i, 0, 5)C[i][0] = 1;
fr(i, 1, 5) fr(j, 1, i) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % Mod;
n = read(), K = read(), w = read();
fr(i, 1, n)a[i] = read(), T.insert(1, 0, lim, a[i], 1);
Q = read();
inv = qpow(w, Mod- 2, Mod) % Mod;
fr(i ,1, Q) {
int x = read(), y = read();
T.insert(1, 0, lim, a[x], -1);
a[x] = y;
T.insert(1, 0, lim, a[x], 1);
LL ans = 0;
delfr(i, 0, w) delfr(j, 0, w) {
ans = (ans + (i * qpow(j, K, w) % w) % Mod * cnt(1, i, j) % Mod) % Mod;
}
write(((f(1, K) - ans + Mod) % Mod + Mod) % Mod * inv % Mod);
ki;
}
return 0;
}