2020牛客寒假算法基础集训营2（全解）

题目链接：https://ac.nowcoder.com/acm/contest/3003#question
此篇文章的博客园链接：https://www.cnblogs.com/lonely-wind-/p/12271400.html
emmm,没什么好说的，心理战。。。不交一发就不会知道这样确实是对的。。。

题目说明：

A.做游戏 B.排数字 C.算概率 D.数三角
（水题）（思维）（期望DP）（思维,勾股定理）

E.做计数 F.拿物品 G.判正误 H.施魔法
（思维）（贪心）（类hash）（DP）

I.建通道 J.求函数
（思维）（线段树）

A.做游戏

没什么好说的，水题，每次取相克的最小值就好了，即 $ans=min(A,Y)+min(B,Z)+min(C,X)$ 。
以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(int argc, char const *argv[])
{
    ll a,b,c,x,y,z;
    cin>>a>>b>>c;
    cin>>x>>y>>z;
    ll sum=0;
    sum+=min(a,y);
    sum+=min(b,z);
    sum+=min(c,x);
    cout<<sum<<endl;
    return 0;
}

B.排数字

也没什么好说的，我们看一下 $6161616$ 就知道这是最多的情况，那么6的数量会比1多1个。。所以我们统计一下1的个数和6的个数就好了。
以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mac=2e5+10;

char s[mac];

int main(int argc, char const *argv[])
{
    int n;
    scanf ("%d",&n);
    scanf ("%s",s+1);
    int one=0,six=0;
    for (int i=1; i<=n; i++){
        if (s[i]=='1') one++;
        else if (s[i]=='6') six++;
    }
    if (six>=one+1) printf("%d\n",one);
    else {
        if (six>=2) printf("%d\n",six-1);
        else printf("0\n");
    }
    return 0;
}

C.算概率

看一下题目，应该是期望DP，然后再看一下数据范围。。。 $n<=2000$ ，那么应该是 $n^{2}$ 算法，那么我们就设 $dp[i][j]$ 这个为一个状态，那么他具体代表什么意思呢？肯定有一个是答对的题目数量，我们将它放在 $j$ 位置，那么很明显 $i$ 就代表了已经答的题目数量。

那么怎么状态转移呢？正在答的这一题可能答对也可能答错,那么也就是说 $dp[i][j]=dp[i-1][j]*(1-p)+dp[i-1][j-1]*p$
以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mac=2e3+10;
const int mod=1e9+7;

ll dp[mac][mac],a[mac];

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i];
    dp[0][0]=1;
    for (int i=1; i<=n; i++){
        dp[i][0]=dp[i-1][0]*((1-a[i]+mod)%mod)%mod;
        for (int j=1; j<=i; j++){
            dp[i][j]=dp[i-1][j]*((1-a[i]+mod)%mod)%mod;
            dp[i][j]+=dp[i-1][j-1]*a[i]%mod;
            dp[i][j]%=mod;
        }
    }
    for (int i=0; i<=n; i++)
        cout<<dp[n][i]<<' ';
    cout<<endl;
    return 0;
}

D.数三角

emmm，就是用到了勾股定理，一个直角三角形 $c^{2}=a^{2}+b^{2}$ ，我们将斜边延长一些，那么不就变成了钝角了吗。

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mac=600;

struct node
{
    int x,y;
}pt[mac];

ll dist(int p1,int p2)
{
    ll x1=pt[p1].x,x2=pt[p2].x;
    ll y1=pt[p1].y,y2=pt[p2].y;
    ll dis=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    return dis;
}

int angle(ll mx,ll mid,ll mi)
{
    double s1=sqrt(mx*1.0),s2=sqrt(mid*1.0),s3=sqrt(mi*1.0);
    if (s1<s2+s3) return 1;
    return 0;
}

int ok(int id1,int id2,int id3)
{
    ll eg1=dist(id1,id2);
    ll eg2=dist(id1,id3);
    ll eg3=dist(id2,id3);
    ll mx=max(eg1,max(eg2,eg3));
    ll mi=min(eg1,min(eg2,eg3));
    ll mid=eg1+eg2+eg3-mx-mi;
    if (!angle(mx,mid,mi)) return 0;
    if (mx>mi+mid) return 1;
    return 0;
}

int main(int argc, char const *argv[])
{
    int n;
    scanf ("%d",&n);
    for (int i=1; i<=n; i++){
        scanf ("%d%d",&pt[i].x,&pt[i].y);
    }
    int ans=0;
    for (int i=1; i<=n; i++)
        for (int j=i+1; j<=n; j++)
            for (int k=j+1; k<=n; k++){
                if (ok(i,j,k)) ans++;
            }
    printf("%d\n",ans);
    return 0;
}

E.做计数

