JLOI2013过了好长时间,才写第四题。。

第一问比较好想。

第二问我想到了n^3次方的做法,但是数据。。。。于是没敢写,然后上网查了一下题解,居然是O(n^3)过的,数据这么弱。。。

/*
* Problem: JLOI2013-Terrain
* Author: Shun Yao
*/ #include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <assert.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <time.h> #include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <bitset>
#include <utility>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional> //using namespace std; const int MAXN = 1010;
const int MOD = 2011; int n;
std::map<int, int> ocr; struct Data {
int h, k;
} a[MAXN]; bool cmp(Data a, Data b) {
return a.h != b.h ? a.h > b.h : a.k < b.k;
} int main(/*int argc, char **argv*/) {
int i, j, t, f[2][MAXN], ans1, ans2, cur, k; freopen("terrain.in", "r", stdin);
freopen("terrain.out", "w", stdout); scanf("%d", &n);
for (i = 1; i <= n; ++i) {
scanf("%d%d", &a[i].h, &a[i].k);
++ocr[a[i].h];
}
std::sort(a + 1, a + n + 1, cmp);
ans1 = ans2 = 1;
for (i = 1; i <= n; ) {
t = 0;
for (j = 0; j < ocr[a[i].h]; ++j)
ans1 = ans1 * (std::min(i, a[i + j].k) + t++) % MOD;
memset(f[0], 0, sizeof f[0]);
f[0][1] = 1;
cur = 0;
for (j = 0; j < ocr[a[i].h]; ++j) {
memset(f[1 - cur], 0, sizeof f[1 - cur]);
for (k = 1; k <= std::min(i, a[i + j].k); ++k)
f[1 - cur][k] = (f[1 - cur][k - 1] + f[cur][k]) % MOD;
cur = 1 - cur;
}
t = 0;
for (j = 1; j <= i; ++j)
t = (t + f[cur][j]) % MOD;
ans2 = ans2 * t % MOD;
i += ocr[a[i].h];
}
printf("%d %d", ans1, ans2); fclose(stdin);
fclose(stdout);
return 0;
}

最新文章

  1. CSS常用选择器名
  2. codeforces 723F : st-Spanning Tree
  3. COGS 2479 偏序 题解
  4. PHP Header下载文件在IE文件名中文乱码问题
  5. Informatica 9.1常用查询
  6. android开发之res下的menu (xml+代码的形式)
  7. C#语言之“String.Split”的使用【转】
  8. ZUFE OJ 2301 GW I (3)
  9. GDI和内核对象区别
  10. python时间模块time
  11. iOS UIDatePicker设置为中文的方法
  12. 没有IDE的日子
  13. Xshell 连接虚拟机特别慢 解决方案
  14. zookeeper伪分布式集群安装
  15. 怎样防止应用因获取IDFA被AppStore拒绝
  16. Bean相关
  17. Lesson9 some interesting things in C#
  18. spring事务管理实现方式
  19. Visual C++ 经典的人脸识别算法源代码
  20. 【Todo】Java学习路线(方向指导)

热门文章

  1. Camel、Pastal、匈牙利标记法区别及联系
  2. Android XML使用的学习记录
  3. SQLiteParameter不能将TableName作为参数
  4. POJ 1681 Painter&#39;s Problem (高斯消元 枚举自由变元求最小的步数)
  5. JPA中的@MappedSuperclass
  6. 图表框架HelloCharts(2)柱状图
  7. uvalive 4255 Guess(拓扑排序)
  8. HTMLParser 解析HTML
  9. Java [Leetcode 169]Majority Element
  10. 私有pod简记