08-11 NOIP模拟测试17

暴力n^4+特性可得75，然而由于我的智障测试点分治阀很shi以及没有开longlong也没取模只有60分。。。

像这种数据范围只给<=不确定具体范围而不好卡分治时，可以用输入量先算下复杂度，然后用计算量分治。对于这题算下n*m>6400 n^4够呛跑特性即可。

正解：

看这数据范围正解应该是n^3的，所以我们要去掉一层枚举。

这题答案爆long long，++ans必死。所以我们要一次拿出多个答案，就是+=。

哪里有+=成段操作，线段树？加个log好像就T了。。。

天天爱跑酷？好像差不多，我们可以用类似的思想，不用对于每个答案都走一遍流程，而可以只走一遍，巧妙地在整体的计算过程中不断得到当时已经可以得到的局部答案。

那题的过程体现在桶上，这题是否也可？

然后引入一个十分关键而我考场上压根没往这想的性质：

不得不说这真的是太帅了。真没想到哇，看来我还是菜啊。

把这个性质拓展到二维也是类似的。每次枚举两个行n^2（就是x1,x2），然后向右O(m)扫，过程中维护桶存x1~x2卡着的横向前缀和。由于k很大，不能够最后处理桶里的答案，所以在过程中实时统计。最后删除不能memset，怎么来怎么回去就好。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define ll long long
 4 #define reg register
 5 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
 6 using namespace std;
 7 const int N=405,G=1000005;
 8 int read();
 9 int z[N][N];
10 int sum[N][N];
11 int bk[G];
12 int n,m,g;
13 int get(int i,int j,int k,int l)
14 {
15     return ((sum[k][l]-sum[i-1][l]-sum[k][j-1]+sum[i-1][j-1])%g+g)%g;
16 }
17 int main()
18 {
19     n=read(); m=read(); g=read();
20     F(i,1,n)
21     {
22         F(j,1,m)
23         {
24             z[i][j]=read();
25             sum[i][j]=((sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1])%g+z[i][j]+g)%g;
26         }
27     }
28     ll ans=0;
29     reg int t;
30     F(i,1,n)
31     {
32         F(j,i,n)
33         {
34             F(k,1,m)
35             {
36                 t=get(i,1,j,k);
37                 ans+=bk[t];
38                 ++bk[t];
39             }
40             ans+=bk[0];
41             F(k,1,m) --bk[get(i,1,j,k)];
42         }
43     }
44     printf("%lld
",ans);
45     return 0;
46 }
47 int read()
48 {
49     int x=0;
50     char tc=getchar();
51     while(tc<'0'||tc>'9') tc=getchar();
52     while(tc>='0'&&tc<='9') x=x*10+tc-48,tc=getchar();
53     return x;
54 }

View Code

刚看觉得是一道很nb的dp题，只会k==1的类小胖守皇宫。

然后发现似乎可以贪心，想了下觉得是正确的。然而我充分不相信我觉得，于是觉得贪心不是正解，但能拿到不少分。

于是放弃了一堆分类讨论的dp，开始码一个不走心的贪心dfs。

码完就发现了问题，发现在处理祖先链上的子孙时有点bug。

说正解吧：真是贪心

发现对于一个没有被控制的点，在它的k级祖先驻队一定是最优的。假设我们将小队下调，那么子孙一定还能被控制，而祖先方向的控制范围-1，答案变差。

钦定一个节点做根，我们把所有节点的深度从大到小排序，这可以用bfs来O(n)做，也可以得深度排序或者优先队列加个logn。

然后扫，对于一个没有被控制的点，++ans，向上找k级祖先，然后从k级祖先暴力dfs走k步控制周围点，重复这个过程。根节点注意特判。

