【题解】牛客模考 · 大厂定制出题模拟笔试
A式计数法
难度：1星
知识点：模拟，字符串
题意：对于每个给定数字，使用A式计数法输出。
按照题意模拟即可。注意倒序处理。每隔A个字符输出一个'_'字符即可。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int t=in.nextInt();
for(int i=0;i<t;i++){
int a=in.nextInt();
String s=in.next(),out="";
int cnt=0;
for(int j=s.length()-1;j>=0;j--){
if(cnt>0&&cnt%a==0)out='_'+out;
cnt++;
out=s.charAt(j)+out;
}
System.out.println(out);
}
}
} 质数之手
难度2.5星
知识点：数论、枚举
题意：给定n，找到最小一个正整数是n的数位重排、且是素数。若不存在则输出0
思路： 考虑到n不超过1e6，所以只需要把所有素数筛出来，然后枚举即可。
需要考虑以下限制条件：
-
必须是素数（可以用筛法解决，O(1)判断）
- 必须是n的重排（可以利用桶统计每个数的次数，O(10)判断）
import java.util.*;
public class Main{
static boolean jud(int a,int b){ //判断是否构成重排
int[] A=new int[10],B=new int[10];
while(a>0){
A[a%10]++;
a/=10;
}
while(b>0){
B[b%10]++;
b/=10;
}
for(int i=0;i<10;i++)if(A[i]!=B[i])return false;
return true;
}
static boolean[] pr;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n=in.nextInt();
pr = new boolean[1000010];
for(int i=1;i<=1e6;i++)pr[i]=true;
pr[1]=false;
for(int i=2;i<=1e6;i++){
if(pr[i]){
for(int j=i*2;j<=1e6;j+=i){
pr[j]=false;
}
}
}
ArrayList<Integer> out = new ArrayList<Integer>();
for(int i=1;i<=1e6;i++){
if(jud(n,i)&&pr[i])out.add(i);
}
System.out.println(out.size());
if(out.size()>0){
System.out.println(out.get(0));
}
}
} 合成二叉树
知识点：贪心、二叉树
难度：3.5星。
思路：
使用贪心策略，优先合并两个节点数最小的树一定是最优解。
因此按题意模拟，把所有树放入优先队列，每次优先选择两个节点数最小的树进行合并即可。合并后再加入优先队列。
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
map<TreeNode*,int>siz;
map<TreeNode*,int>id;
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param T TreeNode类vector
* @return TreeNode类
*/
int getSiz(TreeNode *T)
{
if(T==nullptr)
return 0;
return getSiz(T->left)+getSiz(T->right)+1;
}
TreeNode* mergeTree(vector<TreeNode*>& T) {
// write code here
auto cmp=[](TreeNode*& a, TreeNode*& b)
{
if(siz[a]==siz[b])
return id[a]>id[b];
else
return siz[a]>siz[b];
};
priority_queue<TreeNode*,vector<TreeNode*>,decltype(cmp)>q(cmp);
int n=T.size();
for(int i=0;i<n;i++)
{
siz[T[i]]=getSiz(T[i]);
id[T[i]]=i;
q.push(T[i]);
}
while(q.size()!=1)
{
TreeNode *a=q.top();
q.pop();
TreeNode *b=q.top();
q.pop();
if(siz[a]!=siz[b])
{
TreeNode *c=new TreeNode(1);
if(siz[a]>siz[b])
swap(a,b);
c->left=a;
c->right=b;
siz[c]=siz[a]+siz[b]+1;
id[c]=n++;
q.push(c);
}
else
{
TreeNode *c=new TreeNode(1);
c->left=a;
c->right=b;
siz[c]=siz[a]+siz[b]+1;
id[c]=n++;
q.push(c);
}
}
return q.top();
}
}; 插班生
难度：5星
思路：
对于每个节点，我们可以通过预处理的方式达成 O(1) 的查询。
预处理方式如下：我们先只考虑插班生右方的学生。
如果第一个位置是插班生，那么右边的依次是 -(n-1) -(n-2),...,-2,-1
当插班生右移时，插班生右边的依次是 -(n-2),...,-2,-1
我们可以发现，当一个点会减成负的时，如果再将插班生右移，我们会发现剩下的一定都是负的。
因此可以把每个点的“会减成负的”的区间求出来，利用差分、前缀和达成区间的合并。这样就能批量处理，达成O(1)查询了。
对于插班生左边的学生，处理方式同右边。
#include <iostream>
using namespace std;
const int maxn = 1e5 + 5;
#define ll long long
#define int long long
ll pre[maxn], suf[maxn], pre2[maxn], suf2[maxn], sum[maxn], a[maxn];
signed main(){
int n;
cin >> n;
ll ans = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
ans += a[i];
}
for(int i = 1; i <= n; i++){
if(a[i] >= n - 1) continue;
ll l = i - (n - a[i] - 1), d = 0;
if(l < 1){
d = - l + 1;
l = 1;
}
pre[l]++;
pre[i]--;
pre2[l] += d;
pre2[i] -= d + (i - l);
}
for(int i = n; i >= 1; i--){
if(a[i] >= n - 1) continue;
ll r = i + (n - a[i] - 1), d = 0;
if(r > n){
d = r - n;
r = n;
}
suf[r]++;
suf[i]--;
suf2[r] += d;
suf2[i] -= d + (r - i);
}
for(int i = 1; i <= n; i++){
pre[i] = pre[i-1] + pre[i];
pre2[i] += pre[i] + pre2[i-1];
}
for(int i = n; i >= 1; i--){
suf[i] = suf[i+1] + suf[i];
suf2[i] += suf[i] + suf2[i+1];
}
// for(int i = 1; i <= n; i++){
// cout << suf2[i] << " ";
// }
for(int i = 1; i <= n; i++){
cout << ans - a[i] - (i-1) * i / 2 - (n-i) * (n-i+1) / 2 + suf2[i] + pre2[i] - 2 * (n - i) * (i - 1) << " ";
}
} 