我们做个变形就出来了，两边同时平方： $i+j+2\sqrt{ij}=k$ 那么要维持正整数， $ij$ 必须是平方数，即 $\sqrt{ij}$ 是个整数。那么我们只需要枚举1到 $\sqrt{n}$ 设为 $i$ 然后找 $i^{2}$ 的因子就好了，复杂度是 $O(\sqrt{n}*\sqrt{n})$

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

int solve(int x)
{
    if (x==1) return 1;
    int m=sqrt(x);
    int sum=1;
    for (int i=1; i<m; i++){
        if (x%i==0) sum+=2;
    }
    return sum;
}

int main(int argc, char const *argv[])
{
    int n;
    cin>>n;
    int m=sqrt(n);
    long long ans=0;
    for (int i=1; i<=m; i++){
        ans+=solve(i*i);
    }
    cout<<ans<<endl;
    return 0;
}

F.拿物品

实际上就是按照 $（a+b）$ 的值贪心。至于为什么，出题人很良心的说明了：
假设物品已经被选完，此时牛牛选择的物品 $A$ 属性的价值和是 $N$ ，牛可乐选择的物品 $B$ 属性价值和是 $M$ 。
如果牛牛的 $(a_{1},b_{1})$ 物品与牛可乐的 $(a_{2},b_{2})$ 交换，则 $N′=N−a_{1}+a_{2},M′=M+b_{1}−b_{2}$
对于牛牛（目标是最大化 $N−M$ ）来说会变得更优仅当 $a_{1}+b_{1}<a_{2}+b_{2}$ （ $N′−M′>N−M$ 化简就能得到），
对于牛可乐也一样。所以两人都会优先选择 $a_{i}+bi_{i}$ 最大的物品。
以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

const int mac=2e5+10;

struct node
{
    int val,id;
    bool operator <(const node&a)const{
        return val>a.val;
    }
}p[mac];

int main(int argc, char const *argv[])
{
    int n;
    scanf ("%d",&n);
    for (int i=1; i<=n; i++)
        scanf ("%d",&p[i].val),p[i].id=i;
    int x;
    for (int i=1; i<=n; i++)
        scanf ("%d",&x),p[i].val+=x;
    sort(p+1,p+1+n);
    for (int i=1; i<=n; i+=2)
        printf("%d ",p[i].id);
    printf("\n");
    for (int i=2; i<=n; i+=2)
        printf("%d ",p[i].id);
    printf("\n");
    return 0;
}

G.判正误

万万没想到确是是一种取模处理的方式。。。原式取模的意义下，有概率成立，我们可以多取几个模提高真确率。。。

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mac=2e3+10;
const ll mod=1e9+7;

