csps模拟测试70

　　T1：见过高考数学题，没见过中考数学题？？？？

　　首先是赵爽弦图。推一波柿子，属于义务教育内容。

　　得到就是$\sum \limits_{i=1}^n n|i^2$

　　然后考试时我就在颓柿子，旁边的Barca大力打表。

　　这时突然，吧人擦眉头紧皱猥琐微笑，露出痛苦AK的神情。打了一份不到百B的代码并通过了样例

　　woc打表？？？

　　然后我也开始打，然后5min后，我也眉头紧皱猥琐微笑，露出痛苦AK的神情。

　　。。。。然后就A了

　　T2：DP+链表优化，或者某笑一直鼓吹的“小XX线段树”

　　核心思想在于最多进行根号n次更新就不在有贡献。

　　T3：拼图，构造题没见过。

　　小范围爆搜，大范围拼图。

　　爆写4.0k，分类300行。

  1 #include
  2 #include
  3 #include
  4 #include
  5 #include
  6 using std::cout;
  7 using std::endl;
  8 const int N=1010;
  9 const int dx[8]={-3,-2,0,2,3,2,0,-2},dy[8]={0,2,3,2,0,-2,-3,-2};
 10 int a[N][N],n,cnt;
 11 inline int rd()
 12 {
 13     int s=0,w=1;
 14     char cc=getchar();
 15     for(;cc<'0'||cc>'9';cc=getchar()) if(cc=='-') w=-1;
 16     for(;cc>='0'&&cc<='9';cc=getchar()) s=(s<<3)+(s<<1)+cc-'0';
 17     return s*w;
 18 }
 19 int st[5][5]=
 20 {
 21 {1,16,19,2,15},
 22 {11,22,5,12,21},
 23 {18,8,25,17,7},
 24 {4,13,20,3,14},
 25 {10,23,6,9,24}
 26 };
 27 int u[5][5]=
 28 {
 29 {19,14,25,20,15},
 30 {11,22,17,12,23},
 31 {5,8,1,4,7},
 32 {18,13,24,21,16},
 33 {10,3,6,9,2}
 34 };
 35 int d[5][5]=
 36 {
 37 {10,21,6,9,22},
 38 {16,13,24,19,14},
 39 {5,8,1,4,7},
 40 {11,20,15,12,23},
 41 {17,3,25,18,2}
 42 };
 43 int l[5][5]=
 44 {
 45 {18,5,24,19,6},
 46 {10,21,16,9,22},
 47 {25,13,1,4,14},
 48 {17,8,23,20,7},
 49 {11,3,15,12,2}
 50 };
 51 int r[5][5]=
 52 {
 53 {18,10,24,17,9},
 54 {13,21,7,12,22},
 55 {5,16,1,4,25},
 56 {19,11,23,20,8},
 57 {14,3,6,15,2}
 58 };
 59 int q[5][5]=
 60 {
 61 {25,17,8,24,16},
 62 {20,11,14,19,10},
 63 {5,23,1,4,7},
 64 {13,18,9,12,15},
 65 {21,3,6,22,2}
 66 };
 67 int c[5][5]=
 68 {
 69 {17,7,24,16,8},
 70 {12,21,3,11,22},
 71 {5,15,18,6,25},
 72 {2,10,23,1,9},
 73 {13,20,4,14,19}
 74 };
 75 int e[5][5]=
 76 {
 77 {9,25,15,10,24},
 78 {20,12,7,21,13},
 79 {5,17,1,4,16},
 80 {8,22,14,11,23},
 81 {19,3,6,18,2}
 82 };
 83 void in(int x,int y,int (*s)[5])
 84 {
 85     for(int i=0;i<5;i++)
 86         for(int j=0;j<5;j++)
 87             a[x+i][y+j]=s[i][j]+cnt;
 88 }
 89 void dfs1(int x,int y,int op)
 90 {
 91     if(x==1&&y==1&&op!=9) return;
 92     if(x==1&&y-5==1)
 93     {
 94         in(x,y,e);
 95         cnt+=25;
 96         return ;
 97     }
 98     if(op==9)
 99     {
100         in(x,y,st);
101         cnt+=6;
102         dfs1(x+5,y,1);
103         return;
104     }
105     if(op==1&&x+5>n)
106     {
107         in(x,y,r);
108         cnt+=25;
109         dfs1(x,y+5,2);
110         return;
111     }
112     if(op==8)
113     {
114         in(x,y,c);
115         cnt+=25;
116         dfs1(x,y+5,2);
117         return;
118     }
119     if(op==2&&y+4==n)
120     {
121         if(x-5==1)
122         {
123             in(x,y,u);
124             cnt+=25;
125             dfs1(x-5,y,0);
126         }
127         else
128         {
129             in(x,y,q);
130             cnt+=25;
131             dfs1(x-5,y-5,8);
132         }
133         return;
134     }
135     if(op==2&&x+4==n&&y+9==n)
136     {
137         in(x,y,r);
138         cnt+=25;
139         dfs1(x,y+5,2);
140         return;
141     }
142     if(op==2&&x+4==n)
143     {
144         in(x,y,u);
145         cnt+=25;
146         dfs1(x-5,y,0);
147         return;
148     }
149     if(op==2&&x-5==1)
150     {
151         in(x,y,d);
152         cnt+=25;
153         dfs1(x+5,y,1);
154         return;
155     }
156     if(op==0&&y+4==n&&x==1)
157     {
158         in(x,y,l);
159         cnt+=25;
160         dfs1(x,y-5,3);
161         return;
162     }
163     if(op==0&&y+4!=n&&x-5==1)
164     {
165         in(x,y,r);
166         cnt+=25;
167         dfs1(x,y+5,2);
168         return;
169     }
170     if(op==1)
171     {
172         in(x,y,d);
173         cnt+=25;
174         dfs1(x+5,y,1);
175         return;
176     }
177     if(op==0)
178     {
179         in(x,y,u);
180         cnt+=25;
181         dfs1(x-5,y,0);
182         return;
183     }
184     if(op==3)
185     {
186         in(x,y,l);
187         cnt+=25;
188         dfs1(x,y-5,3);
189         return;
190     }
191 }
192 void dfs2(int x,int y,int op)
193 {
194     //cout<195     //if(y>n) while(1);
196     if(x==1&&y==1&&op!=9) return;
197     if(x==1&&y-5==1)
198     {
199         in(x,y,e);
200         cnt+=25;
201         return ;
202     }
203     if(op==9)
204     {
205         in(x,y,st);
206         cnt+=6;
207         dfs2(x+5,y,1);
208         return;
209     }
210     if(op==1&&x+4==n)
211     {
212         in(x,y,r);
213         cnt+=25;
214         dfs2(x,y+5,2);
215         return;
216     }
217     if(op==2&&x+4==n)
218     {
219         in(x,y,u);
220         cnt+=25;
221         dfs2(x-5,y,0);
222         return;
223     }
224     if(op==2&&x-5==1)
225     {
226         in(x,y,d);
227         cnt+=25;
228         dfs2(x+5,y,1);
229     }
230     if(op==0&&y+4==n&&x-5==1)
231     {
232         in(x,y,u);
233         cnt+=25;
234         dfs2(x-5,y,0);
235         return;
236     }
237     if(op==0&&x-5==1)
238     {
239         in(x,y,r);
240         cnt+=25;
241         dfs2(x,y+5,2);
242         return;
243     }
244     if(op==0&&y+4==n&&x==1)
245     {
246         in(x,y,l);
247         cnt+=25;
248         dfs2(x,y-5,3);
249         return;
250     }
251     if(op==1)
252     {
253         in(x,y,d);
254         cnt+=25;
255         dfs2(x+5,y,1);
256         return;
257     }
258     if(op==0)
259     {
260         in(x,y,u);
261         cnt+=25;
262         dfs2(x-5,y,0);
263         return;
264     }
265 
266     if(op==3)
267     {
268         in(x,y,l);
269         cnt+=25;
270         if(x-5!=1) dfs2(x,y-5,3);
271         return;
272     }
273 }
274 int main()
275 {
276     //freopen("t.out","w",stdout);
277     n=rd();//printf("%d\n",n);
278     if(n==5)
279     {
280         for(int i=0;i<5;i++)
281         {
282             for(int j=0;j<5;j++)
283                 printf("%d ",st[i][j]);
284             puts("");
285         }
286         return 0;
287     }
288     if(n&1) dfs1(1,1,9);
289     else dfs2(1,1,9);
290     for(int i=1;i<=5;i++)
291         for(int j=1;j<=5;j++)
292             if(a[i][j]>=7) a[i][j]+=cnt-6;
293     for(int i=1;i<=n;i++)
294     {
295         for(int j=1;j<=n;j++)
296             printf("%d ",a[i][j]);
297         puts("");
298     }
299 }
300 /*
301 g++ -std=c++11 1.cpp -o 1
302 ./1
303 25
304 g++ 4.cpp -o 4
305 ./4
306 
307 */