河南理工大学算法协会暑期集训积分赛（二）

欢迎访问我校oj：hpuoj
本场积分赛传送门: Uncle_drew is so handsome

再战斐波那契

Description:
小z 学会了斐波那契和 gcd 后，老师又给他出了个难题，求第N个和第M个斐波那契数的最大公约数，这可难倒了小z ，不过在小z 的再三请求下，老师又告诉他了个条件，gcd(N,M)∈[1,90]。
可是，笨拙的小z 还是不会，于是请求你帮他解答这个问题。

已知:

输入格式
输入包括 T 组，T∈[1,10].
接下来 T 行,每行两个整数 N,M, 表示斐波那契的第 N 项和第 M 项，(N,M∈[1,1e18]).

输出格式
输出包含 T 行,每行输出一个整数.

样例
input

3
1 2
2 3
3 4

output

1
1
1

Problem solving:
神tm签到题。。。
这道题主要是有个规律斐波那契数列第M项和第N项的gcd就是斐波那契数列第gcd（m,n）项的值。即：
gcd(f(m),f(n)) = f(gcd(m,n))
顺便记一下
long long可以存到大概第92项斐波那契数，unsigned一下会再多一项。Ps：我之前一直以为50项就爆long long了。。。如果知道这个92，那猜这个规律应该就挺简单了吧。
而我是跑了N个循环找到的当时并不确定的规律。。。

Code：

#include<bits/stdc++.h>
using namespace std;
unsigned long long a[100],x,y;
int main()
{
    a[0]=0,a[1]=1;
    for(int i=2;i<=100;i++)
    {    a[i]=a[i-1]+a[i-2];
    }
    int t;
    cin>>t;
    while(t--)
    {
        cin>>x>>y;
        cout<<a[__gcd(x,y)]<<endl;
    }
}

恐怖的怪物

Description:
一天早上，Dicer一觉醒来，发现自己来到了MineCraft的世界里面，身为MineCraft游戏爱好者的他欣喜不已，于是他在地下挖了一片长方体的空间作为秘密基地，可是他发现光照亮度小于等于7时，会有恐怖的怪物出现，并且他通过查阅资料发现光源方块产生光照每一米（方格）衰减1光照等级。

此规律在坐标轴的3个方向上（东西、南北、上下）均成立。换句话来说，对角线方向的光照衰减依照“曼哈顿距离”（两个点在坐标系上的绝对轴距总和）计算。这意味着，假如地上插着一支火把（光照等级14），则在水平面上与火把相邻的4个方向的方格上光照等级均为13，而在水平面上与火把对角的4个方格上光照等级均为12（譬如，西北方格的光照等级为14-向西1级-向北1级）。

上述这种衰减特性会在光源周围产生菱形的照明。该效果会在光源周围的光源扩散呈钻石状。如果被不透明方块阻挡，光照也可以沿着复杂而弯曲的路径扩散。

如下图所示，红色为光源（亮度等级为14）,黑色为秘密物品，其余各个位置光照强度如图所示。

秘密基地为N∗M的空间，不考虑高度，初始地面光照强度为0。为了不生成恐怖的怪物，Dicer布置了一些光源，但他不知道是否仍会生成怪物，现在请你帮助Dicer判断。

注：光源及秘密物品均为不透明方块，且其上方均不会生成怪物。

输入格式
第一行是一个T。（1≤T≤100）
接下来有T组数据，每一组第一行是N,M,（1≤N,M≤1000）,接下来有N行，每行M个字符，代表秘密基地地面放置的方块，0代表空气，#代表秘密物品，Y代表萤石(光照等级为15)，H代表火把(光照等级为14)，F代表附魔台(光照等级为12)，R代表激活的红石火把(光照等级为7)。

输出格式
输出包含T行，每行如果仍会生成怪物，输出”Yes”,否则输出”No”。

样例
input

2
2 3
0Y0
00#
3 4
R00#
00R0
0R00

output

No
Yes

input

2
1 5
0Y0R0
2 4
Y#0R
0000

output

Yes
No

input

1
5 4
Y0F0
0000
0000
0000
0000

output

No

Problem solving:
简单？的bfs问题。就是条件有点多。。。比赛的时候写炸了

这道题给了5s，按理说只要查找写的对，就不会超时。我想了一下我的方法，应该是里面出现了死循环，咳咳。

