当前位置: 开发笔记 > 编程语言 > 正文

开发笔记:Wannafly挑战赛27

作者：大盗哈喽小马甲_943 | 来源：互联网 | 2023-09-07 16:25

本文由编程笔记#小编为大家整理，主要介绍了Wannafly挑战赛27相关的知识，希望对你有一定的参考价值。Wannafly挑战赛27

本文由编程笔记#小编为大家整理，主要介绍了Wannafly挑战赛27相关的知识，希望对你有一定的参考价值。

Wannafly挑战赛27

　　我打的第一场$Wannafly$是第25场,$T2$竟然出了一个几何题?而且还把我好不容易升上绿的$Rating$又降回了蓝名...之后再不敢打$Wannafly$了.

　　由于某一场比赛打了一半就咕咕咕了,现在$Rating$已经降得很低了,干脆打一场碰碰运气好了.

　　差六名就抽到我发奖品了，就当攒点$rp$给联赛好了.

　　T1:http://www.nowcoder.com/acm/contest/215/A

　　题意概述:给出长度为$n$的序列, 求有多少对数对 $(i,j)(1<=i

　　这次的签到题还是很简单的,$N^2$暴力实在是太假了,但是可以发现数据范围内的完全平方数并不是很多,开一个桶记录之前出现过数的次数,每读入一个数就枚举范围内所有完全平方数进行判断即可.(注意数组下标不能为负)

1 # include
2 # include <iostream>
3 # include
4 # include
5 # include <string>
6 # include
7 # define R register int
8 # define ll long long
9
10 using namespace std;
11
12 const int maxn=100005;
13 int n;
14 int a[maxn];
15 int h,t[maxn+5];
16 ll q[maxn],ans;
17
18 int main()
19 {
20 scanf("%d",&n);
21 ll i=0;
22 while (1)
23 {
24 q[++h]=i*i;
25 i++;
26 if(i*i>=200005) break;
27 }
28 for (R i=1;i<=n;++i)
29 {
30 scanf("%d",&a[i]);
31 for (R j=1;j<=h;++j)
32 {
33 if(a[i]>q[j]) continue;
34 if(q[j]-a[i]<=maxn) ans+=t[ q[j]-a[i] ];
35 }
36 t[ a[i] ]++;
37 }
38 printf("%lld",ans);
39 return 0;
40 }

灰魔法师

　　T2:http://www.nowcoder.com/acm/contest/215/B

　　题意概述:给定一棵仙人掌,求最少用多少颜色可以对其染色,一条边连接的两个点不能染相同的染色.$n<=10^5,m<=2 imes 10^5$

　　仙人掌?图的色数?我记得这不是一个$NP$完全问题吗?

　　技术分享图片

　　然而...一个图必须至少使用$n$种颜色才能染色的一个条件是至少存在$n$个点构成一张完全图,对于仙人掌来说,最多出现一个$3$个点构成的环使得色数为$3$,大于等于$4$的情况根本不存在。

　　判断答案是否为$1$:没有边答案就是$1$;

　　判断答案是否为$2$:黑白染色判断即可.　　

　　判断答案是否为$3$:找三元环看起来非常麻烦，虽然传说中有一种$O(Msqrt{N})$的做法,但是...不是$1$又不是$2$不就是三了吗?

1 # include
2 # include
3 # include
4 # include
5 # include <string>
6 # include
7 # define R register int
8
9 using namespace std;
10
11 const int maxn=100005;
12 const int maxm=200005;
13 int n,m,x,y,h,f;
14 int firs[maxn],vis[maxn];
15 struct edge
16 {
17 int too,nex;
18 }g[maxm<<1];
19
20 void add (int x,int y)
21 {
22 g[++h].too=y;
23 g[h].nex=firs[x];
24 firs[x]=h;
25 }
26
27 void dfs (int x)
28 {
29 int j;
30 for (R i=firs[x];i;i=g[i].nex)
31 {
32 j=g[i].too;
33 if(vis[j]&&vis[j]==vis[x]) f=1;
34 if(vis[j]) continue;
35 if(vis[x]==1) vis[j]=2;
36 if(vis[x]==2) vis[j]=1;
37 dfs(j);
38 }
39 }
40
41 int main()
42 {
43 scanf("%d%d",&n,&m);
44 if(m==0)
45 {
46 printf("1");
47 return 0;
48 }
49 for (R i=1;i<=m;++i)
50 {
51 scanf("%d%d",&x,&y);
52 add(x,y);
53 add(y,x);
54 }
55 vis[1]=1;
56 dfs(1);
57 if(f) printf("3");
58 else printf("2");
59 return 0;
60 }

紫魔法师

　　T3:http://www.nowcoder.com/acm/contest/215/C

　　题意概述:将一棵树删去一些边使得每个联通块的大小$<=k$的方案数.$k<=n<=2000$

　　看上去像是个树形$dp$,$dp[i][j]$表示以$i$为根的子树中保留$i$,根处的联通块大小为$j$的方案数,慢慢转移就好.

　　当然不行啦!慢慢转移就$TLE$了!你需要的是快快转移.

　　$asuldb$和$zutter$两位大佬一同表示树上背包的复杂度是$O(NK)$,我还以为我记错了,直到我造了一棵扫帚树...

　　现在的复杂度是$O(TLE)$,但是听说牛客的机器能跑$10^{10}$,就开始了漫长的卡常之旅,首先肯定是一些最简单的$register,inline$,转移的时候只转移到子树大小(扫帚树就是专门卡这个的)，后来加上了这个：

1 inline char gc()
2 {
3 static char now[1<<22],*S,*T;
4 if (T==S)
5 {
6 T=(S=now)+fread(now,1,1<<22,stdin);
7 if (T==S) return EOF;
8 }
9 return *S++;
10 }
11 inline int read()
12 {
13 R x=0;
14 register char ch=gc();
15 while(!isdigit(ch))
16 ch=gc();
17 while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-‘0‘,ch=gc();
18 return x;
19 }

神仙快读

　　这个：

1 inline int ad (int a,int b)
2 {
3 a+=b;
4 if(a>=mod) a-=mod;
5 return a;
6 }

加法取模优化

　　把所有的$long$ $long$换成$int$;

　　如果乘法中有一项已经是$0$就不乘了;

　　然而结果依然是:

　　技术分享图片

　　正当大家纷纷退出卡常大赛的时候,我突然想起之前看$pks$的博客中提到的毒瘤优化,试了一下发现在本机编译都过不了,但是尝试了一下"自测",发现牛客网能编译这个!于是就愉快的过掉了这道题.下面是我已经看不大懂的代码.

1 #pragma GCC diagnostic error "-std=c++14"
2 #pragma GCC target("avx")
3 #pragma GCC optimize(3)
4 #pragma GCC optimize("Ofast")
5 #pragma GCC optimize("inline")
6 #pragma GCC optimize("-fgcse")
7 #pragma GCC optimize("-fgcse-lm")
8 #pragma GCC optimize("-fipa-sra")
9 #pragma GCC optimize("-ftree-pre")
10 #pragma GCC optimize("-ftree-vrp")
11 #pragma GCC optimize("-fpeephole2")
12 #pragma GCC optimize("-ffast-math")
13 #pragma GCC optimize("-fsched-spec")
14 #pragma GCC optimize("unroll-loops")
15 #pragma GCC optimize("-falign-jumps")
16 #pragma GCC optimize("-falign-loops")
17 #pragma GCC optimize("-falign-labels")
18 #pragma GCC optimize("-fdevirtualize")
19 #pragma GCC optimize("-fcaller-saves")
20 #pragma GCC optimize("-fcrossjumping")
21 #pragma GCC optimize("-fthread-jumps")
22 #pragma GCC optimize("-funroll-loops")
23 #pragma GCC optimize("-fwhole-program")
24 #pragma GCC optimize("-freorder-blocks")
25 #pragma GCC optimize("-fschedule-insns")
26 #pragma GCC optimize("inline-functions")
27 #pragma GCC optimize("-ftree-tail-merge")
28 #pragma GCC optimize("-fschedule-insns2")
29 #pragma GCC optimize("-fstrict-aliasing")
30 #pragma GCC optimize("-fstrict-overflow")
31 #pragma GCC optimize("-falign-functions")
32 #pragma GCC optimize("-fcse-skip-blocks")
33 #pragma GCC optimize("-fcse-follow-jumps")
34 #pragma GCC optimize("-fsched-interblock")
35 #pragma GCC optimize("-fpartial-inlining")
36 #pragma GCC optimize("no-stack-protector")
37 #pragma GCC optimize("-freorder-functions")
38 #pragma GCC optimize("-findirect-inlining")
39 #pragma GCC optimize("-fhoist-adjacent-loads")
40 #pragma GCC optimize("-frerun-cse-after-loop")
41 #pragma GCC optimize("inline-small-functions")
42 #pragma GCC optimize("-finline-small-functions")
43 #pragma GCC optimize("-ftree-switch-conversion")
44 #pragma GCC optimize("-foptimize-sibling-calls")
45 #pragma GCC optimize("-fexpensive-optimizations")
46 #pragma GCC optimize("-funsafe-loop-optimizations")
47 #pragma GCC optimize("inline-functions-called-once")
48 #pragma GCC optimize("-fdelete-null-pointer-checks")
49 # include
50 # include
51 # include
52 # include
53 # include <string>
54 # include
55 # define mod 998244353
56 # define R register int
57 # define ll long long
58
59 using namespace std;
60
61 const int maxn=2004;
62 int n,k,h,x,y;
63 int firs[maxn],siz[maxn],dep[maxn];
64 int dp[maxn][maxn];
65
66 struct edge
67 {
68 int too,nex;
69 }g[maxn<<1];
70
71 inline void add (int x,int y)
72 {
73 g[++h].too=y;
74 g[h].nex=firs[x];
75 firs[x]=h;
76 }
77
78 inline int ad (int a,int b)
79 {
80 a+=b;
81 if(a>=mod) a-=mod;
82 return a;
83 }
84
85 void dfs (int x)
86 {
87 siz[x]=1;
88 int j;
89 dp[x][1]=1;
90 for (R i=firs[x];i;i=g[i].nex)
91 {
92 j=g[i].too;
93 if(dep[j]) continue;
94 dep[j]=dep[i]+1;
95 dfs(j);
96 siz[x]+=siz[j];
97 for (R s=min(siz[x],k);s;--s)
98 {
99 if(s==1)
100 {
101 dp[x][s]=(1LL*dp[x][s]*dp[j][0])%mod;
102 continue;
103 }
104 dp[x][s]=(1LL*dp[x][s]*dp[j][0])%mod;
105 for (R f=1;f<=min(s,siz[j]);++f)
106 {
107 if(dp[x][s-f]==0||dp[j][f]==0) continue;
108 dp[x][s]=ad(dp[x][s],1LL*dp[x][s-f]*dp[j][f]%mod);
109 }
110 }
111 }
112 for (R i=1;i<=min(k,siz[x]);++i)
113 dp[x][0]=ad(dp[x][0],dp[x][i]);
114 }
115
116 inline char gc()
117 {
118 static char now[1<<22],*S,*T;
119 if (T==S)
120 {
121 T=(S=now)+fread(now,1,1<<22,stdin);
122 if (T==S) return EOF;
123 }
124 return *S++;
125 }
126 inline int read()
127 {
128 R x=0;
129 register char ch=gc();
130 while(!isdigit(ch))
131 ch=gc();
132 while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-‘0‘,ch=gc();
133 return x;
134 }
135
136 int main()
137 {
138 n=read(),k=read();
139 for (R i=1;ii)
140 {
141 x=read(),y=read();
142 add(x,y);
143 add(y,x);
144 }
145 dep[1]=1;
146 dfs(1);
147 printf("%d",dp[1][0]);
148 return 0;
149 }

蓝魔法师

　　T4:http://www.nowcoder.com/acm/contest/215/D

　　题意概述:一个空的可重集合$S$,$n$次操作，每次操作给出$x,k,p$，执行以下操作：
　　1、在$S$中加入$x$。
　　2、输出

　　技术分享图片

1 #pragma GCC diagnostic error "-std=c++14"
2 #pragma GCC target("avx")
3 #pragma GCC optimize(3)
4 #pragma GCC optimize("Ofast")
5 #pragma GCC optimize("inline")
6 #pragma GCC optimize("-fgcse")
7 #pragma GCC optimize("-fgcse-lm")
8 #pragma GCC optimize("-fipa-sra")
9 #pragma GCC optimize("-ftree-pre")
10 #pragma GCC optimize("-ftree-vrp")
11 #pragma GCC optimize("-fpeephole2")
12 #pragma GCC optimize("-ffast-math")
13 #pragma GCC optimize("-fsched-spec")
14 #pragma GCC optimize("unroll-loops")
15 #pragma GCC optimize("-falign-jumps")
16 #pragma GCC optimize("-falign-loops")
17 #pragma GCC optimize("-falign-labels")
18 #pragma GCC optimize("-fdevirtualize")
19 #pragma GCC optimize("-fcaller-saves")
20 #pragma GCC optimize("-fcrossjumping")
21 #pragma GCC optimize("-fthread-jumps")
22 #pragma GCC optimize("-funroll-loops")
23 #pragma GCC optimize("-fwhole-program")
24 #pragma GCC optimize("-freorder-blocks")
25 #pragma GCC optimize("-fschedule-insns")
26 #pragma GCC optimize("inline-functions")
27 #pragma GCC optimize("-ftree-tail-merge")
28 #pragma GCC optimize("-fschedule-insns2")
29 #pragma GCC optimize("-fstrict-aliasing")
30 #pragma GCC optimize("-fstrict-overflow")
31 #pragma GCC optimize("-falign-functions")
32 #pragma GCC optimize("-fcse-skip-blocks")
33 #pragma GCC optimize("-fcse-follow-jumps")
34 #pragma GCC optimize("-fsched-interblock")
35 #pragma GCC optimize("-fpartial-inlining")
36 #pragma GCC optimize("no-stack-protector")
37 #pragma GCC optimize("-freorder-functions")
38 #pragma GCC optimize("-findirect-inlining")
39 #pragma GCC optimize("-fhoist-adjacent-loads")
40 #pragma GCC optimize("-frerun-cse-after-loop")
41 #pragma GCC optimize("inline-small-functions")
42 #pragma GCC optimize("-finline-small-functions")
43 #pragma GCC optimize("-ftree-switch-conversion")
44 #pragma GCC optimize("-foptimize-sibling-calls")
45 #pragma GCC optimize("-fexpensive-optimizations")
46 #pragma GCC optimize("-funsafe-loop-optimizations")
47 #pragma GCC optimize("inline-functions-called-once")
48 #pragma GCC optimize("-fdelete-null-pointer-checks")
49 # include
50 # include
51 # define R register int
52
53 using namespace std;
54
55 const int maxn=100005;
56 int n,x,k,p,a[maxn];
57 int anss[maxn],vis[maxn],s,ans;
58
59 inline char gc()
60 {
61 static char now[1<<22],*S,*T;
62 if (T==S)
63 {
64 T=(S=now)+fread(now,1,1<<22,stdin);
65 if (T==S) return EOF;
66 }
67 return *S++;
68 }
69 inline int read()
70 {
71 R x=0;
72 register char ch=gc();
73 while(!isdigit(ch))
74 ch=gc();
75 while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-‘0‘,ch=gc();
76 return x;
77 }
78
79 int gcd (int a,int b)
80 {
81 int p=1;
82 if(a<b) swap(a,b);
83 while(a&&b)
84 {
85 if(a%2==0&&b%2==0) p*=2,a/=2,b/=2;
86 else if(a%2&&b%2==0) b/=2;
87 else if(a%2==0&&b%2) a/=2;
88 else a-=b;
89 if(a<b) swap(a,b);
90 }
91 return p*a;
92 }
93
94 int qui (int a,int b)
95 {
96 int s=1;
97 while (b)
98 {
99 if(b&1) s=1LL*s*a%p;
100 a=1LL*a*a%p;
101 b=b>>1;
102 }
103 return s;
104 }
105
106 int main()
107 {
108
109 n=read();
110 for (R i=1;i<=n;++i)
111 {
112 a[i]=read();
113 k=read();
114 p=read();
115 ans=0;
116 for (R j=1;j<=i;++j)
117 {
118 if(vis[ a[j] ]==i)
119 s=anss[ a[j] ];
120 else
121 {
122 int g=gcd(a[i],a[j]);
123 if(g==1) s=1;
124 else s=qui(g,k);
125 }
126 ans=ans+s;
127 if(ans>=p) ans-=p;
128 vis[ a[j] ]=i;
129 anss[ a[j] ]=s;
130 }
131 printf("%d
",ans);
132 }
133 return 0;
134 }

绿魔法师

　　T5:http://www.nowcoder.com/acm/contest/215/E

　　题意概述:对"灰魔法师"一题的延伸,要求构造一个长度为$n$的数列使得恰好有$k$对数相加是一个完全平方数.$n<=10^5,k<=10^{10}$

　　构造？等官方题解下来再说吧。

　　T6:http://www.nowcoder.com/acm/contest/215/F

　　题意概述:直接粘题面吧,$Wannafly$的题面都挺简洁的.
　　一个空的二维平面上，每次加入或删除一个整点。
　　求每次操作完之后满足以下条件的三个点$p1,p2,p3$的对数。
　　1、$p1.y>p2.y>p3.y$;
　　2、$p1.x>max(p2.x,p3.x)$;
　　令操作数为n，保证$n<=60000,1<=x,y<=n$。
　　保证不会重复加入点,也不会删除不存在的点;

　　这是啥...二维线段树还是$CDQ$分治？顺便问一下有没有二维平衡树啊.

　　所以我虽然没做出来绿魔法师却因此上绿名了?要是做出来岂不是可以黄名?

　　---shzr