Some Interesting Problems（持续更新中）

　　这种题目详解，是“一日一测”与“一句话题解”栏目所无法覆盖的，可能是考试用题，也可能是OJ题目。常常非常经典，可以见微知著。故选其精华，小列如下。

T1：fleet 给定一个序列，询问[L,R]间有多少种不同的权值。（普通数据结构范围）

e.g.：序列1,1,2,3,2的[1,5]有3种不同权值，[1,3]有2种不同权值。

ANSWER：可以考虑使用主席树求解。查询[L,R]时返回root[R]的[L,R]值之和。root[i]与root[i-1]的不同在于：prev[aa[i]]这个位置（即上一次出现aa[i]的位置）-1，在i这个位置+1。先预处理完毕，再应付查询。

T2：给定一个序列，询问[L,R]间有多少种权值k恰出现k次。（普通数据结构范围）

e.g.：序列1,1,2,3,2的[1,1]有1种权值，[1,2]有0种权值，[2,5]有2种权值。

ANSWER：可以考虑使用主席树求解。但是，我们也可以考虑使用离线。因为答案本质上统计的是一种情形，而我们可以考虑该情形对答案的贡献。如果把询问[L,R]转化为二维矩阵中某点[L,R]的权值，那么每一种情形的贡献也可以看做是矩形的修改。因为这样很令人不爽，可以进一步地转换，使用差分的思想，将矩形拆成4个角，问题于是转化为单点修改与矩阵前缀和的查询。这个东西很像BZOJ的一道题：MONICA。那是一道CDQ分治套树状数组的典型题目，因为有时间的先后。但是，这道题目完全可以先修改再查询，于是可以sort以后直接使用树状数组求解。然而，如果你真的能够看懂上面那段东西，你可能就会惊奇的发现，这种思路其实和主席树一模一样。于是，我们可以反观我们的学习过程。当我们在学主席树的时候，真的有想过离线的做法吗?

 1 #define PN "count"
 2 #include 
 3 #include 
 4 #include 
 5 template<class T>inline void readint(T &res) {
 6     static char ch;T flag=1;
 7     while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;
 8     res=ch-48;
 9     while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;
10     res*=flag;
11 }
12 const int N = 1000000 + 100;
13 const int Q = 1000000 + 100;
14 struct DATUM {
15     int x, y, delta;
16     bool operator<(const DATUM &rhs) const {
17         if(x!=rhs.x) return x<rhs.x;
18         if(y!=rhs.y) return y<rhs.y;
19         if(delta!=rhs.delta) return delta<rhs.delta;
20     }
21 } data[N*4+Q];
22 int tot, ans[Q];
23 inline void addD(int x,int y,int delta) {data[++tot]=(DATUM){x,y,delta};}
24 
25 int n, a[N];
26 void add(int pos,int val) {for(int x=pos;x<=n;x+=x&-x)a[x]+=val;}
27 int query(int pos) {int val=0;for(int x=pos;x;x-=x&-x)val+=a[x];return val;}
28 
29 #include 
30 std::vector<int> same[N];
31 int main() {
32     int q;readint(n);readint(q);
33     for( int i = 1; i <= n; i++ ) same[i].push_back(0);
34     for( int i = 1, x, siz; i <= n; i++ ) {
35         readint(x);same[x].push_back(i);
36         siz=same[x].size();
37         if(siz>x) {
38             addD(same[x][siz-x-1]+1,i,+1);
39             addD(same[x][siz-x]+1,i,-1);
40             if(siz>x+1) addD(same[x][siz-x-2]+1,i,-1); 
41             if(siz>x+1) addD(same[x][siz-x-1]+1,i,+1);
42         }
43     }
44     for( int i = 1, l, r; i <= q; i++ ) readint(l),readint(r),addD(l,r,i+1);
45     std::sort(data+1,data+tot+1);
46     for( int i = 1; i <= tot; i++ ) {
47         if(data[i].delta<=1) add(data[i].y,data[i].delta);
48         else if(data[i].y>=1&&data[i].y<=n) ans[data[i].delta-1]=query(data[i].y);
49     }
50     for( int i = 1; i <= q; i++ ) printf("%d\n",ans[i]);
51     return 0;
52 }

T3：给定n个长度为m的字符串，问有多少对字符串的相同字符数为0,为1,为2,为3,……为m。输出m+1个数。（总字符数≤1e5）

e.g.：4个长度为3的字符串xyz，xyz，zzx，xzz中有2对字符串的相同字符数为0，有1对字符串的相同字符数为1，有2对字符串的相同字符数为2，有1对字符串的相同字符数为3。

ANSWER：首先考虑暴力，是稳定的n^2*m，需要满足n约小于1000。然后，请忽略数据有意形成的数据断带。之后，对于m很小的情况，可以考虑暴力枚举出所有的字符串（就是状态压缩），因为相同字符数为m的情况可以直接预知，而又可以枚举每一位局部不同然后加以统计。于是考虑DP[2][S][j]，表示在修改第i位时，与串S的相同字符数为j的串的数目。最后简单修改后，就可以输出答案。代码如下：

 1 #define PN "words"
 2 #include 
 3 #include 
 4 #include 
 5 
 6 const int N = 100000 + 1000;
 7 int n, m;
 8 long long bucket[N];
 9 