这道题的难点就是每个点的亮度有可能源于两个点，而你肯定要取最大值。但是怎么取？我一开始直接用了max，然后就是一直tle，因为这样会出现死循环的情况，就是满足不了return的情况。后来看了学长的代码，吃了一惊，原来还可以这样写。

开三个队列，分别存储出现Y，H，F的位置。然后从存着Y的队列开始进行bfs，如果当前亮度是到了14，就把装有H的队列中的元素放入第一个队列继续bfs，12也是同理。这一点还挺好理解的。这样操作的话，每个点自然就是可以达到尽可能大的亮度。最后在判断有没有小于等于7的空地存在即可。

在今天之前我还一直以为我的bfs挺不错的。现在我觉得我连mc的资深玩家都不配当了。
Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1010;
int t,n,m,l[maxn][maxn];
char s[maxn][maxn];
int d[4][2]={1,0,0,1,-1,0,0,-1};
struct node{
    int x,y;
};
queue<node> wo,yao,meizi;
bool bfs()
{
    while(!wo.empty())
    {
        int x=wo.front().x;
        int y=wo.front().y;
        wo.pop();
        if(l[x][y]==8)    break;
        for(int i=0;i<4;i++)
        {
            int dx=x+d[i][0];
            int dy=y+d[i][1];
            if(dx<0||dx>=n||dy<0||dy>=m||s[dx][dy]!='0'||l[dx][dy])
                continue;
            l[dx][dy]=l[x][y]-1;
            wo.push({dx,dy});
            while(l[dx][dy]==14&&(!yao.empty()))
            {
                wo.push(yao.front());
                yao.pop();
            }
            while(l[dx][dy]==12&&(!meizi.empty()))
            {
                wo.push(meizi.front());
                meizi.pop();
            }
//            cout<<l[dx][dy]<<endl;
        }
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(l[i][j]<=7&&s[i][j]=='0')    return 0;
    return 1;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        while(!wo.empty())    wo.pop();
        while(!yao.empty())    yao.pop();
        while(!meizi.empty())    meizi.pop();
        memset(l,0,sizeof(l));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin>>s[i][j];
                if(s[i][j]=='Y')    wo.push({i,j}),l[i][j]=15;
                if(s[i][j]=='H')    yao.push({i,j}),l[i][j]=14;
                if(s[i][j]=='F')    meizi.push({i,j}),l[i][j]=12;
            }            
        }
        if(bfs())    puts("No");
        else    puts("Yes");
    }
}

连连看

Description:
众所周知，《连连看》是一个老少皆宜的游戏。
《连连看》是由黄兴武创作的一款PC端益智类游戏，只要将相同的两张牌用三根以内的线段连在一起就可以消除，规则简单容易上手。

现在呢，Boctorio学长突然想玩连连看了，但不是单纯的玩游戏，他想自己出一局连连看。
由于Boctorio学长是一个蒟蒻，他不知道自己出的连连看是否符合能够通过多次操作将其全部消除，所以想要你帮他检查一下他出的连连看是否符合规则。

输入格式
第一行输入个T,表示T组数据（1≤t≤100）
每组数据第一行两个数 n,m ,表示连连看棋盘的长和宽（1≤n,m≤100）
接下来 n 行，每行输入 m 个正整数aij，表示 m 个棋子 (1≤aij≤n∗m)。

每种棋子只会出现一对，因此数据保证只有一种有效结果。

输出格式
每组数据输出一行。
如果棋盘符合规定，输出”Yes”，否则，输出”No”（不包括引号）。

样例
input

3
2 2
1 2
2 1
3 4
1 6 2 3
4 5 3 1
4 2 6 5
4 4
1 2 3 6
8 4 7 8
5 6 5 7
1 2 3 4

output

No
No
Yes

Problem solving:
暂无(毫无思路题)

Code：

/**
 *　　　　　　　　┏┓　　 　┏┓
 * 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　　　┃　　　　　　　┃ 　
 * 　　　　　　　┃　　　━　　 　┃
 * 　　　　　　　┃　＞　　　＜　┃
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┃...　⌒　... 　┃
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┗━┓　　　┏━┛
 * 　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃　　　┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　
 * 　　　　　　　　　┃　　　┃  　　　　　　
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　
 * 　　　　　　　　　┃　　　┗━━━┓
 * 　　　　　　　　　┃　　　　　　　┣┓
 * 　　　　　　　　　┃　　　　　　　┏┛
 * 　　　　　　　　　┗┓┓┏━┳┓┏┛
 * 　　　　　　　　　　┃┫┫　┃┫┫
 * 　　　　　　　　　　┗┻┛　┗┻┛
 */
