Links: Login - Professional IT Written Interview Reference Platform_ Niuke
Source: Niuke.com
 

Now you'll give a square map with an n-side length. There are empty places on the map and enemies in some places.

Now we have a chance to bomb the enemy. The area to bomb the enemy is a square area of k*k. The problem you need to solve now is to calculate the maximum number of enemies to bomb. (

Enter a description:

This topic contains multiple sets of data, with two numbers n, k entered in the first row of each set.
The next n rows, each with n numbers, represent the number of enemies at this point.
Data Range:
1<=n<=50
1<=k<=n
 There are no more than 100 enemies at each point (0<=a[i][j]<=100).

Output description:

Each set of data outputs contains a row representing the result of the calculation.

Example 1

input

4 2 1 1 0 0 1 1 0 0 0 0 2 2 0 0 2 2

4 2
1 1 0 0
1 1 0 0
0 0 2 2
0 0 2 2

output

8

8

Explain

In the example, it is clear that bombing the lower right corner will defeat the most enemies

Water topic: Small amount of data, suggest direct violence or consider prefix and

//The feature is that they are all square, read the pictures first
//Read in the diagram, then iterate through it, saving the results in an array, and then putting the values in a queue First pop-up with higher priority queue values
//But it's just a walk through how emmm is implemented in code?
//The second idea is a two-dimensional prefix and
#include <bits/stdc++.h>
using namespace std;
int n,k;
int a[110][110];
int main(){
	int n,k;
	while(cin>>n>>k){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>a[i][j];
		}
	}
	long long ans=0;
	for(int i=0;i<n-k+1;i++){//Violence traversal (small amount of data) Note condition i<n-k+1 
		for(int j=0;j<n-k+1;j++){
		long long  cnt=0;
		for(int x=i;x<i+k;++x){
			for(int y=j;y<j+k;++y)
				cnt+=a[x][y];
		}	
		ans=max(cnt,ans);
		}
	}
	cout<<ans<<endl;}
}

​
#include <bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int a[N][N];
int main(){
	int n,k,t,ans=-1;
	while(cin>>n>>k){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cin>>a[i][j];
				a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
			}
		}//Save an Entire Graph 
		for(int i=k;i<=n;i++){
			for(int j=k;j<=n;j++){
				t=a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k];
				ans=max(t,ans);
			}
		}//The area of the graph enclosed by n and k is prefixed with 
		cout<<ans<<endl;
		ans=-1;
		memset(a,0,sizeof(a));
	}
}

​

Standard one-dimensional prefixes and expressions

Standard two-dimensional prefixes and expressions

 

Application of prefix sum

An array a of length n, Q queries, one l, r for each query, sum the intervals [l, r]. Time limit 1.00s 1 <= n, Q <= 1e5; 1 <= L <= R <= n; 0 <= a I <= 1e9.for (int I = l; I <= r; I ++) ans += a[i]; Calculate a[l] + a[l+1] +... each time you ask If a [r-1] + a [r], the time complexity will reach O (q*n) after Q queries. O(q*n) apparently TLE

Prefixes and what's useful? (

