AtCoder Beginner Contest 156

时间:2020-02-23 zdragon 人气:0

https://atcoder.jp/contests/abc156/tasks

A - Beginner

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    //freopen("in.txt","r",stdin);
    int n,r;
    scanf("%d%d",&n,&r);
    if(n>=10) printf("%d\n",r);
    else printf("%d\n",r+100*(10-n));
    return 0;
}

A.cpp

B - Digits

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    //freopen("in.txt","r",stdin);
    int n,k,ans=0;
    scanf("%d%d",&n,&k);
    while(n) {
        n/=k;
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}

B.cpp

C - Rally

题意：在一条直线上，有N个人，分别在Xi位置上，要求找一点使得N个人到该点的距离平方和最小，并输出距离平方和。

数据范围：1<=N，Xi<=100

题解：暴力枚举每一个1~100每个位置即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=105;
int a[N];
int main() {
    //freopen("in.txt","r",stdin);
    int n,ans=1e9;
    scanf("%d",&n);
    for(int i=0,x;i<n;i++) {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=100;i++) {
        int s=0;
        for(int j=0;j<n;j++) {
            s+=(a[j]-i)*(a[j]-i);
        }
        ans=min(ans,s);
    }
    printf("%d\n",ans);
    return 0;
}

C.cpp

D - Bouquet

题意：有n种不同的花，每种一朵，要求至少取1朵但，不能取a朵或b朵花，求能取得方案数（mod 1e9+7)。

数据范围：2<=n<=1e9，1<=a<b<=min(n,2e5)

题解：总方案数-取a朵-取b朵-不取。即为 2^n-C(n,a)-C(n,b)-1。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MD=1e9+7;
int quick_pow(int x,int y) {
    int ans=1;
    while(y) {
        if(y&1) ans=1LL*ans*x%MD;
        y>>=1;
        x=1LL*x*x%MD;
    }
    return ans;
}
void add(int &x,int y) {
    x+=y;
    if(x>=MD) x-=MD;
    if(x<0) x+=MD;
}
int main() {
    //freopen("in.txt","r",stdin);
    int n,a,b;
    scanf("%d%d%d",&n,&a,&b);
    int ans=quick_pow(2,n),s=1;
    add(ans,-1);
    for(int i=1;i<=b;i++) {
        s=1LL*s*(n-i+1)%MD,s=1LL*s*quick_pow(i,MD-2)%MD;
        if(i==a) add(ans,-s);
        if(i==b) add(ans,-s);
    }
    printf("%d\n",ans);
    return 0;
}

D.cpp

E - Roaming

题意：有n个房间，每个房间初始有一个人，每次移动可将一个人移到另一个房间，求k次移动后n个房间的状态数。

数据范围：3<=n<=2e5，2<=k<=1e9

题解:

1.没有房间的人数为0的移法：把1移到2，然后2~3来回移动k-2次，最后在移回1。

2.有且只有一个房间的人数为0的移法：把1移到其它房间，然后在其它房间任意移动。

3.超过一个房间的人数为0的移法：结合上面两种移法即可。

枚举0的个数i，然后就是将i个人分到n-i的房间的子问题。

即为：$\sum_{0}^{min(k,n-1)}C_{n}^{i}*C_{n-1}^{i}$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e5+5;
const int MD=1e9+7;
int f[N],inv[N];
int quick_pow(int x,int y) {
    int ans=1;
    while(y) {
        if(y&1) ans=1LL*ans*x%MD;
        y>>=1;
        x=1LL*x*x%MD;
    }
    return ans;
}
int C(int n,int m) {
    return 1LL*f[n]*inv[m]%MD*inv[n-m]%MD;
}
void add(int &x,int y) {
    x+=y;
    if(x>=MD) x-=MD;
}
void init() {
    f[0]=1;
    for(int i=1;i<N;i++) f[i]=1LL*f[i-1]*i%MD;
    inv[N-1]=quick_pow(f[N-1],MD-2);
    for(int i=N-2;i>=0;i--) inv[i]=1LL*inv[i+1]*(i+1)%MD;
}
int main() {
    //freopen("in.txt","r",stdin);
    init();
    int n,k,ans=0;
    scanf("%d%d",&n,&k);
    k=min(k,n-1);
    for(int i=0;i<=k;i++) {
        add(ans,1LL*C(n,i)*C(n-1,i)%MD);
    }
    printf("%d\n",ans);
    return 0;
}

E.cpp

F - Modularness

题意：有k个非负整数di，q个查询，每次查询给三个整数n，x，m，构造出一个长度为n的序列，其中:

$a_{0}=x,a_{i}=a_{i-1}+d_{(i-1) mod k}$，输出存在多少个下标i（0<=i<n-1）满足$a_{i} mod m <a_(i+1) mod m$。

数据范围：1<=k,q<=5000，0<=di,xi<=1e9，2<=ni,mi<=1e9。

题解：

加载全部内容