1001： 食物链（poj1182），直接贴代码，稍作可过
并查集
//
// main.cpp
// 携程1
//
// Created by zhang on 14-4-11.
// Copyright (c) 2014年 apple. All rights reserved.
// #include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional> using namespace std;
const int maxk=;
int N,K;
int D[maxk],X[maxk],Y[maxk];
int par[*maxk],rankh[*maxk]; void init(int n)
{
for(int i=;i<n;i++)
{
par[i]=i;
rankh[i]=;
}
}
int find(int x)
{
if (par[x]==x)
{
return x;
}
else return par[x]=find(par[x]);
} void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y) return; if(rankh[x]<rankh[y])
{
par[x]=y;
}
else
{
par[y]=x;
if(rankh[x]==rankh[y]) rankh[x]++;
}
} bool same(int x,int y)
{
return find(x)==find(y);
} int main()
{
//freopen("Users/apple/Desktop/携程1/携程1.in","r",stdin);
//freopen("Users/apple/Desktop/携程1/携程1.out","w",stdout);
int T;
scanf("%d",&T);
while (T--) { scanf("%d%d",&N,&K);
init(*N);
for(int i=;i<K;i++)
{
scanf("%d %d %d",&D[i],&X[i],&Y[i]);
} int ans=;
for(int i=;i<K;i++)
{
int t=D[i];
int x=X[i]-,y=Y[i]-; if(x<||N<=x||y<||N<=y)
{
ans++;
continue;
}
if(t==)
{
if(same(x,y+N)||same(x,y+*N))
{
ans++;
}
else
{
unite(x,y);
unite(x+N,y+N);
unite(x+*N,y+*N);
}
}
else
{
if (same(x,y)||same(x,y+*N))
ans++;
else
{
unite(x,y+N);
unite(x+N,y+*N);
unite(x+*N,y);
}
}
} printf("%d\n",ans);
}
return ;
}
1001
1002： dp[i][j] 表示第一条边为i, 第二条边的长度为 j 是否可行。 然后对所有可行的三条边的组合求最大三角形面积即可。
三角形面积：海伦公式
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath> using namespace std; const int INF = ;
const int MAXL = ;
const int MAXN = ; int n;
int a[MAXN];
int ans;
bool dp[MAXL][MAXL]; int my_abs(int x) {
return x > ? x : -x;
} double Area(double x, double y, double z) {
double p = (x+y+z)/;
return sqrt(p*(p-x)*(p-y)*(p-z));
} bool check(int x, int y, int z) {
int t[] = {x, y, z};
sort(t, t+);
if (t[]+t[] <= t[]) return false;
return true;
} int main() {
#ifdef Phantom01
freopen("1002.txt", "r", stdin);
#endif // Phantom01 while (scanf("%d", &n)!=EOF) {
if (==n) break; int sum = ;
for (int i = ; i < n; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
memset(dp, false, sizeof(dp));
dp[][] =true; for (int k = ; k < n; k++)
for (int i = sum - a[k]; i >= ; i--)
for (int j = sum - a[k]; j >= ; j--) {
dp[i+a[k]][j] = dp[i][j] || dp[i+a[k]][j];
dp[i][j+a[k]] = dp[i][j] || dp[i][j+a[k]];
}
ans = -;
for (int i = ; i <= sum; i++)
for (int j = ; j <= sum; j++) if (dp[i][j]) {
if (check(i, j, sum-i-j))
ans = max((int)(Area(i, j, sum-i-j)*), ans);
}
printf("%d\n", ans);
} return ;
}
1002
1003： 二维线段树可做，不过因为数据范围比较小，逆序枚举所以矩形，看该点最后落在哪个矩形中。
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std; const int MAXN = ; int x[MAXN*], y[MAXN*];
int x1[MAXN], x2[MAXN], y1[MAXN], y2[MAXN], R[MAXN], G[MAXN], B[MAXN];
int n, m;
int cntx, cnty; bool check(int px, int py, int k) {
if (x1[k]<=px&&px<=x2[k] && y1[k]<=py&&py<=y2[k])
return true;
return false;
} int main() {
#ifdef Phantom01
freopen("1003.txt", "r", stdin);
#endif // Phantom01 while (scanf("%d%d", &n, &m)!=EOF) {
if (==n&&==m) break;
cntx = cnty = ;
for (int i = ; i < n; i++) {
scanf("%d%d%d%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i], &R[i], &G[i], &B[i]);
}
for (int i = ; i < m; i++) {
int px, py;
bool flag = false;
scanf("%d%d", &px, &py);
for (int j = n-; j >= ; j--)
if (check(px, py, j)) {
flag = true;
printf("%d %d %d\n", R[j], G[j], B[j]);
break;
}
if (!flag) puts("255 255 255");
}
} return ;
}
1003
1004： 可以证明，只有对称的时候后手能赢
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std; int main()
{
int n, i;
int a[];
while(scanf("%d", &n), n) {
for(i = ; i < n; ++i) scanf("%d", a+i);
sort(a, a+n);
int cnt = ;
bool flag = ;
for(i = ; i < n; ++i) {
if(a[i] == a[i-]) cnt++;
else {
if(cnt&) {
flag = ;
break;
}
else cnt = ;
}
}
if(!flag) puts("Lose");
else puts("Win");
}
return ;
}
1004