今天的题比较水... 班上的大佬们都AK了 我这种蒟蒻就完全不会矩阵快速幂
我永远恨矩阵快速幂
然后这道题还是比较简单的 就是维护区间连续最大和
线段树维护一下就可以了
代码
#include <bits/stdc++.h> #define oo 2 * 1e9 using namespace std; const int N = 5 * 1e5 + 5; int n,m,lmax[4 * N],rmax[4 * N],f[4 * N],a[N],g[4 * N],sum[4 * N]; struct data{ int lma,rma,s,sm; data(int lma = 0,int rma = 0,int s = 0,int sm = 0): lma(lma),rma(rma),s(s),sm(sm) { } }; void update(int o) { g[o] = max(g[2 * o], g[2 * o + 1]); sum[o] = sum[2 * o] + sum[2 * o + 1]; lmax[o] = lmax[2 * o]; rmax[o] = rmax[2 * o + 1]; f[o] = max(f[2 * o], f[2 * o + 1]); f[o] = max(f[o], rmax[2 * o] + lmax[2 * o + 1]); lmax[o] = max(lmax[o], sum[2 * o] + lmax[2 * o + 1]); rmax[o] = max(rmax[o], sum[2 * o + 1] + rmax[2 * o]); f[o] = max(f[o], max(lmax[o], rmax[o])); } void build(int o,int l,int r) { if(l == r) { sum[o] = a[l]; g[o] = a[l]; rmax[o] = max(0, a[l]); lmax[o] = max(0, a[l]); f[o] = max(0,a[l]); return ; } int mid = (l + r) >> 1; build(2 * o, l, mid); build(2 * o + 1, mid + 1, r); update(o); } void Init( ) { scanf("%d%d",& n,& m); for(int i = 1;i <= n;i ++) scanf("%d",& a[i]); build(1, 1, n); } data query(int o,int l,int r,int L,int R) { if(l >= L && r <= R) return data(lmax[o], rmax[o], f[o], sum[o]); int mid = (l + r) >> 1; data q1,q2,q3; q1 = data(0, 0, 0, 0); q2 = data(0, 0, 0, 0); q3 = data(0, 0, 0, 0); int t1 = 0,t2 = 0; if(L <= mid) { q1 = query(2 * o, l, mid, L, R); t1 = 1; } if(mid < R) { q2 = query(2 * o + 1, mid + 1, r, L, R); t2 = 1; } if(! t1 && t2) return q2; if(t1 && ! t2) return q1; if(t1 && t2) { q3.lma = max(q1.lma, q3.lma); q3.rma = max(q3.rma, q2.rma); q3.s = max(q3.s, max(q1.s, q2.s)); q3.s = max(q3.s, q1.rma + q2.lma); q3.lma = max(q3.lma, q1.sm + q2.lma); q3.rma = max(q3.rma, q2.sm + q1.rma); q3.s = max(q3.s, max(q3.lma, q3.rma)); } return q3; } void modify(int o,int l,int r,int pos,int del) { if(l == r) { sum[o] = del; rmax[o] = max(0, del); lmax[o] = max(0, del); f[o] = max(0,del); g[o] = del; return ; } int mid = (l + r) >> 1; if(pos <= mid) modify(2 * o, l, mid, pos, del); else modify(2 * o + 1, mid + 1, r, pos, del); update(o); } int query_max(int o,int l,int r,int L,int R) { if(l >= L && r <= R) return g[o]; int mid = (l + r) >> 1; int ans = -oo; if(L <= mid) ans = max(ans, query_max(2 * o, l, mid, L, R)); if(mid < R) ans = max(ans, query_max(2 * o + 1, mid + 1, r, L, R)); return ans; } inline int read( ) { int t = 1,ans = 0; char x; x = getchar( ); while(x < '0' || x > '9') { if(x == '-') t = -1; x = getchar( ); } while(x >= '0' && x <= '9') { ans = ans * 10 + x - '0'; x = getchar( ); } return ans * t; } void Solve( ) { while(m --) { int opt,l,r; opt = read( ); if(opt == 1) { l = read( ); r = read( ); data ans = query(1, 1, n, l, r); if(ans.s == 0) ans.s = query_max(1, 1, n, l, r); printf("%d ",ans.s); } else { l = read( ); r = read( ); a[l] = r; modify(1, 1, n, l, r); } } } int main( ) { freopen("BRS.in","r",stdin); freopen("BRS.out","w",stdout); Init( ); Solve( ); }
这道题就是矩阵快速幂 然后借着这道题的机会我重新学习了一波矩阵快速幂...
方程还是很简单的 就不说了 最重要的就是构造转移矩阵和初始矩阵
完了发现这是一道水水题 先把$dp[1],dp[2] ... dp[k]$预处理出来
然后转移矩阵 $1111$ 初始矩阵 $dp[k]$
$1000$ $dp[k - 1]$
$0100$ $dp[...]$
$0010$ $dp[2]$
$0001$ $dp[1]$ 类似于这种
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3 + 5; const ll MOD = 7777777; ll dp[N],s[20][5]; ll K,n; struct Matrix { ll a[15][15]; }h; void Moc(ll & a,ll b) { a = (a + b) % MOD; } Matrix pl(Matrix A,Matrix B) { Matrix c; for(int i = 1;i <= K;i ++) for(int j = 1;j <= K;j ++) c.a[i][j] = 0; for(int i = 1;i <= K;i ++) for(int j = 1;j <= K;j ++) { for(int k = 1;k <= K;k ++) Moc(c.a[i][j], 1ll * A.a[i][k] * B.a[k][j] % MOD); } return c; } void Init( ) { scanf("%d%d",& K,& n); dp[0] = 1; for(int i = 1;i <= K;i ++) { for(int k = 0;k < i;k ++) { Moc(dp[i], dp[k]); } } for(int i = 1;i <= K;i ++) { h.a[1][i] = 1; } for(int j = 2;j <= K;j ++) h.a[j][j-1] = 1; for(int i = 1;i <= K;i ++) s[i][1] = dp[i]; } Matrix fast_pow(Matrix A,int del) { Matrix ans; for(int i = 1;i <= K;i ++) for(int j = 1;j <= K;j ++) { ans.a[i][j] = 0; if(i == j) ans.a[i][j] = 1; } for(;del;del >>= 1,A = pl(A, A)) if(del & 1) ans = pl(ans, A); return ans; } void Solve( ) { h = fast_pow(h, n - K); ll ans = 0; for(int i = 1;i <= K;i ++) Moc(ans, h.a[1][i] * s[K + 1 - i][1] % MOD); printf("%lld ",ans); } int main( ) { freopen("fyfy.in","r",stdin); freopen("fyfy.out","w",stdout); Init( ); Solve( ); }
...这道题是扫描线的板子啊 而且数据范围这么小 就乱搞都可以过得
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int M = 10005; int n,q; ll ans = 0; int yy[M * 2]; struct Event{ int x,y1,y2; int d; }; vector<Event>e; struct Node { int sum,cnt; Node * ls,* rs; void up(int l, int r){ if(cnt) sum = yy[r] - yy[l - 1]; else if(l != r) sum = ls -> sum + rs -> sum; else sum = 0; } }pool[M],* root,* tail = pool; Node *build(int l = 1, int r = q) { Node * nd = ++ tail; if(l == r) nd -> sum = 0, nd -> cnt = 0; else { int mid = (l + r) >> 1; nd -> ls = build(l, mid); nd -> rs = build(mid + 1, r); nd -> up(l, r); } return nd; } #define Ls l, mid, nd -> ls #define Rs mid+1, r, nd -> rs void modify(int L, int R, int d, int l = 1, int r = q, Node * nd = root) { if(L <= l && R >= r) nd -> cnt += d, nd -> up(l, r); else { int mid = (l + r) >> 1; if(L <= mid) modify(L, R, d, Ls); if(R > mid) modify(L, R, d, Rs); nd -> up(l, r); } } bool operator < (const Event & a, const Event & b) { return a.x < b.x; } inline int read( ) { int t = 1,ans = 0; char x; x = getchar( ); while(x < '0' || x > '9') { if(x == '-') t = -1; x = getchar( ); } while(x >= '0' && x <= '9') { ans = ans * 10 + x - '0'; x = getchar( ); } return ans * t; } void Init( ) { scanf("%d",& n); int cnt = 0,k = 0; for(int i = 1;i <= n;i ++){ int x1,x2,y1,y2; x1 = read( ); y1 = read( ); x2 = read( ); y2 = read( ); e.push_back((Event){x1, y1, y2, 1}); e.push_back((Event){x2, y1, y2, -1}); yy[++ cnt] = y1; yy[++ cnt] = y2; } sort(yy + 1, yy + 1 + cnt); sort(e.begin( ), e.end( )); q = unique(yy + 1, yy + 1 + cnt) - yy - 1; root = build( ); } void Solve( ) { for(int i = 0;i < 2 * n;i ++) { ll dx = i == 0 ? 0 : e[i].x - e[i - 1].x; ans += 1ll * root -> sum * dx; int p1 = find(yy + 1, yy + 1 + q, e[i].y1) - yy; int p2 = find(yy + 1, yy + 1 + q, e[i].y2) - yy; modify(p1 + 1, p2, e[i].d); } printf("%lld ", ans); } int main( ) { freopen("olddriver.in","r",stdin); freopen("olddriver.out","w",stdout); Init( ); Solve( ); }