The second match of Heilongjiang Vocational College (synchronized match)

List of articles

Topic knowledge

• simulation
• thinking
• shortest path -dij and fold
• Prime sieve
• kmp
• Union checking set
• Completely backpack
• discretization

Title code

A The Dragon Vocational College competes for supremacy

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
ll n;
ll a[maxn];
int main(){
    
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
    
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
    
		ll cnt=0;
		for(int j=1;j<i;j++){
    
			if(a[i]>a[j]){
    
				cnt++;
			}
		}
		printf("%lld ",cnt);
	}
	return 0;
}

B Last sign in It is also a basic string problem

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
map<string,ll> mp;
ll n;
ll cnt;
int main(){
    
	cin>>n;
	for(int i=1;i<=n;i++){
    
		string s;
		cin>>s;
		if(!mp[s]){
    
			cnt++;
		}
		mp[s]++;
	}
	cout<<cnt<<endl;
	return 0;
}

C Send you a classic question of the string

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
const ll maxn=1e6+10;
string t;
ll nex[maxn];
ll n;
void getnex(){
    
	ll j=0,k=-1;
	nex[0]=-1;
	ll len=t.size();
	while(j<len){
    
		if(k==-1||t[j]==t[k]){
    
			j++;
			k++;
			nex[j]=k;
		}else{
    
			k=nex[k];
		}
	}
}
int main(){
    
	cin>>t;
	getnex();
	for(int i=1;i<t.size()+1;i++){
    
		cout<<nex[i]<<" ";
	}
	return 0;
}

D Switch

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long int ll;
const int maxm=1e6+5;
const int maxn=1e6+10;
int n,nz,qc,q,z;
map<ll,int> mp,vis;
int nz1[maxn],qc1[maxn];
int f[maxn];
int cnt;
void init(){
    
	for(int i=0;i<maxn;i++){
    
		f[i]=i;
	}
}
int fd(int x){
    
	if(x==f[x])return x;
	return f[x]=fd(f[x]);
}
int main(){
    
	init();
	scanf("%d%d%d%d%d",&n,&nz,&qc,&z,&q);
	for(int i=1;i<=n;i++){
    
		ll x;
		scanf("%lld",&x);
		mp[x]=i;
	}
	//cout<<q<<endl;
	for(int i=1;i<=nz;i++){
    
		ll x;
		scanf("%lld",&x);
		nz1[i]=mp[x];
	}
	for(int i=1;i<=qc;i++){
    
		ll x;
		scanf("%lld",&x);
		qc1[i]=mp[x];
	}
	for(int i=1;i<=z;i++){
    
		ll x,y;
		scanf("%lld%lld",&x,&y);
		int x1=fd(mp[x]);
		int y1=fd(mp[y]);
		if(x1!=y1){
    
			f[x1]=y1;
		}
	}
	for(int i=1;i<=qc;i++){
    
		int x1=fd(qc1[i]);
		vis[x1]=1;
		//cout<<x1<<" ";
	}
	
	while(q--){
    
		ll x;
		scanf("%lld",&x);
		int x1=fd(mp[x]);
		//cout<<x1<<endl;
		if(vis[x1]){
    
			printf("wa\n");
		}else{
    
			printf("ac\n");
		}
	}
	return 0;
}

E purchase

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
ll n,v;
ll t[maxn],w[maxn];
ll f[maxn];
int main(){
    
	scanf("%lld%lld",&n,&v);
	for(int i=1;i<=n;i++){
    
		scanf("%lld%lld",&t[i],&w[i]);
	}
	for(int i=1;i<=n;i++){
    
		for(int j=t[i];j<=v;j++){
    
			f[j]=max(f[j],f[j-t[i]]+w[i]);
		}
	}
	cout<<f[v];
	return 0;
}

F character string

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
string s,t;
int main(){
    
	cin>>s;
	cin>>t;
	if(s.find(t)==string::npos){
    
		cout<<"NO";
	}else{
    
		cout<<"YES";
	}
	return 0;
}

