2022-9-2总结

低仿机器人(robo)

一个纯模拟题，没什么好说的。

有一些坑点需要注意:

1. 不要出现 END 或 ERROR 后就退出循环，要把当前数据点的输入全读取完再跑下一个数据点。

2. 指令中可能存在小数，判一下是否有小数点就行了。

3. 机器人不会执行发生 ERROR 的那条指令，需要输出发出这条指令前的状态.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("robo.in", "r", stdin);
        freopen("robo.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

namespace robot {
    int kill; // 打掉的靶子数

    int lim; // 弹匣容量上限
    stack<int> magazine; // 弹匣
    
    int ammo[2]; // 0->小水晶弹 1->大水晶弹
    
    int robot_way; // 机器人朝向  0↗ 1↘ 2↖ 3↙
    int gun_way; // 炮口朝向   0↑ 1← 2↓ 3→
    
    int posx, posy; // 位置

    void reset(); // 重置
    void shoot(); // 射击
    void change_gun(int d); // 转炮台
    bool go_ahead(int step); // 前进
    void change_robot(int d); // 转机器人
    bool load_ammo(int type); // 填充弹匣
}
using namespace robot;


int n, m, k;
int mp[205][205]; // 地图: 0空地, 1障碍, 2靶子, 3水池
int hit[205][205]; // 小水晶弹击中次数

void solve();
void clear();

int main()
{
    int t; cin >> t;
    while(t --> 0)
    reset(), solve();
    return 0;
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        cin >> mp[i][j];
    for(int i = 0; i <= n; i++)
        mp[i][0] = mp[i][m+1] = 1;
    for(int j = 0; j <= m; j++)
        mp[0][j] = mp[n+1][j] = 1;
    cin >> posx >> posy; posx++, posy++;
    cin >> lim;
    cin >> ammo[1] >> ammo[0];
    gun_way = robot_way = 0;
    
    cin >> k;
    
    bool haveend = false;
    bool flag = false;
    string s, opt; int x;
    getline(cin, s);
    for(int i = 1; i <= k; i++)
    {
        getline(cin, s);
        
        int opttot = 0;
        opt.clear();
        opt += s[0]; opt += s[1];
        if(s.size() > 2 and s[2] == 'D') opt += s[2];
        for(int i = 1; i < s.size(); i++)
        {
            if(s[i-1] == ' ' and s[i] != ' ')
                opttot++;
            if(s[i] == '.') flag = true;
        }
        x = 0;
        for(int i = opt.size()+1; i < s.size(); i++)
        {
            if(!isdigit(s[i])) break;
            x = x*10 + s[i]-'0';
        }
        
        if(haveend or flag) continue;
        
        if(opt == "FT")
        {
            if(opttot != 1) { flag = true; continue; }
            if(x != 0 and x != 1) { flag = true; continue; }
            change_gun(x);
        }
        else if(opt == "FF")
        {
            if(opttot != 1) { flag = true; continue; }
            if(x != 0 and x != 1) { flag = true; continue; }
            if(!load_ammo(x)) { flag = true; continue; }
        }
        else if(opt == "FE")
        {
            if(opttot != 0) { flag = true; continue; }
            shoot();
        }
        else if(opt == "WT")
        {
            if(opttot != 1) { flag = true; continue; }
            if(x != 0 and x != 1) { flag = true; continue; }
            change_robot(x);
        }
        else if(opt == "WG")
        {
            if(opttot != 1) { flag = true; continue; }
            if(!go_ahead(x)) { flag = true; continue; }
        }
        else if(opt == "END")
        {
            if(opttot != 0) { flag = true; continue; }
            haveend = true;
        }
    }
    
    // line 1
    if(haveend) cout << "Complete" << endl;
    else cout << "ERROR" << endl;
    
    // line 2
    cout << posx-1 << " " << posy-1 << endl;
    
    // line 3
    cout << kill << endl;
    
    // line 4
    cout << gun_way << " " << robot_way << " "
        << ammo[1] << " " << ammo[0] << endl; 
}

namespace robot {
    bool load_ammo(int type)
    {
        if(ammo[type] == 0) return true;
        if(magazine.size() == lim) return false;
        magazine.push(type);
        ammo[type]--;
        return true;
    }
    void shoot()
    {
        if(magazine.empty()) return;
        int bullet = magazine.top();
        magazine.pop();
        int x = posx, y = posy;
        while(mp[x][y] == 0 or mp[x][y] == 3)
            x += dx[gun_way], y += dy[gun_way];
        if(mp[x][y] != 2) return;
        if(bullet == 1)
            mp[x][y] = 0, kill++;
        else if(++hit[x][y] >= 2)
            mp[x][y] = 0, kill++;
    }
    bool go_ahead(int step)
    {
        int x = posx, y = posy;
        for(int i = 1; i <= step; i++)
        {
            x += dx[robot_way], y += dy[robot_way];
            if(mp[x][y] != 0) return false;
        }
        posx = x, posy = y;
        return true;
    }
    void change_robot(int d)
    {
        if(d == 0)
        {
            robot_way += 1;
            if(robot_way > 3)
                robot_way = 0;
        }
        else
        {
            robot_way -= 1;
            if(robot_way < 0)
                robot_way = 3;
        }
    }
    void change_gun(int d)
    {
        if(d == 0)
        {
            gun_way += 1;
            if(gun_way > 3)
                gun_way = 0;
        }
        else
        {
            gun_way -= 1;
            if(gun_way < 0)
                gun_way = 3;
        }
    }
    void reset(){

        memset(mp, 0, sizeof(mp));
        memset(hit, 0, sizeof(hit));
        kill = 0;
        ammo[0] = ammo[1] = 0;
        magazine = stack<int>();
        lim = 0;
        robot_way = gun_way = 0;
        posx = posy = 1;

    }
}

迷路的刺豚(expand)

因为 $p \le 15$, 可以考虑状压DP。

设 $f_{i,j}$ 表示 经过的菜店集合为 $i$，当前位置在第 $j$ 个菜店时的最短路，$g_{i,j}$ 表示最大体格之和。

转移非常好写，只需要预处理出一些东西就行了。

首先需要预处理出在每个格子的最大体格，可以将障碍和边界看作起点，进行多起点的八连通bfs即可。

然后需要处理菜店之间两两的最短路和最大体格之和，可以跑 $p$ 遍 Dijkstra 处理出来。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("expand.in", "r", stdin);
        freopen("expand.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

const int P = 25;
const int N = 305;
const int dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, -1, 1};

struct node {
    int x, y;
    int dis, sum;
};
bool operator < (node a, node b)
{
    if(a.dis != b.dis)
        return a.dis > b.dis;
    else
        return a.sum < b.sum;
}

int n, m, s;
int sx, sy, p;
int mp[N][N];
int siz[N][N];
int dis[P][P];
int sum[P][P];
int qry[N][N];
bool vis[N][N];
int f[1<<16][16]; // 最短路
int g[1<<16][16]; // 最大和
int px[P], py[P];

void get_size();
void dijkstra(int sx, int sy, int id);

#define pos(i) (1<<(i-1))
#define lowbit(i) (i&-i)

int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        scanf("%d", &mp[i][j]);
    scanf("%d%d%d", &sx, &sy, &p);
    sx++, sy++;
    
    for(int i = 1; i <= p; i++)
    {
        scanf("%d%d", &px[i], &py[i]);
        px[i]++, py[i]++;
        qry[px[i]][py[i]] = i;
    }
    
    get_size();

    for(int i = 1; i <= p; i++)
        dijkstra(px[i], py[i], i);
    dijkstra(sx, sy, 0);
    
    memset(f, 0x3f, sizeof(f));
    memset(g, -0x3f, sizeof(g));
    
    for(int i = 1; i <= p; i++)
    {
        f[pos(i)][i] = dis[0][i];
        g[pos(i)][i] = sum[0][i];
    }
    
    for(int i = 1; i < (1<<p); i++)
    {
        if(i == lowbit(i)) continue;
        for(int j = 1; j <= p; j++)
        {
            if(!(i&pos(j))) continue;
            int k = i-pos(j);
            for(int s = 1; s <= p; s++)
            {
                if(!(k&pos(s))) continue;
                if(f[i][j] > f[k][s]+dis[s][j])
                {
                    f[i][j] = f[k][s]+dis[s][j];
                    g[i][j] = g[k][s]+sum[s][j];
                }
                else if(f[i][j] == f[k][s]+dis[s][j])
                {
                    g[i][j] = max(g[i][j], g[k][s]+sum[s][j]);
                }
            }
            
        }
    }
    
    int id = 0;
    for(int i = 1; i <= p; i++)
        if(f[(1<<p)-1][i] < f[(1<<p)-1][id]) id = i;
    
    printf("%d %d", f[(1<<p)-1][id], g[(1<<p)-1][id]
    +siz[sx][sy]
    );
}


