Analysis and summary of 2021ccpc online games

1001 ： Cut wires

There are an infinite number of street lights on the street 1 Start , The streetlights are wired together . But the connection is regular , If the number of the street lamp x It's even , Then it is numbered x / 2 Connected to a . If the number of the street lamp x Is odd , So it's with 3*x+1 Connected to a , Given n, Ask you to stand on the street lamp numbered n and n+1 How many wires can be cut between .（ The street lamp number on the left <=n, The street lamp number on the right >n）.
The data range is as follows ：

It can be seen from the figure that the enumeration of violence will definitely time out , But generally no one can use . It is only necessary to calculate the sum of odd connected lines and even connected lines , Need to find a few examples to push .

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int main()
{
    
    int t;
    scanf("%d", &t);
    while (t--)
    {
    
        int  n;
        scanf ("%d",&n);
        LL res = 0;
        res += n - n/2; // Calculate even numbers 
        int b = (n-1)/3+1;// Calculate the odd case 
        if (b%2) res+=(n-b)/2+1;
        else
        res+=(n-b+1)/2;
        printf ("%lld\n",res);
    }
    return 0;
}

1006： Sum of squares

The topic is really concise and comprehensive , Let you accumulate from 1 To k Sum of the squares of and find n, In addition, each term can be multiplied by 1, Or take a ride -1, That is, either add or subtract , And let you output the answer .

Data range

Don't mention searching , Some people really dare to use , This is really a regular question , At that time, we no longer wanted to write because of the annoying operation of the server , What a pity .
Subtracting from the square is a common practice in high school , After subtracting, you will find the rule , Subtract every two adjacent terms to get 2, When you calculate the first few , Find out 1,2,3 Can be calculated , At this time, it's enough to think of constructing with four periods .

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    
    int t;
    scanf("%d", &t);
    while (t--)
    {
    
        int n;
        scanf("%d", &n);
        int k=n;
        string res;
        
        if (n%4==1) res+="1";
        if (n%4==2) k+=2,res+="0001";
        if (n%4==3) k-=1,res+="01";
        for (int i=0;i<n/4;i++)
          res+="1001";
          
         cout<<k<<endl;
         cout<<res<<endl;
    }
    return 0;
}

1007： Quadratic function

The main idea of the topic is to give a quadratic function , A given range lets you find its minimum value in the range , Then you should think of Trisection , Find the extreme value of quadratic function . Dichotomy is the property dividing point for finding the satisfaction of the primary function .
A good link to three points ++++++++++++++++++++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
const LL inf = 1e18;
vector<int>mh[100];
int cul (int x)
{
    
    int res = 0;
    while (x)
    {
    
        res+=x%10;
        x/=10;
    }
    return res;
}
void init()
{
    
    for (int i=1;i<=N;i++)
    {
    
        int x = cul(i);
        mh[x].push_back(i);
    }
}
LL doit(LL x,LL A,LL B)
{
    
    return A*x*x+B*x;
}
int main()
{
    
    init();
    int t;
    scanf("%d", &t);
    while (t--)
    {
    
        LL a,b,c,d,n;
         scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&n);
        LL res = inf;
        for (int i=1;i<=54;i++)
        {
    
            if (mh[i].size()==0) continue;
            LL A = a*i+b;
            LL B = c*i*i+d*i;
            int l=0,r = upper_bound(mh[i].begin(),mh[i].end(),n)-mh[i].begin();
            r--; // Make sure the right endpoint is within the range of the argument 
            if (r<0) continue;
            if (A<=0) // Is a straight line 
            {
    // Extremum can only be at the start and end 
                res = min(res,doit(mh[i][0],A,B));
                res = min(res,doit(mh[i][r],A,B));
            }
            else
            {
    
                LL resl = inf,resr = inf;
                while (l<=r)
                {
    
                    int lmid = l + (r - l)/3;
                    int rmid = r - (r - l)/3;
                    resl = doit(mh[i][lmid],A,B);
                    resr = doit(mh[i][rmid],A,B);
                    if (resl<=resr)
                     r = rmid-1;
                     else
                     l = lmid+1;
                }
                res = min(res,min(resl,resr));
            }
        }
        printf ("%lld\n",res);
    }
    return 0;
}

1009： Command sequence

The main idea of the title is to give a string , The robot will move up, down, left and right according to the instructions of the string , Let you find the number of substrings that can bring the robot back to the origin . Classic substrings are prefixes and string hashes , Subsequence thinking DP.
This problem is the classic prefix and hash . The robot can return to the origin, that is, the number of times to the left is equal to the number of times to the right, and the number of times to the up is equal to the number of times to the down .

Data range

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const int N = 1e5+10;
char s[N];
map<PII,int> mh;
int main()
{
    
    int t;
    scanf("%d", &t);
    while (t--)
    {
    
        mh.clear();
        int n;
        scanf("%d", &n);
        scanf("%s", s+1);
        int x=0,y=0;
        LL res = 0;
        mh[make_pair(0,0)] = 1;
        for (int i = 1; i <= n; i ++ )
        {
    
            if (s[i]=='U') x--;
            else if (s[i]=='D') x++;
            else if (s[i]=='L') y--;
            else
            y++;
            res += mh[make_pair(x,y)];
            mh[make_pair(x,y)]++;
        }
        printf ("%lld\n",res);
    }
    return 0;
}

Links to supplementary questions , Go in and turn down Source Inside 2021 Chinese college students program design competition （CCPC）- Online trials