A - Last Train
难度: ⭐⭐⭐⭐
题目大意
现有n个车站, 每个车站都有6个属性, l, d, k, c, A, B; 从时刻l开始发车, 每隔时间d发一辆, 一共发k辆; 并且火车是从A点前往B点, 所需时间是c; 设F(x)指从车站x的车最晚什么时候出发可以到车站n;
解题思路
因为所有车站的目标都是n, 那么我们可以从车站n开始反向进行最短路dijkstra; 找到从v出发可以到达u的最晚的一班车; 如果v的l + c > F(u); 则说明从v来的车赶不上u的满足条件的最晚的那班车; 否则我们找的车次就是num = min((F(u) - (l + c)) / d, k - 1); 然后就可以用l + num * d来更新F(u);
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353, inf = 2e18;
typedef pair<int, int> PII;
int n, m, res;
string s;
struct node{
int u, l, d, k, c;
};
node P[N];
vector<node> v[N];
int dis[N];
void dijkstra(){
for(int i = 1; i <= n; i++) dis[i] = -inf;
priority_queue<PII> heap;
heap.push({inf, n});
dis[n] = inf;
while(heap.size()){
PII t = heap.top();
heap.pop();
int id = t.second;
for(auto x : v[id]){
int y = dis[id] - (x.l + x.c);
if(y < 0) continue;
int num = x.l + min(y / x.d, x.k - 1) * x.d;
if(num > dis[x.u]){
dis[x.u] = num;
heap.push({dis[x.u], x.u});
}
}
}
}
signed main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int l, d, k, c, a, b;
cin >> l >> d >> k >> c >> a >> b;
v[b].push_back({a, l, d, k, c});
}
dijkstra();
for(int i = 1; i < n; i++){
if(dis[i] == -inf) cout << "Unreachable" << endl;
else cout << dis[i] << endl;
}
return 0;
}
B - Lucky bag
难度: ⭐⭐⭐⭐
C - Oil Deposits
难度: ⭐⭐
题目大意
给定一个n * n的矩阵, 矩阵中有若干个石油, 相邻的石油可看作一堆石油; 相邻是指上下左右以及对角线; 问该矩阵有多少堆石油;
解题思路
dfs板子题;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, cnt;
string s;
char g[200][200];
bool st[200][200];
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
void dfs(int a, int b){
st[a][b] = true;
for(int i = 0; i < 8; i++){
int x = a + dx[i], y = b + dy[i];
if(x >= 1 && x <= n && y >= 1 && y <= m && (!st[x][y]) && g[x][y] == '@') dfs(x, y);
}
}
signed main(){
while(cin >> n >> m){
if(n == 0 && m == 0) break;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
st[i][j] = false;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> g[i][j];
}
}
int res = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(g[i][j] == '@'){
if(!st[i][j]) {
dfs(i, j);
res++;
}
}
}
}
cout << res << endl;
}
return 0;
}
D - Add All
难度: ⭐⭐
题目大意
给定n个数, 可以任选两个数a, b相加得到新的数, 并且相加会有a + b的代价, 问如何相加可以让代价最小;
解题思路
哈夫曼树板子
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, cnt;
string s;
int p[N];
signed main(){
while(cin >> n){
if(n == 0) break;
priority_queue<int, vector<int>, greater<int>> heap;
for(int i = 1; i <= n; i++){
int a;
cin >> a;
heap.push(a);
}
int res = 0;
while(heap.size() > 1){
int a = heap.top();
heap.pop();
int b = heap.top();
heap.pop();
int c = a + b;
res += c;
heap.push(c);
}
cout << res << endl;
}
return 0;
}
E - German Conference for Public Counting
难度: ⭐⭐
题目大意
现在有很多个牌子, 牌子上有一个0~9之间的一个数字; 现在给定一个数n, 问我们至少需要多少个牌子可以把0~n中任意一个数表示出来; n为1e9;
解题思路
签到题, 对于n(n>1)位数的数, 一定存在一个n-1位的数是由同一个数组组成; eg: 0~23213中一定存在1111, 2222...10000; 所有0~9中每个数字的牌子都要至少准备n-1个; 而0~23213中还存在11111和22222, 所有再根据第n位的数遍历其他位的数就行; 复杂度最大为O(n)(n是位数, 最大为9)
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5;
signed main() {
string s;
cin >> s;
if (s.size() == 1) cout << s[0] - '0' + 1;
else {
int res = 10 * (s.size() - 1);
res = res + (s[0] - '0') - 1;
if (s[1] - '0' > s[0] - '0') res++;
else if (s[1] - '0' == s[0] - '0') {
bool f = true;
for (int i = 1; i < s.size(); i++) {
if (s[i] < s[0]) {
f = false;
break;
}
}
if (f) res++;
}
cout << res;
}
return 0;
}
F - Eszett
难度: ⭐⭐
题目大意
给定一个由大写字母组成的字符串, 将其转化成小写字母输出, 然后在转换后我们可以将"ss"转化为B, 并且保证字符串中最多只有3个s; 输出所有可能的字符串, 无论顺序; 字符串长度最大为20, S最多出现3次;
解题思路
可以记一下string的replace函数: replace(下标, 长度, 字符串); 作用是用该字符串替换从下标开始的某长度的字符串; 返回值是修改后的字符串; 所以该函数相当于遍历了一遍字符串, 所以复杂度就是O(n);
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5;
signed main() {
string s;
string res;
cin >> s;
for (int i = 0; i < s.size(); i++) s[i] = s[i] + 32;
cout << s << endl;
if (s.find("sss")!=-1) {
cout << s.replace(s.find("sss"), 3, "Bs") << endl;
cout << s.replace(s.find("Bs"), 2, "sB") << endl;
}
else if (s.find("ss") != -1) {
cout << s.replace(s.find("ss"), 2, "B") << endl;
}
return 0;
}
G - Yet Another Permutation Problem
难度: ⭐⭐
题目大意
定义一个长度为n的全排列数组, 其由1 ~ n的n个数字组成; 现在给定一个长度n, 要求输出一个长度为n的全排列数组, 对于该数组, Ai 和Ai+1可以得到一个最大公因数, 请问该数组怎么排列可以得到种类最多的最大公因数;
解题思路
对于数组x, 如果想要得到最大公因数x, 那么代价最小就是让其后面是2 * x; 利用这个贪心策略从1开始, 让其后面是前一个数的2倍, 直到新的数大于n;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, cnt;
string s;
bool st[N];
int p[N];
signed main(){
int T;
cin >> T;
while(T--){
cin >> n;
for(int i = 1; i <= n; i++) st[i] = false;
int idx = 0;
for(int i = 1; i <= n; i++){
if(st[i]) continue;
p[++idx] = i;
st[i] = true;
int j = 2 * i;
while(j <= n){
st[j] = true;
p[++idx] = j;
j *= 2;
}
}
for(int i = 1; i <= n; i++){
cout << p[i] << ' ';
}
cout << endl;
}
return 0;
}