1007 High Priestess
埃及分数
1008 Lovers
线段树维护取膜意义下的区间s和。
每个区间保存前缀lazy和后缀lazy。
#include <iostream> using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> void _R(T &x) { cin >> x; } void _R(int &x) { scanf("%d", &x); } void _R(ll &x) { scanf("%lld", &x); } void _R(double &x) { scanf("%lf", &x); } void _R(char &x) { scanf(" %c", &x); } void _R(char *x) { scanf("%s", x); } void R() {} template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); } template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } const int inf = 0x3f3f3f3f; const int mod = 1e9+7; /**********showtime************/ const int maxn = 1e5+9; ll sum[maxn<<2]; ll lazylen[maxn<<2],lazyback[maxn<<2],lazypre[maxn<<2]; ll sumten[maxn<<2]; char str[10]; void build(int le, int ri, int rt) { sum[rt] = 0; lazylen[rt] = lazyback[rt] = lazypre[rt] = 0; sumten[rt] = 1; if(le == ri) { return; } int mid = (le + ri) >> 1; build(le, mid, rt<<1); build(mid+1, ri, rt<<1|1); sumten[rt] = sumten[rt<<1] + sumten[rt<<1|1]; } ll ten[maxn]; void pushdown(int le, int ri, int rt){ int mid = (le + ri) >> 1; sumten[rt<<1] = ten[lazylen[rt]] * sumten[rt<<1]%mod; sum[rt<<1] = ((sum[rt<<1]*ten[lazylen[rt]]%mod + sumten[rt<<1]*lazypre[rt]%mod )%mod+ 1ll*(mid-le+1)*lazyback[rt] % mod)%mod; sumten[rt<<1] = ten[lazylen[rt]] * sumten[rt<<1]%mod; sumten[rt<<1|1] = ten[lazylen[rt]]*sumten[rt<<1|1]%mod; sum[rt<<1|1] = ((sum[rt<<1|1]*ten[lazylen[rt]]%mod + sumten[rt<<1|1]*lazypre[rt]%mod )%mod+ 1ll*(ri-mid)*lazyback[rt] % mod)%mod; sumten[rt<<1|1] = ten[lazylen[rt]]*sumten[rt<<1|1]%mod; lazypre[rt<<1] = (lazypre[rt] * ten[lazylen[rt<<1]]%mod + lazypre[rt<<1] )% mod; lazyback[rt<<1] = ((lazyback[rt<<1] * ten[lazylen[rt]])%mod + lazyback[rt]) % mod; lazylen[rt<<1] = lazylen[rt<<1] + lazylen[rt]; lazypre[rt<<1|1] = (lazypre[rt] * ten[lazylen[rt<<1|1]]%mod + lazypre[rt<<1|1])% mod; lazyback[rt<<1|1] = (lazyback[rt<<1|1] * ten[lazylen[rt]]%mod + lazyback[rt]) % mod; lazylen[rt<<1|1] = lazylen[rt<<1|1] + lazylen[rt]; lazylen[rt] = 0; lazyback[rt] = 0; lazypre[rt] = 0; } void pushup(int rt) { sum[rt] = (sum[rt<<1] + sum[rt<<1|1])%mod; sumten[rt] = (sumten[rt<<1] + sumten[rt<<1|1]) % mod; } void update(int L, int R, int b, int le, int ri, int rt) { if(le >= L && ri <= R) { sumten[rt] = 1ll*10*sumten[rt]%mod; sum[rt] = ((1ll*sum[rt]*10%mod + 1ll*sumten[rt]*b%mod )%mod + 1ll*(ri-le+1)*b % mod)%mod; sumten[rt] = 1ll*10*sumten[rt]%mod; lazypre[rt] = (1ll* b * ten[lazylen[rt]]%mod + lazypre[rt]) % mod; lazyback[rt] = (1ll*lazyback[rt] * 10 %mod + b)%mod; lazylen[rt]++; return; } if(lazylen[rt]) pushdown(le, ri, rt); int mid = (le + ri) >> 1; if(mid >= L) update(L, R, b, le, mid, rt<<1); if(mid < R) update(L, R, b, mid+1, ri, rt<<1|1); pushup(rt); } ll query(int L, int R, int le, int ri, int rt) { if(le >= L && ri <= R) { return sum[rt]; } if(lazylen[rt]) pushdown(le, ri, rt); int mid = (le + ri) >> 1; ll res = 0; if(mid >= L) res = (res + query(L, R, le, mid, rt<<1) )% mod; if(mid < R) res = (res + query(L, R, mid+1, ri, rt<<1|1)) % mod; pushup(rt); return res; } int main(){ // freopen("data.in", "r", stdin); ten[0] = 1; for(int i=1; i<maxn; i++) ten[i] = ten[i-1] * 10 % mod; int T; scanf("%d", &T); int cas = 0; while(T--) { int n,m; scanf("%d%d", &n, &m); build(1, n, 1); printf("Case %d: ", ++cas); while(m--) { scanf("%s", str); if(str[0] == 'w') { int le, ri, b; scanf("%d%d%d", &le, &ri, &b); update(le, ri, b, 1, n, 1); } else { int le, ri; scanf("%d%d", &le, &ri); printf("%lld ", query(le, ri, 1, n , 1)); } } } return 0; }
1010 Wheel of Fortune
转化为判定问题，是否存在一种对于球的完备匹配，且
匹配次数最多的颜色数量不超过 ⌊n⌋。 2
1011 The Magician
硬核模拟
1012 The Hanged Man
树链剖分
普通树形背包复杂度 O(nm2)，不可取。 考虑在 dfs 序上做 01 背包。