比赛链接:http://hihocoder.com/contest/hihointerview26
A.排序后枚举两个点,确定一个矩形后二分剩下两个点。
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int maxn = ;
typedef struct Point {
int x, y;
Point() {}
Point(int xx, int yy) : x(xx), y(yy) {}
}Point;
int n;
LL ans;
Point p[maxn]; bool cmp(Point a, Point b) {
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
} bool bs(int x, int y) {
int ll = , rr = n, mm;
while(ll <= rr) {
mm = (ll + rr) >> ;
if(p[mm].x == x && p[mm].y == y) return ;
else if(cmp(p[mm], Point(x, y))) ll = mm + ;
else rr = mm - ; }
return ;
} int main() {
// freopen("in", "r", stdin);
int x3, y3, x4, y4;
while(~scanf("%d", &n) && n) {
ans = 1000000LL * 1001000LL;
for(int i = ; i < n; i++) {
scanf("%d%d", &p[i].x, &p[i].y);
}
sort(p, p+n, cmp);
for(int i = ; i < n; i++) {
for(int j = i + ; j < n; j++) {
x3 = p[i].x; y3 = p[j].y;
x4 = p[j].x; y4 = p[i].y;
if(bs(x3, y3) && bs(x4, y4)) {
int a = x3 - x4;
int b = y3 - y4;
if((LL)a * b == ) continue;
ans = min(ans, abs((LL)a*b));
}
}
}
printf("%lld\n", ans == 1000000LL * 1001000LL ? - : ans);
}
return ;
}
B.按题要求爆搜
#include <bits/stdc++.h>
using namespace std; const int maxn = ;
int n;
set<string> ret;
set<string>::iterator it;
int num[maxn];
set<int> pos; int main() {
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
for(int i = ; i < maxn; i++) num[i] = i;
while(~scanf("%d", &n)) {
ret.clear();
do {
int nn = ( << (n));
for(int i = ; i < nn; i++) {
pos.clear();
int tmp = i;
int cnt = ;
while(tmp) {
if(tmp & ) pos.insert(cnt+);
tmp >>= ; cnt++;
}
string t = "";
bool ex = ;
t += (num[] + '');
int pre = num[];
for(int i = ; i <= n; i++) {
if(ex) break;
if(pos.find(i) != pos.end()) {
t += '-';
pre = -;
}
if(pre > num[i]) {
ex = ;
break;
}
t += (num[i] + '');
pre = num[i];
}
if(!ex) ret.insert(t);
}
// for(int i = 1; i <= n; i++) printf("%d", num[i]);
// printf("\n");
}while(next_permutation(num+, num+n+));
// printf("%d\n", ret.size());
for(it = ret.begin(); it != ret.end(); it++) {
cout << *it << endl;
}
}
return ;
}
C.找到规律后斯特灵数胡搞(好像没必要?)
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int maxn = ;
const LL mod = 1000000007LL;
LL f[maxn], a[maxn];
LL S[maxn][maxn];
int n; LL exgcd(LL a, LL b, LL &x, LL &y) {
if(b == ) {
x = ;
y = ;
return a;
}
else {
LL ret = exgcd(b, a%b, x, y);
LL tmp = x;
x = y;
y = tmp - a / b * y;
return ret;
}
} LL inv(LL a) {
LL x, y;
exgcd(a, mod, x, y);
return (x % mod + mod) % mod;
} LL C(LL n, LL m) {
return f[n] * inv(f[m]) % mod * inv(f[n-m]) % mod;
} LL mul(LL x, LL n) {
LL ret = ;
while(n) {
if(n & ) ret = ret * x % mod;
n >>= ;
x = x * x % mod;
}
return ret;
} int main() {
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
memset(S, , sizeof(S));
S[][] = ;
for(int p = ; p < maxn; p++) {
for(int k = ; k < maxn; k++) {
S[p][k] = (LL)k * S[p-][k] % mod + S[p-][k-] % mod;
}
}
f[] = ;
for(int i = ; i < maxn; i++) {
f[i] = f[i-] * (LL)i % mod;
}
memset(a, , sizeof(a));
a[] = ; a[] = ;
for(int i = ; i <= ; i++) {
for(int k = ; k <= i; k++) {
a[i] = (a[i] + f[k] * S[i][k] % mod) % mod;
}
}
while(~scanf("%d", &n)) {
printf("%lld\n", a[n]);
}
return ;
}