2019暑期多校联赛（7/27）题解

420 阅读 5 评论 0 点赞

各位同学，昨日多校联赛已经结束，题目也重新放到题库中2103~2112，有兴趣的同学可以重新提交训练

###  1.【狂猎来袭】
法一：输入一个整数n,然后进行highbit(n)与lowbit(n)的操作，其中highbit(n)可以套用公式pow(2,i) <= n <pow(2,i+1) 的方法确定highbit的位置，lowbit可以直接通过操作 n&(-n) 的方法取得。
法二：数据比较小的情况下，直接进行左右移位，记录移位的次数以确定二进制的位置，记录后构造出答案即可。

参考代码：
```cpp
#include<iostream>
using namespace std;

int k,t,ans;

inline int pow(int a,int b){
    int ans=1,base=a;
    while(b){
        if(b&1) ans*=base;
        base*=base;
        b>>=1; 
    }
    return ans;
}

int highbit(int n){
    int i=0;
    while(!(pow(2,i) <= n && n < pow(2,i+1))){
        i++;
    }
    return pow(2,i);
}

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

int main(){
    cin>>t;
    while(t--){
        cin>>k;
        if(k<0) k = -k;
        ans = highbit(k) | lowbit(k);
        cout<< ans <<endl;
    }
    return 0;
}

```
### 2.【施放魔法】
简单的卷积核矩阵运算，本题是属于简化版本的运算方法，具体方式可以参照此图讲解。

![](/image_editor_upload/20190728090605_22098.png)（原矩阵 h）
  ![](/image_editor_upload/20190728090619_54378.png)（卷积核 A）
 ![](/image_editor_upload/20190728090637_99864.png) 将卷积核h的中心对准x的第一个元素，然后对应元素相乘后相加，没有元素的地方补0。这样结果Y中的第一个元素值Y11=1*0+2*0+1*0+0*0+0*1+0*2+-1*0+-2*5+-1*6=-16，每个元素都像这样计算出来就可以得到一个输出矩阵，就是卷积结果
 ![](/image_editor_upload/20190728090711_25919.png) 这就是结果。
```cpp
#include <iostream>
using namespace std;

const int maxn = 105;
int n,m;
int org[maxn][maxn]={0};
int ker[3][3]={0};
int ans[maxn][maxn]={0};

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>org[i][j];
        }
    }

for(int i=0;i<3;i++){
        cin>>ker[i][0]>>ker[i][1]>>ker[i][2];
    }

for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int tmp=0;
            for(int a=0;a<3;a++){
                for(int b=0;b<3;b++){
                    tmp += (ker[a][b] * org[i-1+a][j-1+b]);
                }
            }
            ans[i][j]=tmp;
        }
    }

for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<ans[i][j]<<' ';
        }
        cout<<endl;
    }
    
    return 0;
}

```

### 3.【狂猎褪去】
签到题，直接一层遍历找以三个数字为一组挨个访问，记录下每组中a[i-1],a[i],a[i+1]这三个数字之中的第二大的情况，每有一个这个情况就记录一次。

```cpp
#include<iostream>
#include<cstring>
using namespace std;

const int maxn=100005;
int n,ans=0;
int arr[maxn]={0};

int main(){
    while(cin>>n){
        memset(arr,0,sizeof(arr));
        ans=0;
        for(int i=0;i<n;i++)    cin>>arr[i];
        for(int i=1;i<n-1;i++){
            if( (arr[i]>arr[i-1]&&arr[i]<arr[i+1]) || (arr[i]<arr[i-1]&&arr[i]>arr[i+1]) ){
                ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

```

### 4.【误落迷宫】
DFS搜索，还顺带了一丢丢的图论知识，记住需要使用一个数组记忆走过的路线不要重复，本题的核心不在于找得到环路，而是在于直接沿着路线走下去可以走到尽头没有。
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int maxn=205;
int edge[maxn][maxn],vis[maxn],flag=1,n;

