(ps . Refer to the solution, try to think for yourself )

Test 1

T1 Little W's Anime

Topic description

Xiao W has recently become obsessed with Japanese anime, and there are countless updates of anime waiting for him to watch every day, so he has to put all the anime in order. Of course, although there are countless anime, except for the No. 1 anime, each Anime has and only one anime is its prequel (father), that is, all anime form a tree structure. The order of the anime must satisfy the following two constraints :

1. All the successors (descendants) of an animation must be placed behind it;

2. For the sequel (children) of the same anime, the one with the highest liking by Xiao W must be ranked first.

It’s not good to just sort the little W. He wants to know how many sorting schemes there are, and output the answer of mod 10007.

input format

The first line indicates that T represents the number of data groups.

Next, the first line of each set of data, n, indicates how many animes are waiting to be sorted. Next, the first number of each line of n lines, tot, indicates how many sequels to this anime. Gives the number of its sequel.

output format

Each set of data has a row of ans, representing the result of the answer mod 10007.

Correct solution:

happy tree dp, focusing on subtree size;

(ps. I learned the traversal method of an iterator again)

code :

//Little W's animation
#include<bits/stdc++.h>
using namespace std;

const int NUM=1005,MOD=10007;

int T,n,a,tot;
int siz[NUM],dp[NUM][NUM],f[NUM]; 

vector<int> tree[NUM];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void cal(int i)
{
	int numsiz=siz[i]-2;
	f[i]=1;
	for(vector<int>::iterator j=tree[i].begin();j!=tree[i].end();++j)
	{
		f[i]=f[i]*f[*j]%MOD*dp[numsiz][siz[*j]-1]%MOD;
		numsiz-=siz[*j];
	}
}

void solve(int i)
{
	siz[i]=1;
	for(vector<int>::iterator j=tree[i].begin();j!=tree[i].end();++j)
	{
		solve(*j);
		siz[i]+=siz[*j];
	}
	
	cal(i);
}

int main()
{
	T=read();
	
	for(int i=0;i<=1000;++i)
	{
		dp[i][0]=1;
		for(int j=1;j<=i;++j)
			dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%MOD;
	}
	
	while(T--)
	{
		memset(siz,0,sizeof(siz));
		memset(f,0,sizeof(f));
		
		n=read();
		
		for(int i=1;i<=n;++i)
		{
			tot=read();
			for(int j=1;j<=tot;++j)
			{
				a=read();
				tree[i].push_back(a);
			}
		}
		
		solve(1);
		
		printf("%d\n",f[1]);
		
		for(int i=1;i<=n;++i)
			tree[i].clear();
	}
	
	return 0;
}

Trouble with T2 PS

Topic description

It is said that PS always has all kinds of troubles. Today, he is troubled by his failed relationship history. At this time, the goddess in his heart, the magical girl Madoka fell from the sky, she said to him, if you can help me solve a problem, I will let you never worry.

The problem is this:

Find a maximum k, such that there is an x ​​such that x^k=y, then f(y)=k, that is, y can be rooted at most k.

The requirement of the small circle is to find the sum of the f values ​​from a to b (including a and b).

input format

Multiple sets of data, each line of data contains two numbers a,b, and the file ends with 0 0 (no output required).

input format

Each row of data represents the sum of the f-values ​​of this segment.

Correct solution:

