题型

• 30个选择题，大概涉及到操作系统、计算机网络、安卓、数据库、数据结构、组合数/方案数、Java基础。30分。
• 问答题，安卓的场景题，30分。
• 编程题，3道，20*3=60分

编程题1

题意：
给出一个字符串，长度为1e6，每次操作可以删除或增加一个字符，求最小的操作数使得这个字符串里出现的字母个数都相同。保证字符串长度是出现的字母个数的倍数。
思路：
大概题意读出来有点假，可能是最后要求的字符串长度是不变？

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll cnt[26];

int main(){
    string s;
        cin>>s;
        ll n=s.size();
        memset(cnt,0,sizeof cnt);
        for(int i=0;i<n;i++){
            int t=s[i]-'a';
            cnt[t]++;
        }
        ll ans=0;
        ///长度只能为n？
        ll m=0;
        for(int i=0;i<26;i++){
            if(cnt[i]!=0){
                m++;
            }
        }
        ll tmp=n/m;
        for(int i=0;i<26;i++){
            if(cnt[i]!=0){
                ans+=abs(tmp-cnt[i]);
            }
        }
        cout<<ans<<endl;

    return 0;
}

编程题2

多重背包的模板题，就是约束了每种物品最多用两次。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;

int weight[maxn],value[maxn];
int dp[maxn];

int main(){
    int n,w;cin>>n>>w;
    for(int i=1;i<=n;i++) cin>>weight[i]>>value[i];
    for(int i=1;i<=n;i++){
        for(int j=w;j>=weight[i];j--){
            for(int k=1;k<=2&&j-weight[i]*k>=0;k++){
                dp[j]=max(dp[j],dp[j-weight[i]*k]+value[i]*k);
            }
        }
    }
    int ans=0;
    for(int i=0;i<=w;i++) ans=max(ans,dp[i]);
    cout<<ans<<endl;
    return 0;
}

编程题3

昨天学长刚出的题。
给出长度为1000的一个数删除k位使得剩下数值最大。
赛时写了一个O(nk)的写法。
贪心的考虑，数值最大就是高位的数越大越好。
那考虑什么时候才会删除，比如564，要删除一个的话，是删除5比较优的，因为5<6，所以6在前面更优。
然后每次都遍历一遍，如果当前位的数小于下一位的数，就删除当前位的数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
int vis[maxn];

int main(){
    string s;cin>>s;
    int k=s[0]-'0',n=s.size();
    while(k--){
        int i=0;
        for(i=0;i<n-1;i++){
            if( (s[i]-'0') < (s[i+1]-'0') ){
                break;
            }
        }
        for(int j=i;j<n-1;j++) s[j]=s[j+1];
        n--;
    }
    for(int i=0;i<n;i++)
        cout<<s[i];
    return 0;
}

优化：
大体贪心思路跟朴素版的一样，如果k不为0，就将当前位的数跟之前的数比较，如果之前保存的数位小，就说明用当前数更优，也就是删除之前保存的数位，这样直到k为0.维护出来一个单调非递减的序列。
如果最后k还不为0，就从后面开始删。
时间复杂度O(n)

#include <bits/stdc++.h>

using namespace std;

#define ll long long 

string str;

int main(){

    int k;

    cin>>str>>k;

    ll len=str.size();

    ll l=1,r=0;

    char c[len];

    c[0]=str[0];

    int flag=0;

    while(l<len){

        if(k<=0) flag=1;

        if(flag) {

            c[++r]=str[l++];

        }

        else {            

            while(r>=0&&c[r]<str[l]){///

                r--;k--;

                if(k<=0){

                    flag=1;break;

                }

            }

            c[++r]=str[l++];

        }

    }

    for(int i=0;i<=r-k;i++){

        printf("%c",c[i]);

    }

    return 0;

}