D - The Modcrab (CF - 903B)

题意：

• Vova在玩RPG类型的游戏时遇到一个BOSS，每回合开始（他先手）他有两种选择：

  $1$、攻击BOSS（他自己的攻击力为$a$₁)；

  $2$、吃药恢复自己$c$₁那么多的血，（$c$₁大于$a$₂且恢复后可能大于自身本来的$h$₁的初始血量）；

  BOSS有$h$₂ 的血和$a$₂的攻击力，要求你以最快速度打败怪兽，然后输出需要的回合数和每回合的指令（HEAL为吃药恢复，STRIKE为攻击BOSS）

解题思路：

• 如果自己的血量可以承受BOSS的下次攻击或者你比BOSS先杀掉它，那么就选择攻击BOSS，否则及吃药回血，就这样直接模拟就行了.

代码：

#include<bits/stdc++.h>
//#include<iostream>
//#include<algorithm>
//#include<cmath>
//#include<cstring>
//#include<stdio.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
int a[N];
int main()
{
    int h1,a1,c1,a2,h2;
    scanf("%d%d%d",&h1,&a1,&c1);
    int ma=h1;
    scanf("%d%d",&h2,&a2);
    int len=0;
    for(int i=0;;i++)
    {
        if(h2<=0)
        {
            len=i;
            break;
        }
        if(h1-a2<=0)
        {
            if(h2-a1<=0)
            {
                len=i+1;
                a[i]=0;
                break;
            }
            a[i]=1;
            h1+=c1;
//            cout<<h1<<endl;
            h1-=a2;
        }
        else
        {
            h2-=a1;
            h1-=a2;
            a[i]=0;
        }
    }
    printf("%d\n",len);
    for(int i=0;i<len;i++)
    {
        if(a[i]==1)
            printf("HEAL\n");
        else
            printf("STRIKE\n");
    }
    return 0;
}

E - Buggy Robot （CF - 888B）

题意：

• 一个机器人有上下左右的指令，它从（0,0）出发，目的地也是（0,0），但是机器出了一点故障，问给出的指令中有多少是正确的指令。

解题思路：

• 因为它要原本要返回原位置，即有一个左的指令就一定有有一个右的指令，上下指令同理，所以正确的指令个数就为2*（MIN（左，右）+MIN（上，下），（乘2是因为如果当前左指令正确那么它所对的右指令也肯定是正确的）

代码：

#include<bits/stdc++.h>
//#include<iostream>
//#include<algorithm>
//#include<cmath>
//#include<cstring>
//#include<stdio.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
char a[N];
int main()
{
    int n;
    int l=0,r=0,u=0,d=0;
    scanf("%d%s",&n,a);
    for(int i=0;i<n;i++)
    {
        if(a[i]=='L')
            l++;
        else if(a[i]=='R')
            r++;
        else if(a[i]=='U')
            u++;
        else
            d++;
    }
    int ans=2*(min(l,r)+min(u,d));
    printf("%d\n",ans);
    return 0;
}

F - Bertown Subway （CF - 884c)

题意：

• 有$n$个车站，每个车站对应一个车站（可以是自己），且所有车站都可达，然后要求你求出在所有车站中，能$a$车站到达$b$车站的有序对（a,b）的个数的最大值，（你可以修改两个车站的对应的车站）。

解题思路：

• 因为所有车站都可达，所有必定存在环，在一个环中的有序对数位环中车站平方的个数，因为可以修改两个车站对应的车站，所以可以把两个最大次大的环（如果存在）合并在一起，然后把所有环中车站数的平方加在一起即可。

代码：

#include<bits/stdc++.h>
//#include<iostream>
//#include<algorithm>
//#include<cmath>
//#include<cstring>
//#include<stdio.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
int a[N];
ll b[N];
int vis[N];
void dfs(int n,ll &ans)
{
    ans++;
    if(vis[a[n]]==0)
    {
        vis[a[n]]=1;
        dfs(a[n],ans);
    }
    return;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int k=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            vis[i]=1;
            dfs(i,b[++k]);
        }
    }
    sort(b+1,b+1+k);
    if(k==1)
        printf("%lld\n",b[k]*b[k]);
    else
    {
        b[k-1]+=b[k];
        k--;
        ll ans=0;
        for(int i=1;i<=k;i++)
        {
            ans+=b[i]*b[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}