这种比赛，看得和平时的SRM一样，我是来打酱油的。本来是5.1晚12点做的，可悲剧的是TC服务器不知道出了什么事，跟上回一次做SRM似的，Compile不了，Submit不了，郁闷坏了，老期待呢，结果却没做成，不过可能也是好事，250题做的比较慢，拿到250，直接就去看Sample了，可是题目自我感觉比较拗口，DNA链要放过来匹配。错过了早提交的机会，结果就到了提交高峰期了，然后TC服务器就悲剧了，一直悲剧了几个小时，真的是。
幸运的是24小时后重赛。重赛这场RP好些，250吸取教训，慢慢看题，用冒泡的方法，按不同的比较方法跑两趟就行了。然后就卡在了500的题了。对这题的反应比较慢，难道是被Simulation给吓到了？
题目大意是不超过10个操作，重复2*10^9次，操作是UDLR，当然不能全部模拟，刚开始以为会有什么公式的东西，也发现每次的操作只要抓住起点和终点，然后接下来的轨迹就沿着这条线了，如果要公式统计面积的话，会有交集部分，如果考虑到容斥原理的话，因为操作数最多就10个，所以最多也就10个块能产生交集（除去起点终点重合的情况），这也就以为这times那么大，里面有很多无用的信息，然后这个时候发现Room里面提交早的人很早就提交了，所以想必思路应该比较直接，不会难，然后就手动模拟了几下，发下模拟几下后形状会趋于稳定，于是就打算模拟下去直到稳定，也就是说增加的数目和上次的一样。很可能第一次的稳定不是真的稳定，最后一个Test也说明了这点，于是我又加了一条，当稳定的次数超过一定数目时，就停止模拟。这个次数其实6、7次应该就足够没问题的，后来还是有点担心，调到了10。
这样250、500就顺利提交了，然后没时间看1000的了，到Cha的时候有个小插曲，我打开一个代码，发现只有头，没有类，就直接Cha，然后囧的是，类就在下面，我没看到。。晕。。。后来有阴影不敢Cha了。幸运的是最终的Test也显示出这些大多数没问题。最后的Rank 400+，资格赛每场进600个，顺利晋级，打酱油成功，吼吼~
1 #include < iostream > 2 #include < string > 3 #include < string .h > 4 #include < vector > 5 #include < math.h > 6 #include < map > 7 #include < set > 8 #include < time.h > 9 #include < algorithm > 10 using namespace std; 11 12 const int MAX = 1005 ; 13 const int HALF = 500 ; 14 int mm[MAX][MAX]; 15 16 void getD( int x, int y, int & dx, int & dy, char t) 17 { 18 if (t == ' U ' ) dx = x - 1 , dy = y; 19 if (t == ' D ' ) dx = x + 1 , dy = y; 20 if (t == ' L ' ) dx = x, dy = y - 1 ; 21 if (t == ' R ' ) dx = x, dy = y + 1 ; 22 } 23 24 int go( string program, int times) 25 { 26 int dd = 0 ; 27 int res = 1 ; 28 int tt = 0 ; 29 int x = 0 + HALF, y = 0 + HALF; 30 memset(mm, 0 , sizeof (mm)); 31 mm[HALF][HALF] = 1 ; 32 for ( int i = 0 ; i < times; i ++ ) 33 { 34 int cnt = 0 ; 35 for ( int j = 0 ; j < program.size(); j ++ ) 36 { 37 int dx, dy; 38 getD(x, y, dx, dy, program[j]); 39 if (mm[dx][dy] == 0 ) 40 { 41 mm[dx][dy] = 1 ; 42 cnt ++ ; 43 } 44 x = dx, y = dy; 45 } 46 if (cnt != dd) 47 { 48 dd = cnt; 49 res += dd; 50 } 51 else 52 { 53 if (tt > 10 ) 54 { 55 res += (times - i) * dd; 56 return res; 57 } 58 else 59 { 60 res += dd; 61 tt ++ ; 62 } 63 } 64 } 65 return res; 66 } 67 68 class RobotSimulation 69 { 70 public : 71 int cellsVisited( string program, int times) 72 { 73 return go(program, times); 74 } 75 };
转载于:https://www.cnblogs.com/litstrong/archive/2010/05/03/1726320.html
