亲宝软件园·资讯

展开

AtCoder Beginner Contest 156

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。

题解:

加载全部内容

相关教程
猜你喜欢
用户评论