ABC462

赛时ABCE，补D，本次题还是相对简单的，但是做E题过程中因为低级失误罚时很严重，D题没注意不同开始时间也算不同组合

AB

A题：输出字符串中的数字，判断即可。
B题：i给给j礼物，往对j的数组中添加i即可。

C

Problem Statement

There are $N$ points numbered $1$ through $N$ on a two-dimensional plane. Point $i$ $(1\le i\le N)$ has coordinates $(X_i,Y_i)$. Here, it is guaranteed that $X$ and $Y$ are each permutations of $(1,2,\ldots,N)$.

Find the number of values of $i$ such that the interior (not including the boundary) of the rectangle with sides parallel to the $x$-axis and $y$-axis, with lower-left vertex $(0,0)$ and upper-right vertex $(X_i,Y_i)$, contains none of the $N$ points numbered $1$ through $N$.

分析：

寻找二维坐标中有多少个点，满足条件：该点和原点构成的矩形中无其他点（不包含边界）。

思路：

对于两个点P(x,y)、Q(a,b)，不妨设$x<a$，则当$y\ge a$时满足条件。
再看$x=a$的情况，此时b和y任意取值均满足条件。
因此我们对x坐标升序排序，若x坐标相同，则对y进行降序排序。

• 显然x坐标最小的点一定满足条件。
• 设上一个选中的点为(x,y)，此时判断的点位(a,b)，由于已经满足$x\le a$，那么当$y\ge b$时，该点就可以选入。

Code

void sol()
{
    int n;
    cin>>n;
    vector<pair<int,int>>a(n);
    for(auto &[x,y]:a)
    {
        cin>>x>>y;
    }
    sort(a.begin(),a.end(),cmp);
    int lst=MAX,res=0;
    for(auto [x,y]:a)
    {
        if(y<=lst)
        {
            // cout<<x<<' '<<y<<'\n';
            res++;
        }
        lst=min(lst,y);
    }
    cout<<res;
}

E

Problem Statement

You are given integers $A,B,X,Y$.

A piece is placed on a two-dimensional plane. Initially, the piece is at coordinate $(0,0)$.

You can perform the following operation zero or more times:

• Let the current coordinate of the piece be $(x,y)$. Move the piece to one of the coordinates $(x-1,y),(x+1,y),(x,y-1),(x,y+1)$.

The cost of the $k$-th operation ($k \geq 1$) depends on the parity of $k$, as follows:

• If $k$ is odd: Let the current coordinate of the piece be $(x,y)$. The cost of moving to $(x-1,y)$ or $(x+1,y)$ is $A$, and the cost of moving to $(x,y-1)$ or $(x,y+1)$ is $B$.
• If $k$ is even: Let the current coordinate of the piece be $(x,y)$. The cost of moving to $(x-1,y)$ or $(x+1,y)$ is $B$, and the cost of moving to $(x,y-1)$ or $(x,y+1)$ is $A$.

Find the minimum total cost required to move the piece to coordinate $(X,Y)$.

$T$ test cases are given; solve each one.

分析：

根据操作次数的奇偶性，移动的代价(A/B)会改变。寻求到(X,Y)的最小代价。

思路：

首先坐标可能为负，但是我们可以将最优路径和终点对称到第一象限，因此直接对坐标取绝对值。
我们先贪心地走最小代价的方向，这样路线就是锯齿状，可以进行偶数次到达坐标(X,X)或(Y,Y)（取决于终点X和Y的较小值）。花费代价为$2\times\min(A,B)\times\min(X,Y)$
随后问题转化为了走直线代价怎么更小。我们假设X>Y，我们贪心到达了(Y,Y)，接下来我们需要到达终点(X,Y)，也就是横坐标右移。我们以移动两格为例（因为这样可以忽略奇偶性，总是移动偶数步），两种策略：

1. $\rightarrow,\rightarrow$，代价为A+B。
2. $\uparrow,\rightarrow,\downarrow,\rightarrow$，代价为4A（或4B）。

因此我们只需要判断A+B和4A（或4B）的大小即可。
如果移动距离是奇数，我们需要额外判断最后一步的代价。

Code

void sol()
{
    int A,B,X,Y;
    cin>>A>>B>>X>>Y;
    X=abs(X);
    Y=abs(Y);
    if(A>B)
    {
        A=min(3*B,A);
        int Z=min(X,Y);//move to (Z,Z)
        int cost=2*Z*B;
        int r=max(X,Y)-Z;
        cost+=(r/2)*(A+B);
        if(r%2)
        {
            if(X==Z)
            {
                cost+=B;
            }
            else
            {
                cost+=A;
            }
        }
        cout<<cost<<endl;
    }
    else
    {
        B=min(3*A,B);
        int Z=min(X,Y);//move to (Z,Z)
        int cost=2*Z*A;
        int r=max(X,Y)-Z;
        cost+=(r/2)*(A+B);
        if(r%2)
        {
            if(X==Z)
            {
                cost+=B;
            }
            else
            {
                cost+=A;
            }
        }
        cout<<cost<<endl;
    }
}

补题

D

Problem Statement

A murder occurred at a certain mansion. There are $N$ suspects, called person $1$, person $2$, $\dots$, person $N$.

Person $i$ entered the mansion at time $S_i$, left the mansion at time $T_i$, and did not enter or leave at any other times.

The following facts are known about the crime:

• There are exactly two culprits.
• The crime started at some integer time $x$, took $D$ units of time, and was completed at time $x + D$.
• Both culprits were in the mansion at all times from the start to the completion of the crime. (They may have entered the mansion exactly when the crime started, or left exactly when it was completed.)

Assuming that both culprits are among the $N$ suspects, how many combinations of the two culprits and the crime start time are possible? Here, the order of the two culprits does not matter.

分析：

需要求有多少对嫌疑人同时在房间中呆了D时长。
！！！需要额外注意不同的开始时间算不同组合！！！
我们设罪犯i对应的时间分别为$(S_i,T_i)$，则他的犯罪开始时间可能为$[S_i,T_i-D]$。

思路：

用差分维护所有嫌疑人可能开始犯罪的时间后，按时间遍历，如果该点可能的嫌疑人数X不小于2，则有$\binom{X}{2}$种可能。累计答案即可。

Code

void sol()
{
    int N,D;
    cin>>N>>D;
    int res=0;
    vector<int>T(1e6+1,0);
    for(int i=1;i<=N;i++)
    {
        int s,t;
        cin>>s>>t;
        if(s+D>t)continue;
        T[s]++;
        T[t-D+1]--;
    }
    int sum=0;
    for(int i=1;i<=1e6;i++)
    {
        sum+=T[i];
        if(sum>=2)
        {
            res+=sum*(sum-1)/2;
        }
    }
    cout<<res;
}