24牛客多校第一场

牛客多校第一场

按过题人数顺序

C.Sum of Suffix Sums

• 题意: 定义 $suf_i = \sum_i^n a_i $
• q个操作每次给出 t, v 代表每次从序列中删除后面t个后，加入一个v, 每次操作后输出 $\sum_1^{size} suf_i $

签到题，因为初始为空，且不会删除空序列，每次只加入一个数，模拟时间复杂度为O (q), 关键在于取模

int main()
{
	int q; cin >> q;
    vector<ll> a;
    ll res = 0;
    while(q --) {
        ll t, v; cin >> t >> v;
        while(t --) {
            ll tmp = 1ll * a.size() * a.back() % mod;
            res = (res - tmp % mod + mod) % mod;
            a.pop_back();
        }
        a.push_back(v);
        ll tmp = 1ll * a.size() * a.back() % mod;
        res = (res + tmp) % mod;       
        cout << res << endl;
    }
    
	return 0;
}

H.World Finals

• 题意：两场比赛都给出了每场的参赛队伍名称，过题数，罚时，如果同一个参赛队伍这两场比赛全参加了那么可以任意分配两场都参加了的队伍的比赛场次的选择，问lzr010506最高可能的排名是多少?

也是签到题，分别计算出每场lzr010506在只参加某一场的队伍中的排名，因为参加两场的可以随便选择，取min就是答案

struct Info {
    string s;
    int t, f;
    bool operator < (const Info& _) const {
        if(t == _.t) return f < _.f;
        return t > _.t;
    }
};
int main()
{
	int n, m; cin >> n;
    map<string, int> mp1, mp2;
    vector<Info> comp1(n);
    for(auto &[s, t, f] : comp1) {
        cin >> s >> t >> f;
        mp1[s] ++;
    }
    cin >> m;
    vector<Info> comp2(m);
    for(auto &[s, t, f] : comp2) {
        cin >> s >> t >> f;
        mp2[s] ++;
    }
    sort(comp1.begin(), comp1.end());
    sort(comp2.begin(), comp2.end());
    int rk1 = 1, rk2 = 1;
    for(auto &[s, t, f] : comp1) {
        if(s == "lzr010506") break;
        if(mp2.find(s) == mp2.end()) rk1 ++;
    }
    for(auto &[s, t, f] : comp2) {
        if(s == "lzr010506") break;
        if(mp1.find(s) == mp1.end()) rk2 ++;
    }
    cout << min(rk1, rk2) << endl;
	return 0;
}

A.A Bit Common

• 题意：求有多少长为 n 的元素是 [0, $ 2^m $) 的整数序列满足存在一个非空子序列的 AND 和是 1 答案对输入的正整数 q 取模
• 1 ≤ n, m ≤ 5000, 1 ≤ q ≤ $10^9$

数据范围提示应该是个$n^2$的做法或者$n*m$,

I.Mirror Maze

• 题意：有一个 n × m 的矩形镜子迷宫，镜子有 “\, /, -, |” 四种，每种镜子有特定的光线反射方向，注意直接通过镜子的情况不算被反射。
• 有 q 个询问，每个询问给定一个点光源 (x, y, dir)，表示在 (x, y) 位置向dir 方向发射一束光线，问经过足够的时间之后，这束光线被多少个不
  同的镜子反射过。
• $ 1 ≤ n, m ≤ 1000, 1 ≤ q ≤ 10^5 $

赛时当模拟写的，刚开始想的图论，发现建图能力不够，后来转向记忆化，能造的样例都能过，赛后只过了6%，还是存在大问题

因为是镜子，所以可以一直反射，如果不出界，最终会形成一个环，否则会形成一个链到外界。逆着看，就是从外面射进来得一束光，预处理最外层射进来的每一束光，处理完剩下的点一定在某个环中，再处理这个所在的环。所有处理过的点都标记一下，防止多次遍历，点在insert前要判断会不会被反射回来

