虽然这些题目都是算法的板子题 但是实际考试给的时间太少时间相当紧张

所以考前一个月把所有题都再敲一遍熟悉熟悉 顺便丢csdn水水

希望我的这些代码也能登上bsc的查重光荣榜

至少我个人觉得我这个远古马蜂比较好理解一点

1.四个常见问题

众所周知 四个常见问题只有一个

18104 练习使用多case解题

这是第一道题 所以顺便说一下的是bsc的oj里面是不能用万能头的 能用的库我在这个代码里面全部引用一下给各位看一眼 当然也可以复制下去当板子用吧 记得开long long

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <malloc.h>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <queue>
#include <utility>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <functional>
//我校oj只允许使用这些库

using namespace std;
typedef long long i64;
i64 lcd(i64 a,i64 b)
{
    return a*b/__gcd(a,b);
}

int main()
{
    int T=1;
    scanf("%d",&T);
    while(T--)
    {
        i64 a,b;
        scanf("%lld%lld",&a,&b);
        printf("%lld\n",lcd(a,b));
    }
    printf("group 1 done\n");
    i64 a,b;
    scanf("%lld%lld",&a,&b);
    while(a!=0||b!=0)
    {
        printf("%lld\n",lcd(a,b));
        scanf("%lld%lld",&a,&b);
    }
    printf("group 2 done\n");
    while(scanf("%lld%lld",&a,&b)!=-1)
    {
        printf("%lld\n",lcd(a,b));
    }
    printf("group 3 done\n");
    return 0;
}

2.C++ STL的应用

19116 丑数

因为实际上的题目数据远远不到他唬人用的1e8 所以不如直接预处理存进去再调用 当然bsc的本意应该是想让我们开map去重遍历的 我就懒得搞了 反正期末考试能过就行 他自己说数据不会改的

#include <iostream>
#include <algorithm>
#define homo 114514
using namespace std;
typedef long long i64;
int ugly[homo]={0};

int main()
{
    //先预处理ugly数组
    int l2=1,l3=1,l5=1;
    ugly[1]=1;
    for(int i=2;i<=homo;i++)
    {
        ugly[i]=min(ugly[l2]*2,min(ugly[l3]*3,ugly[l5]*5));
        if(ugly[i]==ugly[l2]*2) l2++;
        if(ugly[i]==ugly[l3]*3) l3++;
        if(ugly[i]==ugly[l5]*5) l5++;
        //这里不要手贱加上else 会少很多情况的
    }
    int T=1;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        printf("%d\n",ugly[n]);
    }
    return 0;
}

18005 它不是丑数 

在进行期末考试模拟测试的时候发现有一个隐藏的衍生题也会参与抽题 于是在这里打个补丁

不过好在数据范围甚至比上面那题还要小 所以我们取答案的时候只要改成间隔累加即可

#include <iostream>
#include <algorithm>
#define homo 114514
using namespace std;
typedef long long i64;
int ugly[homo]={0};

int main()
{
    //先预处理ugly数组
    int l2=1,l3=1,l5=1;
    ugly[1]=1;
    for(int i=2;i<=homo;i++)
    {
        ugly[i]=min(ugly[l2]*2,min(ugly[l3]*3,ugly[l5]*5));
        if(ugly[i]==ugly[l2]*2) l2++;
        if(ugly[i]==ugly[l3]*3) l3++;
        if(ugly[i]==ugly[l5]*5) l5++;
        //这里不要手贱加上else 会少很多情况的
    }
    int T=1;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        int count=0;
        int i=0;//记录第几个丑数
        while(count<n)
        {
            count=count+ugly[i+1]-ugly[i]-1;
            i++;
        }
        i--;
        count=count-(ugly[i+1]-ugly[i]-1);
        printf("%d\n",ugly[i]+n-count);
    }
    return 0;
}

18440 走迷宫

就像这一章的标题说的 stl的应用 上一题是map这一题则是queue 一个bfs板子题

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long i64;
struct point{
    int first;
    int second;
    int step;
};
//方向向量
int xto[4]={0,-1,0,1};
int yto[4]={1,0,-1,0};

int main()
{
    int T=1;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        char mp[n][m];
        for(int i=0;i<n;i++)
        {
            scanf("%s",mp[i]);
        }
        int sc,sr,ec,er;
        scanf("%d%d%d%d",&sc,&sr,&ec,&er);
        queue<point> s;
        s.push({sc,sr,0});
        int flag=0;
        while(!s.empty())
        {
            point now=s.front();
            s.pop();
            for(int i=0;i<4;i++)
            {
                point nxt;
                nxt.first=now.first+xto[i];
                nxt.second=now.second+yto[i];
                nxt.step=now.step+1;
                //贪吃蛇型的边界循环 处理一下就行
                if(nxt.first<0) nxt.first=n-1;
                else if(nxt.first==n) nxt.first=0;
                if(nxt.second<0) nxt.second=m-1;
                else if(nxt.second==m) nxt.second=0;
                if(mp[nxt.first][nxt.second]=='0')
                {
                    s.push(nxt);
                    if(nxt.first==ec&&nxt.second==er)
                    {
                        flag=nxt.step;
                        break;
                    }
                    mp[nxt.first][nxt.second]='1';
                }
            }
            if(flag)
                break;
        }
        if(flag==0)
            printf("die\n");
        else
            printf("%d\n",flag);
    }
    return 0;
}

