Zhejiang programming competition 2019

ZOJ - 4104

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

 ZOJ - 4105 

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

 

G - Lucky 7 in the Pocket

 ZOJ - 4106

Water question

H - Singing Everywhere

 ZOJ - 4107

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

 ZOJ - 4108 

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