寒假第一、二场合集-创新互联

• 写在前面
• 第一场
• • 7-2 签到题
  • • 题目内容
    • 输入格式
    • 输出格式:
    • 输入样例:
    • 输出样例
    • 我的代码
    • 总结
    • • 问题分析
      • lowbit函数
  • 7-6 dh与学妹过桥
  • • 题目内容
    • 输入格式
    • 输出格式:
    • 输入样例:
    • 输出样例
    • AC代码
    • 总结
    • • 解题思路
  • 7-7 有多少个质数
  • • 题目内容
    • 输入格式
    • 输出格式:
    • 输入样例:
    • 输出样例
    • 我的代码
    • AC代码
    • 总结：
    • • 问题分析：
      • 埃氏筛
  • 7-8 天上也会掉馅饼
  • • 题目内容
    • 输入格式
    • 输出格式:
    • 输入样例:
    • 输出样例
    • AC代码
    • 总结
    • • 解题思路
  • 7-9 遍遍遍历
  • • 题目内容
    • 输入格式
    • 输出格式:
    • 输入样例:
    • 输出样例
    • AC代码1
    • AC代码2
    • 总结
    • • 解题思路
  • 7-10 无间道
  • • 题目内容
    • 输入格式
    • 输出格式:
    • 输入样例:
    • 输出样例
    • 我的代码（不是正确的代码）
    • AC代码
    • 总结
    • • 问题分析
      • 解题思路
  • 7-11 简单的图
  • • 题目内容
    • 输入格式
    • 输出格式:
    • 输入样例:
    • 输出样例
    • AC代码
    • 总结
    • • 解题思路
• 第二场
• • 7-6 YooQ和olderciyuan玩石子
  • • 题目内容
    • 输入格式
    • 输出格式:
    • 输入样例:
    • 输出样例
    • AC代码
    • 总结
    • • 问题分析
      • 解题思路
      • 注意
  • 7-7 霸道
  • • 题目内容
    • 输入格式
    • 输出格式:
    • 输入样例:
    • 输出样例
    • AC代码
    • 总结
    • • 问题分析
      • 解题思路
      • 注意
  • 7-9 WaWa机
  • • 题目内容
    • 输入格式
    • 输出格式:
    • 输入样例:
    • 输出样例
    • AC代码
    • 总结
    • • 问题分析
      • 解题思路
• 写在后面

如果有佬发现文章中有任何问题（包括但不限于引用题目以及码的佬的文章的版权问题），欢迎随时踢我。

第一场共11题，AC6题，其中有一题数据不是特别完善，被我钻了空子。涉及知识点：位运算、 dp、 数论、 模拟、 二叉树、 图的构建

小明和小东是生活在二进制世界的人，一天他们分别获得了一个十进制数，他们想通过将该十进制数分解成二进制数，然后取出其二进制下最小非零数值的部分进行比较，如果小明的更小那么输出"xiaoming"，如果小东的更小输入“xiaodong”，如果一样小输出“same”。

第一行输入一个整数 1≤t≤1000 , 代表测试数据的组数。

每组数据输入一行，每行两个正整数 x,y ,x是小明获得的数 , y是小东获得的数 .

保证所有输入数据 1≤x,y≤1e18.

参考题意输出格式即可。

2
1 1
2 1

same
xiaodong

#includeusing namespace std;
#define int long long
signed main()
{int t;
    cin>>t;
    while(t--)
    {long long a,b;
        long long ma=0,mb=0,x=0,y=0;
        cin>>a>>b;
        while(a)//计算数字a中出现第一个1前有多少个0
        {ma=a%2;//用十进制转二进制的方法取末位
            a/=2;
            if(ma==0)
                x++;
            else
                break;
        }
        while(b)//计算数字b中出现第一个1前有多少个0
        {mb=b%2;
            b/=2;
            if(mb==0)
                y++;
            else
                break;
        }
        if(x==y)
            cout<<"same"<<'\n';
        else if(x>y)
        {cout<<"xiaodong"<<'\n';
        }
        else
            cout<<"xiaoming"<<'\n';
    }
    return 0;
}