18276 走迷宫2

跟上题相比多了个传送门 思想没有变化 还是bfs

值得一提传送门的位置不能走完就标记为墙 还有就是记得要删边界转移

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long i64;
struct point
{
    int first;
    int second;
    int step;
};
//方向向量
int xto[4]= {0,-1,0,1};
int yto[4]= {1,0,-1,0};

int main()
{
    int T=1;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        char mp[n][m];
        for(int i=0; i<n; i++)
        {
            scanf("%s",mp[i]);
        }
        int t;
        scanf("%d",&t);
        point door[n][m];
        while(t--)
        {
            int ax,ay,bx,by;
            scanf("%d%d%d%d",&ax,&ay,&bx,&by);
            door[ax][ay]= {bx,by,0};
            mp[ax][ay]='2';
        }
        int sc,sr,ec,er;
        scanf("%d%d%d%d",&sc,&sr,&ec,&er);
        queue<point> s;
        s.push({sc,sr,0});
        int flag=-1;
        //printf("Searching:\n");
        while(!s.empty())
        {
            point now=s.front();
            s.pop();
            //printf("x=%d y=%d\n",now.first,now.second);
            if(now.first==ec&&now.second==er)
            {
                flag=now.step;
                break;
            }
            if(mp[now.first][now.second]=='2')
            {
                point next;
                next=door[now.first][now.second];
                next.step=now.step+1;
                s.push(next);
            }
            else
            {
                for(int i=0; i<4; i++)
                {
                    point nxt;
                    nxt.first=now.first+xto[i];
                    nxt.second=now.second+yto[i];
                    nxt.step=now.step+1;
                    if(nxt.first<0||nxt.second<0||nxt.first>=n||nxt.second>=m) continue;
                    if(mp[nxt.first][nxt.second]!='1')
                    {
                        s.push(nxt);
                        if(mp[nxt.first][nxt.second]!='2')
                            mp[nxt.first][nxt.second]='1';
                    }
                }
            }
        }
        if(flag==-1)
            printf("die\n");
        else
            printf("%d\n",flag);
    }
    return 0;
}

18105 银行的叫号顺序

依据题意模拟就可以了 结合本章标题 我们使用优先队列这一数据结构

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long i64;

int main()
{
    int n;
    scanf("%d",&n);
    priority_queue<pair<int, string>>q;//默认就是从小到大排的 不用写cmp
    int serial=99999;//同等级前提下用来记录第几个到
    int now_time=0;
    while(n--)
    {
        int time,level;
        string name;
        cin>>time>>level>>name;
nxt://防伪认证 重生之我是goto大师
        if(time<=now_time)
        {
            q.push({level*100000+serial,name});
            serial--;
            continue;
        }
        if(!q.empty())
        {
            cout<<q.top().second<<endl;
            q.pop();
        }
        now_time+=5;
        goto nxt;
    }
    while(!q.empty())
    {
        cout<<q.top().second<<endl;
        q.pop();
    }
    return 0;
}

18216 银行服务

这个升级真的升级了个寂寞 只需要拿上一题的代码在最后全部输出里面加个条件就行

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long i64;

int main()
{
    int n,off_work;
    scanf("%d%d",&n,&off_work);
    priority_queue<pair<int, string>>q;
    int serial=99999;
    int now_time=0;
    while(n--)
    {
        int time,level;
        string name;
        cin>>time>>level>>name;
nxt://防伪认证 重生之我是goto大师
        if(time<=now_time)
        {
            q.push({level*100000+serial,name});
            serial--;
            continue;
        }
        if(!q.empty())
        {
            cout<<q.top().second<<endl;
            q.pop();
        }
        now_time+=5;
        goto nxt;
    }
    while(!q.empty()&&now_time<=off_work)
    //这里记得把等号删掉 看都不看一眼直接交的wa了活该
    {
        cout<<q.top().second<<endl;
        q.pop();
        now_time+=5;
    }
    return 0;
}

19121 小明手上的牌

优先队列的隐藏题 也是优先队列 照题意模拟即可

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
typedef long long i64;

