1.bzoj2563:

将边权均摊至端点,若两个端点分属两个人,相减时会抵消;若同属一人,则获得边权收益,依此贪心。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 10005
using namespace std;
typedef double d;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, m;
double a[N], sa, sb;
 
int main() {
    n = read(); m = read();
    for(int i=1; i<=n; i++) a[i] = read();
    for(int i=1; i<=m; i++) {
        int u=read(), v=read(), w=read();
        a[u] += ((d)w / 2);
        a[v] += ((d)w / 2);
    }
    sort(a+1, a+n+1);
    sa = 0; sb = 0;
    for(int i=n; i>=1; i--) { sa += a[i]; sb += a[--i]; }
    printf("%d", (int)(sa - sb));
    return 0;
}

2.bzoj1584:

注意到代价至多为n,且dp值单调不减,那么维护不同颜色出现j次的最小pos值即可,维护$\sqrt n$个j值就好。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 40005
#define INF 1000000000
using namespace std;
int n, m;
int a[N], b[205], c[205];
int dp[N], pre[N];

int main() {
    scanf("%d%d", &n, &m); m = sqrt(n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    memset(pre, -1, sizeof(pre));
    dp[0] = 0;
    for(int i=1; i<=n; i++) {
        dp[i] = INF;
        for(int j=1; j<=m; j++)
            if(pre[a[i]] <= b[j]) c[j]++;
        pre[a[i]] = i;
        for(int j=1; j<=m; j++)
            if(c[j] > j) {
                int t = b[j] + 1;
                while(pre[a[t]] > t) t++;
                b[j] = t; c[j]--;
            }
        for(int j=1; j<=m; j++)
            dp[i] = min(dp[i], dp[b[j]] + j*j);
    }
    printf("%d\n", dp[n]);
    return 0;
}

3.bzoj1584:

分数规划问题,二分一个答案k,判定$ {V\over C } \ge k$,即$ k\cdot C-V\le0$,即判断图中是否存在负环,构图可以用前缀和优化,思想很妙,但是只适用于一个封闭图形。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 55
#define INF 1000000000
using namespace std;
typedef double d;
const double eps = 1e-6;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
static int n, m, nm, v[N][N], sum;
static int heng[N][N], shu[N][N];
int head[3005], nex[200005], point[200005], cnt;
double weight[200005];
 
void Input() {
    n=read(); m=read(); nm = (n+1)*(m+1);
     
    memset(v, 0, sizeof(v));
     
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            v[i][j] = read();
     
    for(int j=1; j<=m; j++)
        for(int i=1; i<=n; i++)
            v[i][j] += v[i-1][j];
 
    for(int j=1; j<=m; j++) sum += v[n][j];
     
    for(int i=1; i<=(n+1); i++)
        for(int j=1; j<=m; j++)
            heng[i][j] = read();
     
    for(int i=1; i<=n; i++)
        for(int j=1; j<=(m+1); j++)
            shu[i][j] = read();
}
 
inline int id(int x, int y) { return (x-1)*(m+1) + y; }
 
void Link(int x, int y, double z) {
    nex[++cnt] = head[x]; head[x] = cnt;
    point[cnt] = y; weight[cnt] = z;
}
 
void Build_graph(double k) {
    memset(head, 0, sizeof(head));
    cnt = 0;
    for(int i=1; i<=(n+1); i++)
        for(int j=1; j<=m; j++) {
            Link(id(i,j), id(i,j+1), k*heng[i][j]+v[i-1][j]);
            Link(id(i,j+1), id(i,j), k*heng[i][j]-v[i-1][j]);
        }
    for(int j=1; j<=(m+1); j++)
        for(int i=1; i<=n; i++) {
            Link(id(i,j), id(i+1,j), k*shu[i][j]);
            Link(id(i+1,j), id(i,j), k*shu[i][j]);
        }
 
}
 
queue<int> Q;
int num[3005]; double dis[3005]; bool inq[3005];
 
bool SPFA(){
    while( !Q.empty()) Q.pop();
    for(int i=1; i<=nm; i++){
        dis[i]=0; inq[i]=true; num[i]=0;
        Q.push(i);
    }
    while( !Q.empty()){
        int x=Q.front(); Q.pop(); inq[x]=false;
        for(int i=head[x]; i; i=nex[i]) {
            int v = point[i]; double w = weight[i];
            if(dis[v] > dis[x]+w+eps){
                dis[v] = dis[x] + w;
                if((++num[v]) > nm) return true;
                if( !inq[v]) inq[v] = true, Q.push(v);
            }
        }
    }
    return false;
}
 
 
bool Check(double k) {
    Build_graph(k);
    return SPFA();
}
 
void Half_Solve() {
    double l = 0, r = (d)sum;
    sum = 50;
    while(sum--) {
        double mid = (l + r) / 2;
        if(Check(mid)) l = mid;
        else r = mid;
    }
    printf("%.3lf", (l + r) / 2);
}
 
int main() {
    Input();
    Half_Solve();
    return 0;
}

4.bzoj1007:

由于我们要求直线上方的半平面交,注意到都是上方,则我们先按斜率排序,那么能被算成是边界的直线的交点的x坐标一定递增,用单调栈维护即可。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 50005
using namespace std;
const double eps = 1e-8;
int n, stk[N], top; bool ans[N];
struct LINE { double A, B; int id; } l[N];

bool cmp(const LINE a, const LINE b) {
    if(fabs(a.A - b.A) < eps) return a.B < b.B;
    else return a.A < b.A;
}

void Initlaize() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        scanf("%lf%lf", &l[i].A, &l[i].B);
        l[i].id = i;
    }
    sort(l+1, l+n+1, cmp);
}

double getx(int i, int j) {
    double x, y;
    x = l[i].A - l[j].A; y = l[j].B - l[i].B;
    return (y / x);
}

void insert(int i) {
    while(top) {
        if(fabs(l[stk[top]].A - l[i].A) < eps) top--;
        else if(top>1 && getx(i,stk[top-1]) <= getx(stk[top-1], stk[top]))
            top--;
        else break;
    }
    stk[++top] = i;
}

void Solve() {
    top = 0;
    for(int i=1; i<=n; i++) insert(i);
    memset(ans, false, sizeof(ans));
    for(int i=1; i<=top; i++) ans[l[stk[i]].id] = true;
    for(int i=1; i<=n; i++) if(ans[i]) printf("%d ", i);
}

int main() {
    Initlaize();
    Solve();
    return 0;
}

5.bzoj2957:

将斜率记录下来,然后分块,对于每个块中都维护一个最长上升序列,显然整个数组的答案序列是上升的,于是块与块之间的转移是可以用二分查找实现的。设块大小为 $x$,则我们单次修改复杂度为 $O(x)$,询问复杂度 $O(\lceil{n\over x}\rceil log_2^{x})$,那么当x取 $\sqrt{n\cdot log_2^n\over2}$时最优。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
using namespace std;
const double eps = 1e-10;
typedef double d;
typedef long long LL;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, m, b;
double k[N];
int belong[N];

struct BLOCK {
    double a[1010];
    int len, l, r;
    
    void Rebuild() {
        double maxk = 0; len = 0;
        for(int i=l; i<=r; i++)
            if(maxk+eps < k[i])
                maxk = k[i], a[++len] = k[i];
    }
    
    int get_ans(double & x) {
        int pos = (len+1)-(upper_bound(a+1, a+len+1, x+eps) - a);
        if(pos) x = a[len];
        return pos;
    }
} block[200];

int solve() {
    double maxk = 0;
    int ans = 0;
    for(int i=1; block[i].l>0; i++)
        ans += block[i].get_ans(maxk);
    return ans;
}

int main() {
    n = read(); m = read();
    b = (int)sqrt(n*log(n)/log(2)/2);
    for(int i=1; (i-1)*b+1<=n; i++) {
        block[i].l = (i-1) * b + 1;
        block[i].r = min(i * b, n);
    }
    for(int i=1; i<=n; i++)
        belong[i] = (i - 1) / b + 1;
    while(m--) {
        int x = read(), y = read();
        k[x] = (double) y / x;
        block[belong[x]].Rebuild();
        printf("%d\n", solve());
    }
    return 0;
}

用线段树维护每个区间单独考虑时的答案,合并答案时,我们要知道左儿子对右儿子的贡献,如果左儿子的最大值比右儿子的左儿子的最大值要大,那么右儿子的左儿子是不会对答案做出贡献,递归右儿子,否则右儿子的右儿子不会被修改的值所影响,递归左儿子。

#include <cstdio>
#include <algorithm>
#define N 100005
#define L(a) (a<<1)
#define R(a) (a<<1|1)
using namespace std;
static int n, m, num[N*4];
static double maxk[N*4];

int Solve(int p, int Le, int Re, double mk) {
    if(Le == Re) return (maxk[p] > mk) ? 1 : 0;
    int mid = (Le + Re) >> 1;
    if(mk >= maxk[L(p)]) return Solve(R(p),mid+1,Re,mk);
    else return num[p] - num[L(p)] + Solve(L(p),Le,mid,mk);
}

void Modify(int p, int Le, int Re, int x, double k) {
    if(Le == Re) { num[p]=1; maxk[p]=k; return; }
    int mid = (Le + Re) >> 1;
    if(x <= mid) Modify(L(p),Le,mid,x,k); else Modify(R(p),mid+1,Re,x,k);
    maxk[p] = max(maxk[L(p)], maxk[R(p)]);
    num[p] = num[L(p)] + Solve(R(p),mid+1,Re,maxk[L(p)]);
}