这题我练习的时候花了很多时间，主要是对“其二进制下最小非零数值的部分”的理解花了很长时间。在网上冲浪的时候，发现有一个叫lowbit()的函数能处理这个题目。

lowbit(x)的值是x的二进制表达式中最低位的1所对应的十进制值，简单来说，lowbit(x)是将 x 转化成二进制数之后，只保留最低位（从右往左数，第一位）的1及其后面的0，截断前面的内容，然后再转成10进制数。

举个栗子🌰，lowbit（6）=2

代码码在这

int lowbit(int x)
{return x&(-x);
}

有个佬的总结挺好的，我就不赘述了，链接码在这
https://blog.csdn.net/weixin_44694201/article/details/118034246

注：
1:lowbit(x)不是一个封装好的函数，要自己手搓
2:lowbit(x)有几种不同的写法，比较推荐上面这种，容易理解

吃完饭后dh和学妹一起走到了一条江边，有两列平行的石墩桥，每个石墩上都有一个小写字母，dh对学妹说：我走上面这列石墩，你走下面的石墩，我先走一个石墩然后你在你那列石墩跟着我走一个同样字母的石墩，一直向前走，直到过了这条河，你知道你最多能踩多少个石墩吗？你答的出来吗？

输出两行字符串，表示两列石墩桥(字符串长度大不超过1000)

输出一个整数，表示最多走多少个石墩

abcdef
acebeee

3

#includeusing namespace std;
const int N =1e3+5;
#define int long long
char a[N],b[N];
int f[N][N];
signed main()
{scanf("%s%s",a,b);
    for (int i = 0;i< strlen(a); i ++)
        for (int j = 0; j< strlen(b); j ++)
        {if (a[i] == b[j])  f[i + 1][j + 1] = f[i][j] + 1;
            else f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j]);
        }
    cout<< f[strlen(a)][strlen(b)]<< endl;
    return 0; 
}

这题我写错了，后面借助网络的力量，发现理解错题目了。dh走一步，学妹不一定要走到dh站的石墩上的字母上，抽象一下就是典型的dp最长公共子序列（LCS）。

这里也把佬的总结码在这
https://blog.csdn.net/qq_62362934/article/details/125919681

注：佬的总结跟我的有点不一样

1.设计状态（定义一个数组，确定其各维含义）

i表示当dh走到a的i位置，j表示学妹走到b的j位置，f[i][j]表示dh走到a的i位置，学妹走到b的j位置时，学妹走的石墩数。其中学妹走过的石墩上的字母，即为a的最长公共子序列，f[i][j]表示最长公共子序列的长度。

2.状态转移方程（类似于数学归纳法，由前面的数据根据一定的关系推出后面的数据）

1)如果有某一个字符串为空的话，f[i][j]=0，在这个是全局变量，初始化为0，不用特别考虑

2)如果a[i]=b[j]，那么dh走一步，学妹也走一步，最长公共子序列的长度可以在原来的基础上+1，表示为：

if(a[i]==b[i]) f[i+1][j+1] = f[i][j - 1] + 1;

3)如果a[i]!=b[j],这时有两种选择，要么dh走一步，要么学妹走一步，又要求大，那么表示为：

f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j]);

3.找出初始值

这里是全局变量，初始化为0。

给一个正整数 n ，你需要求出 1,2,3,…,n 这 n 个数字有多少个是质数。
质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

在一行中给出一个正整数 n (1<=n<=30,000,000)

在一行中输出一个数字，表示 1,2,3,…,n 有多少个数字是质数。

10

4