If the prefixes and sums described above are used, the sum of the intervals [l, r] and the preceding r terms can be obtained within the time of O(1) and the preceding L-1 items can be subtracted and a[l]+a[l+1]+... + A[r-1]+a[r] = sum[r]-sum[l-1]; (

The prefix and sum are preprocessed in advance, so only one calculation is needed for each query.

ans = PrefixSum[r] – PrefixSum[l - 1];

The time complexity is reduced to O(n+q).

Prefix sum is an important preprocessing that greatly reduces query time complexity

string can slow down code

Links: Login - Professional IT Written Interview Reference Platform_ Niuke
Source: Niuke.com
 

Title Description

Small W is calculating an array column {An}, where A1=1,A2=2,An+2=An+1+An. Although his calculations were very accurate, he soon confused his draft paper and found out some of the results of his calculations, but he forgot which of the columns they were.

Enter a description:

Each row contains an Ak (k<=100000) in a number of columns.

Total rows T<=30.

Output description:

For each Ak, the output line includes a positive integer k to indicate which item in the input is the number of columns.

Example 1

input

2 3 5 8 13

2
3
5
8
13

output

2 3 4 5 6

2
3
4
5
6

#include <bits/stdc++.h>
using namespace std;
long long a[100005];
int main(){
	a[0]=1;
	a[1]=2;
	for(int i=2;i<100000;i++){
		a[i]=a[i-1]+a[i-2];
	}
	string num;
	while(cin>>num){
		long long t=0;
		for(int i=0;i<num.length();i++){
			t=t*10+(num[i]-'0');
		
		}	for(int i=0;i<100000;i++){
						if(a[i]==t){
							cout<<i+1<<endl;
							break;	}
            }
	}
	return 0;
}

The map question applies to an idea of Union and collection

Or it can be simulated directly

Links: Login - Professional IT Written Interview Reference Platform_ Niuke
Source: Niuke.com
 

Title Description

おみやげをまらいました! 

The frog still brought you a gift. But it has one small requirement: you have to win it on the stone scissors cloth to get the gift! (

You specify that there are three strings S1,S2,S3S_1, S_2, S_3S1, S2, S3, representing three types of fists, of which S1S_1S1. Can beat S2S_2S2, S2S_2S2. Can beat S3S_3S3, S3S_3S3. Can beat S1S_1S1.

Now, from your observation, you know the order in which the frog wants to punch. You need to arrange your own order so that you can win every game.

"Shao [124],"[12], "[12],"[Fu], "[12],"[12], "...

Enter a description:

The first three lines have two strings per line, Sa,SbS_a, S_bSa, Sb, for SaS_aSa. Can beat SbS_bSb. (
The data is guaranteed not to contradict each other, and there are exactly three different strings. (
Next, a number of NNNNNs represent NNN battles. (
The next NNN line contains a string for each line, indicating the type of fist a frog takes. Note that the frog's fist may not be legal (that is, it is not one of the three strings), then output "Fake"\texttt{Fake"}"Fake".

Output description:

There are NNN lines, one string per line, indicating what you need in each round. (
If the opponent makes an illegal offer, output "Fake"\texttt{Fake"}"Fake".

Example 1

input

stone sci sci paper paper stone 4 stone sci spock paper

stone sci
sci paper
paper stone
4
stone
sci
spock
paper

output

paper stone Fake sci

paper
stone
Fake
sci

Remarks:

2≤∣S∣≤502 \leq |S| \leq 502≤∣S∣≤50

1≤N≤1001 \leq N \leq 1001≤N≤100

 

//The first impression was to think about and collect the idea that who can open three trees and who can win who is the father
//Discuss according to the situation and make a logical and non-logical judgement.
//Optimize for mapping with map<string,string>
//Or it could be direct violence, because you only need to compare three
#include <bits/stdc++.h>
using namespace std;
map<string,string> f;
int main()
{
	string a,b;
	for(int i=0;i<3;i++){
		cin>>a>>b;
		f[b]=a;
	}
	int n;
	cin>>n;
	string t;
	for(int i=0;i<n;i++){
		cin>>t;
		if(f.find(t)==f.end()){
			cout<<"Fake"<<endl;
		}
		else{
			cout<<f[t]<<endl;
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main() {
    string s1, s2, s3;
    string temp;
    cin >> s1 >> s2 >> temp >> s3 >> temp>>temp;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        if (s == s1) {
            cout << s3 << endl;
            continue;
        }
        else if (s == s2) {
            cout << s1 << endl;
            continue;
        }
        else if (s == s3) {
            cout << s2 << endl;
            continue;
        }
        else {
            cout << "Fake" << endl;
            continue;
        }
 
    }
    return 0;}

I am a chicken.

Probably the next day after serious study.

Last question:

Raceway construction:

Method: Binary+Tree+dfs

The diameter of a tree

1. Basic concepts

Simple path: All points on the path are visited at most once.

Tree diameter: The longest simple path on a tree.

Simply put, define a tree whose diameter is .

There are two common ways to find the diameter of a tree, two DFS and two DP trees.

Tree DP is difficult to record diameter paths and endpoints, and the advantages of time complexity are too limited to understand, so this article only introduces the former.

2. Twice DFS diameters

2.1 Algorithmic Ideas

1 From any point P, find the farthest point Q from it through DFS.

Second, starting from point Q, find the farthest W from it through DFS.

(3) The diameter is WQ.

2.2 Reference Code

dfs code

#include<bits/stdc++.h>
using namespace std;
vector<int>edge[100005];
int vis[100005];
int dis[100005];
void dfs(int st)
{
    for(int i=0;i<edge[st].size();i++)
    {
        int to=edge[st][i];
        if(!vis[to])
        {
            vis[to]=1;
            dis[to]=dis[st]+1;//Note that this code calculates the diameter of an unweighted tree, so the edge weight is 1
            //If you have a right tree, then 1 here will change to edge right
            dfs(to);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;//n points
    for(int i=1;i<=n-1;i++)//Because it's a tree, it has n-1 edges
    {
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);//Undirected graph storage, use structure if you have a right tree
    }
    dfs(1);//From 1 dfs side
    int maxlen=0,Q,W,ans=0;
    for(int i=1;i<=n;i++)
    {
        if(dis[i]>maxlen) maxlen=dis[i],Q=i;
        dis[i]=vis[i]=0;
    }//Find an end point of the diameter Q
    dfs(Q);//Start from Q
    for(int i=1;i<=n;i++)
        if(dis[i]>ans) ans=dis[i],W=i;//Find another end point W and get the diameter length
    return 0;
}

Links: Login - Professional IT Written Interview Reference Platform_ Niuke
Source: Niuke.com
 

City C will host a series of racing competitions. Before the competition, it is necessary to build a track in the city.
There are 1,2,..., 1 bidirectional road suitable for the construction of a race track. Each road connects two intersections. Among them, the two intersections connected by the Dixie road are numbered as the Dixie Road ai and ai_ bi, the length of the road is_ li. With this 1 road, you can get to all the other intersections from any intersection.
A track is a distinct set of roads 1, 2,...,, _ 1, _ 2,..., _ , e1, e2,..., ek, satisfy can start from an intersection, pass through road 1, 2,..., _ 1, _ 2,..., _ E1, e2,..., EK (once per road, no turning around is allowed) arrives at another intersection. The length of a track equals the sum of the lengths of the roads it passes through. For safety, at most one track is required to pass each road.
Currently, the plan for the construction of the track has not been determined. Your task is to design a scheme for the construction of a track so that the shortest length of the track is the longest (that is, the shortest track in the track is the longest possible).

Enter a description:

The first line of the input file contains two positive integers separated by spaces, which represent the number of intersections and the number of tracks that need to be built.
Next line 1, line contains three positive integers, _, _, _, _ , _ , _ , ai, bi, li means the number of the two intersections and the length of the road for which the section is suitable for the construction of a track. Ensure that any two intersections can reach each other through this 1 road. Each row is separated by a space between adjacent numbers.

Output description:

The output is a row containing an integer representing the maximum length of the track with the minimum length.

Example 1

input

7 1 1 2 10 1 3 5 2 4 9 2 5 8 3 6 6 3 7 7

7 1
1 2 10
1 3 5
2 4 9
2 5 8
3 6 6
3 7 7

output

31

31

Remarks:

2 <= n <= 50000, 1 <= m <= n - 1, 1 <= ai, bi <= n, 1 <= li <= 10000

Tree Diameter+Binary+Multset Ordered multiset
(You can actually switch multiset to vector s, but that's slower)

First, the diameter of the tree is calculated by using the tree DP (or two DFS) as the right boundary r of the dichotomy. The shortest edge of a tree as the left half boundary l
The length of the shortest dichotomous track mid=(l+r)/2
check(mid) function to determine if there are at least m race tracks with length >=mid

How to judge?
Point 1 is used as the root node (any point can be selected as the root node), and it is recursive to the subtree dfs from the leaf node up.

For instance:
Assume the current node is x and one of its children is y. Edge length of x,y is w, dfs(y,x,k) denotes the length of the longest chain connected to y less than mid in a subtree rooted in Y
If dfs(y, x, k)+w>=mid then ans+.
Otherwise add the length of this join x chain to the multiset set set
(Because it is possible for this chain to be longer than or equal to the other chains that connect x, this also explains why dfs() always returns less than mid)

Next, deal with the chains in the s set:
Find the shortest one. Because this set is sorted from small to large, find the chain to which s.begin() points.
Reuse lower_bound looks for the first chain of length >= (mid-*s.begin()).
If such two chains exist, the two chains can be paired (length sum >=mid), ans++, and the two numbers deleted.
Otherwise, the longest chain whose length is less than mid is continuously updated, and this value is returned.
 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50050,inf=1e9;
int n,m,head[N],tot=0,ans=0;
int d[N],v[N];
multiset<int>s[N];
multiset<int>::iterator it;
struct edge{
	int ver,to,w;
}e[N*2];

void add(int x,int y,int z){
	e[++tot].ver=y;
	e[tot].w=z; 
	e[tot].to=head[x];
	head[x]=tot;
}
int dfs(int x,int pre,int k){
	s[x].clear();
	int now;
	for(int i=head[x];i;i=e[i].to)
	{
		int y=e[i].ver;
		if(y==pre)continue;
		now=e[i].w+dfs(y,x,k);
		if(now>=k)ans++;
		else{
		s[x].insert(now);	
		}
    }
    int maxi=0;
    while(!s[x].empty()){
       if(s[x].size()==1){
      return max(maxi,*s[x].begin());
	   }
       it=s[x].lower_bound(k-*s[x].begin());
       if(it==s[x].begin()&&s[x].count(*it)==1){ it++;}
       if(it==s[x].end()){
       	maxi=max(maxi,*s[x].begin());
       	s[x].erase(s[x].begin());
	   }
	   else{
	   	ans++;
	    s[x].erase(it);
	    s[x].erase(s[x].begin());
	   }
	}
	return maxi;
}
int check(int k){
    ans=0;
    dfs(1,0,k);
    if(ans>=m)return 1;
    return 0;
}
int up=0;
void dp(int x){
	v[x]=1;
	for(int i=head[x];i;i=e[i].to){
		int y=e[i].ver;
		if(v[y])continue;
		dp(y);
		up=max(up,d[x]+d[y]+e[i].w);
	    d[x]=max(d[x],d[y]+e[i].w);
	}
}
int main(){
	cin>>n>>m;
	int x,y,z,l=inf,r=0,mid,res;
	for(int i=1;i<n;i++)
    {
      cin>>x>>y>>z;
      if(z<l)l=z;
      add(x,y,z);
      add(y,x,z);
	}
	dp(1);
	r=up; 
    while(l<=r){
    	int mid=l+(r-l)/2;
    	if(check(mid)){
    		res=mid;
    		l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	cout<<res;
	return 0;
}