Niuke multi school E G J L

C. awoo’s Favorite Problem
The topic is to give two only abc A three letter string , The first one can put ab Switch to ba Or the bc Switch to cb, Ask if these two strings can be equal .
The idea is to remove b Two strings are equal and corresponding to the position a In the first, it cannot be on the right of the second ,c contrary .

But I learned a kind of introduction stl How to write it . I 80 The multi line code was shocked .

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int)2e5;

int main() {
    
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) {
    
		int n;
		string s[2], t[2];
		cin >> n >> s[0] >> s[1];
		vector<int> cnt[2][3];
		for(int d = 0; d < 2; d++) {
    
			for(int i = 0; i < n; i++) {
    
				cnt[d][s[d][i] - 'a'].push_back(i);
				if(s[d][i] != 'b') {
    
					t[d].append(1, s[d][i]);
				}
			}
		}
		bool tag = t[0] == t[1];
		for(int k = 0; k < 3; k++) {
    
			if(cnt[0][k].size() != cnt[1][k].size()) {
    
				tag = false;
			}
		}
		if(!tag) {
    
			cout << "NO\n";
		} else {
    
			for(int i = 0; i < (int)cnt[0][0].size(); i++) {
    
				if(cnt[0][0][i] > cnt[1][0][i]) {
    
					tag = false;
				}
			}
			for(int i = 0; i < (int)cnt[0][2].size(); i++) {
    
				if(cnt[0][2][i] < cnt[1][2][i]) {
    
					tag = false;
				}
			}
			if(!tag) {
    
				cout << "NO\n";
			} else {
    
				cout << "YES\n";
			}
		}
	}
	
	
	return 0;
}

" Weilai cup "2022 Niuke summer multi school training camp 2
E.
tag：NTT, Combinatorial mathematics , Principle of tolerance and exclusion
The question ： The required length is n Appears in the string of k individual bit The number of schemes is x, Then the given value n, Request from 0 To n All correspondences of x The number .
x Yes 998244353 modulus

Ideas ： According to the meaning of the question , Obviously, at most, we can only construct n/3 individual bit, If so, at least k individual bit, So the answer should be 26^n-k*3 * （k individual bit and n-k*3 Number of schemes composed of characters ）, However, there is a need to throw away more than k Circumstances , Because a k+1 One is that it does not conform to the problem k Number of schemes . After deriving the formula, it is found that it becomes two arrays for convolution , utilize ntt Optimize the complexity

PS： It was dented by the previously sorted template . This question debug To make the 2 Hours

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
using namespace std;
const int N=1e6+100;
const int mod=998244353,G=3,Gi=332748118;// Most of the time 
int limit=1,L,r[N<<2];
long long n,m,a[N<<2],b[N<<2],fac[N];
long long fastpow(long long a, long long k)
{
    
	long long res=1ll;
	while(k)
    {
    
		if(k&1)
		{
    
		    res=(res*a)%mod;
		}
		a=(a*a)%mod;
		k>>=1ll;
	}
	return res%mod;
}
void NTT(long long *A,int type,int deg)//NTT The board 
{
    
	for(int i=0;i<limit;i++)
    {
    
        if(i<r[i])
        {
    
            swap(A[i],A[r[i]]);
        }
    }
	for(int mid=1;mid<limit;mid<<=1)
    {
    
		long long Wn=fastpow(type==1?G:Gi,(mod-1)/(mid<<1));
		for(int j=0;j<limit;j+=(mid<<1))
		{
    
			long long w = 1;
			for(int k = 0; k < mid; k++, w = (w * Wn) % mod)
			{
    
				 int x=A[j+k];
                 int y=w*A[j+k+mid]%mod;
				 A[j+k]=(x+y)%mod,
				 A[j+k+mid]=(x-y+mod)%mod;
			}
		}
	}
	if(type==-1)
    {
    
        long long inv =fastpow(limit,mod-2);
	    for(int i=0;i<=limit;i++)
        {
    
           A[i]=(A[i]*inv)%mod;
        }
    }
}
void poly_mul(long long *a,long long *b,int deg)// Polynomial multiplication 
{
    
    while(limit<=deg)
    {
    
        limit<<=1;
        L++;
    }
    for(int i=0;i<limit;i++)
    {
    
        r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
    }
	NTT(a,1,deg);
	NTT(b,1,deg);
	for(int i=0;i<=m*2;i++)
    {
    
        a[i]=(a[i]*b[i])%mod;
    }
	NTT(a,-1,deg);
}
void getfac()
{
    
    fac[0]=1;
    for(int i=1;i<=N;i++)
    {
    
        fac[i]=i*fac[i-1]%mod;
    }
}
int inv(int n)
{
    
    return fastpow(n,mod-2);
}
int C(int n,int m)
{
    
    if(n<m||n<0||m<0)
        return 0;
    return fac[n]*inv(fac[m])%mod*inv(fac[n-m])%mod;
}
int main()
{
    
    fastio
    getfac();
	cin>>n;
	m=n/3;
	for(int i=0;i<=m;i++)
    {
    
        a[i]=1ll*C(n-2*i,i)*fastpow(26,n-3*i)%mod*fac[i]%mod;
        b[i]=1ll*(i&1?mod-1:1)*inv(fac[i])%mod;
    }
    reverse(a,a+m+1);
    poly_mul(a,b,m*2);
    for(int i=m;i>=0;i--)
    {
    
        cout<<a[i]*inv(fac[m-i])%mod<<" ";
    }
    for(int i=m+1;i<=n;i++)
    {
    
        cout<<0<<" ";
    }
	return 0;
}

