前言
这是蒟蒻 AK 的第一场考试!
让我们恭喜它!
比赛 id:124047
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 做的,题目涉及到初中数学一次函数
令 y1=k1x+b1,y2=k2x+b2
如果两条直线仅有一个交点,则:
- k1≠k2
若两条直线至少有一个焦点,则:
- k1≠k2||(k1=k2&b1=b2)
起初我本来想用一个二维 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
这道题一开始不容易看懂,但通过推理我们知道 Sk 就相当于把字符串 S 翻 k 倍。
因为可以无限翻倍,所以说除了 S 中不存在的数之外,最长公共子序列的长度就是 T∪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; }
总结
-
考试需要有灵活的思维
-
调试代码的能力真的蒻爆了
-
下次考试不要再迟到了!!!