void get_size()
{
    queue<node> q;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
    {
        siz[i][j] = s;
        if(mp[i][j])
        {
            q.push({i, j, -1});
            siz[i][j] = -1;
        }
    }
    for(int i = 1; i <= n; i++)
        q.push({i, 0, -1}), q.push({i, m+1, -1});
    for(int j = 1; j <= m; j++)
        q.push({0, j, -1}), q.push({n+1, j, -1});
    while(!q.empty())
    {
        node a = q.front(); q.pop();
        for(int k = 0; k < 8; k++)
        {
            int nx = a.x+dx[k];
            int ny = a.y+dy[k];
            if(nx < 1 or nx > n or ny < 1 or ny > m) continue;
            if(mp[nx][ny] == 1) continue;
            if(siz[nx][ny] > a.dis+1)
            {
                siz[nx][ny] = a.dis+1;
                q.push({nx, ny, a.dis+1});
            }
        }
    }
}
void dijkstra(int sx, int sy, int id)
{
    memset(vis, 0, sizeof(vis));
    
    priority_queue<node> q;
    q.push({sx, sy, 0, 0});
    while(!q.empty())
    {
        node a = q.top(); q.pop();
        if(vis[a.x][a.y]) continue;
        vis[a.x][a.y] = true;
        if(qry[a.x][a.y] != 0)
        {
            int t = qry[a.x][a.y];
            dis[id][t] = a.dis;
            sum[id][t] = a.sum;
        }
        for(int k = 0; k < 4; k++)
        {
            int nx = a.x+dx[k];
            int ny = a.y+dy[k];
            if(nx < 1 or nx > n or ny < 1 or ny > m) continue;
            if(mp[nx][ny] == 1) continue;
            q.push({nx, ny, a.dis+1, a.sum+siz[nx][ny]});
        }
    }
}