由于k很小可做，复杂度为O(kn)。

  1 #include<cstdio>
  2 #include<vector>
  3 #include<queue>
  4 #include<algorithm>
  5 #include<cstdlib>
  6 #define ll long long
  7 #define reg register
  8 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
  9 using namespace std;
 10 int read();
 11 const int N=100005;
 12 int n,d,typ;
 13 bool vis[N],cl[N];
 14 int fa[N];
 15 vector<int> p;
 16 queue<int> q;
 17 struct R{
 18     int u,v,next;
 19 }r[N<<1];
 20 int fir[N],o=1;
 21 void add(int u,int v)
 22 {
 23     r[++o].u=u;
 24     r[o].v=v;
 25     r[o].next=fir[u];
 26     fir[u]=o;
 27 }
 28 void bfs()
 29 {
 30     q.push(1);
 31     int u,v;
 32     while(!q.empty())
 33     {
 34         u=q.front();
 35         q.pop();
 36         p.push_back(u);
 37         vis[u]=1;
 38         for(reg int i=fir[u];i;i=r[i].next)
 39         {
 40             v=r[i].v;
 41             if(vis[v]) continue;
 42             fa[v]=u;
 43             q.push(v);
 44         }
 45     }
 46 }
 47 void dfs(int u,int fa,int step)
 48 {
 49     cl[u]=1;
 50     if(step==d) return;
 51     for(reg int i=fir[u];i;i=r[i].next)
 52     {
 53         int v=r[i].v;
 54         if(v==fa) continue;
 55         dfs(v,u,step+1);
 56     }
 57 }
 58 int main()
 59 {
 60     n=read(); d=read(); typ=read();
 61     if(d==0)
 62     {
 63         printf("%d
",n);
 64         return 0;
 65     }
 66     int ta,tb;
 67     F(i,1,n-1)
 68     {
 69         ta=read(); tb=read();
 70         add(ta,tb); add(tb,ta);
 71     }
 72     reg int ans=0,x;
 73     bfs();
 74     for(reg int i=p.size()-1;i>=0;--i)
 75     {
 76         if(!cl[p[i]])
 77         {
 78             ++ans;
 79             x=p[i];
 80             F(o,1,d)
 81             {
 82                 if(!fa[x]) break;
 83                 x=fa[x];
 84             }
 85             dfs(x,0,0);
 86         }
 87     }
 88     printf("%d
",ans);
 89     return 0;
 90 }
 91 int read()
 92 {
 93     int x=0;
 94     char tc=getchar();
 95     while(tc<'0'||tc>'9') tc=getchar();
 96     while(tc>='0'&&tc<='9') x=x*10+tc-48,tc=getchar();
 97     return x;
 98 }
 99 /*
100 
101 g++ 2.cpp -o 2
102 ./2
103 4 1 0
104 1 2
105 1 3
106 1 4
107 
108 g++ 2.cpp -o 2
109 ./2
110 6 1 0
111 1 2
112 1 3
113 1 4
114 4 5
115 4 6
116 
117 
118 g++ 2.cpp -o 2
119 ./2
120 20 2 0
121 1 11
122 1 2
123 1 3
124 2 5
125 2 4
126 4 10
127 4 6
128 6 9
129 6 7
130 6 8
131 3 12
132 12 13
133 12 14
134 12 15
135 12 16
136 14 17
137 17 18
138 17 19
139 13 20
140 
141 */

View Code

T3日常神仙，也不是之前那种能卡过的T3。

这真的是道好题，

考场上只会bfs+状压暴力转移，24分。

说正解：神状压！

隐藏的十分隐蔽。不过这题非常综合，在通往真理的路上迷雾重重，都是高难思维点。

启发：在当前的问题无法着手时，不妨利用一些性质或者是技巧（平时积累）转化（当然是简化）题意，逐步击破！

阶段一：从扯淡题意中抽离模型。

给定一个n长的0/1串，m个区间长度（可重复使用），用最少的区间翻转n串，使n串全为1。

或者一种令我走进死胡同的说法：给定一个n长的0/1串，m个不同长度全1串，用最少的区间异或n串，使n串全为1。然后便能发现n串的0位有奇数个区间叠加，1位有偶数个区间叠加，然后我就开始YY什么01Trie、哈希表。emm...
在一种思路走不通的时候，如果超过自己的心态极限，不要犹豫换个角度，或先拿到部分分稳住。

阶段二：

是对于以往的大区间频繁修改问题，我们可以用差分转化为单点修改（或者直接线段树），异或也可以差分。

定义b[i]=a[i]^a[i-1]，那么[l,r]的翻转在b的表现为b[l]与b[r+1]取反。

然后问题就转化为在n+1（多出的一个数处理边界）数中，用m个距离不同的1xxx1对异或使序列全为0（b[]，全0即a[]全等，之所以n+1也是定义了等的是什么）。

似乎还是不可做。emm

阶段三：

我们发现答案中不会存在一个操作对于两个0。那么有以下理解：

1.异或到0 1，含义可理解为1走到0的位置。

2.1 1，两个1相遇相消。

对2k个点为起点分别bfs一遍，复杂度O(2kmn)

注意bfs左右都要走，例如一点在左，4长距离，5长和1长区间，显然是先右5再左1，而不是(右1)*4

要使所有物品消失，又k很小，考虑状压。

非常非常类似与愤怒的小鸟，直接状态刷表即可。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #include<queue>
  5 #include<algorithm>
  6 #include<cstdlib>
  7 #define ll long long
  8 #define reg register
  9 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
 10 using namespace std;
 11 //1亮0灭，异或差分,1不同
 12 //消1为0
 13 int read();
 14 const int N=40005;
 15 const int K=20;
 16 const int M=70;
 17 int n,need,m;
 18 int a[N],b[N],id[N],pos[K],len[M],cnt;
 19 int dis[K][K];
 20 bool vis[N];
 21 queue<pair<int,int> > q;
 22 struct OPT{
 23     int obj,w;
 24 }opt[N];
 25 int dp[1<<K];
 26 int ocnt;
 27 void bfs(int st)
 28 {
 29     memset(vis,0,sizeof(vis));
 30     q.push(make_pair(st,0));
 31     int u,v,sp;
 32     vis[st]=1;
 33     dis[id[st]][id[st]]=0;
 34     while(!q.empty())
 35     {
 36         u=q.front().first;
 37         sp=q.front().second;
 38         q.pop();
 39         if(id[u]&&dis[id[st]][id[u]]==-1)
 40         {
 41             dis[id[st]][id[u]]=sp;
 42         }
 43         F(i,1,m)
 44         {
 45             v=u+len[i];
 46             if(v<=n&&!vis[v])
 47             {
 48                 vis[v]=1;
 49                 q.push(make_pair(v,sp+1));
 50             }
 51             v=u-len[i];
 52             if(v>0&&!vis[v])
 53             {
 54                 vis[v]=1;
 55                 q.push(make_pair(v,sp+1));
 56             }
 57         }
 58     }
 59 }
 60 int main()
 61 {
 62     memset(dis,-1,sizeof(dis));
 63     n=read(); need=read(); m=read();
 64     F(i,1,n) a[i]=1;
 65     int t;
 66     F(i,1,need) a[read()]=0;
 67     a[0]=1;
 68     ++n;
 69     a[n]=1;
 70     F(i,1,n)
 71     {
 72         b[i]=a[i]^a[i-1];
 73         if(b[i])
 74         {
 75             id[i]=++cnt;
 76             pos[cnt]=i;
 77         }
 78     }
 79     F(i,1,m)
 80     {
 81         len[i]=read();
 82     }
 83     if(m==1)
 84     {
 85         int ans=0;
 86         F(i,1,n)
 87         {
 88             if(b[i])
 89             {
 90                 b[i]=0;
 91                 b[i+len[1]]^=1;
 92                 ++ans;
 93             }
 94         }
 95         printf("%d
",ans);
 96         return 0;
 97     }
 98     F(i,1,cnt) bfs(pos[i]);
 99     F(i,1,cnt)
100     {
101         F(j,i+1,cnt)
102         {
103             if(dis[i][j]==-1) continue;
104             opt[++ocnt].obj=(1<<(i-1))|(1<<(j-1));
105             opt[ocnt].w=dis[i][j];
106 //            printf("(%d->%d) %d
",i,j,dis[i][j]);
107         }
108     }
109     memset(dp,0x3f,sizeof(dp));
110     dp[0]=0;
111     const int S=(1<<cnt)-1;
112     for(reg int s=0;s<=S;++s)
113     {
114         F(i,1,ocnt)
115         {
116             dp[s|opt[i].obj]=min(dp[s|opt[i].obj],dp[s]+opt[i].w);
117         }
118     }
119     printf("%d",dp[S]);
120     return 0;
121 }
122 int read()
123 {
124     int x=0;
125     char tc=getchar();
126     while(tc<'0'||tc>'9') tc=getchar();
127     while(tc>='0'&&tc<='9') x=x*10+tc-48,tc=getchar();
128     return x;
129 }

View Code

最后　　加油!qwq

08-11 NOIP模拟测试17

A. 入阵曲

B. 将军令

C. 星空