2020牛客寒假算法基础集训营2

A.做游戏

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
LL A,B,C,X,Y,Z;
int main()
{
    cin>>A>>B>>C>>X>>Y>>Z;
    cout<<min(A,Y)+min(B,Z)+min(C,X)<<endl;
    return 0;
}

B.排数字

#include "bits/stdc++.h"
using namespace std;
string s;
int n;
int main()
{
    cin>>n;
    cin>>s;
    int x=0,y=0;
    for(auto ch:s){
        if(ch=='6') x++;
        if(ch=='1') y++;
    }
    cout<<min(x-1,y)<<endl;
}

C.算概率

分析： $dp(i,j)$ 代表前i道题做对j道的概率，显然我们可以得到 $dp(i,j)=dp(i-1,j-1) \times P_i+dp(i-1,j) \times (1-P_i)$

#include "bits/stdc++.h"
using namespace std;
const int maxn=2000+10;
typedef long long LL;
const LL mod=1e9+7;
int n;
LL p[maxn],dp[maxn][maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        dp[i][0]=dp[i-1][0]*(1-p[i]+mod)%mod;
        for(int j=1;j<=i;j++){
            dp[i][j]=((dp[i-1][j]*(1-p[i]+mod)%mod)+(dp[i-1][j-1]*p[i]%mod))%mod;
        }
    }
    for(int i=0;i<=n;i++) printf("%lld ",dp[n][i]);
    printf("\n");
    return 0;
}

D.数三角

分析：首先三点不共线，然后 $a^2+b^2<c^2$

#include "bits/stdc++.h"
using namespace std;
const int maxn=500+10;
const double eps=1e-9;
int n;
struct node{
    double x,y;
}p[maxn];
double dp[maxn][maxn];
double v[5];
void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            dp[i][j]=((p[i].x-p[j].x)*(p[i].x-p[j].x))+((p[i].y-p[j].y)*(p[i].y-p[j].y));
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    if(n<3){
        printf("0\n");
        return 0;
    }
    init();
    int cnt=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((p[i].y-p[k].y)*(p[i].x-p[j].x)-((p[i].x-p[k].x)*(p[i].y-p[j].y))==0) continue;
                v[0]=dp[i][j];
                v[1]=dp[i][k];
                v[2]=dp[j][k];
                sort(v,v+3);
                if(v[0]+v[1]<v[2]) cnt++;
            }
        }
    }
    printf("%d\n",cnt);
    return 0;
}

E.做计数

分析：化成 $i+j+2 \sqrt{ i \times j}=k$ ，所以只需要 $i \times j$ 为完全平方数，所以就是统计不超过n的所有完全平方数的所有因子数

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
LL n;
int main()
{
    scanf("%lld",&n);
    LL cnt=0;
    for(LL i=1;i*i<=n;i++){
        LL tmp=i*i;
        for(LL j=1;j*j<=tmp;j++){
            if(tmp%j==0){
                if(j*j==tmp) cnt++;
                else cnt+=2;
            }
        }
    }
    printf("%lld\n",cnt);
    return 0;
}

F.拿物品

分析：牛牛选取一个增加 $a_i$ ，相当于牛可乐消耗一个，失去 $b_i$ ，所以我们按照 $a_i+b_i$ 进行贪心即可

#include "bits/stdc++.h"
using namespace std;
const int maxn=2e5+100;
int n;
struct node{
    int a,b,id,sum;
}p[maxn];
bool cmp(node x,node y){
    return x.sum>y.sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&p[i].a);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i].b);
        p[i].id=i;
        p[i].sum=p[i].a+p[i].b;
    }
    sort(p+1,p+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(i%2) printf("%d ",p[i].id);
    }
    printf("\n");
    for(int i=1;i<=n;i++){
        if(i%2==0) printf("%d ",p[i].id);
    }
    printf("\n");
    return 0;
}

