srm 550

发表于   |   分类于   |  

300

Description

有个机器人，从某一点出发，他只有碰到地形边缘或者碰到走过的点时才会改变运动方向，然后接着走，现在给出他的运动轨迹，判断他的运动是否合法，如果合法的话，那么整个地形的最小面积是多少。每次走的步数$\le 50$

Solution

先确定最大的最小的$x,y$,然后进行验证，如果走到重复的地方或者不应该转弯时转弯则不合法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
const int N = 205;
bool vis[N][N];
struct RotatingBot {
    int minArea(vector <int> moves) {
        int n = moves.size();
        int x = 100, y = 100;
        int mxx = 100, mxy = 100, mnx = 100, mny = 100;
        for (int i = 0; i < n; ++i) {
            int dir = i % 4;
            int tx = x + dx[dir] * moves[i];
            int ty = y + dy[dir] * moves[i];
            mxx = max(mxx, tx), mnx = min(mnx, tx);
            mxy = max(mxy, ty), mny = min(mny, ty);
            x = tx, y = ty;
        }
        x = 100, y = 100;
        vis[x][y] = 1;
        if (mxx > 151 || mxy > 151 || mnx < 49|| mxy < 49)  return -1;
        for (int i = 0; i <= 151; ++i) {
            vis[i][mxy + 1] = vis[i][mny - 1] = 1;
            vis[mxx + 1][i] = vis[mnx - 1][i] = 1;
        }
        for (int i = 0; i < n; ++i) {
            int dir = i % 4;
            for (int j = 0; j < moves[i]; ++j) {
                int tx = x + dx[dir];
                int ty = y + dy[dir];
                if (vis[tx][ty])    return -1;
                vis[tx][ty] = 1;
                x = tx, y = ty;
            }
            if (i != n - 1 && !vis[x + dx[dir]][y + dy[dir]])   return -1;
        }
        return (mxx - mnx + 1) * (mxy - mny + 1);
    }
};

500

Description

两个人在一个无限大的格子里轮流涂红蓝两色，第一个人先在$(0,0)$涂红，然后接下来的每一轮，对于所有的点$(x,y)$，如果$(x-1,y-1)$和$(x-2,y)$一个有另一个人的颜色，一个为空，那么就把这个点涂成自己的颜色，问经过$t$轮之后，某个区域的染色情况。

Solution

将前几轮的情况手画一下，是下图这个样子的。。

容易发现只有在$y\le x$这些格子才会被染色，然后发现按$y=-x+b$来看，奇数的没有被染色，偶数的有被染色的。且非常类似杨辉三角，其实杨辉三角奇数项才会被染色。这里有个神奇的结论$c[n][m]为奇数时当且仅当(n \& m) == m$，于是就做完了QvQ

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>//conclusion
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct CheckerExpansion {
    vector <string> resultAfter(long long t, long long x0, long long y0, int w, int h) {
        vector<string> ans;
        for (int i = 0; i < h; ++i) {
            string s = "";
            for (int j = 0; j < w; ++j) {
                LL x = x0 + j;
                LL y = y0 + h - i - 1;
                if (y > x) {
                    s += ".";
                    continue;
                }
                if ((x + y) % 2 == 0) {
                    LL n = (x + y) / 2;
                    LL m = abs(x - n);
                    if (n >= t) s += ".";
                    else if ((n & m) == m) {    //amazing 
                        if (n & 1)  s += "B";
                        else s += "A";
                    }
                    else s += ".";
                }
                else s += ".";
            }
            ans.pb(s);
        }
        return ans;
    }
};