T1 抓牛
你在 $n$ ，牛在 $k$，你一步可以走到 $n-1,n+1,2 imes n$，问最少几步能抓到牛
sol：dp
$f_i$ 表示走到 $i$ 最少走了几步
当 $i leq n - 1$ 时，显然 $f_i = f_{i+1} + 1$（因为只能一步一步走过去）
$i$ 在 $n$ 右边时，有两种转移
对于一个偶数，它可能是左边走过来的，或者是它的一半跳过来的
对于一个奇数，他有可能是左边走过来的，也可能是从某位置一步跳到右边然后往左走一步
这种 $frac{(i+1)}{2} -> (i+1) ->i$ 的怎么算呢，当然是 $f_i = f_{frac{(i+1)}{2}} + 2$
T2 $k$阶前缀和
求一个数列的 $k$ 阶前缀和膜$10^9+7$，$n leq 5000,k leq 10^9$
sol：打表找规律
打出来表，发现是一个斜着的杨辉三角，然后搞一下就可以了
但我并不是这么推的。。
考虑数列 $1space 0space 0space 0space 0space 0$
一阶前缀和是$1space 1space 1space 1space 1space 1 = $$i-1 choose 0$
二阶前缀和$i choose 1$
三阶前缀和$i+1 choose 2$
...
$k$ 阶前缀和 $i+k-2 choose k-1$
所以预处理出这个再搞就可以了
T3 小乔
给一个极坐标，将 $2pi$ 分成 $2m$ 个单位角度
每次给一个扇形，最后求至少被 $k$ 个扇形覆盖的区域面积是多少
sol：扫描线 + 平衡树/权值线段树/差分树状数组
主席树好像会被卡空间 qwq
首先将跨过坐标轴的询问拆开，然后搞一个扫描线，维护一个数据结构支持单点插入、单点删除、查询被 $k$ 个扇形覆盖的区域
每次扫描线扫到一条扇形的边的时候插入/删除
然后怎么查询被 $k$ 个扇形覆盖的区域呢？显然是第 $k$ 大的半径内部的部分
事实证明，平衡树 xjb 转复杂度也是对的
只不过常数有点大...
AK 啦好开心 qwq
#include<bits/stdc++.h> #define LL long long using namespace std; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = 100000 + 10; int n,k; LL f[maxn]; int main() { freopen("meet.in","r",stdin); freopen("meet.out","w",stdout); n = read(),k = read(); f[n] = 0; for(int i=n-1;i>=0;i--)f[i] = f[i + 1] + 1; for(int i=n+1;i<=k;i++) { if(i & 1) f[i] = min(f[i - 1] + 1,f[(i + 1) / 2] + 2); else f[i] = min(f[i / 2] + 1,f[i - 1] + 1); } cout<<f[k]; }
#include<bits/stdc++.h> #define int long long using namespace std; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = 5010,mod = 1e9 + 7; int n,k;int a[maxn],s[maxn],Inv[maxn]; inline int ksm(int x,int t) { int res = 1; while(t) { if(t & 1)res = res * x % mod; x = x * x % mod; t = t >> 1; } return res; } inline int inv(int x){return ksm(x,mod - 2);} /*sig (1~x) from (x + k - i) choose (i) * a[0][i]*/ inline int C(int n,int m) { if(n < m || n < 0 || m < 0)return 0; int cur = n,ans = 1; for(int i=m;i>=1;i--) { (ans *= cur) %= mod; (ans *= Inv[i]) %= mod; cur--; } return ans; } int xs[maxn]; signed main() { freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); n = read();k = read() - 1; //for(int i=1;i<=n+k;i++)fac[i] = fac[i - 1] * i % mod; Inv[0] = 1; for(int i=1;i<=n;i++)Inv[i] = inv(i); for(int i=1;i<=n;i++)a[i] = read(); //for(int i=1;i<=n;i++)a[i] -= a[i - 1]; //for(int i=1;i<=n;i++)cout<<a[i]<<" "; for(int i=1;i<=n;i++)xs[i] = C(i + k - 1,(i + k - 1) - k) % mod; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) (s[i] += xs[i - j + 1] * a[j]) %= mod; for(int i=1;i<=n;i++)printf("%lld ",s[i]); }
#include<bits/stdc++.h> #define LL long long using namespace std; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = 400005; int n,m,kk; int top1,top2; struct qwq{int l,r,R;}nega[maxn],posi[maxn]; struct ques{int st,r;char f;bool operator < (const ques &b)const{return st<b.st;}}opts[maxn]; namespace RP { struct node{int ls,rs,size,val;}tr[maxn << 2]; int dfn,root,ops; inline void pushup(int x){tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+1;} inline void lt(int &x) { int k=tr[x].rs;tr[x].rs=tr[k].ls; tr[k].ls=x;tr[k].size=tr[x].size; pushup(x); x=k; } inline void rt(int &x) { int k=tr[x].ls;tr[x].ls=tr[k].rs; tr[k].rs=x;tr[k].size=tr[x].size; pushup(x); x=k; } inline int rng() { static unsigned long long seed = 233333333333333333LL; seed = seed + (seed << 17) + 531433123515; return seed; } /* void rp() { int x; for(int i=1;i<=min(n,10);i++)lt(x = rng() % n + 1); for(int i=1;i<=min(n,10);i++)rt(x = rng() % n + 1); } */ inline void magic(int &x,char f) { if(f) { if(tr[tr[tr[x].ls].ls].size > tr[tr[x].rs].size) rt(x),rt(x); else if(tr[tr[tr[x].ls].rs].size > tr[tr[x].rs].size) lt(tr[x].ls),rt(x); else return; } else { if (tr[tr[tr[x].rs].rs].size > tr[tr[x].ls].size) lt(x); else if (tr[tr[tr[x].rs].ls].size > tr[tr[x].ls].size) rt(tr[x].rs),lt(x); else return; } if(rng() & 1)lt(x); //Lucky! magic(tr[x].ls,0);magic(tr[x].rs,1); return; } inline void Insert(int &x,int v) { if (!x) { x = ++dfn; tr[x].ls = tr[x].rs = 0; tr[x].size = 1; tr[x].val = v; //rp(); } else { tr[x].size++; if (v<tr[x].val) Insert(tr[x].ls,v); else Insert(tr[x].rs,v); magic(x,v < tr[x].val); } } inline int del(int &x,int v) { tr[x].size--; int k = tr[x].val; if (v == k || (v < k && !tr[x].ls) || (v > k && !tr[x].rs) ) { if (!tr[x].ls || !tr[x].rs) x = tr[x].ls + tr[x].rs; else tr[x].val = del(tr[x].ls,v + 1); return k; } else { if (v < k) return del(tr[x].ls,v); else return del(tr[x].rs,v); } } inline int kth(int k) { int x = root; while(tr[tr[x].ls].size + 1 != k) { if(tr[tr[x].ls].size+1 < k) k -= tr[tr[x].ls].size,k--,x = tr[x].rs; else x = tr[x].ls; } return tr[x].val; } } using namespace RP; int main() { freopen("xiaoqiao.in","r",stdin); freopen("xiaoqiao.out","w",stdout); n = read(),m = read(),kk = read(); for(int i=1;i<=n;i++) { int R = read(),l = read(),r = read(); if(l == m) l = -m; if(r == -m) r = m; if(l == r) continue; if(l >= 0 && r >= 0) { if(l > r) { if(m) nega[++top1]=(qwq){-m,0,R}; if(l != m) posi[++top2]=(qwq){l,m,R}; if(r) posi[++top2]=(qwq){0,r,R}; } else posi[++top2]=(qwq){l,r,R}; } else if(l <= 0 && r <= 0) { if(l > r) { if(l) nega[++top1]=(qwq){l,0,R}; if(r != -m) nega[++top1]=(qwq){-m,r,R}; if(m) posi[++top2]=(qwq){0,m,R}; } else nega[++top1]=(qwq){l,r,R}; } else if (l <= 0 && r >= 0) { if (l) nega[++top1]=(qwq){l,0,R}; if (r) posi[++top2]=(qwq){0,r,R}; } else if(l >= 0 && r <= 0) { nega[++top1]=(qwq){-m,r,R}; posi[++top2]=(qwq){l,m,R}; } } LL res1 = 0,res2 = 0; root = dfn = ops = 0; for(int i=1;i<=top1;i++) { opts[++ops] = (ques){nega[i].l,nega[i].R,1}; opts[++ops] = (ques){nega[i].r,nega[i].R,0}; } sort(opts + 1,opts + ops + 1); int last = opts[1].st; int l = 1,r = 1; while(l <= ops) { while(r <= ops && opts[r].st == opts[l].st) r++; if(tr[root].size >= kk) { LL x = kth(tr[root].size - kk + 1); //di k da = n - k + 1 xiao res1 += x * x * (opts[l].st - last); } for(int i=l;i<r;i++) { if(opts[i].f == 1) Insert(root,opts[i].r); else del(root,opts[i].r); } last = opts[l].st; l = r; } root = dfn = ops = 0; for(int i=1;i<=top2;i++) { opts[++ops] = (ques){posi[i].l,posi[i].R,1}; opts[++ops] = (ques){posi[i].r,posi[i].R,0}; } sort(opts + 1,opts + ops + 1); last = opts[1].st; l = 1,r = 1; while(l <= ops) { while(r <= ops && opts[r].st == opts[l].st) r++; if(tr[root].size >= kk) { LL x = kth(tr[root].size - kk + 1); //di k da = n - k + 1 xiao res2 += x * x * (opts[l].st - last); } for(int i=l;i<r;i++) { if(opts[i].f == 1) Insert(root,opts[i].r); else del(root,opts[i].r); } last = opts[l].st; l = r; } cout<<res1 + res2; }