总结
阅读能力需要加强
这场的题除了最后一题图论建议都补了
A - Wilbur and Swimming Pool
在一个二维平面中有一个四边平行于坐标轴的矩形,给出\(1 - 4\)个坐标,分别对应矩形的\(1 - 4\)个顶点,求矩形的面积是多少;若面积无法确定则输出\(-1\)。
由于矩形四边平行于坐标轴,因此在所有坐标中取\(x\)与\(y\)的最值,相减再相乘得出矩形面积
若面积为\(0\),则说明这些点围成的图形是一个点或者一条直线,输出\(-1\)即可
为什么那么多人写模拟
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main()
{
int n;
cin >> n;
int mxx = -INF, mxy = -INF;
int mnx = INF, mny = INF;
while (n--) {
int x, y;
cin >> x >> y;
mxx = max(mxx, x);
mxy = max(mxy, y);
mnx = min(mnx, x);
mny = min(mny, y);
}
int ans = (mxx - mnx) * (mxy - mny);
if (!ans) ans = -1;
cout << ans;
return 0;
}
B - Increasing Matrix
给出一个\(n*m\)的矩阵,你可以修改值为\(0\)的元素,使每行每列都构成严格递增的序列,并且让所有元素之和尽可能大,无法构造则输出\(-1\)。
矩阵的第一列和最后一列,以及第一行和最后一行都不会出现\(0\)
题目求最大的元素值之和,实际上在每个严格递增序列中就是要让每个数都尽可能大。
由于最后一列与最后一行都不会出现0,因此限制了每个序列的尾项。
可以发现要使元素尽量大,取值就只会被它右边或者下边的元素影响,因此我们可以从右下角逆推回去,取值为 $$min(a[x + 1][y], a[x][y + 1]) – 1$$即可满足题目条件
最后检查一遍每个序列是否符合题目要求即可,时间复杂度\(O(n*m)\)
#include <bits/stdc++.h>
using namespace std;
const int N = 550;
int a[N][N];
int main()
{
int n, m;
long long ans = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j], ans += a[i][j];
for (int i = n - 1; i > 1; i--)
for (int j = m - 1; j > 1; j--)
if (!a[i][j]) a[i][j] = min(a[i + 1][j], a[i][j + 1]) - 1, ans += a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 2; j <= m; j++)
if (a[i][j - 1] >= a[i][j]) return cout << "-1", 0;
for (int j = 1; j <= m; j++)
for (int i = 2; i <= n; i++)
if (a[i - 1][j] >= a[i][j]) return cout << "-1", 0;
cout << ans;
return 0;
}
C - Mishka and the Last Exam
给定整数\(n\)与长度为\(n/2\)的数组\(b\),构造出一个非递减的序列\(a\)满足\(b[i] = a[i] + a[n – i + 1]\)
贪心地构造数组\(a\),让左半部分的数尽量小,右半部分的数尽量大
先令当前左半部分的数等于它前一个数,即可得到右半部分对应的数
若此数大于后一个数,则令这个数等于后一个数,同时调整左半部分对应的数即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 2e18;
const int N = 4e5 + 10;
ll a[N], b[N];
int main()
{
int n;
cin >> n; n /= 2;
for (int i = 1; i <= n; i++) cin >> b[i];
a[2 * n + 1] = INF;
for (int i = 2 * n, j = 1; j <= n; i--, j++) {
a[i] = b[j] - (a[j] = a[j - 1]);
if (a[i] > a[i + 1]) a[j] = b[j] - (a[i] = a[i + 1]);
}
for (int i = 2; i <= 2 * n; i++)
if (a[i - 1] > a[i]) return cout << -1, 0;
for (int i = 1; i <= 2 * n; i++)
cout << a[i] << ' ';
return 0;
}
D - Meme Problem
给出整数d,构造两个浮点数\(a\)和\(b\)满足 \(a + b = d\) 并且 \(a * b = d\)
两个方程两个未知数,代入即可得到一元二次方程 \(a * (d – a) = d\),利用求根公式即可。注意特判\(0\)和无解的情况。
也可以用二分嗯写
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
double d;
cin >> d;
if (fabs(d) < 1e-8)
return puts("Y 0.000000000 0.000000000"), void();
if (d < 4)
return puts("N"), void();
double a = (d - sqrt(d * d - 4 * d)) / 2;
double b = d - a;
printf("Y %.9f %.9f\n", a, b);
}
int main()
{
int t;
cin >> t;
while (t--) solve();
return 0;
}
E - Ehab and a 2-operation task
给出\(n\)个元素的序列,可以对此序列进行如下操作:
\(1\) 对序列前缀加上一个任意数
\(2\) 对序列前缀取任意模数
求进行不超过\(n + 1\)次操作之后能构成一个严格递增序列的操作序列
\(n + 1\)次操作可以说是很大的提示
由于每次都是对一个前缀进行操作,我们自然可以想到从后往前操作
我们可以给该序列定义任意一个大于\(n\)的模数\(mod\)
在此简化剩余系中,加法可以将当前数变化为任意一个数
因此从后往前对于序列每个前缀进行\(1\)操作之后,再整体取一次模即可
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
const int mod = 2e5;
int a[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int m = mod - a[n] - 1;
printf("%d\n1 %d %d\n", n + 1, n, m);
for (int i = n - 1, j = mod - 2; i >= 1; i--, j--)
{
int v = (j - (a[i] + m) % mod + mod) % mod;
printf("1 %d %d\n", i, v);
m = (m + v) % mod;
}
printf("2 %d %d\n", n, mod);
return 0;
}
F - Balanced Ternary String
给出一个只包含\(0,1,2\)的字符串,长度保证为\(3\)的倍数,在一次操作中你可以修改任意一个字符,最终得到\(0,1,2\)这三种字符出现次数相同的字符串,在保证修改次数最少的情况下,求字典序最小的结果
易知题目要让\(0,1,2\)三种字符的数量都等于\(n/3\)
可以对三种字符都开一个双端队列
- 若字符\(0\)达不到需求,可以在另外两种字符中选出一个最前的位置进行修改
- 若字符\(2\)达不到需求,可以在另外两种字符中选出一个最后的位置进行修改
- 若字符\(1\)达不到需求,先看字符\(2\)有没有多出,有的话选择最前的一个\(2\)进行修改,否则选择最后的一个\(0\)进行修改
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
const int INF = 1e9;
char s[N];
deque<int> q[3];
int main()
{
int n;
scanf("%d%s", &n, s + 1);
for (int i = 1; i <= n; i++) q[s[i] - '0'].push_back(i);
int cnt = n / 3;
for (int i = q[0].size(); i < cnt; i++) {
int u = q[1].size() > cnt ? q[1].front() : INF;
int v = q[2].size() > cnt ? q[2].front() : INF;
if (u < v) s[u] = '0', q[1].pop_front();
else s[v] = '0', q[2].pop_front();
}
for (int i = q[2].size(); i < cnt; i++) {
int u = q[0].size() > cnt ? q[0].back() : 0;
int v = q[1].size() > cnt ? q[1].back() : 0;
if (u > v) s[u] = '2', q[0].pop_back();
else s[v] = '2', q[1].pop_back();
}
for (int i = q[1].size(); i < cnt; i++) {
if (q[2].size() > cnt) s[q[2].front()] = '1', q[2].pop_front();
else s[q[0].back()] = '1', q[0].pop_back();
}
printf("%s", s + 1);
return 0;
}
G - Hard Process
给出一个01序列,在一次操作中你可以把0变成1,最多进行k次,求进行操作后最长的全1子串长度
尺取法(没见过可以去了解一下)
可以利用双指针,每次都取得修改k个0能取得的最长全1子串的长度
时间复杂度\(O(n)\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
int a[N];
int main()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
int L = 1, R = 1, cnt = 0, ansL = 0, ansR = 0, ans = 0;
while (L <= n && R <= n) {
// 在 L 确定的情况下,移动 R 指针到最右的位置
while (R <= n && (a[R] == 1 || cnt < k)) cnt += !a[R++];
if (R - L > ans) ansL = L, ansR = R, ans = R - L;
while (a[L] == 1) L++;
L++, cnt--;
}
cout << ans << '\n';
for (int i = 1; i <= n; i++) {
if (i >= ansL && i < ansR) cout << "1 ";
else cout << a[i] << ' ';
}
return 0;
}
H - Fight Against Traffic
给出一个\(n\)个点\(m\)条边的无向连通图,要求再加一条无向边,保证加边之后无重边自环,且\(s\)到\(t\)的最短路长度不变,求有多少种加边方案。
\(n\)只有1000,考虑\(O(n^2)\)的做法
直接用两次dijkstra跑出\(s\)与\(t\)的最短路\(ds\)与\(dt\)
然后双重循环枚举每两个点\(u\)与\(v\)
首先判断是否原来就存在边,这个用map就可以解决
只需满足$$min(ds[u] + dt[v] + 1, ds[v] + dt[u] + 1) >= ds[t]$$
即可计入答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1010, M = 2010, INF = 1e9;
int h[N], e[M], ne[M], idx;
int ds[N], dt[N];
int n, m, s, t;
void add(int a, int b)
{
e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}
void dij(int d[], int s)
{
vector<int> v(n + 1);
for (int i = 1; i <= n; i++) d[i] = INF;
d[s] = 0;
priority_queue<PII> q;
q.push(make_pair(1, s));
while (q.size()) {
int x = q.top().second; q.pop();
if (v[x]) continue;
v[x] = 1;
for (int i = h[x]; i; i = ne[i]) {
int u = e[i];
if (d[u] > d[x] + 1) {
d[u] = d[x] + 1;
q.push(make_pair(-d[u], u));
}
}
}
}
int main()
{
cin >> n >> m >> s >> t;
map<PII, bool> mp;
while (m--) {
int u, v;
cin >> u >> v;
add(u, v); add(v, u);
if (u > v) swap(u, v);
mp[PII(u, v)] = 1;
}
dij(ds, s), dij(dt, t);
int ans = 0;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (mp.count(PII(i, j))) continue;
if (min(ds[i] + dt[j] + 1, ds[j] + dt[i] + 1) >= ds[t]) ans++;
}
}
cout << ans;
return 0;
}
标签:const,int,排位赛,ans,cin,long,第一场,题解,INF
From: https://www.cnblogs.com/bous/p/16646831.html