#includeusing namespace std;
#define int long long
int n,sum;
int jugde(int x)
{if(x<2)
        return 0;
    if(x==2||x==3)
        return 1;
    if(x%4!=1&&x%4!=3)
        return 0;
    for(int i=3; i*i<=x; i+=4)
    {if(x%i==0||x%(i+2)==0)
            return 0;
    }
    return 1;

}
signed main()
{cin>>n;
    for(int i=2;i<=n;i++)
    {if(jugde(i))
            sum++;
    }
    cout<

#includeusing namespace std;
const int maxn=3e7+5;
bool su[maxn];
int primer[maxn];
int main()
{int n,sum=0;
    cin>>n;
    su[0]=su[1]=true;
    for(int i=2;i<=n;i++)
    {if(!su[i])
        {primer[sum++]=i;
            for(int j=2*i;j<=n;j+=i)
                su[j]=true;
        }
    }
    cout<

#includeusing namespace std;
#define int long long
const int N=1e3+5;
int dp[N][N],a[N][N];
signed main(){int n,d,mxt=0,maxn=0;
    cin>>d>>n;
    for(int i=1;i<=n;i++)
    {int x,t;
        cin>>x>>t;;
        a[t][x]++;
        mxt=max(mxt,t);
    }
    for(int i=mxt;i>=0;i--)
    {for(int j=1;j<=d;j++)
        {dp[i][j]=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1])+a[i][j];
        }
    }
    for(int j=1;j<=d;j++)//开始时小明的位置不确定，所以要比较小明在不同位置开始能接到的馅饼数
        maxn=max(maxn,dp[0][j]);
    cout<

dp[i][j]=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1])+a[i][j];

#includeusing namespace std;
#define int long long
void retree(string a,string b)
{int t = b.find(a[0]);//找根节点在b中的位置
	if (t != 0)//如果这个根节点还有叶节点
		retree(a.substr(1, t), b.substr(0, t));//对左叶的树进行操作
	if (b.size() >t + 1)//如果这个根节点有右子叶
		retree(a.substr(t + 1), b.substr(t + 1));
	cout<< a[0];//输出节点代表的信息
    return ;
}
signed main()
{int n;
    cin>>n;
    string q,z;
    cin>>q>>z;
    retree(q,z);
    cout<<'\n';
    return 0;
}

#include#includeusing namespace std;
#define int long long
struct TNode{char data;
    TNode *lchild,*rchild;
};
typedef TNode *BinTree;
BinTree pre_mid_build(char* pre, char* mid, int num){if(pre==NULL||mid==NULL||num<=0)
        return NULL;

    BinTree root=new TNode;
    root->data=pre[0];
    root->lchild=NULL;root->rchild=NULL;

    if(num==1)  return root;

    int left_num=0;//左子树结点总数
    char* middle_root=mid;

    while(*middle_root!=pre[0]&&middle_root<=(mid+num-1)){middle_root++;
        left_num++;
    }

    if(left_num>0)//创建左子树
        root->lchild=pre_mid_build(pre+1,mid,left_num);
    if(num-left_num-1>0)//创建右子树
        root->rchild=pre_mid_build(pre+left_num+1,mid+left_num+1,num-left_num-1);
    return root;
}

void PostorderTraversal(BinTree T){//后序遍历
    if(T) {PostorderTraversal(T->lchild);
        PostorderTraversal(T->rchild);
        cout<< T->data;
    }
    return ;
}
void DestroyBiTree(BinTree &T){//销毁二叉树
    if(T) {DestroyBiTree(T->lchild);
        DestroyBiTree(T->rchild);
        delete T;
        T = nullptr;
    }
    return ;
}
signed main(){int n;
    cin>>n;
    char pre[n+5];
    char mid[n+5];
    cin>>pre>>mid;
    BinTree root=pre_mid_build(pre, mid, n);
    PostorderTraversal(root);
    DestroyBiTree(root);
    cout<<'\n';
    return 0;
}

