A题
题意：给你 n 个数 , 你需要改变这些数使得这 n 个数的值相等 , 并且要求改变后所有数的和需大于等于原来的所有数字的和 , 然后输出满足题意且改变后最小的数值。
AC代码：
#include<bits/stdc++.h> using namespace std;
#define int long long
signed main(){
int _;
cin>>_;
while(_--){
int n;
cin>>n;
int arr[n+];
int s=;
for(int i=;i<=n;i++){
cin>>arr[i];
s+=arr[i];
}
int x=s/n;
if(s%n==){
cout<<x;
}else{
cout<<x+;
}
cout<<endl;
}
return ;
}
B1，B2题
题意：给你个长度为 n 的数组和一个队列 , 队列最多可以同时存在 k 个数。遍历这个数组 , 如果当前数组对应的数在队列中则不做改动 , 如果不在则将它插入队首 , 并且将队尾弹出。遍历完后按照队列顺序输出。
思路：模拟即可【deque+map】
AC代码：
#include<bits/stdc++.h> using namespace std; #define int long long
map<int,int> vis;
deque<int> q;
signed main(){
int n,k;
cin>>n>>k;
int temp;
for(int i=;i<=n;i++){
scanf("%lld",&temp);
if(vis[temp]){
continue;
}else{
vis[temp]++;
q.push_front(temp); if(q.size()>k){
int x=q.back();
q.pop_back();
vis[x]--;
}
}
}
deque<int>::iterator it = q.begin();
cout<<q.size()<<endl;
for(;it!=q.end();it++){
printf("%lld ",*it);
}
return ;
}
C题：
题意：有六种管子 , 其中1、2可以互相转换 ， 3、4、5、6可以互相转换 ， 然后给你两行管道 ， 每行有 n 列问水能不能从左上角（第1行第1列）流到右下角（第2行第n列）
思路：模拟即可。判断是否从row==2行流出。是，则判断流出的水是不是水平的。否则，直接NO。【注意：后面四种的形状只能上下两个都是才能往前走】
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int _;
cin>>_;
while(_--){
int n;
cin>>n;
string s1,s2;
cin>>s1>>s2;
int mp[][n+];
int row=;
int flag=;
for(int i=;i<n;i++){
if(!flag){
break;
}
if(i==){
if(s1[i]==''||s1[i]==''){
mp[row][i]=;
}else{
mp[row][i]=;
row=;
if(s2[i]==''||s2[i]==''){
flag=;
break;
}else{
mp[row][i]=;
}
}
continue;
}
if(row==){
if(s1[i]==''||s1[i]==''){
mp[row][i]=;
continue;
}else{
mp[row][i]=;
row=;
if(s2[i]==''||s2[i]==''){
flag=;
break;
}else{
mp[row][i]=;
}
}
}else{
if(s2[i]==''||s2[i]==''){
mp[row][i]=;
continue;
}else{
mp[row][i]=;
row=;
if(s1[i]==''||s1[i]==''){
flag=;
break;
}else{
mp[row][i]=;
}
}
}
}
if(!flag||row==){
printf("NO\n");
continue;
}
if(mp[][n-]==||mp[][n-]==){
printf("YES\n");
}else{
printf("NO\n");
}
}
return ;
}
/*
6
7
2323216
1615124
1
3
4
2
13
24
2
12
34
3
536
345
2
46
54
*/
D题
题意：给你一个字符串 ， 有q个操作：
①、 将 pos 位置的字符改为 c
②、查询 L~ R 区间不同字符的个数
思路1：set模拟实现。
AC代码：
#include<bits/stdc++.h> using namespace std;
set<int> s[];
char str[];
int main(){ scanf("%s",str+);
for(int i=;i<=strlen(str+);i++){
s[str[i]-'a'].insert(i);
}
int _;
scanf("%d",&_);
while(_--){
int T;
scanf("%d",&T);
if(T==){
int x;
char c;
scanf("%d",&x);
cin>>c;
s[str[x]-'a'].erase(x);
s[c-'a'].insert(x);
str[x]=c;
}else{ int l,r;//cin>>l>>r;
scanf("%d%d",&l,&r);
int ans=;
for(int i=;i<;i++){
set<int>::iterator it;
it=s[i].lower_bound(l);
if(it==s[i].end()){
continue;
}
if(*it>=l&&*it<=r)
ans++; }
printf("%d\n",ans);
}
} return ;
}
思路2：【了解了大佬们的写法】维护26个树状数组,代表每个字母从1到i出现了多少次,对于查询,遍历这26个树状数组看每个字母是否在区间内出现,对于修改,这个位置原来的字母减去1,新来的字母加上1即可.
AC代码：
#include<bits/stdc++.h>// 维护26棵树状数组QAQ using namespace std;
#define int long long
int n;
struct str{
int c[];
int lowbit(int x){
return x&(-x);
}
void update(int x,int v){
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=v;
}
int getsum(int x){
int res=;
for(int i=x;i;i-=lowbit(i))
res+=c[i];
return res;
}
int query(int l,int r){
return getsum(r)-getsum(l-);
}
}st[];
signed main(){
string s;
cin>>s;
n=s.size();
for(int i=;i<s.size();i++){
st[s[i]-'a'].update(i+,);
}
int Q;
cin>>Q;
int temp;
while(Q--){
cin>>temp;
if(temp==){
int x;
char y;
cin>>x>>y;
st[s[x-]-'a'].update(x,-);
s[x-]=y;
st[y-'a'].update(x,);
}else{
int sum=;
int L,R;
cin>>L>>R;
for(int i=;i<;i++){
if(st[i].query(L,R)>)
sum++;
}
printf("%lld\n",sum);
}
}
return ;
}
