CF Educational Round 78 (Div2)题解报告A~E
A:Two Rival Students
依题意模拟即可
#include<bits/stdc++.h>
using namespace std;
int T;
int n, x, a, b;
int main()
{
cin >> T;
while(T--)
{
cin >> n >> x >> a >> b;
if(a > b) swap(a, b);
while(x != 0)
{
if(a > 1) x--, a--;
else if(a == 1) break;
}
while(x != 0)
{
if(b < n) x--, b++;
else if(b == n) break;
}
cout << b - a << endl;
}
return 0;
}
B: Magic Stick
1,2,3会跑成循环，其他的只要不断扩大后减小就行，特判。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int x, y; cin >>x >> y;
if(x >= y) {
puts("YES"); continue;
}
else
{
if(x == 2 && y != 3) {
puts("NO");
continue;
}
if(x == 3 && y != 3)
{
puts("NO");
continue;
}
if(x == 1 && y != 1)
{
puts("NO");
continue;
}
}
puts("YES");
}
return 0;
}
C: Dominated Subarray
线性扫一遍就好了，其实是查询相同的两个元素的距离最小是多少
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], T, n, vis[maxn]; int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
int ans = 0x3f3f3f3f;
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
vis[i] = 0;
} for(int i = 1; i <= n; i++)
{
int x = a[i];
if(vis[x]) ans = min(i-vis[x], ans);
vis[x] = i;
} if(ans == 0x3f3f3f3f) puts("-1");
else cout << ans + 1<< endl;
}
return 0;
}
D: Yet Another Monster Killing Problem
二分+贪心
首先特判英雄最高的攻击力和怪兽最大的生命值，不够就肯定打不完。
对于英雄而言，如果两个英雄\((i,j)\)攻击力相同，但是\(i.s>j.s\)，那么我们肯定不选择\(j\)而选择\(i\)。
所以我们按照\(p\)进行排序，之后进行后缀操作\(b(i).s\)表示\(i\)~\(n\)最大耐力值。
对于某个怪物而言，我们可以找到一个英雄他的攻击力恰好大于这个怪物，因为\(b\)已经针对\(p\)排好序了，所以我们可以二分找这个英雄。
我们从第一天开始，枚举每个怪物，如果当前能杀死最多怪物的英雄，对于某个怪物而言，如果英雄的耐力不足以支持当前的操作，则开启新的一天，循环杀死所有怪物。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int T, n, m;
int a[maxn]; struct Node{
int p, s;
}b[maxn]; bool cmp(Node a, Node b) {return a.p < b.p;}
bool cmpp(Node x, int y) {return x.p < y;} int main()
{
cin >> T;
while(T--)
{
int mx = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
mx = max(mx, a[i]);
}
scanf("%d", &m);
for(int i = 1, x, y; i <= m; i++)
{
scanf("%d%d", &x, &y);
b[i] = {x, y};
}
sort(b+1, b+1+m, cmp);
if(b[m].p < mx)
{
puts("-1");
continue;
} for(int i = m - 1; i >= 1; i--)
b[i].s = max(b[i].s, b[i+1].s);
int days = 1;
int las = 0; //上一个怪物
int cnt = 0x3f3f3f3f; //从上一个怪物杀到现在的英雄的最小耐力 for(int i = 1; i <= n; i++)
{
int t = lower_bound(b+1, b+m+1, a[i], cmpp) - b;
cnt = min(b[t].s, cnt);
if(cnt + las < i) //当前这只怪物杀不掉了
{
cnt = b[t].s;
days += 1;
las = i - 1;
}
}
cout << days << endl;
}
return 0;
}
E:The Contest
- \(dp\)
- \(f(i,1/2/3)\)表示第\(i\)个数放在第\(1,2,3\)个同学手上的最小操作数。
- 对于初始状态\(x\)在第\(i\)个同学手上，有\(a(x)=i\)。
- 有状态转移方程\(f(i,k) = min(f(i,k), f(i,j)+(k!=a(i+1)))\)，其中\((1\leq j \leq3,j\leq k \leq 3)\)
- 解释：因为\(1,2,3\)同学手上的序列数要单调，所以\(j\leq k\)。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], n;
int f[maxn][5];
int main()
{
int n1, n2, n3;
cin >> n1 >> n2 >> n3; n = n1 + n2 + n3;
for(int i = 1, x; i <= n1; i++)
scanf("%d", &x), a[x] = 1;
for(int i = 1, x; i <= n2; i++)
scanf("%d", &x), a[x] = 2;
for(int i = 1, x; i <= n3; i++)
scanf("%d", &x), a[x] = 3;
memset(f, 0x3f, sizeof(f));
f[0][1] = f[0][2] = f[0][3] = 0;
for(int i = 0; i <= n - 1; i++)
for(int j = 1; j <= 3; j++)
for(int k = j; k <= 3; k++)
f[i+1][k] = min(f[i+1][k], f[i][j] + (k != a[i+1]));
cout << min(min(f[n][1], f[n][2]), f[n][3]) << endl;
return 0;
}