int main() {
    scanf("%d%d", &n, &m);
    while(m--) {
        int x, y; scanf("%d%d", &x, &y);
        Modify(1, 1, n, x, (double)y/x);
        printf("%d\n", num[1]);
    }
    return 0;
}

6.bzoj1072:

可重集合的排列问题,询问能除尽某一模数的排列有多少,蛤蛤暴力艹过。。。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int T, a[10], n, d, b[20], ans;
char ch[20];

void check() {
    long long x = 0;
    for(int i=1; i<=n; i++)
        x = x * 10 + b[i];
    if(x % d == 0) ans++;
}

void DFS(int p) {
    for(int i=0; i<=9; i++)
    if(a[i] > 0) {
        b[p] = i; a[i]--;
        if(p == n) check();
        else DFS(p+1);
        a[i]++;
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%s", ch); n = strlen(ch);
        scanf("%d", &d);
        memset(a, 0, sizeof(a));
        for(int i=0; i<n; i++) a[ch[i]-'0']++;
        ans = 0; DFS(1);
        printf("%d\n", ans);
    }
    return 0;
}

这种题目一般是数位dp,然而这题不行,于是自然的由数位转状压dp。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int T, n, mod, A[20]; char ch[20];
int a[10], dp[1050][1005];
int jie[10];
vector<int> stu[10];

int count(int x) {
    int sum = 0;
    for( ; x; x>>=1) if(x & 1) sum++;
    return sum;
}

void Pre_work() {
    jie[0] = 1;
    for(int i=1; i<=9; i++) jie[i] = jie[i-1] * i;
    for(int i=0; i<1024; i++) {
        int num = count(i);
        stu[num].push_back(i);
    }
}

void Solve() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i=0; i<=n; i++) {
        int sz = stu[i].size();
        for(int l=0; l<sz; l++) {
            int t = stu[i][l];
            for(int d=0; d<mod; d++)
                for(int j=1; j<=n; j++)
                if( !((1<<(j-1)) & t))
                    dp[((1<<(j-1)) | t)][(d*10+A[j]) % mod] += dp[t][d];
        }
    }
    for(int i=0; i<=9; i++) dp[(1<<n)-1][0] /= jie[a[i]];
    printf("%d\n", dp[(1<<n)-1][0]);
}

int main() {
    Pre_work();
    scanf("%d", &T);
    while(T--) {
        memset(a, 0, sizeof(a));
        scanf("%s%d", ch, &mod);
        n = strlen(ch);
        for(int i=0; i<n; i++) a[ch[i]-'0']++;
        for(int i=1; i<=n; i++) A[i] = ch[i-1] - '0';
        Solve();
    }
    return 0;
}

7.bzoj1037:

一开始设计了个三维dp[i][j][k]表示用了i个男,j个女,在所有后缀中,男比女多与女比男多的最大值为k时的方案,然后发现状态设置的太过模糊而无法转移。然后发现是四维dp。。。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MOD 12345678
using namespace std;
static int n, m, K, ans;
static int dp[155][155][25][25];
//dp[i][j][b][g]表示用了i个♂,j个♀, 在最大后缀中♂比♀多b人,♀比♂多g人
int main() {
    scanf("%d%d%d", &n, &m, &K);
    dp[0][0][0][0] = 1;
    for(int i=0; i<=n; i++)
     for(int j=0; j<=m; j++)
      for(int b=0; b<=K; b++)
       for(int g=0; g<=K; g++) {
           dp[i+1][j][b+1][max(g-1,0)] += dp[i][j][b][g];
           dp[i+1][j][b+1][max(g-1,0)] %= MOD;
           dp[i][j+1][max(b-1,0)][g+1] += dp[i][j][b][g];
           dp[i][j+1][max(b-1,0)][g+1] %= MOD;
       }
    for(int b=0; b<=K; b++)
        for(int g=0; g<=K; g++)
            ans = (ans + dp[n][m][b][g]) % MOD;
    printf("%d\n", ans);
    return 0;
}

8.bzoj3884:

这题太神我想不到QAQ,降幂大法确是一个有用的东西,不停地调用欧拉定理使得复杂度降为$O(log_2^p)$。许久不做数学欧拉函数都不会求了。但是感觉降幂大法有不对的地方,因为它没有保证$a^{\varphi(n)} \equiv1\ (mod\ n)$中 $a$与 $n$互质。而PoPoQQQ则处理了该种情况,他将$a$与 $n$ 同时约了 $2^k$。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int T, P;
int phi(int x) {
    int res = x;
    for(int i=2; i*i<=x; i++)
        if(x % i == 0) {
            res /= i; res *= (i-1);
            while( !(x % i)) x /= i;
        }
    if(x ^ 1) res /= x, res *= (x-1);
    return res;
}

int pow(int a, int b, int c) {
    if(b == 0) return 1 % c;
    if(b == 1) return a % c;
    int t = pow(a, b>>1, c); t = LL(t) * t % c;
    if(b & 1) return LL(t) * a % c;
    else return t;
}

int solve(int P) {
    if(P == 1) return 0;
    int phi_p = phi(P);
    return pow(2, solve(phi_p)+phi_p, P);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &P);
        printf("%d\n", solve(P));
    }
    return 0;
}

9.bzoj1041:

设整点坐标为 $(x,y)$,$0< x,y< r$,移项得 $y^2 = r^2-x^2 = (r+x)(r-x)$;设 $d = gcd(r+x, r-x)$,则可设 $r+x=d\cdot v^2,\ r-x=d\cdot u^2$,显然 $u<v$,那么$x,y,r$都可以用$d,u,v$表示,故$r = {d(v^2 + u^2)\over2}$,先用$O(\sqrt r)$的时间复杂度预处理出每个可行的 $d$,对于每个 $d$,枚举 $u$,这是$O(\sqrt({2*r\over d}))$的。总复杂度蒟蒻不会算,上界是$O({r\over {\sqrt d}})$的,但远远达不到。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned int u32;
u32 n;
u32 fac[1000005], tot = 0;
long long ans = 0;

void Calc_fac(u32 n) {
    u32 i;
    for(i=1; i*i<n; i++)
        if(n % i == 0)
            fac[++tot] = i, fac[++tot] = n / i;
    if(i*i == n) fac[++tot] = i;
}

int gcd(int a, int b) {
    if(b == 0) return a;
    else return gcd(b, a%b);
}

int main() {
    scanf("%u", &n);
    Calc_fac(n<<1);
    ans = 0;
    for(int i=1; i<=tot; i++) {
        u32 d = fac[i];
        if((n<<1) % d != 0) continue;
        u32 bd = (n<<1) / d;
        for(u32 u=1; u*u<=bd; u++) {
            u32 v = sqrt(bd - u*u);
            if(u >= v) break;
            if(u*u+v*v==bd && gcd(u,v)==1) ans++;
        }
    }
    printf("%lld\n", (ans+1)<<2);
    return 0;
}

10.bzoj1022:

这是nim游戏的变种,若全是1时特判一下就好,否则和正常nim一样。

#include <cstdio>
using namespace std;
int T, n, x, ans;
bool rev;

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        ans = 0; rev = false;
        for(int i=1; i<=n; i++) {
            scanf("%d", &x);
            if(x != 1) rev = true;
            ans ^= x;
        }
        if(rev) puts(ans ? "John" : "Brother");
        else puts(ans ? "Brother" : "John");
    }
    return 0;
}

11.bzoj3404:

因为每种状态的后继状态只有两种,故我们可以$O(1)$的转移SG函数,并且此题只需要知道SG函数是否为0。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
bool dp[1000005];
int T, n, mx, mn;

void work(int x) {
    mx = 0; mn = 10;
    for( ; x; x /=10)
        if(x % 10) {
            mx = max(mx, x % 10);
            mn = min(mn, x % 10);
        }
}

int main() {
    dp[0] = 0;
    for(int i=1; i<=1000000; i++) {
        work(i);
        dp[i] = !(dp[i-mx] & dp[i-mn]);
    }
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        puts(dp[n] ? "YES" : "NO");
    }
    return 0;
}

12.bzoj2653:

蒟蒻只会$O(n^2logn)$的暴力:用平衡树预处理出所有区间的中位数,复杂度$O(n^2logn)$,然后用线段树维护区间最值,预处理复杂度:$O(n^2)$,询问复杂度$O(Qnlogn)$,结果只有15分,其他的超时了。。。然后将线段树改成了ST表,预处理复杂度:$O(n^2logn)$,询问复杂度$O(Qn)$,终于拿满了暴力。。。

正解是二分答案,二分中位数是谁,然后就是套路了,大于二分的数的设为1,否则设为-1,只用看区间和大于等于0便可判断出是否可行。至于如何判断区间的两个端点都是一个范围的,我们可以先取必须取的区间信息,再在两端取一个从左或从右开始的区间最值信息。很抽象,但也很简单。这东西可以用线段树维护,但是我们不能对于每一个枚举的值便重新建一棵线段树,那么可以用主席树去做,时间空间均为$O(nlogn)$,所以总复杂度为建树+询问 = $O(nlogn+Qlog^2n)$。

暴力:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 2005
using namespace std;
static int n, Q, A[N], ans, q[4];
static int mid_num[N][N];
struct Treap_Tree {
    int fa[N], ch[N][2], key[N], siz[N], rad[N];
    int Index, root;
    
    void Init() {
        Index = root = 0;
        srand(23333);
    }
    
    void Newnode(int p, int x, int f) {
        fa[p] = f; key[p] = x; siz[p] = 1;
        ch[p][0] = ch[p][1] = 0;
        rad[p] = rand() % 100000;
    }
    
