Hand speed game, because the level is not enough three questions regret to leave the game.
A. Meaning Mean
meaning of a title
You a sequence where you can choose two numbers at a time to delete and add their average to the end of the sequence. When the length of the sequence is\(1\) What is the maximum value of the remaining number at the time of the
reasoning
At the time the game was don and it was delayed for several minutes. The idea was to add odd and odd numbers first, and even and even numbers, so as to avoid rounding off the next\(-1\) . In fact, it is sufficient to choose the two smallest numbers in the sequence each time the operation is performed, since each operation is equivalent to dividing the two numbers by\(2\) , so dividing large numbers as little as possible will ensure that the number left at the end is the largest.
coding
void solve()
{
int n;
cin>>n;
priority_queue<int,vector<int>,greater<int>> q;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
(x);
}
while(()!=1)
{
int x=();();
int y=();();
((x+y)/2);
}
cout<<()<<endl;
}
B. Maximize Mex
meaning of a title
Give you a sequence and a\(x\) You can do this any time you want.\(a_i:=a_i+x\) . Ask you to optimally manipulate the sequence of\(MEX\) What's the maximum.
meaning of a title
general request\(MEX\) I'd open a bucket to keep track of how many times each number appeared, traversing from smallest to largest the first number that didn't appear was the\(MEX\) This question is the same thing. The question is the same, if there are more than one identical number then only one number can produce a contribution and then let the rest be added\(x\) Ready to go.
coding
void solve()
{
int n,m;
cin>>n>>m;
vector<int> num(n+2);
for(int i=1;i<=n;i++)
{
int x;cin>>x;
if(x>n) continue;
num[x]++;
}
for(int i=0;i<=n+1;i++)
{
if(!num[i]) {cout<<i<<endl;return;}
num[i]--;
if(i+m<=n) num[i+m]+=num[i];
num[i]=0;
}
}
C1. Adjust The Presentation (Easy Version)
meaning of a title
Gives you a length of\(n\) The order of the operators of the\(a\)and then give you a length of\(m\) Establishes the order of items that can only be operated by whom\(b\) . Each operator can be inserted anywhere in the queue after operating once. Ask you this\(m\) Can an item be manipulated to completion by the corresponding operator.
reasoning
First of all a person who is done operating it can insert it into any position in the queue, indicating that heIt's unbeatable.If the operator specified by the item currently being operated on is at the back of the queue and he has not operated on any item, then he cannot get to the front of the queue to operate anyway, and the sequence is not legal. If the operator corresponding to this item has already operated on it, since he can go to any position, then this item can be operated on immediately. If all items can be manipulated then the sequence is legal.
coding
using namespace std;
void solve()
{
int n,m,q;
cin>>n>>m>>q;
vector<int> a(n+1),b(m+1);
vector<int> vis(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
int pos=1;
for(int i=1;i<=m;i++)
{
if(vis[b[i]]) continue;
else if(a[pos]==b[i])
{
vis[a[pos]]=1;
pos++;
continue;
}
else {cout<<"TIDAK\n";return;}
}
cout<<"YA\n";
}
C2. Adjust The Presentation (Hard Version)
meaning of a title
exist\(\text{C1}\) A modified operation has been added to the base of the I have\(q\) Sub-modification operations, each of which can replace an item-specified operator (permanent operation), ask whether the sequence is still legal after you have modified it.
reasoning
If one can switch places at will(invincible) indicates that he has already manipulated the item, then the earliest he can switch positions is the subscript of the first item that designates him as the operator, i.e., the first\(b_j=i\) subscript\(j\) . Then each person's earliest invincibility time cannot be earlier than the invincibility time of the person in front of him. Now the question is how to maintain this earliest invincibility time.
We will only modify one position at a time, so he can affect the position in front of him, the position behind him and himself. So we only need to update these three positions for each modification.
coding
void solve()
void void solve()
int n,m,q,num=0.
cin>>n>>m>>q.
vector<int> a(n+1),b(m+1),inv(n+1),s(n+1);
vector<set<int>> times(n+1);//maintain the earliest invincibility time for each person
for(int i=1;i<=n;i++) cin>>a[i],inv[a[i]]=i;
for(int i=1;i<=m;i++)
{
cin>>b[i];
b[i]=inv[b[i]];
times[b[i]].insert(i);
}
for(int i=1;i<=n;i++)
{
s[i]=times[i].empty()?m+1:*times[i].begin();//if no item is specified that he operates on, then the person's invincibility time is positive infinity
}
for(int i=1;i<n;i++) if(s[i]>s[i+1]) num++;//count the number of people who are not legal
if(num) cout<< "TIDAK\n";
else cout<< "YA\n".
auto update=[&](int x,int c)
{
if(c==1) s[x]=times[x].empty()?m+1:*times[x].begin();
if(x>1 && s[x-1]>s[x]) num+=c;
if(x<n && s[x]>s[x+1]) num+=c;
};
while(q--)
{
int x,y;cin>>x>>y.
y=inv[y];
update(b[x],-1);//delete the contribution at this position
times[b[x]].erase(x);
update(b[x],1);//update the invincibility time and the number of illegal positions after deletion
b[x]=y;//modify
update(b[x],-1);
times[b[x]].insert(x);
update(b[x],1);
if(num) cout<< "TIDAK\n";
else cout<< "YA\n";
}
}