10 char s[N];
11 #define HOLE(x,y) s[(x-1)*m+y]
12 void bruce() {
13     for( int i = 1; i <= n; i++ ) scanf("%s",s+(i-1)*m);
14     for( int i = 1, j, k, tot; i <= n; i++ ) for( j = i + 1; j <= n; j++ ) {
15         tot = 0;
16         for( k = 0; k < m; k++ ) if(HOLE(i,k)==HOLE(j,k)) tot++;
17         bucket[tot]++;
18     }
19 }
20 
21 const int APP = 531441;
22 const int M = 13;
23 int appear[APP], cur, three[M];
24 long long f[2][APP][M];
25 char ch;
26 void solve() {
27     for( int i = 1, now, j; i <= n; i++ ) {
28         now = 0;
29         for( j = 1; j <= m; j++, now*=3 ) {
30             while((ch=getchar())==' '||ch=='\n');ch-='x';
31             now+=ch;
32         }
33         appear[now/3]++;
34     }
35     three[0]=1;
36     for( int i = 1; i <= m; i++ ) three[i]=three[i-1]*3;
37     for( int i = 0; i < three[m]; i++ ) f[cur][i][m]=appear[i];
38     for( int i = 0, j, k; i < m; i++ ) {
39         cur^=1;memcpy(f[cur],f[cur^1],sizeof(f[cur^1]));
40         for( j = 0; j < three[m]; j++ ) {
41             int s1 = (j/three[i]%3)*three[i], s2 = j - s1;
42             for( k = 0; k < three[i+1]; k += three[i]) if(k!=s1) for( int p = m-i; p <= m; p++ ) f[cur][s2+k][p-1]+=f[cur^1][j][p];
43         }
44     }
45     for( int p = 0, i; p <= m; p++ ) for( i = 0; i < three[m]; i++ ) bucket[p]+=appear[i]*f[cur][i][p];
46     bucket[m]-=n;
47     for( int i = 0; i <= m; i++ ) bucket[i]/=2;
48 }
49 
50 int main() {
51     freopen(PN".in","r",stdin);
52     freopen(PN".out","w",stdout);
53     scanf("%d%d",&n,&m);
54     if(m<=12) solve();
55     else bruce();
56     for( int i = 0; i <= m; i++ ) printf("%I64d\n",bucket[i]);
57     return 0;
58 }

T4:BZOJ1001狼抓兔子。求无向方格图的最小割。

ANSWER：这样的最小割?对偶图的最短路。dinic以前说过，但是对偶图确实可以快上很多倍（实验验证dinic约2500ms，对偶图约400ms）。因为这样的图的最小割一定是能够分隔源点与汇点的一段连续折线。于是可以把边之间的小“胞体”作为节点建边跑最短路。如图（摘自优秀博客http://www.cnblogs.com/jinkun113/p/4682827.html，同志们可以看一看）：

大概就是这样了。最后说一下，建议使用读入优化，不然结果会很让人伤心。

还有，对了，做完了可以看一看BZOJ2007[NOI2010]海拔，也是一道类似的题目，不过是有向边。

T5:随rand 给定n个正整数和一个模数mod。还有一个数x其初始值为1，我们将对x进行m次操作。每一次操作是从n个数中随机选出一个数p，然后x=x*p%mod。求x的期望值a/b，为避免输出浮点数请mod1e9+7后输出。(n≤1e5,m≤1e9,mod≤1e3)

e.g.:最开始有2个正整数1和2，mod=3，无论进行多少次操作，x总期望为3/2。

ANSWER：达哥出的题。这道题的暴力转移很好想。因为n和m看上去都很邪恶，而mod却很小，x再猖狂也是在0~mod-1这个范围内的。而最后答案的计算不过是a/b，a就是进行m次操作后每个模数的情况数乘以每个模数求和，而b就是进行m次操作后每个模数的情况数求和。中间“情况数”可以随便mod1e9+7。于是可以建立转移方程了。

　　方程：dp[i][j]=∑dp[i-1][k]*p[k][j]

　　在这里，dp[i][j]指进行i次操作后模数j的情况数mod1e9+7。p[k][j]指每一次操作，模数k能有几种转移到模数j的方法。我们可以发现，p[k][j]只与n个数本身有关，是妥妥的常量（特别是n没有用了）。加上滚动，这就是空间复杂度为O(mod^2)而时间复杂度为O(m*mod^2)的DP方法。