    void rotate(int x) {
        int y=fa[x], z=fa[y], l, r;
        l = (ch[y][1]==x); r = l^1;
        if(y != root) ch[z][ch[z][1]==y] = x;
        fa[x] = z; fa[y] = x; fa[ch[x][r]] = y;
        ch[y][l] = ch[x][r]; ch[x][r] = y;
        siz[y] = siz[ch[y][0]] + siz[ch[y][1]] + 1;
        siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
        if(fa[x] == 0) root = x;
    }
    
    void Treap(int p) {
        while(fa[p] && rad[fa[p]] > rad[p])
            rotate(p);
    }
    
    void Insert(int x) {
        if(root == 0) {
            root = Index = 1;
            Newnode(root, x, 0);
            return;
        }
        int p = root, f;
        while(p) {
            f = p;
            if(x <= key[p]) p = ch[p][0];
            else p = ch[p][1];
        }
        int d; if(x <= key[f]) d=0; else d=1;
        ch[f][d] = ++Index; Newnode(ch[f][d], x, f);
        p = ch[f][d]; while(fa[p]) {p=fa[p]; siz[p]++;}
        Treap(ch[f][d]);
    }

    int Query_num(int rank) {
        int p = root;
        while(p > 0) {
            if(rank == siz[ch[p][0]]+1) return key[p];
            if(rank < siz[ch[p][0]]+1) p = ch[p][0];
            else { rank -= (siz[ch[p][0]]+1); p = ch[p][1]; }
        }
    }
    
} T;

struct Sparse_Table {
    int Max[13][N];
    
    void Build(int id) {
        for(int i=1; i<=n; i++) Max[0][i] = mid_num[id][i];
        for(int k=1; k<=12; k++) {
            int len = (1 << k);
            for(int i=1; i<=(n-len+1); i++)
                Max[k][i] = max(Max[k-1][i], Max[k-1][i+(len>>1)]);
        }
    }
    
    int Query_max(int l, int r) {
        int len = (r - l + 1);
        int k; for(k=0; (1<<(k+1))<=len; k++);
        return max(Max[k][l], Max[k][r-(1<<k)+1]);
    }
    
} ST[N];

void Pre_work() {
    for(int i=1; i<=n; i++) {
        T.Init();
        for(int j=i; j<=n; j++) {
            T.Insert(A[j]);
            int rk = (T.siz[T.root] >> 1) + 1;
            mid_num[j][i] = mid_num[i][j] = T.Query_num(rk);
        }
    }
    for(int i=1; i<=n; i++) ST[i].Build(i);
}

int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &A[i]);
    Pre_work();
    scanf("%d", &Q);
    while(Q--) {
        for(int i=0; i<4; i++) {
            scanf("%d", &q[i]);
            q[i] = (q[i] + ans) % n + 1;
        }
        sort(q, q+4); ans = -1000000000;
        for(int i=q[0]; i<=q[1]; i++)
            ans = max(ans, ST[i].Query_max(q[2], q[3]));
        printf("%d\n", ans);
    }
    return 0;
}

正解:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <algorithm>
#define N 20005
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, Q, ans, q[4], A[N], Index = 0;
pair<int,int> h[N];
map<int,int> root_id;
int T[N];
struct Node {
    int Lc, Rc;
    int Sum, Lsum, Rsum;
} s[N*100];

void Build(int p, int Le, int Re) {
    if(Le == Re) {s[p].Sum = s[p].Lsum = s[p].Rsum = 1; return;}
    int mid = (Le + Re) >> 1;
    s[p].Lc = ++Index; s[p].Rc = ++Index;
    Build(s[p].Lc, Le, mid); Build(s[p].Rc, mid+1, Re);
    s[p].Sum = s[s[p].Lc].Sum + s[s[p].Rc].Sum;
    s[p].Lsum = s[p].Rsum = s[p].Sum;
}

void Insert(int p, int p1, int Le, int Re, int x) {
    s[p].Lc = s[p1].Lc; s[p].Rc = s[p1].Rc;
    if(Le == Re) { s[p].Sum = -1; s[p].Lsum = s[p].Rsum = 0; return; }
    int mid = (Le + Re) >> 1;
    if(x <= mid) s[p].Lc = ++Index; else s[p].Rc = ++Index;
    if(x <= mid) Insert(s[p].Lc, s[p1].Lc, Le, mid, x);
    else Insert(s[p].Rc, s[p1].Rc, mid+1, Re, x);
    s[p].Sum = s[s[p].Lc].Sum + s[s[p].Rc].Sum;
    s[p].Lsum = max(0, max(s[s[p].Lc].Lsum, s[s[p].Lc].Sum + s[s[p].Rc].Lsum));
    s[p].Rsum = max(0, max(s[s[p].Rc].Rsum, s[s[p].Rc].Sum + s[s[p].Lc].Rsum));
}

int Query_sum(int p, int Le, int Re, int l, int r) {
    if(Le == l && Re == r) return s[p].Sum;
    int mid = (Le + Re) >> 1;
    if(r <= mid) return Query_sum(s[p].Lc, Le, mid, l, r);
    else if(l > mid) return Query_sum(s[p].Rc, mid+1, Re, l, r);
    else return Query_sum(s[p].Lc,Le,mid,l,mid) + Query_sum(s[p].Rc,mid+1,Re,mid+1,r);
}

int Query_Lsum(int p, int Le, int Re, int l, int r) {
    if(Le == l && Re == r) return s[p].Lsum;
    int mid = (Le + Re) >> 1;
    if(r <= mid) return Query_Lsum(s[p].Lc, Le, mid, l, r);
    else if(l > mid) return Query_Lsum(s[p].Rc, mid+1, Re, l, r);
    else return max(Query_Lsum(s[p].Lc, Le, mid, l, mid), Query_sum(s[p].Lc, Le, mid, l, mid) + Query_Lsum(s[p].Rc, mid+1, Re, mid+1, r));
}

int Query_Rsum(int p, int Le, int Re, int l, int r) {
    if(Le == l && Re == r) return s[p].Rsum;
    int mid = (Le + Re) >> 1;
    if(r <= mid) return Query_Rsum(s[p].Lc, Le, mid, l, r);
    else if(l > mid) return Query_Rsum(s[p].Rc, mid+1, Re, l, r);
    else return max(Query_Rsum(s[p].Rc, mid+1, Re, mid+1, r), Query_sum(s[p].Rc, mid+1, Re, mid+1, r) + Query_Rsum(s[p].Lc, Le, mid, l, mid));
}

void Pre_work() {
    sort(h+1, h+n+1);
    T[0] = ++Index;
    Build(T[0], 1, n);
    for(int i=1; i<=n; i++) {
        T[i] = ++Index;
        root_id[h[i].first] = T[i];
        Insert(T[i], T[i-1], 1, n, h[i].second);
    }
    for(int i=n; i>=1; i--) {
        while(h[i].first == h[i-1].first) i--;
        root_id[h[i].first] = root_id[h[i-1].first];
    }
    root_id[h[1].first] = T[0];
}

bool check(int id) {
    int sum = Query_sum(id, 1, n, q[1], q[2]);
    if(q[0] != q[1]) sum += Query_Rsum(id, 1, n, q[0], q[1]-1);
    if(q[2] != q[3]) sum += Query_Lsum(id, 1, n, q[2]+1, q[3]);
    return sum >= 0;
}

