2020 CCPC网络选拔赛部分题解


1002 Graph Theory Class

题意:给n个结点1,2,…n,i和j之间的边权是lcm(i+1,j+1),问最小生成树边权和
解题思路:让所有结点变成2,3,4…n+1.这样把其中所有质数向2连边,所有合数向它的因子连边。这样答案为[3,n+1]数字和+[3,n+1]质数和。然后套min25板子就行,难点是需要知道min25板子(

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;
int k;
typedef long long LL;

namespace Min25 {

int prime[N], id1[N], id2[N], flag[N], ncnt, m;

LL g[N], sum[N], a[N], T, n;

inline int ID(LL x) {
return x <= T ? id1[x] : id2[n / x];
}

inline LL calc(LL x) {
return x * (x + 1) / 2 - 1;
}

inline void init() {
//for(int i=0;i<N;++i) prime[i]=id1[i]=id2[i]=flag[i]=g[i]=sum[i]=a[i]=0;
ncnt=0;m=0;
T = sqrt(n + 0.5);
for (int i = 2; i <= T; i++) {
if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;
for (int j = 1; j <= ncnt && i * prime[j] <= T; j++) {
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
for (LL l = 1; l <= n; l = n / (n / l) + 1) {
a[++m] = n / l;
if (a[m] <= T) id1[a[m]] = m; else id2[n / a[m]] = m;
g[m] = calc(a[m]) % k;
}
for (int i = 1; i <= ncnt; i++)
for (int j = 1; j <= m && (LL)prime[i] * prime[i] <= a[j]; j++)
g[j] = (g[j] - (((LL)prime[i]%k) * (g[ID(a[j] / prime[i])] - sum[i - 1])%k) +k)%k;
}

inline LL solve(LL x) {
if (x <= 1) return x;
return n = x, init(), g[ID(n)];
}

}

int main() {
int T;
scanf("%d",&T);
while(T--)
{
LL n; scanf("%lld%d", &n,&k);
LL tmp=Min25::solve(n+1);
tmp=(tmp-2+k)%k;
tmp=(tmp+(((3+n+1)%k)*((n-1)%k))/2)%k;
cout<<tmp<<endl;
}
//printf("%lld\n", Min25::solve(n));
}

1003 Express Mail Taking

水题

#include<bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f
#define all(x) (x).begin(),(x).end()
#define PII pair<int,int>
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
#ifdef LOCAL
const int maxn=30;
#else
const int maxn=1e6+5;
#endif
int a[maxn];
int n,m,k;
void init()
{
scanf("%d%d%d",&n,&m,&k);
FOR(i,0,m) scanf("%d",a+i);
sort(a,a+m);
}
void sol()
{
int pos=1;
LL ans=0;
for(int i=m-1;i>=0;--i)
{
ans+=abs(pos-k);
ans+=abs(a[i]-k);
pos=a[i];
}
ans+=abs(pos-1);
cout<<ans<<'\n';
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
sol();
}
return 0;
}

1005 Lunch

题意:有n个数字,每次操作可以选择一个数字x,把它变成k个x/k(k是x的因子)。选择的x不可以是1.当全场只有1则输了
解题思路:
对于一个l来说,它由若干个质因子组成。对于奇数质因子,比如t,取了之后,t被拆成t个l/t,因为t是奇数,其实相当于变成了1个l/t的情况。所以l最多操作它的(奇数质因子个数)次,会变成

2

x

2^x

2x的形式。而变成

2

x

2^x

2x的时候,只要x不为0,那么不管怎么取都会变成必败态。也就是说,

2

x

2^x

2x对应了nim博弈种只剩下1个石头的状态。
那么(奇数质因子个数+ [l为偶数])就是当前局面可以操作的最多次数,对应nim博弈中的石子个数。可以理解为,如果取k = 偶数,相当于把整块石子拿完,取奇数则取多少个奇数质因子对应了取多少个石子。
然后就转化成了nim博弈问题,求异或和就好了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100;
int isp[maxn], p[maxn];
int main(void) {
int N = 100010;
for (int i=2;i<=N;i++) {
if (isp[i] == 0) p[++p[0]] = i;
for (int j=1;j<=p[0] && i*p[j]<=N;j++) {
isp[i*p[j]]=1;
if (i%p[j]==0) break;
}
}
int T; scanf("%d",&T);
while (T--) {
int n; scanf("%d",&n);
int ans = 0;
for (int i=1;i<=n;i++) {
int l; scanf("%d",&l);
int g=0;
if (l%2==0) {
g++;
while (l%2==0) l/=2;
}
for (int j=2;p[j]*p[j]<=l;j++) if (l%p[j]==0) {
g++, l/=p[j];
while (l%p[j] == 0) g++, l/=p[j];
}
if (l > 1) g++;
ans ^= g;
}
if (ans) printf("W\n");
else printf("L\n");
}
return 0;
}

1006 Robotic Class

不是我写的,当我正在翻看它长长的题面的时候小伙伴已经开始敲起了代码(
据说是直接模拟题意。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, K[505];
int a[505][2020],b[505][2020],c[505][2020],d[505][2020];
ll gao(int t, ll x, int cc) {
if (t == n) return x;
int pos = lower_bound(a[t],a[t]+K[t],x) - a[t];
if (pos < K[t] && x == a[t][pos] && cc == 1) pos++;
return gao(d[t][pos], c[t][pos]*(ll)x+b[t][pos], c[t][pos]*cc);
}
int main(void) {
//freopen("f.in","r",stdin);
int T; scanf("%d",&T);
for (int cas=1;cas<=T;cas++) {
printf("Case #%d: ",cas);
scanf("%d",&n);
for (int i=1;i<n;i++) {
scanf("%d",&K[i]);
for (int j=0;j<=K[i];j++) {
scanf("%d%d%d",&c[i][j],&b[i][j],&d[i][j]);
if (j < K[i]) scanf("%d",&a[i][j]);
}
}
int f=1;
for (int i=n-1;i>=1;i--) {
for (int j=0;j<K[i];j++) {
ll left = gao(i, a[i][j], -1);
ll right = gao(i, a[i][j], 1);
ll mid = gao(i, a[i][j], 0);
if (left != right || left != mid) {
f=0;
break;
}
}
if (f == 0) break;
}
if (f) printf("YES\n");
else printf("NO\n");
}

return 0;
}

1007 CCPC Training Class

题意:对于字符串S,定义Border(S)为S最长的不为S的前缀使得该前缀是S的后缀。
定义D(S) = D(Border(S))+1,当S为空则D(S) = 0
给一个字符串,可以重排它们。设重排出来的串是

t

1

t

2

t

3

.

.

.

t

n

t_1t_2t_3...t_n

t1​t2​t3​...tn​,设T[i] =

t

1

t

2

.

.

.

t

i

t_1t_2...t_i

t1​t2​...ti​,求

M

a

x

(

D

(

T

[

i

]

)

)

 

(

1

<

=

i

<

=

n

)

Max(D(T[i])) \ (1<=i<=n)

Max(D(T[i])) (1<=i<=n)最大可以是多少
解题思路:一看榜单这么多人过,看样例猜一个出现最多次的字母次数,敢交敢过。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define fors(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
int a[26];
const int maxn = 2e5 + 50;
char s[maxn];
int main()
{
int T; cin>>T;
int ca = 0;
while(T--){
scanf("%s", s);
memset(a,0,sizeof a);
int ans = 0;
int len = strlen(s);
fors(i,0,len) ans = max(ans, ++a[s[i]-'a']);
printf("Case #%d: %d\n",++ca, ans);
}
}

1010 Reports

真 · 签到

1011 3x3 Convolution

题意:给一个n * n的矩阵,然后和另一个3 * 3的卷积核一直做卷积,a[i][j]以(i,j)位置作为3 * 3的左上角来卷积
解题思路:如果不是左上角为1的卷积核,则一定会产生流失导致最终全部为0.

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define fors(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
const int maxn = 55;
int a[maxn][maxn];
int b[3][3];
int n;
int main()
{
int T; cin>>T;
while(T--){
scanf("%d", &n);
fors(i,0,n)
fors(j,0,n) scanf("%d", &a[i][j]);
int f = 1;
fors(i,0,3) fors(j,0,3){
scanf("%d", &b[i][j]);
if(i==0&&j==0){
if(b[i][j] == 0) f = 0;
}else{
if(b[i][j] > 0) f = 0;
}
}
if(f){
fors(i,0,n)
fors(j,0,n) {
printf("%d", a[i][j]);
if(j==n-1) printf("\n");
else printf(" ");
}
}else{
fors(i,0,n)
fors(j,0,n) {
printf("0");
if(j==n-1) printf("\n");
else printf(" ");
}
}
}
}

1012 Xor

以前写过差不多的。
稍微改一下就是这题

1013 Residual Polynomial

题意:给一个多项式

f

(

x

)

=

i

=

0

n

a

i

x

i

f(x) = \sum_{i=0}^n a_ix^i

f(x)=∑i=0n​ai​xi

f

i

(

x

)

=

b

i

f

i

1

(

x

)

+

c

i

f

i

1

f_i(x) = b_if_{i-1}'(x)+c_if_{i-1}

fi​(x)=bi​fi−1′​(x)+ci​fi−1​

f

1

(

x

)

=

f

(

x

)

f_1(x) = f(x)

f1​(x)=f(x)

f

n

(

x

)

f_n(x)

fn​(x)的每个系数.
解题思路:以

f

1

f_1

f1​为基础一步一步化开观察
(

f

n

(

x

)

f^n(x)

fn(x)代表对

f

(

x

)

f(x)

f(x)求n阶导)

f

2

(

x

)

=

b

2

f

1

(

x

)

+

c

2

f

(

x

)

f_2(x)=b_2f^1(x)+c_2f(x)

f2​(x)=b2​f1(x)+c2​f(x)

f

3

(

x

)

=

b

2

b

3

f

2

(

x

)

+

(

b

2

c

3

+

b

3

c

2

)

f

1

(

x

)

+

c

2

c

3

f

(

x

)

f_3(x)=b_2b_3f^2(x)+(b_2c_3+b_3c_2)f^1(x)+c_2c_3f(x)

f3​(x)=b2​b3​f2(x)+(b2​c3​+b3​c2​)f1(x)+c2​c3​f(x)

f

4

(

x

)

=

b

2

b

3

b

4

f

3

(

x

)

+

(

b

2

b

3

c

4

+

b

3

b

4

c

2

+

b

2

b

4

c

3

)

f

2

(

x

)

+

(

c

2

c

3

b

4

+

c

3

c

4

b

2

+

c

2

c

4

b

3

)

f

1

(

x

)

+

c

2

c

3

c

4

f

(

x

)

f_4(x)=b_2b_3b_4f^3(x)+(b_2b_3c_4+b_3b_4c_2+b_2b_4c_3)f^2(x)+(c_2c_3b_4+c_3c_4b_2+c_2c_4b_3)f^1(x)+c_2c_3c_4f(x)

f4​(x)=b2​b3​b4​f3(x)+(b2​b3​c4​+b3​b4​c2​+b2​b4​c3​)f2(x)+(c2​c3​b4​+c3​c4​b2​+c2​c4​b3​)f1(x)+c2​c3​c4​f(x)
可以发现,

f

n

n

(

x

)

f_n^n(x)

fnn​(x)的表达式中,

f

i

(

x

)

f^i(x)

fi(x)的系数对应

i

=

2

n

(

b

i

x

+

c

i

)

\prod_{i=2}^n(b_ix+c_i)

∏i=2n​(bi​x+ci​)中

x

i

x^i

xi的系数,设为

p

i

p_i

pi​。这个东西可以分治NTT求出来。
设最终

x

i

x^i

xi的系数为

w

i

w_i

wi​
则可得

w

i

=

i

+

j

=

k

p

j

a

k

t

=

i

+

1

k

t

w_i=\sum_{i+j=k} p_j*a_k*\prod_{t=i+1}^{k} t

wi​=∑i+j=k​pj​∗ak​∗∏t=i+1k​t
后面那个乘积部分对于每个

w

i

w_i

wi​不统一,改写一下:
则可得

w

i

i

!

=

i

+

j

=

k

p

j

a

k

k

!

w_i*i!=\sum_{i+j=k} p_j*a_k*k!

wi​∗i!=∑i+j=k​pj​∗ak​∗k!

a

[

i

]

=

a

[

n

i

]

(

n

i

)

!

a[i] = a[n-i]*(n-i)!

a[i]=a[n−i]∗(n−i)!,则每个

i

!

w

i

i!w_i

i!wi​也可以通过p和修改后的a卷积求出了。

以下是通过代码,跑的挺慢,不推荐当作分治NTT的板子。

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int maxn = 2e5 + 50;
const int mod = 998244353;
int qm(int a, int b){int res = 1; while(b){if(b&1) res = (ll)res*a%mod; a = (ll)a*a%mod; b >>= 1; } return res; }
int mulwn[maxn<<2], invwn[maxn<<2];
int fac[maxn], ifac[maxn];
void INIT(){
fac[0] = ifac[0] = 1;
for(int i = 1; i < maxn; ++i) fac[i] = (ll)fac[i-1]*i%mod, ifac[i] = qm(fac[i], mod-2);

for(ll i=1;i < maxn*4;i<<=1) mulwn[i]=qm(3,(mod-1)/i);
for(ll i=1;i < maxn*4;i<<=1) invwn[i]=qm(mulwn[i],mod-2);
}
struct NTT {
int n, m, rev[maxn << 2];
int a[maxn << 2], b[maxn << 2];
void init(int len) {
for (n = 1, m = 0; n < len + len; n <<= 1, m++);
for (int i = 0; i < n; ++i) {
rev[i] = (rev[i >> 1] >> 1) | (i & 1) << (m - 1);
a[i] = 0;
b[i] = 0;
}
}
void ntt(int *a, int f) {//
for (int i = 0; i < n; ++i)if (i < rev[i])swap(a[i], a[rev[i]]);

for (int k = 2; k <= n; k <<= 1) {
int wn=(f>0)?mulwn[k]:invwn[k];
int mid = k>>1;
for(int i = 0; i < n; i += k){
int w = 1;
for(int j = 0; j < mid; ++j, w = (ll)w*wn%mod){
int temp = ((ll)w*a[i+j+mid])%mod;
a[i+j+mid] = (a[i+j]-temp+mod)%mod;
a[i+j] = (a[i+j]+temp)%mod;
}
}
}
return;
}
void Calculate() {
ntt(a, 1); ntt(b, 1);
for (int i = 0; i < n; ++i)a[i] = (ll)a[i]*b[i]%mod;//¼ÇµÃÈ¡Ä£
ntt(a, -1);
int invl = qm(n, mod-2);
for(int i = 0; i < n; ++i){
a[i] = (ll)a[i]*invl%mod;
}
}
} F;
int n;
int a[maxn], b[maxn], c[maxn];
void init()
{
cin>>n;
for(int i = 0; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 2; i <= n; ++i) scanf("%d", &b[i]);
for(int i = 2; i <= n; ++i) scanf("%d", &c[i]);
}
vector<int> w[maxn<<2];
void work(int rt, int l, int r){
w[rt].clear();
if(l == r){
w[rt].pb(c[l]); w[rt].pb(b[l]);
return;
}
int mid = (r+l)>>1;
work(rt<<1, l, mid);
work(rt<<1|1, mid+1, r);
int len = w[rt<<1].size() + w[rt<<1|1].size()-1;
if(r-l+1<=1000){
for(int i = 0; i < len; ++i) w[rt].pb(0);
for(int i = 0; i < w[rt<<1].size(); ++i){
for(int j = 0; j < w[rt<<1|1].size(); ++j){
w[rt][i+j] = (w[rt][i+j] + (ll)w[rt<<1][i]*w[rt<<1|1][j]%mod)%mod;
}
}
w[rt<<1].clear(); w[rt<<1|1].clear();
return;
}
F.init(len);
for(int i = 0; i < w[rt<<1].size(); ++i) F.a[i] = w[rt<<1][i];
for(int i = 0; i < w[rt<<1|1].size(); ++i) F.b[i] = w[rt<<1|1][i];
w[rt<<1].clear(); w[rt<<1|1].clear();
F.Calculate();
for(int i = 0; i < len; ++i){
w[rt].push_back(F.a[i]);
}
return;
}

void sol(){
work(1,2,n);//w[rt][i] * a[j]
int len = w[1].size() + n;
F.init(len);
for(int i = 0; i < w[1].size(); ++i) {
F.a[i] = w[1][i];
//cout<<"i:"<<i<<" val:"<<w[1][i]<<endl;
}
for(int i = 0; i <= n; ++i) F.b[i] = (ll)a[n-i]*fac[n-i]%mod;
F.Calculate();
for(int i = 0; i <= n; ++i) {
int ans = (ll)F.a[n-i]*ifac[i]%mod;
printf("%d", ans);
if(i == n) printf("\n");
else printf(" ");
}
}
int main(){

INIT();
int T; cin>>T;
while(T--){
init();
sol();
}
}
/*
3
3
0 0 0 1
1 1
1 1
*/

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

2020 CCPC网络选拔赛部分题解

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 2020 CCPC网络选拔赛部分题解
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