2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest(补题中)

加粗：赛时AC 

普通：赛后AC

A. Xu Xiake in Henan Province

水题，有几个零就输出对应的语句。

B. Ultraman vs. Aodzilla and Bodzilla

有人打的时候非要雪花勇闯天涯去做没人出的题，我不说是谁.jpg

模拟+贪心，这题的细节非常多而且繁杂。

首先我们必须明确，结束战斗的回合数是一定的，也就是把hpa+hpb刚好砍完的那一刻，既然回合一定，那么就一定要先解决掉一个怪兽使得收到的伤害最少。

那么我们会发现，先把A杀掉或者先把B杀掉的回合数也是一定的，但是如果把刀集中在一起，由于伤害是递增的，就会造成伤害溢出的情况。所以用可能会将前面溢出的一些伤害打在另一只怪兽身上。

最难的部分体现在要按照字典序输出，我们分类讨论：

一.如果先杀A的伤害更低，我们记录一个杀A溢出伤害x和一个最终溢出伤害y，那么：

1.假如y为正数，就说明目前B还没有死亡，此时x的绝对值一定大于y的绝对值，就需要在前面把A刀转为B刀，基于字典序最小的规定，一定是把刚好等于溢出伤害的地方转为B刀。

2.假如y为负数，就不需要更改。

二、如果先杀B的伤害更低，我们记录一个杀B溢出伤害x和一个最终溢出伤害y，那么：

无论y是否为负数，此时x的绝对值一定大于y的绝对值，就需要在前面把B刀转为A刀，基于字典序最小的规定，注意，由于‘A’<‘B’，所以应该是从第1个到刚好伤害到达小于等于x的绝对值的时候全部转为A刀，但是，这个转换有一个很特殊的情况：

如果y是正数的话，那么B刀转为A刀的时候一定要保证y<=伤害<=x，才能够保证击杀掉A也杀掉B(y是负数的话转A刀就不用考虑必须杀死A，因为A已经死了)。此时，假如我们从小到大一个个从1开始转A刀的话，就有可能在最后一刀的时候刚好伤害>x，而少了这一刀的话就伤害

三、如果两种击杀方式相等，此时我们并不能够保证那种情况的字典序最小，最好的办法就是两种都做一遍然后选择答案更合适的输出

#include 
#include
#include<string>
#include
#include
#include
#include
#include
#include
#define N 1000010
#define ll long long
using namespace std;
ll a[N],T;
ll hpa,hpb,atka,atkb;
char ch[N],ch2[N];
//快读 
inline void read(ll &p)
{
    p=0;
    ll f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') p=p*10+(ch-'0'),ch=getchar();
    p*=f;
}


int main()
{
    read(T);
    for(int i=1;i<=N-10;i++) a[i]=a[i-1]+i;
    while(T--)
    {
        read(hpa);read(hpb);
        read(atka);read(atkb);
        
        
        ll shaab=lower_bound(a+1,a+1+N,hpa+hpb)-a;
        ll shaa=lower_bound(a+1,a+1+N,hpa)-a;
        ll shab=lower_bound(a+1,a+1+N,hpb)-a;
        ll shanga=0,shangb=0;
        ll limhpa=hpa,limhpb=hpb,limhpb2=limhpb,limhpa2=hpa;
        int i;
        
        for(i=1;i<=shaa;i++) shanga+=(atka+atkb),limhpa2-=i;
        for(i=shaa+1;i<=shaab;i++) shanga+=atkb,limhpb-=i;
        
        
        
        for(i=1;i<=shab;i++) shangb+=(atka+atkb),limhpb2-=i;
        for(i=shab+1;i<=shaab;i++) shangb+=atka,limhpa-=i;
        
        
            for(i=1;i<=shaa;i++) ch[i]='A';
            for(i=shaa+1;i<=shaab;i++) ch[i]='B';
            //伤害区间(limhpb-abs(limhpa1)) 
            if(limhpb>0) ch[abs(limhpa2)]='B';
            for(i=1;i<=shab;i++) ch2[i]='B';
            for(i=shab+1;i<=shaab;i++) ch2[i]='A';
            ll limms=0;
                for(i=1;i<=shab;i++)
                {
                    if(limms>=limhpa) break;
                    limms+=i;
                    ch2[i]='A';
                }
                if(limms>abs(limhpb2))
                {
                    ch2[i-1]='B';
                    ch2[i-2]='B';
                    i--;
                    limms-=i;
                    i--;
                    limms-=i;
                    for(i;i<=shab;i++)
                    {
                        if(limms+i>limhpa) break;
                    }
                    ch2[i-1]='A';
                }
                else
                {
                    for(i;i<=shab;i++)
                    {
                        if(limms>abs(limhpb2)) break;
                        ch2[i]='A';
                        limms+=i;
                    }
                    ch2[i-1]='B';
                }
        if(shanga<shangb) 
        {
            printf("%lld ",shanga);
            for(int i=1;i<=shaab;i++) printf("%c",ch[i]);
        }
        else if(shanga>shangb)
        {
            printf("%lld ",shangb);
            for(int i=1;i<=shaab;i++) printf("%c",ch2[i]);
        }
        else
        {
            printf("%lld ",shanga);
            bool f=1;
            for(int i=1;i<=shaab;i++)
            {
                if(ch[i]0;break;}
                else if(ch[i]>ch2[i]){f=1;break;}
            }
            if(f) for(int i=1;i<=shaab;i++) printf("%c",ch2[i]);
            else for(int i=1;i<=shaab;i++) printf("%c",ch[i]);
        }
        printf("\n");
    }
    return 0;
}

