2017.08.18【NOIP提高组】模拟赛B组总结

今天第一题，就是道语文题，题面较为恶心，但实际上，这道题是道水题，看懂的人都能对，没有什么意义。

第二题

：
题意：
给你一个n，要你求有多少个正整数二元组(x,y)，满足1x+1y=1n!。
题解：
首先将原式变形，变成这个样子y=n!−xx−n!，然后我们可以很直观的得到一个东西，就是x一定是大于等于n！的。那么x=n！+i，考虑将将分子拆开，变成这个样子（为什么分母是i因为x=n！+i，与后面的n！消掉了），y=(n!)2+i×n!i,后面一项i×n!肯定能被分母整除，我们不管它，那么现在的问题不就是求(n!)2的约数个数吗？
然后用线筛的方法求出它的每个质因子的质数，然后用高精度存答案，注意压位。还有一个常数优化，就是，每次得到一个答案，先判断一下当前答案是否大于模数，如果不是，则等到当前答案大于模数位置再进行高精度乘法。

第三题

题意：自己看

Description

在美鱼和理树后援团拯救世界的同时，外表柔弱的理树也开始坚强起来，思考着离开这个世界的办法。误打误撞地，她遇上了正在教室破坏课桌打开迷宫入口的沙耶。沙耶告诉理树，这个世界的出口就是这个迷宫的出口。于是理树毫不犹豫地跟沙耶一起跳进了迷宫。在迷宫里，两个女孩子互帮互助，一会儿割绳子，一会儿泡温泉，一会儿雕冰块，跌跌撞撞地走到了终点。不出所料，终点也有一个机关在等着她们。
终点的机关是一个立着的m*n 的方格棋盘，在有些格子上放了一个玩偶，而有些地方直接挖了个大坑。只有取走所有玩偶才能打开出口。但是，由于奇怪的设定，理树和沙耶不能直接触碰玩偶，他们需要操纵机器人来收集它。机器人的走法很奇怪，和国际象棋的马有点像，只不过马可以走任意方向的1*2 路线，它们只会由上往下走r*c(或c*r)的路线，不能回头。而机器人一旦经过一个有玩偶的格子，那个格子上的玩偶将被回收，并且在机器人离开时，那个格子会变成一个坑。理树可以把机器人放在任何一个有玩偶的格子上作为起点，也可以在任何一个有玩偶的格子回收机器人。机器人行走可以视为瞬移，只不过每一次设置新起点都会消耗1 时间。并且，有坑的格子不能落脚。就在这个紧要关头，玩偶*爱好者的沙耶却流着口水智商归0。理树不得不转而求助你，帮忙计算出最少多少时间就能收集到所有玩偶。

Input

第一行包含4 个整数M、N、R、C，意义见问题描述。接下来M 行每行一个长度为N 的字符串。如果某个字符是’.’，表示这个地方有一个玩偶；如果这个字符是’x’，表示这个地方是坑。

Output

输出一个整数，表示最短时间。

Sample Input

3 3 1 2
…
.x.
…

Sample Output

4
Data Constraint
30%的数据中，1<=M,N<=4，1<=R,C<=3。
70%的数据中，1<=M<=20，1<=N<=4，1<=R,C<=3。
100%的数据中，1<=M,N<=50，1<=R,C<=10。
Hint

55分做法：直接贪心。
75分做法：dfs四次，每个dfs的顺序都不一样。
其实就是一个二分图匹配，要用到匈牙利算法，本问题的难点在于如何连边，对于一个点，与他连边（下面的点），共有四个（当然前提条件是不是坑），如果能连边就连边，然后就套用匈牙利算法，每次找到一个点就将答案减一，初始化答案为，所有的”.”的个数。

代码

t2：

const
        mo=1000000000;
var
        num,p:array[1..700000+5] of longint;
        bz:array[0..700000+5] of boolean;
        s:ansistring;
        n,i,j,tot2,tot:longint;
        k:int64;
        a:array[0..6000+5] of int64;
procedure work(t:int64);
var
        x,y:int64;
        i:longint;
begin
        x:=0;
        for i:=1 to a[0] do
        begin
                y:=(a[i]*t+x) div mo;
                a[i]:=(a[i]*t+x) mod mo;
                x:=y;
        end;
        while x<>0 do
        begin
                inc(i);
                a[i]:=x mod mo;
                x:=x div mo;
        end;
        a[0]:=i;
