学校选拔赛练习题

· · 个人记录

ps:果然现场赛脑子在演我现赛后补题顺利到我都怀疑脑子在比赛的时候在演我

第一题 经典递归题

观察题目能发现每次2的次幂达到一定次数后会和成一个新的2次幂如案例1315 = 2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）,所以考虑使用递归，具体实现如下，要注意的是递归每层可能会多输出+，所以需要特判一下(描述有点不清楚(主要很难表达)直接看代码吧)

ll n;
void dfs(ll x,ll ff){
    // cout << x << endl;
    if(ff && x > 0) cout << "+";
    if(x <= 4){
        if(x == 1)cout << "2(0)";
        else if(x == 2) cout << "2";
        else if(x == 3) cout << "2+2(0)";
        else if(x == 4) cout << "2(2)";
        return ;
    }
    ll ci = 0, sm = 1;
    while(sm * 2 <= x){
        sm *= 2;
        ci ++;
    }
    cout <<"2(";
    dfs(ci, 0);
    cout <<")";
    dfs(x - poww((ll)2, ci),1);
}
int main(){
    cin >> n;
    dfs(n,0);
    return 0;
}

第二题 递归输出序列

这题需要注意的是题目输出要求(比赛波动速读裂开)，他的输出是有优先级的，所以记录一下每次得到的序列位置在排序一遍即可,本题数据有点弱不排序也可以90

ll n, k;
ll a[30], ans[30], vv[30];
ll as = 0;
vector<ll> v[N];
ll tot = 0;
ll pp[N][30];
ll ext[N];
void bfs(ll id, ll sum, ll cnt){ 
    if(sum == k && cnt > 1){
        tot ++;
        for(ll i = 1; i < cnt; i ++){
            v[tot].push_back(ans[i]);
            pp[tot][vv[i]] = 1;
        } 
        ext[tot] = tot; 
        as ++;
    }
    for(ll i = id; i <= n; i ++){
        ans[cnt] = a[i];
        vv[cnt] = i;
        bfs(i + 1, sum + a[i], cnt + 1);
    }
}
ll cmp (ll a, ll b){
    for(ll i = n; i >= 1; i --){
        if(pp[a][i] == pp[b][i]) continue;
        return pp[a][i] < pp[b][i];
    }
    return 0;
}
int main(){
    cin >> n;
    FOR(i, 1, n){
        cin >> a[i];
    }
    cin >> k;
    bfs(1,0,1);
    sort(ext + 1, ext + 1 + tot, cmp);
//  for(ll i = tot ; i >= 1 ; i --){
//      for(ll j = 0; j < v[i].size(); j ++) cout << v[i][j] <<' '; cout << endl;
//  }
    for(ll i = 1; i <= tot; i ++){
        for(ll j = 0; j < v[ext[i]].size(); j ++) cout << v[ext[i]][j] << ' ';
        cout << endl;
    }
    cout << as << endl;
    return 0;
}

/*
3
0 -1 0
-1

5
1 2 3 4 5 
10

6
1 2 3 4 5 3 
10

*/

第三题 语文阅读理解

这题主要是题目读的有点问题实际上是个傻逼题，题目意思是找到1 - n 孤独生成元，这个孤独生成元是值一个生成元递增序列的第一个值如 n = 1 ,d(n) = 2,1无法由其他数字生成出来所以它是孤独的

ll vis[N];
int main(){
    ll n;
    cin>>n;
    for(ll i = 1; i <= n ; i++){
        if(vis[i]) continue;
        ll st = i;
        while(st <= n){
            ll ff = st , sm = 0;
            while(ff){
                sm += ff % 10;
                ff /= 10;
            }
            st += sm;
            vis[st] = 1;
        }
        cout << i << endl;

    }   
    return 0;
}

第四题 经典bfs字典序最小

题目意思是找到从(1,1) 到 (n,m)中最短路且所选择的路段字典序最小 首先我们bfs先从(n,m)找到(1,1)记录该路径上每一位的前缀确定下从(1,1)到(n,m)所能到达的点，然后再次bfs从(1,1)到(n,m)找当前点到下一个点的差是否为1，如果为1说明该路径是可以走的，然后吧所有走到终点的字符路径进行排序取最小的一个即可

ll n, m;
char mp[1000][1000];