生日(birthday)

又是一道结论题：当区间长度 $len \ge 14$ 时答案一定为 Yes。

证明: 对于一个元素数量为 $len$ 的集合，选取子集的方案数为 $2^{len}$，而选取元素总和的值域为 $[1,v*len]$，所以当 $2^{len} \ge v*len$ 时，一定有解，此时 $len \ge 14$。

对于 $len < 14$ 的询问，可以折半搜索解决，每个数的系数可能为 $1,-1,0$，当总和为 $0$ 时代表有解。

有一个小技巧: 每次清空桶时可以不用 memset ，可以将桶的类型改为 int, 然后记录一个时间戳，就可以做到 $O(1)$ 清空桶了。

关于修改操作，因为是模 $v$ 意义下，肯定存在循环，所以我们可以倍增搞出每个数进行 $2^i$ 次操作后的值，因为只需要计算 $len \le 14$ 时的答案，所以每次暴力把数都算出来就行了，区间修改可以写个线段树来维护每个数修改了多少次。

#include <cstdio>
#include <iostream>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("birthday.in", "r", stdin);
        freopen("birthday.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

const int N = 100005;

namespace tr {
    struct node {
        int l, r, lz;
    } a[N*4];
    int lim;
    void build(int i = 1, int l = 1, int r = lim);
    void add(int ql, int qr, int i = 1);
    int get(int pos, int i = 1);
}

void prework();
bool check(int l, int r);
void dfs(int pos, int sum, bool choose, int l, int r, int type);

int n, m, v;
int a[N];
int f[N][20];
int dft;
int t1[20005];
int t2[20005];

int main()
{
    cin >> n >> m >> v;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    tr::lim = n;
    tr::build();
    prework();
    
    int opt, l, r;
    for(int i = 1; i <= m; i++)
    {
        cin >> opt >> l >> r;
        if(opt == 1)
        {
            if(r-l+1 >= 14)
                cout << "Yes\n";
            else if(check(l, r))
                cout << "Yes\n";
            else
                cout << "No\n";
        }
        else if(opt == 2)
            tr::add(l, r);
    }
}

void prework()
{
    for(int i = 1; i < v; i++)
        f[i][0] = i*i*i%v;
    for(int k = 1; k < 20; k++)
        for(int i = 1; i < v; i++)
            f[i][k] = f[f[i][k-1]][k-1];
}

bool flag;
bool check(int l, int r)
{
    for(int i = l; i <= r; i++)
    {
        int x = tr::get(i);
        for(int k = 0; k < 20; k++)
            if(x&(1<<k)) a[i] = f[a[i]][k];
    }
    flag = false; dft++;
    int mid = (l+r)>>1;
    dfs(l,     0, false, l,    mid, 0);
    dfs(mid+1, 0, false, mid+1,  r, 1);
    return flag;
}
void dfs(int pos, int sum, bool choose, int l, int r, int type)
{
    if(pos > r)
    {
        if(!choose) return void();
        
        if(sum == 0) flag = true;
        if(type == 0)
        {
            if(sum > 0) t1[sum] = dft;
            if(sum < 0) t2[-sum] = dft;
        }
        else
        {
            if(sum > 0) flag |= (t2[sum]==dft);
            if(sum < 0) flag |= (t1[-sum]==dft);
        }
        return void();
    }
    
    dfs(pos+1, sum+a[pos]+1, true, l, r, type);
    dfs(pos+1, sum,        choose, l, r, type);
    dfs(pos+1, sum-a[pos]-1, true, l, r, type);
}

namespace tr {
    #define ls (i<<1)
    #define rs (i<<1|1)
    void pushdown(int i)
    {
        a[ls].lz += a[i].lz;
        a[rs].lz += a[i].lz;
        a[i].lz = 0;
    }
    void build(int i, int l, int r)
    {
        a[i].l = l, a[i].r = r;
        if(l == r) return void();
        int mid = (l+r)>>1;
        build(ls, l, mid);
        build(rs, mid+1, r);
    }
    void add(int ql, int qr, int i)
    {
        if(ql <= a[i].l and a[i].r <= qr)
            return void(a[i].lz += 1);
        pushdown(i);
        if(ql <= a[ls].r) add(ql, qr, ls);
        if(qr >= a[rs].l) add(ql, qr, rs);
    }
    int get(int pos, int i)
    {
        if(a[i].l == a[i].r)
        {
            int x = a[i].lz;
            a[i].lz = 0; return x;
        }
        pushdown(i);
        if(pos <= a[ls].r) return get(pos, ls);
        if(pos >= a[rs].l) return get(pos, rs);
        return 114514;
    }
}