10.3 Morning

Test

T1： Problme

有一个大小为$N\times M$棋盘上有K个小葱分别在第$X[i], Y[i]$点上，面向$D[i]$，战斗力为$F[i]$。其中$D[i]$为${0, 1, 2, 3}$分别表示上下左右。如果下一步将走出棋盘，那么小葱们会花费一秒钟的时间向后转弯，而每一次移动需要花费一秒。如果有一秒几个小葱碰到了一个点上，这几个小葱会打架，然后最后只有战斗力最大的能够存活，其它的小葱不会再移动。数据保证$F[i]$和初始的$X[i],Y[i]$。问$T$秒之后所有的小葱分别在什么位置。

这个题由于数据比较水，所以我们是可以直接暴力的。然后大体思路如下：首先我们要判断这个棋盘的边缘判断。如果不考虑其它因素，那么代码大概如下：

        if(Edge[i].X == 1 && Edge[i].D == 2){
            Edge[i].D = 3 ; continue ;
        }// 左
        else if(Edge[i].X == N && Edge[i].D == 3){
            Edge[i].D = 2 ; continue ;
        }// 右
        else if(Edge[i].Y == 1 && Edge[i].D == 0){
            Edge[i].D = 1 ; continue ;
        }// 上
        else if(Edge[i].Y == N && Edge[i].D == 1){
            Edge[i].D = 0 ; continue ;
        }/ 下

这很简单。然后我们考虑没撞到的情况，是要向前走一步的。这个也很简单。但是我们要考虑到这个打架的问题，那么我们要利用一个二维数组进行记录当前节点有哪根葱占着。假设当前的$X[j], Y[j]$是被谁$U$占着了。注意这里的U是已经移动过的小葱。因为我们对于每一根葱的枚举不可能同时进行，我们在进行枚举的时候虽然有一定顺序，但也不要忘了他们的移动是并列的同步进行。也就是说之前的一个节点$U$移动过之后到达了点$X[j], Y[j]$，然后我们当前枚举到了小葱i，那么我们就要用到$Map[a][b]$表示当前棋盘上的点$(a, b)$是被拿一根葱占着。然后我们就比较$i$的战斗力和$Map[X[j]][Y[j]]$的战斗力。
如果当前点i被干掉了，那么我们记录一下i的死亡位置$Ans$，在这里我们可以使用$STL$中的对数函数$pair<int, int> Ans[MAXN]$来记录横纵坐标。然后设置一个$Flag[i]$ $=$ $0$表示i这个点的存在消失，下一个$T--$的时候进行的枚举以及打架过程便不再对i进行。而如果i赢了，那么$Map[X[j]][Y[j]]$执行同样的操作，然后我们更改$Map[X[j]][Y[j]]$ $=$ $i$就可以了。

T3

令F[i]为从第1个点走到第i个点的方案数。那么F[1] = 1 ；
i的转移方案可以从[1,i]之间的任意一个j点转移过来，那么从j到i的方案数为从i到j的边数也就是$A[j]$ & $A[i]$，然后我们再乘上从1到j的方案数。那么总少可以得出一个DP方程:$F[i] =\sum A_{i}$&$A_{j} * F[j]$
但是这样的时间复杂度大概在$O(N^{2})$左右，并不能过掉所有的数据。
然后可以考虑玄学优化。干到$O(200N)$。