priority_queue<int,vector<int>,greater<int>> Q;

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int a[m],b[n-m];
    for(int i=0;i<m;i++)
    {
        scanf("%d",&a[i]);
        Q.push(a[i]);
    }
    for(int j=0;j<n-m;j++)
    {
        Q.pop();
        scanf("%d",&b[j]);
        Q.push(b[j]);
    }
    cout<<Q.top()<<endl;
    return 0;
}

19159 小明手上的牌2

这道题是2023年期末考试新出的题 作为5分压轴题放在测试末尾 用于区分背答案和认真学的题 每年最后两道题都是新出的 占10分 当然不保证这道题之后不会加入常规题库

在上面那道题的基础上改成了后面的牌每次取最小的 其实对后面的数排个序就可以了

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
typedef long long i64;

priority_queue<int,vector<int>,greater<int>> Q;

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int a[m],b[n-m];
    for(int i=0;i<m;i++)
    {
        scanf("%d",&a[i]);
        Q.push(a[i]);
    }
    for(int j=0;j<n-m;j++)
        scanf("%d",&b[j]);
    sort(b,b+n-m);
    for(int j=0;j<n-m;j++)
    {
        Q.pop();
        Q.push(b[j]);
    }
    cout<<Q.top()<<endl;
    return 0;
}

18118 勇者斗恶龙

这一题是课上介绍sort的例题 本身就是个贪心 排序完了就行

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long i64;

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    while(n!=0||m!=0)
    {
        int a[n],b[m];
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        for(int i=0;i<m;i++) scanf("%d",&b[i]);
        sort(a,a+n);sort(b,b+m);
        int ret=0;
        int i=0,j=0;
        while(j<m&&i<n)
        {
            if(a[i]<=b[j])
            {
                ret+=b[j];
                i++;j++;
            }
            else j++;
        }
        if(j==m&&i<n)
            printf("Loowater is doomed!\n");
        else
            printf("%d\n",ret);
        scanf("%d%d",&n,&m);
    }
    return 0;
}

18107 校赛排名

也是sort例题 不过这次要自己写cmp

不过注意开stable_sort保证数据相同的情况下按原顺序排列

#include <iostream>
#include <algorithm>

using namespace std;

struct Student
{
    int cnt;
    long long time;
    char name[21];
};
bool cmp(Student a, Student b)
{
    if(a.cnt != b.cnt)
        return a.cnt > b.cnt;
    else if(a.time != b.time)
        return a.time < b.time;
    else
        return false;
}
Student student[500000];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d %d %s", &student[i].cnt, &student[i].time, student[i].name);
    stable_sort(student,student+n,cmp);
    for(int i=0; i<n; i++)
        printf("%s\n", student[i].name);
    return 0;
}

18290 校赛排名2

这题也是无法直接做 但是堂测和期末考试都会抽到这道题

一开始又犯老毛病把数组开在函数里面了 看来上次div4连着RE三发掉大分教训还不够

还得是bsc再次就我于水火之中 回头这两张图哥们直接贴床上警示自己了

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long i64;
struct team
{
    char name[20];
    bool accepted[200]={false};
    int time[200]={0};
    int all_ac=0;
    int all_time=0;
} all[100000];
bool cmp(team a,team b)
{
    if(a.all_ac==b.all_ac)
        return a.all_time<b.all_time;
    return a.all_ac>b.all_ac;
}

int main()
{
    int n=0;//记录总队伍数
    int now_time=0,if_ac=0;
    char team_name[20],question;
    while(scanf("%d %s %c %d",&now_time,team_name,&question,&if_ac)!=EOF)
    {
        int flag=0;//找这个队之前有没有提交过
        int i;
        for(i=0;i<n;i++)
        {
            if(!strcmp(team_name,all[i].name))
            {
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
            strcpy(all[n].name,team_name);
            i=n;
            n++;
        }
        if(if_ac==0)
        {
            all[i].accepted[question]=true;
            all[i].time[question]+=now_time;
        }
        else
        {
            if(!all[i].accepted[question])
            {
                all[i].time[question]+=20;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j='A';j<='O';j++)
        {
            if(all[i].accepted[j])
            {
                all[i].all_ac++;
                all[i].all_time+=all[i].time[j];
            }
        }
    }
    sort(all,all+n,cmp);
    for(int i=0;i<n;i++)
    {
        if(all[i].all_ac==0)
            break;
        printf("%s %d %d\n",all[i].name,all[i].all_ac,all[i].all_time);
    }
    return 0;
}

3.递归思想和分治

递归这个东西就是比较难想 用hd的话来说就是脑子压不了几个栈

1142 巡逻的士兵

对于每个数 他能得到的可能性无非两种：在这个人数的基础上删去奇数和删去偶数 不难看出删完之后不同的路径必然得出不同的结果 所以可以直接写函数进行递归

#include <iostream>
#include <algorithm>

using namespace std;

int solve(int n)
{
    if(n==3)//剩下3个组成一种情况
        return 1;
    if(n<3)//一不小心删多了
        return 0;
    if(n%2==0)
        return solve(n/2)+solve(n/2);
    else
        return solve(n/2)+solve(n/2+1);
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n!=0)
    {
        printf("%d\n",solve(n));
        scanf("%d",&n);
    }
    return 0;
}

但是直接递归发现会超时 所以我们开一个map对中间得到的答案进行存储

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

map<int,int> mp;

int solve(int n)
{
    if(mp[n]!=NULL)
        return mp[n];
    if(n==3)//剩下3个组成一种情况
        return mp[n]=1;
    if(n<3)//一不小心删多了
        return mp[n]=0;
    if(n%2==0)
        return mp[n]=solve(n/2)+solve(n/2);
    else
        return mp[n]=solve(n/2)+solve(n/2+1);
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n!=0)
    {
        printf("%d\n",solve(n));
        scanf("%d",&n);
    }
    return 0;
}