G.判正误

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+8;
int T;
LL a,b,c,d,e,f,g;
LL quickmod(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int main()
{
    cin>>T;
    while(T--){
        cin>>a>>b>>c>>d>>e>>f>>g;
        g%=mod;
        if(((quickmod(a,d)+quickmod(b,e))%mod+quickmod(c,f))%mod==g){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}

H.施魔法

分析：对于当前位置i，有种决策，一种是作为前一段的尾，即 $dp(i-1)+a(i)-a(i-1)$ ，还有一种是新起一段

$dp(i-k)+a(i)-a(i-k+1)$ ，二者取最小值就好了，注意从1到K开始往后枚举时，只能作为前一段的尾。

#include "bits/stdc++.h"
using namespace std;
const int maxn=3e5+100;
typedef long long LL;
int n,k;
LL a[maxn],dp[maxn];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=k;i++) dp[i+k-1]=a[i+k-1]-a[1];
    for(int i=2*k;i<=n;i++) dp[i]=min(dp[i-1]+a[i]-a[i-1],dp[i-k]+a[i]-a[i-k+1]);
    printf("%lld\n",dp[n]);
    return 0;
}

I.建通道

分析：首先对点去重，得到去重之后的点数m。我们枚举最低位k，使得在其中存在 $v_i$ 使得该位为0，存在 $v_j$ 使得该位为1。然后让所有为0的跟 $v_j$ 连，让所有为1的跟 $v_i$ 连

#include "bits/stdc++.h"
using namespace std;
int n;
int main()
{
    set<int>s;
    scanf("%d",&n);
    int v0=0,v1=pow(2,31)-1;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        v0|=x;
        v1&=x;
        s.insert(x);
    }
    int v=v0^v1;
    int ans=0;
    for(int i=0;i<=30;i++){
        int tmp=1<<i;
        if(tmp&v){
            ans=tmp*(s.size()-1);
            break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

J.求函数

分析：把式子化开，就得到如下形式： $\prod_{i=l}^r k_i+ \sum_{i=l}^rb_i \prod_{j=i+1}^r k_j$ 。于是我们可以把区间 $[l,r]$ 分成两段 $[l,r_1][r_1+1,r]$ 。于是令 $\prod_{i=l_1}^{r_1}k_i=m_1,\prod_{i=r_1+1}^rk_i=m_2$ ， $\sum_{i=l}^{r_1}b_i \prod_{j=i+1}^{r_1} k_j=n_1， \sum_{i=r_1+1}^rb_i \prod_{j=i+1}^r k_j=n_2$

所以 $m_1 \times m_2+ n_1 \times m_2+n_2$

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=2e5+10;
const LL mod=1e9+7;
int n,m;
LL b[maxn],k[maxn];
struct node{
    int l,r;
    LL k,b;
}tree[maxn<<2];
void pushup(int rt){
    tree[rt].k=tree[rt<<1].k*tree[rt<<1|1].k%mod;
    tree[rt].b=(tree[rt<<1].b*tree[rt<<1|1].k+tree[rt<<1|1].b)%mod;
}
void build(int l,int r,int rt){
    tree[rt].l=l,tree[rt].r=r;
    if(l==r){
        tree[rt].k=k[l];
        tree[rt].b=b[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int id,int rt,LL k1,LL b1){
    if(tree[rt].l==tree[rt].r){
        tree[rt].k=k1,tree[rt].b=b1;
        return;
    }
    int mid=(tree[rt].l+tree[rt].r)>>1;
    if(id<=mid) update(id,rt<<1,k1,b1);
    else update(id,rt<<1|1,k1,b1);
    pushup(rt);
}
pair<LL,LL> query(int l,int r,int rt){
    if(tree[rt].l==l&&tree[rt].r==r) return make_pair(tree[rt].k,tree[rt].b);
    int mid=(tree[rt].l+tree[rt].r)>>1;
    if(r<=mid) return query(l,r,rt<<1);
    else if(l>mid) return query(l,r,rt<<1|1);
    else return make_pair(query(l,mid,rt<<1).first*query(mid+1,r,rt<<1|1).first%mod,
                (query(l,mid,rt<<1).second*query(mid+1,r,rt<<1|1).first+query(mid+1,r,rt<<1|1).second)%mod);
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&k[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
    build(1,n,1);
    while(m--){
        int op,i,l,r;
        LL k1,b1;
        scanf("%d",&op);
        if(op==1){
            scanf("%d%lld%lld",&i,&k1,&b1);
            update(i,1,k1,b1);
        }else{
            scanf("%d%d",&l,&r);
            pair<LL,LL> tmp=query(l,r,1);
            printf("%lld\n",(tmp.first+tmp.second)%mod);
        }
    }
    return 0;
}