/*
1
5 5 1 1

5
5 15 5 25
5 15 25 5
251765086 586338075 348202 6436188
23 76 3 33

*/

D. Keiichi Tsuchiya the Drift King

数学题，杰哥做的，我看不懂，弃疗.jpg

#define _CRT_SECURE_NO_WARNINGS
#include 
#include <string>
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include 

using namespace std;
typedef long long ll;
#define finc(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define fdec(i,a,b) for(int i=(int)(b);i-->(int)(a);)
#define reset(a,...) a=decltype(a)(__VA_ARGS__)
#define endl '\n'
#define endb ' '
#define read(a,str) scanf("%"#str,&a)
#define print(a,str) printf("%"#str,a)

const double pi = acos(-1);

double dis(double a, double b)
{
    return sqrt(a * a + b * b);
}

void ac()
{
    double a, b, r, d;
    cin >> a >> b >> r >> d;
    double delta = pi * d / 180, now = atan(b / (a + r));
    if (delta >= now)
    {
        printf("%.9lf\n", dis(a + r, b) - r);
        return;
    }
    double ans = dis(a + r, b);
    ans *= cos(now - delta);
    printf("%.9lf\n", ans - r);
}

int main()
{
    //ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int test = 1; cin >> test;
    while (test--)
        ac();

    return 0;
}

E. Resistors in Parallel

这题有点让人无语，我是打了个表发现规律的，至于为什么我不是很清楚，后续会补上的。

总的来说就是以质数的积为界限，以质数+1的积为答案，但是由于数字有点大，所以需要高精度，或者用别的语言，我是用py写得。

学习一门外语真是非常重要啊.jpg

F. Honeycomb

模拟题，是壕哥写得，写得时候注意字符该怎么处理，注意cin和getline的速度很慢，所以T了很多发，gets的速度会快很多。

#include 
#include 
#include 
#include 
#include <string>
using namespace std;
int mo[6][2]= {{-1,-3},{-1,3},{1,-3},{1,3},{-2,0},{2,0}};
char mp[4000+10][6000+10];
struct node
{
    int x,y,num;
};
queue q;
int v[4000+10][6000+10];
node a,b;
int r,c;
void read()
{
    int i,j;
    for (i=0; i<4*r+3; i++)
    {
        gets(mp[i]);
        for (j=0; mp[i][j]; j++)
        {
            v[i][j]=0;
            if (mp[i][j]=='S')
            {
                a.x=i;
                a.y=j;
            }
            else if (mp[i][j]=='T')
            {
                b.x=i;
                b.y=j;
            }
        }
    }
    a.num=1;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int i,j;
        scanf("%d%d",&r,&c);
        getchar();
        read();
        q.push(a);
        v[a.x][a.y]=1;
        int ans=-1;
        while (!q.empty())
        {
            node now=q.front();
            q.pop();
            for (i=0; i<6; i++)
            {
                int x=now.x+mo[i][0],y=now.y+mo[i][1];
                if (x<0||y<0||x>=4*r+3||y>=6*c+3||mp[x][y]!=' ')
                    continue;
                node neww;
                neww.x=x+mo[i][0],neww.y=y+mo[i][1];
                if (neww.x<0||neww.y<0||neww.x>=4*r+3||neww.y>=6*c+3)
                    continue;
                if (neww.x==b.x&&neww.y==b.y)
                {
                    ans=now.num+1;
                    v[neww.x][neww.y]=1;
                    break;
                }
                if (v[neww.x][neww.y]) continue;
                v[neww.x][neww.y]=1;
                neww.num=now.num+1;
                q.push(neww);
            }
            if (ans!=-1)
                break;
        }
        while (!q.empty())
            q.pop();
        printf("%d\n",ans);
    }
    return 0;
}
/*
  +---+       +---+
 /     \     /     \
+       +---+       +---+
 \           \     /     \
  +   +   S   +---+   T   +
 /     \     /           /
+       +---+       +   +
 \           \     /     \
  +---+       +---+       +
 /                       /
+       +---+       +   +
 \                 /     \
  +---+       +---+       +
       \     /     \     /
        +---+       +---+
*/

I. Distance

思维题，首先确定策略，策略是每两次都加入最外围没有加入答案的两棵树木，在这两次之间的答案增量是一样的，而在第二次时会改变增量。

相关

标签