NOIP模拟测试31

好久没写题解了，感觉很多好题没留下什么就这么过去了，着急改题很多细节和原理都没有注意到，思考也不够（考得越来越差），所以还是很有必要写的。

看到后的确没什么可接受复杂度的思路。直接说做法吧。

70%：O（nk^2）

把每个a_i看成一组，由(ai*bi)%k知每组最多有k个物品（循环节），然后问题就转化为一个分组背包，看有多少个<k的非负整数能被凑出。

由于循环节长远不到k，所以骗到了70分。。。

70%：O（nklogk）

观察到上面对每个物品都要遍历一次容量，而很多容量是无用状态。最明显的，对于一个组内的物品，其实是一个物品重复放很多次而算作一次。

然后我们可以发现分组没有什么用，定义一个单个物品为权值为ai，数量为ai在模k意义下的能取到值的个数，即循环节长度。

接着这个多重背包就可以用二进制优化了。

80%：O（nk）

发现一个容量会被重复凑出很多次。

放在模k意义下，那么答案最多有k个。设dp[k]为k能否被凑出，然后搜索用n个物品反复拓展到新状态即可。

100%：O（n+k）

从给的样例中其实就能看出答案是个等差数列，yy一下能发现公差就是ai和k的gcd

然后就AC了。。。。。。

考场上我这都没看出来额。。。

正确性：

ax+by=c(mod k)有整数解当且仅当 d|c，

那么ax+by+cz+....=q(mod k)有整数解当且仅当gcd(a,b,c,...)|q

其实就是裴蜀定理的推论。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define F(i,a,b) for(register int i=a;i<=b;++i)
 4 int n,mod;
 5 int p[500005],pcnt;
 6 int gcd(int a,int b){return !b?a:gcd(b,a%b);}
 7 int main()
 8 {
 9     scanf("%d %d",&n,&mod);int t,d=0,pt=0;
10     F(i,1,n){scanf("%d",&t);d=gcd(d,t%mod);}
11     do{
12         p[++pcnt]=pt;
13         pt=(pt+d)%mod;
14     }while(pt);
15     printf("%d
",pcnt);
16     std::sort(p+1,p+pcnt+1);
17     F(i,1,pcnt)printf("%d ",p[i]);
18     return 0;
19 }

View Code

考试的时候一直在想图论，然后最后就打了一个n^2m^2的拓扑跑了。。。

后来一想DAG拓扑不就是dp吗。。。

拓扑没办法优化可是dp可以

40%：O（n^2m^2）朴素dp：f[i][j]=max(f[k][l]+b[i][j]+|i-k|+|j-l|)

80%：O（nmlognlogm）

柿子套路，遇到绝对值要拆开

之后就可以用四个二维树状数组维护了。

100%：

切比雪夫距离

转化坐标(i,j)->(i+j,i-j)，可以由归纳得，然而好像不能通过画图直观理解。

要求的曼哈顿距离|i-i'|+|j-j'|转化为max(|i-i'|,|j-j'|)

这样我们就可以不用二维树状数组维护具体位置了，维护拆掉绝对值后的四个变量即可。

由于同层之间不能转移，离散化。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<queue>
 4 #include<cstring>
 5 #include<algorithm>
 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=2005;
12 const int inf=1000000000;
13 int n,m;
14 int id[N][N],icnt;
15 int lsh[1000005],lcnt;
16 char cx[1000005];
17 ll x1[1000005],x2[1000005],x3[1000005],x4[1000005];
18 struct P{
19     int x,y,a,b;
20     friend bool operator<(P g,P h){return g.a<h.a;}
21 }p[N*N];
22 int main()
23 {
24     memset(x1,0xcf,sizeof(x1));
25     memset(x2,0xcf,sizeof(x2));
26     memset(x3,0xcf,sizeof(x3));
27     memset(x4,0xcf,sizeof(x4));
28     n=read(),m=read();
29     reg int t;
30     F(i,1,n)F(j,1,m)
31     {
32         t=read();
33         if(t)
34         {
35             cx[t]=1;
36             id[i][j]=++icnt;
37             p[icnt]=(P){i+j,i-j,t};
38         }
39     }
40     F(i,1,1000000)if(cx[i])lsh[i]=++lcnt;
41     F(i,1,n)F(j,1,m)
42     {
43         t=read();
44         if(id[i][j])
45         {
46             p[id[i][j]].a=lsh[p[id[i][j]].a];
47             p[id[i][j]].b=t;
48         }
49     }
50     sort(p+1,p+icnt+1);
51     ll ans=-inf;
52     x1[0]=x2[0]=x3[0]=x4[0]=0;
53     F(i,1,icnt)
54     {
55         ll t;
56         if(p[i].a-1==0)t=0;
57         else t=max(max(x1[p[i].a-1]+p[i].x,x2[p[i].a-1]-p[i].x),max(x3[p[i].a-1]+p[i].y,x4[p[i].a-1]-p[i].y));
58         ans=max(ans,p[i].b+t);
59         x1[p[i].a]=max(x1[p[i].a],p[i].b+t-p[i].x);
60         x2[p[i].a]=max(x2[p[i].a],p[i].b+t+p[i].x);
61         x3[p[i].a]=max(x3[p[i].a],p[i].b+t-p[i].y);
62         x4[p[i].a]=max(x4[p[i].a],p[i].b+t+p[i].y);
63     }
64     printf("%lld
",ans);
65     return 0;
66 }
67 int read()
68 {
69     int x=0;char tc=getchar();
70     while(tc<'0'||tc>'9')tc=getchar();
71     while(tc>='0'&&tc<='9')x=x*10+tc-48,tc=getchar();
72     return x;
73 }

View Code

NOIP模拟测试31

A. math

B. biology