鞍山网站开发公司,做响应式网站需要学哪些知识,阜阳手机网站建设,前端网站开发培训原题链接#xff1a;http://codeforces.com/gym/101147/problem/F 题意#xff1a;n*n的棋盘#xff0c;给m个主教的坐标及其私有距离p#xff0c;以及常数C#xff0c;求位于同一对角线上满足条件#xff1a;dist(i, j) p[i]^2 p[j]^2 C 的主教集合的元素个数最… 原题链接http://codeforces.com/gym/101147/problem/F 题意n*n的棋盘给m个主教的坐标及其私有距离p以及常数C求位于同一对角线上满足条件dist(i, j) p[i]^2 p[j]^2 C 的主教集合的元素个数最大值。 解题思路 上述条件可以等价为 d(j) - d(i) 1 p[i]^2 p[j]^2 C // d(i) 为第i个主教相对于该对角线顶点的距离 d(j) - p[j]^2 - C 1 d(i) p[i]^2 设 f(i) d(i) p[i] ^2, g(i) d(i) - p[i]^2 - C 1 下面考虑一条对角线设 c[x] 为长度为x 的最后一个主教编号例如c[len] i 代表长度为len的防线最后一个主教编号为i。 (特别的c[0] 0, f(0) -INF ) 首先将该对角线上的主教按 d(i) 排序 len 为当前最大长度1依次查询每一个主教并同时更新最大长度, 伪代码如下 对当前查询的主教u j lower_bound(c, clenucmp) - c if j len g(u) f(c[j-1]) c[len] u if j ! len g(u) f(c[j-1]) c[j] u 注意 数据范围为 LL 代码如下 1 #include cstring2 #include cstdio3 #include algorithm4 #include vector5 using namespace std;6 const int maxn 10000010;7 typedef long long LL;8 #define INF 999999999999999999LL9 vectorint D1[2*maxn];
10 vectorint D2[2*maxn];
11
12 int c[maxn];
13 int row[maxn], col[maxn], p[maxn];
14 int n, m, C;
15 //计算对角线编号
16 int dig_id1(int x, int y) {return x-yn;}
17 int dig_id2(int x, int y) {return xy;}
18
19 int d1(int i) {return min(row[i], col[i]);}
20 int d2(int i) {return min(n-row[i]1, col[i]);}
21
22 LL f1(int i) {return !i ? -INF : d1(i) LL(p[i])*p[i];}
23 LL f2(int i) {return !i ? -INF : d2(i) LL(p[i])*p[i];}
24
25 LL g1(int i) {return d1(i) - LL(p[i])*p[i] - C 1;}
26 LL g2(int i) {return d2(i) - LL(p[i])*p[i] - C 1;}
27
28 bool cmpd1(int i, int j) {return d1(i) d1(j);}
29 bool cmpd2(int i, int j) {return d2(i) d2(j);}
30 bool cmp1(const int a,const int b) {return f1(a) f1(b);}
31 bool cmp2(const int a,const int b) {return f2(a) f2(b);}
32 LL (*f[])(int) {
33 f1,
34 f2
35 };
36 LL (*g[])(int) {
37 g1,
38 g2
39 };
40 bool (*cmp[])(const int ,const int ) {
41 cmp1,
42 cmp2
43 };
44
45 int cal(vectorint D,int flag) {
46 if(!D.size()) return 0;
47 if(flag 0) sort(D.begin(), D.end(), cmpd1);
48 else sort(D.begin(), D.end(), cmpd2);
49 for(int i 0; i D.size(); i) c[i] 0;
50 int len 1;
51 int j;
52 for(int i 0; i D.size(); i){
53 int u D[i];
54 j lower_bound(c, clen, u, cmp[flag]) - c;
55 if(j len g[flag](u) f[flag](c[j-1])) {
56 c[len] u;
57 }
58 if(j ! len g[flag](u) f[flag](c[j-1])) {
59 c[j] u;
60 }
61 }
62 return len - 1;
63 }
64 #define fin stdin
65 int main() {
66 // FILE * fin;
67 // fin fopen(bishops.in, r);
68 int T;
69 fscanf(fin, %d, T);
70 while(T--) {
71 fscanf(fin, %d%d%d, n, m, C);
72 for(int i 0; i 2*n; i) D1[i].clear();
73 for(int i 0; i 2*n; i) D2[i].clear();
74 for(int i 1; i m; i) {
75 fscanf(fin, %d%d%d, row[i], col[i], p[i]);
76 int id1 dig_id1(row[i], col[i]);
77 int id2 dig_id2(row[i], col[i]);
78 D1[id1].push_back(i);
79 D2[id2].push_back(i);
80 }
81 int ans 0;
82 for(int i 0; i 2*n; i) {
83 ans max(ans, cal(D1[i], 0));
84 ans max(ans, cal(D2[i], 1));
85 }
86 printf(%d\n, ans);
87 }
88 return 0;
89 } 转载于:https://www.cnblogs.com/Kiraa/p/6089377.html
