题目链接 官方题解
A. Word Correction
题目大意
设
a,e,i,o,u,y
a
,
e
,
i
,
o
,
u
,
y
是六个特殊字母，如果一个小写字母串从左往右读，出现连续两个特殊字母时，则删除后面这个特殊字母，直至没有连续两个特殊字母，输出这样处理后的字符串。
思路 - 模拟
按照题意模拟即可：
i
i
表示将要输出的字母，jj表示下一个可能会输出的字母 ①如果
i,j
i
,
j
都是特殊字母，则
i
i
不变，令jj变为下一个字母 ②如果
i,j
i
,
j
至少有一个不是特殊字母，则输出
i
i
，然后令i=ji=j，
j
j
变为下一个字母
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN =
103;
int n;
char s[MAXN];
inline bool isVowel(
char ch) {
return ch ==
'a' || ch ==
'e' || ch ==
'i' || ch ==
'o' || ch ==
'u' || ch ==
'y';
}
int main() {
while(
2 ==
scanf(
"%d%s", &n, s)) {
for(
int i =
0, j =
1; i < n;) {
if(isVowel(s[i]) && isVowel(s[j])) {
j;
}
else {
printf(
"%c", s[i]);
i = j;
if(j < n) {
j;
}
}
}
printf(
"\n");
}
}
B. Run For Your Prize
题目大意
在一条数轴上坐标为2∼106−12∼106−1范围内有
n
n
个奖品，甲可以从坐标为11的位置开始拿奖品，乙可以从坐标为
106
10
6
的位置开始拿奖品，两人每移动一个单位距离需要
1
1
秒，拿奖品不耗时，求两人把所有奖品拿完的最短耗时？
思路 - 模拟
枚举相邻的两个奖品（左边分别为i,ji,j），甲拿前者及其左边的奖品，乙拿后者及其右边的奖品，则总耗时为
max(i−1,106−j)
m
a
x
(
i
−
1
,
10
6
−
j
)
，取最小值。注意边界值，及甲或者乙不拿奖品的时候。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int END =
1e6;
int n;
int last, cur, ans;
int main() {
while(
1 ==
scanf(
"%d", &n)) {
ans = END;
last =
0;
while(n-- >
0) {
scanf(
"%d", &cur);
ans = min(ans, max(END - cur, last -
1));
last = cur;
}
ans = min(ans, last -
1);
printf(
"%d\n", ans);
}
}
C. Constructing Tests
题目大意
设一个
n
n
阶0101方阵，若其每一个
m
m
阶子方阵内都至少含有一个00，此时这个
n
n
阶方阵内最多能有kk个
1
1
。现在给定kk，构造
n,m
n
,
m
使其满足上述条件，无法构造则输出
−1
−
1
。
思路 - 枚举
用将
n
n
阶方阵划分成不重叠的mm阶方阵，不够的不计算，则共能划分成
⌊nm⌋2
⌊
n
m
⌋
2
个完整的
m
m
阶方阵，每个方阵右下角取00，其全为
1
1
，则能满足题意。从而得到关系：n2−⌊nm⌋2=kn2−⌊nm⌋2=k。 又：
m=1
m
=
1
时，
k
k
横为00，且
n
n
不变时，kk随着
m
m
的递增而非递减，可知对于每一个nn，
k
k
的下界为3n243n24，从而由
k
k
得到nn的上界为
4k3−−√
4
k
3
，所以枚举
n
n
，然后计算得mm，再判断
n,m,k
n
,
m
,
k
是否满足得到的关系即可。
代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const double EPS =
1e-6;
int x;
int main() {
int T;
scanf(
"%d", &T);
while(T-- >
0) {
scanf(
"%d", &x);
if(x ==
0) {
printf(
"1 1\n");
continue;
}
bool flag =
false;
for(
int n =
2; ((
3LL * n * n) >>
2LL) <= x; ++n) {
long long tmp =
1LL * n * n - x;
if(tmp >
0) {
int n_m =
sqrt(tmp) + EPS;
int m = n / n_m;
if(n * n - (n / m) * (n / m) == x) {
printf(
"%d %d\n", n, m);
flag =
true;
break;
}
}
}
if(!flag) {
printf(
"-1\n");
}
}
}
D. Buy a Ticket
题目大意
给定一个
n
n
个顶点，mm条边的无向图，每条边都有权值
w
w
，每个顶点有权值aa，对于每一个顶点
i
i
找出一个顶点jj（
i
i
到jj的最短路径为
dist
d
i
s
t
，
j
j
的权值为xx），使得：
2dist+x
2
d
i
s
t
+
x
最小。
思路 - Dijkstra
设置一个超级源点，其到每个顶点都有条无向边，权值为该顶点的权值，则问题转化为单元最短路，直接用堆优化的
Dijkstra
D
i
j
k
s
t
r
a
即可。
代码
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN =
200003;
const int MAXM =
200003;
struct Node {
int v;
long long w;
Node() {}
Node(
int v,
long long w):v(v), w(w) {}
bool operator< (
const Node& a)
const {
return w > a.w;
}
};
struct Edge {
int v, nxt;
long long w;
}edge[(MAXM + MAXN) <<
1];
int tot, fir[MAXN];
void init() {
tot =
0;
memset(fir, -
1,
sizeof(fir));
}
void addEdge(
int u,
int v,
long long w) {
edge[tot].v = v;
edge[tot].w = w;
edge[tot].nxt = fir[u];
fir[u] = tot++;
edge[tot].v = u;
edge[tot].w = w;
edge[tot].nxt = fir[v];
fir[v] = tot++;
}
int n, m;
long long a;
long long dist[MAXN];
bool vis[MAXN];
void dijkstra() {
memset(vis,
false,
sizeof(vis));
memset(dist,
0x3f,
sizeof(dist));
dist[
0] =
0;
priority_queue<Node> q;
q.push(Node(
0, dist[
0]));
int u, v;
long long w;
Node cur;
while(!q.empty()) {
cur = q.top();
u = cur.v;
w = cur.w;
q.pop();
if(vis[u]) {
continue;
}
vis[u] =
true;
for(
int i = fir[u]; i != -
1; i = edge[i].nxt) {
v = edge[i].v;
w = edge[i].w;
if(dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
q.push(Node(v, dist[v]));
}
}
}
}
int main() {
int u, v;
long long w;
while(
2 ==
scanf(
"%d%d", &n, &m)) {
init();
while(m-- >
0) {
scanf(
"%d%d%I64d", &u, &v, &w);
addEdge(u, v, w <<
1LL);
}
for(
int i =
1; i <= n; ++i) {
scanf(
"%I64d", &a);
addEdge(
0, i, a);
}
dijkstra();
for(
int i =
1;i <= n; ++i) {
printf(
"%I64d%c", dist[i], i == n ?
'\n' :
' ');
}
}
}
