牛客网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^2\dfrac{1}{m}\ast\sum_i^m(b_i-\overline{b})^2
\]

\[m\ast\sum_i^m(b_i-\overline{b})^2
\]

\[m\ast\sum_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\n", (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集合划分

神仙题目,弃疗.

第二场