Training summary

This week, I chose this set of topics to practice. I feel that this set of topics still has some merits, but what we do can only be said to be in line with the rules. In addition, the speed and accuracy of simple topics have been greatly improved compared with the previous ones. Don't say more. Keep up your efforts.

C Insertion Sort

Title and analysis

This problem is to give you two numbers n, K, followed by p is a remainder, which has nothing to do with the meaning of the problem. N is the length of the array. Which function in the title means that the first k numbers can be automatically arranged into an increasing sequence. I ask you how many full permutations in the full permutation of N numbers can become an increasing sequence after the operation of this function. The length of the sequence is greater than or equal to n − 1 n-1 n−1.
Then we start to analyze and we can know if k = n − 1 k=n-1 k=n − 1 or k = n k=n If k=n, then the left and right permutations meet the conditions, then the answer is naturally A n n A^n_n Ann, i.e n ! n! n!. If it is less than n-1, it can be divided into three parts. The first two parts are ( n − 2 ) × A k k (n-2)\times A_k^k (n−2) × Akk ， and ( n − k ) × A k k (n-k)\times A_k^k (n−k) × Akk, the last part can be defined in this way: determine that the last digit is n, and then the first n-1 number is the answer that n becomes n-1 under the condition of the same K, so write it back and add it directly.

code

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>

#define ll long long
#define INF 0x3f3f3f3f

using namespace std;

ll cal(ll n,ll m,ll p)//This function is used to calculate the combination number Amn
{
    ll res=1;
    for(ll i=0;i<m;i++)
    {
        res=res*(n-i)%p;
    }
    return res;
}

ll jisuan(ll n,ll k,ll p)//This function calculates the final answer
{
    if(k>=n-1)
    {
        return cal(n,n,p);
    }
    else
    {
        ll ans=((2*n-k-2)*cal(k,k,p))%p;//This part is the two conclusions
        ans=(ans+jisuan(n-1,k,p))%p;
        return ans;
    }
}

void solve(int index)
{
    ll n,k,p;
	scanf("%lld%lld%lld",&n,&k,&p);
	printf("Case #%d: ",index);
	printf("%lld\n",jisuan(n,k,p));
	return ;
}

int main()
{
	int t = 1;
	scanf("%d",&t);
	for(int index=1;index<=t;index++)
	{
		solve(index);
	}
    return 0;
}

J How Much Memory Your Code Is Using?

Title and analysis

The meaning of this question should be well understood, that is, let you find out how many KB the defined variables occupy, because the calculation is calculated according to B, so the following is the final conversion. Moreover, there is no such method of naming multiple variables with commas, so it should be easy to judge. Let's write it directly.

code

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

ll judge(char a,char b)
{
    if(a=='b')
        return 1;
    else if(a=='c')
        return 1;
    else if(a=='i')
        return 4;
    else if(a=='_')
        return 16;
    else if(a=='f')
        return 4;
    else if(a=='d')
        return 8;
    else if(a=='l')
    {
        if(b=='l')
            return 8;
        else
            return 16;
    }
    return 0;
}

void solve(int k)
{
    int n;
    scanf("%d",&n);
    string str;
    ll ans=0;
    getline(cin,str);
    while(n--)
    {
        ll temp=0;
        getline(cin,str);
        int len=str.size();
        int left=0,right=0;
        for(int i=0;i<len;i++)
        {
            if(str[i]=='[')
                left=i;
            if(str[i]==']')
                right=i;
        }
        ll scale=1;
        if(left==right)
            temp=1;
        for(int i=right-1;i>left;i--)
        {
            temp+=((str[i]-'0')*scale);
            scale*=10;
        }
        ans+=(temp*judge(str[0],str[5]));
    }
    ll shang=ans/1024;
    ll yu=ans%1024;
    if(yu!=0)
        shang++;
    printf("Case #%d: %lld\n",k,shang);
}

int main()
{

	int t = 1;
	scanf("%d",&t);
	for(int k=1;k<=t;k++)
	{
		solve(k);
	}
    return 0;
}

K Let the Flames Begin

Title and analysis

Although the topic is easy to understand, it is not so easy to really do it. The main reason is that we have not contacted Joseph Ring before, so there is a short board. It can be regarded as the exposure of this training. As for this topic, it uses the relevant knowledge in this aspect. If you basically don't know this knowledge point, it's difficult to make this topic. Moreover, some changes have been made on the basis of Joseph's ring,
enclosed link
The key formula is such a recursive formula: A ( n , m ) = ( A ( n − 1 , m − 1 ) + k ) % n A(n,m)=(A(n-1,m-1)+k)\%n A(n,m)=(A(n−1,m−1)+k)%n
You can give yourself a few examples. It's relatively easy to push them out.
Note in the following calculation:
When m is relatively large, it should be processed accordingly, and when m is small, it should be pushed directly.
The process is as follows:
Because the range of m is 1e18 and the range of k is 1e6, and each time it is an operation of adding k, there are many times this % n \%n %n many times it's useless, so we can put these at once k k k is added to reduce the complexity. (I also saw other people's ideas here. I'm still too delicious)

code

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

ll F(ll n,ll m,ll k)
{
    if(m==1)return (k-1)%n;
    return (F(n-1,m-1,k)+k)%n;
}

void solve(int index)
{

    ll n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    printf("Case #%d: ",index);
    if(k==1)
    {
        printf("%lld\n",m);
        return ;
    }
    if(m<=1e6)
        printf("%lld\n",F(n,m,k)+1);
    else
    {
        ll ct=n-m+1;
        ll val=(k-1)%ct;
        ll now=1;
        while(now<m)
        {
            if(val+k>=ct+1)
            {
                ct++;
                val=(val+k)%ct;
                now++;
                continue;
            }
            ll x=(ct-val-1)/(k-1);
            x=min(x,m-now);
            now+=x;
            val+=k*x;
            ct+=x;
        }
        printf("%lld\n",val+1);
    }
}
int main()
{

    int t = 1;
    scanf("%d",&t);
    for(int k=1; k<=t; k++)
    {
        solve(k);
    }
    return 0;
}