// D R U L
ll dfn[4][2] = {{1, 0},{0, 1}, {-1, 0}, {0, -1}};
string cs[4] = {"D", "R", "U", "L"};
struct Node{
    ll x, y;
    string ans;
};
ll dis[1000][1000];
void bfs(ll x, ll y){
    queue<pair<ll,ll>> q;
    q.push({x, y});
    dis[x][y] = 1;
    while(q.size()){
        auto nw = q.front();q.pop();
        for(ll i = 0 ; i < 4; i ++){
            ll xs = nw.first + dfn[i][0], ys = nw.second + dfn[i][1];
            if(xs >= 1 && xs <= n && ys >= 1 && ys <= m && !dis[xs][ys] && mp[xs][ys] == '0'){
                dis[xs][ys] = dis[nw.first][nw.second] + 1;
                q.push({xs, ys});
            }

        }
    }
    // for(ll i = 1; i <= n; i ++){
    //     for(ll j = 1; j <= m; j ++)cout << dis[i][j] <<' ';cout << endl;
    // }
}
ll vis[1000][1000];
vector<string> vvv;
void bfs1(ll x, ll y){
    queue<Node> q;
    q.push({x, y, ""});
    vis[x][y] = 1;
    while(q.size()){
        Node it = q.front(); q.pop();
        if(it.x == n && it.y == m){
            vvv.push_back(it.ans);
            continue;
        }
        for(ll i = 0; i < 4; i ++){
            ll xs = it.x + dfn[i][0], ys = it.y + dfn[i][1];
            ll tt =abs(dis[it.x][it.y] - dis[xs][ys]);
            if(xs >= 1 && xs <= n && ys >= 1 && ys <= m && !vis[xs][ys] && tt == 1){
                vis[xs][ys] = 1;
                // cout << xs << ' ' << ys << endl;
                q.push({xs, ys, it.ans + cs[i]});
            }
        }
    }
    sort(vvv.begin(), vvv.end());
    cout << vvv[0].size() <<endl;
    cout << vvv[0] << endl;

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

    bfs(n, m);
    bfs1(1,1);
    return 0;
}

第五题经典简单动态规划题

给你一个三角形数组要求从下到上找到总值最大的值是多少 我们考虑dp[i][j]表示当前在第(i,j)个点时的最大值是多少因为到达该点是从左下或右下到来的所以每次需要判断下路径最大所以公式为

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

ll n;
ll mp[110][110];
ll dp[110][110];
int main(){
    cin >> n;
    for(ll i = 1; i <= n; i ++){
        for(ll j = 1; j <=i ;j ++){
            cin >> mp[i][j];
        }
    }
    for(ll i = n - 1;i >= 1; i --){
        for(ll j = 1; j<= i; j ++){
            mp[i][j] += max(mp[i + 1][j] , mp[i + 1][j + 1]);
        }
    }
    cout <<mp[1][1] << endl;

    return 0;
}

第六题 傻逼题(比赛脑抽补题秒解绝了感觉脑子在演我)

只需要暴力判断每个芯片是否合法即可

ll mp[30][30];
ll n;
ll slove(ll id){

    for(ll i = 1; i <= n; i ++){
        if(i == id) continue;
        if(!mp[id][i])continue;
        ll ff = 1;
        for(ll j = 1; j <=n ; j ++){
            if(i == j  ) continue;
            if(mp[i][j] != mp[id][j]){
                ff = 0;
                break;
            }
        }
        if(ff) return 1;
    }
    return 0;
}
int main(){
    cin >> n;
    for(ll i = 1; i <= n ; i ++){
        for(ll j = 1; j <= n; j ++){
            cin >> mp[i][j];
        }
    }
    for(ll i = 1; i <= n; i ++){
        ll fase = slove(i);

        if(fase){
            for(ll j = 1; j <= n ; j ++){
                if(mp[i][j]) cout << j << ' ';
            }
            break;
        }
    }

    return 0;
}

第七题 暴力题

暴力求解即可

ll ans[N];
int main(){
    ll n, m;
    RLL2(n, m);
    for(ll i = 0; i <= 1000; i ++){
        for(ll j = 0;j <= 1000; j ++){
            ll sum = i * n + j * m;
            ans[sum] = 1; 
        }
    }
    ll mx = 0 ;
    for(ll i = 0; i < n * m + 10; i ++){
        if(!ans[i]) {
            mx = i;
        }
    }
    cout << mx << endl;

    return 0;