// warm heart, wagging tail,and a smile just for you!
//
//                            _ooOoo_
//                           o8888888o
//                           88" . "88
//                           (| -_- |)
//                           O\  =  /O
//                        ____/`---'\____
//                      .'  \|     |//  `.
//                     /  \|||  :  |||//  \
//                    /  _||||| -:- |||||-  \
//                    |   | \\  -  /// |   |
//                    | \_|  ''\---/''  |   |
//                    \  .-\__  `-`  ___/-. /
//                  ___`. .'  /--.--\  `. . __
//               ."" '<  `.___\_<|>_/___.'  >'"".
//              | | :  `- \`.;`\ _ /`;.`/ - ` : | |
//              \  \ `-.   \_ __\ /__ _/   .-` /  /
//         ======`-.____`-.___\_____/___.-`____.-'======
//                            `=---='
//        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//

Points in rectangle

Description:
在二维平面中有一个矩形，它的四个坐标点分别为(0,a),(a,0),(n,n−a),(n−a,n)。你现在有m个点，现在你想知道有多少个点是在这个矩形内的(边上的也算)。

输入格式
第一行输入n,a(1≤a\<n≤1e3)。
第二行一个正整数m(1≤m≤1e3),代表你拥有的点的个数，接下来m行，每行一个点的坐标xi,yi(1≤xi,yi≤1e3)。

输出格式
第一行输出在矩形内的点的个数，然后输出在矩形内点的坐标，横坐标大的优先，如果横坐标相同，则纵坐标大的优先。如果没有，输出−1。

样例
input

6 1
5
1 2
1 3
2 3
3 4
4 5

output

4
4 5
3 4
2 3
1 2

Problem solving:
也算是一道签到了吧，就是不太好想，不画一下的话。
我的思路是把四条边的表达式写出来，对每个输入的x找出y的边界值然后进行比较。

如图所示，将图分为三部分，然后我们可以这样判断
1.如果x，y中有一个大于n的，就说明这个点不会在矩形中
2.x\n-a的时候，跟上面一样不过此时上下界对应的值是y2和y4
4.x>a && x\<n-a的时候，上下界对应的值是y3和y4

关于y1，y2,y3,y4的表达式
本题中这个还是很好求得的
y1=-x+a y2=x+a
y3=-x+2*n-a y4=x-a

判断完用结构体排一下序输出即可。

Code：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
}p[1005];
bool cmp(node a,node b)
{
    if(a.x==b.x)    return a.y>b.y;
    return a.x>b.x;
}
int main()
{
    int n,a,m,x,y,pos=0;
    double s,k,sx,sy;
    cin>>n>>a>>m;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y;
        if(x>n||y>n)    continue;
        if(x>=a&&x<=n-a)
        {
            if(y>x+a||y<x-a)    continue;
        }
        if(x<a)
        {
            if(y>x+a||y<-x+a)    continue;
        }
        if(x>n-a)
        {
            if(y<x-a||y>-x+2*n-a)    continue;
        }
        p[pos].x=x,p[pos].y=y;
        pos++;
    }
    if(pos==0)
        puts("-1");
    else
    {
        cout<<pos<<endl;
        sort(p,p+pos,cmp);
        for(int i=0;i<pos;i++)
        {
            cout<<p[i].x<<' '<<p[i].y<<endl;
        }        
    }

}

Numbers of interval

Description:

输入格式
第一行输入n,k(1≤n,k≤1e6).
接下来输入n个数，第i个数为ai(1≤ai≤1e3).

输出格式
输出满足条件的区间个数

样例
input
3 5
2 3 5
output
4

Problem solving:
这道题做出来的人很多，我忘了lower_bound，用一个前缀和数组就行了。注意这道题的ans会爆int。
这道题看了学长的题解和标程之后觉得自己明白的很透彻。然后跟一个同学交流这道题的时候发现自己也是没那么明白。不过现在还是很透彻的，记录一下。

