源代码: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
题目大意:
思路:
根据上图,我们可以发现当数组为ai,3*ai时,操作不会减少
因此,我们可以构造出 1 , 3 , 9... 1,3,9... 1,3,9...这样的数组,判断 a i ≥ 1 e 9 a_i\geq 1e9 ai?≥1e9即可
代码:
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) (a1?,b1?),(an?,bn?)
-
连 ( a 1 , b 1 ) , ( a 1 , b n ) , ( a n , b x ) (a_1,b_1),(a_1,b_n),(a_n,b_x) (a1?,b1?),(a1?,bn?),(an?,bx?),其中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) (a1?,bx1?),(an?,by1?),(ax2?,b1?),(ay1?,bn?)其中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(n2)
正难则反,在脑子里模拟一遍flood fill,可以发现里已有点最近的点总是在已有点附近,那么我们可以从重点出发,向内bfs寻找起点,如此一来,时间复杂度降为 O ( n log ? n ) O(n\log n) O(nlogn)
代码:
代码使用了部分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';
}