Wannafly挑战赛27
我打的第一场$Wannafly$是第25场,$T2$竟然出了一个几何题?而且还把我好不容易升上绿的$Rating$又降回了蓝名...之后再不敢打$Wannafly$了.
由于某一场比赛打了一半就咕咕咕了,现在$Rating$已经降得很低了,干脆打一场碰碰运气好了.
差六名就抽到我发奖品了，就当攒点$rp$给联赛好了.
T1:http://www.nowcoder.com/acm/contest/215/A
题意概述:给出长度为$n$的序列, 求有多少对数对 $(i,j)(1<=i<j<=n)$ 满足 $a_i+a_j$为完全平方数。$n,a_i<=10^5$
这次的签到题还是很简单的,$N^2$暴力实在是太假了,但是可以发现数据范围内的完全平方数并不是很多,开一个桶记录之前出现过数的次数,每读入一个数就枚举范围内所有完全平方数进行判断即可.(注意数组下标不能为负)
# include <cstdio>
# include <iostream>
# include <cstring>
# include <algorithm>
# include <string>
# include <cmath>
# define R register int
# define ll long long using namespace std; const int maxn=;
int n;
int a[maxn];
int h,t[maxn+];
ll q[maxn],ans; int main()
{
scanf("%d",&n);
ll i=;
while ()
{
q[++h]=i*i;
i++;
if(i*i>=) break;
}
for (R i=;i<=n;++i)
{
scanf("%d",&a[i]);
for (R j=;j<=h;++j)
{
if(a[i]>q[j]) continue;
if(q[j]-a[i]<=maxn) ans+=t[ q[j]-a[i] ];
}
t[ a[i] ]++;
}
printf("%lld",ans);
return ;
}
灰魔法师
T2:http://www.nowcoder.com/acm/contest/215/B
题意概述:给定一棵仙人掌,求最少用多少颜色可以对其染色,一条边连接的两个点不能染相同的染色.$n<=10^5,m<=2 \times 10^5$
仙人掌?图的色数?我记得这不是一个$NP$完全问题吗?
然而...一个图必须至少使用$n$种颜色才能染色的一个条件是至少存在$n$个点构成一张完全图,对于仙人掌来说,最多出现一个$3$个点构成的环使得色数为$3$,大于等于$4$的情况根本不存在。
判断答案是否为$1$:没有边答案就是$1$;
判断答案是否为$2$:黑白染色判断即可.
判断答案是否为$3$:找三元环看起来非常麻烦，虽然传说中有一种$O(M\sqrt{N})$的做法,但是...不是$1$又不是$2$不就是三了吗?
# include <cstdio>
# include <iostream>
# include <cstring>
# include <algorithm>
# include <string>
# include <cmath>
# define R register int using namespace std; const int maxn=;
const int maxm=;
int n,m,x,y,h,f;
int firs[maxn],vis[maxn];
struct edge
{
int too,nex;
}g[maxm<<]; void add (int x,int y)
{
g[++h].too=y;
g[h].nex=firs[x];
firs[x]=h;
} void dfs (int x)
{
int j;
for (R i=firs[x];i;i=g[i].nex)
{
j=g[i].too;
if(vis[j]&&vis[j]==vis[x]) f=;
if(vis[j]) continue;
if(vis[x]==) vis[j]=;
if(vis[x]==) vis[j]=;
dfs(j);
}
} int main()
{
scanf("%d%d",&n,&m);
if(m==)
{
printf("");
return ;
}
for (R i=;i<=m;++i)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
vis[]=;
dfs();
if(f) printf("");
else printf("");
return ;
}
紫魔法师
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$,转移的时候只转移到子树大小(扫帚树就是专门卡这个的)，后来加上了这个：
inline char gc()
{
static char now[<<],*S,*T;
if (T==S)
{
T=(S=now)+fread(now,,<<,stdin);
if (T==S) return EOF;
}
return *S++;
}
inline int read()
{
R x=;
register char ch=gc();
while(!isdigit(ch))
ch=gc();
while(isdigit(ch)) x=(x<<)+(x<<)+ch-'',ch=gc();
return x;
}
神仙快读
这个：
inline int ad (int a,int b)
{
a+=b;
if(a>=mod) a-=mod;
return a;
}
加法取模优化
把所有的$long$ $long$换成$int$;
如果乘法中有一项已经是$0$就不乘了;
然而结果依然是:
正当大家纷纷退出卡常大赛的时候,我突然想起之前看$pks$的博客中提到的毒瘤优化,试了一下发现在本机编译都过不了,但是尝试了一下"自测",发现牛客网能编译这个!于是就愉快的过掉了这道题.下面是我已经看不大懂的代码.
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
# include <cstdio>
# include <iostream>
# include <cstring>
# include <algorithm>
# include <string>
# include <cmath>
# define mod
# define R register int
# define ll long long using namespace std; const int maxn=;
int n,k,h,x,y;
int firs[maxn],siz[maxn],dep[maxn];
int dp[maxn][maxn]; struct edge
{
int too,nex;
}g[maxn<<]; inline void add (int x,int y)
{
g[++h].too=y;
g[h].nex=firs[x];
firs[x]=h;
} inline int ad (int a,int b)
{
a+=b;
if(a>=mod) a-=mod;
return a;
} void dfs (int x)
{
siz[x]=;
int j;
dp[x][]=;
for (R i=firs[x];i;i=g[i].nex)
{
j=g[i].too;
if(dep[j]) continue;
dep[j]=dep[i]+;
dfs(j);
siz[x]+=siz[j];
for (R s=min(siz[x],k);s;--s)
{
if(s==)
{
dp[x][s]=(1LL*dp[x][s]*dp[j][])%mod;
continue;
}
dp[x][s]=(1LL*dp[x][s]*dp[j][])%mod;
for (R f=;f<=min(s,siz[j]);++f)
{
if(dp[x][s-f]==||dp[j][f]==) continue;
dp[x][s]=ad(dp[x][s],1LL*dp[x][s-f]*dp[j][f]%mod);
}
}
}
for (R i=;i<=min(k,siz[x]);++i)
dp[x][]=ad(dp[x][],dp[x][i]);
} inline char gc()
{
static char now[<<],*S,*T;
if (T==S)
{
T=(S=now)+fread(now,,<<,stdin);
if (T==S) return EOF;
}
return *S++;
}
inline int read()
{
R x=;
register char ch=gc();
while(!isdigit(ch))
ch=gc();
while(isdigit(ch)) x=(x<<)+(x<<)+ch-'',ch=gc();
return x;
} int main()
{
n=read(),k=read();
for (R i=;i<n;++i)
{
x=read(),y=read();
add(x,y);
add(y,x);
}
dep[]=;
dfs();
printf("%d",dp[][]);
return ;
}
蓝魔法师
T4:http://www.nowcoder.com/acm/contest/215/D
题意概述:一个空的可重集合$S$,$n$次操作，每次操作给出$x,k,p$，执行以下操作：
1、在$S$中加入$x$。
2、输出
所有数的范围都是$1e5$
暴力(O(TLE)):
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
# include <cstdio>
# include <iostream>
# define R register int using namespace std; const int maxn=;
int n,x,k,p,a[maxn];
int anss[maxn],vis[maxn],s,ans; inline char gc()
{
static char now[<<],*S,*T;
if (T==S)
{
T=(S=now)+fread(now,,<<,stdin);
if (T==S) return EOF;
}
return *S++;
}
inline int read()
{
R x=;
register char ch=gc();
while(!isdigit(ch))
ch=gc();
while(isdigit(ch)) x=(x<<)+(x<<)+ch-'',ch=gc();
return x;
} int gcd (int a,int b)
{
int p=;
if(a<b) swap(a,b);
while(a&&b)
{
if(a%==&&b%==) p*=,a/=,b/=;
else if(a%&&b%==) b/=;
else if(a%==&&b%) a/=;
else a-=b;
if(a<b) swap(a,b);
}
return p*a;
} int qui (int a,int b)
{
int s=;
while (b)
{
if(b&) s=1LL*s*a%p;
a=1LL*a*a%p;
b=b>>;
}
return s;
} int main()
{ n=read();
for (R i=;i<=n;++i)
{
a[i]=read();
k=read();
p=read();
ans=;
for (R j=;j<=i;++j)
{
if(vis[ a[j] ]==i)
s=anss[ a[j] ];
else
{
int g=gcd(a[i],a[j]);
if(g==) s=;
else s=qui(g,k);
}
ans=ans+s;
if(ans>=p) ans-=p;
vis[ a[j] ]=i;
anss[ a[j] ]=s;
}
printf("%d\n",ans);
}
return ;
}
绿魔法师
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