用set维护链。用一个数组存下来路径，能避免传参过多导致记忆化不好处理的麻烦，更新答案因为是记忆化归的过程，要逆着边更新边处理

同样用set也可以维护环，但是归的过程要把路径上的所有点更新，即先处理完数据再更新答案

struct node {
    int x, y, d;
    node(int x, int y, int d) : x(x), y(y), d(d) {}
};
char g[N][N];
map<string, int> mp;
int st[N][N][4], res[N][N][4];
int n, m, q;
vector<node> pt;
bool ref(int x, int y, int dir) {
    char c = g[x][y];
    if(c == '\\' || c == '/') return true;
    if(c == '-' && dir <= 1) return true;
    if(c == '|' && dir >= 2) return true;
    return false;
}
void dfs(int x, int y, int dir) {
    if(x < 1 || x > n || y < 1 || y > m) return ;
    if(st[x][y][dir]) return ;
    st[x][y][dir] = 1;
    pt.push_back((node){x, y, dir});
    char c = g[x][y];
    if(c == '-') {
        if(dir == 0) dfs(x + 1, y, 1);
        else if(dir == 1) dfs(x - 1, y, 0);
        else if(dir == 2) dfs(x, y -1, 2);
        else dfs(x, y + 1, 3);
    } else if(c == '|') {
        if(dir == 0) dfs(x - 1, y, 0);
        else if(dir == 1) dfs(x + 1, y, 1);
        else if(dir == 2) dfs(x, y + 1, 3);
        else dfs(x, y - 1, 2);
    } else if(c == '\\') {
        if(dir == 0) dfs(x, y - 1, 2);
        else if(dir == 1) dfs(x, y + 1, 3);
        else if(dir == 2) dfs(x - 1, y, 0);
        else dfs(x + 1, y, 1);
    } else if(c == '/') {
        if(dir == 0) dfs(x, y + 1, 3);
        else if(dir == 1) dfs(x, y - 1, 2);
        else if(dir == 2) dfs(x + 1, y, 1);
        else dfs(x - 1, y, 0);
    }
}
void solve1(int x, int y, int dir) {//处理链，倒序判断，避免传参导致信息不好维护
    pt.clear();
    dfs(x, y, dir);
    reverse(pt.begin(), pt.end());
    set<PII> s;
    for(auto &[x, y, d] : pt) {
        if(ref(x, y, d)) {
            s.insert({x, y});
        }
        res[x][y][d] = s.size();
    }
}
void solve2(int x, int y, int dir) {//处理环, 环是循环，上面每个方向的2点的答案都一样
    pt.clear();
    dfs(x, y, dir);
    reverse(pt.begin(), pt.end());
    set<PII> s;
    for(auto &[x, y, d] : pt) {
        if(ref(x, y, d)) {
            s.insert({x, y});
        }
    }
    for(auto &[x, y, d] : pt) {
        res[x][y][d] = s.size();
    }
}
int main()
{
	cin >> n >> m;
    for(int i = 1; i <= n ;i ++) {
        cin >> g[i] + 1;
    }
    for(int i = 1; i <= n; i ++) {
        solve1(i, 1, 3);
        solve1(i, m, 2);
    }
    for(int j = 1; j <= m; j ++) {
        solve1(1, j, 1);
        solve1(n, j, 0);
    }
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            for(int k = 0; k < 4; k ++) {
                if(!st[i][j][k]) {
                    solve2(i, j, k);
                }
            }
        }
    }
    mp["above"] = 0;
    mp["below"] = 1;
    mp["left"] = 2;
    mp["right"] = 3;
    cin >> q;
    while(q --) {
        int x, y; string s; cin >> x >> y >> s;
        int tmp = mp[s];
        if(tmp == 0) x--;
        else if(tmp == 1) x ++;
        else if(tmp == 2) y --;
        else y ++;
        cout << res[x][y][tmp] << endl;
    }
	return 0;
}