18441 偷懒的士兵

这题和上面几乎一模一样 区别是最小情况的返回值有区别

不过为了防止想不通还是再讲一下 你可以不用和上一道题一样理解成去掉偶数和去掉奇数两种情况 你可以看成是n个士兵中满足条件的一定等于奇数位中满足条件的加上偶数位中满足条件的 那么代码在上一题的基础上小改一下即可

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

map<int,int> mp;

int solve(int n)
{
    if(mp[n]!=NULL)
        return mp[n];
    if(n==3)//剩下3个组成一种情况
        return mp[n]=0;
    if(n<3)//一不小心删多了
        return mp[n]=n;
    if(n%2==0)
        return mp[n]=solve(n/2)+solve(n/2);
    else
        return mp[n]=solve(n/2)+solve(n/2+1);
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n!=0)
    {
        printf("%d\n",solve(n));
        scanf("%d",&n);
    }
    return 0;
}

18442 偷懒的士兵2

这题算是课程里面最难想的一道了 毕竟别的都可以靠背嘛

看起来和上一题区别不大 但是现在我要找的是最小的位置 那我就要找一个合适的方式去记录我现在的位置 但是传入数组的话势必会超时 具体的做法就是每次传入三个值 分别是现在数组的第一个数字 数组中元素两两之间的差值和数组的长度 有了这三个元素 再加上这个数组一些固定的性质 我们就可以知道我们想要的关于这个数组的一切信息 对0要进行特判

#include <iostream>
#include <algorithm>
#include <map>
//如果递归的函数只传入一个值的话可以考虑用map存答案加快运算速度 但是如果传好几个值的话开结构体map就有些得不偿失 一般也不会把题目这么出

using namespace std;

int solve(int n,int head,int del)
{
    if(n==3)//剩下3个组成一种情况
        return 0;
    if(n<3)//一不小心删多了
        return head;
    int a=solve((n+1)/2,head,del*2);//去掉偶数の场合 头不变 长度砍半 距离翻倍
    int b=solve(n/2,head+del,del*2);//去掉奇数の场合 头是第二个 距离翻倍 长度砍半
    if(a>0&&b>0)//特判 0不能参与比较 开挂要封号的
        return min(a,b);
    else if(a>0)
        return a;
    else if(b>0)
        return b;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n!=0)
    {
        printf("%d\n",solve(n,1,1));
        scanf("%d",&n);
    }
    return 0;
}

4.枚举的技巧

个人特别讨厌这章 思路很明显但是码起来太长了 折磨人

再怎么优化的枚举还是枚举 代码大起来还是恶心人

18443 除法等式