　　但是，m确实很大。考虑到DP方程确实太简单了，我们可以考虑使用矩阵快速幂。于是，空间复杂度仍为O(mod^2)，而时间复杂度却成了O(log m*mod^3)。本题的前80%都有mod≤300，似乎80分稳了。在考场上我是这样认为的，但是我最后在老年机上只有20，在极速的floj上也只有50。只要仔细想一想，m最大为1e9，那log m就是30，mod^3=27000000，是绝对过不了的。不过，想到了这里，我们应该放弃吗？绝不！

　　我们知道O(log m*mod^3)是很慢的，但是O(log m*mod^2)却是可行的。考虑矩阵快速幂的本质，是对顺序的漠视。我们一节base算出来的，在本质上其实是进行若干次操作后1能够变成哪些模数。那么我们其实可以更加直接，因为可以直接乘起来。这样，时间复杂度打了标，空间复杂度亦变成了O(mod)。代码如下。

 1 #define PN "rand"
 2 #include 
 3 #include 
 4 #include 
 5 
 6 //char *hd, *tl, buf[(1<<15)+2];
 7 //#define getc() ((hd==tl&&(tl=(hd=buf)+fread(buf,1,1<<15,stdin)),hd==tl)?0:*hd++)
 8 template<class T>inline void readin(T &res) {
 9     static char ch;T flag=1;
10     while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;
11     res=ch-48;
12     while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;
13     res*=flag;
14 }
15 
16 const int N = 100000 + 1000;
17 const int SIZ = 1000 + 50;
18 const int MOD = 1e9+7;
19 
20 #define set(x) (x>MOD?x-MOD:x)
21 int mod, base[SIZ], rus[SIZ], tmp[SIZ];
22 
23 void calc() {
24     int a = 0, b = 0, ans;
25     for( int pos = 0; pos < mod; pos++ ) a=set(a+(long long)rus[pos]*pos%MOD);
26     for( int pos = 0; pos < mod; pos++ ) b=set(b+rus[pos]);
27     ans = a;
28     for( int bound = MOD - 2; bound; bound>>=1, b=(long long)b*b%MOD ) if(bound&1) ans=(long long)ans*b%MOD;
29     printf("%d\n",ans);
30 }
31 
32 void matrix_(int type) {
33     for( int i = 0; i < mod; i++ ) tmp[i]=0;
34     if(!type) {
35         for( int i = 0, j; i < mod; i++ ) for( j = 0; j < mod; j++ ) tmp[i*j%mod]=set(tmp[i*j%mod]+(long long)base[i]*base[j]%MOD);
36         for( int i = 0; i < mod; i++ ) base[i]=tmp[i];
37     } else {
38         for( int i = 0, j; i < mod; i++ ) for( j = 0; j < mod; j++ ) tmp[i*j%mod]=set(tmp[i*j%mod]+(long long)base[i]*rus[j]%MOD);
39         for( int i = 0; i < mod; i++ ) rus[i]=tmp[i];
40     }
41 }
42 
43 
44 int main() {
45     freopen(PN".in","r",stdin);
46     freopen(PN".out","w",stdout);
47     int n, m;readin(n);readin(m);readin(mod);
48 //    memset(rus,0,sizeof(rus));memset(base,0,sizeof(base));
49     for( int i = 1, x, pos; i <= n; i++ ) {
50         readin(x);
51         for( pos = 0; pos < mod; pos++ ) base[x]++;
52     }
53     rus[1]=1;
54     for( int bound = m; bound; bound>>=1, matrix_(0) ) if(bound&1) matrix_(1);
55     calc();
56     return 0;
57 }

T6:BZOJ 2064 状压DP 给定一个初始集合和目标集合，有两种操作：1.合并集合中的两个元素，新元素为两个元素之和 2.分裂集合中的一个元素，得到的两个新元素之和等于原先的元素。要求用最小步数使初始集合变为目标集合，求最小步数。

