前言

这是蒟蒻 AK 的第一场考试！
让我们恭喜它！

T1 100pts

通过数学计算一下高度即可

#include <iostream>
using namespace std;
const int maxn = 1e5 + 5;

int n, T;
int v[maxn], t[maxn], high[maxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> T;
    for(int i = 1; i <= n; i++) {
        cin >> v[i] >> t[i];
        high[i] = max(T - t[i], 0) * v[i];
    }
    int minHigh = -1, index;
    for(int i = 1; i <= n; i++) {
        if(high[i] > minHigh) {
            minHigh = high[i];
            index = i;
        }
    }
    cout << index << endl;
}

T2 100pts

通过分析题目可知：

• 如果侦测到冰川第一次融化，输出最近一个还没有融化的冰川即可。
• 如果所有冰川均融化则无解
• 如果侦测到冰川不是第一次融化，为了使字典序最小输出 1 即可，前提是冰川 1 已经融化，否则无解。

#include <iostream>
#include <vector>
using namespace std;
#define F "No solution"

int n, m;
char info[1000005];
vector<int> ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    cin >> info;
    int now = 1;
    for(int i = 0; i < m; i++) {
        if(info[i] == 'N') {
            ans.push_back(now++);
        }
        else {
            if(now == 1) {
                cout << F << endl;
                return 0;
            }
            ans.push_back(1);
        }
    }
    if(now > n + 1) {
        cout << F << endl;
        return 0;
    }
    for(int i = 0; i < ans.size(); i++)     {
        cout << ans[i] << " ";
    }
    return 0;
}

T3 100pts

用的 STL 做的，题目涉及到初中数学一次函数

令 $y_1 = k_1x + b_1$，$y_2 = k_2x + b_2$

如果两条直线仅有一个交点，则：

• $k_1 \ne k_2$

若两条直线至少有一个焦点，则：

• $k_1 \ne k_2 || (k_1 = k_2 \& b_1 = b_2)$

起初我本来想用一个二维 map 来记录每一个一次函数，但是我发现这样子进行操作2或操作3太慢了，会TLE

但是通过之前的推论我们知道了进行操作2只需要知道 $k$ 就行了，所以说我们可以拿一个 map 出来存放 $k$ 相同的数量，需要询问的时候直接输出一 $次函数数量总和 - (斜率 = k的一次函数的数量)$

遇到删除就不行了，删除时与给定的一次函数相同的一次函数也会被删除掉，也就是说我们还是需要一个二维 map 来记录每一个一次函数，在删除的时候把除了重合所有斜率相同的一次函数删除即可。

但是这样子还是 TLE 了，卡了一下数据范围就过了。

#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

int n;
map<int, map<int, int> > linesmall;
map<int, int> linebig;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    int sum = 0;
    while(n--) {
        int cz;
        cin >> cz;
        int k, b;
        cin >> k >> b;
        if(cz == 1) {
            linesmall[k][b]++;
            sum++;
            linebig[k]++;
        }
        if(cz == 2) {
            cout << sum - linebig[k] << '\n';
        }
        if(cz == 3) {
            sum = linebig[k] - linesmall[k][b];
            map<int ,int> tmp;
            linesmall[k][b] = 0;
            if(abs(k) <= 50)tmp = linesmall[k];//最后一个数据点貌似非常水，不需要这句话就可以 A. 但是有了会 TLE， 所以说就特判一下为了防止 Subtask 2 出错
            linesmall.clear();
            linebig.clear();
            linebig[k] = sum;
            linesmall[k] = tmp;
            tmp.clear();
        }
    }
    return 0;
}

T4 100pts

这道题一开始不容易看懂，但通过推理我们知道 $S^k$ 就相当于把字符串 $S$ 翻 $k$ 倍。

因为可以无限翻倍，所以说除了 $S$ 中不存在的数之外，最长公共子序列的长度就是 $T\cup S$ 元素的数量

而 $k$ 也很好求了。

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1e6 + 5;

int n, m, c1, c2, k = 1;
int ans = 0;
int a[maxn];
bool used[maxn];
vector<int> b(1);
vector<int> index[maxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> c1 >> c2;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        used[a[i]] = true;
        index[a[i]].push_back(i);
    }
    int ans = 0;
    for(int i = 1, tmp; i <= m; i++) {
        cin >> tmp;
        if(used[tmp]) b.push_back(tmp);
        ans += used[tmp];
    }
    int it = 0;
    for(int i = 1; i < b.size(); i++) {
        bool suc = true;
        while(suc){
            suc = true;
            for(int j = 0; j < index[b[i]].size(); j++) {
                if(index[b[i]][j] > it) {
                    it = index[b[i]][j];
                    suc = false;
                    break;
                }
            }
            if(suc) {
                k++;
                it = 0;
            }
        }
    }
    cout << c1 * ans << " " <<c2 * k;
    return 0;
}

总结

• 考试需要有灵活的思维

• 调试代码的能力真的蒻爆了

• 下次考试不要再迟到了！！！