题目链接:Codeforces Round 920 (Div. 3)

A. Square

难度:800

输入矩形的四个坐标,计算四边形的面积。

获取到输入坐标中x和y轴的最小值最大值,相乘计算面积即可。

int t;
int a[4][2],minx,miny,maxx,maxy;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        F(i,0,3)
            CI a[i][0]>>a[i][1];
        minx=maxx=a[0][0];
        miny=maxy=a[0][1];
        F(i,0,3)
        {
            minx=min(minx,a[i][0]);
            maxx=max(maxx,a[i][0]);
            miny=min(miny,a[i][1]);
            maxy=max(maxy,a[i][1]);
        }
        CO abs(maxx-minx)*abs(maxy-miny) L;
    }
    return 0;
}

B. Arranging Cats

难度:800

给出两段只由0和1组成的字符串s和n,每一步可以把一个1变成0、把0变成1、把一个0和1对调。求出最小多少步可以让字符串s与n相等。

为求出最小的步数,可以先把需要0变成1和需要1变成0的两位进行交换,这样一步就可以让两位字符相等,等无法交换时,再一位一位的修改字符串。所以分别计算出s和n中不相等位中字符1的个数,最大的一个即为最小步数。

int t,n;
string s1,s2;
int main()
{   
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n;
        CI s1>>s2;
        int x1=0,x2=0;
        F(i,0,n-1)
            if (s1[i]!=s2[i])
            {
                if (s1[i]=='1') x1++;
                else x2++; 
            }
        if (x1>x2) CO x1 L;
        else CO x2 L;
    }
    return 0;
}

C. Sending Messages

难度:900

有n个短信需要发送,每个短信在第\(a_i\)时刻发送,手机初始为开机状态有f格电,每单位时间会消耗a格电,开关机一次需要b格电,当电量≤0时将无法发送短信。求这n个短信能否全部发出去。

进行模拟即可,在需要发短信的时刻手机需要保持开机状态,但在没发短信的等待时刻可以选择开机等待或者关机等待。判断开机等待还是关机等待消耗的电量少,选择最少的即可,最后看能否发完全部短信。

int t;
LL mes,power,use,off;
LL a[200005];
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI mes>>power>>use>>off;
        F(i,1,mes)
            CI a[i];
        int t=0,f=1;
        F(i,1,mes)
        {
            if ((a[i]-a[i-1])*use<=off) power-=(a[i]-a[i-1])*use;
            else power-=off;
            if (power<=0) 
            {
                f=0;
                break;
            }
        }
        if (f) CO "YES" L;
        else CO "NO" L;
    }
    return 0;
}

D. Very Different Array

难度:1100

给出两个数组a,b,长度分别为n,m,且n≤m。要在b数组的m个数中选出n个数并排序,然后依次与a数组中对应的数相减,使得绝对值的和最大,即sum(abs(ai-bi))最大。

为了使两个数组每个元素差的绝对值最大,需要将两个数组中最大的数与最小的数相减。所以首先先将数组a从小到大排序,将数组b从大到小排序,然后再维护一个数组c和指针k,将b数组中的前k个元素依次加入到数组c中,再将b数组的后n-k个元素依次加入到数组c中,然后再计算c与b差的绝对值。不断移动指针k,保存下最大的那个差的绝对值。

这样做可以得到正确的结果,但是会导致超时。观察数组c可以发现,每次指针k移动,c中都只有一个元素发生了改变。所以可以直接记录下b数组的前n个元素与a的差的绝对值,同时指针k指向b数组的第n个数,然后指针k不断向左移动直到指向第一个元素,同时不断从记录下的结果中删去指针指向元素b[k]与对应元素a[k]的差,再添加上对应的元素b[k+m-n]与a[k]的差,并记录最大值。

LL t,n,m,ans,ma;
LL a[200005],b[200005];

bool cmp(LL a,LL b)
{
    return a>b;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        ans=0;
        ma=0;
        CI n>>m;
        CII(a,1,n)
        CII(b,1,m)
        sort(a+1,a+n+1);
        sort(b+1,b+m+1,cmp);

        F(i,1,n)
            ans+=abs(b[i]-a[i]);
        ma=ans;

        FD(i,n,1)
        {
            ans-=abs(b[i]-a[i]);
            ans+=abs(b[i+m-n]-a[i]);
            ma=max(ma,ans);
        }
        CO ma L;
    }
    return 0;
}

E. Eat the Chip

难度:1600

给出一个棋盘和两个已经放在棋盘上的棋子a,b,a只能向下,沿对角线左下、右下移动1格,b只能向上,沿对角线左上、右上移动1格。a先走,如果一个棋子移动后盖在了另一棋子上,就算赢。

这题根据a,b所在坐标就能分析出最终谁赢。如果a在b棋子的下方或者平行,那么a一直向下走,b一直向上走,最后谁都吃不了对方,所以平手。如果a在b棋子上方,但两者的横向距离太远,直到两个棋子平行横向上仍有距离,则为平手。
如果ab之间纵向间隔的格子为偶数,因为a先走,所以a能吃掉b;同样如果间隔为奇数,则b能吃掉a。这是被吃掉的一方就要努力避开对方。所以还需要计算出当双方平行时,双方的横向移动范围。如果被吃的一方移动范围有一边超出了吃的一方,则可以逃出去,变为平局。

int t,n,m,xa,ya,xb,yb;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n>>m>>xa>>ya>>xb>>yb;
        if (xa>=xb) CO "Draw" L;
        elif (abs(ya-yb)-1>(xb-xa-1)) CO "Draw" L;
        elif ((xa-xb)%2!=0) 
        {
            int la=max(1,ya-(xb-xa)/2-1);
            int ra=min(m,ya+(xb-xa)/2+1);
            int lb=max(1,yb-(xb-xa)/2);
            int rb=min(m,yb+(xb-xa)/2);
            if (la<=lb&&ra>=rb) CO "Alice" L;
            else CO "Draw" L;
        }
        else 
        {
            int la=max(1,ya-(xb-xa)/2);
            int ra=min(m,ya+(xb-xa)/2);
            int lb=max(1,yb-(xb-xa)/2);
            int rb=min(m,yb+(xb-xa)/2);
            if (lb<=la&&rb>=ra) CO "Bob" L;
            else CO "Draw" L;
        }
    }
    return 0;
}

循之际,如星夜般的幻想。