主要需要理解的就是在你构造的前缀和数组中第n项到第m项的和为
sum[m]-sum[n-1](注意是n-1，如果是n的话，那表示的就是第n+1项到第m项的和，因为你会把a[n]也减掉。

现在我们要查找区间和大于等于k的区间个数，因为是前缀和数组，所以构造出来的前缀和数组一定是有序的（升序。如果直接O(n*n)，1e6的数据范围肯定会超时。又正好看到数组是有序的，这时候就~很自然~的想到二分(虽然我并没有想到)。区间和大于等于k即a[m]-a[n-1]>=k,所以我们先确定区间的左端点，然后二分查找到第一个使区间和大于等于k的右端点的值，此时我们找到的这个右端点的右面的每一个端点都可以跟那个确定的左端点组成一个区间和大于等于k的区间，查找所有点为左端点的情况，答案累加即可。
唯一有点绕的就是sum[n]-sum[m-1]>=k换成了sum[m-1]+k<=sum[n]
查找第一个符合要求的右端点可以这样写

lower_bound(sum+1,sum+n+1,k+a[i-1])-sum

Code：

#include<bits/stdc++.h>
using namespace std;
int a[1000050],p[1000050];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i],p[i]=p[i-1]+a[i];
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        int mid=lower_bound(p+1,p+1+n,p[i-1]+k)-p;
        ans+=(n-mid+1);
    }
    cout<<ans<<endl;
}

剪纸

Description:
中国剪纸是一种用剪刀或刻刀在纸上剪刻花纹，用于装点生活或配合其他民俗活动的民间艺术。在中国，剪纸具有广泛的群众基础，交融于各族人民的社会生活，是各种民俗活动的重要组成部分。其传承赓续的视觉形象和造型格式，蕴涵了丰富的文化历史信息，表达了广大民众的社会认以、道德观念、实践经验、生活理想和审美情趣，具有认知、教化、表意、抒情、娱乐、交往等多重社会价值。
2006年5月20日，剪纸艺术遗产经国务院批准列入第一批国家级非物质文化遗产名录 。2009年9月28日至10月2日举行的联合国教科文组织保护非物质文化遗产政府间委员会第四次会议上，中国申报的中国剪纸项目入选“人类非物质文化遗产代表作名录”。

剪窗花最基本的操作为将剪纸进行多次对折，然后对对折之后的纸进行裁剪，展开后就是一个精美的艺术品。现在我们对问题进行化简，我们利用如下方法将一张形状矩形的纸按照对阵轴进行对折：

假设剪后的形状为一个三角形，则展开效果为：

现在给你一个对折两次且剪切后的图形，请你给出展开的图形形状。

输入格式
多组输入，处理到文件结束。
每组输入第一行两个数字n,m（1≤n,m≤100)。
接下来n行，每行m个字符，表示对折且剪切后的图形。
保证输入字符只包含 ‘.’ 和 ‘*’ 。

输出格式
输出展开后的图形。

样例
input

3 3
**.
*..
...

output

......
..**..
.****.
.****.
..**..
......

Problem solving:
签到题，搞清楚每个点的关系就行。（这个我写的可能是有点麻烦了，可以去看一下下面学长的标程

Code：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[405][405];
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        for(int i=n;i<2*n;i++)
            for(int j=m;j<2*m;j++)
                cin>>a[i][j];
        for(int i=n;i<2*n;i++)
        {
            for(int j=0;j<m;j++)
            {
                a[i][j]=a[i][2*m-j-1];
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                a[i][j]=a[2*n-i-1][j];
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j=m;j<2*m;j++)
            {
                a[i][j]=a[2*n-i-1][j];
            }
        }
        for(int i=0;i<2*n;i++)
        {
                for(int j=0;j<2*m;j++)
                cout<<a[i][j];
            puts("");
        }

    }
}

Fake hpuoj predictor

Description:
总所周知，HPU(Harmonious and Peaceful University) Online Judge具有一个强大的的rating(积分)系统，它采用的是国际上权威的ELO等级分制度(ELO Rating System)，LOL，守望先锋,codeforces,topcoder等知名游戏的排行均是采用此制度。
具体算法为：

其中R(A)和R(B)为选手A和B初始的rating，那么E(A)和E(B)即为这两者进行对战后A和B各自获胜的期望。
本场比赛的积分公式即为

