Wannafly挑战赛27
我打的第一场$Wannafly$是第25场,$T2$竟然出了一个几何题?而且还把我好不容易升上绿的$Rating$又降回了蓝名...之后再不敢打$Wannafly$了.
由于某一场比赛打了一半就咕咕咕了,现在$Rating$已经降得很低了,干脆打一场碰碰运气好了.
差六名就抽到我发奖品了，就当攒点$rp$给联赛好了.
T1:
题意概述:给出长度为$n$的序列, 求有多少对数对 $(i,j)(1<=i<j<=n)$ 满足 $a_i+a_j$为完全平方数。$n,a_i<=10^5$
这次的签到题还是很简单的,$N^2$暴力实在是太假了,但是可以发现数据范围内的完全平方数并不是很多,开一个桶记录之前出现过数的次数,每读入一个数就枚举范围内所有完全平方数进行判断即可.(注意数组下标不能为负)
1 # include2 # include 3 # include 4 # include 5 # include 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:
题意概述:给定一棵仙人掌,求最少用多少颜色可以对其染色,一条边连接的两个点不能染相同的染色.$n<=10^5,m<=2 \times 10^5$
仙人掌?图的色数?我记得这不是一个$NP$完全问题吗?
然而...一个图必须至少使用$n$种颜色才能染色的一个条件是至少存在$n$个点构成一张完全图,对于仙人掌来说,最多出现一个$3$个点构成的环使得色数为$3$,大于等于$4$的情况根本不存在。
判断答案是否为$1$:没有边答案就是$1$;
判断答案是否为$2$:黑白染色判断即可.
判断答案是否为$3$:找三元环看起来非常麻烦，虽然传说中有一种$O(M\sqrt{N})$的做法,但是...不是$1$又不是$2$不就是三了吗?
1 # include2 # include 3 # include 4 # include 5 # include 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 edge16 {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:
题意概述:将一棵树删去一些边使得每个联通块的大小$<=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 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;i
T4:
题意概述:一个空的可重集合$S$,$n$次操作，每次操作给出$x,k,p$，执行以下操作： 1、在$S$中加入$x$。 2、输出
所有数的范围都是$1e5$
暴力(O(TLE)):
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 >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 else121 {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\n",ans);132 }133 return 0;134 }
T5:
题意概述:对"灰魔法师"一题的延伸,要求构造一个长度为$n$的数列使得恰好有$k$对数相加是一个完全平方数.$n<=10^5,k<=10^{10}$
构造？等官方题解下来再说吧。
T6:
题意概述:直接粘题面吧,$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