void dfs(int x){
    for(int i=1;i<=n;i++){
        if(vis[i] && edge[x][i]){
            flag=0;
            return;
        }
        if(edge[x][i]){
            vis[i]=1;
            dfs(i);
            vis[i]=0;
        }
    }
}
int main(){
    while(~scanf("%d",&n)){
        memset(edge,0,sizeof(edge));
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            if(x!=y)
                edge[x][y]=1;
        }
        int t;
        scanf("%d",&t);
        vis[t]=1;
        flag=1;
        dfs(t);
        if(flag)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

```

### 5.【误落迷宫2】
BFS搜索的加难版本，重点在于找到中间的【三夫人】这个中间点，再只存储下已经移动的步数再清空搜索状态重新开始搜索终点，因此，本题目亦可以视为由【开始点】BFS搜索找到【三夫人】，再由【三夫人】BFS搜索找到【终点】，这样的两个过程。
```cpp
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;

const int maxn=105;
char mp[maxn][maxn]={0};
int vis[maxn][maxn]={0};
const int dir[4][2]= {0,1,0,-1,1,0,-1,0};   //四个方向 右，左，下，上
int t,n,m;
int out_x,out_y;    //出口位置
int tre_x,tre_y;    //三夫人位置
int flag=false;     //判断是否已经找到三夫人了

struct state {
    int x,y;
    int step;
};

void clear(queue<state>& q){    //queue没有clear操作，可以自定义一个clear，其中最理想的方式就是利用swap函数
    queue<state> empty;
    swap(empty,q);
}

bool check(state s) {
    if(!vis[s.x][s.y]&&mp[s.x][s.y]!='1'&&s.x<n&&s.y<m&&s.x>=0&&s.y>=0) {
        return true;
    }
    return false;
}

int bfs(state st) {
    queue<state> q;
    state now,next;
    st.step=0;
    q.push(st);
    vis[st.x][st.y]=1;
    while(!q.empty()) {
        now=q.front();
        if(now.x==tre_x&&now.y==tre_y){
            //cout<<now.x<<"!!!!!!!!!!!!!!!"<<now.y<<"-------"<<now.step<<endl;
            clear(q);
            memset(vis,0,sizeof(vis));
            vis[now.x][now.y]=1;
            q.push(now);
            flag=true;
        }
        if(flag && (now.x==out_x&&now.y==out_y)){
            return now.step;
        }

for(int i=0; i<4; i++) {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            next.step=now.step+1;
            if(check(next)) {
                //cout<<next.x<<"--"<<next.y<<"--"<<next.step<<endl;
                q.push(next);
                vis[next.x][next.y]=1;
            }
        }
        q.pop();
    }
    return -1; 
}

int main() {
    state st;

cin>>n>>m;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin>>mp[i][j];
            if(mp[i][j]=='S') { //起始点
                st.x=i;
                st.y=j;
                st.step=0;
            }
            if(mp[i][j]=='E') { //终点
                out_x=i,out_y=j;
            }
            if(mp[i][j]=='T') { //三夫人位置
                tre_x=i,tre_y=j;
            }
            if(mp[i][j]=='1'){  //墙壁
                vis[i][j]=1;
            }
        }
    }
    cout<<bfs(st)<<endl;
    return 0;
}

```

### 6.【抢夺资源】
标准的巴什博弈问题，在 n%(m+1)的清空下，杰洛特必应
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int main(){
    int n, m;
    while(cin >> n >> m)
        if(n % (m + 1))
            cout << "Gerlot" << endl;
        else
            cout << "Wildhunte" << endl;
    return 0;
}

```
### 7.【增添战力】
贪心算法，先对每一个豪杰的战斗力进行排序，只选择最优秀的的交给对人才需求较少的城池，次优的交给对人才需求多的城池，最后再利用算术平均值的公式将两个城池的平均值之和输出即可。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5+7;
int n,n1,n2,nn1,nn2;
double a[maxn];
int main()
{
    scanf("%d%d%d",&n,&n1,&n2);
    if(n1>n2)swap(n1,n2);
    nn1=n1,nn2=n2;
    for(int i=0;i<n;i++)
        scanf("%lf",&a[i]);
    sort(a,a+n);
    reverse(a,a+n);
    double sum1=0,sum2=0;
    for(int i=0;i<n;i++){
        if(n1){
            sum1+=a[i];
            n1--;
        }else if(n2){
            sum2+=a[i];
            n2--;
        }
    }
    double ans = (sum1/nn1)+(sum2/nn2);
    printf("%.6f\n",ans);
}

