黑龙江职业学院校赛第二场(同步赛)

黑龙江职业学院校赛第二场

文章目录
- 题目知识点
- 题目代码
- - A 龙职院卷怪争霸
  - B 最后一个签到还是个字符串基础题
  - C 送你们一个字符串的经典题吧
  - D 交换机
  - E 采购
  - F 字符串
  - G 求素数
  - H 玩游戏
  - I 逛漫展
  - J 面基
结语

文章目录题目知识点

模拟
思维
最短路-dij和fold
素数筛
kmp
并查集
完全背包
离散化

题目代码 A 龙职院卷怪争霸

#include
#include
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
			if(a[i]>a[j]){
				cnt++;
			}
		}
		printf("%lld ",cnt);
	}
	return 0;
}

B 最后一个签到还是个字符串基础题

#include
#include
#include
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
map 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< 
C 送你们一个字符串的经典题吧 
#include
#include
#include
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
		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
		cout< 
D 交换机 
#include
#include
#include
#include
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 mp,vis;
int nz1[maxn],qc1[maxn];
int f[maxn];
int cnt;
void init(){
	for(int i=0;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<
		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<
		ll x;
		scanf("%lld",&x);
		int x1=fd(mp[x]);
		//cout<
			printf("wan");
		}else{
			printf("acn");
		}
	}
	return 0;
}
 
E 采购 
#include
#include
#include
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 字符串 
#include
#include
#include
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 求素数 
#include
#include
#include
#include
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("%dn",dp[m]-dp[n]);
		cout<<(dp[m]-dp[n-1])< 
H 玩游戏 
#include
#include
#include
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
map mp;
ll n;
ll cnt;
int main(){
	cin>>n;
	if(!(n&1)){
		printf("-1");
	}else{
		printf("%lld",n);
	}
	return 0;
}
 
I 逛漫展 
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long int ll;
typedef pair 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
		scanf("%lld",&w[i]);
	}
	memset(dist,0x3f,sizeof(dist));
	for(int i=0;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<
			printf("-1n");
		}
		else
		{
			for(int k=0;k
				if(w[k]>z||vis[k])continue;
				vis[k]=1;
				for(int i=0;i
					for(int j=0;j
						dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
					}
				}
			}
			if(dist[x][y]==inf){
				puts("-1");
			}else{
				printf("%lldn",dist[x][y]);
			}
		}
	}
	return 0;
}
 
J 面基 
#include
#include
#include
#include
#include
using namespace std;
typedef long long int ll;
typedef pair P;
const ll maxn=4e5+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
map mp;
ll m,xa,xb,s;
ll cnt;
struct node{
	ll to,w;
};
vector g[maxn];
priority_queue,greater > 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});
			}
		}
	}
	
	ll dis=d[xb];
	if(d[xb]==inf)printf("-1n");
	else{
		printf("%lldn",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;
}
 
结语 
遇事不决 可问春风
春风不语 即随本心
我若本心能定 怎会遇事不决 春风亦有春风愁 不劳春风为我忧。
自此春风盈满袖，只为一解平安愁

黑龙江职业学院校赛第二场(同步赛)

C/C++/C#相关栏目本月热门文章