G Find prime number

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long int ll;
const int maxm=1e7;
const int maxn=1e8;
int t;
int n,m;
int dp[maxn];
bool v[maxn];
int pri[maxm];
int cn;
void pr()
{
    
	dp[1]=0;
	v[1]=1;
	for(int i=2;i<=maxn;i++){
    
		if(!v[i]){
    
			pri[++cn]=i;
			v[i]=false;
			dp[i]=dp[i-1]+1;
		}else{
    
			dp[i]=dp[i-1];
		}
		for(int j=1;j<=cn&&(i*pri[j]<=maxn);j++){
    
			v[pri[j]*i]=true;
			if(i%pri[j]==0)break;
		}
	}
}
int main(){
    
	pr();
	//scanf("%d",&t);
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--){
    
		//scanf("%d%d",&n,&m);
		cin>>n>>m;
		//printf("%d\n",dp[m]-dp[n]);
		cout<<(dp[m]-dp[n-1])<<endl;
	}
	return 0;
}

H Play a game

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
map<string,ll> mp;
ll n;
ll cnt;
int main(){
    
	cin>>n;
	if(!(n&1)){
    
		printf("-1");
	}else{
    
		printf("%lld",n);
	}
	return 0;
}

I Rambling Exhibition

#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const ll maxn=300;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll n,m,q;
ll w[maxn];
ll dist[maxn][maxn];
ll vis[maxn];
int main(){
    
	scanf("%lld%lld%lld",&n,&m,&q);
	for(int i=0;i<n;i++){
    
		scanf("%lld",&w[i]);
	}
	memset(dist,0x3f,sizeof(dist));
	for(int i=0;i<n;i++){
    
		dist[i][i]=0;
	}
	for(int i=1;i<=m;i++){
    
		ll x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		dist[x][y]=min(dist[x][y],z);
		dist[y][x]=min(dist[y][x],z);
	}
	while(q--){
    
		ll x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		//cout<<w[x]<<" "<<w[y]<<endl;
		if(z<w[x]||z<w[y])
		{
    
			printf("-1\n");
		}
		else
		{
    
			for(int k=0;k<n;k++){
    
				if(w[k]>z||vis[k])continue;
				vis[k]=1;
				for(int i=0;i<n;i++){
    
					for(int j=0;j<n;j++){
    
						dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
					}
				}
			}
			if(dist[x][y]==inf){
    
				puts("-1");
			}else{
    
				printf("%lld\n",dist[x][y]);
			}
		}
	}
	return 0;
}

J Face base

#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<stdio.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const ll maxn=4e5+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
map<ll,ll> mp;
ll m,xa,xb,s;
ll cnt;
struct node{
    
	ll to,w;
};
vector<node> g[maxn];
priority_queue<P,vector<P>,greater<P> > que;
ll d[maxn];
ll vis[maxn];
void dij(){
    
	for(int i=0;i<=cnt;i++) d[i]=inf; d[xa]=0; que.push({
      0,xa}); while(!que.empty()){
       P p=que.top(); que.pop(); ll u=p.second; if(vis[u])continue; vis[u]=1; for(auto i:g[u]){
       if(d[i.to]>(d[u]+i.w)){
    
				d[i.to]=d[u]+i.w;
				que.push({
    d[i.to],i.to});
			}
		}
	}
	/*for(int i=1;i<=cnt;i++){ cout<<d[i]<<" "; } cout<<endl;*/
	ll dis=d[xb];
	if(d[xb]==inf)printf("-1\n");
	else{
    
		printf("%lld\n",dis/s+(dis%s!=0));
	}
}
int main(){
    
	scanf("%lld%lld%lld%lld",&m,&xa,&xb,&s);
	if(!mp[xa]){
    
		cnt++;
		mp[xa]=cnt;
	}
	if(!mp[xb]){
    
		cnt++;
		mp[xb]=cnt;
	}
	for(int i=1;i<=m;i++){
    
		ll x,y,l,w;
		scanf("%lld%lld%lld%lld",&x,&y,&l,&w);
		if(!mp[x]){
    
			cnt++;
			mp[x]=cnt;
		}
		if(!mp[y]){
    
			cnt++;
			mp[y]=cnt;
		}	
		if(w==1){
    
			g[mp[x]].push_back({
    mp[y],l});
		}else if(w==2){
    
			g[mp[x]].push_back({
    mp[y],l});
			g[mp[y]].push_back({
    mp[x],l});
		}
	}
	xa=mp[xa];
	xb=mp[xb];
	dij();
	return 0;
}

Conclusion

• Never decide Ask the spring breeze
• The spring breeze is silent That is, follow your heart
• If my heart can settle How can you not make up your mind when you are in trouble Spring breeze also has spring breeze sorrow Don't worry about me .
• Since then, the spring breeze has filled my sleeves , Just for the sake of peace