G
Sign in problem
The question ： Construct a length of n Permutation , Required arrangement val value val=max(LIS,LDS) Minimum .
Ideas ： Divide and divide .
It is not difficult to think of dividing the arrangement into sqrt(n) Block , Each block contains ceil(sqrt(n)) Elements , Output these elements in reverse order to ensure val Value minimization .

#include <bits/stdc++.h>
using namespace std;
int main()
{
    
    int t;
    for(cin>>t;t;t--)
    {
    
        int n;
        cin>>n;
        int m=ceil(sqrt(n));
        int k=n%m;
        for(int i=k;i>=1;i--)
            cout<<i<<" ";
        for(int i=k;i<n;i+=m)
        {
    
           for(int j=i+m;j>=i+1;j--)
               cout<<j<<" ";
        }
        cout<<endl;
    }
    return 0;
}

J

The question ： Construct the given permutation into an arithmetic sequence , And let This value is the smallest . Find the minimum value .（ To six decimal places ）

tag： Linear regression equation , Least squares equation

We will i Regarded as ordinate , take a[i] Regarded as abscissa . Use the formula below to find

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=10007;
ll t,n;
long double a[100005],up,down,avex,avey;
int main(){
    
    scanf("%lld",&t);
    while(t--){
    
        scanf("%lld",&n); avex=avey=up=down=0;
        for(int i=1;i<=n;i++){
    
            scanf("%llf",&a[i]);
            avey+=a[i]*1.0;avex+=i*1.0;
        }
        avex/=n;avey/=n;
        for(int i=1;i<=n;i++){
    
            up+=(i*1.0-avex)*(a[i]-avey);
            down+=(i*1.0-avex)*(i*1.0-avex);
        }
        long double d=up/down;
        long double ax=(avey-d*avex);
        long double sum=0;
        for(int i=1;i<=n;i++){
    
            double x=d*i*1.0+ax-a[i];
            sum+=x*x;
        }
        printf("%.15llf\n",sum);
    }
    system("pause");
    return 0;
}

L
The question ： Given n World and m A little bit , There are different ways of connecting different points in different worlds . From the point of 1 Start , Each step can choose to pass through an edge or stay in place , Then we will go to the next world .
Find out from 1 To m The minimum number of worlds needed .

#include <bits/stdc++.h>
using namespace std;
int n,m,ans;
int main()
{
    
    cin>>n>>m;
    vector<int>pre(m+1,-1e9);
    vector<int>now(m+1,-1e9);
    int ans=1e9+7;
    for(int i=1;i<=n;i++)
    {
    
        int l;
        cin>>l;
        pre[1]=i;
        for(int j=1,u,v;j<=l;j++)
        {
    
            cin>>u>>v;
            now[v]=max(now[v],pre[u]);
            if(v==m)
                ans=min(ans,i-now[v]+1);
        }
        pre=now;
    }
    if (ans>n)
        cout<<"-1"<<endl;
    else
        cout<<ans<<endl;
    return 0;
}