Lut本科回忆录

呃呃这场签到一时半会没写出来就去睡觉了，睡醒已经结束，然后一题没开
更新至L,F,A,J…
(好无聊好无聊好无聊呜呜呜7.30)

题L

题意：给定一个 $n * m$ 排布的灯，有 $q$ 次操作，每次操作可以 $打开/关闭$ 某具体 $行/列$ , 问最后有多少灯是打开的（$1<=n,m,q<=1e6$）。

解：由于后面的操作会对当前操作有影响，所以不妨我们对操作倒着看，这时候第一次打开某一行或列必然是增加答案的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int row[N], col[N];
struct S{
    string x1, x2; int x;
}s[N];
int main(){
    int n, m, k; cin >> n >> m >> k;
    ll ans = 0;
    for(int i = 1; i <= k; ++ i){
        cin >> s[i].x1 >> s[i].x >> s[i].x2;
    }
    for(int i = k; i >= 1; -- i){
        auto t = s[i];
        if(t.x1 == "row"){
            if(row[t.x] == 0){
                row[t.x] = 1;
                if(t.x2 == "on") ans += m;
                n --;
            }
        }else {
            if(col[t.x] == 0){
                col[t.x] = 1;
                if(t.x2 == "on") ans += n;;
                m --;
            }
        }
    }
    cout << ans;
}

题F

题意：$n$ 个候选人每人都有一个 $a_i (political$ $tendencies)$，有 $n - 1$ 轮投票，每轮投票中未出局的候选人可以给一个人投票，票数最多者出局，其中对于 $i$ 这个候选人而言，他会投给 $j$ 候选人，当且仅当存在最大的 $|a_i - a_j|$, 如果同时存在了两个相同最大值的$|a_i - a_j|$ ， 那么优先投给$a_j$ 较大的人。问最后剩下来的是几号候选人。

解：由题意可得，每轮出局的必然是剩余候选人中 $a_i$ 值是 $最大/最小$， 那么我们可以对 $a_i$ 排完序后对两端用双指针，将两个指针与中间候选人的 $a_{mid}$ 进行比较。 最终复杂度为 $O(n)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
pair<int, int> p[N];
int main(){
    int n; cin >> n;
    for(int i = 1; i <= n; ++ i){
        int x; cin >> x;
        p[i] = {x, i};
    }
    sort(p + 1, p + 1 + n);
    int l = 1, r = n;
    while(l < r){
        int mid = l + r >> 1;
        if(2 * p[mid].first > p[l].first + p[r].first)
            l ++;
        else 
            r --;
    }
    cout << p[l].second;
}

题A

题意：已知一个消息字符串 $s$, 其加密字符串为 $t+s+t$，其中字符串 $t$ 为识别字符串，用于解码。但对于本题中读取加密字符串是一个个字符读取，当加密字符串 $0101101010$， 已知$t=010$, 其标准的消息字符串 $s=1101$, 但由于读取过程的问题，在计算机读取了加密字符到 $01011010$ 时就会停止并且获得消息字符串 $s=11$ 与需求不符，存在歧义。 题目给定消息字符串 $s$ 的长度和识别字符串 $t$，要求任意构造一个不存在歧义的消息字符串 $s$（$1<=|t|, n<=1000$, 本题中字符串由 $01$ 构成）。

解：由于可以任意构造且字符串的长度很小，而且我们是知道识别字符串 $t$的， 那么首先要使得 $s$中不存在 $t$，我们可以直接假设 $s$ 全为 $0$， 用 $find$ 函数查看是否存在歧义，存在则用全 $1$ 代替。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
void solve(){
    int n, f = 0; string t; cin >> n >> t; string x = t;
    for(int i = 1; i <= n; ++ i) x = x + "0"; x = x + t;
    if(x.find(t, 1) != x.size() - t.size()) f = 1;
    for(int i = 1; i <= n; ++ i) cout << f; cout << '\n';
}
int main(){
    int T; cin >> T;
    while(T --) solve();
}

题J

题意：给定整数 $n$ 和 $m$，要求构造长度为 $n$ 的数组 $a$，其中 $-m<=a_i<=m$, 对任意 $2<=k<=n$，满足连续 $k$ 个元素和 $>=0$，问存在多少种构造情况$(1<=n,m<=5000, 答案模998244252)$

解：用 $dp[i][j]$ 表示前 $i$ 个元素种包含第 $i$ 个元素最小和为 $j$ 的情况数。我们再用一个 $sum[i][j]$ 表示包含第 $i$ 个元素和为 $j$ 的情况数，这样我们对和从大到小枚举，就 $O(n*m)$ 跑过。

#include<iostream>
using namespace std;
const int N = 5010, MOD = 998244353;
int dp[N][N + N], sum[N][N + N];
int main(){
    int n, m; cin >> n >> m;
    for(int i = m; i >= -m; -- i) {
        sum[1][i + N] = 1;
        dp[1][i + N] = dp[1][i + N + 1] + sum[1][i + N];
    }
    for(int i = 2; i <= n; ++ i){
        for(int j = m; j >= -m; -- j){
            if(j >= 0) sum[i][j + N] = dp[i - 1][j + N - m];
            else sum[i][j + N] = dp[i - 1][N - j];
            dp[i][j + N] = (dp[i][j + N + 1] + sum[i][j + N]) % MOD;
        }
    }
    cout << dp[n][N - m];
}