#includeusing namespace std;
#define int long long
int a[1000005],b[1000005],c[1000005];
bool cmp(int a,int b)
{return aint n,m,k=0;
    cin>>n>>m;
    //a表示信任的人数，b表示被信任的人数
    while(m--)
    {int x,y;
        cin>>x>>y;
        a[x]++;
        b[y]++;
    }
    for(int i=1;i<=n;i++)
    {if(a[i]==0||b[i]==n)
            c[k++]=i;
    }
    cout<

#includeusing namespace std;
#define int long long
set>s;//存n个人之间的关系，由于set中没有重复数据的特性，将重复数据过滤
setans;//把内奸的存起来，set中能自动排序
signed main()
{int n,m,q,sum=0;
    cin>>n>>m;
    vectorsum1(n+5,0);//sum1[i]表示i信任多少人
    vectorsum2(n+5,0);//sum2[i]表示i被多少人信任
    
    while(m--)
    {int a,b;
        cin>>a>>b;
        s.insert({a,b});//因为有重复数据，所以不能在输入的时候直接计数
    }
    
     set>::iterator it1;//迭代器，用于遍历set
     for(it1=s.begin();it1!=s.end();it1++)
     {sum1[it1->first]++;
        sum2[it1->second]++;
     }
       
     for(int i=1;i<=n;i++)
        if(sum1[i]==0&&sum2[i]==n-1)//满足题目给出的内奸条件的，存入ans
        {ans.insert(i);
            sum++;
        }
        
    cout<::iterator  it;
    for(it=ans.begin();it!=ans.end();it++)
        cout<<*it<<'\n';
    return 0;
}

#includeusing namespace std;
#define int long long
const int N=1e6+5;
vectortu[N];
map,int>c;
signed main()
{int n,m;
    cin>>n>>m;
    while(m--)
    {int u,v;
        cin>>u>>v;
        tu[u].push_back(v);
        tu[v].push_back(u);
        c[{u,v}]++;
    }
    int k;
    cin>>k;
    while(k--)
    {int x,y;
        cin>>x>>y;
        if(x==y)
            cout<x,y}]-c[{y,x}]<<"\n";//c[{x,y}]和c[{y,x}]在图上表示相同的边，且都存在重复的情况
    }
    return 0;
}

#includeusing namespace std;
#define int long long

signed main()
{int t;
    cin>>t;
    while(t--)
    {priority_queue,greater>q;//优先队列，top是最小值
        int n,sum=0,sum1=0;
        cin>>n;
        
        while(n--)
        {int x;
            cin>>x;
            q.push(x);
        }
        
        while(q.size()>1)//只剩一堆石子的时候结束循环
        {sum=q.top();
            q.pop();
            sum=sum+q.top();
            q.pop();
            q.push(sum);//把石子合并后入队，并排序
            sum1+=sum;
        }
        
        cout<

#includeusing namespace std;
#define int long long
int n,i,j=1;
deque>q;
vectora(1e5+1,0);
signed main() 
{cin>>n;
    deque>::iterator it=q.end();
    while(n--)
    {++i;
        int d;
        cin>>d;
        it=q.end()-1;
        while(!q.empty()&&d>it->second)//要先判断队列是否为空
        {q.pop_back();
            it=q.end()-1;
        }
        q.push_back({i,d});
        
        if(q.size()>=3)//队列中人数大于2时，第一个人吃饭
        {it=q.begin();
            a[j++]=it->first;//把第一个人的序号存到a中
            q.pop_front();//把第一个元素弹出
        }
    }
    
    cout<

for(int i=1;i

#includeusing namespace std;
#define int long long
signed main()
{int t;
    cin>>t;
    while(t--)
    {int n,h,flag=1;
        cin>>n>>h;
        int a[n+1];
        
        for(int i=0;i>a[i];
        while(flag)
        {flag=0;
            for(int j=n-1;j>0;j--)
            {if(a[j]+a[j-1]<=h&&a[j]flag++;
                    swap(a[j],a[j-1]);
                }
            }
        }
        for(int i=0;i