【2022阿里灵犀互娱】游戏测开笔试AC_Code

测开笔试，90分钟，3道编程题+八股，第二题输出格式模拟题，就不贴了

T1-进制转换

题意 

有一个数，可能是2～16进制的其中之一，算出所有可能的结果，并转成十进制后对1e9+7取模，答案从小到大排列，若存在相同的结果，只保留一个。

输入描述

一个数，表示得到的数字。保证不会出现 '0'~'9'， 'A'~'F' 以外的字符，输入数字长度不超过100000，且保证无前导零

输出描述

每行输出可能的结果

样例数据

输入
11

输出
3 4 5 6 7 8 9 10 11 12 （换行输出）

AC_Code

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
int main()
{
	string s;  cin>>s;
	int n=s.length();
    vector<int> a(n);
    for(int i=0; i<n; i++) {
        if(s[i]>='0' && s[i]<='9')  a[i]=s[i]-'0';
        else a[i]=s[i]-'A'+10;
    }
    vector<ll> ans;
    int ma = max(2,*max_element(a.begin(), a.end())+1);
    for(int i=ma; i<=16; i++) {
        ll val = 0;
        for(auto x: a) val = (val * i % mod + x) % mod;
        ans.push_back(val);
    }
    sort(ans.begin(),ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    for(auto x: ans)  cout<< x <<endl; 
	return 0;
}

T3-特殊字符串

题意

一个字符串仅包含小写字母，希望删除其中一个非空连续子串，使剩下的字符串至少有k种不同字母。求有多少种不同的删除方案。若删除的子串位置不同，则视为两种不同的方案。

输入描述

第一行输入正整数n和k，代表字符串长度以及最终字符串的字母种类最小值。
第二行一个长度为n的只包含小写字母的字符串s (保证至少k种字符) 1<=n<=200000，1<=k<=26

输出描述

输出删除子串的方案数

样例

输入
5 2
aabba
输出
9

AC_Code 

#include <bits/stdc++.h>
#define ll long long 
const int N = 2e5+10;
using namespace std;
char s[N];

int main()
{
	int n, k;	cin >> n >> k;
	scanf("%s",s+1);
	vector<int> cnt(26);
    for(int i=1; i<=n; i++) cnt[s[i]-'a']++;
    ll ans=0;
    int l=1, r=1, pre=0, suf=0;
    for(int i=0; i<26; i++) 
        if(cnt[i]) suf |= (1<<i);
    
    while(l<=n) {
        while(r<=n) {
            if( cnt[s[r]-'a']>1 && __builtin_popcount(pre | suf)>=k )  cnt[s[r++]-'a']--;
            else if( cnt[s[r]-'a']==1 &&  __builtin_popcount(pre | (suf ^ (1<<s[r]-'a')))>=k )  
                suf ^= (1 << s[r]-'a'), cnt[s[r++]-'a']--;
            else break;
        }
        ans += max(0, r-l);
        pre |= (1<<(s[l++]-'a'));
    }
    printf("%lld\n", ans);
	return 0;
}