竞赛讨论区 > 牛客挑战赛60 B题数据有锅
头像
sigland
编辑于 2022-05-13 22:41
+ 关注

牛客挑战赛60 B题数据有锅

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v,x) for(auto v:x)
#define all(x) (x).begin(), (x).end()
#define VI vector<int>
#define VLL vector<ll>
#define pll pair<ll, ll>
#define double long double
//#define int long long
using namespace std;

#ifdef LOCAL
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
	cerr << " " << to_string(H);
	debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 2050;
const int inf = 1e9;
//const ll inf = 1e18;
const ll mod = 998244353;//1e9 + 7;

int n, m, k;

int vis[N][N];
pii a[N * N];

void sol()
{
	cin >> n >> m >> k;
	n <<= 1, m <<= 1;
	for(int i = 0; i <= n; i++)
		for(int j = 0; j<= m; j++)
			vis[i][j] = 0;
	for(int i = 1; i <= k; i++)
		cin >> a[i].fi >> a[i].sc;
	k = min(k, 3000);
	for(int i = 1; i <= k; i++)
		a[i].fi <<= 1, a[i].sc <<= 1;
	for(int i = 1; i <= k; i++)
	{
		for(int j = i + 1; j <= k; j++)
		{
			++vis[(a[i].fi + a[j].fi) / 2][(a[i].sc + a[j].sc) / 2];
		}
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(vis[i][j] >= 2)
			{
				cout << "YES ";
				cout << fixed << setprecision(1) << 1.0 * i / 2 << ' ' << 1.0 * j / 2 << '\n';
				return;
			}
		}
	}
	cout << "NO" << '\n';
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt;
	cin >> tt;
	while(tt--)
		sol();
}

spj有问题,上面这个做法如果在得到最早可行的解直接break出来会判对,但是这样最后扫一遍的写法就会判错(有些是答案的点被判成不是答案了)。
直接break:(AC)
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v,x) for(auto v:x)
#define all(x) (x).begin(), (x).end()
#define VI vector<int>
#define VLL vector<ll>
#define pll pair<ll, ll>
#define double long double
//#define int long long
using namespace std;

#ifdef LOCAL
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
	cerr << " " << to_string(H);
	debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 2050;
const int inf = 1e9;
//const ll inf = 1e18;
const ll mod = 998244353;//1e9 + 7;

int n, m, k;

int vis[N][N];
pii a[N * N];

void sol()
{
	cin >> n >> m >> k;
	n <<= 1, m <<= 1;
	for(int i = 0; i <= n; i++)
		for(int j = 0; j<= m; j++)
			vis[i][j] = 0;
	for(int i = 1; i <= k; i++)
		cin >> a[i].fi >> a[i].sc;
	k = min(k, 3000);
	for(int i = 1; i <= k; i++)
		a[i].fi <<= 1, a[i].sc <<= 1;
    int x = 0, y = 0;
	for(int i = 1; i <= k; i++)
	{
		for(int j = i + 1; j <= k; j++)
		{
			++vis[(a[i].fi + a[j].fi) / 2][(a[i].sc + a[j].sc) / 2];
			x = (a[i].fi + a[j].fi) / 2;
			y = (a[i].sc + a[j].sc) / 2;
			if(vis[x][y] > 1)
			{
				break;
			}
		}
		if(vis[x][y] > 1)
			break;
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(vis[i][j] >= 2)
			{
				cout << "YES ";
				cout << fixed << setprecision(1) << 1.0 * i / 2 << ' ' << 1.0 * j / 2 << '\n';
				return;
			}
		}
	}
	cout << "NO" << '\n';
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt;
	cin >> tt;
	while(tt--)
		sol();
}
出题人谢罪

全部评论

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

等你来战

查看全部

热门推荐