AtCoder Beginner Contest 156 A~~D

A.水题签到

#include<iostream>

using namespace std;

int main(){
	int n,r;
	cin>>n>>r;
	int ans;
	if(n >=10){
		cout<<r<<endl;
	}
	else{
		ans = 100*(10-n);
	cout<<ans+r<<endl;
	}

	
	return 0;
}

B
题意：就是一个数的k进制有多少位

思路：主要是一个进制转换

#include<iostream>

using namespace std;
char ans[205];
int main(){
    long long  N, R, m=0, now;
    long long  num  = 0;
    cin>>N>>R;
    	while(N){
		now = N % R;
		if(now <= 9){
			ans[m++] = '0' + now;    //ASCll表的运用
		}else{
			ans[m++] = 'A' + now - 10;
		}
		
		N /= R;
		
	}
	
	
	if(m == 0)
		cout<<0;
	
	for(int i=m-1; i>=0; i--)    //利用for循环把反序输出成正序
		num++;
		
		cout<<num<<endl;
	return 0;
}

C
题意：就是一个想要开会，不同楼层有不同的人，然后你要找到一个楼层，使得这个楼层减去每个人楼层的平方最小。

思路：一开始拿着题，就想着应该是中位数吧，但是W3，然后又想要不就是平均数或者中位数，两者取小即可，但是W8，最后一像楼层是有范围的，那么这样的话我就直接暴力，不断更新最小值不就行了嘛

#include<iostream>
#include<algorithm>
#include<math.h>

using namespace std;

long long  a[105];

int main(){
	int n;
	cin>>n;
    long long sum;
	long long ans;
	long long  maxx = -0x3f3f3f3f;
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
		maxx = max(maxx,a[i]);
	}
    ans = 0x3f3f3f3f;
	for(int i=1;i<=maxx;i++){
		sum = 0;
		for(int j=1;j<=n;j++){
			sum += (a[j]-i)*(a[j]-i);
		}
		ans = min(ans,sum);
	}
	cout<<ans<<endl;
	
	return 0;
}

D.
题意：就是一个数学组合问题

思路：我一开始想的是回溯法，找到足够的然后记为1，num++，然后在回溯继续寻找。但是太慢了，第二个样例没跑出来…

后来有蒙佬用了同余定理解决了组合问题，orz

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=1e9+7;
ll qmi(ll a, ll k)
{
    ll res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}
 
 
ll C(int a, int b) 
{
    ll res = 1;
    for (ll i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (ll)res * j % p;
        res = (ll)res * qmi(i, p - 2) % p;
    }
    return res;
}
 
 
ll lucas(ll a, ll b)
{
    if (a < p && b < p) return C(a, b);
    return (ll)C(a % p, b % p) * lucas(a / p, b / p) % p;
}
int main()
{
	ll n, a, b;
	cin >>n>>a>>b;
	cout <<(qmi(2,n)-(lucas(n,a)%p+lucas(n,b)%p)%p-1+p)%p<<endl;
}