2021 BUAA Winter Training 2赛后补题

2021 BUAA Winter Training 2

${A\ -\ Tricky\ Alchemy}$ ${\scriptstyle [\ CodeForces\ -\ 912A\ ]}$

题意

有黄、蓝三种颜色的颜料各A,B个，要求合成黄、绿、蓝三种颜色各x,y,z个，求一共还需要多少个颜料。

黄色消耗两个黄色颜料，蓝色消耗三个蓝色颜料，绿色消耗黄色颜料和蓝色颜料各一个。

解法

很简单的分开求即可。

注意不能一起求，为了这我还 $WA\times 2$ ，简直药丸。。。

附代码：

#include
#include
#include
using namespace std;
long long a,b,x,y,z,ans1,ans2;
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
void solve(){
    a=read();b=read();x=read();y=read();z=read();
    ans1=(x*2+y-a);ans2=(y+z*3-b);
    if(ans1<0)ans1=0;
    if(ans2<0)ans2=0;
    printf("%lld\n",ans1+ans2);
}
int main(){
    solve();
    return 0;
}

$\text{ }$

${B\ -\ The\ Meaningless\ Game}$ ${\scriptstyle [\ CodeForces\ -\ 833A\ ]}$

题意

每局游戏一开始两个人的分都是 $1$ ，之后多轮游戏，每轮选择一个数 $k$ ，赢的人分数乘上 $k^2$ ，输的人乘上 $k$ 。

现在给出 $n$ 组结果，问每组结果是否可能存在。

解法

我们发现如果这组结果 ${a,b}$ 存在，那么 $a\times b$ 一定是某个数的三次方。

