NOIP模拟测试19

T1：

　　题目大意：将一颗有N个节点的树分割，使得每个联通块大小相等，问一共有多少方案。（N<=1000000）

　　首先，一条很显然的性质，每个联通块的大小一定是N的因子。

　　然后，我们可以对于每个因子d，DFS一遍，维护一个si值，代表该子树中有多少节点是连通的，一旦这个值等于d，将这颗子树切掉，若这个值大于d，则判定不合法。

　　这个方法每次DFS只验证一个因子，效率较低。

　　我们可以只进行一遍DFS将每颗子树的大小存进一个桶里。一颗子树被切掉，当且仅当该子树中剩下的点共有d个，若d合法，则当前子树原有的节点数应为d的倍数，我们可以枚举每个因子的每个倍数，在桶里查询，若总数为N/d，则合法。

　　时间复杂度为$sum_{d|N}d=O(Nlog_2N)$

Code:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=1000010;
 7 int n,nm=0,m=0,ans=1;
 8 int fi[N],d[210],s[N];
 9 struct edge{
10     int v,ne;
11 }e[N<<1];
12 void add(int x,int y)
13 {
14     e[++nm].v=y;
15     e[nm].ne=fi[x];fi[x]=nm;
16 }
17 int read()
18 {
19     int s=0;char c=getchar();
20     while(c<'0'||c>'9') c=getchar();
21     while(c>='0'&&c<='9'){
22         s=(s<<3)+(s<<1)+c-'0';
23         c=getchar();
24     }
25     return s;
26 }
27 void divide()
28 {
29     for(int i=2;i<=sqrt(n);i++){
30         if(n%i==0){
31             d[++m]=i;
32             if(i*i!=n) d[++m]=n/i;
33         }
34     }
35 }
36 bool dfs(int x,int p)
37 {
38     s[x]=1;
39     for(int i=fi[x];i!=0;i=e[i].ne){
40         int y=e[i].v;
41         if(y==p) continue;
42         dfs(y,x);
43         s[x]+=s[y];
44     }
45 }
46 bool check(int x)
47 {
48     int tot=0;
49     for(int i=x;i<=n;i+=x){
50         int l=lower_bound(s+1,s+n+1,i)-s;
51         int r=upper_bound(s+1,s+n+1,i)-s;
52         tot+=r-l;
53     }
54     if(x*tot==n) return true;
55     else return false;
56 }
57 int main()
58 {
59     n=read();
60     if(n!=1) ans++;
61     for(int i=1;i<n;i++){
62         int x=read(),y=read();
63         add(x,y);add(y,x);
64     }
65     divide();
66     dfs(1,0);
67     sort(s+1,s+n+1);
68     for(int i=1;i<=m;i++){
69         if(check(d[i])) ans++;
70     }
71     printf("%d
",ans);
72     return 0;
73 }

T2：

　　题目大意：一个圆环上有N个数，将这N个数分为M个块，使得最大的块的和最小，输出这个最小值。

　　显然的单调性，二分答案。

　　对于圆环，短环成链并复制一倍。

　　关键点在于起始点的选择，$O(N)$枚举起始点再$O(N)$判断是绝对不可行的，我们需要优化。

　　我们可以优化判断，一般的判断方式是一个一个累加，直到大于二分的值位置，这个过程可以用倍增优化，设st[i][j]为以i为起点，长度为2^j的区间和，从大到小枚举j，若加和小于二分的值，则累加。

　　时间复杂度$O(NM*log_2NM)$，M较大时有可能被卡掉。

　　还有一种思路是优化枚举起点。

　　我们先假设以0处为起始点，用$O(N)$的方法先找到此时的第一个块，也就是最靠左的块，并设这个块的左端点为L，右端点为R。

　　那么枚举的起始点只用在区间[L,R]内移动。

　　证明：

　　　　由于是圆环，所以从一个点向左右扩展都是可以的，如果以R+1为起始点，它可以向左扩展，其向左的第一个块必定为[L,R]，与枚举起始点在L的情况重复了，所以不需要再枚举，其它点同理。

　　所以我们就在复杂度上除了一个M。

　　但是这个方法在一开始二分的值较大时会被卡成$O(N)$，所以在一开始要强化剪枝，一旦发现可行情况或发现不可行时要立即中止，才能保证算法的高效

　　时间复杂度$O((N^2log_2N)/M)$，M较小时会十分低效。

　　将两种思路综合起来就很难被卡掉了，或者可以测试点分治。我用的是第二种思路。

Code:

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int N=50010;
 5 int n,m,nn,L=0,R=0,ans;
 6 int t[N<<1];
 7 bool judge(int y,int x)
 8 {
 9     int ans=1,tot=0;
10     for(int i=y;i<=y+n-1;i++){
11         if(tot+t[i]>x){
12             ans++;tot=t[i];
13         }
14         else tot+=t[i];
15         if(ans>m) return false;
16     }
17     return true;
18 }
19 bool check(int x)
20 {
21     int l=1,r=0,tot=0;
22     for(int i=1;i<=n;i++){
23         if(tot+t[i]>x) break;
24         r=i;tot+=t[i];
25     }
26     for(int i=l;i<=r;i++){
27         if(judge(i,x)) return true;
28     }
29     return false;
30 }
31 int main()
32 {
33     scanf("%d%d",&n,&m);
34     nn=2*n-1;
35     for(int i=1;i<=n;i++){
36         scanf("%d",&t[i]);
37         R+=t[i];L=max(L,t[i]);
38     }
39     for(int i=n+1;i<=nn;i++)
40         t[i]=t[i-n];
41     ans=R;
42     while(L<=R){
43         int mid=(L+R)>>1;
44         if(check(mid)){
45             ans=mid;
46             R=mid-1;
47         }
48         else
49             L=mid+1;
50     }
51     printf("%d
",ans);
52     return 0;
53 }

T3：

　　详见洛谷1606白银莲花池。

　　我打的是BFS和DFS，用spfa也可以。

　　首先要求起点到终点的最短路径。我们发现移动一步的贡献不大于1，用不着最短路算法，一般的BFS可以解决。

　　但是此题有两种边权，0和1，并且0在使用一次后会变成1。

　　性质一：起点到终点的最短路中没有环。

　　证明一：环的权值不为负，所以走环之后步数不会少。

　　性质二：同一个点至多被经过一次。

　　证明二：若同一个点被经过多次，则一定存在环。

　　我们可以记录每个点是否被走过，然后就可以BFS了。

　　到现在这道题和算法竞赛进阶指南0x26中电路维修一样。可以用双端队列BFS解决，若到一个点的贡献为0，则从队头入队，反之从队尾入队。

　　问题一解决，现在求路径条数。

　　数据有问题，不过在作者和某NC的竭力hack，以及tdcp提供错误AC标程，该问题已被解决。

　　我们发现如果一个点被重复经过，会导致结果的错误，我们需要一个强有力的剪枝。

　　我们把从起点开始的求最短路BFS改为从终点开始，求出终点到所有点的最短距离，作为估价函数，搜索中一旦发现当前代价加估价大于最短路时，立即终止搜索，这样就可以防止重复了。

　　题目要求经过空格不同才算方案不同。

　　这个用BFS不好解决，我们可以嵌套DFS。

　　性质三：所有连通的敌人可以缩为一个点。

　　我们发现敌人就是一个中介点，由于敌人和方案数无关，它不能被入队，但是我们可以经过敌人到达其他的空地。

　　我没建边，所以用了鬼畜的DFS。

　　大框架还是BFS，每次对出队元素进行DFS，如果遇到敌人，则继续进行DFS，遇到空格就将其入队。

　　注意在同一次DFS中，更新节点的信息来源于同一个节点，所以一个点只能被更新一次。多次DFS之间，为防止重复，每个点只能入队一次。

　　BFS到最后，即为正确答案。

　　由于DFS的存在，时间复杂度$O(N^2M^2)$，但远远达不到这个上界。

Code：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #define LL long long
  5 using namespace std;
  6 const int N=61;
  7 int n,m,sx,sy,ex,ey;
  8 int ans1=0;
  9 LL ans2=0;
 10 int a[N][N],v[N][N];
 11 LL dp[N][N][N*N];
 12 bool vis[N][N],in[N][N],out[N][N][N*N];
 13 int dex[9]={0,1,1,2,2,-1,-1,-2,-2};
 14 int dey[9]={0,2,-2,1,-1,2,-2,1,-1};
 15 deque<int> q1,q2,q3;
 16 void bfs1()
 17 {
 18     v[ex][ey]=1;
 19     q1.push_back(ex);q2.push_back(ey);
 20     while(!q1.empty()){
 21         int x=q1.front(),y=q2.front();
 22         q1.pop_front();q2.pop_front();
 23         for(int i=1;i<=8;i++){
 24             int xx=x+dex[i],yy=y+dey[i];
 25             if(a[xx][yy]==2||xx<1||xx>n||yy<1||yy>m) continue;
 26             if(v[xx][yy]!=0) continue;
 27             if(a[xx][yy]==1){
 28                 v[xx][yy]=v[x][y];
 29                 q1.push_front(xx);q2.push_front(yy);
 30             }
 31             else{
 32                 v[xx][yy]=v[x][y]+1;
 33                 q1.push_back(xx);q2.push_back(yy);
 34             }
 35         }
 36     }
 37     for(int i=1;i<=n;i++){
 38         for(int j=1;j<=m;j++){
 39             v[i][j]-=1;
 40             if(a[i][j]==3) ans1=v[i][j];
 41         }
 42     }
 43 }
 44 void dfs1(int xx,int yy,int x,int y,int z)
 45 {
 46     vis[xx][yy]=true;
 47     for(int i=1;i<=8;i++){
 48         int nex=xx+dex[i],ney=yy+dey[i];
 49         if(a[nex][ney]==2||nex<1||nex>n||ney<1||ney>m) continue;
 50         if(a[nex][ney]==1){
 51             if(v[nex][ney]+z>ans1) continue;
 52             if(vis[nex][ney]) continue;
 53             dfs1(nex,ney,x,y,z);
 54         }
 55         else{
 56             if(v[nex][ney]+z+1>ans1) continue;
 57             if(in[nex][ney]) continue;
 58             in[nex][ney]=true;
 59             dp[nex][ney][z+1]+=dp[x][y][z];
 60             if(!out[nex][ney][z+1]){
 61                 q1.push_back(nex);q2.push_back(ney);q3.push_back(z+1);
 62                 out[nex][ney][z+1]=true;
 63             }
 64         }
 65     }
 66 }
 67 void dfs2(int x,int y,int z)
 68 {
 69     vis[x][y]=false;
 70     for(int i=1;i<=8;i++){
 71         int nex=x+dex[i],ney=y+dey[i];
 72         if(a[nex][ney]==2||nex<1||nex>n||ney<1||ney>m) continue;
 73         if(a[nex][ney]==1){
 74             if(v[nex][ney]+z>ans1) continue;
 75             if(!vis[nex][ney]) continue;
 76             dfs2(nex,ney,z);
 77         }
 78         else{
 79             if(v[nex][ney]+z+1>ans1) continue;
 80             in[nex][ney]=false;
 81         }
 82     }
 83 }
 84 void bfs2()
 85 {
 86     while(!q1.empty()){
 87         q1.pop_back();q2.pop_back();
 88     }
 89     dp[sx][sy][0]=1;out[sx][sy][0]=true;
 90     q1.push_back(sx);q2.push_back(sy);q3.push_back(0);
 91     while(!q1.empty()){
 92         int x=q1.front(),y=q2.front(),z=q3.front();
 93         out[x][y][z]=false;
 94         q1.pop_front();q2.pop_front();q3.pop_front();
 95         dfs1(x,y,x,y,z);
 96         dfs2(x,y,z);
 97     }
 98     ans2=dp[ex][ey][ans1];
 99 }
100 int main()
101 {
102     scanf("%d%d",&n,&m);
103     for(int i=1;i<=n;i++){
104         for(int j=1;j<=m;j++){
105             scanf("%d",&a[i][j]);
106             if(a[i][j]==3){
107                 sx=i;sy=j;
108             }
109             if(a[i][j]==4){
110                 ex=i;ey=j;
111             }
112         }
113     }
114     bfs1();
115     if(ans1==-1){
116         printf("%d
",ans1);
117         return 0;
118     }
119     else
120         printf("%d
",ans1-1);
121     bfs2();
122     printf("%lld
",ans2);
123     return 0;
124 }