源代码:
ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)
更好的阅读体验:
折跃坐标
A. Playoff
题目大意:
思路:
比较简单的数学思路
我们发现每轮会刷掉奇数位的选手
不难发现和证明 最终剩下的一定是$2^n-1 $
代码:
void solution()
{
cin >> n;
cout << (1 << n) - 1 << endl;
}
B. Prove Him Wrong
题目大意:
思路:
根据上图,我们可以发现当数组为a
i
,3*a
i
时,操作不会减少
因此,我们可以构造出
1
,
3
,
9…
1,3,9…
1
,
3
,
9
.
.
.
这样的数组,判断
a
i
≥
1
e
9
a_i\geq 1e9
a
i
≥
1
e
9
即可
代码:
void solution()
{
cin >> n;
vector<ll> V;
ll nowNum = 1;
while (V.size() < n)
{
V.push_back(nowNum);
nowNum *= 3;
if (nowNum > 1e9)
break;
}
if (V.size() == n)
{
cout << "YES" << endl;
for (auto it : V)
cout << it << " ";
cout << endl;
}
else
{
cout << "NO" << endl;
}
}
C. Fault-tolerant Network
题目大意:
思路:
一个恶心人的思路题罢了
有这么几种连法
-
连
(a
1
,
b
1
)
,
(
a
n
,
b
n
)
(a_1,b_1),(a_n,b_n)
(
a
1
,
b
1
)
,
(
a
n
,
b
n
)
-
连
(a
1
,
b
1
)
,
(
a
1
,
b
n
)
,
(
a
n
,
b
x
)
(a_1,b_1),(a_1,b_n),(a_n,b_x)
(
a
1
,
b
1
)
,
(
a
1
,
b
n
)
,
(
a
n
,
b
x
)
,其中x时任意位置 -
连
(a
1
,
b
x
1
)
,
(
a
n
,
b
y
1
)
,
(
a
x
2
,
b
1
)
,
(
a
y
1
,
b
n
)
(a_1,b_{x1}),(a_n,b_{y1}),(a_{x2},b_1),(a_{y1},b_n)
(
a
1
,
b
x
1
)
,
(
a
n
,
b
y
1
)
,
(
a
x
2
,
b
1
)
,
(
a
y
1
,
b
n
)
其中x,y均为任意位置
建议自己画个图好好比划一下
代码:
void solution()
{
ll ans = 1e12;
cin >> n;
vector<ll> ga(n), gb(n);
for (int i = 0; i < n; i++)
cin >> ga[i];
for (int i = 0; i < n; i++)
cin >> gb[i];
ans = min({ans, abs(ga[0] - gb[0]) + abs(ga[n - 1] - gb[n - 1]), abs(ga[0] - gb[n - 1]) + abs(ga[n - 1] - gb[0])});
{
ll tmpAns = abs(ga[0] - gb[0]);
ll t1 = 1e12;
ll t2 = 1e12;
for (int i = 1; i < n; i++)
t1 = min(t1, abs(ga[n - 1] - gb[i]));
for (int i = 1; i < n; i++)
t2 = min(t2, abs(gb[n - 1] - ga[i]));
tmpAns = tmpAns + t1 + t2;
ans = min(ans, tmpAns);
}
{
ll tmpAns = abs(ga[n - 1] - gb[n - 1]);
ll t1 = 1e12;
ll t2 = 1e12;
for (int i = 0; i < n - 1; i++)
t1 = min(t1, abs(ga[0] - gb[i]));
for (int i = 0; i < n - 1; i++)
t2 = min(t2, abs(gb[0] - ga[i]));
tmpAns = tmpAns + t1 + t2;
ans = min(ans, tmpAns);
}
{
ll tmpAns = abs(ga[0] - gb[n - 1]);
ll t1 = 1e12;
ll t2 = 1e12;
for (int i = 0; i < n - 1; i++)
t1 = min(t1, abs(ga[n - 1] - gb[i]));
for (int i = 1; i < n; i++)
t2 = min(t2, abs(gb[0] - ga[i]));
tmpAns = tmpAns + t1 + t2;
ans = min(ans, tmpAns);
}
{
ll tmpAns = abs(ga[n - 1] - gb[0]);
ll t1 = 1e12;
ll t2 = 1e12;
for (int i = 1; i < n; i++)
t1 = min(t1, abs(ga[0] - gb[i]));
for (int i = 0; i < n - 1; i++)
t2 = min(t2, abs(gb[n - 1] - ga[i]));
tmpAns = tmpAns + t1 + t2;
ans = min(ans, tmpAns);
}
{
ll tmpAns = abs(ga[n - 1] - gb[0]) + abs(ga[n - 1] - gb[n - 1]);
ll t1 = 1e12;
for (int i = 1; i < n; i++)
t1 = min(t1, abs(ga[0] - gb[i]));
tmpAns = tmpAns + t1;
ans = min(ans, tmpAns);
}
{
ll tmpAns = abs(gb[0] - ga[0]) + abs(gb[0] - ga[n - 1]);
ll t1 = 1e12;
for (int i = 1; i < n; i++)
t1 = min(t1, abs(gb[n - 1] - ga[i]));
tmpAns = tmpAns + t1;
ans = min(ans, tmpAns);
}
{
ll tmpAns = abs(gb[n - 1] - ga[0]) + abs(gb[n - 1] - ga[n - 1]);
ll t1 = 1e12;
for (int i = 1; i < n; i++)
t1 = min(t1, abs(gb[0] - ga[i]));
tmpAns = tmpAns + t1;
ans = min(ans, tmpAns);
}
{
ll tmpAns = abs(ga[0] - gb[0]) + abs(ga[0] - gb[n - 1]);
ll t1 = 1e12;
for (int i = 1; i < n; i++)
t1 = min(t1, abs(ga[n - 1] - gb[i]));
tmpAns = tmpAns + t1;
ans = min(ans, tmpAns);
}
{
ll tmpAns = 0;
ll t1 = 1e12;
ll t2 = 1e12;
for (int i = 1; i < n - 1; i++)
t1 = min(t1, abs(ga[0] - gb[i]));
for (int i = 1; i < n - 1; i++)
t2 = min(t2, abs(ga[n - 1] - gb[i]));
tmpAns = tmpAns + t1 + t2;
t1 = t2 = 1e12;
for (int i = 1; i < n - 1; i++)
t1 = min(t1, abs(gb[0] - ga[i]));
for (int i = 1; i < n - 1; i++)
t2 = min(t2, abs(gb[n - 1] - ga[i]));
tmpAns = tmpAns + t1 + t2;
ans = min(ans, tmpAns);
}
cout << ans << endl;
}
D. Nearest Excluded Points
题目大意:
思路:
很容易可以想到一种从已有点进行bfs的做法,但会超时,
如果这2e5个点组成了一个正方形或者圆形,时间复杂度接近
O
(
n
2
)
O(n^2)
O
(
n
2
)
正难则反,在脑子里模拟一遍flood fill,可以发现里已有点最近的点总是在已有点附近,那么我们可以从重点出发,向内bfs寻找起点,如此一来,时间复杂度降为
O
(
n
log
n
)
O(n\log n)
O
(
n
lo
g
n
)
代码:
代码使用了部分c++2a新增功能
int n;
cin >> n;
map<pair<int, int>, int> vis, mp;
set<pair<int, int>> s;
vector<pair<int, int>> ans(n + 1);
for (int i = 1; i <= n; i++)
{
int t1, t2;
cin >> t1 >> t2;
mp[{t1, t2}] = i;
for (auto [dx, dy] : dir4)
s.insert({t1 + dx, t2 + dy});
}
queue<array<int, 5>> q;
for (auto [x, y] : s)
if (!mp.contains({x, y}))
q.push({x, y, x, y, 0});
while (!q.empty())
{
auto [orix, oriy, x, y, dis] = q.front();
q.pop();
for (auto [dx, dy] : dir4)
{
if (vis[{x + dx, y + dy}] == 1)
continue;
if (!mp.contains({x + dx, y + dy}))
continue;
{
ans[mp[{x + dx, y + dy}]] = {orix, oriy};
q.push({orix, oriy, x + dx, y + dy, dis + 1});
vis[{x + dx, y + dy}] = 1;
}
}
}
for (int i = 1; i <= n; i++)
{
auto [x, y] = ans[i];
cout << x << " " << y << '\n';
}