枚举除数然后检验被除数 这样可以只需要遍历10*9*8*7*6即可（但是五层循环还是写得人好折磨） 而且里面的细节很多 记得看看注释里面说的

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
typedef long long i64;
int to_int(int a[])//将数组转为整数
{
    return a[0]*10000+a[1]*1000+a[2]*100+a[3]*10+a[4];
}
void solve(int n)
{
    int a[5]={0};//模拟除数
    int flag[15]={0};//记录一个数有没有被用过
    for(a[0]=0;a[0]<=9;a[0]++)
    {
        flag[a[0]]=1;
        for(a[1]=0;a[1]<=9;a[1]++)
        {
            if(flag[a[1]]==1&&a[1]!=0) continue;
            flag[a[1]]=1;
            for(a[2]=0;a[2]<=9;a[2]++)
            {
                if(flag[a[2]]==1&&a[2]!=0) continue;
                flag[a[2]]=1;
                for(a[3]=0;a[3]<=9;a[3]++)
                {
                    if(flag[a[3]]==1&&a[3]!=0) continue;
                    flag[a[3]]=1;
                    for(a[4]=0;a[4]<=9;a[4]++)
                    {
                        if(flag[a[4]]==1&&a[4]!=0) continue;
                        flag[a[4]]=1;
                        int original=to_int(a)*n;//现在找到了被除数 对其进行拆分
                        int legal=1;
                        if(original>=100000)//防止打过5位数
                            legal=0;
                        string s=to_string(original);//C++11中引入的快捷转为字符串的函数
                        int sl=s.length();
                        for(int i=0;i<sl;i++)
                        {
                            if(flag[s[i]-'0']==1&&s[i]!='0')//这里也不要忘了特判0的情况
                            {
                                legal=0;
                                break;
                            }
                            else
                            {
                                flag[s[i]-'0']=1;//这边数完也要记得标记
                            }
                        }
                        //还要排除全是0的情况
                        if(original==0)
                            legal=0;
                        if(legal==1)
                        {
                            printf("%05d/%05d=%d\n",original,to_int(a),n);
                        }
                        //flag数组还需要重置
                        for(int i=0;i<10;i++)
                            flag[i]=0;
                        for(int i=0;i<5;i++)
                            flag[a[i]]=1;
                        flag[a[4]]=0;
                    }
                    flag[a[3]]=0;
                }
                flag[a[2]]=0;
            }
            flag[a[1]]=0;
        }
        flag[a[0]]=0;
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n!=0)
    {
        solve(n);
        printf("\n");
        scanf("%d",&n);
    }
    return 0;
}

上面这个代码优化到3w左右了但还是超时 bsc这题数据限制太死了 找了下参考又写了一个

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long i64;

bool check(int a,int b)
{
    int bl[15]={0};
    for(int i=1;i<=5;i++)
    {
        int lmt=a%10;
        if(bl[lmt]>0&&lmt!=0) return false;
        bl[lmt]++;
        a/=10;
    }
    for(int i=1;i<=5;i++)
    {
        int lmt=b%10;
        if(bl[lmt]>0&&lmt!=0) return false;
        bl[lmt]++;
        b/=10;
    }
    return true;
}

void solve(int n)
{
    for(int i=1;i<=98765;i++)//三万不能过九万过了 想不通
    {
        int original=n*i;
        if(original>=100000) break;
        if(check(original,i))
            printf("%05d/%05d=%d\n",original,i,n);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n!=0)
    {
        solve(n);
        printf("\n");
        scanf("%d",&n);
    }
    return 0;
}

1079 三角形

说是巧爆 其实算是数学题吧 我们简单分析一下 首先肯定要分情况讨论 分别是这条边为斜边和这条边是直角边 题目要求按顺序排 那么很显然先枚举直角边的情况 得出的都是大数

那么我们就看直角边的情况 有公式a²+n²=b² 枚举a和b肯定不行 复杂度太大了 就要用数学方式整理一下再巧爆 我们移个项得到n²=b²-a²=(b-a)(b+a) 那么我们只要找加起来是偶数（奇偶性相同）的两个数乘起来等于n²就可以了 所以我们其实只需要枚举一个b就可以算出a然后再进行判断就可以了 这样我们的复杂度就成功优化到了线性 具体实现请看void part1(int n)函数

至于作为斜边的情况 就愉悦开摆遍历两层吧 反正能过就行 具体实现请看void part2(int n)函数

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long i64;

void part1(int n)
{
    //printf("Part1:\n");
    int s=n*n;//bsc的oj比较抽象 在外面算好尽可能提升速度
    for(int i=1;i<=s;i++)//这里的i是化简后公式里面的(b-a)
    {
        if(s%i==0)//条件1：必须得是s的因数
        {
            int j=s/i;//那么(b+a)就是这里的另一个因数
            if(i*j==s)//条件2：代公式
            {
                if((i+j)%2==0)//条件3：b必须是整数
                {
                    int b=(i+j)/2,a=j-b;//二元一次方程组解出a和b的值
                    if(b<=0||a<=0)
                        continue;
                    printf("%d,%d\n",b,a);
                }
            }
        }
    }
}
void part2(int n)
{
    //printf("Part2:\n");
    int q=n*n;
    for(int a=1;a<n;a++)
    {
        for(int b=a;b<n;b++)//限定b>a
        {
            if(a*a+b*b==q)
            {
                printf("%d,%d\n",b,a);
            }
        }
    }
}

void solve()
{
    int n;
    scanf("%d",&n);
    part1(n);
    part2(n);
}

int main()
{
    int T=1;
    scanf("%d",&T);
    while(T--)
    {
        solve();
        printf("\n");
    }
    return 0;
}

8623 龙龙

也算数学题吧 找规律 发现一旦出现多个重复 那么重复次数和之前的差值有对应关系

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long i64;