ANSWER：当时特别迷，不知道怎么办。后来看了一下题解，实质上是最优子结构的应用。最优子结构操作起来很像套娃。因为最坏情况就是把所有的元素合并成一个，然后再拆开，步数为n+m-2。而我们可以发现，如果一个集合要变成另一个集合，而两个集合都分别存在一个子集之和相等，那么就可以减少2次操作，减少的是一次合并与一次拆分。然后，我们就可以枚举原始集合与目标集合，统计其中可以减少的次数。对于两个给定的集合，我们可以枚举其中的每一个元素，这样就可以间接查询所有子集了。如果两个集合之和相等，那么就可以减少一次操作。最后答案为n+m-2*f[(1<

 1 #include 
 2 #include 
 3 #include 
 4 #define smax(x,y) x=std::max(x,y)
 5 const int N = 10;
 6 int n, m, a[N+1], b[N+1], suma[1<1<1<1<<N];
 7 int main() {
 8     scanf("%d",&n);
 9     for( int i = 1; i <= n; i++ ) scanf("%d",&a[i]);
10     scanf("%d",&m);
11     for( int i = 1; i <= m; i++ ) scanf("%d",&b[i]);
12     for( int i = 1, pos = 1; pos <= n; i<<=1, pos++ ) suma[i]=a[pos];
13     for( int j = 1, pos = 1; pos <= m; j<<=1, pos++ ) sumb[j]=b[pos];
14     for( int i = 1, lima = 1<k];
15     for( int j = 1, limb = 1<k];
16     for( int i = 1, j, k, lima = 1<1<for( j = 1; j < limb; j++ ) {
17         for( k = 1; k <= i; k<<=1 ) if(i&k) smax(f[i][j],f[i-k][j]);
18         for( k = 1; k <= j; k<<=1 ) if(j&k) smax(f[i][j],f[i][j-k]);
19         if(suma[i]==sumb[j]) f[i][j]++;
20     }
21     printf("%d\n",n+m-2*f[(1<1][(1<1]);
22     return 0;
23 }

但是，考虑到原始集合与目标集合的实质差异并不大，只是在减少操作时在等号两边，于是可以考虑移项，原始集合是正的，而目标集合是负的，就可以统一考虑了。

 1 #include 
 2 #include 
 3 #include 
 4 #define smax(x,y) x=std::max(x,y)
 5 const int N = 20;
 6 int n, m, sum[1<1<<N];
 7 int main() {
 8     scanf("%d",&n);
 9     for( int i = 1, sta = 1; i <= n; i++, sta<<=1 ) scanf("%d",&sum[sta]);
10     scanf("%d",&m);
11     for( int i = 1, x, sta = 1<1 ) {
12         scanf("%d",&x);
13         sum[sta]=-x;
14     }
15     n+=m;
16     for( int i = 1, lim = 1<i ) {
17         sum[i]=sum[k]+sum[i-k];
18         for( p = 1; p <= i; p<<=1 ) if(i&p) smax(f[i],f[i-p]);
19         if(sum[i]==0) f[i]++;
20     }
21     printf("%d\n",n-2*f[(1<1]);
22     return 0;
23 }

T7:IRREGULAR 给你一棵树，每个点有点权，输出1~n每个点的困难度。一个点P的困难度是指，所有LCA为P的点对的路径异或和的最大值。点对可以是相同的2个点。按DFS序维护可持久化TRIE，为差量全局桶，询问时启发式合并。

E.G:对于一棵5个结点的树，1为根有儿子2、3和5，2和5是叶子结点，3有儿子4。5个点的权值分别为1775、6503、8147、2354和8484，可以算出这5个点的困难度分别为16044、6503、8147、2354和8484。

ANSWER：对于最大异或和这种经典问题，一个很直观的想法就是使用01TRIE。但是，本人当时一直是想使用DFS进行统计，将下面的所有直接合并到上面，显然不可行。于是考场上选择暴力枚举点对写ST表，无奈其他地方时间耗费太多，有东西没考虑到，这道题连暴力分也没有得到。

　　事后发现了一个性质（其实我以前曾经知道），就是u点到v点的路径异或和=dis[u]^dis[v]^dis[LCA]^aa[LCA]，这里dis[u]指从u向上到根的点权异或和，aa[LCA]当然就是LCA的点权啦。

　　然后根据这个性质可以发现，其实不用从下往上，直接用可持久化TRIE树和DFS序就好了。于是可以先搞出DFS序，再构造出可持久化TRIE，再顺着统计每个结点的答案，因为一棵子树的DFS序是连续的，就可以很方便地统计询问了。

　　这样似乎是可以的，但是复杂度其实没有办法保证，于是考虑启发式合并。使用重链剖分方便地保证重子树优先，然后就小幷大了。

　　上面似乎说地很抽象，但最后实施起来其实是很具体的。但是中间有一点小细节还是让我调了很久。一处是query查询[L,R]时减的是L-1，还有一处是insert是siz的处理。

　　代码如下：

 1 #define PN "irregular"
 2 #include 
 3 #include 
 4 #include 
 5 
 6 template<class T>inline void readin(T &res) {
 7     static char ch;T flag = 1;
 8     while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;
 9     res=ch-48;
10     while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;
11     res*=flag;
12 }
13 
14 const int N = 100000 + 1000;
15 const int ROOT = 1;
16 struct Edge {int v,upre;}g[N<<1];
17 int head[N], ne = 0;
18 inline void adde(int u,int v) {g[++ne]=(Edge){v,head[u]};head[u]=ne;}
19 
20 int n, aa[N];
21 
22 int fa[N], dis[N], s[N], son[N];
23 void DFS(int u) {
24     dis[u]=dis[fa[u]]^aa[u];
25     s[u]=1;
26     for( int i = head[u], v; i; i = g[i].upre ) {
27         if((v=g[i].v)==fa[u]) continue;
28         fa[v]=u;
29         DFS(v);
30         s[u]+=s[v];
31         if(s[son[u]]v;
32     }
33 }
34 
35 int in[N], out[N], seq[N], idy;
36 void DFS2(int u) {
37     in[u]=++idy;seq[idy]=u;
38     if(son[u]) DFS2(son[u]);
39     for( int i = head[u], v; i; i = g[i].upre ) {
40         if((v=g[i].v)==fa[u]||v==son[u]) continue;
41         DFS2(v);
42     }
43     out[u]=idy;
44 }
45 
46 const int BITS = 32;
47 const int NODES = N * 60;
48 int digit[BITS], root[N], siz[NODES], ch[NODES][2], tail;
49 int query(int L,int R,int x) {
50     L = root[L], R = root[R];
51     for( int floor = 0; floor < BITS; floor++,x>>=1 ) digit[floor]=x&1;
52     int ans = 0;
53     for( int floor = BITS - 1; floor >= 0; floor-- ) {
54         ans<<=1;
55         if(siz[ch[R][digit[floor]^1]]-siz[ch[L][digit[floor]^1]]) {
56             ans++;
57             L = ch[L][digit[floor]^1], R = ch[R][digit[floor]^1];
58         } else L = ch[L][digit[floor]], R = ch[R][digit[floor]];
59     }
60     return ans;
61 }
62 
63 int main() {
64     freopen(PN".in","r",stdin);
65     freopen(PN".out","w",stdout);
66     readin(n);
67     for( int i = 1; i <= n; i++ ) readin(aa[i]);
68     for( int i = +1, u, v; i < n; i++ ) {
69         readin(u);readin(v);
70         adde(u,v);adde(v,u);
71     }
72     fa[ROOT]=ROOT;
73     DFS(ROOT);
74     DFS2(ROOT);
75     for( int i = 1; i <= n; i++ ) {
76         for( int floor = 0, x = dis[seq[i]]; floor < BITS; floor++,x>>=1 ) digit[floor]=x&1;
77         int ori = root[i-1], now = root[i] = ++tail;
78         for( int floor = BITS - 1; floor >= 0; floor-- ) {
79             siz[now]=siz[ori]+1;
80             ch[now][digit[floor]^1]=ch[ori][digit[floor]^1];
81             ori = ch[ori][digit[floor]];
82             now = ch[now][digit[floor]] = ++tail;
83         }
84         siz[now]=siz[ori]+1;//注意此处 
85     }
86     for( int u = 1; u <= n; u++ ) {
87         int ans = aa[u];
88         if(son[u]) ans = std::max(ans,query(in[son[u]]-1,out[son[u]],dis[u]^aa[u]));//注意左端减一 
89         for( int v = seq[out[son[u]]+1], x; fa[v]==u; v = seq[out[v]+1] ) {
90             for( x = in[v]; x <= out[v]; x++ )
91                 ans = std::max(ans,query(in[u]-1,in[v]-1,dis[seq[x]]^aa[u]));
92         }
93         printf("%d\n",ans);
94     }
95     return 0;
96 }

IRREGULAR

T8：给一个n行m列的矩阵，你需要填入一些数。每一行有两个限制的li与ri(1≤li＜ri≤m)，要求每一行在1~li与ri~m之间都恰填入一个数，而每一行共填入2个数。每列最多填入1个数。问最后的方案数，%998244353。

E.G.:n=2,m=6,l1=2,r1=4,l2=5,r2=6。方案数共12。

ANSWER：DP，基于未来状态，造坑与填坑。因为每一列最多填入一个数，所以很容易知道行其实没有用。实质上是在填一些区间。于是就可以每一列不断右推，左端点必须不断填入，而右端点要么填入，要么留在未来。如此想来就很简单了。

　　bukl[i]表示L为i的情况数，bukr[i]表示R为i的情况数。dp[i][j]表示枚举到填入第i列，而已经枚举到的右区间有j个还将要被填的方案数。

　　dp[i][j+bukr[i]]<-dp[i-1][j]*P(i-j+S,bukl[i]) 之前已经填入了一些数，于是还剩i-j+S个确定的位置，然后把bukl[i]个数填入，bukr[i]个右端点的都放到未来

　　dp[i][j+bukr[i]-1]<-dp[i-1][j]*P(i-j+S-1,bukl[i])*(j+bukr[i]) 之前已经填入了一些数，又在此列填了一个右区间的数，于是还剩i-j+S-1个确定的位置，然后把bukl[i]个数填入

　　实在是很优啊！LKQ说这种DP太偏，其实不然。之前已经有不少题都是这样了，像BZOJ4321，像CF的超级二叉树……

T9：从前有一个旅馆，老板特别喜欢数字4和7。所以，他只让一个房间里住4或7个人。现在告诉你每个房间住的人数（7人以内），将一个原在i号房间的人移动到j房间的代价是abs(i-j)，要想能满足老板的要求，花费的代价是多少？

ANSWER：发现人都是一样的。所以说，一个人从i号房间移动到j号房间其实可以理解为：（不妨设i

T10：【NOIP普及组车站分级】一条单向的铁路线上，依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）现有 m 趟车次的运行情况（全部满足要求），试推算这 n 个火车站至少分为几个不同的级别。请注意，n≤100000，m≤50000，∑si≤100000

ANSWER：原题的 n, m ≤ 1000，都要用上虚点（高级点连虚点，虚点连低级点）。像这道题，单单这种技巧便显得十分无力。考虑原题中虚点的作用，是把重复的东西捆在一起。如果你做过BZOJ萌萌哒，那你会觉得一切好像曾经都遇见过。当时做这道题目，我用了极其神奇的分块，就是这种想法。当然，那道题目用的实质上是倍增（因为倍增空间大一点但跑得飞快），这道题目也一样。倍增就是len+len->2len的方法，这么去做。但是我当时害怕炸空间，就再次深入思考，发现线段树也能够覆盖区间，而且结点数更少。直到最后才发现，使用线段树后结点会少很多但转移边少不到哪儿去，空间小时间相应更大。可是，提交之后两个方法最初都WA了，迷乱之中终于发现虚点也可以有边权。

代码如下（个人认为很清真）：

 1 #define PN "c"
 2 #include 
 3 #include 
 4 #include 
 5 
 6 const int SIZ = 600000 + 1000;
 7 const int M = 6000000 + 100000;
 8 struct EDGE {int v,upre;}g[M];
 9 int head[SIZ], ne = 0;
10 int in[SIZ], level[SIZ], pos[SIZ], idc;
11 bool mark[SIZ];
12 inline void adde(int u,int v) {in[v]++;g[++ne]=(EDGE){v,head[u]};head[u]=ne;}
13 
14 #include 
15 std::queue<int> q;
16 int n;
17 void solve() {
18     int u, i, v, ans = 1;
19     q.push(0);//破缺者
20     for( i = 1; i <= n; i++ ) if(!in[pos[i]]) q.push(pos[i]), level[pos[i]]=1;
21     while(!q.empty()) {
22         u = q.front();q.pop();
23         for( i = head[u], v; i; i = g[i].upre ) {
24             v = g[i].v;
25             in[v]--;if(!in[v]) q.push(v);
26             level[v]=std::max(level[v],level[u]+mark[v]);
27             ans=std::max(ans,level[v]);
28         }
29     }
30     printf("%d\n",ans);
31 }
32 
33 struct NODE {
34     int id;
35     NODE *ls, *rs;
36 } pool[SIZ], *tail=pool, *root;
37 NODE *build(int lf,int rg) {
38     NODE *nd=tail++;nd->id=++idc;
39     if(lf==rg) mark[nd->id]=1, pos[lf]=nd->id;
40     else {
41         int mid=(lf+rg)>>1;
42         nd->ls=build(lf,mid);
43         adde(nd->ls->id,nd->id);
44         nd->rs=build(mid+1,rg);
45         adde(nd->rs->id,nd->id);
46     }
47     return nd;
48 }
49 void addedge(NODE *nd,int lf,int rg,int L,int R,int linkpoint) {
50     if(L<=lf&&rg<=R) {
51         adde(nd->id,linkpoint);    
52         return ;
53     }
54     int mid=(lf+rg)>>1;
55     if(L<=mid) addedge(nd->ls,lf,mid,L,R,linkpoint);
56     if(midrs,mid+1,rg,L,R,linkpoint);
57 }
58 
59 int main() {
60     freopen(PN".in","r",stdin);
61     freopen(PN".out","w",stdout);
62     int m;
63     scanf("%d%d",&n,&m);
64     root=build(1,n);
65     for( int i = 1, j, s, last, now, linkpoint; i <= m; i++ ) {
66         scanf("%d%d",&s,&last);linkpoint=++idc;
67         adde(0,linkpoint);//破缺者 
68         adde(linkpoint,pos[last]);
69         for( j = 1; j < s; j++ ) {
70             scanf("%d",&now);adde(linkpoint,pos[now]);
71             addedge(root,1,n,last+1,now-1,linkpoint);
72             last = now;
73         }
74     }
75     solve();
76     return 0;
77 }

线段树

 1 #define PN "c"
 2 #include 
 3 #include 
 4 #include 
 5 
 6 const int S = 17;
 7 const int SIZ = 1700000 + 10000;
 8 const int M = 6000000 + 100000;
 9 struct EDGE {int v,upre;}g[M];
10 int head[SIZ], ne = 0, in[SIZ], level[SIZ];
11 inline void adde(int u,int v) {in[v]++;g[++ne]=(EDGE){v,head[u]};head[u]=ne;}
12 
13 int n, base[S];
14 inline int HOLE(int dep,int pos) {return base[dep]+pos;}
15 
16 #include  
17 std::queue<int> q;
18 void solve() {
19     int u, i, v, ans = 1;
20     q.push(0);//破缺者
21     for( i = 1; i <= n; i++ ) if(!in[i]) q.push(i), level[i]=1;
22     while(!q.empty()) {
23         u = q.front();q.pop();
24         for( i = head[u], v; i; i = g[i].upre ) {
25             v = g[i].v;
26             in[v]--;if(!in[v]) q.push(v);
27             level[v]=std::max(level[v],level[u]+(v<=n));
28             ans=std::max(ans,level[v]);
29         }
30     }
31     printf("%d\n",ans);
32 }
33 
34 int main() {
35     freopen(PN".in","r",stdin);
36     freopen(PN".out","w",stdout);
37     int m, tot;
38     scanf("%d%d",&n,&m);tot=n;
39     for( int len = 2, dep = 1, pos; len < n; len <<= 1, dep++ ) {
40         base[dep]=tot;
41         for( pos = 1; pos <= n - len + 1; pos++ )
42             adde(HOLE(dep-1,pos),HOLE(dep,pos)),adde(HOLE(dep-1,pos+(len>>1)),HOLE(dep,pos));
43         tot += n - len + 1;
44     }
45     for( int i = 1, j, s, last, now, linkpoint, pos, dep, len, t; i <= m; i++ ) {
46         scanf("%d%d",&s,&last);linkpoint=++tot;
47         adde(0,linkpoint);//破缺者 
48         adde(linkpoint,last);
49         for( j = 1; j < s; j++ ) {
50             scanf("%d",&now);adde(linkpoint,now);
51             for( pos = last+1, dep = 0, len = 1, t = now - last - 1; t; dep++, len<<=1, t>>=1 ) if(t&1)
52                 adde(HOLE(dep,pos),linkpoint), pos+=len;
53             last = now;
54         }
55     }
56     solve();
57     return 0;
58 }

倍增

T11：超立方体。点是0维元素（超立方体），线是1维元素（超立方体），面是2维元素（超立方体），体是3维元素（超立方体）。例如，4维超立方体由16个0维元素、32个1维元素、24个2维元素、8个3维元素和1个4维元素构成。现询问一个n维的超立方体分别由多少超立方体构成。(n≤1e7)

ANSWER：一个n维的超立方体与一个n维的直角坐标系息息相关。n维直角坐标系的实质是n个相互垂直的单位向量。单位向量就是2个点，也就是说每一维只有2种状态。考虑共点的情况，就是n维的状况完全一致。然后点分开，变成共线，就是n-1维的状况完全一致。之后共面，又有一维分开，n-2维的情况完全一致……于是发现，共“i”维，就是n-i维的状况完全一致，而其他i维可以自由选取，每一种共“i”维的情况就定出了一个i维超立方体。所以i维超立方体共有C(n,n-i)*2^n-ⁱ个。

　　怎么求C排列数？大概有以下几种情况：

　　法一是暴力杨辉三角（时空复杂度过大，预处理O(n^2)）。

　　法二是预处理阶乘逆元（要求模数有逆元，预处理复杂度O(n)）。

　　法三是lucas定理（要求模数是质数且不能过大，单次O(p*log_pn)）。

　　法四是线性筛因数（模数任意，预处理复杂度O(n)，查询O(lgn)）。

　　但这里其实是法五。因为C(n,i)=C(n,i-1)*(n-i+1)/i，而且模数是质数，复杂度O(n)。当然，这种算法基本上没有任何用处。

　　但我还是提一下

T12：BZOJ 4726 SABOTA 某个公司有n个人, 上下级关系构成了一个有根树。其中有个人是叛徒(这个人不知道是谁)。对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒占的比例超过x，那么这个人也会变成叛徒，并且他的所有下属都会变成叛徒。你要求出一个最小的x，使得最坏情况下，叛徒的个数不会超过k。

ANSWER：叛徒？不是公司，是黑帮吧……如果x小了，叛徒就会有很多，就会超过k。如果x太大，也会是很不优的。一个直观的想法就是预处理siz后直接二分答案。WXH说不能二分，因为ta直接TLE了。于是，此题能够不DFS那就应该for。　　

　　怎么check呢？有几个很显然的事实：叶子变成叛徒的情况最坏，而整个过程是向上的感染，最后一定是一整个子树。知道了这件基本事实以后，我们就可以搞了。

 1 #include 
 2 #include 
 3 #include 
 4 
 5 const int N = 500000 + 1000;
 6 const double eps = 1e-7;
 7 int n, k, fa[N], siz[N];
 8 double delta[N];
 9 bool hack[N];
10 
11 bool check(double mid) {
12     memset(hack,0,sizeof(bool)*(n+1));
13     for( int u = n; u >= 1; u-- ) {
14         if(siz[u]==1) hack[u]=1;
15         if(hack[u]) {
16             if(siz[u]>k) return false;
17             if(delta[u]>mid+eps) hack[fa[u]]=1;
18         }
19     }
20     return true;
21 }
22 
23 int main() {
24     scanf("%d%d",&n,&k);
25     for( int i = 2; i <= n; i++ ) scanf("%d",&fa[i]);
26     for( int u = n; u >= 1; u-- ) siz[u]++, siz[fa[u]]+=siz[u];
27     for( int u = n; u >= 1; u-- ) delta[u] = siz[u]*1.0/(siz[fa[u]]-1);
28     double lf = 0.0, rg = 1.0, mid, ans;
29     while(lf+eps<rg) {
30         mid = (lf+rg)/2;
31         if(check(mid)) ans = mid, rg = mid;
32         else lf = mid;
33     }
34     printf("%lf\n",ans);
35     return 0;
36 }

二分

　　但是这道题网上的人都说是树形DP。又是怎么回事？原来DP是一维的，表示该树不能被完全感染的最小的x。同样也是向上感染，状态也很好转移。如果子树u的大小大于k，那么ans就需要更新了，如果ans＜dp[u]，那么叛徒的个数就会超过k。

 1 #include 
 2 #include 
 3 #include 
 4 
 5 const int N = 500000 + 1000;
 6 int n, k, fa[N], siz[N];
 7 double dp[N], ans;
 8 inline void smax(double &a,double b) {a=std::max(a,b);}
 9 
10 int main() {
11     scanf("%d%d",&n,&k);
12     for( int i = 2; i <= n; i++ ) scanf("%d",&fa[i]);
13     for( int u = n; u >= 1; u-- ) siz[u]++, siz[fa[u]]+=siz[u];
14     for( int u = n; u >= 1; u-- ) {
15         if(siz[u]==1) dp[u]=1.0;
16         if(siz[u]>k) ans=std::max(ans,dp[u]);
17         smax(dp[fa[u]],std::min(dp[u],siz[u]*1.0/(siz[fa[u]]-1)));
18     }
19     printf("%lf\n",ans);
20     return 0;
21 }

树形DP

　　互相比较，发现其实思想是差不多的。万变不离其宗嘛。

T13：KAND。现在给你n个数，从中选出k个数，询问有多少种方案使得这k个数的按位与等于r。模大质数输出。

ANSWER：看似无从下手。但是，确实存在一个很显然却很难想到的性质：当且仅当是几个包含s的数的按位与才能包含s。这里的包含，是把二进制的每一位当做元素，把每个数当做集合来看的。也就是说，只要我们知道了包含s的数的个数，就能很方便地算出n个数中选k个数按位与能够包含s的方案数。既然已经算到这里，就直接用一个小容斥就可以了。

　　再说一遍，我们选k个数按位与为r直接统计出结果很难，但是已经说过了，选k个数按位包含r的方案数很好统计，只需要统计出有多少个数包含r就好了，再组合一下容斥一下就能得出结果。但是，怎么统计出有多少个数包含r？如果使用纯暴力，最坏能够达到3ⁿ的复杂度。于是IFT横空出世。

　　IFT是一种计数系统，分阶段拆位转移，可以刚好统计出包含s的所有数。本质是把包含s的ss转移到s，有且只有一种方式转移。而其他的一定不能够得到转移，总的复杂度做到了k*2^k。

（注：本人很久之后才发现，原来“IFT”就是FWT，普通的FWT是对半分，但是直接按位枚举是完全正确的，而且很优。）

　　代码如下：

 1 #define PN "kand"
 2 #include 
 3 const int N = 1e5+10;
 4 const int P = 20;
 5 const int MOD = 1e9+7;
 6 int n, k, s, lim, cnt[1<<P], fac[N], vfac[N];
 7 int mpow(int a,int b) {
 8     int ans=1;
 9     for(;b;a=(long long)a*a%MOD,b>>=1) if(b&1) ans=(long long)ans*a%MOD;
10     return ans;
11 }
12 void init_comb() {
13     fac[0]=1;for( int i = 1; i <= n; i++ ) fac[i]=(long long)fac[i-1]*i%MOD;
14     vfac[n]=mpow(fac[n],MOD-2);for( int i = n-1; i>=0; i-- ) vfac[i]=(long long)vfac[i+1]*(i+1)%MOD;
15 }
16 int comb(int n,int m) {
17     if(m>n) return 0;
18     return (long long)fac[n]*vfac[m]%MOD*vfac[n-m]%MOD;
19 }
20 void fix(int &a) {if(a>=MOD)a-=MOD;if(a<0)a+=MOD;}
21 void sum(int delta) {
22     for( int i = 0; i < P; i++ ) {
23         int bit=1<1-bit;
24         for( int ss=s; ss; ss=(ss-1)&s ) {
25             cnt[ss]+=delta*cnt[ss|bit];
26             fix(cnt[ss]);
27         }
28         cnt[0]+=delta*cnt[bit];
29         fix(cnt[0]);
30     }
31 }
32 int main() {
33     freopen(PN".in","r",stdin);
34     freopen(PN".out","w",stdout);
35     scanf("%d%d%d",&n,&k,&s);lim=1<<P;
36     for( int i = 1, x; i <= n; i++ ) scanf("%d",&x), cnt[x]++;
37     sum(+1);
38     init_comb();for( int ss = 0; ss < lim; ss++ ) cnt[ss]=comb(cnt[ss],k);
39     sum(-1);
40     printf("%d\n",cnt[s]);
41     return 0;
42 }

kand

未完待续……

综合模拟赛 VIB

Some Interesting Problems（持续更新中）

相关

标签