C. Sum of Suffix Sums (后缀和/思维)

时间复杂度 ：$O(q)$

题意

    起始有一个空的数组，现在对该数组进行$q$ 次操作：

  • 给定两个非负整数 $t$ 和 $v$ ，从末尾移除 $t$ 个元素并将元素 $v$ 加到末尾。保证每次元素数量不小于 $t$

    每次操作后输出每个索引的后缀和的总和，由于答案可能会很大，对答案进行 $1000000007$ 取模.

数据范围

  • $1 \le q \le 5 \times 10^5$
  • $0 \le v \le 10^9$

思路

    由于每次操作输出后缀总和，不妨直接从答案出发；设 $sum[i]$ 为前 $i$ 个元素的后缀总和，当末尾添加一个元素（ 第 $i+1 $ 个元素 ）$ v$ 时，其对后缀的贡献为 $v \times i$ ，即$sum[i+1]=sum[i]+v*i$ ; 当取出 $t$ 个元素时，类似于栈的 $pop$ 操作,直接将元素数量减去 $t$ 即可 .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
const i64 p = 1e9 + 7;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int q, top = 0;
    cin >> q;
    vector<i64> sum(q + 5);
    for (int i = 1; i <= q;i++){
        int t, v;
        cin >> t >> v;
        top -= t;
        top++;
        sum[top] = (sum[top - 1] % p + (top * v) % p) % p;
        cout << sum[top] << endl;
    }
    return 0;
}

H. World Finals (模拟)

时间复杂度：$O(Max(m,n \log n))$

题意

    共有两场比赛可供队伍参加，分别给定 $n$ 和 $m$ ，表示两场比赛可能参赛的队伍数量，每支队伍有对应的答题数 $p$ 和罚时 $t$ (按照 $icpc$ 赛制进行排序)，保证不会出现答题数和罚时完全相同的队伍。可能出现一支队伍有两场比赛的参与权，但每支队伍只能参加一场比赛，其中队伍名 $lzr010506$ 有两场的参赛可能。求队伍 $lzr010506$ 可能取得的最高排名 .

数据范围

  • $1 \le n,m \le 10^5$
  • $1 \le p,t \le 10^9$

思路

​    简单模拟题，要使得指定队伍排名最高，则其余拥有两场比赛参赛权的队伍应当去参加另一场比赛.

​    对所有队伍根据规则进行结构体排序，再记录拥有两场比赛参赛权的队伍，依次枚举其在各自比赛的位次，当遇到特殊队伍则跳过，两种比赛的最高排名取最大值即可.

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
struct node{
    string name;
    int p, t;
    bool operator<(const node x)const{
        if(p!=x.p)
            return p > x.p;
        else
            return t < x.t;
    }
} team1[100010], team2[100010];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, m;
    map<string, int> cnt;
    cin >> n;
    for (int i = 1; i <= n;i++){
        cin >> team1[i].name >> team1[i].p >> team1[i].t;
        cnt[team1[i].name]++;
    }
    sort(team1 + 1, team1 + n + 1);
    cin >> m;
    for (int i = 1; i <= m; i++){
        cin >> team2[i].name >> team2[i].p >> team2[i].t;
        cnt[team2[i].name]++;
    }
    sort(team2 + 1, team2 + m + 1);
    int ans = 1e6;
    int tot = 0;
    for (int i = 1; i <= n;i++){
        if(team1[i].name=="lzr010506"){
            tot++;
            break;
        }
        if(cnt[team1[i].name]==2)
            continue;
        else 
            tot++;
    }
    ans = min(ans, tot);
    tot = 0;
    for (int i = 1; i <= m; i++){
        if (team2[i].name == "lzr010506"){
            tot++;
            break;
        }
        if (cnt[team2[i].name] == 2)
            continue;
        else
            tot++;
    }
    ans = min(ans, tot);
    cout << ans << endl;
    /*for (int i = 1; i <= n;i++)
        cout << team1[i].name << ' ' << team1[i].p << ' ' << team1[i].t << endl;
    for (int i = 1; i <= m; i++)
        cout << team2[i].name << ' ' << team2[i].p << ' ' << team2[i].t << endl;*/
    return 0;
}