RA代表上轮比赛结束后的积分。
K为积分系数,对于不同等级的选手的K是不同的。
SA代表比赛实际总得分，对于每局比赛来说，每赢一个人就会加1分,输了不扣分。
EAi代表A与第i个选手比赛获胜的期望。
对于HPU Online Judge，用户等级表为:

codancer有一个成为Grand Master的梦想，已知他的初始rating为0，他总共参加了m场比赛，对于每场比赛有一个榜单，对于codancer来说，排在他前面的人都打败了他，排在他后面的人都输给了他，因此你可以通过和每个参加比赛的选手比较计算出总得分SA和总期望∑EAi。
那么最终codancer打完本场比赛后的rating为

现在他打完了这m场比赛后他迫切的想知道自己的rating变为了多少(因为管理员太懒了，已经鸽了m场的rating计算了)，现在他想让你帮他写一个预测器来预测一下。

输入格式
单组输入，第一行输入一个m(1≤m≤100)，代表codancer参加的比赛的数量。
接下来对于每场比赛：
第一行输入一个整数n代表有n(1≤n≤100)个人参加的比赛。
接下来n行每行输入一个字符串和数字，代表参赛选手的用户名和他的rating，codancer即为他自己的用户名(用户名长度不超过20)，假如输入的名字为codancer,则不用输入数字(其他参赛选手的rating是不会更新的，因为管理员太懒了)。

输出格式
输出codancer最终的rating，向上取整。

样例
input

3
5
tourist 2000
capryang 1900
boctorio 1800
dicer 1800
codancer
2
codancer
rookie 200
2
wzy 1500
codancer

output

12

提示
每计算完一场都需要向上取整，建议参与运算的变量都使用double。

Problem solving:
这道题的难点就是读题。读懂了之后直接模拟就行了。
学长说：写了就能过。。。
然后我无限wa。最后借了学长的代码看了一下。也没发现有啥不一样的，可能就是精度问题吧。

Code：

#include<bits/stdc++.h>
using namespace std;
double find(double x)
{
    if(x<=1349)    return 15;
    if(x<=1499)    return 20;
    if(x<=1599)    return 25;
    if(x<=1699)    return 30;
    if(x<=1799)    return 35;
    return 50;
}
int main()
{
    int t;
    cin>>t;
    string s;
    double ra=0,rb;
    while(t--)
    {
        int n;
        cin>>n;
        double ea=0,sum=0;
        double k=find(ra),sa=0;
        for(int i=1;i<=n;i++)
        {
            cin>>s;
            if(s=="codancer")
            {
                sa=n-i;
                continue;
            }
            cin>>rb;
            ea=1.0/(1+pow(10,(rb-ra)/400));
            sum+=ea;
        }
        ra=ceil(ra+k*(sa-sum));
    }
    printf("%.0lf\n",ra);
}

花花与三猫Catlive

Description:
“大佬”中分和“呆B”李白正在玩一个游戏，游戏规则是这样的：

1. 游戏刚开始的时候，中分和李白相距L步，相对而望。
2. 老父亲和老母亲手中各有一个M个面的均匀骰子。（也就是说可以随机生成[1,m]内的任意一个数字，且概率均等）
3. 在每个回合开始的时候，老父亲和老母亲都会掷一下手中的骰子。
4. 当老父亲的骰子掷到1的时候，中分可以向李白走一步。
5. 当老母亲的骰子掷到m的时候，李白可以向中分走一步。
6. 当中分和李白相遇的时候，游戏结束。

可是老父亲和老母亲刚刚拍完新节目，他们太累了，不想做这个游戏，但是他们还很想知道，这个游戏平均需要多少次才能结束。聪明的你，能告诉他们吗？

结果是一个实数s，可以证明s能被表示成一个分数 qp，请输出q⋅p−1，其中q−1表示q在模109+7意义下的逆元。

输入格式
第一行是一个正整数 T(1≤T≤1000)，表示测试样例的组数。
接下来T行，每行两个正整数L,M(1≤L,M≤1000)，含义如题面描述。

输出格式
输出包括T行，每行一个答案。

样例
input

2
1 2
2 1

output

1
1

