“九韶杯”河科院程序设计协会第一届程序设计竞赛题目分析以及总结

还是有很多不足的，模拟思维还需加强，还有一直被诟病的图论

一：6的个数；

水题，没有过多的花里胡哨，手算（不太建议）或者代码模拟即可

参考代码如下：

#pragma GCC optimize(3)
#include
using namespace std;
int n=2021, num = 0;
int main()
{
    ios::sync_with_stdio(false);
    for (register int i = 1; i <= 2021; i++)
    {
        int num1=i;
        while (num1)
        {
            if (num1 % 10==6)num++;
            num1 /= 10;
        }
    }
    cout<<num;
    return 0;
}

二：小明的作业；

不好意思，错了，我是弱鸡；

三：斐波那契（模拟思维的具体体现）

提供两种思路

1.常见的gcd写法，即gcd的递归写法，也有相应的辗转相除法，不在赘叙；

#pragma GCC optimize(3)
#include
using namespace std;
int a[100]={0,1,1};
int b[100];
long long  fenzi;
long long  fenmu;
long long  gcd(long long  a,long long  b)//手写gcd函数 
{
    if(b==0) return a;
    return gcd(b,a%b);
}
int main()
{
    for(register int i=3;i<=18;i++)
    {
        a[i]=a[i-1]+a[i-2];
    }
    for(int i=1;i<=13;i++)
    {
        b[i]=a[i]*a[i+1];//分母 
    }
    fenzi=1;//分子 
    fenmu=1;//分母 
    for(int i=2;i<=13;i++)
    {
        fenzi=fenzi*b[i]+1*fenmu;
        fenmu=fenmu*b[i];
        long long  temp=gcd(fenzi,fenmu);//两者的最大共约数 
        fenzi=fenzi/temp;//通分 ,不通分的后果就是程序不走或者直接爆 
        fenmu=fenmu/temp;//通分 
    } 
    cout<"/"<endl;
    return 0;
} 

还要一种是关于STL库里好像是直接能写一种gcd函数，具体请看这篇https://blog.csdn.net/qq_44731019/article/details/109478391（转载），然后网上给出的代码思路也是和手写gcd大致的，这个相较于手写省去了很多麻烦，学到了；

摘自网上代码：

#include
#include
using namespace std;
int main()
{
    long long f[14];
    f[0]=1;
    f[1]=1;
    for(int i=2;i<=13;i++)
    {
        f[i]=f[i-1]+f[i-2];
    }
    long long up=1,down=1;
    for(int i=1;i<13;i++)
    {
        long long x=f[i]*f[i+1];
        long long k=__gcd(x,down);
        down*=(x/k);
        up=up*(x/k)+down/x;
    }
    long long k=__gcd(up,down);
    up/=k;
    down/=k;
    cout<'/'<endl;
    return 0;
}

四：数列重组；

全排列肯定是少不了了，久违的next_permutation()肯定是要用的，

大体思路即是，在按照字典序的情况下，先判断是否升序还是降序，并且对他们进行标记，然后满足了三个开始重新标记，即进行下一轮的升序或者降序判断，并且在满足条件的时候加一

参考代码如下:

#pragma GCC optimize(3) 
#include 
using namespace std;
int a[20] = {2, 3, 3, 3, 5, 6, 6, 7, 7, 8};
int ans;//放结果 
int main(){
    ios::sync_with_stdio(false); 
    do{//next_permutaion()一般搭配do-while使用 
        bool flag1 = false, flag2 = false;//flag1表示之前是否出现递增，flag2表示之前是否出现递减
        int cnt = 0;//计数器 
        for(register int i = 0;i<9; i++){//为社么是小于9呢？因为有i+1,那这样最后一个会越界，然后结果减半 
            if(a[i + 1] > a[i]){
                flag1 = true;
                if(flag2){
                     cnt ++;
                    flag2 = false;
                     flag1 = false;//flag1也要，因为当出现分割点后每次要从新的起点开始算，不受之前的区间影响了

                }

            }
            else if(a[i + 1] < a[i]){
                flag2 = true;
                if(flag1){
                    cnt ++;
                    flag1 = false;
                    flag2 = false;
                }

            }
        }
        if(cnt <= 2) ans ++;
    }while(next_permutation(a, a + 10));//按字典序排序 
    cout << ans;
    return 0;
}

五：三角形个数

妥妥的好题，模拟思维的具体体现，这个题我是最后才做的，刚开始确实没想到是等差数列；不过网上大多数人说用前缀和求，我是弱鸡，我不会(●ˇ∀ˇ●)

具体思路：

其实是找倒三角和正三角的个数，很不好找的其实

如果三角形的边长是i

对于大三角形来说，如果正三角形是以1开始，到n-i+1结束的等差数列

而对于倒三角来说，是从1开始，到n-2i+1结束的；

#pragma GCC optimizee(3)
#include
using namespace std;
const long long  M=1e9+7;
int main()
{
    ios::sync_with_stdio(false);
    long long d=20210411,n;
    long long sumz=0;  
    for(n=d;n>=1;n--)
        sumz=(sumz+n*(n+1)/2)%M;
    long long sumd=0;  
    for(n=d-1;n>=1;n-=2)
        sumd=(sumd+n*(n+1)/2)%M;
    printf("%lld\n",(sumz+sumd)%M);
    return 0;
}

此外，本题特别鸣谢我身旁的zhy同学，如果他不和我说这个题是等差并且一直在坚持这个题，或许我就give up了；

