首页 > 代码库 > usaco-4.4-shutter-passed
usaco-4.4-shutter-passed
此题取巧了,Usaco在这题上并没有指明不可以用分析法,而且dfs肯定TLE,所以我们取巧。
先观察样例数据,如果把还没移动的那一步也算上,那么空格的位置为
4 3 5 6 4 2 1 3 5 7 6 4 2 3 5 4 (n=3,样例)
5 4 6 7 5 3 2 4 6 8 9 7 5 3 1 2 4 6 8 7 5 3 4 6 5 (n=4)
我们凭借极其敏锐的眼光发现这组序列为
435 642 1357 642 35 4 (n=3,样例)
5 46 753 2468 97531 2468 753 46 5 (n=4)
即长度为1,2,3,4,...,n,n+1,n,...,4,3,2,1这样的2n+1组等差序列
我们讨论第1~n+1组序列,这些序列满足
*公差的绝对值为2
*奇数组为降序列,偶数组为升序列
*对于第i组(1<=i<=n+1),若为奇数组则首项为n+i,偶数组则首项为n-i+2
对于第n+2~2n+1组,可以由对称性求出。
输出时从第二组开始即可。
把规律总结成这样后,代码应该很好写了吧。
/*ID: qq104801LANG: C++TASK: shuttle*/#include <iostream>#include <fstream>#include <cstring>#include <vector>#include <queue>#include <stack>#include <algorithm>using namespace std;void test(){ freopen("shuttle.in","r",stdin); freopen("shuttle.out","w",stdout); int n,p,s=0,k; cin>>n; p=n+1; for(int i=2;i<=2*n+1;i++) { k=(i<=n+1)?i:2*n+2-i; p+=(k&1)^(i>n+1)?1:-1; s++; cout<<p<<((s%20==0||i==2*n+1) ? ‘\n‘ : ‘ ‘); for(int j=2;j<=k;j++) p+=(k&1)?-2:2,s++, cout<<p<<((s%20)?‘ ‘:‘\n‘); } }int main () { test(); return 0;}
test data:
USACO TrainingGrader Results 14 users onlineBRA/1 CHN/4 IDN/1 IND/1 KOR/1 PER/1 USA/4 VNM/1USER: cn tom [qq104801]TASK: shuttleLANG: C++Compiling...Compile: OKExecuting... Test 1: TEST OK [0.008 secs, 3372 KB] Test 2: TEST OK [0.011 secs, 3372 KB] Test 3: TEST OK [0.011 secs, 3372 KB] Test 4: TEST OK [0.008 secs, 3372 KB] Test 5: TEST OK [0.005 secs, 3372 KB] Test 6: TEST OK [0.008 secs, 3372 KB] Test 7: TEST OK [0.008 secs, 3372 KB] Test 8: TEST OK [0.011 secs, 3372 KB] Test 9: TEST OK [0.008 secs, 3372 KB] Test 10: TEST OK [0.016 secs, 3372 KB]All tests OK.YOUR PROGRAM (‘shuttle‘) WORKED FIRST TIME! That‘s fantastic -- and a rare thing. Please accept these special automated congratulations.Here are the test data inputs:------- test 1 ----1------- test 2 ----3------- test 3 ----4------- test 4 ----5------- test 5 ----7------- test 6 ----8------- test 7 ----9------- test 8 ----10------- test 9 ----11------- test 10 ----12Keep up the good work!Thanks for your submission!
usaco-4.4-shutter-passed
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。