提示
2在模109+7意义下的逆元是500000004
Problem solving:
这道题比赛的时候嫌题面太长我就没看。后来发现这就是一道水题。。。题意就是两个人的距离给出了是L，用一个m面的骰子掷一下，如果是1或者m，就会有人走一步，不用管是谁走，效果都是一样的。所以每次有人走一步的概率就是2/m，总共要走l步，让输出的就是l/（2/m），即l*m/2
表面上这道题还让你求逆元，实际上这里我们用到的只有2的逆元，而且还给出了2在模1e9+7意义下的逆元。所以，是个水题。以后这种看见题面太长就不想看的坏毛病必须得改一下了。

Code：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    long long n,m;
    while(t--)
    {
        cin>>n>>m;
        cout<<n*m*500000004%1000000007<<endl;
    }
}

Same String

Description:
有两个只由小写字母组成的长度为n的字符串s1,s2和m组字母对应关系，每一组关系由两个字母c1和c2组成，代表c1可以直接变成c2,你需要判断s1是否可以通过这m组关系转换为s2。

输入格式
第一行输入一个n(1≤n≤100)，代表字符串的长度。
第二行和第三行输入两个字符串s1,s2。
第四行输入一个m(1≤m≤325)，代表有m组关系。
接下来m行，第i行两个字符ui,vi,代表ui可以直接变为vi。

输出格式
如果s1可以通过这些m组关系转化变为s2，输出”YES”，否则输出”NO”。

样例
input

6
aabbcc
cdbcad
4
a c
c a
a d
b c

output

YES

提示
可以转换多次，比如a可以转换为b，而b可以转换为c，则a可以转换为c。
样例一：aabbcc->cabbcc->cdbbcc->cdbccc->cdbcac->cdbcaa->cdbcad
Problem solving:
这道题我是用存图做的，跟昨天专练里面的一道题很像，就不详细讲了。
这道题还有另一种算法，可以看下面学长的标程
Code：

#include<bits/stdc++.h>
using namespace std;
int mmp[50][50],vis[50];
bool bfs(int x,int y)
{
    queue<int> q;
    q.push(x);vis[x]=1;
    while(!q.empty())
    {
        x=q.front();q.pop();
        if(x==y)    return 1;
        for(int i=0;i<=26;i++)
        {
            if(mmp[x][i]&&vis[i]==0)
            {
                q.push(i);
                vis[i]=1;
            }
        }
    }
    return 0;
}
int main()
{
    int n,m;string a,b;
    char c,d;
    cin>>n>>a>>b>>m;
    for(int i=0;i<m;i++)
    {
        cin>>c>>d;
        int x=c-'a',y=d-'a';
        mmp[x][y]=1;
    }
    int flag=0;
    for(int i=0;i<n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(bfs(a[i]-'a',b[i]-'a')==0)
        {
            flag=1;
            break;
        }
    }
    if(flag)    puts("NO");
    else    puts("YES");
}

学长标程和题解

再战斐波那契

Problem solving:
打表找规律会发现GCD(F(N),F(M))=F(GCD(N,M))

Code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll f[10000];
int main()
{
    ll n,m;
    f[1]=f[2]=1;
    for(int i=3;i<=100;i++) f[i]=f[i-1]+f[i-2];
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%lld %lld",&n,&m);
        printf("%lld\n",f[__gcd(n,m)]);
    }
    return 0;
}

恐怖的怪物

Problem solving:
对于每个有光源的点暴力的BFS
每次BFS 更新各点光源的最大值
不透明方块不需要更新

Code：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1000+10;

