A.跳躍游戲
題目：
分析：
根據跳躍規則，只要中間存在高度介于起點和終點之間的平臺即可讓小Z從第一個平臺跳到最后一個平臺，
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i ++)
cin >> a[i];
bool check = false;
if (a[0] < a[n - 1])
check = true;
for (int i = 1; i < n - 1; i ++)
{
if (a[0] < a[i] && a[i] < a[n - 1])
{
check = true;
break;
}
}
if (check)
cout << "YES";
else
cout << "NO";
return 0;
}
B.數數
題目：
分析：
首先n最大只有4000，因此我們可以預處理前4000個數，看每一個數其因子數量是否為奇數，最后做一遍前綴和即可，
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 4e3 + 5;
bool st[N];
int s[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
for (int i = 1; i <= 4e3; i ++)
{
unordered_map<int, bool> mp;
int cnt = 0;
for (int j = 1; j * j <= i; j ++)
{
if (i % j == 0 && !mp[j])
{
cnt ++;
mp[j] = true;
int k = i / j;
if (!mp[k])
{
mp[k] = true;
cnt ++;
}
}
}
if (cnt & 1)
st[i] = true;
}
for (int i = 1; i <= 4e3; i ++)
s[i] = s[i - 1] + st[i];
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
cout << s[n] << endl;
}
return 0;
}
C.操作陣列
題目：
分析：
用b陣列減a陣列可以得到a序列的每一個數到b序列每一個數的距離，用S1和S2分別表示正距離和以及負距離的和，由于每次操作必然是讓某個數+1讓某個數-1，這兩個數還不能相同，因此這種對稱操作使得當且僅當S1+S2=0時有解并且最優解時S1，
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
LL a[N], b[N], c[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i ++)
cin >> a[i];
for (int i = 0; i < n; i ++)
cin >> b[i];
for (int i = 0; i < n; i ++)
c[i] = b[i] - a[i];
LL cnt1 = 0, cnt2 = 0, cnt3 = 0;
for (int i = 0; i < n; i ++)
{
if (c[i] > 0)
cnt1 += c[i];
if (c[i] < 0)
cnt2 += c[i];
}
cnt3 = abs(cnt1 + cnt2);
if (cnt3 == 0)
cout << cnt1;
else
cout << -1;
return 0;
}
D.遺跡探險
題目：
分析：
首先我們對最優解的選取分個類：
1.不使用傳送門：最優解為從（1，1）-> (n，m)獲得寶藏之和的最大值
2.使用傳送門：對于傳送門A，B，A在B的前面（這里前面所指代的位置關系參照代碼里的排序規則）
①從A到B：最優解為（1，1）->(A.x,A.y)獲得寶藏的之和的最大值 + （B.x,B.y）->(n,m)獲得寶藏之和的最大值
②從B到A：最優解為（1，1）->(B.x,B.y)獲得寶藏之和的最大值 + （A.x,B.y）->(n,m)獲得寶藏之和的最大值
由于k并不是特別大，因此傳送門的選取組合我們可以列舉，那么最終全域最優解就是上面三種情況取個max
現在考慮兩個問題，如何求(1,1)->(x,y)的寶藏之和的最大值？如何求（x,y）->(n,m)寶藏之和的最大值？對于前一個問題實際上就是經典的數字三角形模型，而對于后一個問題實際上可以轉化成求（n,m）->(x,y)寶藏之和的最大值，也可以用數字三角形模型做：
1.狀態表示：定義f[i][j]表示從（1，1）->(i,j)獲得的寶藏之和的最大值，g[i][j]表示從(n,m)->(i,j)獲得的寶藏之和的最大值，
2.狀態計算：
f[i][j] = max(f[i][j - 1]， f[i - 1][j]) + w[i][j]
g[i][j] = max(g[i + 1][j], g[i][j + 1]) + w[i][j]
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e3 + 5;
LL w[N][N];
LL f[N][N], g[N][N];
struct Node
{
int x, y;
}node[N];
bool cmp(Node A, Node B)
{
if (A.x != B.x)
return A.x < B.x;
else
return A.y < B.y;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
cin >> w[i][j];
for (int i = 0; i <= N; i ++)
for (int j = 0; j <= N; j ++)
f[i][j] = g[i][j] = -2e16;
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
if (i == 1 && j == 1)
f[i][j] = w[i][j];
else
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
}
}
for (int i = n; i >= 1; i --)
{
for (int j = m; j >= 1; j --)
{
if (i == n && j == m)
g[i][j] = w[i][j];
else
g[i][j] = max(g[i + 1][j], g[i][j + 1]) + w[i][j];
}
}
int t;
cin >> t;
while (t --)
{
int k;
cin >> k;
for (int i = 0; i < k; i ++)
cin >> node[i].x >> node[i].y;
sort(node, node + k, cmp);
LL res = f[n][m];
for (int i = 0; i < k; i ++)
{
for (int j = i + 1; j < k; j ++)
{
int a = node[i].x, b = node[i].y, c = node[j].x, d = node[j].y;
res = max(res, max(f[a][b] + g[c][d], f[c][d] + g[a][b]));
}
}
cout << res << endl;
}
return 0;
}
E.頂級廚師
題目：
分析：
首先我們分別對a序列和b序列從小到大排序，對于每一個詢問，我們可以直接二分答案，對于那些禁止的組合我們再特殊處理一下即可，
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, M = 1e6 + 5;
LL a[N], b[N], del[M];
int n, m, k, q;
LL check(LL mid)
{
LL cnt = 0;
for (LL i = 1, j = m; i <= n; i ++)
{
while (a[i] * b[j] > mid && j >= 1)
j --;
cnt += j;
}
for (int i = 0; i < k; i ++)
{
if (del[i] <= mid)
cnt --;
}
return cnt;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k >> q;
for (int i = 1; i <= n; i ++)
cin >> a[i];
for (int i = 1; i <= m; i ++)
cin >> b[i];
for (int i = 0; i < k; i ++)
{
int u, v;
cin >> u >> v;
del[i] = a[u] * b[v];
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
while (q --)
{
int x;
cin >> x;
LL l = 0, r = 1e13;
while (l < r)
{
LL mid = l + r >> 1;
if (check(mid) >= x)
r = mid;
else
l = mid + 1;
}
cout << l << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/552376.html
標籤：其他
上一篇：Codeforces Round 871 (Div. 4)
下一篇：返回列表