ZOJ Monthly, January 2014(2014省份赛练习)

ZOJ Monthly, January 2014(2014省赛练习)

比赛链接

C
每一堆用一个vector保存，排序，询问的时候枚举小的一堆然后在大的一堆里面log(n)找放的位置，然后去算一下答案，

当然你要记录一下做过的询问，如果已经计算过了就没必要计算，直接拿出来就可以了，总体的极限复杂度是O(sqrt(n)*n)

n-1个数必然是n*n, n*n-2,........n*n-2*(n-2), 然后剩下的数/2向上取整就是最后一个能得到的最大的数

printf("%d\n", n*n*(n-1)-(n-1)*(n-2)+(n*n-2*n+4)/2);

简单搜索

队友做的，简单数学题

C：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef pair<int, int> PII;
#define snuke(it, x) \
	for(__typeof((x).begin())it = (x).begin(); \
			it != (x).end(); it++)
const int N = 100005;
const int M = 100005;
vector <PII > vec[N];
map <PII, int> ans;
int a[N];
int n, m;
int main() {
	int i, j, t;
	while(scanf("%d", &n) == 1) {
		ans.clear();
		for(i = 1; i <= n; i++) {
			vec[i].clear();
			scanf("%d", &a[i]);
			for(j = 0; j < a[i]; j++) {
				scanf("%d", &t);
				vec[i].push_back(make_pair(t, i));
			}
			sort(vec[i].begin(), vec[i].end());
		}
		scanf("%d", &m);
		for(i = 0; i < m; i++) {
			int x, y;
			scanf("%d%d", &x, &y);
			if(vec[x].size() < vec[y].size())
				swap(x, y);
			if(ans.count(make_pair(x, y))) {
				printf("%d\n", ans[make_pair(x, y)]);
				continue;
			}
			int cnt = 0;
			int pre = -1;
			snuke(j, vec[y]) {
				int k = lower_bound(vec[x].begin(), vec[x].end(), *j)-vec[x].begin();
				if(pre == k) continue;
				pre = k;
				if(k != 0)cnt++;
				if(k != vec[x].size()) cnt++;
			}
			ans[make_pair(x, y)] = cnt;
			printf("%d\n", cnt);
		}
	}
	return 0;
}

F：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int a[11];
double ans;
double gao(int a, int b, int c) {
   // printf("a=%d b=%d c=%d\n", a, b, c);
    double p = (a+b+c)*1.0/2;
   // printf("%lf\n", sqrt(p*(p-a)*(p-b)*(p-c)));
    return sqrt(p*(p-a)*(p-b)*(p-c));
}
int b[11];
int c[11];
void dfs(int u) {
    if(u == 6) {
        memset(c, 0, sizeof(c));
        for(int i = 0; i < 6; i++)
            c[b[i]] += a[i];
        sort(c, c+3);
        int cnt[4][4] = {0};
        for(int i = 0; i < 6; i+=2) {
            int x = b[i], y = b[i+1];
            if(x >y) swap(x, y);
            cnt[x][y]++;
        }
        for(int i = 0; i < 3; i++)
            for(int j = i+1; j < 3; j++)
                if(cnt[i][j] >= 2) return;
        if(c[0]+c[1] > c[2] && c[0]&&c[1] && c[2] ) {
            ans = max(ans, gao(c[0], c[1], c[2]));
           // for(int i = 0; i < 6; i++)
          //      printf("%d ", b[i]);
           // puts("");
        }
        return;
    }
    for(int i = 0; i < 3; i++) {
        b[u] = i;
        dfs(u+1);
    }
}
int main() {
    int i, j;
    while(~scanf("%d", &a[0])) {
        for(i = 1; i < 6; i++)
            scanf("%d", &a[i]);
        ans = 0;
        dfs(0);
        printf("%.11f\n", ans);
    }
    return 0;
}

ZOJ Monthly, January 2014(2014省份赛练习)

相关推荐