【每日一题】 UVA - 1587 Box 二维有点偏序的感觉

一开始用set存xjb分类讨论,然后wa,

然后简化了一点,改用vector,然wa

最后又发现没有初始化,然wa

wa了一个半小时

最后看了题解orz

然后找了一组样例把自己的代码改对了

/*

1 1
1 1
1 1
1 1
1 2
1 2

*/

正统题解:不妨设三条边为a<=b<=c, 那么对每个面(边对)sort后,必然得到 ab ab ac ac bc bc 然后照着这个序列写六个判断就好了orz

#define _CRT_SECURE_NO_WARNINGS
#include<cmath>
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<stack>
#include<vector>
#include<string.h>
#include<queue>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define rep(i,t,n) for(int i =(t);i<=(n);++i)
#define per(i,n,t) for(int i =(n);i>=(t);--i)
#define mmm(a,b) memset(a,b,sizeof(a))
#define eps 1e-6
#define pb push_back #define mp make_pair
#define x first
#define y second
pair<int, int> a[];
int main() {
while (cin >> a[].x >> a[].y){ rep(i, , )scanf("%d%d", &a[i].x, &a[i].y);
rep(i, , )if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
sort(a + , a + );
puts(a[] == a[] && a[] == a[] && a[] == a[] && a[].x==a[].x&&a[].y==a[].y&&a[].x==a[].y?"POSSIBLE":"IMPOSSIBLE"); }
}
/*
POSSIBLE
IMPOSSIBLE
*/

第一版代码,先判每个面出现了两遍,再把不同的三个面找出来,按有几个面是正方形分类

#define _CRT_SECURE_NO_WARNINGS
#include <cmath>
#include <iostream>
#include <stdio.h>
#include<algorithm>
#include <map>
#include <cstring>
#include <time.h>
#include <string>
#include <vector>
#include <set>
using namespace std;
#define rep(i,t,n) for(int i =(t);i<=(n);++i)
#define per(i,n,t) for(int i =(n);i>=(t);--i)
#define mmm(a,b) memset(a,b,sizeof(a))
const double pi = acos(-1.0);
const int maxn = + ;
int n,m; int main()
{ int x, y; while (cin >> x >> y){
set<int> S[];
vector < set<int>> V;
S[].insert(x), S[].insert(y);
rep(i, , ) { cin >> x >> y;
S[i].insert(x), S[i].insert(y);
}
int f[];
mmm(f, );
int vis[]; mmm(vis, );
rep(i, , )rep(j, , )if (i != j) {
if (S[i] == S[j]) { f[i] = ; if (!vis[i]&&!vis[j]) { V.push_back(S[i]); vis[j] = ; vis[i] = ;} }
}
rep(i, , )if (!f[i]) { f[] = ; }
if (f[] == ) { puts("IMPOSSIBLE"); continue; }
int cnt=;
rep(i, , )if (V[i].size() == )cnt++;
if (cnt == ) { if (V[] == V[] && V[] == V[]) puts("POSSIBLE"); else puts("IMPOSSIBLE"); continue; }
if (cnt == ) {
vector < set<int>> T;
for (auto t : V)if (t.size() == ) { T.push_back(t); }
if(*T.begin()==*T.rbegin()) { puts("POSSIBLE"); continue; }else { puts("IMPOSSIBLE"); continue; }
}
if(cnt==) { puts("IMPOSSIBLE"); continue; }
if (cnt == ) {
int ok = ;
vector < int> T;
rep(i, , )if (*V[].begin() == *V[i].begin())T.push_back(*V[i].rbegin());
else if (*V[].begin() == *V[i].rbegin())T.push_back(*V[i].begin());
rep(i, , )if (*V[].rbegin() == *V[i].begin())T.push_back(*V[i].rbegin());
else if (*V[].rbegin() == *V[i].rbegin())T.push_back(*V[i].begin());
//else ok = 0;
if(T.size()!=){ puts("IMPOSSIBLE"); continue; }
if(T.front()!=T.back()) { puts("IMPOSSIBLE"); continue; }
else { puts("POSSIBLE"); continue; }
}
}
cin >> n;
return ;
}
/* 1 1
2 1
2 1
1 1
1 1
1 1
*/

第二版代码:用vector存,并且简化了分类:要么可以 要么不可能//废话

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
#define rep(i,t,n) for(int i =(t);i<=(n);++i)
#define per(i,n,t) for(int i =(n);i>=(t);--i)
#define mmm(a,b) memset(a,b,sizeof(a))
int main()
{ int x, y;
while (cin >> x >> y) {
vector < vector<int>> V;
vector<int> v[];
if (x > y)swap(x, y);
v[].push_back(x); v[].push_back(y);
rep(i, , ) { cin >> x >> y;
if (x > y)swap(x, y);
v[i].push_back(x); v[i].push_back(y);
}
int f[]; int vis[]; mmm(vis, );
mmm(f, );
rep(i, , )rep(j, , )if (i != j) {
if (v[i] == v[j]) { f[i] = ; if (!vis[i]&&!vis[j]) { V.push_back(v[i]); vis[j] = ; vis[i] = ;} }
}
rep(i, , )if (!f[i]) { f[] = ; }
if (f[] == ) { puts("IMPOSSIBLE"); continue; }
int ok = ;
int t = ;
int x = ;
if (V[].front() == V[].front())t = V[].back(); else if (V[].front() == V[].back())t = V[].front(); else {
x = ;
if (V[].front() == V[].front())t = V[].back(); else if (V[].front() == V[].back())t = V[].front(); else ok = ;
}
int t2 = ;
if (t == V[x].front())t2 = V[x].back(); else if (t == V[x].back())t2 = V[x].front(); else {
ok = ;
}
if (t2 != V[].back())ok = ;
if (ok)puts("POSSIBLE");
else puts("IMPOSSIBLE");
}
return ;
}
上一篇:css3简单介绍


下一篇:Redis需要多少内存预留-内存占用多少才安全