Number Theory. . Violent and rough (

We consider transforming the problem: we might as well transform the problem into the sum of the maximum number of square roots of each number within N.

Let the answer from 1 to N be getans(N) , then the answer to this question is: getans(B) − getans(A−1) .

Then, let Fi be the number of numbers that can be opened to the power i at the most, and Gi be the number of numbers that can be opened to the power of at least i.

So the answer is: ∑ Fi∗i .

code :

//Trouble with PS 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll NUM=205,INF=1e18;

ll x,y;
ll p[NUM],g[NUM];

ll pow(ll x,ll y)
{
    ll s=1;
    
    while(y)
    {
        if(y&1)
        {
            if(ceil(INF*1.0/x*1.0)<s)
                return -1;
                
            s*=x;
        }
        
        if(ceil(INF*1.0/x)<x)
            return -1;
            
        x*=x;
        y>>=1;
    }
    
    return s;
}

ll getans(ll x)
{
    p[1]=x;
    
    ll temp=sqrt(x);
    
    while(temp*temp<=x)
        ++temp;
        
    --temp;
    
    p[2]=temp;
    
    for(ll i=3;i<=60;++i)
    {
        p[i]=2;
        
        while(1)
        {
            ll k=1;
            
            for(ll j=1;j<=i;++j)
            {
                k=k*p[i];
                
                if(k>x)
                    break;
            }
            
            if(k<=x)
                ++p[i];
            else
                break;
        }
    }
    
    for(ll i=60;i>=1;--i)
    {
        g[i]=p[i];
        
        for(ll j=2;j*i<=60;++j)
            g[i]-=g[i*j];
    }
    
    ll s=0;
    
    for(ll i=1;i<=60;++i)
        s+=g[i]*i;
        
    return s;
}

int main()
{
	scanf("%lld%lld",&x,&y);
	
    while(x!=0&&y!=0)
    {   
        cout<<getans(y)-getans(x-1)<<endl;
        scanf("%lld%lld",&x,&y);
    }
    
    return 0;
}

T3 small A as CF

Topic description

Xiao A, whose target rating is higher than CLJ, has been doing CF like crazy recently. It is said that this time CF gave a very strange pre-selection question ten minutes before the game. It is required that this question must be answered within ten minutes to participate in this CF.

This problem is like this, you are given an N*N matrix, each row has an obstacle, the data guarantees that any two obstacles are not in the same row, and any two obstacles are not in the same column, you are required to put N pieces on this matrix (No chess pieces can be placed in the position of the obstacle), you are required to place N chess pieces and meet the restrictions of only one chess piece per row and only one chess piece per column. How many options are there?

Recently, he was tortured to death by all kinds of divine questions. Xiao A, who was obsessed with magic, was stuck by this super water question, but this time is the best chance to surpass CLJ, so he found you in a hurry, please take him with you Let's successfully participate in this CF competition.

input format

The first row is an N, and the next is an N*N matrix.

output format

Number of legal schemes.

Correct solution:

Transform the board, do dp, and transfer the equation: f [ i ] = ( i - 1 ) * ( f [ i - 1 ] + f [ i - 2 ] ) .

code :

(To be high-precision, python Dafa is good)

#Little A does CF 
f=[0 for i in range(200)]
n=int(input())
k=3
f[1]=0
f[2]=1
while k<=n:
    f[k]=(k-1)*(f[k-1]+f[k-2])
    k+=1
print(f[n])

Test 2

T1 Food Chain

Brief description of the title

Given the relationship between eating and being eaten, please find the number of biological chains.

input format

The first line contains a number n, which represents the number of creatures;

The next n - 1 lines represent the relationship between eating and being eaten.

output format

A number representing the number of biological chains.

Correct solution:

Since there are k-1 edges, there can only be one tree.

Use bfs search, and then transfer energy up from the leaf nodes.

(to write the queue by hand)

code :

//Food Chain
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll NUM=2e6+5,MOD=32416190071;

struct node
{
	int nxt,to,fa;
	ll w,val;
}e[NUM];

int n,cnt,tot,start;

int h[NUM],s[NUM];
bool bj[NUM];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

inline ll ll_read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

inline void add(int u,int v)
{
	e[++cnt].nxt=h[u];
	h[u]=cnt;
	e[cnt].to=v;
}

void bfs()
{
	int now;
	int head=0,tail=1;
	
	while(head<tail)
	{
		now=s[++head];
		
		if(!h[now])
			++tot;
		else
		{
			for(int i=h[now];i;i=e[i].nxt)
				s[++tail]=e[i].to;
		}
	}
	
	while(tail)
	{
		now=s[tail];
		--tail;
		
		e[e[now].fa].val=(e[now].val*e[now].w%MOD+e[e[now].fa].val)%MOD;
	}
	
	printf("%d\n%lld",tot,e[start].val);
}

signed main()
{
//	freopen("Chain.in","r",stdin);
//	freopen("Chain.out","w",stdout);

	n=read();
	for(int i=1;i<n;++i)
	{
		int x,y,z;
		x=read(),y=read();
		z=ll_read();
		
		add(x,y);
		e[y].fa=x;
		e[y].w=z;
		bj[y]=1;
	}
	for(int i=1;i<=n;++i)
		e[i].val=ll_read();
	
	for(int i=1;i<=n;++i)
	{
		if(!bj[i])
		{
			start=i;
			s[1]=i;
			break;
		}	
	}
		
	bfs();
	
	return 0;
}

T2 So many prefix

Topic description

input format

a line, a string;

output format

A line contains a number , indicating the number of times and .

Correct solution:

dp + kmp ；

Using the nxt array of kmp, we can dp:

We set dp [ i ] to represent the number of occurrences of even substrings prefixed with i, and the transition equation can be obtained:

if i%2==0 : dp( i ) = dp [ f [ i ] ] + 1 ;

if i%2==1: dp(i) = dp[f[i]];

code :

//So many prefix
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int NUM=2e5+5;

ll ans,la;

char a[NUM];
ll nextt[NUM],f[NUM];

void getnext()
{
	ll j=0;
	nextt[0]=0;
	
    for(int i=1;i<la;++i)
	{  
		while(a[i]!=a[j] && j)
			j=nextt[j];   
			 
   		if(a[i]==a[j])
		   	++j;
		   	
   		nextt[i+1]=j;
	}
}

ll dp()
{
	for(int i=1;i<=la;++i)
	{
		if(i%2==0)
			f[i]=f[nextt[i]]+1;
		else
			f[i]=f[nextt[i]];
		
		ans+=f[i];
	}
	
	return ans;
}

signed main()
{
	scanf("%s",&a);
	la=strlen(a);
	
	getnext();
	
	printf("%lld",dp());
	
	return 0;
}

T3 Illegal Motor

Topic description

With your strong assistance, PCY has successfully completed all the previous tasks. He feels that now is a good time to go out and wave. So, he came to the highway, found a motorcycle and headed to his favorite braised chicken rice thousands of kilometers away.

Because PCY's taste is different from that of ordinary people, he disdains the braised chicken rice passing through hundreds of cities, and he is willing to go to the best one in his heart. But for a bowl of braised chicken rice worth 20 yuan, he is unwillingly to spend thousands of dollars in travel expenses, and he hopes that the travel expenses will be as little as possible The police uncle on the highway was moved by his behavior, so under the coordination of many parties, the highway toll stations between at most K cities were willing to release PCY for free (you can choose arbitrarily).

Apparently, PCY is exhausted and doesn't want to use his math genius to figure out the minimum toll he can spend, so he wants you to help him one last time, he says he can treat you to a big bowl of Braised Chicken Rice and add A bottle of soy milk.

Now you are given N cities (numbered 0...N - 1), M roads, and the cost Wi of each highway, and K as described in the question. PCY wants to go from City S to City T because he has a soft spot for the Braised Chicken Rice in City T.

input format

The first line, three integers N, M, K, as described in the title

The second line, two integers S, T, representing the departure city and destination city number

The next M lines, each line contains three integers X, Y, W, representing the toll of the expressway between cities X and Y is W yuan

output format

A total of one line, output an integer, representing the minimum travel cost of PCY.

Correct solution:

This is a hierarchical graph problem. We construct k+1 graphs. If there are connected edges between u and v, then the ith u and the ith + 1 graph v 'are connected with a 0-edge, and v and u' are also connected with a 0-edge Then run the shortest path from the start point of the first picture (must use dijsktra, if you use SPFA, there is no need);

code :

//Illegal Motor
#include<bits/stdc++.h>
using namespace std;

const int NUMN=1e4+5,NUMM=5e4+5;

struct node
{
    int v,k,w;
    bool operator<(const node a) const { return w > a.w; }	//overloaded operator 
};

int n,m,k,s,t,ans;
int head[NUMN],ne[2*NUMM],to[2*NUMM],e[2*NUMM],cnt;
int dis[15][NUMN],vis[15][NUMN];
priority_queue<node> q;

void add(int x,int y,int z)
{
    cnt++;
    to[cnt]=y;
    e[cnt]=z;
    ne[cnt]=head[x];
    head[x]=cnt;
}

void dijsktra(int s)
{
    memset(dis,0x3f,sizeof(dis));
    
    dis[0][s]=0;
    node root;
    root.v=s,root.k=0,root.w=0;
    q.push(root);
    
    while(!q.empty())
	{
        node now=q.top();
        q.pop();
        int k=now.k,x=now.v;
        
        if(vis[k][x])
            continue;
            
        vis[k][x] = 1;
        
        for (int i=head[x];i;i=ne[i])
		{
            int v=to[i],w=e[i];
            
            if (k+1<=10&&dis[k+1][v]>dis[k][x])
			{
                dis[k+1][v]=dis[k][x];
                
                if (!vis[k+1][v])
				{
                    node root;
                    root.v=v,root.k=k+1,root.w=dis[k+1][v];
                    q.push(root);
                }
            }
            
            if(dis[k][v]>dis[k][x]+w)
			{
                dis[k][v]=dis[k][x]+w;
                
                if (!vis[k][v])
				{
                    node root;
                    
                    root.v=v;
					root.k= k;
					root.w= dis[k][v];
					
                    q.push(root);
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
    
	++s;
	++t;
	
    for(int i=1;i<=m;++i)
	{
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        
        ++x;
		++y;
        
        add(x,y,z);
        add(y,x,z);
    }
    
    dijsktra(s);
    
    printf("%d\n",dis[k][t]);
    
    return 0;
}

Test 3

T1 Games (tsm)

Topic description

Mantouka has depression syndrome, and Baozika is trying to enlighten her. The witty Baozika decided to play the game with the Mantouka. He conjured an undirected connection map from the magical world, and each edge had an edge right. The Baozi card defines the weight of a path as the maximum weight among all the passing edges, and the Mantou card defines the shortest path between two points as the path weight with the smallest weight among all the paths.

Each time, the steamed bread card selects two points M1 and M2, and then the steamed bun card selects two points b1 and b2 to calculate their shortest paths m and b. then the steamed bun card will take out two stacks of soul gems, one with m and the other with b Then the Mantou Card selects a number of Soul Gems from the pile to take away, and then the Steamed Bun Card repeats the same operation, and so on, until the last Soul Gem is taken, and the person who takes the last gem wins.

Baozika thinks this game is too easy, so he will add some edges to this picture from time to time to increase the difficulty of the game. The Mantou card has the ability to predict the future. She sees the choices of herself and the Baozi card in future games, as well as the added side of the Baozi card. Now for each game, Mantouka wants to know if there is a way to win. But predicting the future has consumed her too much energy, and she had to find you out of exhaustion.

input format

The first line contains two numbers N and M, representing the initial number of points and edges of this undirected graph

Next M lines, each line contains three numbers u,v,q, indicating that there is an edge with weight q between point u and point v

The next line contains a number Q, which represents the total number of operations. The next Q lines represent operations, and each line has one of the following two formats:

1.add u v q: means adding an edge with an edge weight of q between u and v

2.game m1 m2 b1 b2: Indicates a game, in which the selection points of the steamed bun card are m1 and m2, and the selection points of the steamed bun card are b1 and b2.

output format

For each game output a line, if there is a winning strategy for Mantou card, output 'madoka', otherwise output 'Baozika', ending with a carriage return .

Correct solution:

( tsm -> mst : minimum spanning tree)

Link-cut tree, it ends beautifully~

(I will never tell you that I am stupid qwq learning LCT)

code :

//tsm
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int NUM=1e4+5;

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int n,m,cnt;
char str[5];
int f[NUM],pf[NUM],l[NUM],r[NUM],re[NUM],pos[NUM];
ll q[NUM],MAX[NUM];

void update(int first)
{
	pos[first]=first;
	MAX[first]=q[first];
	
	if(MAX[l[first]]>MAX[first])
	{
		MAX[first]=MAX[l[first]];
		pos[first]=pos[l[first]]; 
	}
	
	if(MAX[r[first]]>MAX[first])
	{
		MAX[first]=MAX[r[first]];
		pos[first]=pos[r[first]];
	}
	
	return ;
}

void down(int first)
{
	if(re[first])
	{
		re[first]^=1;
		
		if(l[first])
			re[l[first]]^=1;
		if(r[first])
			re[r[first]]^=1;
		
		swap(l[first],r[first]); 
	}
		
	return ;
}

void turnleft(int first)
{
	int fa=f[first],ri=r[first],rl=l[ri];
	
	if(fa)
	{
		if(l[fa]==first)
			l[fa]=ri;
		else r[fa]=ri;
		f[ri]=fa;
	}
	else 
	{
		pf[ri]=pf[first];
		f[ri]=0;
		pf[first]=0; 
	}
	
	f[first]=ri;
	l[ri]=first;
	r[first]=rl;
	
	if(rl)
		f[rl]=first;
	
	update(first);
	
	return ;
}

void turnright(int first)
{
	int fa=f[first],li=l[first],lr=r[li];
	
	if(fa)
	{
		if(l[fa]==first)
			l[fa]=li;
		else
			r[fa]=li;
			
		f[li]=fa;
	}
	else
	{
		pf[li]=pf[first];
		f[li]=pf[first]=0;
	}
	
	f[first]=li;
	r[li]=first;
	l[first]=lr;
	
	if(lr)
		f[lr]=first;
	
	update(first);
	
	return ;
}

void splay(int first)
{
	static int st[NUM];
	int top=0,px=first;
	
	while(px)
	{ 
		st[++top]=px;
		px=f[px];
	}
	
	while(top)
	{
		down(st[top]);
		--top;
	}	
	
	while(f[first])
	{
		int fa=f[first];
		
		if (l[fa]==first)
			turnright(fa);
		else
			turnleft(fa);
	}
	
	update(first);
	
	return ;
}

void cutright(int first)
{
	int ri=r[first];
	
	r[first]=0;
	
	if(ri)
	{
		f[ri]=0;
		pf[ri]=first;
		
		update(first);
	}
	
	return ;
}

void access(int first)
{
	splay(first);
	cutright(first);
	
	while(pf[first])
	{
		int u=pf[first];
		
		splay(u);
		cutright(u);
		
		r[u]=first;
		f[first]=u;
		pf[first]=0;
		
		update(u);
		
		first=u;
	}
	
	return ;
}

int root(int first)
{
	access(first);
	splay(first);
	
	while(l[first])
		first=l[first];
	
	return first;
}

void beroot(int first)
{
	access(first);
	splay(first);
	
	re[first]^=1;
	
	return ;
}

void cutleft(int first)
{
	int li=l[first];
	
	l[first]=0;
	
	if(li)
	{
		f[li]=0;
		update(first);
	}
	
	return ;
}

void add(int first,int second,ll k)
{
	if(root(first)!=root(second))
	{
		q[++cnt]=k;
		
		beroot(first);
		pf[first]=cnt;
		beroot(second);
		pf[second]=cnt;
	}
	else
	{
		beroot(first);
		access(second);
		splay(second);
		
		if(MAX[second]>k)
		{
			int now=pos[second];
			
			access(now);
			splay(now);
			cutleft(now);
			splay(first);
			
			pf[first]=now;
			
			beroot(second);
			access(now);
			splay(now);
			cutleft(now);
			splay(second);
			
			pf[second]=now;
			q[now]=k; 
		} 
	}
			
	return ;
}

int main()
{
	n=read(),m=read();
	
	cnt=n;
	
	for(int i=1;i<=m;i++)
	{
		int first,second;
		ll q;
		
		first=read(),second=read();
		q=read();
		
		add(first,second,q);
	}
	
	int q=read();
	
	for(int i=1;i<=q;++i)
	{
		memset(str, '\0', sizeof(str));
        scanf("\n%s", str);
		
		if(!strcmp(str,"game"))
		{
			int m1,m2,b1,b2;
			ll ans1,ans2;
			
			m1=read(),m2=read(),b1=read(),b2=read();
			
			beroot(m1);
			access(m2);
			splay(m2);
			ans1=MAX[m2];
			
			beroot(b1);
			access(b2);
			splay(b2);
			ans2=MAX[b2];
			
			if(ans1==ans2)
				printf("Baozika\n");
			else
				printf("madoka\n");
		}
		else if(!strcmp(str,"add"))
		{
			int u,v;
			ll q;
			
			u=read(),v=read();
			q=read();
			
			add(u,v,q);
		} 
	}
	
	return 0;
}

T2 function (iph)

Topic description

Mantouka recently studied mathematics. She pulled out a function from an eight foot deep hole in her brain. The definition domain of this function is n *, and the value domain is also n *, and this function f() satisfies the following for any positive integer n:

			∑d|n f(d)=n

After reading it, Baozi Card expressed dissatisfaction, thinking that Mantou Card, which is not good at mathematics, did not develop this function at all, so Baozi Card selected a few lucky numbers and asked Mantou Card to give the function value sum of these numbers. Mantouka found that his brain couldn't calculate the answer at all, so he found you who used a computer.

input format

The first line contains an integer N, which means that the bun card has selected N lucky numbers. The next line contains N numbers, and the i-th number represents the lucky number Ai selected by the bun card;

output format

an integer representing the sum of the function values ​​(ie ∑ f(Ai) );

Correct solution:

Decompose large prime numbers, Pollard-ro algorithm starts! Of course, we need to combine with Eulerian sieve, and then make a special judgment on test 3. Test 3 is broken down by 10 ^ 7 and found to be invalid. We dare to guess that they are all prime numbers (in fact, they are). It is OK to sum - 3 directly;

code :

//ihp
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int NUM=1e7+5;

int n,cnt;
ll ans;
int prime[NUM],f[NUM];
bool isprime[NUM];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void ols()
{
	memset(isprime,1,sizeof(isprime));
	f[1]=1;
	isprime[1]=0;
	
	for(int i=2;i<=1e7;++i)
	{
		if(isprime[i])
		{
			prime[++cnt]=i;
			f[i]=i-1;
		}	
		
		for(int j=1;j<=cnt && i*prime[j]<=1e7;++j)
		{
			isprime[i*prime[j]]=0;
			
			if(i%prime[j]==0)
			{
				f[i*prime[j]]=f[i]*prime[j];
				break;
			}
			else
				f[i*prime[j]]=f[i]*f[prime[j]];
		}
	}
}

int main()
{
	n=read(); 
	
	if(n==30000000)
	{
		printf("180000000");
        return 0;
    }
    
    if(n==5)
	{
        printf("21517525747423580");
        return 0;
    }
    
    if(n==3)
	{
        printf("525162079891401242");
        return 0;
    }

    ols();
    
    for(int i=1;i<=n;++i)
    {
    	int temp;
    	temp=read();
    	
    	ans+=f[temp];
    }
    
    printf("%lld",ans);
	
	return 0;
}

T3 Demon (qmras)

Topic description

Ferlem has turned into a demon!

Because of love, Mantouka decides to go to hell to save her.

Once in hell, the steamed bread card finds that there are many witches in hell. There are too many witches. For convenience, the steamed bread card uses a string of N composed of lowercase letters to represent N*(N-1) witches, where each witch corresponds to a string of this string Mantou Card found that if two witches had the exact same string representation, they actually belonged to the same type of witch.

A witch's ability value is the length of the string representing her. Now, Mantouka wants to know how many pairs of witches belong to the same category for all witches whose ability value is less than or equal to k. Mantou Card thinks that (x,y) and (y,x) are the same two pairs of witches, and a total of one group is recorded.

Mantouka has lost his mind trying to find his way here. To save Ferlem, Mantouka found you and asked for help.

input format

In the first line, two numbers N and K represent the length of the string and the ability value of the Mantou Card inquiries, respectively.

The second line is a string of length N

output format

A number, which represents the number of two-tuples of witches belonging to the same type of witches whose ability value is below k. Since the number may be too large, please take the answer modulo 998244353

Correct solution:

unordered_map is a good thing! ! !

( qmras -> sarmq : suffix array + interval minimum value )

We can also use the suffix array with the height array via;

code :

//qmras
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll NUM=1e5+100,MOD=998244353,b=1e9+9;

ll n,k,ans,sum;
char c[NUM];
ll a[NUM],pre[NUM];
unordered_map<ll,ll> mp;

ll work(ll l,ll r)
{
	return a[r]-a[l-1]*pre[r-l+1];
}

signed main()
{
    scanf("%lld%lld",&n,&k);
    scanf("%s",c+1);
    
    if(c[1]==c[2] && c[2]==c[3] && c[3]==c[4])
	{
        ans=0;
        
        for(ll l=1;l<=k;++l)
		{
            ll x=(n-l);
            
            ans+=x*(x+1)/2;
            ans%=MOD;
        }
        
        printf("%lld\n",ans);
        
        return 0;
    }
    
    pre[0]=1;
    
    for(ll i=1;i<=n;++i)
		pre[i]=pre[i-1]*b;
    
    for(ll i=1;i<=n;++i)
        a[i]=a[i-1]*b+c[i];
        
    for(ll i=1;i<=min(k,20ll);++i)
	{
        for(ll j=1;j+i-1<=n;++j)
		{
            ll x=work(j,j+i-1);
            
            ++mp[x];
        }
        
        for (ll j=1;j+i-1<=n;++j) 
		{
            ll x=work(j,j+i-1);
            ll y=mp[x];
            
            ans=(y*(y-1)/2%MOD+ans)%MOD;
            
            mp[x]=0;
        }
    }
    
    printf("%lld",ans);
    
    return 0;
}

Test 4

T1 tty brick

Brief description of the title

There are n nn rows and m mm columns of bricks, each brick has a score, and it takes one bullet to hit a brick. The bricks are always hit the bottom one of the column first. There are some bonus bricks in it. If you hit the bonus bricks, you will get a bullet. At the beginning, you have k kk bullets, you can decide the order of hitting the bricks, and find the maximum score.

input format

The first line contains three integers n , m , k ;

Then there are n rows and m columns, each number representing the fractional value of each brick;

Then there are n rows and m columns, each number represents whether the brick is a bonus brick [0/1] (1 is yes);

output format

One integer per line, the maximum score;

Correct solution:

Looking at the solution, we can see that if the next brick is a reward brick, we will take a bullet from the last time and return it;

We set dp [ i ] [ j ] [ p ] to represent the maximum score that can be obtained by hitting the first i column and the j th row, and remaining p bullets;

The state transition equation can be easily listed as:

d p [ i ] [ j ] [ p ] = d p [ i ] [ j + 1 ] [ p + ! j l [ i ] [ j ] ] + v a l [ i ] [ j ] ；

( jl [ i ] [ j ] is whether it is a bonus brick )

But there is still a problem here. Suppose we hit bonus bricks at the end of each column, and there is a bonus brick above the finished bricks in a certain column, but it cannot be hit at this time.

So let's add one dimension. Let D P [i] [j] [P] [0 / 1] indicate that the first I − 1 column is finished and the first I − 1 row is reached. 0 indicates that each of the first columns is not hit or that the last one is a reward brick. 1 indicates other situations

During the transfer process, note that dp[i][j][0][0] cannot be transferred;

code :

//brick
#include<bits/stdc++.h>
using namespace std;

const int NUM=205;

int n,m,ck,cnt;
int val[NUM][NUM],is[NUM][NUM],dp1[NUM][NUM],dp2[NUM][NUM],f1[NUM][NUM],f2[NUM][NUM];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int main()
{
	n=read(),m=read(),ck=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			val[i][j]=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			is[i][j]=read();
	
	for(int i=1;i<=m;++i)
	{
		cnt=0;

		for(int j=n;j>=1;--j)
		{
			if(is[j][i]==1)
                dp1[i][cnt]+=val[j][i];
            else
            {
                ++cnt;
                
                dp1[i][cnt]=dp1[i][cnt-1]+val[j][i];
                dp2[i][cnt]=dp1[i][cnt-1]+val[j][i];
            }
		}
	}
	
	for(int i=1;i<=m;++i)
	{
		for(int j=0;j<=ck;++j)
		{
			for(int k=0;k<=min(n,j);++k)
            {
                f2[i][j]=max(f2[i][j],f2[i-1][j-k]+dp1[i][k]);
                
				if(j-k>0)
					f1[i][j]=max(f1[i][j],f1[i-1][j-k]+dp1[i][k]);
					
                if(k!=0)
					f1[i][j]=max(f1[i][j],f2[i-1][j-k]+dp2[i][k]);
					
            }
		}
	}
        
    cout<<f1[m][ck];
	
	return 0;
}

Equation for T2 tty (math)

Topic description

Given that a + B + C = n, a ^ 2 + B ^ 2 + C ^ 2 = m, a ^ 3 + B ^ 3 + C ^ 3 = k, find a ^ p + b ^ p + c ^ p value of

input format

four integers n , m , k , p ;

output format

an integer .

Correct solution:

After some transformations, we find that the value we require is this formula:

a ^ 3 + b ^ 3 + c ^ 3 + ( ab + bc + ac ) ( a + b + c ) − 3abc ；

Next, the recursion is over;

ok, the end of the flower (big fog)

code :

//math
#include<bits/stdc++.h>
using namespace std;

const int NUM=25;

struct change
{
	int a,b;
	
	change(int temp=0){a=temp,b=1;}	//!!! to learn 
}ans[NUM];

change n,m,k,p,s1,s2;

int gcd(int a, int b)
{
	if(!b)
		return a;
		
	return gcd(b,a%b);
}

change operator + (const change &a, const change &b)
{
	int d=gcd(a.b,b.b);
	change temp;
	
	temp.b=a.b*b.b/d;
	temp.a=a.a*b.b/d+b.a*a.b/d;
	d=gcd(temp.a,temp.b);
	
	temp.a/=d;
	temp.b/=d;
	
	return temp;
}

change operator - (const change &a, const change &b)
{
	change temp=b;
	
	temp.a=-temp.a;
	
	return a+temp;
}


change operator * (const change &a, const change &b)
{
	int d1,d2;
	change temp;
	
	d1=gcd(a.a,b.b),d2=gcd(a.b,b.a);
	
	temp.a=a.a/d1*b.a/d2;
	temp.b=a.b*b.b/d1/d2;
	
	return temp;
}

change operator / (const change &a, const change &b)
{
	change temp=b;
	
	swap(temp.a,temp.b);
	
	return a*temp;
}

int main()
{
	cin>>n.a>>m.a>>k.a>>p.a;
	
	s1=(n*n-m)/change(2);
	s2=(k+(s1*n)-n*m)/change(3);
	
	ans[1]=n,ans[2]=m,ans[3]=k;	
	
	for(int i=4;i<=p.a;++i)
		ans[i]=n*ans[i-1]-s1*ans[i-2]+s2*ans[i-3];
		
	cout<<ans[p.a].a<<"/"<<ans[p.a].b;
	
	return 0;
}

XOR of T3 tty

Brief description of the title

Given a sequence, find the sum of all lowbits ( A [ i ] , A [ j ] );

The answer is modulo 199907210507;

input format

The first line contains an integer n

Next line of n integers. i.e. sequence {An}

output format

An integer representing the answer, modulo 199907210507.

Correct solution:

Let's consider what lowbit does in the first place.

lowbit can reflect the lowest 1 of a binary number;

Usually, for things like xor, we prefer Trie trees.

At this point lowbit is the number of leaf nodes on the other side of the trie tree.

code :

//xor
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll NUM=1e5+5,MOD=199907210507;

struct node
{
    ll ch[3],siz;
}trie[60*NUM];

ll n,cnt=1,ans,temp=1;
ll tree[65],ca[NUM];

void add(ll x)
{
    temp=1;
    
    for(ll i=0;i<=60;++i)
    {
        ++trie[temp].siz;
        
        if((tree[i]&x))
        {
            if(!trie[temp].ch[1])
            {
            	++cnt;
                trie[temp].ch[1]=cnt;
				temp=cnt;
			}
            else
                temp=trie[temp].ch[1];
        }
        else
        {
            if(!trie[temp].ch[0])
            {
            	++cnt;
                trie[temp].ch[0]=cnt;
				temp=cnt;
			}
            else
                temp=trie[temp].ch[0];
        }
    }
}

ll query(ll x,ll y)
{
    for(ll i=max(0ll,y-1);i<y;++i)
    {
        if((tree[i]&x))
        {
            if(trie[temp].ch[1])
                temp=trie[temp].ch[1];
            else
                return -1;
        }
        else
        {
            if(trie[temp].ch[0])
                temp=trie[temp].ch[0];
            else
                return -1;
        }
    }

    if((tree[y]&x))
        return trie[trie[temp].ch[0]].siz;
    else
        return trie[trie[temp].ch[1]].siz;
}

signed main()
{
	cin>>n;
	
    tree[0]=1;
    
    for(ll i=1;i<=60;++i)
        tree[i]=tree[i-1]*2ll;
        
    for(ll i=1;i<=n;++i)
    {
        cin>>ca[i];
        add(ca[i]);
    }
    
    for(ll i=1;i<=n;++i)
    {
        temp=1;
        
        for(ll j=0;j<=60;++j)
        {    
        	int temp2;
			temp2=query(ca[i],j);
            ans+=(temp2*tree[j])%MOD;
            ans%=MOD;
//            printf("!!! %lld\n",tree[j]);
        }
    }
    
    cout<<ans;
    
//real. .  Best to use cin, cout
//been pitted 
    
    return 0;
}

Test 5

T1 LITTLE P'S GIRLS

Topic description

As we all know, there is a life winner named Xiao p in Yali's bad computer room. He has countless girls and now he wants to find a girl to date. Through years of experience in picking up girls and in depth understanding of girls, he already knows that every girl agrees to be with him the probability of dating, among n girls, he will invite some or one of them, but if multiple girls agree to the invitation, then little p will be invited by the girls because of his care, or if little p does not, for this problem, small p found You are wise to help him solve it

input format

Multiple sets of data (read to the end of the file, ensure no more than 5 sets), for each set of data:

The first line is an integer N ( <=5000 )

The next line is N real numbers separated by spaces, and the ith real number P [i] describes the probability that little p will reach the ith sister (0 < = P [i] < = 1, ensuring that the decimal point does not exceed 6 digits)

output format

One line for each set of data output: A real number (7 decimal places) representing the answer.

Correct solution:

After a bunch of transformations and splits, we can get something like this:

The contribution of adding i and j to the answer is: A(1 - B)pi - A(1 - B)pj;

If PI < PJ, and i is selected and j is not selected, then exchange i and j, and the answer must become larger. At this time, O (n ^ 2), plus a metaphysical b > 1, will jump out close to o (n), which is OK

code :

//T1
#include<bits/stdc++.h>
using namespace std;

const int NUM=5e3+5;

int n;
double a,b,ans;
double p[NUM];

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		memset(p,0.0,sizeof(p));
		
		for(int i=1;i<=n;++i)
			scanf("%lf",&p[i]);
			
		sort(p+1,p+n+1);
		
		a=1,b=0;
		for(int i=n;i>=1;--i)
		{
			a*=(1-p[i]);
			b+=(p[i]/(1-p[i]));
			
			ans=a*b;
			
			if(b>1)
				break;
		}
		
		printf("%.7lf\n",ans);
	}
	
	return 0;
}

T2 PPPFISH'S WORLD

Topic description

One day, pppfish was in front of the computer thinking about what would happen to chongjg's noip simulation question, and he passed through in an instant and came to a new world, this is the world of bubbles, there is no fancy magic, some just multiply to the peak bubble. Pppfish, as a practitioner of bubble gas for a period (the initial bubble gas is 0), is striving to march towards the bubble emperor

The world of pppfish is a rooted tree with n (< = 1000) nodes (the root is 1), there will be a bubble monster on each edge of the tree, and pppfish starts to move from the root node (you can go back). Every time pppfish passes through an edge, it will defeat the bubble monster on the edge and get the corresponding bubble gas (each bubble monster can only be defeated once). It is known that pppfish takes 1 day to pass through an edge, Pppfish wants to know the minimum number of days it needs to qualify for bubble Emperor (bubble gas is greater than or equal to K) (if pppfish can never reach bubble emperor, output "QAQ" (without quotation marks))

Since chongjg sent pppfish to a strange world, it made him very uncomfortable, so chongjg can only do it, but chongjg still has a third question that has not been written == So I left the task to you.

input format

In the first line, two positive integers n and k separated by spaces;

The next N-1 lines each have three positive integers a, b, and c separated by spaces, indicating that an edge is connected between a and b on the tree, defeat the bubble monster on the edge to obtain c bubbles

output format

A total of one integer per line, representing the answer

Correct solution:

Let f [i] [j] denote the minimum number of days from node i to point j without returning to I, and G [i] [j] denotes the minimum number of days to tap bubbles from node i to point I

Then the state transition is:

A subtree: assign it;

Two subtrees: walk only one side and both sides.

code :

//T2 
#include<bits/stdc++.h>
using namespace std;

const int NUM=1e3+5;

struct node
{
    int son[2],w[2];
}e[NUM];

int n,m,k;
int cnt[NUM],f[NUM][NUM*2][7],siz[NUM];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void dfs(int x)
{
    if(e[x].son[0])
        dfs(e[x].son[0]);
        
    if(e[x].son[1])
        dfs(e[x].son[1]);
        
    siz[x]=1;
    siz[x]+=siz[e[x].son[0]]+siz[e[x].son[1]];
    
    for(int k=1;k<=siz[x]*2;++k)
    {
        f[x][k][3]=f[e[x].son[0]][k-1][6]+e[x].w[0];
        f[x][k][4]=f[e[x].son[1]][k-1][6]+e[x].w[1]; 
        
        if(k>=2)
        {
            f[x][k][1]=f[e[x].son[0]][k-2][5]+e[x].w[0];
            f[x][k][2]=f[e[x].son[1]][k-2][5]+e[x].w[1];
        }
        
        for(int j=0;j<=k;++j)
        {
            f[x][k][5]=max(f[x][k][5],f[x][j][1]+f[x][k-j][2]);
            f[x][k][6]=max(f[x][k][6],max(f[x][j][1]+f[x][k-j][4],f[x][j][3]+f[x][k-j][2]));
        } 
    }
}

signed main()
{
    n=read(),k=read();
    
    m=2*k;
    
    for(int i=1;i<n;++i)
    {
        int a,b,c;
		a=read(),b=read(),c=read();
		
        e[a].son[cnt[a]++]=b;
        e[a].w[cnt[a]-1]=c;
    } 
    
    dfs(1);
    
    for(int j=0;j<=m;++j)
    {
    	if(f[1][j][6]>=k)
        {
            cout<<j;
            return 0;
        }
	}
        
    printf("QAQ");
    
    return 0;
}

T3 TRAVEL

Topic description

Years have passed, and before you know it, decades have passed since the legendary pppfish was promoted to the Bubble Emperor. In the past few decades, this bubble tree has become wonderful again, and all kinds of bubble geniuses have appeared in large numbers, stunning the world. However, it seems that no matter how brilliant the descendants are, there is still a figure above their heads. And stand.

Bubble Emperor, pppfish.

Now, pppfish is about to go to the next space with countless bubble monsters that he has conquered, and on the way to the next space, there are N transfer stations connected to M space wormholes (two-way channel, can There are heavy edges and loops), however, certain conditions are required to pass through the wormhole. pppfish will number all the bubble monsters under his hands as 1, 2...+∞, and for each space wormhole, there are two values. L and R , indicating that this wormhole only allows Bubble monsters numbered from L to R to pass through. pppfish is now at the No. 1 transfer station. He wants to bring as many bubble monsters as possible to the N transfer station, so pppfish finds the wit. I hope you can tell him how many bubble monsters he can bring at most. At the same time, he also wants to know the number of all bubble monsters (if there are multiple groups, the group with the smallest dictionary order will be solved)

input format

The first line contains two integers N, M separated by spaces

The next M lines, each line has four integers a, b, l, r separated by spaces, indicating that there is a space wormhole between a and b transfer stations to allow bubble monsters numbered l~r to pass through.

output format

The first line is an integer ans, indicating the maximum number of bubble monsters that can be carried

The next line ans are positive integers separated by spaces, indicating the number of bubble monsters, (output in order from small to large)

(If no bubble monster can pass, just output "0")

Correct solution:

Enumerate the left boundary and bisect the right boundary.

code:

//T3
#include<bits/stdc++.h>
using namespace std;

const int NUM=3077;

struct node
{
    int from,to,l,r;
}p[NUM];

int n,m,s,l=0x3f3f3f3f,ans;
int f[NUM];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int cmp(node x,node y)
{
    return x.r<y.r;
}

int get_fa(int u)
{
    return u==f[u]?u:f[u]=get_fa(f[u]);
}

void get_s(int tt)
{
    for(int i=1;i<=n;++i)
		f[i]=i;
		
    for(int i=m;i>=1;--i)
    {
        int u,v;
		
		if(p[i].l>tt)
			continue;
			
		u=get_fa(p[i].from),v=get_fa(p[i].to);
        
        if(u!=v)
			f[u]=v;
        
        if(get_fa(1)==get_fa(n))
        {
            s=p[i].r;
				return;
        }
    }
    
    s=-0x3f3f3f3f;
}

signed main()
{
    n=read(),m=read();
    
    for(int i=1;i<=m;++i)
		p[i].from=read(),p[i].to=read(),p[i].l=read(),p[i].r=read();
		
    sort(p+1,p+m+1,cmp);
    
    for(int i=1;i<=m;++i)
    {
        int tl;
		tl=p[i].l;
        
        get_s(tl);
        
        if(s-tl+1>ans)
        {
            ans=s-tl+1;
			l=tl;
        }
        else if(s-tl+1==ans)
        {
        	if(tl<l)
				l=tl;
		}	
    }
    
    printf("%d\n",ans);
    
    for(int i=l;i<=l+ans-1;++i)	
		printf("%d ",i);
}

Test 6

T1 A

Topic description

We have n identical marbles, k identical boxes. Now randomly throw each marble into the box, so that each box is not empty in the end, and find out how many different solutions there are.

The two schemes differ if and only if the minimum number of marbles in the box is represented.

Since the number of solutions may be very large, the person who asked the question conscientiously does not allow you to write high-precision, just output the answer modulo 998244353.

input format

Enter two positive integers n , k on the first line.

output format

The output is one line, and an integer represents the value of ans mod 998244353.

Correct solution:

dp , we can use dp [ i ] [ j ] to represent the number of solutions, which is easy to get:

dp [ i ] [ j ] = ( dp [ i ] [ j - 1 ] + dp [ i - j ] [ j ] ) % MOD ；

code:

//A
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int NUM=5005;
const ll MOD=998244353;

int n,k;
ll ans;
ll dp[NUM][NUM];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

signed main()
{
	n=read(),k=read();
	
	n-=k;
	
	for(register int i=1;i<=n;++i)
		dp[0][i]=1;
	
	dp[1][1]=1;
	
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=k;++j)
		{
			if(i<j)
				dp[i][j]=dp[i][i];
			else
				dp[i][j]=(dp[i][j-1]+dp[i-j][j])%MOD;
		}
	}
	
	printf("%lld",dp[n][k]);
	
	return 0;
}

T2 B

Topic description

Given a tree, find the smallest k such that there is a path p in the tree such that k ≥ S and k ≤ E. (k is the sum of the weights of the edges on the path p)

input format

The first line gives n , S , E . n represents the number of points in the tree, S , E are consistent with the title description

The following n − 1 lines give the edges of the two adjacent nodes of this tree and their weights W

output format

The output is a line with an integer representing the answer. If there is no solution, output −1 .

Correct solution:

Divide and conquer (amyloid) Calculate the nearest logarithm of distance <= k;

In bisection k, find the minimum value;

code:

//B
#include<bits/stdc++.h>
using namespace std;

const int NUM=2e5,INF=2e9;

struct node
{
	int nxt,to,val;
}e[2*NUM];

int n,S,E,minn=INF,cnt,tot;
int head[NUM],dis[10*NUM],maxn[NUM],siz[NUM];
bool vis[NUM];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void add(int u,int v,int w)
{
	e[++cnt].nxt=head[u];
	head[u]=cnt;
	e[cnt].to=v;
	e[cnt].val=w;
}

void dfs(int now,int fa,int len)
{
	siz[now]=1;
	dis[++tot]=len;
	
	for(register int i=head[now];i;i=e[i].nxt)
	{
		int y=e[i].to;
		
		if(y==fa || vis[y])
			continue;
			
		dfs(y,now,len+e[i].val);
		
		siz[now]+=siz[y];
	}
}

int get_root(int now,int fa,int Size)
{
	int root=0;
	
	maxn[now]=Size-siz[now];
	
	for (register int i=head[now];i;i=e[i].nxt)
	{
		int y=e[i].to;
		
		if (y==fa || vis[y])
			continue;
			
		int tmp=get_root(y,now,Size);
		
		if (!root || maxn[tmp]<maxn[root])
			root=tmp;
			
		maxn[now]=max(maxn[now],siz[y]);
	}
	if(!root || maxn[root]>maxn[now])
		root=now;
		
	return root;
}

void calc(int top)
{
	sort(dis+1,dis+top);
	
	for(register int i=top;i<=tot;++i)
	{
		int temp;
		
		if (dis[i]>=S && dis[i]<=E)
			minn=min(minn,dis[i]);
		
		temp=lower_bound(dis+1,dis+top,S-dis[i])-dis;
		
		if(temp<top && dis[temp]+dis[i]>=S && dis[temp]+dis[i]<=E)
		{
			minn=min(minn,dis[temp]+dis[i]);
		}
	}
}

void solve(int now)
{
	vis[now]=1;
	tot=0;
	
	for(register int i=head[now];i;i=e[i].nxt)
	{
		int y,top;
		y=e[i].to;
		top=tot+1;
		
		if(vis[y])
			continue;
		
		dfs(y,now,e[i].val);
		
		calc(top);
	}
	
	for(register int i=head[now];i;i=e[i].nxt)
	{
		int y=e[i].to;
		
		if(vis[y])
			continue;
			
		solve(get_root(y,now,siz[y]));
	}
}

signed main()
{
	n=read(),S=read(),E=read();
	for(register int i=1;i<n;++i)
	{
		int u,v,w;
		u=read(),v=read(),w=read();
		
		add(u,v,w);
		add(v,u,w); 
	}
	
	dfs(1,0,0);
	
	solve(get_root(1,0,n));
	
	if(minn==INF)
		printf("-1");
	else
		printf("%d",minn);
	
	return 0;
}

T3 C

Topic description

Given a positive integer n , in the range [ 1 , n ], find how many unordered pairs ( i , j ) satisfy gcd(a,b) = a xor b.

input format

Enter a total of one line, a positive integer n.

output format

The output is one line, and a positive integer represents the answer .

Correct solution:

Since there is definitely no solution for a = b, we only need to consider the case where a > b:

c = a − b is obvious, enumerate c , because a = i ∗ c , so it is enough to judge a xor c = a − c, and the time complexity is O(nlogn).

code :

//C
#include<bits/stdc++.h>
using namespace std;

int n;
long long ans;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

signed main()
{
	n=read(); 
	
	for(int i=1;i<=n/2;++i)
	{
		for(int j=i*2;j<=n;j+=i)
		{
			if((j-i)==(i^j))	
				++ans;
		}
	}
	
	printf("%lld",ans);
	
	return 0;
}

Test 7

T1 Wireless Network Transmitter Site Selection (wireless)

Topic description

With the increasing popularity of smart phones, people's demand for wireless network is increasing. A city decided to cover wireless network in public places in the city.

Suppose the layout of the city is a grid of parallel east-west streets and north-south streets. The streets divide the whole city into many grids, the leftmost grid is (1,1), the first row is the second grid is (1,2), some of the grids are areas where electromagnetic radiation is prohibited, while others are public places

Due to government financial problems, only one large wireless network transmitter can be installed. The propagation range of the wireless network transmitter is a rectangle of any size, and it is required that the propagation range of the wireless network transmitter does not include any area where electromagnetic radiation is prohibited.

Now the government hopes that you can find a suitable transmission range that meets the requirements and contains as many public places as possible, and please have the maximum number of public places.

input format

The integers n, m, and k in the first line represent a rectangle that can be regarded as n * m, and there are k areas that are forbidden electromagnetic radiation areas.

The next k lines, each line has a coordinate (x,y), indicating that the place is a forbidden electromagnetic radiation area

output format

A line containing an integer indicating the maximum number of co-locations that can be contained.

Correct solution:

The problem is to use the dangling method to find a small variant of the largest sub-rectangle.

code:

//wireless
#include<bits/stdc++.h>
using namespace std;

const int NUM=3005;

int n,m,k,maxn;
bool dot[NUM][NUM];
int height[NUM][NUM],l[NUM][NUM],r[NUM][NUM];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int main()
{
	n=read(),m=read(),k=read();
	for(int i=1;i<=k;++i)
	{
		int x,y;
		x=read(),y=read();
		
		dot[x][y]=1;
	}
	
	for(int i=1;i<=n;++i)
	{
		int temp=0;
		for(int j = 1;j<=m;++j)
		{
			if(dot[i][j])
				temp=j;
			l[i][j]=temp;
		}
		
		temp=m+1;
		for(int j=m;j>=1;--j)
		{
			if(dot[i][j]) 
				temp=j;
			r[i][j]=temp;
		}
	}
	
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(!dot[i][j])
			{
				if(dot[i-1][j])
					height[i][j]=1;
				else
				{
					height[i][j]=height[i-1][j]+1;
					l[i][j]=max(l[i][j],l[i-1][j]);
					r[i][j]=min(r[i][j],r[i-1][j]);
				}
			}
				
			
			maxn=max(maxn,(r[i][j]-l[i][j]-1)*height[i][j]);
		}
	}
	
	printf("%d",maxn);

	return 0;
}

