首页 > 网易8.12 ac代码
头像
牛客691621789号
编辑于 2020-08-13 11:24
+ 关注

网易8.12 ac代码

本来第一题题目太长看着很恶心,写完后三道之后剩十几分钟准备来随便写写骗点分,没想到贪心一下竟然ac了???好快乐啊

第一题
#include<iostream>
#include<string.h>
#include<stack>
#include<vector>
#include<stdio.h> 
using namespace std;

int main()
{
	int T, N;
	cin >> T;
    int visited[10];
    int cnt[128];
    vector<string> arr(7);
	while(T--)
    {
        memset(visited, 0, sizeof(visited));
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < 7; ++i)
        {
            cin >> arr[i];
        }
        int index, index2;
        bool flag = true;
        for(int i = 0; i < 7; ++i)
        {
            index = arr[i][0] - '0';
            index2 = arr[i][1];
            ++cnt[index2];
            if(visited[index]) flag = false;
            visited[index] = 1;
        }
        if(cnt['T'] >= 4 || cnt['B'] >= 4 || cnt['W'] >= 4) flag = false;
        if(flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

第二题
#include<iostream>
#include<vector>
#include<string.h>
#include<set>
using namespace std;

int arr[501][501];
int main()
{
	int n;
	cin >> n;
	memset(arr, 0, sizeof(arr));
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= n; ++j)
		{
			cin >> arr[i][j];
		}
	}
	vector<int> row(n + 1), col(n + 1);
	for(int i = 1; i <= n; ++i)
	{
		int sum1 = 0, sum2 = 0;
		for(int j = 1; j <= n; ++j) sum1 += arr[i][j], sum2 += arr[j][i];
		row[i] = sum1;
		col[i] = sum2;
	}
	int ei, ej, total;
	vector<int> rowv(n + 1);
	vector<int> colv(n + 1);
	set<int> rows, cols;
	int x, y, xx, yy;
	for(int i = 1; i <= n; ++i) rows.insert(i), cols.insert(i);
	for(int k = 1; k <= n; ++k)
	{
		x = 0, y = 0, total = -1;
		for(auto i : rows)
		{
			++x;
			y = 0;
			for(auto j : cols)
			{
				++y;
				int tmp = row[i] + col[j] - arr[i][j];
				if(total < tmp){
					xx = x;
					yy = y;
					ei = i;
					ej = j;
					total = tmp;
				}
			}
		}
		// 处理十字
		rows.erase(ei);
		cols.erase(ej);
		for(int i = 1; i <= n; ++i) col[i] -= arr[ei][i];
		for(int i = 1; i <= n; ++i) row[i] -= arr[i][ej];
		cout << xx << " " << yy << endl; 
	}
}


// 19:51

第三题
#include<iostream>
#include<string.h>
#include<stack>
#include<vector>
#include<stdio.h> 
using namespace std;

const int maxn = 100001;
int t[maxn];
int e[maxn];
int s[maxn];
int main()
{
	int T, N;
	cin >> T;
	while(T--)
	{
		// init
		memset(t, 0, sizeof(t));
		memset(e, 0, sizeof(e));
//		memset(s, 0, sizeof(s));
		//begin
		cin >> N;
		int dummy, total;
		int ans = -1;
        if(N == 0) return 0;
		for(int i = 0; i < N; ++i) cin >> t[i] >> e[i] >> dummy;
		stack<vector<int> > s;
		int cost = 0, res = 0xfffffff;
		for(int i = 0; i < N; ++i)
		{
			if(s.empty()){
				cost = 0;
				s.push({e[i], 0, i});
			}
			else{
				auto p = s.top();
				if(p[0] == e[i]){
					total = t[i] - t[p[2]];
//					cout << " total - cost " << total - cost << endl;
					if(ans < total - cost || ((ans == total - cost) && res > e[i]) ){
						ans = total - cost;
						res = e[i];
					}
					s.pop();
					cost = total + p[1];
				}
				else{
					s.push({e[i], cost, i});
					cost = 0;
				}
			}
		}
		cout << res << endl;
	}
}


第四题
这题代码写的很乱,一开始以为是找到一个目标之后就一直走过去,后来才发现是每走一步都会判断一次
#include<iostream>
#include<string.h>
#include<stack>
#include<vector>
#include<stdio.h> 
#include<queue>
#include<string>
using namespace std;

	int xxx[4] = {-1, 1, 0, 0}, yyy[4] = {0, 0, -1, 1};
const int maxn = 100001;
int arr[55][55];
int visited[55][55];
int mht[10][55][55];
int dis[10][55][55];

void bfs(int mx, int my)
{
	int st = arr[mx][my];
	memset(visited, 0, sizeof(visited));
	queue<vector<int> > q;
	visited[mx][my] = 1;
	q.push({mx, my, 0});
	while(!q.empty())
	{
		auto p = q.front();
		q.pop();
		int x = p[0], y = p[1], d= p[2];
		dis[st][x][y] = d;
		mht[st][x][y] = abs(x - mx) + abs(y - my);
		++d;
		for(int i = 0; i < 4; ++i)
		{
			int xx = x + xxx[i], yy = y + yyy[i];
			if(arr[xx][yy] != -1 && !visited[xx][yy]){
				visited[xx][yy] = 1;
				q.push({xx, yy, d});
			}
		}
	}
}
int main()
{
	int T, m, n, stx, sty, stv;
	cin >> T;
	char ch;
	while(T--)
	{
		memset(arr, -1, sizeof(arr));
		memset(mht, 0, sizeof(mht));
		memset(dis, -1, sizeof(dis));
		vector<pair<int,int> > pos; 
		cin >> m >> n;
		string tmp;
		for(int i = 1; i <= m; ++i)
		{
			cin >> tmp;
			for(int j = 1; j <= n; ++j)
			{
				ch = tmp[j - 1];
				if(ch == '*'){
					arr[i][j] = 10;
					stx = i, sty = j;
				}
				else if(ch == '.') arr[i][j] = 11;
				else if(ch != '#'){
					arr[i][j] = ch - '0';
					pos.push_back({i, j});
				}
			}
		}
		// 计算马曼哈顿和最短距离
		int len = pos.size(), x1, x2, y1, y2, v1, v2, d;
		for(int i = 0; i < len; ++i)
		{
			x1 = pos[i].first, y1 = pos[i].second;
			bfs(x1, y1);
		}
		int total = len, target, cnt = total;
		vector<bool> found(total);
		stv = 10;
		int m = 0xffff, ans = 0;
		int x = stx, y = sty;
				memset(visited, 0, sizeof(visited));
		while(cnt)
		{
			visited[x][y] = 1;
			m = 0xffff;
			target = -1;
			//找到要目标 
			for(int i = 0; i < total; ++i)
			{
				if(!found[i] && mht[i][x][y] < m){
					target = i;
					m = mht[i][x][y];
				}
			}
			//开始走路
			m = dis[target][x][y];
			if(m == -1) break;
			for(int i = 0; i < 4; ++i)
			{
				if(arr[x + xxx[i]][y + yyy[i]] != -1 && dis[target][x + xxx[i]][y + yyy[i]] < m){
					x += xxx[i];
					y += yyy[i];
					break;
				}
			}
			++ans;
			if(visited[x][y]) break;
			if(dis[target][x][y] == -1) break; 
			if(arr[x][y] == target){
				memset(visited, 0, sizeof(visited));
				found[target] = 1;
				--cnt;
			}
		}
		if(cnt) cout << -1 << endl;
		else cout << ans << endl;
	}
	
}

// 21:40





全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