void solve()
{
    i64 n;
    scanf("%lld",&n);
    i64 res=0;
    i64 i=1;
    i64 a[n+1]={0};
    i64 m=0;
    while(1)
    {
        a[i]=n/i;
        res+=a[i];
        if(a[i]==a[i-1])
        {
            res-=a[i]*2;
            m=a[i];
            break;
        }
        i++;
    }
    for(i=1;i<=m;i++)
    {
        res+=(a[i]-a[i+1])*i;
    }
    printf("%lld\n",res);
}

int main()
{
    int T=1;
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

发现错误 这是为啥呢 让我们找bsc问一下（

但是n也没提前给范围啊 说明我们根本就不能用数组存 我们要用变量存之前的值 那我们就开工吧

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long i64;

void solve()
{
    i64 n;
    scanf("%lld",&n);
    if(n<0)
    {
        printf("0\n");
        return;
    }
    i64 res=0;
    i64 i=1;
    i64 m=0;
    i64 lst=0;
    while(1)
    {
        i64 tmp=n/i;
        res+=tmp;
        if(tmp==lst)
        {
            res-=tmp*2;
            m=tmp;
            break;
        }
        i++;
        lst=tmp;
    }
    for(i=1;i<=m;i++)
    {
        res+=(n/i-n/(i+1))*i;
    }
    printf("%lld\n",res);
}

int main()
{
    int T=1;
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

18444 分数拆分

这题算是这一节里面最符合巧爆朴素认知的题了 没有太多数学要素 就是尽可能限制遍历的范围和次数 如果你志在天梯赛那我觉得可以多做些这种题 反正学校现在100个名额 争取一下应该不难

巧爆的朴素认知是什么？就是就像上面说的，尽可能少套循环，循环范围限制死一点。

首先是少套循环，在这一题里面两个分数加起来的情况只需要遍历一个即可，三个分数的情况遍历两个即可，另外一个可以使用公式算出来。具体来说，我们以两个为例，公式就是1/k = 1/y + 1/z，我们遍历y的话不难得到z的公式z=k*y/(y-k)，那么内部的条件就是z是不是整数即可。三个也是同理，可以自己尝试推一下，相信初中数学的水平你还是有的。

然后就是遍历的范围，同样以刚才的两个为例，现在我需要遍历的是y，那么y可能得取值范围是多少呢？还是刚才那个式子1/k = 1/y + 1/z<=2/y，所以y<=2*k，我们的遍历范围就有了。同样的，三个的情况你可以自己尝试着推一推。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

void solve(ll n)
{
    //先考虑两个的情况
    for (ll z = n+1; z <= 3*n; z++)
    {
        //先判断两项是否成立,即1/k==1/y+1/z
        //已知k，z，若成立，则所求中y一定为整数，1/y==1/k-1/z, 即 y=k*z/(z-k)
        ll y = n * z / (z - n);
        if ((n * z) % (z - n) == 0 && y >= z)//随着z的递增，y有可能小于z，则判断如果y大于z,则输出式子1/k==1/y+1/z
            printf("1/%lld=1/%lld+1/%lld\n", n, y, z);
    }
    /* 再考虑三个的情况
     * 如果你推了的话应该不难看出遍历z<=3*n
     * k*z/(z-n)<y<=2*n*z/(z-n)+1
     * x=(n*y*z)/(y*z-n*z-n*y)
     * 再判断x是不是整数即可 */
    for(ll z=n+1;z<=3*n;z++)
    {
        ll tmp=n*z/(z-n);
        for(ll y=tmp+1;y<=2*tmp+1;y++)
        {
            ll x=n*y*z/(y*z-n*z-n*y);
            if((n*y*z)%(y*z-n*z-n*y)==0&&x>=y&&y>=z)
                printf("1/%lld=1/%lld+1/%lld+1/%lld\n",n,x,y,z);
        }
    }
}

int main()
{
    ll n;
    scanf("%lld",&n);
    while(n!=0)
    {
        solve(n);
        printf("\n");
        scanf("%lld",&n);
    }
    return 0;
}

发现错误 这是为什么呢 我们看看错误提示 发现顺序有问题 不能先输出两个的情况再输出一个的情况 那其实也好办 把第二个循环放进去就行

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

void solve(ll n)
{
    //先考虑两个的情况
    for (ll z = n+1; z <= 3*n; z++)
    {
        //先判断两项是否成立,即1/k==1/y+1/z
        //已知k，z，若成立，则所求中y一定为整数，1/y==1/k-1/z, 即 y=k*z/(z-k)
        ll y = n * z / (z - n);
        if ((n * z) % (z - n) == 0 && y >= z)//随着z的递增，y有可能小于z，则判断如果y大于z,则输出式子1/k==1/y+1/z
            printf("1/%lld=1/%lld+1/%lld\n", n, y, z);
        /* 再考虑三个的情况
         * 如果你推了的话应该不难看出遍历z<=3*n
         * k*z/(z-n)<y<=2*n*z/(z-n)+1
         * x=(n*y*z)/(y*z-n*z-n*y)
         * 再判断x是不是整数即可 */
        ll tmp=n*z/(z-n);
        for(ll y=tmp+1;y<=2*tmp+1;y++)
        {
            ll x=n*y*z/(y*z-n*z-n*y);
            if((n*y*z)%(y*z-n*z-n*y)==0&&x>=y&&y>=z)
                printf("1/%lld=1/%lld+1/%lld+1/%lld\n",n,x,y,z);
        }
    }
}

int main()
{
    ll n;
    scanf("%lld",&n);
    while(n!=0)
    {
        solve(n);
        printf("\n");
        scanf("%lld",&n);
    }
    return 0;
}

5.搜索算法

顾名思义，这章的主要内容就是bfs和dfs，但是两道题目其实都是dfs，前面说过递归可能比较难想通，也没啥必要想太通，但是dfs一定要想通一点，因为你把模版想通之后所有的题目都很容易想通

18124 N皇后问题

先看一眼bsc的ppt吧家人们

这里的回溯简单来说的形式就是标记->dfs递归->取消标记 直接看代码吧

#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long ll;
using namespace std;
int n,res;
int mp[15][15]={0};//mp[i][j]标识第i行第j个有没有棋子

void dfs(int x)//传入行号
{
    if(x==n)//终止条件写在最前面
    {
        res++;
        return ;
    }
    for(int i=0;i<n;i++)
    {
        mp[x][i]=1;//尝试把皇后放在各列
        int j=0;
        for(j=0;j<x;j++)//找之前的
        {
            if(mp[j][i]==1)//在同一列
                break;
            int del=x-j;
            if(mp[j][i-del]==1||mp[j][i+del]==1)//在同一条对角线上
                break;
        }
        if(j==x)//一直到最后都没有break
            dfs(x+1);//再递归找下一行
        mp[x][i]=0;//这里一定要记得标记回去 不然怎么叫回溯呢
    }
}

int main()
{
    int T=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(mp,0,sizeof(mp));
        res=0;//初始化
        dfs(0);
        printf("%d\n",res);
    }
}

这个二维的有点小烦所以改成了一维的 更加方便 不需要我手动标记 循环过程中会自己覆盖掉

#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long ll;
using namespace std;
int n,res;
int mp[15]={0};//mp[i]记录第i行放皇后的列数

void dfs(int x)//传入行号
{
    if(x==n)//终止条件写在最前面
    {
        res++;
        return ;
    }
    for(int i=0;i<n;i++)
    {
        mp[x]=i;//尝试把皇后放在各列
        int j=0;
        for(j=0;j<x;j++)//找之前的
        {
            if(mp[x]==mp[j])//在同一列
                break;
            if(mp[x]-x==mp[j]-j||mp[x]+x==mp[j]+j)//在同一条对角线上
                break;
        }
        if(j==x)//一直到最后都没有break
            dfs(x+1);//再递归找下一行
    }
}

int main()
{
    int T=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(mp,0,sizeof(mp));
        res=0;//初始化
        dfs(0);
        printf("%d\n",res);
    }
}