```
### 8.【虚张声势】
一个简单的字符串操作，注意只考虑英文字母，不考虑符号与空格等，因此情况 abc! 和 cb a? 这样的话都属于正确（不会被识破），这里还要注意不要使用cin>>和scanf输入字符串，可能会存在空格所以要用gets这类的方法。
算法的核心在于将ASCII码换做数组的下标，每次遇到一个字母就进行一次自增（计数），以达到计数的效果（不要使用排序可能会炸）。
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int maxn=1005;
int t;
char str1[maxn];
char str2[maxn];
int arr1[256];
int arr2[256];
bool flag;

int main(){
    scanf("%d",&t);
    getchar();
    while(t--){
        flag=true;
        memset(str1,0,sizeof(str1));
        memset(str2,0,sizeof(str2));
        memset(arr1,0,sizeof(arr1));
        memset(arr2,0,sizeof(arr2));

//gets(str1);
        //gets(str2);
        fgets(str1,sizeof(str1),stdin);
        fgets(str2,sizeof(str2),stdin);

for(int i=0;i<strlen(str1);i++){
            if((str1[i]>='a'&&str1[i]<='z')||(str1[i]>='A'&&str1[i]<='Z')){
                arr1[str1[i]]++;
            }
        }
        for(int i=0;i<strlen(str2);i++){
            if((str2[i]>='a'&&str2[i]<='z')||(str2[i]>='A'&&str2[i]<='Z')){
                arr2[str2[i]]++;
            }
        }
        for(int i=0;i<256;i++){
            if(arr1[i]!=arr2[i]){
                printf("No\n");
                flag=false;
                break;
            }
        }
        if(flag){
            printf("Yes\n");
        }
    }
    return 0;
}

```
### 9.【连环阵】
本题的题目描述样例中错了一个字，导致出错。
彻底的描述为：

题目名：
    连环阵
题目描述：
    杰洛特主动出击狂猎的老巢，然而在此之前，他遇到了一个女术士，杰洛特想要女术士助自己一臂之力，她却出了一个难题给杰洛特，只有答对了才能与他同行
    女术士给杰洛特一个四位数的素数，要求他说出这个四位数的数字的另外两个四位素数(从小到达输出)，要求：
    1.这个三个四位数组成等差数列
    2.这三组数字的构成相同(即每个四位数都是其他数字的一种排列)
输入：
    多组数据输入
    每次一个整数
输出：
    输出这三个数字，如果没有达成条件的三个数字，则输出"No"
样例输入：
4817
1232
样例输出：
1487 4817 8147
No

记得几个要求，第一求四位数的素数，第二这个四位数的素数还同时存在两个其他的素数，这三个素数购成等差数列，同时，这三个素数的购成是相同的，比如说 1487 4817 8147他们的购成均是由 ‘1’ ‘4’ ‘8’ ‘7’构成的。
我们首先要做的就是线性筛选出9999以内的素数，然后对这些素数以下标的方式存储在一个数组中，最后通过全排列的方法统计出输入数字的拆分与再组合数，接下来就是通过题目条件，构成等差数列，同时三个数又都是素数。
细心可以发现，满足这个要求的四位数并不多，只有两组，所以可以拆分成两份代码分别运行与提交
首先是找出符合要求的素数：
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10005;
const int tmp_max=25;   
// 4! < 25

int cnt[maxn]={0};
int pre[maxn]={0};
int dif[maxn]={0},dif_pos;

