目录
牛客网NOIP赛前集训营-普及组（第二场）
A 你好诶加币
B 最后一次
C 选择颜色
D 合法括号序列
牛客网NOIP赛前集训营-提高组（第二场）
A 方差
B 分糖果
C 集合划分
牛客网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 集合划分
神仙题目,弃疗.
