CF Educational Round 78 (Div2)题解报告A~E

时间:2024-09-15 10:36:32

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;
}

F: Make Them Similar 待补。