这次题拿的是2019 ICPC Mid-Central Regional，A、I、L签到模拟，F最短路，C二分答案，H技巧+桶计数，其中L题读错wa了好几发，浪费不少时间，F题经典错误，数组开小又RE2发，还有诸如int溢出，TLE之类的错误。
A – Basketball One-on-One
题意
给你一串字符串，A后面的数字代表A得分，B后面的数字代表B得分，问最后谁得分多
题目分析
暴力
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int main(int argc, char const *argv[]) {
string s;
cin >> s;
int a = 0, b = 0;
for(int i = 0; i < s.size() - 1; i++) {
if(s[i] == 'A') a += s[i+1] - '0';
else if(s[i] == 'B') b += s[i+1] - '0';
}
if(a >b) puts("A");
else puts("B");
return 0;
}
C – Convoy （二分答案）
题意
一辆车连司机可以坐5人，告诉你每个人开车从A到B或者从B到A花费的时间，一共有k辆车，问你让所有人从A到B花费的最少时间。车最终可以留在A地也可以留在B地，回程司机不能带人。
题目分析
将每个人花费的时间从小到大排，然后二分答案，check时枚举使用的车数，每辆车从小到大分配给每位司机，由于check时假设已经知道花费时间了，所以可以求出每个司机最终连自己可以运送几人，和总人数比较，如果多于总人数则check左边，否则check右边。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
LL dri, a[maxn];
LL n, k;
bool check(LL x) {
LL cnt = 0;
for(LL i = 0; i < dri; i++) {
LL round = x / a[i];
cnt += (round+1 >> 1);
if(round == 0) return cnt*4+i >= n;
}
return cnt*4+dri >= n;
}
int main(int argc, char const *argv[]) {
cin >> n >> k;
dri = min(n,k);
for(LL i = 0; i < n; i++) scanf("%lld",&a[i]);
sort(a,a+n);
LL l = 0, r = 2e11+10;
while(l < r) {
LL mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid+1;
}
cout << l << endl;
return 0;
}
F – Dragon Ball I (最短路)
题意
告诉你七颗龙珠的位置，要你从1号点出发，收集所有的龙珠，总路径最短。
题目分析
由于龙珠只有七颗，所以可以遍历全部的走法，即七颗龙珠的全排列，然后分别求出全部走法的最短路，找最小值即可，最短路可以预先处理好，分别求出1号点为起点的dijkstra最短路以及七颗龙珠为起点的dijkstra最短路。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 5e5 + 10;
const double PI = acos(-1.0);
const LL inf = 0x3f3f3f3f3f3f3f3f;
typedef pair<LL, int> PII;
int h[maxn], val[maxn], to[maxn], ne[maxn], idx, zhu[maxn];
LL dis[10][maxn], tot;
bool vis[maxn];
void add(int u, int v, int w) {
val[idx] = w;
to[idx] = v;
ne[idx] = h[u];
h[u] = idx++;
}
void dijkstra(int sta) {
priority_queue<PII> q;
memset(vis, 0, sizeof vis);
dis[tot][sta] = 0;
q.push({0, sta});
while (q.size()) {
auto now = q.top();
q.pop();
int id = now.second;
if (vis[id] == 1) continue;
vis[id] = 1;
for (int i = h[id]; i != -1; i = ne[i]) {
int j = to[i];
if (dis[tot][j] > dis[tot][id] + val[i]) {
dis[tot][j] = dis[tot][id] + val[i];
q.push({-dis[tot][j],j});
}
}
}
tot++;
}
int main(int argc, char const *argv[]) {
memset(h, -1, sizeof h);
memset(dis, 0x3f, sizeof dis);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
add(y, x, z);
}
dijkstra(1);
int pai[10] = {1, 2, 3, 4, 5, 6, 7};
for (int i = 1; i <= 7; i++) {
cin >> zhu[i];
dijkstra(zhu[i]);
}
LL ans = inf;
do {
LL now = dis[0][zhu[pai[0]]];
now += dis[pai[0]][zhu[pai[1]]];
now += dis[pai[1]][zhu[pai[2]]];
now += dis[pai[2]][zhu[pai[3]]];
now += dis[pai[3]][zhu[pai[4]]];
now += dis[pai[4]][zhu[pai[5]]];
now += dis[pai[5]][zhu[pai[6]]];
ans = min(ans, now);
} while (next_permutation(pai, pai + 7));
if (ans < inf)
cout << ans << endl;
else
puts("-1");
return 0;
}
H – Farming Mars
题意
给你n块土壤的PH值，有m次询问，每次询问下标为L到R的土壤间，PH值相同的最大值是否大于等于（R-L+1）/2+1，大于等于输出usable。其中PH值为浮点数，精确到小数点后六位。
题目分析
将PH值都 * 1000000从而转换为int，然后用桶的方式记录预处理出所有区间的最大值并比较，m次询问直接查表即可。这道题一开始用了unordered_map，结果TLE了，说明有数据卡hash构造。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e4+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int a[maxn];
int tong[14000005];
bool flag[maxn][maxn];
int main(int argc, char const *argv[]) {
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
double x;
scanf("%lf",&x);
a[i] = (int) (x*1000000) ;
}
for(int i = 1; i <= n; i++) {
int mmax = -1;
for(int j = i; j <= n; j++) {
tong[a[j]]++;
mmax = max(mmax, tong[a[j]]);
flag[i][j] = mmax >= ((j-i+1)/2+1);
}
for(int j = i; j <= n; j++) tong[a[j]] = 0;
}
while(m--) {
int l, r;
scanf("%d%d",&l,&r);
if(flag[l][r]) puts("usable");
else puts("unusable");
}
return 0;
}
I – Soft Passwords
题意
给你S和P，若S和P相等；或者将P的所有大写转换成小写，小写转换成大写后相等；或者P前面插入一个数字后等于S；或者P后面插入一个数字等于S；满足一种情况就输出YES，否则输出NO。
题目分析
模拟即可
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int main(int argc, char const *argv[]) {
string s, p;
cin >>s >> p;
if(s == p) puts("Yes");
else if(s.size() == p.size()) {
for(int i = 0; i < s.size(); i++) {
if(s[i] >= 'a' && s[i] <= 'z') s[i] -=32;
else if(s[i] >= 'A' && s[i] <= 'Z') s[i] += 32;
}
if(s == p) puts("Yes");
else puts("No");
}
else if(s.size() - p.size() == 1) {
if(s.substr(0,s.size()-1) == p && s[s.size()-1] >= '0' && s[s.size()-1] <= '9') puts("Yes");
else if(s.substr(1,s.size()-1) == p && s[0] >= '0' && s[0] <= '9') puts("Yes");
else puts("No");
}
else puts("No");
return 0;
}
L – Umm Code
题意
给你一串字符串，每个单词用空格分隔开，若一个单词只由’u’或者’m’或者标点符号组成，则属于密文的一部分，找到整个字符串的密文后（只有u和m），七个为一组，将u转换成1，m转换成0，组成七位二进制，其十进制表示就是明文所对应的ASCII码，输出明文
题目分析
模拟即可，注意判断标点。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 5e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
char s[maxn];
char change(string s) {
int res = 1, now = 1;
for (int i = s.size() - 1; i >= 0; i--) {
if (s[i] == 'u') res += now;
now *= 2;
}
return (char)res;
}
int main(int argc, char const *argv[]) {
cin.getline(s, maxn);
int n = strlen(s);
string ans;
string code;
int f = 0;
for (int i = 0; i < n; i++) {
if (s[i] ==' ') {
if (f == 1) {
code.clear();
f = 0;
} else {
ans += code;
code.clear();
}
continue;
}
if ((!((s[i] >= 'a' && s[i] <= 'z') ||(s[i] >= 'A' && s[i] <= 'Z') ||(s[i] >= '0' && s[i] <= '9')))) continue;
if (s[i] != 'u' && s[i] != 'm')
f = 1;
code += s[i];
}
if (f == 0 && code.size()) ans += code;
for (int i = 0; i < ans.size(); i += 7) {
int res = 0, now = 1;
for (int j = i+6; j >= i; j--) {
if (ans[j] == 'u') res += now;
now *= 2;
}
cout << (char) res;
}
return 0;
}
