HHHOJ NOIP2020模拟赛（叁）2020.02.03 题解
A. 「NOIP模拟赛 叁」木板
题意
将一个边长为 N 的正方形裁剪成四个直角三角形。注意面积不能为 0。
三个必要的切割中的两个始终从一个角落G进行（图中G位于A，实际上也可以是B、C、D），第三次切割必须垂直于前面两个之一（在图中，AE部分垂直于EF部分）。
切割机仅接受整个坐标值，这意味着N必须是整数的，并且点E和F的坐标必须是整数的。 有时候这可能是不可能的。
编写一个程序，根据给出的 N，确定是否可以将四边形的正方形三角形切割成四个矩形三角形，如果可能的话，可以采用多少种方法来完成。 对于40%的数据，n\leq {10}^{7}。 对于另10%的数据，n为质数。 对于100%的数据，n\leq {10} ^ {14}，不超过5组数据。
思路
易证\triangle ABE \sim \triangle ECF 所以\frac{X}{A}=\frac{N}{N-X}。 也就是A=\frac{X\times (N-X)}{N} 因为A、X、N都是整数 所以\frac{X\times (N-x)}{N}是整数。 即：\frac{X\times N - X^2}{N} 分式拆分下：X-\frac{X^2}{N}是整数。 就是X^2 \mod N =0。 就是X^2可以整除N。 设N=\prod {p_i}^{q_i}（把N分解质因数） 那么有\prod {p_i}^{\lceil \frac{q_i}{2} \rceil }X。 由于X取值范围是\text{[}1,N\text{)}。 那么答案就是\frac{N}{\prod {p_i}^{\lceil \frac{q_i}{2} \rceil }} -1. 化简下就是\prod {p_i}^{\lfloor \frac{q_i}{2} \rfloor }-1。 那么筛下素数再弄个快速幂就好了。
Code
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
#define re
#define int long long
#define LD double
#define MAXN 10000000
#define mod 998244353
class Quick_Input_Output{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
char Rd[S],*A,*B;
#define pc putchar
public:
#undef gc
#define gc getchar
inline int read(){
int res=0,f=1;char ch=gc();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
return res*f;
}
inline void write(int x){
if(x<0) pc('-'),x=-x;
if(x<10) pc(x+'0');
else write(x/10),pc(x%10+'0');
}
#undef gc
#undef pc
}I;
#define File freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout);
int n;
class Solve{
private:
int prime[MAXN],tot,ans;
bool vis[MAXN+5];
public:
inline void get_prime(){
for(int i=2;i<=MAXN;i++){
if(vis[i]==0){
prime[++tot]=i;
for(int j=2*i;j<=MAXN;j+=i) vis[j]=1;
}
}
}
inline int fpow(int a,int b){
re int s=1;
while(b){
if(b&1) s*=a;
a*=a;
b>>=1;
}
return s;
}
inline void solve(){
ans=1;
for(int s,i=1;prime[i]<=n&&i<=tot;i++){
s=0;
while(n%prime[i]==0) s++,n/=prime[i];
ans*=fpow(prime[i],s/2);
}
I.write((ans-1ll)*8ll);putchar('\n');
}
}S;
signed main(){
S.get_prime();
while(n=I.read()) S.solve();
} B. 「NOIP模拟赛 叁」卡车
题意
卡车在 n 个城市之间运送货物，城市由 n−1条道路连成网络，使得任意两座城市之间存在唯一的道路。 城市网络中每个城市有一个权值 d_i，道路也都有一个权值w_i。 对于一条路径，令路径上所有城市权值 d_i的最小值为 {min}_d，路径上所有道路权值w_i的总和为 {sum}_w，则该条路径的总权值为 {min}_d\times {sum}_w。 路径的起点和终点可以是任意城市，且路径中不能出现重复的城市。 请求网络中所有路径总权值中的最大值。 n\leq 2\times {10}^5 , 1 \leq d_i ,w_i \leq {10}^9
思路
本题有多种解法。首先是点分治的思想，在点分治的时候，我们每一次选取一个中心，先统计过中心的路径最大值，然后删掉中心，递归处理其它子树。统计过中心的路径最大值，我们以中心为根深度搜索一遍，一个需要注意的地方是路径的两个端点不能在同一子树内，因为这样可能会重复统计。所以我们把路径按子树分类，然后点权排序以后更新路径按子树分类的最大值和次大值，之和与当前点权的乘积就是答案。
本题还可以用并查集来解决。将所有点按照权值从大到小排序，对于将当前点和与其相连的所有点依次合并到一个集合中。并查集需要维护当前集合中的最长路径长度和对应的两个端点。在合并两个集合后，最终集合的最长路一定只有两类情况：一类是其中一个集合的最长路，一共有 2 种；一类是由两个集合的最长路的端点互相连接而成，一共有 2×2=4 种。需要用到最近公共祖先的算法预处理求两点在树上的距离，离线处理即可。每次合并并查集之后用当前点的权值乘以最长路的总长度来更新最优结果即可。即使这个点不在当前合并后的集合的最长路上也是没有问题的，因为如果这样的话，必然已经在之前得到了对应的结果，这次合并不会对最终结果产生影响。
Code –点分治
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
#define re
#define int long long
#define LD double
#define MAXN 200010
#define mod 998244353
class Quick_Input_Output{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
char Rd[S],*A,*B;
#define pc putchar
public:
#undef gc
#define gc getchar
inline int read(){
int res=0,f=1;char ch=gc();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
return res*f;
}
inline void write(int x){
if(x<0) pc('-'),x=-x;
if(x<10) pc(x+'0');
else write(x/10),pc(x%10+'0');
}
#undef gc
#undef pc
}I;
#define File freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout);
int n,d[MAXN],vis[MAXN],sz[MAXN],ans,t,cnt;
struct node{int d,w;bool operator <(const node b)const{return d<b.d;}};
inline node make_node(int x,int y){node pp;pp=(node){x,y};return pp;}
struct Tree{int d,w,t;}tr[MAXN];
inline Tree make_tr(int x,int y,int z){Tree pp;pp=(Tree){x,y,z};return pp;}
inline int cmp(Tree x,Tree y){return x.d<y.d;}
class Edge{
public:
int fir[MAXN*2],nxt[MAXN*2],son[MAXN*2],w[MAXN*2],tot;
inline void add(int x,int y,int z){
++tot;
nxt[tot]=fir[x];
fir[x]=tot;
son[tot]=y;
w[tot]=z;
}
}E;
class Solve{
public:
inline void init(){
n=I.read();
for(int i=1;i<=n;i++) d[i]=I.read();
for(int x,y,z,i=1;i<n;i++){
x=I.read();y=I.read();z=I.read();
E.add(x,y,z);
E.add(y,x,z);
}
}
inline node find(int x,int fa,int siz){//找当前树的重心
node res=make_node(2e18,-1);
re int Max=0;sz[x]=1;
for(int to,i=E.fir[x];i;i=E.nxt[i]){
to=E.son[i];
if(vis[to]==1to==fa) continue ;
res=min(res,find(to,x,siz));
sz[x]+=sz[to];
Max=max(Max,sz[to]);
}
Max=max(Max,siz-sz[x]);
res=min(res,make_node(Max,x));
return res;
}
inline void Get_Min_And_Sum(int x,int fa,int _d,int w){//更新点权最小值与边权之和
tr[++t]=make_tr(_d,w,cnt);
for(int to,_w,i=E.fir[x];i;i=E.nxt[i]){
to=E.son[i];_w=E.w[i];
if(to==favis[to]==1) continue ;
Get_Min_And_Sum(to,x,min(_d,d[to]),w+_w);
}
}
inline int get_nowans(){//当前答案
sort(tr+1,tr+t+1,cmp);
// for(int i=1;i<=t;i++){
// cout<<tr[i].d<<" "<<tr[i].w<<" "<<tr[i].t<<endl;
// }
int res=0,sum1=tr[t].w,sum2=0,T=tr[t].t;
for(int i=t-1;i>=1;i--){
if(tr[i].t!=T) res=max(res,tr[i].d*(tr[i].w+sum1));
else res=max(res,tr[i].d*(tr[i].w+sum2));
if(tr[i].w>sum1){
if(tr[i].t==T) sum1=tr[i].w;
else sum2=sum1,sum1=tr[i].w,T=tr[i].t;
}else if(tr[i].w>sum2&&tr[i].t!=T) sum2=tr[i].w;
}
return res;
}
inline int get(int rt,int tot){//递归点分治
int x=find(rt,0,tot).w,res=0;
t=0;
// cout<<"Get "<<rt<<" "<<tot<<" "<<x<<endl;
vis[x]=1;
tr[++t]=make_tr(d[x],0,cnt);
for(int to,w,i=E.fir[x];i;i=E.nxt[i]){
to=E.son[i];w=E.w[i];
if(vis[to]==1) continue ;
++cnt;
Get_Min_And_Sum(to,x,min(d[to],d[x]),w);
}
res=max(res,get_nowans());
for(int to,i=E.fir[x];i;i=E.nxt[i]){
to=E.son[i];
if(vis[to]==1) continue ;
res=max(res,get(to,sz[to]));
}
return res;
}
inline void solve(){
ans=get(1,n);
I.write(ans);putchar('\n');
}
}S;
signed main(){S.init();S.solve();} C. 「NOIP模拟赛 叁」骆驼
题意
我们都熟悉走马步，现在我们定义一种新的移动方式——骆驼步，它在一个国际棋盘上的移动规则是这样的。
可以看出，骆驼步可以向八个方向走动，且不能走出棋盘范围。
现在给出一个 N\times N 的棋盘，其中 N 是5的倍数。
你需要从左上角出发，每步按照骆驼步的规则，经过每个格子恰好一次，且当你走了 N^2−1步后，你离起点恰好只有一步的距离。
请给出一种合法的方案。 N\leq 1000。
思路
因为N是5的倍数。 自然而然地就会想到拿5\times 5的矩阵来构造N\times N的。 然后乱拼下就好了。
腾讯云开发者