int main() {
    n = read();
    for(int i=1; i<=n; i++) {
        A[i] = read();
        h[i] = make_pair(A[i], i);
    }
    Pre_work();
    Q = read(); ans = 0;
    while(Q--) {
        for(int i=0; i<4; i++) q[i] = (read() + ans) % n + 1;
        sort(q, q+4);
        int l = 1, r = n;
        while(l <= r) {
            int mid = (l + r) >> 1;
            int id = root_id[h[mid].first];
            if(check(id)) { ans = h[mid].first; l = mid+1; }
            else r = mid-1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

13. bzoj3653:

很明显,由于c的选取与a,b的关系仅为c在a和b的子树中,自然的想到用dfs序。然后对于a,b的选取有两种情况:1.b是a的祖先,那么b有$min(dep[a],k)$种选法,c有a的子树大小种选法;2.a是b的祖先,那么这一部分对答案的贡献为$\sum size[b_i]$,b表示所有合法的b的选取点,显然b是a的子孙并且$dep[b]-dep[a]\le k$,我们就可以建一棵以深度为轴,以dfs序为的主席树,那么对于第二个答案我们就可以用$O(logn)$的时间得到。时空复杂度均为$O(nlogn)$。也可以离线用树状数组处理,空间复杂度为O(n),并且常数更小。
正解:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#define N 300005
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
static int n, Q; LL Ans;
vector<int> depv[N];
static int head[N], nex[N*2], point[N*2], cnt;
static int dep[N], siz[N], dfs1[N], dfs2[N], Index;
static int T[N];
map<int,int> root_id;
struct Node {
    int Lc, Rc;
    LL Sum;
} s[N*70];

void Link(int x, int y) {
    nex[++cnt] = head[x]; head[x] = cnt;
    point[cnt] = y;
}

void DFS(int p, int f) {
    dep[p] = dep[f] + 1;
    dfs1[p] = ++Index;
    siz[p] = 1;
    for(int j=head[p]; j; j=nex[j])
        if(point[j] != f) {
            DFS(point[j], p);
            siz[p] += siz[point[j]];
        }
    dfs2[p] = Index;
}

void Build(int &p, int Le, int Re) {
    if(p == 0) p = ++Index; if(Le == Re) return;
    int mid = (Le + Re) >> 1;
    Build(s[p].Lc, Le, mid); Build(s[p].Rc, mid+1, Re);
}

void Insert(int &p, int p1, int Le, int Re, int x, int add) {
    if(p == 0) p = ++Index; s[p] = s[p1];
    if(Le == Re) { s[p].Sum = add; return; }
    int mid = (Le + Re) >> 1;
    if(x <= mid) Insert(s[p].Lc=0, s[p1].Lc, Le, mid, x, add);
    else Insert(s[p].Rc=0, s[p1].Rc, mid+1, Re, x, add);
    s[p].Sum = s[s[p].Lc].Sum + s[s[p].Rc].Sum;
}

void Pre_work() {
    for(int i=1; i<=n; i++) depv[dep[i]].push_back(i);
    Index = 0; Build(T[0], 1, n);
    root_id[0] = T[0]; int tot = 0;
    
    for(int i=1; i<=n; i++) {
        int sz = depv[i].size();
        if(sz == 0) root_id[i] = root_id[i-1];
        for(int j=0; j<sz; j++) {
            tot++; int v = depv[i][j];
            Insert(T[tot], T[tot-1], 1, n, dfs1[v], siz[v]-1);
            root_id[i] = T[tot];
        }
    }
}

LL Qsum(int p, int Le, int Re, int l, int r) {
    if(Le == l && Re == r) return s[p].Sum;
    int mid = (Le + Re) >> 1;
    if(r <= mid) return Qsum(s[p].Lc, Le, mid, l, r);
    else if(l > mid) return Qsum(s[p].Rc, mid+1, Re, l, r);
    else return Qsum(s[p].Lc, Le, mid, l, mid) + Qsum(s[p].Rc, mid+1, Re, mid+1, r);
}

int main() {
    memset(head, 0, sizeof(head)); cnt = 0;
    n=read(); Q=read();
    for(int i=1; i<n; i++) {
        int u=read(), v=read();
        Link(u, v); Link(v, u);
    }
    Index = 0;
    DFS(1, 0);
    Pre_work();
    while(Q--) {
        int a=read(), k=read();
        Ans = min(dep[a]-1, k) * (LL)(siz[a]-1);
        if(dfs1[a] != dfs2[a])
            Ans += Qsum(root_id[min(dep[a]+k, n)], 1, n, dfs1[a]+1, dfs2[a]);
        printf("%lld\n", Ans);
    }
    return 0;
}

14. spoj962:

哈哈这不是bzoj的题,滥竽充数啦。注意到要求的路径不能经过重复的点,那么我们要求从12再到3,可以拆成两条路径即2-->12-->3,由于题目中有每个点只能经过一次,这可以用网络流限流实现。
这里有一个卡常小技巧,存边的时候我们用一个结构体封装,这样可以将信息存在一段连续的内存从而加速访问,如果用数组分开存那么由于不断访问不连续的内存而使常数变很大。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 100000
#define M 2000000
#define INF 1000000000
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int T, n, m, s, t;
struct Edge {
    int nex, to, flow;
} e[M];
int head[N], cnt;
int cen[N]; queue<int> Q;
 
inline int in(int x) { return x; }
inline int out(int x) { return x+n; }
 
void Link(int x, int y, int c) {
    e[++cnt].nex = head[x]; head[x] = cnt;
    e[cnt].to = y; e[cnt].flow = c;
}
 
bool BFS() {
    for(int i=s; i<=t; i++) cen[i] = -1;
    Q.push(s); cen[s] = 0;
    while( !Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int j=head[u]; j; j=e[j].nex)
        if(e[j].flow > 0) {
            int v = e[j].to;
            if(cen[v] < 0) {
                cen[v] = cen[u] + 1;
                Q.push(v);
            }
        }
    }
    return cen[t] > 0;
}
 
int DFS(int p, int minF) {
    if(p==t || minF==0) return minF;
    int minf = minF;
    for(int j=head[p]; j; j=e[j].nex)
    if(e[j].flow && cen[e[j].to] == cen[p]+1) {
        int f = DFS(e[j].to, min(minf, e[j].flow));
        e[j].flow -= f; e[j^1].flow += f;
        minf -= f; if(minf == 0) break;
    }
    return minF - minf;
}
 
int Dinic() {
    int ans = 0;
    while(BFS())
        ans += DFS(s, INF);
    return ans;
}
 
int main() {
    T = read();
    while(T--) {
        n = read(); m = read();
        s = 0; t = n * 2 + 1;
        for(int i=s; i<=t; i++) head[i]=0; cnt = 1;
        Link(s, out(2), 2); Link(out(2), s, 0);
        Link(in(1), t, 1); Link(t, in(1), 0);
        Link(in(3), t, 1); Link(t, in(3), 0);
        for(int i=4; i<=n; i++)
            Link(in(i), out(i), 1), Link(out(i), in(i), 0);
        for(int i=1; i<=m; i++) {
            int u=read(), v=read();
            if(u<1 || u>n || v<1 || v>n) continue;
            Link(out(u), in(v), 1); Link(in(v), out(u), 0);
            Link(out(v), in(u), 1); Link(in(u), out(v), 0);
        }
        
        if(Dinic() == 2) puts("YES");
        else puts("NO");
    }
    
    return 0;
} 

15. bzoj3522:

这真是一道好题,我们想到枚举每个中间点,然后对于每个子树深度相同的点集可以对答案做出贡献,现在问题变为给你$a_1,a_2,...,a_n$这n个数,从中选3个数组合出的所有数的和。这里有一个套路:首先我们考虑从中选两个即:$a_1a_2+a_1a_3+a_1a_4+a_2a_3+a_2a_4+a_3a_4$(此处取n=4),合并一下得:$a_4(\sum_{i=1}^3a_i)+a_3(\sum_{i=1}^2a_i)+a_2(\sum_{i=1}^1a_i)$,这显然可以$O(n)$递推,从中选三个也是同理。然后推出公式乱搞一下。代码中有三层循环,但是其中有一个枚举子树的循环放在全局看只是将每条边遍历了两次,当然就是均摊$O(1)$的。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 5050
using namespace std;
static int n, dep_num[N], f1[N], f2[N];
static int head[N], nex[N*2], point[N*2], cnt;
static long long ans;

void Link(int x, int y) {
    nex[++cnt] = head[x]; head[x] = cnt;
    point[cnt] = y;
}

void DFS(int p, int f, int d) {
    dep_num[d]++;
    for(int j=head[p]; j; j=nex[j])
        if(point[j] != f) DFS(point[j], p, d+1);
}

int main() {
    scanf("%d", &n);
    memset(head, 0, sizeof(head)); cnt = 0;
    for(int i=1; i<n; i++) {
        int u,v; scanf("%d%d", &u, &v);
        Link(u, v); Link(v, u);
    }
    for(int i=1; i<=n; i++) {
        memset(f1, 0, sizeof(f1));
        memset(f2, 0, sizeof(f2));
        for(int j=head[i]; j; j=nex[j]) {
            memset(dep_num, 0, sizeof(dep_num));
            DFS(point[j], i, 1);
            for(int k=1; k<=n; k++) {
                ans += (long long)f2[k] * dep_num[k];
                f2[k] += f1[k] * dep_num[k];
                f1[k] += dep_num[k];
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

16. bzoj2127:

丢链跑:bzoj2127: happiness

17. bzoj3894:

这一题和上一题还是有这很大区别的,比如这里他一次打包五个人,于是就不能用二元组建图了,我们需要新加节点来表示打包选取的代价。同样可以用总收益减去最小割,单个人选择文理可以用s连向id一条容量为选文的代价,id连向t一条容量为选理的代价。新建一个点打包同时选文的代价,s向该点连一条容量为同时选文的代价,该点向其打包的五个点连容量为正无穷的边,这样表示,如果割了某一条文的边,那么就一定要个同时选文的边。选理同样的。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 30005
#define INF 1000000000
#define REP(a,l,r) for(int a=l; a<=r; a++)
using namespace std;
int n, m, nm, s, t, x, SUM;
struct Edge { int nex, to, flow; } e[N*25];
int head[N], cnt;
int cen[N]; queue<int> Q;

inline int id(int x, int y) { return m*(x-1)+y; }
inline int wid(int x, int y) { return m*(x-1)+y+nm; }
inline int lid(int x, int y) { return m*(x-1)+y+nm+nm; }

void Link(int x, int y, int z) {
    e[++cnt].nex = head[x]; head[x] = cnt;
    e[cnt].to = y; e[cnt].flow = z;
}

void insert(int x, int y, int z) {
    Link(x, y, z); Link(y, x, 0);
}

void initlaize() {
    scanf("%d%d", &n, &m);
    nm = n * m; SUM = 0;
    s = 0; t = nm * 3 + 1;
    
    memset(head, 0, sizeof(head)); cnt = 1;
    REP(i,1,n) REP(j,1,m) {
        scanf("%d", &x); SUM += x;
        insert(s, id(i,j), x);
    }
    REP(i,1,n) REP(j,1,m) {
        scanf("%d", &x); SUM += x;
        insert(id(i,j), t, x);
    }
    REP(i,1,n) REP(j,1,m) {
        scanf("%d", &x); SUM += x;
        insert(s, wid(i,j), x); insert(wid(i,j), id(i,j), INF);
        if(i>1) insert(wid(i,j), id(i-1,j), INF);
        if(i<n) insert(wid(i,j), id(i+1,j), INF);
        if(j>1) insert(wid(i,j), id(i,j-1), INF);
        if(j<m) insert(wid(i,j), id(i,j+1), INF);
    }
    REP(i,1,n) REP(j,1,m) {
        scanf("%d", &x); SUM += x;
        insert(lid(i,j), t, x); insert(id(i,j), lid(i,j), INF);
        if(i>1) insert(id(i-1,j), lid(i,j), INF);
        if(i<n) insert(id(i+1,j), lid(i,j), INF);
        if(j>1) insert(id(i,j-1), lid(i,j), INF);
        if(j<m) insert(id(i,j+1), lid(i,j), INF);
    }
}

bool bfs() {
    for(int i=s; i<=t; i++) cen[i] = -1;
    Q.push(s); cen[s] = 0;
    while( !Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int j=head[u]; j; j=e[j].nex)
        if(e[j].flow > 0) {
            int v = e[j].to;
            if(cen[v] < 0) {
                cen[v] = cen[u] + 1;
                Q.push(v);
            }
        }
    }
    return cen[t] > 0;
}

int dfs(int p, int minF) {
    if(p==t || minF==0) return minF;
    int minf = minF;
    for(int j=head[p]; j; j=e[j].nex)
        if(e[j].flow && cen[e[j].to] == cen[p]+1) {
            int f = dfs(e[j].to, min(minf, e[j].flow));
            e[j].flow -= f; e[j^1].flow += f;
            minf -= f; if(minf == 0) break;
        }
    return minF - minf;
}

int dinic() {
    int ans = 0;
    while(bfs()) ans += dfs(s, INF);
    return ans;
}

int main() {
    initlaize();
    printf("%d\n", SUM - dinic());
    return 0;
}

18. bzoj1260:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
char s[55]; int n;
int dp[55][55];

int main() {
    scanf("%s", s+1);
    n = strlen(s+1);
    memset(dp, 127/3, sizeof(dp));
    for(int i=1; i<=n; i++) dp[i][i] = 1;
    for(int k=2; k<=n; k++)
        for(int i=1; i<=n; i++) {
            int l = i, r = i+k-1, len = 0, j;
            while(len<k && s[l] == s[r-len]) len++;
            if(len == k) dp[l][r] = 1;
            else {
                for(j=l; j<=r; j++)
                    dp[l][r] = min(dp[l][r], dp[l][j] + dp[j+1][r]);
                j = l; while(j<r && s[j+1]==s[l]) j++;
                dp[l][r] = min(dp[l][r], dp[j+1][r-len]+1);
                if(len > 0)
                    for(j=r-1; j>=l; j--)
                        if(s[j] == s[r])
                            dp[l][r] = min(dp[l][r], dp[l][j] + dp[j+1][r]-1);
            }
        }
    printf("%d\n", dp[1][n]);
    return 0;
}

19. bzoj3832:

给定一张有向无环图,删掉其中某个点后使得最长链最短。由于图有可能并不连通,我们可以再建一个源汇,令pre[i]表示si的最长链长度,suf[i]表示it的最长链长度,那么一条边(u,v)所在的链中最长的长度可以用pre[u]+1+suf[v]表示,这样的话,最长链上的每一条边都可以代表这条最长链。我们将图拓扑排序一下建出分层图,在每一层中把那一层的边提出来,显然这是一个割集,我们要知道的就是割集中的pre[u]+1+suf[v]最大的那个。所以我们按照拓扑序枚举每一个节点,计算删掉此点后对答案的贡献。首先需要将所有点的suf[i]插入到一棵权值线段树中,然后按拓扑序依次扫过去,对于点x,先将x的所有前驱边对答案的贡献删除,在将suf[x]也删除,此时线段树中的最大值即为删去x后的最长链长度。处理完后加入pre[x]和x的所有后继边对答案的贡献。这个过程类似于扫描线和分治,从左到右依次扫描过去,不断将右边的集合划到左边的集合去,这一步是单纯计算左边与右边对答案的单独贡献,然后处理左右合起来对答案的贡献,这样就像分治里合并集合的贡献。正确性我也不会只能感受一下了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 500005
#define M 2000005
#define L(a) (a<<1)
#define R(a) (a<<1|1)
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
static int n, m, s, t, ans, ansx;
static int in_dgr[N], out_dgr[N], q[N];
static int pre[N], suf[N];
struct Edge { int nex, to; } e[M*4];
static int head[2][N], cnt;

struct Segment_Tree {
    int Sum[N*4], Max[N*4];
    
    void Init() {
        memset(Sum, 0, sizeof(Sum));
        memset(Max, 0, sizeof(Max));
    }
    
    void Modify(int p, int l, int r, int x, int v) {
        if(l == r) {
            Sum[p] += v;
            if(Sum[p] > 0) Max[p] = l;
            else Max[p] = Sum[p] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) Modify(L(p), l, mid, x, v);
        else Modify(R(p), mid+1, r, x, v);
        Sum[p] = Sum[L(p)] + Sum[R(p)];
        Max[p] = max(Max[L(p)], Max[R(p)]);
    }
    
    int Q_max() { return Max[1]; }
    
} T;

void Link(int x, int y, int d) {
    e[++cnt].nex = head[d][x]; head[d][x] = cnt;
    e[cnt].to = y;
}

void initlaize() {
    n=read(); m=read(); s=0; t=n+1;
    for(int i=1; i<=m; i++) {
        int u=read(), v=read();
        Link(u, v, 0); Link(v, u, 1);
        out_dgr[u]++; in_dgr[v]++;
    }
    for(int i=1; i<=n; i++) {
        out_dgr[i]++; in_dgr[i]++;
        Link(s, i, 0); Link(i, s, 1);
        Link(i, t, 0); Link(t, i, 1);
    }
    out_dgr[s] = in_dgr[t] = n;
}

void Pre_work() {
    int hd = 0, tl = 0; q[0] = t;
    while(hd <= tl) {
        int x = q[hd++];
        for(int j=head[1][x]; j; j=e[j].nex) {
            int y = e[j].to;
            suf[y] = max(suf[y], suf[x]+1);
            if((--out_dgr[y]) == 0) q[++tl] = y;
        }
    }
    hd = tl = 0; q[0] = s;
    while(hd <= tl) {
        int x = q[hd++];
        for(int j=head[0][x]; j; j=e[j].nex) {
            int y = e[j].to;
            pre[y] = max(pre[y], pre[x]+1);
            if((--in_dgr[y]) == 0) q[++tl] = y;
        }
    }
}

void Solve() {
    ans = 0x7fffffff;
    T.Init();
    for(int i=s; i<=t; i++) T.Modify(1, 0, n+2, suf[i], 1);
    for(int i=s; i<=t; i++) {
        int x = q[i];
        for(int j=head[1][x]; j; j=e[j].nex)
            T.Modify(1, 0, n+2, pre[e[j].to]+1+suf[x], -1);
        T.Modify(1, 0, n+2, suf[x], -1);
        if(T.Q_max() < ans && x!=s && x!=t) ans = T.Q_max(), ansx = x;
        for(int j=head[0][x]; j; j=e[j].nex)
            T.Modify(1, 0, n+2, pre[x]+1+suf[e[j].to], 1);
        T.Modify(1, 0, n+2, pre[x], 1);
    }
    printf("%d %d", ansx, ans-2);
}

int main() {
    initlaize();
    Pre_work();
    Solve();
    return 0;
}

20. bzoj4551:

这题我没有想出官方正解。这题给节点打标记,实际上相当于给它的子树垒上一个标记,这个标记当然是和以前的标记进行比较并保存深度较大的标记,用线段树乱搞一下就行了,由于线段树部分比较简单所以没有写封装。
正解很神,倒序处理操作,那么显然对于每个点的答案深度是单调递减的,这就可以用并查集搞了,复杂度:$O(q\cdot\alpha n)$

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
#define L(a) (a<<1)
#define R(a) (a<<1|1)
using namespace std;
static int n, m, x, Index;
static int dfn1[N], dfn2[N], dep[N];
static int head[N], nex[N*2], to[N*2], cnt;
char opt[3];

void Link(int x, int y) {
    nex[++cnt] = head[x]; head[x] = cnt;
    to[cnt] = y;
}

void dfs(int p, int f) {
    dep[p] = dep[f] + 1;
    dfn1[p] = ++Index;
    for(int j=head[p]; j; j=nex[j])
        if(to[j] != f) dfs(to[j], p);
    dfn2[p] = Index;
}

int fa[N*4];
void Build(int p, int l, int r) {
    fa[p] = 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    Build(L(p), l, mid); Build(R(p), mid+1, r);
}

void Modify(int p, int Le, int Re, int l, int r, int x, int f) {
    if(dep[f] >= dep[fa[p]]) fa[p] = f;
    if(Le == l && Re == r) {
        if(dep[x] >= dep[fa[p]]) fa[p] = x;
        return;
    }
    int mid = (Le + Re) >> 1;
    if(r <= mid) Modify(L(p), Le, mid, l, r, x, fa[p]);
    else if(l > mid) Modify(R(p), mid+1, Re, l, r, x, fa[p]);
    else {
        Modify(L(p), Le, mid, l, mid, x, fa[p]);
        Modify(R(p), mid+1, Re, mid+1, r, x, fa[p]);
    }
}

int  Query(int p, int l, int r, int x, int f) {
    if(dep[f] >= dep[fa[p]]) fa[p] = f;
    if(l == r) return fa[p];
    int mid = (l + r) >> 1;
    if(x <= mid) return Query(L(p), l, mid, x, fa[p]);
    else return Query(R(p), mid+1, r, x, fa[p]);
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i=1; i<n; i++) {
        int u,v; scanf("%d%d", &u, &v);
        Link(u, v); Link(v, u);
    }
    dfs(1, 0);
    Build(1, 1, n);
    while(m--) {
        scanf("%s%d", opt, &x);
        if(opt[0] == 'C')
            Modify(1, 1, n, dfn1[x], dfn2[x], x, 1);
        else printf("%d\n", Query(1, 1, n, dfn1[x], 1));
    }
    return 0;
}

21. bzoj3887:

如果我们到了某个点,则必定把该点所在的强连通分量走完,这样答案不会更差。我们不走一条反向边,答案就为1号点所在连通块大小。如果要走反向边,那么则必定又要形成一个新环,我们枚举反向边,然后统计拆开的两条链对答案的贡献。一开始把数组的最小值设的太小,运算时爆int所以WA了一次。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#define N 100005
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
static int n, m, ans;
static int head[N], nex[N], to[N], cnt;
static int dfn[N], low[N], Index, bcnt, be[N], val[N];
static int stk[N], top; bool instk[N];
set<int> S[N];
queue<int> Q;

void Link(int x, int y) {
    nex[++cnt] = head[x]; head[x] = cnt;
    to[cnt] = y;
}

void initlaize() {
    n=read(); m=read();
    for(int i=1; i<=m; i++) {
        int u=read(), v=read();
        Link(u, v);
    }
}

void Tarjan(int p) {
    dfn[p] = low[p] = ++Index;
    stk[++top] = p; instk[p] = true;
    for(int j=head[p]; j; j=nex[j])
        if(dfn[to[j]] == 0) {
            Tarjan(to[j]);
            low[p] = min(low[p], low[to[j]]);
        }
        else if( instk[to[j]])
            low[p] = min(low[p], dfn[to[j]]);
    if(dfn[p] == low[p]) {
        int v; bcnt++;
        do {
            v = stk[top--];
            instk[v] = false;
            be[v] = bcnt; val[bcnt]++;
        } while(v != p);
    }
}

struct Topo_Graph {
    int head1[N], nex1[N], to1[N], cnt1;
    int dp[N]; bool inq[N];
    
    void init() {
        memset(head1, 0, sizeof(head1));
        cnt1 = 0;
    }
    
    void link(int x, int y) {
        nex1[++cnt1] = head1[x]; head1[x] = cnt1;
        to1[cnt1] = y;
    }
    
    void spfa() {
        memset(dp, -(127/3), sizeof(dp));
        Q.push(be[1]); dp[be[1]] = val[be[1]];
        inq[be[1]] = true;
        while( !Q.empty()) {
            int x = Q.front(); Q.pop(); inq[x] = false;
            for(int j=head1[x]; j; j=nex1[j]) {
                int y = to1[j];
                if(dp[x] + val[y] > dp[y]) {
                    dp[y] = dp[x] + val[y];
                    if( !inq[y]) { Q.push(y); inq[y]=true; }
                }
            }
        }
    }
    
} G1, G2;

void Tarjan() {
    memset(instk, false, sizeof(instk));
    Index = 0;
    for(int i=1; i<=n; i++)
        if(dfn[i] == 0) Tarjan(i);
    for(int i=1; i<=n; i++)
        for(int j=head[i]; j; j=nex[j])
            if(be[i] != be[to[j]])
                S[be[i]].insert(be[to[j]]);
    G1.init(); G2.init();
    for(int i=1; i<=bcnt; i++)
        for(set<int>::iterator j=S[i].begin(); j!=S[i].end(); j++)
            G1.link(i, *j), G2.link(*j, i);
}

void solve() {
    G1.spfa(); G2.spfa();
    ans = val[be[1]];
    for(int i=1; i<=bcnt; i++)
        for(set<int>::iterator j=S[i].begin(); j!=S[i].end(); j++)
            ans = max(ans, G1.dp[*j] + G2.dp[i] - val[be[1]]);
    printf("%d\n", ans);
}

int main() {
    initlaize();
    Tarjan();
    solve();
    return 0;
}

22. bzoj2440:

莫比乌斯函数的应用,二分答案x,然后判断小于等于x的数中有多少个不含平方数因数的数。这个东西可以用容斥来做,即答案为0个质因子的平方的倍数-1个质因子的平方的倍数+2……,这个式子最终为$\displaystyle Q_x=\sum_{i=1}^{\sqrt x}(-1)^{含有单个质因子个数}{x\over{i\times i}}$,然后我们发现$(-1)^{含有单个质因子个数}$这个系数实际上就是莫比乌斯函数,故$\displaystyle Q_x=\sum_{i=1}^{\sqrt x}\mu(i){x\over{i\times i}}$

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int T; LL n;
int mu[50005];
int p[50005], tot;
bool prime[50005];

int GET_MU() {
    memset(prime, true, sizeof(prime));
    mu[1] = 1; tot = 0;
    for(int i=2; i<=50000; i++) {
        if(prime[i]) p[++tot]=i, mu[i]=-1;
        for(int j=1; j<=tot && p[j]*i<=50000; j++) {
            prime[i*p[j]] = false;
            if(i % p[j] == 0) { mu[i*p[j]] = 0; break; }
            else mu[i*p[j]] = -mu[i];
        }
    }
}

LL Q(int x) {
    LL sum = 0;
    for(int i=1; i*i<=x; i++)
        sum += (mu[i] * (x / (i*i)));
    return sum;
}

LL solve() {
    LL l = 0, r = 0x7fffffff;
    while(l <= r) {
        LL mid = (l + r) >> 1;
        if(Q(mid) < n) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}


int main() {
    GET_MU();
    scanf("%d", &T);
    while(T--) {
        scanf("%lld", &n);
        printf("%lld\n", solve());
    }
    return 0;
}

23. bzoj2005:

求$\displaystyle \sum_i=1}^n \sum_{j=1}^m2\times \gcd(i,j)-1$,实际上就是$\displaystyle 2\times \sum_{i=1}^n \sum_{j=1}^m\gcd(i,j) - n\times m$。问题就转化为了求$\displaystyle \sum_{i=1}^n \sum_{j=1}^m\gcd(i,j)$。我们知道$\displaystyle n=\sum_{d (n) \varphi(d)$,那么就可以将原式转化为$\displaystyle \sum_i=1}^n \sum_{j=1}^m \sum_{d (\gcd(i,j)) \varphi(d)$,交换一下枚举顺序:$\displaystyle \sum_d (\gcd(i,j)) \sum_i=1}^n \sum_{j=1}^m d (i\varphi(d)$,其中$[S]$表示当表达式$S$成立时$[S]$值为1,否则为0。
注意到$\displaystyle \sum_{i=1
)
^n \sum_j=1}^m d (i$式子值为1时,总个数实际上与$\displaystyle \lfloor {n\over d) \rfloor\lfloor m\over d}\rfloor$相等,即在1~n中d的倍数与1~m中d的倍数的乘积。
原式现在变为:$\displaystyle \sum_{d (\gcd(i,j))
\lfloor {n\over d}\rfloor\lfloor {m\over d}\rfloor \varphi(d)$。注意到$\displaystyle \lfloor {n\over d}\rfloor\lfloor {m\over d}\rfloor$的取值的个数,打一张表会发现,数$n$的约数个数是$O(\sqrt n)$级别的,证明也不难:在$1$~$\sqrt n$中每个数都可为n的约数,在$\sqrt n$~$n$中每个n的约数都有且仅有一个${n\over d}$与之对应,而${n\over d}\in[1,\sqrt n]$,所以$n$的约数个数是$O(\sqrt n)$的,所以$\lfloor {n\over d}\rfloor$的个数也是$O(\sqrt n)$的,故$\lfloor {n\over d}\rfloor\lfloor {m\over d}\rfloor$的级别是$O(\sqrt n+ \sqrt m)$的。于是我们将$\lfloor {n\over d}\rfloor\lfloor {m\over d}\rfloor$不同的值的那一段分块出来就好了,乘上欧拉函数的某一段的和。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
using namespace std;
typedef long long LL;
static int n, m;
static LL ans, phi[N];
static int p[N], tot; bool mark[N];

void Get_phi() {
    phi[1] = 1; tot = 0;
    memset(mark, false, sizeof(mark));
    for(int i=2; i<=n; i++) {
        if( !mark[i]) { p[++tot] = i; phi[i] = i-1; }
        for(int j=1; j<=tot && p[j]*i<=n; j++) {
            mark[p[j]*i] = true;
            if(i % p[j] == 0) { phi[p[j]*i]=phi[i]*p[j]; break; }
            else phi[p[j]*i] = phi[i]*(p[j]-1);
        }
    }
    for(int i=1; i<=n; i++) phi[i] += phi[i-1];
}

int main() {
    scanf("%d%d", &n, &m);
    if(n > m) swap(n, m);
    Get_phi();
    for(int i=1,j; i<=n; i=j+1) { //枚举的是d,即gcd的因数
        j = min(n/(n/i), m/(m/i));
    //(n/i)和(m/i)是那两个取值,n/(n/i),m/(m/i)是结束的最末位置,取min即取重叠一段
        ans += (phi[j]-phi[i-1])*(n/i)*(m/i);
    }
    printf("%lld\n", 2*ans-(LL)n*m);
    return 0;
}

24. bzoj4756

用主席树维护强者值即可。也可以从大到小插入强者值,用树状数组维护就好。
主席树:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#define N 100005
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, a[N], fa[N], dfn1[N], dfn2[N], Index;
vector<int> son[N];
pair<int,int> f[N];
map<int, int> root_id;
int root[N];

struct Node {
    int lc, rc;
    int sum;
} s[N*20];

void initlaize() {
    n = read();
    for(int i=1; i<=n; i++) {
        a[i] = read();
        f[i] = make_pair(a[i], i);
    }
    for(int i=2; i<=n; i++) {
        fa[i] = read();
        son[fa[i]].push_back(i);
    }
    sort(f+1, f+n+1);
    int Index = 0;
    for(int i=1; i<=n; i++) {
        if(f[i].first != f[i-1].first) Index++;
        a[f[i].second] = Index;
        f[i].first = Index;
    }
}

void DFS(int p) {
    dfn1[p] = ++Index;
    int sz = son[p].size();
    for(int i=0; i<sz; i++) DFS(son[p][i]);
    dfn2[p] = Index;
}

void Build(int p, int l, int r) {
    s[p].sum = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    s[p].lc = ++Index; s[p].rc = ++Index;
    Build(s[p].lc,l,mid); Build(s[p].rc,mid+1,r);
}

void Insert(int p, int p1, int l, int r, int x) {
    s[p] = s[p1]; s[p].sum++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) {
        s[p].lc = ++Index;
        Insert(s[p].lc, s[p1].lc, l, mid, x);
    }
    else {
        s[p].rc = ++Index;
        Insert(s[p].rc, s[p1].rc, mid+1, r, x);
    }
}

void Pre_work() {
    Index = 0;
    root[0] = ++Index; root_id[0] = 0;
    Build(root[0], 1, n);
    
    for(int i=1; i<=n; i++) {
        root[i] = ++Index;
        Insert(root[i], root[i-1], 1, n, dfn1[f[i].second]);
        root_id[f[i].first] = root[i];
        if(i == n) {
            for(int j=f[i].first+1; j<=n; j++)
                root_id[j] = root_id[j-1];
        }
    }
}

int Qsum(int p, int p1, int Le, int Re, int l, int r) {
    if(Le == l && Re == r) return s[p].sum-s[p1].sum;
    int mid = (Le + Re) >> 1;
    if(r <= mid) return Qsum(s[p].lc, s[p1].lc, Le, mid, l, r);
    else if(l > mid) return Qsum(s[p].rc, s[p1].rc, mid+1, Re, l, r);
    else return Qsum(s[p].lc, s[p1].lc, Le, mid, l, mid)+Qsum(s[p].rc, s[p1].rc, mid+1, Re, mid+1, r);
}

int main() {
    initlaize();
    Index = 0;
    DFS(1);
    Pre_work();
    for(int i=1; i<=n; i++)
        printf("%d\n", Qsum(root_id[n], root_id[a[i]], 1, n, dfn1[i], dfn2[i]));
    return 0;
}

树状数组:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 100005
using namespace std;
static int n, dfn1[N], dfn2[N], Index;
vector<int> son[N];
pair<int, int> f[N];
static int c[N], ans[N];

inline int lowbit(int x) { return x&(-x); }

void Add(int x, int k) {
    for(int i=x; i<=n; i+=lowbit(i))
        c[i] += k;
}

int Sum(int x) {
    int s = 0;
    for(int i=x; i>=1; i-=lowbit(i))
        s += c[i];
    return s;
}

void initlaize() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        int x; scanf("%d", &x);
        f[i] = make_pair(x, i);
    }
    for(int i=2; i<=n; i++) {
        int fa; scanf("%d", &fa);
        son[fa].push_back(i);
    }
}

void DFS(int p) {
    dfn1[p] = ++Index;
    int sz = son[p].size();
    for(int i=0; i<sz; i++)
        DFS(son[p][i]);
    dfn2[p] = Index;
}

int main() {
    initlaize();
    DFS(1);
    sort(f+1, f+n+1);
    for(int i=n; i>=1; i--) {
        int x = f[i].second;
        ans[x] = Sum(dfn2[x])-Sum(dfn1[x]);
        Add(dfn1[x], 1);
    }
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
    return 0;
}

25. bzoj2727

这个人讲的很好:thy
代码由他一手带大,注意建立权值线段树和权值主席树时一定要看清界限,调了一下午最终发现是界限设成了n而不是m的问题的感觉2333....

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 2000005
#define rep(a,l,r) for(int a=(l); a<=(r); a++)
using namespace std;
const int MOD = 1000000009;
typedef long long LL;
long long ans = 0;
static int n, m, tot;
static int a[N], l[N], r[N], c[N], d[N];

inline int pos(int x, int y) { return m*(x-1)+y; }

struct Fenwick_Tree {
    LL t[10005];
    
    inline int lowbit(int x) { return x&(-x); }
    
    void clear() { memset(t, 0, sizeof(t)); }
    
    void add(int x, LL k) {
        for(int i=x; i<=m; i+=lowbit(i))
            t[i] = (t[i] + k) % MOD;
    }
    
    LL  sum(int x) {
        LL v = 0;
        for(int i=x; i>=1; i-=lowbit(i)) {
            v += t[i];
            v %= MOD;
        }
        return v % MOD;
    }
    
} t1, t2, t3;

void initlaize() {
    scanf("%d%d%d", &n, &m, &tot);
    rep(i, 1, n*m) a[i] = 1;
    rep(i, 1, tot) {
        int u,v; scanf("%d%d", &u, &v);
        a[pos(u,v)] = 0;
    }
}

void Pre_work() {
    rep(i, 1, n) {
        l[pos(i,1)] = a[pos(i,1)];
        rep(j, 2, m) {
            if(a[pos(i,j)] == 1)
                l[pos(i,j)] = l[pos(i,j-1)] + 1;
            else l[pos(i,j)] = 0;
        }
    }
    rep(i, 1, n) {
        r[pos(i,m)] = a[pos(i,m)];
        for(int j=m-1; j>=1; j--) {
            if(a[pos(i,j)] == 1)
                r[pos(i,j)] = r[pos(i,j+1)] + 1;
            else r[pos(i,j)] = 0;
        }
    }
    rep(i, 1, n) rep(j, 1, m)
        if(a[pos(i,j)]) c[pos(i,j)] = min(l[pos(i,j)], r[pos(i,j)]) - 1;
    rep(j, 1, m) {
        d[pos(n,j)] = a[pos(n, j)];
        for(int i=n-1; i>=1; i--)
            if(a[pos(i,j)]) d[pos(i,j)] = d[pos(i+1,j)]+1;
            else d[pos(i,j)] = 0;
        rep(i, 1, n) if(a[pos(i,j)]) d[pos(i,j)]--;
    }
}

void Solve() {
    rep(j, 1, m) {  
        t1.clear(),t2.clear(),t3.clear();  
        int top = 0;
        rep(i, 1, n) {
            int t = pos(i,j);  
            if (a[t]==0) {top=i;t1.clear(),t2.clear(),t3.clear();continue;}
            ans = ans + t1.sum(c[t]) * d[t] % MOD;
            ans = ans + t2.sum(c[t]) * c[t] * d[t] % MOD;
            ans = ans + (t3.sum(m)-t3.sum(c[t])) * (c[t]-1)*c[t]/2 * d[t] % MOD;
            ans%=MOD, t=pos(i-1,j);
            if (i == 1) continue; 
            if (c[t]) {  
                t1.add(c[t], -1ll*c[t]*(c[t]+1)/2*(i-1-top-1));  
                t2.add(c[t], c[t]*(i-1-top-1));  
                t3.add(c[t], i-1-top-1);  
            }  
        }  
    }  
    printf("%lld\n",ans);  
}

int main() {
    initlaize();
    Pre_work();
    Solve();
    return 0;
}

26. bzoj2728

首先,与非操作可以通过一系列组合组合出&,|,^,!这四种运算。问题就简化了,每一个位置都可以是0或1,只是有些位置是一套的,因为这些位置上的数对于每个数都相同,于是最终结果这些位置上的数也都要一样,一套的东西可以暴力$O(nK^2)$得到。再然后就是数位dp了。至于在query中为什么要把x加一我没有搞懂(讲道理应该不要加的啊?)。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
static int n, k, be[65], cnt, mark[65];
static LL L, R, a[1005];

bool check(int x, int y) {
    for(int i=1; i<=n; i++)
        if(((a[i]>>x)^(a[i]>>y)) & 1)
            return false;
    return true;
}

int find(int x) {
    if(be[x] != x) be[x] = find(be[x]);
    return be[x];
}

LL query(LL x) {
    if(x < 0) return 0;
    if(x >= (1ll<<k)-1) return (1ll << cnt);
    x++;
    LL ans = 0; int rest = cnt;
    memset(mark, -1, sizeof(mark));
    for(int i=k-1; i>=0; i--) {
        if((x>>i) & 1) {
            if(mark[find(i)] == 1) continue;
            if(mark[find(i)] < 0) {
                rest--;
                mark[find(i)] = 1;
            }
            ans += (1ll << rest);
            if(mark[find(i)] == 0) break;
        }
        else {
            if(mark[find(i)] < 0) {
                rest--;
                mark[find(i)] = 0;
            }
            if(mark[find(i)] == 1) break;
        }
    }
    return ans;
}

int main() {
    scanf("%d%d%lld%lld", &n, &k, &L, &R);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    for(int i=0; i<=k; i++) be[i] = i;
    for(int i=0; i<k; i++) for(int j=0; j<i; j++)
        if(check(i,j)) {
            be[find(i)] = find(j);
            break;
        }
    for(int i=0; i<k; i++)
        if(find(i) == i) cnt++;
    printf("%lld\n", query(R)-query(L-1));
    return 0;
}

27. bzoj2729

一道简单的排列组合问题:女生不能相邻?还有两个烦人的老师?先将女生排好序,共有$m!$中方案,然后女生之间有$m-1$个间隙。我们先将老师和男生看做一个东西,叫做毛子,则共有$n+2$个毛子,先从中选取$m-1$个插入到间隙中,并强行绑定他和他之前的那个女生,现在共有$m+1$个合法位置(算上了开头与结尾),还剩$(n+2)-(m-1)=n-m+3$个毛子需要插入,则共有$\displaystyle {m+n-m+3\choose n-m+3}(n-m+3)!$种方案。现在我们知道了算n个毛子,m个女生的方案,那么两个烦人的老师就可以容斥掉了2333.....
一开始我没有强行绑定导致答案很大,然后发现不绑定的话就会算重。
啊高精度弃疗啦!人生苦短快用python。
Python:

def A(n):
    re=1
    for i in range(1,n+1):
        re*=i
    return re
def C(n,m):
    if n<m:
        return 0
    return A(n)//A(m)//A(n-m)
n,m=[int(i) for i in raw_input().split()]
print (C(n+2,m-1)*A(m-1)*A(n+3)/A(m)-2*C(n+1,m-1)*A(m-1)*A(n+2)/A(m))*A(m)

28. bzoj2730

发掘一下性质,因为如果一个点不是割点那么塌了就塌了,答案还是图中联通块的数量。现在我们只需要考虑割点坍塌的情况(因为只有这样可以使答案增加),对于每一个块(这里的块应该是点双),我们可以把割点想象成类似“安全出口”的东西,如果它包含了两个或两个以上的割点,那么它永远不会被堵死;如果只有一个,则当出口崩溃时它就要自救,即它要在除了割点以外的点建立救援点,这时方案有除了割点外的点数种;如果这个块是不包含任何一个割点,则需要在其中建立两救援点(一个塌了就去另一个),方案有${点数 \choose 2}$种。
Tarjan算法求割点思路清晰代码好写:对于dfs树,根节点如果有两个以上的子树则是割点,非根节点当$dfn[x]\le low[son\in x]$时是割点。
然后求点双连通分量就可以暴力dfs了,反正也是$O(n)$的。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <algorithm>
#define N 505
using namespace std;
int n, m, Index, kase = 0;
struct Edge { int nex, to; } e[N*4];
int head[N], cnt, num;
int dfn[N], low[N];
bool cut[N]; int son;
long long ans1, ans2;

void Link(int x, int y) {
    e[++cnt].nex = head[x];
    head[x] = cnt;
    e[cnt].to = y;
}

void initlaize() {
    pair<int,int> edge[N];
    int s[N*2], tot = 0;
    for(int i=1; i<=m; i++) {
        int x,y; scanf("%d%d", &x, &y);
        edge[i] = make_pair(x,y);
        s[++tot] = x; s[++tot] = y;
    }
    sort(s+1, s+tot+1);
    map<int,int> hashit;
    n = 0;
    for(int i=1; i<=tot; i++)
        if(s[i] != s[i-1])
            hashit[s[i]] = ++n;
    for(int i=1; i<=m; i++) {
        edge[i].first = hashit[edge[i].first];
        edge[i].second = hashit[edge[i].second];
    }
    memset(head, 0, sizeof(head)); cnt=0;
    for(int i=1; i<=m; i++) {
        Link(edge[i].first, edge[i].second);
        Link(edge[i].second, edge[i].first);
    }
}

void Tarjan_dfs(int p, int fa) {
    dfn[p] = low[p] = ++Index;
    for(int j=head[p]; j; j=e[j].nex) {
        int v = e[j].to;
        if(v == fa) continue;
        if(dfn[v] < 0) {
            Tarjan_dfs(v, p);
            low[p] = min(low[p], low[v]);
        }
        else {
            low[p] = min(low[p], dfn[v]);
            continue;
        }
        if(low[v] >= dfn[p]) {
            if(fa < 0) son++;
            else cut[p] = true;
        }
    }
}

void Tarjan() {
    memset(dfn, -1, sizeof(dfn));
    Index = 0;
    memset(cut, false, sizeof(cut));
    for(int i=1; i<=n; i++)
        if(dfn[i] < 0) {
            Tarjan_dfs(i, -1);
            if(son >= 2) cut[i] = true;
            son = 0;
        }
}

void dfs(int p) {
    dfn[p] = Index; if(cut[p]) return;
    cnt++;
    for(int j=head[p]; j; j=e[j].nex) {
        int v = e[j].to;
        if(cut[v] && dfn[v]!=Index) num++,dfn[v]=Index;
        if(dfn[v] == 0) dfs(v);
    }
}

void solve() {
    memset(dfn, 0, sizeof(dfn));
    Index = 0; ans1 = 0; ans2 = 1;
    for(int i=1; i<=n; i++)
        if( !dfn[i] && !cut[i]) {
            Index++; cnt = num = 0;
            dfs(i);
            if(num == 0) {
                ans1 += 2;
                ans2 *= (cnt*(cnt-1)/2);
            }
            if(num == 1) {
                ans1 += 1;
                ans2 *= cnt;
            }
        }
    printf("Case %d: %lld %lld\n", kase, ans1, ans2);
}

int main() {
    while(scanf("%d", &m)!=EOF && m) {
        kase++;
        initlaize();
        Tarjan();
        solve();
    }
    return 0;
}

29. bzoj2733

经典的平衡树启发式合并,但是用线段树合并貌似更快更好。线段树合并相当于维护一堆数组,这些数组的并是n,这样子合并什么的就都是$O(nlogn)$的。
线段树合并:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, m, Index=0, bin[N];
int root[N], pos[N];
char opt[3];
struct Node {
    int Lc, Rc;
    int Sum;
} s[2000005];

int find(int x) {
    if(bin[x] != x) bin[x] = find(bin[x]);
    return bin[x];
}

void Insert(int &p, int l, int r, int x) {
    if(p == 0) p = ++Index;
    if(l == r) { s[p].Sum = 1; return; }
    int mid = (l + r) >> 1;
    if(x <= mid) Insert(s[p].Lc, l, mid, x);
    else Insert(s[p].Rc, mid+1, r, x);
    s[p].Sum = s[s[p].Lc].Sum + s[s[p].Rc].Sum;
}

int Merge(int p1, int p2) {
    if(p1 == 0) return p2;
    if(p2 == 0) return p1;
    s[p1].Lc = Merge(s[p1].Lc, s[p2].Lc);
    s[p1].Rc = Merge(s[p1].Rc, s[p2].Rc);
    s[p1].Sum = s[s[p1].Lc].Sum + s[s[p1].Rc].Sum;
    return p1;
}

void Link(int x, int y) {
    if(find(x) == find(y)) return;
    root[find(x)] = Merge(root[find(x)], root[find(y)]);
    bin[find(y)] = find(x);
}

int Query(int p, int l, int r, int k) {
    if(k > s[p].Sum) return -1;
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(k <= s[s[p].Lc].Sum) return Query(s[p].Lc, l, mid, k);
    else return Query(s[p].Rc, mid+1, r, k-s[s[p].Lc].Sum);
}

void initlaize() {
    n=read(); m=read();
    for(int i=1; i<=n; i++) {
        int a = read(); pos[a] = i;
        Insert(root[i], 1, n, a);
        bin[i] = i;
    }
    for(int i=1; i<=m; i++) {
        int x=read(), y=read();
        Link(x, y);
    }
}

void solve() {
    m = read();
    while(m--) {
        scanf("%s", opt);
        int x=read(), y=read();
        if(opt[0] == 'B') Link(x, y);
        else {
            int t = Query(root[find(x)], 1, n, y);
            printf("%d\n", t>0? pos[t] : t);
        }
    }
}

int main() {
    initlaize();
    solve();
    return 0;
}

30. bzoj2734

思路太神啦,构建一个奇怪的左上三角矩阵,然后选了某个数则其下方和右方的数不能选,由于矩阵至多长为$O(log_3^n)$,宽为$O(log_2^n)$。所以就可以状压dp暴力搞了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
#define MOD 1000000001
#define rep(a,l,r) for(int a=l; a<=r; a++)
using namespace std;
typedef long long LL;
int n; bool mark[N];
int a[20][20], lim[20], dp[20][N];
LL ans = 1;

LL solve(int x) {
    a[1][1] = x; memset(lim, 0, sizeof(lim));
    rep(i, 2, 18)
        a[i][1] = (a[i-1][1]*2<=n ? a[i-1][1]*2 : n+1);
    rep(i, 1, 18) rep(j, 2, 11)
        a[i][j] = (a[i][j-1]*3<=n ? a[i][j-1]*3 : n+1);
    rep(i, 1, 18) rep(j, 1, 11) {
        if(a[i][j] <= n) lim[i] += (1 << (j-1));
        mark[a[i][j]] = true;
    }
    rep(i, 0, 18) rep(j, 0, lim[i]) dp[i][j] = 0;
    //这里一定要循环赋初值,用memset会TLE
    dp[0][0] = 1;
    rep(i, 0, 17) rep(j, 0, lim[i]) if(dp[i][j]) {
        rep(k, 0, lim[i+1])
            if(( !(j&k)) && ( !(k&(k>>1))))
                dp[i+1][k] = (dp[i+1][k] + dp[i][j]) % MOD;
    }
    return dp[18][0];
}

int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        if( !mark[i]) ans = (ans * solve(i)) % MOD;
    printf("%lld\n", ans);
    return 0;
}