首页 > 网易雷火 4.25笔试
头像
HughLocke
编辑于 2020-04-25 18:37
+ 关注

网易雷火 4.25笔试

第一题
每个视角上每个点挨个判断,每个连通块提供2的贡献
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define LL long long
#define pb push_back
const int maxn = 25;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,S;
vector<int>P[3][maxn][maxn];
int main(){
	scanf("%d",&N);
	for(int i = 1; i <= N ; i ++){
		int x,y,z; scanf("%d%d%d",&x,&y,&z);
		P[0][y][z].pb(x);
		P[1][x][z].pb(y);
		P[2][x][y].pb(z);
	}
	int ans = 0;
	for(int i = 0 ; i < 3; i ++){
		for(int j = 0; j <= 20; j ++){
			for(int k = 0; k <= 20; k ++){
				sort(P[i][j][k].begin(),P[i][j][k].end());
				for(int p = 0 ; p < P[i][j][k].size(); p ++){
				//	printf("%d ",P[i][j][k][p]);
					if(!p || (P[i][j][k][p] != P[i][j][k][p - 1] + 1)) ans += 2;
				}
			}
		}
	//	cout << ans << endl;
	}
	cout << ans << endl;
	return 0;
}

 
第二题
单调栈裸题
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define LL long long
#define PLL pair<long long,long long>
#define pb push_back
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,S;
LL H[maxn];
PLL Que[maxn];
int main(){
	scanf("%d",&N);
	for(int i = 1; i <= N ; i ++) scanf("%lld",&H[i]);
	int top = 0; LL ans = 0;
	for(int i = 1; i <= N ; i ++){
		int tmp = i;
		while(top && Que[top].se >= H[i]){
			ans = max(ans,H[i] * (i - Que[top].fi + 1));
			ans = max(ans,Que[top].se * (i - Que[top].fi));
			tmp = Que[top].fi;
			top--;
			
		}
		Que[++top] = mp(tmp,H[i]);
	} 
	for(int i = 1; i <= top; i ++) 
		ans = max(ans,Que[i].se * (N - Que[i].fi + 1));
	printf("%lld\n",ans);
	return 0;
}

 
第三题
dp[a][b][c][d]表示前b位数字的和为a,最后两位数字是c和d的状态下的最多解
迭代或者dfs地推都可
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define LL long long
#define pb push_back
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1000009; 
int N,M,S,X;
LL dp[500][51][10][10];
LL dfs(int a,int b,int c,int d){
	if(~dp[a][b][c][d]) return dp[a][b][c][d];
	if(a > S){
		dp[a][b][c][d] = 0;
		return 0;
	}
	if(b == N){
		if(a == S){
			dp[a][b][c][d] = 1;
			//cout << c << " " << d << endl;
		} 
		else dp[a][b][c][d] = 0;
		return dp[a][b][c][d];
	}
	dp[a][b][c][d] = 0;
	for(int i = 0 ; i < 10; i ++){
		if(b >= 2 && (i + c * 100 + d * 10) % X != 0) continue;
		dp[a][b][c][d] += dfs(a + i,b + 1,d,i); 
		dp[a][b][c][d] %= mod;
	}
	return dp[a][b][c][d];
}
int main(){
	scanf("%d%d%d",&N,&S,&X);
	memset(dp,-1,sizeof(dp));
	cout << dfs(0,0,0,0) << endl;
	return 0;
}

 


第四题
太麻烦了,急着出门不想写了

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