//O(n^4)=O(10000)
void select(int n){
    //取出位置和初始化
    memset(pre,0,sizeof(pre));
    memset(dif,0,sizeof(dif));
    int pos=0,dif_pos=0,tmp[tmp_max]={0};    
    int pre[4]={n%10,(n/10)%10,(n/100)%10,n/1000};
    sort(pre,pre+4);
    
    //全排列
    do{
        tmp[pos++]=pre[0]*1000+pre[1]*100+pre[2]*10+pre[3];  
    }while(next_permutation(pre,pre+4));

//求出差
    for(int i=0;i<pos;i++){
        if(tmp[i]-n>0 && cnt[tmp[i]]){
            dif[dif_pos++]=tmp[i]-n;
        }
    }

//利用差值进行运算
    for(int i=0;i<dif_pos;i++){
        for(int j=i+1;j<dif_pos;j++){
            if(2*dif[i]==dif[j] && cnt[n+dif[i]] && cnt[n+dif[j]]){
                cout<< n <<' '<< n+dif[i] <<' '<< n+dif[j] <<endl;
                return ;
            }
        }
    }
    
}

//线性筛素数
bool isprime(int n){
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)  return false;
    }
    return true;
}

int main(){
    for(int i=1000;i<=9999;i++) {
        if(isprime(i)){
            cnt[i]=1;
        }
    }

for(int i=1000;i<=3333;i++){
        if(cnt[i]){
            select(i);
        } 
    }
    //select(1487);
    return 0;
}

//答案有两种 
//『1487，4817，8147』
//『2969，6299，9629』
//四位数只有三元集因此简单一些

```

再提交代码：
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==1487||n==4817||n==8147){
            printf("1487 4817 8147\n");
        }else if(n==2969||n==6299||n==9629){
            printf("2969 6299 9629\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}

```

### 10.【决战拼接】
动态规划，状态转移为：dp[i] = min(dp[i] , dp[i-n[j]]+1)  n为杰洛特的手下战斗力。
需要注意的是dp的初始状态的赋值，不要遗漏。
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;

int getans(vector<int>& dajiang, int amount) {
    int* dp=new int[amount+1] ();
    for(int i=1;i<amount+1;i++)
        dp[i]=1000;
    dp[0]=0;
    for(int i=0;i<=amount;i++)  {
        for(int j=0;j<dajiang.size();j++)   {
            if(i-dajiang[j]>=0)
                if(dp[i]>dp[i-dajiang[j]]+1)
                    dp[i]=dp[i-dajiang[j]]+1;
        }   
    }
    if(dp[amount]>=1000)
        return -1;
    else
        return dp[amount];
}

int main(){
    int tmp,n;
    scanf("%d",&n);
    vector<int> input;
    for(int i=0;i<n;i++){
        scanf("%d",&tmp);
        input.push_back(tmp);
    }
    scanf("%d",&tmp);
    printf("%d",getans(input,tmp));
    return 0;
}

```

0.0分

3 人评分

本文分类：文章列表
浏览次数：420 次浏览
发布日期：2019-07-28 09:12:05
本文链接：https://blog.dotcpp.com/a/60951

上一篇 > 排序算法总结之-冒泡、选择、插入、希尔、归并排序（含C++代码实现）
下一篇 > 指针和引用的区别

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 5 条评论

: 验题君 5年前回复TA
@子夜葵 @lzyws739307453 感谢反馈，代码测试确实有问题，已经修复并全部重判

: 子夜葵 5年前回复TA
@子夜葵 @dotcpp_admin 这是我故意改的，这就证明你的代码只能过样例，其它的数据过不了

: 子夜葵 5年前回复TA
@子夜葵 @dotcpp_admin 这个是我的样例，如果按题上说的，正确答案应该是19

: 验题君 5年前回复TA
@子夜葵和样例数据不一样啊，你貌似打错了

: 子夜葵 5年前回复TA
误落迷宫2那一题是不是有问题那一题第一次找到目标，在第43行清除标记是不是也把墙给清除了，那第二次就畅通无阻了。 8 8 1S111111 10000001 11101101 1T000001 11111101 10011101 10100001 111E1111 应该是19，而你的却是13 上面这个样例就过不了

2019暑期多校联赛（7/27） 题解

求球的体积

用while循环，卡住终止点是更新后的a=0 ；不断用10求模，不断更新，循环输出

【编程入门】自定义函数处理最大公约数与最小公倍数

年龄与疾病

评论列表 共有 5 条评论

发表评论 取消回复

2019暑期多校联赛（7/27）题解

评论列表共有 5 条评论

发表评论取消回复