HHHOJ NOIP2020模拟赛（叁）2020.02.03 题解

(Updated: )
oi
, ,

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#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 –点分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#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$的。 然后乱拼下就好了。