六：字符串

没有什么特殊的技巧，值得注意的是关于如何接受空格符的问题，这里有两种方法：

1.getline函数：http://c.biancheng.net/view/1345.html（转载）

2.输入的正则用法：https://blog.csdn.net/weixin_43469047/article/details/83753526（转载）；

不得不说长见识了

七：不会

八：友谊纽带

唉，bfs我是很不擅长的，主要是用太多了STL关于队列的操作，我当时都不知道怎么做出来的，并且我的代码和网上标准答案大相径庭，还是学习大佬的代码把

/*1.这题一开始我读题目了，我以为的是把这些点全部连接起来所需要的最小边数；
    于是我用了并查集，只过了两个点~
2.后来发现题目是要求找出一个连通块里的任意两点的距离，也就是连通块的最大长度；
    这样的话我们就可以用BFS暴力搜索所有节点，找出它们距其他节点的最远距离`的最大值`；
    当一次广搜之后仍有节点未被访问的则说明该图不只有一个连通块，输出-1；
*/
#include
using namespace std;
vector<int>G[2005];
int vis[2005];
int BFS(int x){
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(x);
    int ans=0;
    while(!q.empty()){
        int f=q.front();
        q.pop();
        ans=max(ans,vis[f]);
        for(int i=0;i){
            int temp=G[f][i];
            if(vis[temp]==0){
                vis[temp]=vis[f]+1;
                q.push(temp);
            }
        }
    }
    return ans;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i){
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    } 
    int ans=0;
    bool flag=true;
    for(int j=1;j<=n;j++){
        ans=max(ans,BFS(j));
        for(int i=1;i<=n;i++)
            if(vis[i]==0){
                flag=false;break;
            }
    }
    if(flag)
    cout<endl;
    else cout<<"-1"<<endl;
    return 0;
}

转载自：https://blog.csdn.net/alpha_xia/article/details/115703564?spm=1001.2101.3001.6650.2&utm_medium=distribute.pc_relevant.none-task-blog-2~default~OPENSEARCH~Rate-2.pc_relevant_antiscanv2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~OPENSEARCH~Rate-2.pc_relevant_antiscanv2&utm_relevant_index=4；

九：传送门

这题我知道是克鲁斯卡尔啊，我没板子不会写，太难了，寒假的时候最小生成树就不会，主要是图论太难了；

十：最后一个小时的时光，我当时脑子已经一片混沌了，这题我没记错的话应该是直接爆搜了，毕竟我也没啥技巧了，只能搜了，唉；

思路是：枚举出每种获胜情况，并且用check函数检验

然后接下来就是搜了
利用dfs来搜接下来下的一步棋的所有情况
当x==10是结束条件，其实在某一定程度上很像2n皇后，但又不像；

难度较高，高级的思维模拟题，如果没有技巧建议深搜，毕竟搜可以混一部分的分数，运气好的话还可以过

#pragma GCC optimize(3) 
#include 
using namespace std;
int p[100];
int n;
int ans;
int check(int u)//检查函数 
{
    if(p[0]+p[4]+p[8]==3*u||p[2]+p[4]+p[6]==3*u)
     return 1;
    if(p[0]+p[3]+p[6]==3*u||p[1]+p[4]+p[7]==3*u||p[2]+p[5]+p[8]==3*u) 
    return 1;
    if(p[0]+p[1]+p[2]==3*u||p[3]+p[4]+p[5]==3*u||p[6]+p[7]+p[8]==3*u) 
    return 1;
    else
    return 0;
}
int dfs(int x)//深搜 
{
    if(x==10)//边界条件 
    {
        if(check(1)) return 1;//正常返回 
        if(check(-1)) return -1;//异常返回，此处也可以用bool判断 
        return 0; 
    }
    //开始模拟，怎么这么多模拟题 
    int t,lost=0,win=0,d=0;
    if(x&1) t=1;
    else t=-1;
    for(int i=0;i<9;i++)
    {
        if(p[i]==0)
        {
            p[i]=t;
            if(check(t)) win++;
            else
            {
               int p=dfs(x+1);
                if(p==t)
                    win++;
                else if(p==0) d++;
                else lost++;
            }
            p[i]=0;
        }
    }
    if(win!=0) 
    return t;
    else if(d!=0) 
    return 0;
    else 
    return (-1*t);
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        ans=0;
        memset(p,0,sizeof(p));
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            int x,y;
            cin>>x>>y;
            x--;
            y--;
            if(i&1) p[x*3+y]=1;//按位与运算，取 2进制整数 i 的最低位，如果最低位是1 则得1，如果最低位是0 则得0。 奇数 i 的最低位 是1，偶数i 的最低位 是0。 
            else p[x*3+y]=-1;
        }   
    ans=dfs(n+1);
    if(ans==1) cout<<'X'<<endl;
    else if(ans==0)
        cout<<-1<<endl;
    else cout<<'O'<<endl;
    }
    return 0;
}

总结：

通过这次模拟赛，很明确的是，对于难题，思维题，较难的模拟题，还有图论尤其是最小生成树方面还是有很多的不足

但是也得到了一些经验：做不出来或者没思路的时候搜也是一种不错的选择；

下一步加强搜索的优化和训练，学习一些自己在图论上知识的空缺，加强模拟题以及思维题的训练，即使难，多练，也会熟能生巧的；

道阻且长，兴则将至，戒骄戒躁，任重道远，早日成为自己想成为的人。

奔向远方，加油加油！