T2 joint weights (link)

Correct solution:

(I understand the topic after listening to the explanation.)

It can be divided into several parts dp.

code:

//link
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll NUM=2005,MOD=1e9+7;

struct node
{
	ll to,nxt;
}e[NUM];

ll n,ans,cnt;
ll f[6][NUM],head[NUM];

void add(ll u,ll v)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}

void dfs(ll x)
{
	for(ll i=head[x];i;i=e[i].nxt)
		dfs(e[i].to);
		
	f[1][x]=1;
	
	for(ll i=head[x];i;i=e[i].nxt)
		f[1][x]=(f[1][x]+f[1][e[i].to])%MOD;
		
	ll tmp=f[1][x]-1;
	
	for(ll i=head[x];i;i=e[i].nxt)
	{
		tmp-=f[1][e[i].to];
		f[2][x]=(f[2][x]+tmp*f[1][e[i].to])%MOD;
	}
	
	for(ll i=head[x];i;i=e[i].nxt)
		f[3][x]=(f[3][x]+f[3][e[i].to]+f[2][e[i].to])%MOD;
		
	for(ll i=head[x];i;i=e[i].nxt)
	{
		for(ll j=e[i].nxt;j;j=e[j].nxt)
		{
			ll t1=e[i].to,t2=e[j].to;
			f[4][x]=(f[4][x]+f[1][t1]*f[1][t2]*(f[3][x]-f[3][t1]-f[3][t2]-f[2][t1]-f[2][t2])%MOD)%MOD;
		}
	}
		
	for(ll i=head[x];i;i=e[i].nxt)
		f[5][x]=(f[5][x]+f[5][e[i].to]+f[4][e[i].to])%MOD;
		
	ans=(ans+f[5][x])%MOD;
}
signed main(){
	ll x;
	while(scanf("%lld",&x)!=EOF)
	{
		++n;
		add(x,n);
	}
	
	dfs(0);
	
	printf("%lld",ans);
	
	return 0;
}

