Review the preliminaries well. I pressed the line
Fooling around with the cover
1. Divide candy
Generally speaking, T1 is not too difficult. In fact, it is not very difficult
I was so stupid that I didn't think of it until half an hour later
Cough, look at the data range of 10 ^ 9109, it's not done with violence.
If there are n children (including you) and you move K sweets, the final reward you get is k mod n# sweets. In other words, if you move at least l sweets and at most k sweets, if you want to get the most reward, you should choose a number between L and r to maximize the value of this digital analog n.
In the optimal case, there will be ＾ n - 1 candy left. Of course, example ＾ 2 tells us that sometimes we can't be so greedy, and the optimal result may not reach ＾ n - 1, which means that between l and R, the larger the number, the greater the value of modulus n. So in this case, take r candy directly, and the result must be the best. In other cases, the optimal value is n - 1.
So here comes the code you want:
#include<bits/stdc++.h>
using namespace std;
int n,l,r;
int main(){
cin>>n>>l>>r;
cout<<min(r,l+(n-1-l%n))%n; //First try to add the remainder to n-1. If it exceeds R, the result is r mod n, otherwise it is n-1
return 0;
}2. Insert sort
T2 is not too difficult, but there are a lot of pits. Just avoid it
Since the given condition is that the number of modifications does not exceed 50005000, we should write an article at the modification.
Note that after performing the "demonstration code" for an array a, the necessary and sufficient condition for the number ， ai ， to precede aj ， is that one of the following two holds:
-
<
- =And I < J
Consider maintaining an array b to store the relative ranking of each number in array A. when entering a, make statistics (use the above two judgments):
Each operation 2, output
.
Every time you perform operation 1, you will
Change to v. At this time, use O(n) to traverse each element in the array. If an element i satisfies that it was before x and now after x after the array is inserted and sorted (it is still determined by two lines), because the relative position of i and other numbers in the array has not changed, so
Add one,Just reduce it by one. The same is true in the other case.
Upper code
#include<bits/stdc++.h>
using namespace std;
int n,q,a[8005],b[8005],num,x,v,ans;
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(i==j||a[j]<a[i]||a[j]==a[i])b[i]++;
else b[j]++;
}//b[i] here is the ranking of the ith number in array a[i]
}
for(int i=0;i<q;i++)
{
scanf("%d",&num);
if(num==1)
{
scanf("%d%d",&x,&v);
for(int i=1;i<=n;i++)
{
if(i==x)continue;
if((a[i]<a[x]||a[i]==a[x]&&i<x)&&(a[i]>v||a[i]==v&&i>x))
{
b[i]++;b[x]--;
}
else if((a[i]>a[x]||a[i]==a[x]&&i>x)&&(a[i]<v||a[i]==v&&i<x))
{
b[i]--;b[x]++;
}
}
a[x]=v;
}
if(num==2)
{
scanf("%d",&x);
printf("%d\n",b[x]);
}
}
return 0;
}3. Network connection
As T3, it must be difficult, but it's not so difficult to think about it
Seeing that the address string needs to be mapped to the computer number, we can consider using the {map. It is recommended to use {unordered whose usage is basically similar, but the query and modification complexity are} O(1)O(1)_ Map (C++11 is required. If it cannot be compiled locally, the compilation option should be added).
thinking
- First judge whether the address string provided by each computer meets the specification. If not, directly output {ERR;
- For the address string provided by each Server, first find out whether the mapping of the address string has been established in the "unordered_map" (i.e. whether a Server has provided the same address string to establish a connection). If it has, output "FAIL". Otherwise, establish the mapping and output "OK";
- For the address string provided by each Client, first find out whether the mapping of the address string has been established in the unordered_map (i.e. whether a server has provided the address string to establish a connection). If it has, the Client can join the connection, and the number of the server establishing the connection is output. Otherwise, the Client cannot join the connection, and # FAIL is output.
Here is a brief introduction to unordered_map .
unordered_map is essentially like an array,
But you can define the key and value (actually the element corresponding to the subscript) types yourself.
unordered_map<string,int> mp;
So you have an unordered string that can be mapped to an int type_ Map ， array ， mpmp.
mp["hello"] = 532;
This means that in the "mpmp" array, \ mathtt{"hello"}"hello" corresponds to \ mathtt{532}532.
mp.count("hello");
mp.count("world");Determine whether there is a mapping before the element. The return values are 1 and 0 respectively.
The use of map ， is similar to it and will not be repeated here.
The part that determines whether the address string exists can be used as "unordered"_ Map} solution, then the focus of the whole problem is how to judge whether the address string is standardized.
Let's first list all possible forms of address strings that do not conform to the specification.
- For example, a.b.c.d:e, in which one number of integers a,b,c,d,e exceeds the given range of the topic (i.e. 0 ≤ a,b,c,d 2550 ≤ a,b,c,d ≤ 255 ≤ e ≤ 655350), or one number contains a leading 0.
In view of this situation, we can extract a, B, C, D and E in turn by the following methods and judge whether they are within the specified range.
bool check(string s)
{
int len = s.length();
long long tmp = 0;
for(int i=0;i<len;i++)
{
if(s[i]=='.'||s[i]==':')
{
if(0<=tmp&&tmp<=255) //Judge whether a, B, C and d meet the specifications
{
tmp = 0; //Clear
continue;
}
else return false;
}
else if(s[i]<'0'||s[i]>'9') return false;
if(i&&!tmp&&s[i-1]=='0') return false; //This line is used to determine the leading 0
tmp = tmp*10+s[i]-'0'; //Read number
}
if(0<=tmp&&tmp<=65535) return true; //Judge e whether it meets the specification
else return false;
}- The shape is a.b.c:d.e, where the characters are Or: the order of occurrence is not standardized.
In this case, we can use counters to record separately And: times of occurrence, judgment: when it occurs Whether the number of occurrences is 3. -
int cnt1=0,cnt2=0,cnt3=0; for(int i=0;i<len;i++) { if(s[i]=='.'||s[i]==':') { if(s[i]=='.') cnt1++; else if(s[i]==':') cnt2++; if(cnt1<3&&cnt2) return false; //Is the order of occurrence standardized /* Judge whether the range of a, B, C and D is standardized */ } else if(s[i]<'0'||s[i]>'9') return false; /* Judge leading 0 and extract number */ }
-
As shown in Figure a b. C: e ， or A.B.C: e. Among them are characters Or: appear continuously.
At this time, the number of symbols meets the specification, but the number of numbers does not meet the specification. Following the example of case 2, a counter can be used to record the number of occurrences of numbers, and finally judge whether the number of occurrences of characters and numbers meet the specifications. -
In shape a.b.c:e or a.b.c.d:, where the characters are Or: appears at the beginning and end of the address string. When characters appear in the header, we can judge whether there are numbers when characters appear; For the case where characters appear at the end, the method of case 3 can be used.
In both cases, a digital counter is required.
int len = s.length();
long long tmp = 0;
int cnt1=0,cnt2=0,cnt3=0;
for(int i=0;i<len;i++)
{
if((i==0||(s[i-1]=='.'||s[i-1]==':'))&&s[i]>='0'&&s[i]<='9') cnt3++;
//If the current is the first position or the previous is a character, and this position is a number
if(s[i]=='.'||s[i]==':')
{
/*
Counts the number of occurrences of characters
*/
if(cnt1<3&&cnt2) return false; //Is the order of occurrence standardized
if(!cnt3) return false; //If the character appears before the first number
/*
Judge whether the range of a, B, C and D is standardized
*/
}
else if(s[i]<'0'||s[i]>'9') return false;
/*
Judge leading 0 and extract number
*/
}
if(cnt1!=3||cnt2!=1||cnt3!=5) return false; //Judge the number of characters and numbers
/*
Judge whether the scope of e is standardized
*/Put the solutions of the above four cases together to get the function to judge whether the address string is standard or not.
Code
#include <bits/stdc++.h>
using namespace std;
int n;
unordered_map<string,int>address;
bool check(string s)
{
int len = s.length();
long long tmp = 0;
int cnt1=0,cnt2=0,cnt3=0;
for(int i=0;i<len;i++)
{
if((i==0||(s[i-1]=='.'||s[i-1]==':'))&&s[i]>='0'&&s[i]<='9') cnt3++;
//If the current is the first position or the previous is a character, and this position is a number
if(s[i]=='.'||s[i]==':')
{
if(s[i]=='.') cnt1++;
else if(s[i]==':') cnt2++;
//Counts the number of occurrences of characters
if(cnt1<3&&cnt2) return false; //Is the order of occurrence standardized
if(!cnt3) return false; //If the character appears before the first number
if(0<=tmp&&tmp<=255) //Judge whether the range of a, B, C and D is standardized
{
tmp = 0;
continue;
}
else return false;
}
else if(s[i]<'0'||s[i]>'9') return false; //Strange characters appear
if(i&&!tmp&&s[i-1]=='0') return false; //Judge leading 0
tmp = tmp*10+s[i]-'0'; //Extract numbers
}
if(cnt1!=3||cnt2!=1||cnt3!=5) return false; //Is the number of characters and numbers correct
if(0<=tmp&&tmp<=65535) return true; //Range of judgment e
else return false;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
string cpt,adr;
cin>>cpt>>adr;
if(!check(adr)) puts("ERR"); //If the address string does not meet the specification
else if(cpt=="Server")
{
if(address.count(adr)) puts("FAIL");
else
{
address[adr] = i;
puts("OK");
}
}
else if(cpt=="Client")
{
if(address.count(adr)) printf("%d\n",address[adr]);
else puts("FAIL");
}
}
return 0;
}4. Bear's fruit basket
I think T4 is more water than T3
First, build a two-way linked list for the input sequence, maintain each "false block" header, build a two-way linked list, and maintain two linked lists in total.
The "fake block" here means that the types of fruits in each "fake block" must be the same, but the types of fruits in adjacent "fake blocks" may be the same.
We can use the deletion element of the two-way linked list to simulate eating a fruit.
Constantly cycle through the "fake block" head linked list, and record the last fruit type eaten in the process of traversal. When traversing a block, if the fruit it points to is the same as the last eaten fruit, directly delete the block, which is equivalent to merging blocks; If it is different, eat the fruit, update the type of the last eaten fruit, and turn the fruit pointed to by this block into the next fruit of the eaten fruit.
As for the processing method of a fake block being eaten up, the block head of the fake block must point to the next block head. If the type of this block is different from the type of fruit to be eaten, delete this block, because the fruit will be eaten when traversing the next block; If same, do not move, because next process will delete header of the next block. This ensures that false blocks with a length less than one will not appear during traversal. If the fake block is not eaten, the next fruit it points to must be the same type as the one eaten, and no treatment will be done.
Each fruit is traversed once, and each block is deleted once, with time complexity Θ (n).
The code is as follows:
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 2e5+10;
struct Node{
int prev;
int val;
int next;
};
int n;
int shuiguo[MAXN];
Node headList[MAXN];
Node shuiguoList[MAXN];
int cc;
void EatOne(int pos) {
int prev = shuiguoList[pos].prev;
int next = shuiguoList[pos].next;
shuiguoList[prev].next = next;
shuiguoList[next].prev = prev;
printf("%d ", pos);
}
void Del(int pos) {
int prev = headList[pos].prev;
int next = headList[pos].next;
headList[prev].next = next;
headList[next].prev = prev;
}
void Chi() {
int solo = headList[0].next;
int nowcolor = shuiguo[headList[solo].val];
while (solo!=cc+1) {
if (shuiguo[headList[solo].val]!=nowcolor) {
Del(solo);
solo = headList[solo].next;
continue;
}
EatOne(headList[solo].val);
headList[solo].val = shuiguoList[headList[solo].val].next;
if (shuiguo[headList[solo].val]!=nowcolor) {
Del(solo);
}
solo = headList[solo].next;
nowcolor^=1;
}
putchar('\n');
}
int main() {
scanf("%d", &n);
shuiguoList[0].next = 1;
for (int i = 1; i <= n; i++) {
scanf("%d", &shuiguo[i]);
shuiguoList[i].prev = i-1;
shuiguoList[i].next = i+1;
}
shuiguo[0] = 2;
shuiguo[n+1] = 2;
headList[0].next = 1;
for (int i = 1; i <= n; i++) {
if (shuiguo[i]!=shuiguo[i-1]) {
cc++;
headList[cc].prev = cc-1;
headList[cc].next = cc+1;
headList[cc].val = i;
}
}
while (shuiguoList[0].next!=n+1) {
Chi();
}
return 0;
}Learn the preliminaries well. I think the preliminaries are more difficult than the semi-finals
I wish you 70 in the first round and AK in the second round. come on.