所以我们只要判断 $a\times b$ 是否能开出三次方整数根即可。
附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
long long a,b,c;
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
int main(){
    int t=read();
    while(t--){
        a=read();b=read();
        c=round(pow(1.000*(a*b),1.000/3.000));
        if(c*c*c==a*b&&a%c==0&&b%c==0)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

$\text{ }$

${C\ -\ An\ Ordinary\ Game}$ ${\scriptstyle [\ AtCoder\ -\ arc064\underline\ B\ ]}$

题意

给出一个长度不小于3的字符串，两个人在满足如下条件时轮流取出一个字符：

不能取出字符串两端的字符；
取出的字符两端不能是相同字符。

求最后无路可走的人是先手还是后手。

解法

我们很容易（大雾）发现这个题是个结论题：

当首尾字符相同时：字符串长度为奇数时后手输，为偶数时先手输。
当首尾字符不同时：字符串长度为奇数时先手输，为偶数时后手输。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 100010
using namespace std;
int len;
char str[MAXN];
void solve(){
    scanf("%s",str+1);
    len=strlen(str+1);
    if(str[1]==str[len])printf(len&1?"Second\n":"First\n");
    else printf(len&1?"First\n":"Second\n");
}
int main(){
    solve();
    return 0;
}

$\text{ }$

${D\ -\ Quest}$ ${\scriptstyle [\ CodeForces\ -\ 542F\ ]}$

题意

这个题的题意很麻烦啊。。。

有 $n$ 个任务，每个任务有完成的时间 $t_i$ 和价值 $q_i$ 。

给出总时间 $T$ ，要求选出在 $n$ 个任务中的若干个或者一些空结点，组成一颗二叉树，保证：

只有叶子节点是任务；
每个任务的时间 $t_i+$ 这个叶子节点的深度 $<=T$ 。

求最大的价值。

$n<=1000,T<=100$

解法

将这些任务按照 $t_i$ 分组，然后从小到大扫描一遍所有时间，这就相当于从叶子一直扫到树根。

对于每个时间 $t$ 的组，把组内元素按照价值从大到小排序，依次取两个价值最大的节点合成上一层的节点，也就是 $t+1$ 组。

最后时间为 $T$ 的组的第一个元素就是答案。

用 $vector$ 或者优先队列都可以。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#define MAXN 110
using namespace std;
int n,m;
vector<int> a[MAXN];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
void work(){
    for(int i=1;i<=m;i++){
        sort(a[i].begin(),a[i].end(),greater<int>());
        for(int j=0;j<a[i].size();j+=2){
            if(j+1<a[i].size())a[i+1].push_back(a[i][j]+a[i][j+1]);
            else a[i+1].push_back(a[i][j]);
        }
    }
    printf("%d\n",a[m][0]);
}
void init(){
    n=read();m=read();
    for(int i=1,x,y;i<=n;i++){
        x=read();y=read();
        a[x].push_back(y);
    }
}
int main(){
    init();
    work();
    return 0;
}

$\text{ }$

${E\ -\ Buy\ Low\ Sell\ High}$ ${\scriptstyle [\ CodeForces\ -\ 865D\ ]}$

题意

有一支股票，给出 $n$ 天每天的价格，可以选择买进和卖出（卖出时必须有买进的股票），求最后能获得的最大价值是多少。

解法

这是一道神仙烧脑题。。。

因为最后只要求结果，所以中间过程可以不用管。。。（艾姬多娜既视感.jpg）

我们可以在每天都强制买入，然后对于每一天决定是否卖出。

而每一天只要卖出绝对值最小的、已经买过的某一天的股票，就能获得最大利益。

对于卖出，可以视作买入负价值，所以搞一个大根堆，每天放入两个当天股票价格的相反数（因为取最小的之后还要把这个最小的弹出堆）。

反正就挺神奇的。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
long long ans=0;
priority_queue<int> q;
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
int main(){
    int x,t=read();
    while(t--){
        x=read();
        q.push(-x);
        q.push(-x);
        ans+=x+q.top();
        q.pop();
    }
    printf("%lld\n",ans);
    return 0;
}

$\text{ }$

${F\ -\ Large\ Triangle}$ ${\scriptstyle [\ CodeForces\ -\ 1019D\ ]}$

题意

给出 $n$ 个二维平面上的点的坐标，求是否存在三个点组成的三角形的面积恰好是给定的 $S$ 。

解法

首先这个题是可以 $O(n^3)$ 直接莽过去的。。。

然后正解是个 $O(n^2\log_2n)$ 的二分+旋转坐标系。

我们知道三角形面积 $S=\frac{1}{2}\times d\times h$ 。

那么我们可以 $O(n^2)$ 枚举底边，然后问题就变成了确定高。

我们将点按照 $x,y$ 的顺序从小到大排序，然后顺次枚举点对 $(i,j)$ 形成的直线，并按照极角大小从小到大排序。

然后是核心思想——旋转坐标系：

我们顺次枚举每一条直线 $i$ ，用 $rnk[u]$ 表示以当前直线 $i$ 为 $x$ 轴时点 $u$ 的排名。

这时我们发现：

两个点 $u,v$ 的大小关系只有在选中的直线 $i$ 的斜率越过 $(u,v)$ 的斜率时才会发生改变。

也就是说：

每次枚举的直线 $i$ 只对这条直线上的点 $u,v$ 的大小关系有影响。

所以我们只要把直线上下的点分别二分即可。

剩下的就是一些计算几何的基本操作了（什么叉积、面积、极角啥的）

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 2010
#define MAXM 4000010
#define MAX (1LL<<62)
using namespace std;
int n,m=0,id[MAXN],rnk[MAXN];
long long S;
struct Point{
    long long x,y;
    friend bool operator <(const Point &u,const Point &v){
        return u.x==v.x?(u.y<v.y):(u.x<v.x);
    }
    friend Point operator +(const Point &u,const Point &v){
        Point ret;
        ret.x=u.x+v.x;ret.y=u.y+v.y;
        return ret;
    }
    friend Point operator -(const Point &u,const Point &v){
        Point ret;
        ret.x=u.x-v.x;ret.y=u.y-v.y;
        return ret;
    }
}point[MAXN],ans[4];
struct Line{
    int u,v;
    double k;
    friend bool operator <(const Line &u,const Line &v){
        return u.k<v.k;
    }
}line[MAXM];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline long long read(){
    long long date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
inline long long cross(const Point &u,const Point &v){
    return u.x*v.y-u.y*v.x;
}
inline long long area(const Point &a,const Point &b,const Point &c){
    return fabs(cross(b-a,c-a));
}
inline double slope_alpha(const Point &u,const Point &v){
    return atan2(1.000*(v.y-u.y),1.000*(v.x-u.x));
}
void solve(int u,int v){
    if(rnk[u]>rnk[v])swap(u,v);
    int l=1,r=rnk[u]-1,mid;
    long long s;
    while(l<=r){
        mid=l+r>>1;
        s=area(point[id[mid]],point[u],point[v]);
        if(s==S){
            ans[1]=point[id[mid]];
            ans[2]=point[u];ans[3]=point[v];
        }
        if(s>=S)l=mid+1;
        else r=mid-1;
    }
    l=rnk[v]+1;r=n;
    while(l<=r){
        mid=l+r>>1;
        s=area(point[id[mid]],point[u],point[v]);
        if(s==S){
            ans[1]=point[id[mid]];
            ans[2]=point[u];ans[3]=point[v];
        }
        if(s>=S)r=mid-1;
        else l=mid+1;
    }
    swap(id[rnk[u]],id[rnk[v]]);swap(rnk[u],rnk[v]);
}
void work(){
    ans[1].x=MAX;
    for(int i=1;i<=m;i++)solve(line[i].u,line[i].v);
    if(ans[1].x==MAX)printf("No\n");
    else{
        printf("Yes\n");
        for(int i=1;i<=3;i++)printf("%lld %lld\n",ans[i].x,ans[i].y);
    }
}
void init(){
    n=read();S=read()*2;
    for(int i=1;i<=n;i++){
        point[i].x=read();point[i].y=read();
        id[i]=rnk[i]=i;
    }
    sort(point+1,point+n+1);
    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
        m++;
        line[m].u=i;line[m].v=j;
        line[m].k=slope_alpha(point[i],point[j]);
    }
    sort(line+1,line+m+1);
}
int main(){
    init();
    work();
    return 0;
}

$\text{ }$

${G\ -\ New\ Year\ and\ Original\ Order}$ ${\scriptstyle [\ CodeForces\ -\ 908G\ ]}$

题意

$S(n)=\text{把n的所有数位上的数从小到大排序，重组成新的数}$

求：

$\sum_{i=1}^n S(i)$

解法

因为各位数字顺序重排，所以我们考虑将美味数字的贡献分开。

煮个栗子：

$\begin{array}{rcl}112233336679&\\=111111111111&&+\\1111111111&&+\\11111111&&+\\1111&\times 3&+\\11&&+\\1&\times 2&\end{array}$

其中 $\times 3,\times 2$ 是乘上前后数字的差值。

对于每一行，都对应一位数字 $k$ ，而贡献是这么算的：

设所有数位上的数中大于等于 $k$ 的数字有 $m$ 个，则贡献就是 $m$ 个 $1$ 再乘上前后数字的差值 $\Delta$ ，即：

$\underbrace{111\ldots11}_{m\text{位}}\times \Delta$

这样来看，数位 $DP$ 呼之欲出啊。。。

设 $dp[i][j][k][lim]$ 表示前 $i$ 位中有 $j$ 位数大于等于 $k$ 的方案数， $lim$ 表示是否卡上界。

转移的时候枚举第 $i+1$ 位填了 $g$ ，方程就是： $dp[i+1][j+(g>=k)][k][lim]=\sum dp[i][j][k][lim]$

然后前 $n$ 位有 $i$ 个数字大于等于 $k$ 的方案数就是 $sum[i]=dp[n][i][k][0]+dp[n][i][k][1]$ ，对答案的贡献就是 $sum[i]\times \underbrace{111\ldots11}_{i\text{位}}$

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 710
#define MOD 1000000007LL
using namespace std;
int n;
long long now=1,ans=0,dp[MAXN][MAXN][9][2];
char str[MAXN];
void solve(){
    scanf("%s",str+1);
    n=strlen(str+1);
    for(int i=1;i<=9;i++)dp[0][0][i][1]=1;
    for(int i=0;i<n;i++)for(int j=0;j<=n;j++)for(int k=1;k<=9;k++)for(int l=0;l<=1;l++)if(dp[i][j][k][l]){
        int f=(l?str[i+1]-'0':9);
        for(int g=0;g<=f;g++)dp[i+1][j+(g>=k)][k][l&(g==f)]=(dp[i+1][j+(g>=k)][k][l&(g==f)]+dp[i][j][k][l])%MOD;
    }
    for(int i=1;i<=n;i++,now=(now*10%MOD+1)%MOD)for(int k=1;k<=9;k++)ans=(ans+now*((dp[n][i][k][0]+dp[n][i][k][1])%MOD)%MOD)%MOD;
    printf("%lld\n",ans);
}
int main(){
    solve();
    return 0;
}