牛客网NOIP赛前集训营-普及组（第二场）

题目链接:https://www.nowcoder.com/acm/contest/165#question

A 你好诶加币

设最大值为maxx,最小值为minn
分三种情况:
(1.a > 0 且b > 0)
会加爆long long,所以化简式子
(maxx - a >= b)
(2.a < 0 且b < 0)
会加爆long long,所以化简式子
(minn - b <= a)
(3.剩下的情况)
直接输出yes
CODE

#include <iostream>
#include <cstdio>
#define ll long long

ll maxx = 9223372036854775807,minn = -9223372036854775808;

bool calc(ll a,ll b) {
    if(a > 0 && b > 0) {
        if(maxx - b < a) return false;
        return true;
    }
    if(a < 0 && b < 0)
        if(minn - b <= a) return false;
        return true;
    }
    return true;
}

int main() {
    std::cin >> a >> b;
    if(calc(a,b)) {
        std::cout << a + b;
    }
    else puts(""hello, %lld\n"");
    return 0;
}

B 最后一次

直接从n往低处枚举(sqrt{i})判断素数即可.
因为素数的密度大概在(1 / ln n)
所以期望(logn)左右.
所以不会超时.
CODE

#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long

bool calc(ll x) {
    ll q = sqrt(x);
    for(int i = 2;i <= q;++ i) {
        if(x % i == 0) return false;
    }
    return true;
}

int main() {
    ll n;
    std::cin >> n;
    for(ll i = n;i >= 2;-- i) {
        if(calc(i)) {
            std::cout << i;
            return 0;
        }
    }
    return 0;
}

C 选择颜色

结论题吧,即使在考试中看出组合+奇偶讨论一下,但是当时时间不够..
日后再做也还是不会做.
直接放结论吧.
((c-1)^n +(c-1)*-1^n)
当然也可反向推递推式.
(f(n)=(c-2)*f(n-1) + (c-1)*f(n-2))
这个博主讲解的非常好,不过式子有问题,正确的式子应该是上面这个.
然后用矩阵快速幂求.
CODE

#include<cstdio>
#include<iostream>
using namespace std;
int fastpow(int a, int p,int mod)
{
    int base = 1;
    while(p)
    {
        if(p & 1)base = (base * a) % mod;
        a = (a * a) % mod; p >>= 1;
    }
    return base;
}
int main()
{
    int n,c,p;
	    cin >> n >> c;
    p = 10007;
    int ans;
    cout << fastpow(c - 1, n, p) + (c - 1) * fastpow(-1, n, p);
    return 0;
}

D 合法括号序列

DP,暂时不想做.放到以后做.

牛客网NOIP赛前集训营-提高组（第二场）

题目链接:https://www.nowcoder.com/acm/contest/173#question

A 方差

化简式子,不能出现除的形式,不然会有精度问题.

[m^2dfrac{1}{m}astsum_i^m(b_i-overline{b})^2 ]

[mastsum_i^m(b_i-overline{b})^2 ]

[mastsum_i^m{b_i}^2 - 2 ast b_i overline{b} + overline{b}^2 ]

拆开.

[m*({b_1}^2 + {b_2}^2 + {b_3}^2 + ...{b_m}^2) - 2*m* overline{b}ast (b_1+b_2+b_3+....b_m) + m^2*overline{b} ]

设(sum)为(b_1+b_2+...b_m)
折(sum2)为({b_1}^2 + {b_2}^2 + {b_3}^2 + ...{b_m}^2)
则(overline{b} = dfrac{sum}{m})
带入
(m * sum2 - 2 * sum^2+ sum^2)
(m * sum2 - sum ^ 2)
其中先算出(sum = b_1+b_2+....b_n)
然后直接减去那个值就好.
sum2同理
那么时间复杂度就是(O(n))的

#include <iostream>
#include <cstdio>
#define ll long long
const int maxN = 1e5 + 7;

int n;
ll a[maxN];
ll sum1,sum2;

inline ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9') {x =  x * 10 + c - '0';c = getchar();}
    return x * f;
}

int main() {
    scanf("%d",&n);
    int m = n - 1;
    for(int i = 1;i <= n;++ i) 
    	a[i] = read();
   	for(int i = 1;i <= n;++ i) {
   		sum1 += a[i];
   		sum2 += a[i] * a[i];
   	}
   	for(int i = 1;i < n;++ i) 
   		printf("%lld ", (ll)m * (sum2 - a[i] * a[i]) - (sum1 - a[i]) * (sum1 - a[i]));
  	printf("%lld
", (ll)m * (sum2 - a[n] * a[n]) - (sum1 - a[n]) * (sum1 - a[n]));
}

B 分糖果

不会,但是部分分就是,当所有的(a_i)相等时,就成了PJ组的C题.
(n≤4)直接dfs.
(n <= 100, a_i <= 20)
(n <= 100, a_i <= 100)
这部分数据就是DP.
我不会.
放20分的吧.

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int maxN = 1e6 + 7;

int n;
int a[maxN];
int b[maxN];
int cnt;

inline int read() {
	int x = 0,f = 1;char c = getchar();
	while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
	while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
	return x * f;
}

ll power(ll a,int b)
{
	ll ans = 1;
    for(ll now = a;b;b >>= 1,now = now * now % mod) {
    	if(b & 1) ans = ans * now % mod;
    }
    return ans % mod;
}

void dfs(int now) {
	if(now == n + 1) {
		if(b[1] != b[n]) cnt ++;
		return;
	}
	for(int i = 1;i <= a[now];++ i) {
		b[now] = i;
		if(b[now] != b[now - 1])
			dfs(now + 1);
	}
	return ;
}

int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i) {
		a[i] = read();
	}
	dfs(1);
	cout << cnt;
    return 0;
}

C 集合划分

神仙题目,弃疗.