ll qick(ll a,ll b)
{
    a%=mod;
    ll ans=1;
    while (b){
        if (b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a,b,c,d,e,f,g;
    int t;
    cin>>t;
    while (t--){
        cin>>a>>b>>c>>d>>e>>f>>g;
        ll ans1=qick(a,d);
        ll ans2=qick(b,e);
        ll ans3=qick(c,f);
        ll ans=ans1+ans2+ans3;
        if (ans==g) printf("Yes\n");
        else printf("No\n");
    }
}

H.施魔法

将能量排个序，我们可以知道的是每次释放魔法一定是选择连续的一段的。那么我们就可以做一个dp: $dp[i]=min_{j\in[1,i-k+1]}(f_{j-1}+a_{i}-a_{j})$ 即：

dp[m]=a[m]-a[1];
for (int i=m+1; i<=n; i++){
     for (int j=1; j<=i-m+1; j++){
          dp[i]=min(dp[i],dp[j-1]+a[i]-a[j]);
     }
}

但怎么将其化为更低的复杂度呢？我们可以发现 $dp[j-1]-a[j]$ 其实很好维护它的前缀最小值的，我们只需要在每次加一个点的时候更新就好了：
以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mac=3e5+10;
const ll inf=1e18;

int a[mac];
ll dp[mac];

int main()
{
    int n,m;
    scanf ("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
        scanf ("%d",&a[i]);
    sort(a+1,a+1+n);
    memset(dp,0x3f,sizeof dp);
    ll f=-a[1];
    for (int i=m; i<=n; i++){
        dp[i]=f+a[i];
        f=min(f,dp[i-m+1]-a[i-m+2]);
    }
    printf("%lld\n",dp[n]);
    return 0;
}

I.建通道

我觉得出题人说道挺清楚的。。。首先将权值去重（权值相等的点连接代价为 0 ），设去重后有 m 个点，接下来找到最小的二进制位k ，
满足存在 $v_{i}$ 的这个二进制位是 0 且存在 $v_{j}$ 的这个二进制位是1，答案就是 $2k(m−1)$ （相当于所有这位是 0 的点与 j点连边，是1 的点与 i 点连边）。
以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

const int mac=2e5+10;
typedef long long ll;

int a[mac];

int deal(int x,int pw)
{
    x>>=pw;
    if ((x&1)==0) return 1;
    return 0;
}

int main(int argc, char const *argv[])
{
    int n;
    scanf ("%d",&n);
    for (int i=1; i<=n; i++)
        scanf ("%d",&a[i]);
    sort(a+1,a+n+1);
    int p=unique(a+1,a+1+n)-a-1;
    int tmp=1;
    int m0=0,m1=0;
    ll ans=0;
    for (int i=0; i<=30; i++){
        if (i) tmp*=2;
        m0=0;m1=0;
        for (int j=1; j<=p; j++){
            if (!deal(a[j],i)) m1=1; 
            else if (deal(a[j],i)) m0=1;
            if (m0 && m1) {
                ll ans=1ll*tmp*(p-1);
                printf("%lld\n",ans);
                return 0;
            }
        }
    }
    printf ("0\n");
    return 0;
}

J.求函数

题目大意：你有n个一次函数，第i个为： $f_{i}(x)=k_{i}\times x+b_{i}$ ，你有m次操作：
1 i k b 将 $f_{i}(x)$ 修改为 $f_{i}(x)=k\times x+b$
2 l r 求 $f_{r}(f_{r-1}(\cdots (f_{l+1}(f_{l}))\cdots))$
emmm，就这么看询问的话不好看，我们将它放出来就是： $\prod_{i=l}^{r}k_i+\sum_{i=l}^{r}b_{i}\prod_{j=i+1}^{r}k_{j}$
然后我们用线段树维护就好了，不过我们需要注意合并相邻节点 $[l_{1},r_{1}][l_{2},r_{2}]$
我们假设t1维护 $\prod_{i=l}^{r}k_i$ , t2维护 $\sum_{i=l}^{r}b_{i}\prod_{j=i+1}^{r}k_{j}$
假设t1左子树为 $n_{1}$ ，t1的右子树为 $n_{2}$ ，t2左子树为 $m_{1}$ ,t2右子树为 $m_{2}$
那么合并之后为 $\prod k_{i}=n_{1}\times n_{2},\sum b_{i}\prod k_{j}=m_{1}\times n_{2}+m_{2}$

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define lc rt<<1
#define rc rt<<1|1

typedef long long ll;
const int mac=2e5+10;
const int mod=1e9+7;

struct node
{
    ll valk,valkb;
}tree[mac<<2];
int k[mac],b[mac];

void push_up(int rt)
{
    tree[rt].valk=tree[lc].valk*tree[rc].valk%mod;
    tree[rt].valkb=tree[lc].valkb*tree[rc].valk%mod+tree[rc].valkb;
    tree[rt].valkb%=mod;
}

void build(int l,int r,int rt)
{
    if (l==r){
        tree[rt].valk=k[l];
        tree[rt].valkb=b[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson);build(rson);
    push_up(rt);
}

void update(int l,int r,int rt,int pos,int valk,int valb)
{
    if (l==r){
        tree[rt].valkb=valb;
        tree[rt].valk=valk;
        return;
    }
    int mid=(l+r)>>1;
    if (pos<=mid) update(lson,pos,valk,valb);
    else update(rson,pos,valk,valb);
    push_up(rt);
}

node solve(node s1,node s2)
{
    node sum;
    sum.valk=s1.valk*s2.valk%mod;
    sum.valkb=s1.valkb*s2.valk%mod+s2.valkb;
    sum.valkb%=mod;
    return sum;
}

node query(int l,int r,int rt,int L,int R)
{
    node ans={1,0};
    if (l>=L && r<=R){
        return node{tree[rt].valk,tree[rt].valkb};
    }
    int mid=(l+r)>>1;
    if (L<=mid) ans=solve(ans,query(lson,L,R));
    if (R>mid) ans=solve(ans,query(rson,L,R));
    return ans;
}

int main(int argc, char const *argv[])
{
    int n,m;
    scanf ("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
        scanf ("%d",&k[i]);
    for (int i=1; i<=n; i++) 
        scanf ("%d",&b[i]);
    build(1,n,1);
    while (m--){
        int opt,i,ck,cb,l,r;
        scanf ("%d",&opt);
        if (opt==1){
            scanf ("%d%d%d",&i,&ck,&cb);
            update(1,n,1,i,ck,cb); 
        }
        else {
            scanf ("%d%d",&l,&r);
            node ans=query(1,n,1,l,r);
            ll sum=(ans.valk+ans.valkb)%mod;
            printf("%lld\n",sum);
        }
    }
    return 0;
}