本来第一题题目太长看着很恶心，写完后三道之后剩十几分钟准备来随便写写骗点分，没想到贪心一下竟然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) 回帖