end;
begin
        readln(n);
        for i:=1 to n do
                num[i]:=i;
        a[0]:=1;
        a[1]:=1;
        k:=1;
        for i:=2 to n do
        begin
                if not bz[i] then
                begin
                        inc(tot);
                        p[tot]:=i;
                        tot2:=2;
                        for j:=2 to n div i do
                        begin
                                bz[i*j]:=true;
                                while num[i*j] mod i=0 do
                                begin
                                        inc(tot2,2);
                                        num[i*j]:=num[i*j] div i;
                                end;
                                bz[i*j]:=true;
                        end;
                        if k*(tot2+1)>mo then
                        begin
                                work(k);
                                k:=1;
                        end;
                        k:=k*(tot2+1);
                end;
        end;
        work(k);
        write(a[a[0]]);
        for i:=a[0]-1 downto 1 do
        begin
                str(a[i],s);
                while length(s)<=8 do
                        s:='0'+s;
                write(s);
        end;

end.

t3:55分做法：

var
        n,m,r,c,i,j,k,x,y,tot:longint;
        ch:array[-20..70,-20..70] of char;
        bz:array[0..70,0..70] of boolean;
procedure dfs(x,y:longint);
begin
        bz[x,y]:=true;
        if (x+r<=n)and(y+c<=m)and(not bz[x+r,y+c]) then
        begin
                dfs(x+r,y+c);
                exit;
        end;
        if (x+r<=n)and(y-c>0)and(not bz[x+r,y-c]) then
        begin
                dfs(x+r,y-c);
                exit;
        end;
        if (x+c<=n)and(y+r<=m)and(not bz[x+c,y+r]) then
        begin
                dfs(x+c,y+r);
                exit;
        end;
        if (x+c<=n)and(y-r>0)and(not bz[x+c,y-r]) then
        begin
                dfs(x+c,y-r);
                exit;
        end;
end;
begin
        readln(n,m,r,c);
        for i:=1 to n do
        begin
                for j:=1 to m do
                begin
                        read(ch[i,j]);
                        if ch[i,j]='x' then
                                bz[i,j]:=true;
                end;
                readln;
        end;
        x:=1;
        y:=1;
        i:=1;
        j:=1;
        for i:=1 to n do
        begin
                for j:=1 to m do
                begin
                        if not bz[i,j] then
                        begin
                                inc(tot);
                                dfs(i,j);
                        end;
                end;
        end;
        writeln(tot);
end.

t3：100分做法：

const
        u='.';
var
        tot,ans,i,j,k,n,m,r,c:longint;
        ch:array[-50..100,-50..100] of char;
        b,g:array[1..2500]of longint;
        bz,p:array[1..2500]of boolean;
        f:array[1..2500,1..4]of longint;
function find(t:longint):boolean;
var
        i:longint;
begin
        for i:=1 to b[t] do
        begin
                if not bz[f[t,i]] then
                begin
                        bz[f[t,i]]:=true;
                        g[f[t,i]]:=t;
                        exit(true);
                end
                else
                        if not p[f[t,i]] then
                        begin
                                p[f[t,i]]:=true;
                                if find(g[f[t,i]]) then
                                begin
                                        g[f[t,i]]:=t;
                                        exit(true)
                                end;
                        end;
        end;
        exit(false);
end;
function pos(x,y:longint):longint;
begin
        exit(x*n-n+y);
end;
begin
        readln(m,n,r,c);
        for i:=1 to m do
        begin
                for j:=1 to n do
                begin
                        read(ch[i,j]);
                end;
                readln;
        end;
        for i:=1 to m do
        begin
                for j:=1 to n do
                begin
                        if ch[i,j]=u then
                                inc(ans);
                        inc(tot);
                        if ch[i+r,j+c]=u then
                        begin
                                inc(b[tot]);
                                f[tot,b[tot]]:=pos(i+r,j+c);
                        end;
                        if ch[i+r,j-c]=u then
                        begin
                                inc(b[tot]);
                                f[tot,b[tot]]:=pos(i+r,j-c);
                        end;
                        if r<>c then
                        begin
                                if ch[i+c,j+r]=u then
                                begin
                                        inc(b[tot]);
                                        f[tot,b[tot]]:=pos(i+c,j+r);
                                end;
                                if ch[i+c,j-r]=u then
                                begin
                                        inc(b[tot]);
                                        f[tot,b[tot]]:=pos(i+c,j-r);
                                end;
                        end;
                end;
        end;
        for i:=1 to m do
        begin
                for j:=1 to n do
                begin
                        fillchar(p,sizeof(p),0);
                        if ch[i,j]=u then
                        if find(pos(i,j)) then dec(ans);
                end;
        end;
        writeln(ans);
end.

最后几句

其实今天的题目也都不是很难，但考场的分数却又不是很高，还是自己太菜了，需要更多的训练，自是每次总是考完试之后豁然开朗，而在考场中又一筹莫展，只能一步一步来，慢慢进步吧。希望你也加油。

the end

由于我太菜了，难免会有写错的地方，希望大家批评指正，多多包容，thank you for your patience.