19010 最小的特殊数字 

只给最多十个数字 那随便排嘛 全排列问题

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n,k,ans=1e18,a[12],b[12],bl[12];
ll to_ll()
{
    ll ret=0;
    for(int i=1;i<=n;i++)
        ret=ret*10+b[i];
    return ret;
}
void dfs(int x)
{
    if(x==n+1)//终止条件
    {
        if(to_ll()%k==0)
            ans=min(ans,to_ll());
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(x==1&&a[i]==0)
            continue;
        if(bl[i]==0)
        {
            bl[i]=1;
            b[x]=a[i];
            dfs(x+1);
            bl[i]=0;//记得回溯
        }
    }
}

int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    if(n==1&&a[1]==0)//题目也说了要特判
    {
        printf("0\n");
        return 0;
    }
    sort(a+1,a+n+1);
    dfs(1);
    if(ans==1e18)
        printf("-1\n");
    else
        printf("%lld\n",ans);
    return 0;
}

6.动态规划算法

8615 快乐

一道很基础的01背包模板题 需要注意的就是因为至少要有1 所以先减1最后加1

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main()
{
    int n;
    scanf("%d",&n);
    int gethappy[n]={0},losspow[n]={0};
    for(int i=0;i<n;i++) scanf("%d",&gethappy[i]);
    for(int i=0;i<n;i++) scanf("%d",&losspow[i]);
    int dp[n+1][1999]={0};
    for(int i=0;i<1999;i++)//初始化
    {
        if(i>=losspow[0])//一旦j足够我学了就学进去
        {
            dp[0][i]=gethappy[0];
        }
        else
        {
            dp[0][i]=0;
        }
    }
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<1999;j++)
        {
            if(losspow[i]>j)//如果精力不够我学新的
                dp[i][j]=dp[i-1][j];
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-losspow[i]]+gethappy[i]);
            }
        }
    }
    printf("%d\n",dp[n-1][1998]+1);
    return 0;
}