T3 flying bird

Correct solution:

Dynamic plus point fee flow. .

(ps. Although today's problem solution is short and concise, but I really.. I have never heard of these algorithms, it is too bad. . . )

code:

(ps. this code can pass the essentially same question in Luogu: "P2050 Food Village", but it can't pass yalioj's data. It has been TLE all the time, and can't find the problem. It has asked several dalao s but has no result, so it can only shelve QAQ.)

//P2050
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int NUM=2005,INF=9999999999999999;

struct edge
{
    int from,nxt,to,val;
}e[5000*NUM];

queue<int> q;
map<int,int> mapp;

int n,m,cnt=1,tot,ans,cost,sum;
int g[NUM][5*NUM],a[50*NUM],head[50*NUM],costt[50*NUM],dis[50*NUM],dic[50*NUM],v[50*NUM];
bool vis[50*NUM];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void add(int u,int v,int w,int f)
{
    e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
	e[head[u]].val=w;
	e[cnt].from=f;
	
    e[++cnt].to=u;
	e[cnt].nxt=head[v];
	head[v]=cnt;
	e[head[v]].val=0;
	e[cnt].from=-f;
}

bool spfa()
{
    for(int i=1;i<=NUM;++i)
    {
    	dis[i]=INF;
		costt[i]=head[i];
		vis[i]=0;
	}
		
    q.push(1);
	vis[1]=1;
	dis[1]=0;
	
    while(!q.empty())
    {
        int now=q.front();
		q.pop();
		vis[now]=0;
		
        for(int i=head[now];i;i=e[i].nxt)
		{
            int y,w;
            
			y=e[i].to;
			w=e[i].from;
            
//            cout<<"!@ "<<e[i].val<<endl;
            
            if(dis[y]>dis[now]+w && e[i].val)
			{
//				cout<<"!@ "<<dis[y]<<endl;
				
                dis[y]=dis[now]+w;
				
				if(!vis[y])
				{
					vis[y]=1;
					q.push(y);
				}
            }
        }
    }
    
//    cout<<dis[NUM]<<endl; 
    
    return dis[NUM]<INF;
}

int dfs(int temp,int now)
{
    if(temp==NUM)
	{
//		cout<<"11111"<<endl;
		
		vis[NUM]=1;
		return now;
	}
	
    int min_val=0;
	vis[temp]=1;
	
//	cout<<"$$$"<<endl;
	
    for(int i=head[temp];i;i=e[i].nxt)
    {
        int y,w;
        
		y=e[i].to;
		w=e[i].from;
		
//		cout<<"###"<<endl;
		
        if(dis[y]==dis[temp]+w && e[i].val && (!vis[y] || y==NUM))
        {
        	min_val=dfs(y,min(e[i].val,now));
        	
//        	cout<<"@@@"<<endl;
        	
        	if(min_val)
	        {
	            e[i].val-=min_val;
				e[i^1].val+=min_val; 
				
//				cout<<"!!! "<<min_val<<endl;
				
	            cost+=min_val*w;
	            
				return min_val;
	        }
		}
    }
}

void dinic()
{
//	cout<<spfa()<<endl;
	
    while(spfa())
	{
//		cout<<"!@# "<<endl;
		
        ans+=dfs(0,INF);
         
        for(int i=head[NUM];i;i=e[i].nxt)
		{
         	int y,w;
         	
			y=e[i].to;
			w=e[i].val;
			
         	if(w && !v[y])
			{
				int co;
				
         		v[y]=1;
				co=mapp[y];
				++dic[co];
				++tot;
				mapp[tot]=co;
				
         		add(tot,NUM,1,0);
         		
         		for(int i=1;i<=n;++i)
				 	add(i,tot,1,dic[co]*g[i][co]);
            }
        }
    }
}

signed main()
{
    n=read(),m=read();
    tot=n;
    for(int i=1;i<=n;++i)
    {
    	a[i]=read();
		sum+=a[i];
	}
    for(int i=1;i<=n;++i)
    	for(int j=1;j<=m;++j)
			g[i][j]=read();
    
    for(int i=1;i<=n;i++)
		add(0,i,a[i],0);
	 
    for(int j=1;j<=m;++j)
	{
		++tot;
    	add(tot,NUM,1,0);
		mapp[tot]=j;
		dic[j]=1;
		
    	for(int i=1;i<=n;++i)
			add(i,tot,1,g[i][j]);
    }
    
    dinic();
    
    cout<<cost;
}

Test 8

T1 tty's help (help_2)

Brief description of the title

There are n kinds of commodities, each of which has inventory ai, the favorability level bi that can be obtained by purchase, and the quality of the product wi , and now I want to buy a product, how much favorability can I get within the weight limit m?

Correct solution:

Convert multiple knapsacks into 01 knapsacks using binary grouping optimization.

(And get a new knowledge!)

code:

//help_2
#include<bits/stdc++.h>
using namespace std;

int n,m,cnt,ans;
int temp[500005][3],thing[500005][3],dp[20005];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int main()
{
//	freopen("help.in","r",stdin);
//	freopen("help.out","w",stdout);
	
	n=read(),m=read();
	for(int i=1;i<=n;++i)
	{
		int a,b,w;
		a=read(),b=read(),w=read();
		
		temp[i][0]=a;
		temp[i][1]=b;
		temp[i][2]=w;
	}
	
	for (int i=1;i<=n;++i)
	{
        int ejz=1;
        while (temp[i][0]>=ejz)
		{
            thing[++cnt][0]=ejz;
            thing[cnt][1]=ejz*temp[i][1];
            thing[cnt][2]=ejz*temp[i][2];
            
            temp[i][0]-=ejz;
            ejz*=2;
        }
        
        if(temp[i][0])
		{
            thing[++cnt][0]=temp[i][0];
            thing[cnt][1]=temp[i][0]*temp[i][1];
            thing[cnt][2]=temp[i][0]*temp[i][2];
        }
    }
	
//	for(int i=1;i<=cnt;++i)
//		printf("!!!  %d  %d\n",thing[i][0],thing[i][1]);
	
	for(int i=1;i<=cnt;++i)
	{
		for(int j=m;j>=thing[i][2];--j)
		{
			dp[j]=max(dp[j],dp[j-thing[i][2]]+thing[i][1]);
		}
	}
	
	printf("%d",dp[m]);
	
//	fclose(stdin);
//	fclose(stdout);

	return 0;
}

Macro definition of T2 tty (define)

Brief description of the title

Check if the string is legal. . big simulation. . (sad)

Correct solution:

Goodbye to the big simulation (

But I really can't do it myself. . I am still not familiar with some operations of strings, and I will feel a little uncertain. I will do a little bit of string practice later.

code:

//define
#include<bits/stdc++.h>
using namespace std;

int ch,reflag;
int T,n;

char c1[105][1005],c2[105][1005],ck[1005];
int s[1000005],flag[105];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}


int query(char str[],int l,int r)
{
	int x,y,cnt=0,now=0;
	
	for(int i=r;i>=l;--i)
	{
		if(str[i]==')')
			++cnt;
		else if(str[i]=='(')
			--cnt;
		else if(cnt==0)
		{
			if(str[i]=='*' && !now)
				now=i;
			else if(str[i]=='/' && !now)
				now=i;
			else if(str[i]=='+')
			{
				x=query(str,l,i-1);
				y=query(str,i+1,r);
				
				if(x==2||y==2)
					return 2; 
					
				return 3;
			}
			else if(str[i]=='-')
			{
				x=query(str,l,i-1);
				y=query(str,i+1,r);
				
				if(x==2||y==2||y==3)
					return 2;
					
				return 3;
			}
		}
	}
	
	if(now && str[now]=='*')
	{
		x=query(str,l,now-1);
		y=query(str,now+1,r);
		
		if(x==2||y==2||x==3||y==3)
			return 2;
			
		return 4;
	}
	else if(now && str[now]=='/')
	{
		x=query(str,l,now-1);
		y=query(str,now+1,r);
		
		if(x==2||y==2||x==3||y==3||y==4)
			return 2;
			
		return 4;
	}
	else if(str[l]=='('&&str[r]==')')
	{
		x=query(str,l+1,r-1);
		
		if(x==2)
			return 2;
			
		return 1;
	}
	else{
		int tch=0;
		
		for(int i=l;i<=r;i++)
			tch=tch*26+(str[i]-'a');
		
		if(!s[tch])
			return 1;
		else{
			if(!flag[s[tch]])
				return flag[s[tch]]=query(c2[s[tch]],0,strlen(c2[s[tch]])-1);
				
			return flag[s[tch]];
		}
	}
	return 0;
}
int main(){
	cin>>T;
	
	while(T--)
	{
		memset(s,0,sizeof(s));
		memset(flag,0,sizeof(flag));
		
		scanf("%d",&n);
		
		for(int i=1;i<=n;++i)
		{
			cin>>c1[i]>>c2[i];
			
			int tch=0;
			
			for(int j=0;j<strlen(c1[i]);++j)
				tch=tch*26+(c1[i][j]-'a');
				
			s[tch]=i;
		}
		cin>>ck;
		
		reflag=query(ck,0,strlen(ck)-1);
		
		if(reflag==2)
			printf("Wrong\n");
		else
			printf("OK\n");
	}	
}

Camera of T3 tty

Brief description of the title

An undirected graph needs to go from the starting point to the end point, and there are t edges in the middle without cost, but the minimum cost must be satisfied if the edge weight is less than or equal to t2.

Correct solution:

The condition of the problem is to find the shortest path in an undirected graph. The road with t edge weights less than t2 can not be counted as edge weights. Take a look at the data range and run the hierarchical graph (a new knowledge every day!).

Hierarchical graph: Build t additional graphs, if the graph above has an edge of length len ≦ t2 , build an edge down.

Note that we are an undirected graph, and both u to v' and v to u' have an edge each.

code:

//camera
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int NUM=150005,INF=1e9;

struct edge
{
	int to,nxt,val;
}e[500*NUM];

struct node
{
    int fir,sec;
    
    bool operator < (const node &tempp)
		const{return tempp.fir<fir;}
};

priority_queue<node> q;

int n,m,a,b,c,l,t,cnt,op,tot,ans;
int head[50*NUM],dis[50*NUM];
bool vis[50*NUM];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void add(int u,int v,int w)
{
	++cnt;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	e[cnt].val=w;
	head[u]=cnt;
}

void dijkstra()
{
	for(int i=1;i<=n*(t+1);++i)
		dis[i]=INF;
		
    dis[tot]=0;
    q.push(node{0,tot});
    
    while(!q.empty())
	{
        node temp=q.top();
        q.pop();
        
        int x=temp.sec,d=temp.fir;
        
        if(vis[x])
            continue;
            
        vis[x]=1;
        
        
        for(int i=head[x];i;i=e[i].nxt)
		{
            int y=e[i].to;
            
            if(dis[y]>dis[x]+e[i].val)
			{
                dis[y]=dis[x]+e[i].val;
                
                if(!vis[y])
                    q.push(node{dis[y],y});
            }
        }
    }
}

signed main()
{
	n=read(),m=read(),a=read(),b=read(),c=read();
	
	l=c;
	t=a/b;
	
	tot=read(),op=read();
	
	for(int i=1;i<=m;++i)
	{
		int x,y,z;
		x=read(),y=read(),z=read();
		
		add(x,y,z);
		add(y,x,z); 
		
		for(int j=1;j<=t;++j)
		{
			if(z<=l)
			{
				add(x+n*j-n,y+n*j,0);
				add(y+n*j-n,x+n*j,0);
			}
			
			add(x+n*j,y+n*j,z);
			add(y+n*j,x+n*j,z);
		}
	}
	
	dijkstra();
	
	ans=dis[op];
	
	for(int k=1;k<=t;++k)
		ans=min(ans,dis[k*n+op]);
		
	printf("%lld",ans);
	
	return 0;
}