【LittleXi】阿里国际9.9笔试题解

前言：AK,第三题对于普通的同学有点难度

第一题：

题意：

给n（n<500)个数字的lowbit和highbit ，求这n个数字的最大可能异或和

题解：

开一个长度为500的数组，然后[l+1,r-1] 的数字可以任取了，其它记录一下有多少个1就行了

最后高精度转化为十进制输出

第二题：

题意：

给一个长度为n的数组(n<1e5) , 每次可以选择i，j 并且a[i] = a[j] , 删除a[i] , a[j],记操作序列为ij，操作m次删除之后，输出最小化字典序的操作序列

牛牛有手上有几个数字，第i个数字为ai(1si≤n)但值相同的数字可以相连并消去。牛牛想两个位置不同，要消去尽可能多的数字，并使得消去数字的方案字典顺、假设你一共进行了m次操作，消去了2m个数字。第i次换作，你可以选择两个未选择的下标i,j(1≤i,j≤n)，满足ai = aj，将这两个数字消去。如果把每次操作选择的下标按心序写成一行，会产生一个序列b(1<i<2m)你需要输出在能消去最多数字的方案中，字典顺序最小的序列 b。

题解：

把所有相同类型的取出来，然后因为要字典序最小的，所以只能挨着匹配，最后排序一下

#include<vector>
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

void solve(){
    int n;cin>>n;
    vector<int> a(n);
    for(int&x:a) cin>>x,x+=n;
    vector<vector<int>> adj(2*n+1);
    for(int i =0;i<n;i++){
        adj[a[i]].push_back(i);
    }
    vector<pair<int,int>> ans;
    for(int i = 0;i<=2*n;i++){
        for(int j =0;j+1<adj[i].size();j+=2){
            ans.push_back({adj[i][j] , adj[i][j+1]});
        }
    }
    sort(ans.begin(),ans.end());
    for(auto p:ans){
        cout<<p.first + 1<<" "<<p.second + 1<<" ";
    }
}

int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
}

第三题：

题意：

你有两种颜色的石头，几个黑色和 m 个白色，有无限多个物品，对于第i个物品，需要i个黑色或者i个白色石头，假设你最多可以买x个物品，那么买必个物品，有多少方案? 如果在某一次使用的石头是不一样的，那么就是不同方案。

题解：

首先根据1+2+3..+x <= n + m , 算出x是什么，然后你可以认为我们物品大小是1,2,3...x , 开一个长度为n+1的背包，利用背包dp计数一下获取某个大小的总物品的方案数量，然后最后统计满足两个n，m的答案数量有多少就行了。

#include<vector>
#include<iostream>
//T3
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
void solve(){
    ll n , m;cin>>n>>m;
    ll x = 0 ,sm = 0;
    while(1){
        sm += x + 1;
        if(sm > n + m) break;
        x ++;
    }
    vector<ll> dp(n+1,0);
    dp[0] = 1;
    for(ll i = 1;i<=x;i++){
        for(ll j = n;j>=0;j--){
            if(i+j > n) continue;
            dp[i+j] = (dp[i +j] + dp[j]) %mod; 
        }
    }
    sm = (1 + x ) * x / 2;
    ll ans = 0;
    for(ll i = 0;i<=n;i++){
        if(sm - i <= m){
            ans = (ans + dp[i])%mod;
        }
    }
    cout<<ans;
}

signed main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
}

❤关注LittleXi , 谢谢喵， ACM金牌，更新更多题解❤
**********
alt