18705 01背包问题

正统来了 和刚才一样 这个我就直接找了个模板改了一下丢上来了

#include<iostream>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    cin >> m >> n;
    for(int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;

    return 0;
}

19523 最长上升子序列长度

比背包简单的dp基础题 我们只需要扫两层 对一个数i，前面如果有比他小的j，那么到i为止的最长上升子序列长度dp[i]=max(dp[j]+1,dp[i])

#include <iostream>

using namespace std;

int main()
{
    int n;
    scanf("%d",&n);
    while(n!=0)
    {
        int a[n+1];
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int dp[n+1]={0};
        for(int i=1;i<=n;i++)
        {
            dp[i]=1;
            for(int j=1;j<i;j++)
            {
                if(a[i]>a[j])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
            ans=max(ans,dp[i]);
        printf("%d\n",ans);
        scanf("%d",&n);
    }
    return 0;
}

18308 最长公共子序列长度

dp[i][j]表示字符串s1前i位和s2前j位中最长公共子序列的长度 那么转移方程也就很显然了

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string s1,s2;
    cin>>s1;
    cin>>s2;
    int l1=s1.length(),l2=s2.length();
    int dp[l1+1][l2+1]={0};
    int flag=0;
    for(int i=0;i<l1;i++)
    {
        if(s1[i]==s2[0])
            flag=1;
        dp[i][0]=flag;
    }
    flag=0;
    for(int j=0;j<l2;j++)
    {
        if(s2[j]==s1[0])
            flag=1;
        dp[0][j]=flag;
    }
    for(int i=1;i<l1;i++)
    {
        for(int j=1;j<l2;j++)
        {
            if(s1[i]==s2[j])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    printf("%d\n",dp[l1-1][l2-1]);
    return 0;
}

7.并查集与树状树组

18233 万湖之国的形成

如章节名所示 这一题要使用并查集 数据结构本身三言两语讲不完 直接看链接里面的文章吧 我们这里就直接用里面的板子了

#include <iostream>
#include <algorithm>
using namespace std;
struct hole{
    double x;
    double y;
    double r;
};
hole all[100005];
int pre[100005];
bool cmp(hole a,hole b)//排序一下可以大大提升计算速度
{
    return a.x-a.r<b.x-b.r;
}
bool check(hole a,hole b)//检查两个坑是否相交
{
    double distance=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    if(distance<(a.r+b.r)*(a.r+b.r))
        return true;
    return false;
}

int find(int x)     				//查找结点 x的根结点
{
    if(pre[x] == x) return x;		//递归出口：x的上级为 x本身，即 x为根结点
    return pre[x] = find(pre[x]);	//此代码相当于先找到根结点 rootx，然后pre[x]=rootx
}

int main()
{
    int n;
    scanf("%d",&n);
    int res=n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf",&all[i].x,&all[i].y,&all[i].r);
        pre[i]=i;
    }
    sort(all+1,all+1+n,cmp);//标记数组没必要改 因为还是一个一个点
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(all[j].x-all[j].r>=all[i].x+all[i].r)
                break;
            if(check(all[i],all[j]))
            {
                int pi=find(i);
                int pj=find(j);
                if(pi!=pj)
                {
                    res--;
                    pre[pi]=pj;
                }
            }
        }
    }
    printf("%d\n",res);
    return 0;
}

18130 繁忙的公路

最后一题 我们要用到树状数组 这里就直接改了一下文内的代码

#include<iostream>
#define lowbit(x) (x&(-x))
typedef long long ll;
using namespace std;
int c[2000006];
int n,m;
ll ans;
void add_dandian(int x,int k)
{
    for(int i=x;i<=n;i+=lowbit(i))
        c[i]+=k;
}
void search(int begin,int end)
{
    for(int i=end;i;i-=lowbit(i))
        ans+=c[i];
    for(int i=begin-1;i;i-=lowbit(i))
        ans-=c[i];
}
int main()
{
    scanf("%d\n%d\n",&n,&m);
    //printf("n=%d m=%d\n",n,m);
    for(int i=1;i<=n;i++)
    {
        int number;
        scanf("%d\n",&number);
        add_dandian(i,number);
    }
    while(m--)
    {
        char choice;
        int x,y;
        scanf("%c %d %d\n",&choice,&x,&y);
        //printf("%c %d %d\n",choice,x,y);
        if(choice=='H') add_dandian(x,y);
        else if(choice=='Q')
        {
            ans=0;
            search(x,y);
            printf("%lld\n",ans);
        }
    }
    return 0;
}