int t,n,m;
char mp[maxn][maxn];
int vis[maxn][maxn];
int d[4][2]={1,0,-1,0,0,1,0,-1};
queue<pii>H,F;
queue<pii>que;
void init(){
    while(!que.empty()) que.pop();
    while(!H.empty()) H.pop();
    while(!F.empty()) F.pop();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            vis[i][j]=0;
}
bool BFS(){
    while(!que.empty()){
        int x=que.front().first;
        int y=que.front().second;
        que.pop();
        if(vis[x][y]==8) break;
        for(int i=0;i<4;i++){
            int xx=x+d[i][0];
            int yy=y+d[i][1];
            if(xx<=0 || xx>n || yy<=0 || yy>m || vis[xx][yy] || mp[xx][yy]!='0') continue;
            vis[xx][yy]=vis[x][y]-1;
            que.push(pii(xx,yy));
            while(vis[xx][yy]==14 && (!H.empty())){
                que.push(H.front());
                H.pop();
            }
            while(vis[xx][yy]==12 && (!F.empty())){
                que.push(F.front());
                F.pop();
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(vis[i][j]<=7 && mp[i][j]=='0') return false;
    return true;
}
int main()
{

    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        init();
        for(int i=1;i<=n;i++){
            scanf("%s",mp[i]+1);
            for(int j=1;j<=m;j++){
                if(mp[i][j]=='Y') que.push(pii(i,j)),vis[i][j]=15 ;//15
                if(mp[i][j]=='H') H.push(pii(i,j)),vis[i][j]=14;//14
                if(mp[i][j]=='F') F.push(pii(i,j)),vis[i][j]=12;//12
            }
        }
        if(BFS()) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

连连看

Problem solving:
dfs 瞎胡找即可，保存上一步的位置，上一步的方向，上一
步为止的拐角数，然后处理一些复杂的情况可。
由于只有三个条直线，只能拐两个弯，dfs 能够剪枝至很低
的复杂度，标程大约为0.3s。
（由于年代久远，其实出题人也不太记得这个题是不是有什
么坑了。

Code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mp[200][200];
int n,m;
int sx,sy;
int dir[4][2]={{1,0},{0,1},{0,-1},{-1,0}};//分别对应下，右，左，上
int check(int x,int y){
    if(x<0 || x>n+1 || y<0 || y>m+1)
        return 1;
    return 0;
}

bool judge(int x,int y,int step,int pos){//pos表示上一步方向
    if(step>3) return 0;//如果超过了三步，不符合规则
    if(mp[x][y]==mp[sx][sy] && pos!=-1){//如果两个字符相等并且不是同一个（由于下面有方向限制，所以两个值不可能相等）
        mp[x][y]=0;//删去配对字符
        mp[sx][sy]=0;
        return 1;
    }
    if(mp[x][y]!=0 && pos!=-1) return 0;//如果不相等并且不是通路，不符合规则
    int i,x1,y1;
    for(i=0;i<4;i++){
        if(i+pos==3) continue;//不能有正相反的方向 (0.下 3.上)   (1.右 2.左)
        x1=x+dir[i][0];
        y1=y+dir[i][1];
        if(check(x1,y1)) continue;//检查是否越界
        if(judge(x1,y1,step+(pos==i?0:1),i)){//找到一个就返回
            return 1;
        }
    }
    return 0;
}
int main()
{
    int t,times,sum;
    int i,j;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        memset(mp,0,sizeof(mp));
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                scanf("%d",&mp[i][j]);
            }
        }
        sum=0;
        times=0;//times表示查找的次数，大于等于n*m相当于查找一遍还没有找到
        i=j=1;
        while(sum<n*m && times<n*m){
            for(i=1;i<=n;i++){
                for(j=1;j<=m;j++){
                    times++;
                    sx=i,sy=j;
                    if(mp[i][j]!=0 && judge(i,j,0,-1)){
                        sum+=2;
                        times=0;
                    }
                }
            }
        }
        if(sum==n*m){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
    }
    return 0;
}

Points in rectangle

Problem solving:
对于给定的矩形，求出四个边的直线方程
对于给定的点判断和四条直线的关系即可O(1) 的判断是否
在矩形内
统计完直接排序即可

Code：

#include<bits/stdc++.h>

using namespace std;
const int N = 2e3+100;
struct point{
    long long x,y;
    bool friend operator<(point a,point b){
        if(a.x==b.x) return a.y>b.y;
        return a.x>b.x;
    }
}p[N];
long long n,a;
bool check(point P){
    return -P.x+a<=P.y&&-P.x+2*n-a>=P.y&&P.x-a<=P.y&&P.x+a>=P.y;
}
int main(){
    //freopen("17.in","r",stdin);
    //freopen("17.out","w",stdout);
    vector<point> re;
    cin>>n>>a;
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>p[i].x>>p[i].y;
        if(check(p[i])) re.push_back(p[i]);
    }
    sort(re.begin(),re.end());
    if(re.empty()){
        cout<<-1<<endl;
    }
    else{
        cout<<re.size()<<endl;
        for(auto v:re) cout<<v.x<<' '<<v.y<<endl;
    }
    return 0;
}

Numbers of interval

Problem solving:
构造前缀和数组sum
枚举l 然后二分最小的r，那么r 及其右边的都满足条件
线性枚举即可, 复杂度O(nlog(n))

Code：

#include<bits/stdc++.h>


using namespace std;
const int N = 1e6+100;
typedef long long ll;
long long a[N],sum[N];
int main(){
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
        long long ans=0;
        for(int l=1;l<=n;l++){
            int id=lower_bound(sum+1,sum+n+1,k+sum[l-1])-sum;
            ans+=(n-id+1);
        }
        cout<<ans<<endl;
    return 0;
}

剪纸

Problem solving:
开一个二维数组构造即可

Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
int n,m,a;
char str[1000+10][1000+10];
int main()
{
    while(~scanf("%d %d",&n,&m)){
        for(int i=n;i<n*2;i++){
            scanf("%s",str[i]+m);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                str[i][j]=str[n*2-1-i][j]=str[i][m*2-1-j]=str[n*2-1-i][m*2-1-j];
            }
        }
        for(int i=0;i<n*2;i++){
            for(int j=0;j<m*2;j++){
                printf("%c",str[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

Fake hpuoj predictor

Problem solving:
暴力算出codancer 实际的得分和期望得分
根据他当前的rating 使用不同的K 更新rating
每次更新完rating 向上取整

Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
int n,m,a;
struct node{
    char name[30];
    double rating;
}p[maxn];
double cal(double rating){
    if(rating<1350) return 15.0;
    else if(rating<1500) return 20.0;
    else if(rating<1600) return 25.0;
    else if(rating<1700) return 30.0;
    else if(rating<1800) return 35.0;
    else return 50.0;
}
double Rating(double rating){
    double k=cal(rating);
    double ea=0,sa=0;
    for(int i=0;i<n;i++){
        if(strcmp(p[i].name,"codancer")==0) continue;
        ea+=1.0/(1.0+pow(10,(p[i].rating-rating)/400.0));
    }
    for(int i=0;i<n;i++){
        if(strcmp(p[i].name,"codancer")==0){
            sa=n-1-i;
            break;
        }
    }
    double now_rating=rating+k*(sa-ea);
//    return now_rating;
    return ceil(now_rating);
}
int main()
{
    int m;
    scanf("%d",&m);
    double codancerNB_rating=0.0;
    while(m--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%s",p[i].name);
            if(strcmp(p[i].name,"codancer")==0){
                p[i].rating=codancerNB_rating;
                continue;
            }
            scanf("%lf",&p[i].rating);
        }
        codancerNB_rating=Rating(codancerNB_rating);
    }
    printf("%.0lf\n",ceil(codancerNB_rating));
    return 0;
}

花花与三猫Catlive

Problem solving:
每次每只猫能够向前走一步的概率为2/M
答案即为L/（2/m）= LM/2

Code：

#include<bits/stdc++.h>

const int MOD = 1e9 + 7;
int qpow(int a, int b, int mod){
    int res = 1;
    while(b){
        if(b&1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return res;
}

int inv(int p, int mod){
    return qpow(p, mod - 2, mod);
}

int main(){
    int T;
    scanf("%d", &T);
    int L, M;
    while(T--){
        scanf("%d %d", &L, &M);
        printf("%lld\n", 1LL * L * M * 500000004 % MOD);
    }
}

Same String

Problem solving:
解法一: 对于m 组关系建好图，每次判断某个字母可否到达
另一个字母
解法二: 利用Warshall 可以O(263) 求出传递闭包然后O(1
的判断可达性

Code：

#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+100;
typedef long long ll;
bool f[26][26];
int main(){
    // for(int it=1;it<=40;it++){
    //     memset(f,0,sizeof(f));
    //     Create_InFiles(it);
    //     Create_OutFiles(it);
        int n,m;
        string s1,s2;
        cin>>n>>s1>>s2;
        cin>>m;
        char u,v;
        for(int i=1;i<=m;i++){
            cin>>u>>v;
            f[u-'a'][v-'a']=1;
        }
        for(int j=0;j<26;j++){
            for(int i=0;i<26;i++){
                for(int k=0;k<26;k++){
                    f[i][k]|=(f[i][j]&f[j][k]);
                }
            }
        }
        bool check=0;
        for(int i=0;i<n;i++){
            if(s1[i]!=s2[i]){
                if(f[s1[i]-'a'][s2[i]-'a']==0){
                    check=1;break;
                }
            }
        }
        if(check){
            puts("NO");
        }
        else puts("YES");
    // }
    return 0;
}