# Zhejiang programming competition 2019

Meaning:

A sequence of numbers. Each operation can raise any number to the front of the sequence. Ask how many operations can change the sequence into a non descending sequence?

Solution:

It can be observed that any number sequence can be changed into a non descending number sequence by up to n-1 operations. We are building an array like the original array. Consider from the back to the front. If the position of this number is correct, skip it. If it is incorrect, the number must be raised at least once, and they will move back one for the number in front of this number

We define a variable to record the number of moves, cnt. When we process the next number, its position has moved back cnt. Then let it compare with a[i+cnt]. If it is equal, skip it. If it is not equal, it means that the number operated before this number needs to move forward, then cnt + +. In this way, cnt is the final answer.

```const int N = 1e5 + 10;
int num[N];
signed main()
{
// STDIN
int t;
cin >> t;
for (int _ = 1; _ <= t; _++)
{
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++)
{
scanf("%d",&a[i]);
b[i] = a[i];
}
sort(a.begin(), a.end());
int cnt = 0;
for (int i = n-1; i>= 0; i--)
{
if (a[(i+cnt)] != b[i])
{
cnt++;
}
}
cout <<cnt << endl;
}
}```

## F - Abbreviation

Meaning:

Delete the vowel letter of the string. Note that the first letter is not deleted and the processed letter is output

Solution: water problem

Water question

## H - Singing Everywhere

Meaning:

A sequence of numbers, if a [i] > a [I-1] & & A [i] > a [i + 1], calculates a broken tone. When you can delete at most one number, what is the minimum number of broken tones?

Problem solution

Judge the number of broken sounds after deleting each number by violence, and pay attention to the treatment of the boundary

```#define int long long

set<int> se;
signed main()
{
//STDIN
int t; cin >> t;
for (int _ = 1; _ <= t; _++)
{
int n;
cin >> n;
vector<int> a;
for (int i = 1; i <= n; i++)
{
int x;
scanf("%lld", &x);
a.push_back(x);
}
for (int i = 1; i < n-1; i++)
{
if (a[i] > a[i-1] && a[i] > a[i+1]) se.insert(i);
}
int ans = se.size();
int res = ans;
for (int i = 0; i < n; i++)
{
if (i == 0)
{
if (se.find(1) != se.end())
{
res = min(ans-1, res);
}
}
else if (i == n-1)
{
if (se.find(n-2) != se.end())
{
res = min(ans-1, res);
}
}

else{
int t = ans;
if (se.find(i) != se.end()) t--;
if ( i-2 >=0)
{
if ( a[i-1] > a[i-2] && a[i-1] > a[i+1])
{
if (se.find(i-1) == se.end()) t++;
}
else {
if (se.find(i-1) != se.end()) t--;
}

}
if (i+2 <= n-1 )
{
if(a[i+1] > a[i-1] && a[i+1] > a[i+2])
{
if (se.find(i+1) == se.end()) t++;
}
else{
if (se.find(i+1) != se.end()) t--;
}

}
res = min(t, res);
}
}
cout << res << endl;
se.clear();
}
}```

## I - Fibonacci in the Pocket

Meaning:

Find whether the interval sum of Fibonacci sequence is odd or even

Solution:

Find rules

```int mod1(string a, int b) //high-precision a Divide by single precision b
{
int d = 0ll;
for (int i = 0; i < a.size(); i++)  d = (d * 10 + (a[i] - '0')) % b;  //Find the remainder
return d;
}
signed main()
{
// STDIN
int t;
cin >> t;
for (int _ = 1; _ <= t; _++)
{
string a, b;
cin >> a >> b;
int a1 = mod1(a,3);
int b1 = mod1(b,3);
if ((a1 == 1 && b1 == 2) ||(a1 == 0 && b1 == 0)||(a1 == 1 &&b1 == 0)|| (a1 == 2 && b1 == 1) ||(a1 == 0 && b1 == 2))
{
cout<< 0 << endl;
}
else cout << 1 << endl;
}
}```

Posted by php4om on Mon, 16 May 2022 15:32:37 +0300