华建河北住房和城乡建设厅网站,凤岗仿做网站,珠海网络公司有哪些,网站有备案号吗据说A,B,C题都比较水这里就不放代码了 D:Facility Locations 然而D题是一个脑经急转弯的题#xff1a;有m行#xff0c;n列#xff0c;每个位置有可能为0#xff0c;也可能不为0#xff0c;问最多选K行是不是可以使得每一列都至少有一个0#xff0c;其中代价c有个约束条件…据说A,B,C题都比较水这里就不放代码了 D:Facility Locations 然而D题是一个脑经急转弯的题有m行n列每个位置有可能为0也可能不为0问最多选K行是不是可以使得每一列都至少有一个0其中代价c有个约束条件These costs satisfy a locality property: for two clients j and j’ and two facilities i and i’, we have cij ≤ ci’j ci’j’ cij’ . 一看特别像是重复覆盖的模板然而稍加分析就会发现由于上面约束的存在那么任意两行之间的0的摆放要么完全相同要么完全错位所以最后只要找出任意k个完全错开的行判断是不是每一列都有一个0就可以了 1 #include map2 #include set3 #include stack4 #include queue5 #include cmath6 #include ctime7 #include vector8 #include cstdio9 #include cctype
10 #include cstring
11 #include cstdlib
12 #include iostream
13 #include algorithm
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)140))
17 #define lson k1, L, (L R)1
18 #define rson k1|1, ((L R)1) 1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen(in.txt, r, stdin)
23 #define FOUT freopen(out.txt, w, stdout)
24 #define rep(i, a, b) for(int i a; i b; i )
25 #define dec(i, a, b) for(int i a; i b; i --)
26
27 templateclass T T CMP_MIN(T a, T b) { return a b; }
28 templateclass T T CMP_MAX(T a, T b) { return a b; }
29 templateclass T T MAX(T a, T b) { return a b ? a : b; }
30 templateclass T T MIN(T a, T b) { return a b ? a : b; }
31 templateclass T T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
32 templateclass T T LCM(T a, T b) { return a / GCD(a,b) * b; }
33
34 //typedef __int64 LL;
35 typedef long long LL;
36 const int MAXN 51000;
37 const int MAXM 110000;
38 const double eps 1e-4;
39 LL MOD 1000000007;
40
41 int n, m, k, x;
42 bool vis[110];
43
44 int main()
45 {
46 while(~scanf(%d %d %d, n, m, k)) {
47 mem0(vis);
48 int time 0, col 0;
49 rep (i, 1, n) {
50 int add 0;
51 rep (j, 1, m) {
52 scanf(%d, x);
53 if(x || vis[j]) continue;
54 if(!add) time ;
55 add 1;
56 vis[j] 1, col ;
57 }
58 }
59 puts(col m time k ? yes : no);
60 }
61 return 0;
62 } View Code ERepeated Substrings 据说是一个后缀数组的最长公共前缀LCP的应用 赛后又自己写了一遍后缀数组其实是把模板打了一遍模板见链接终于还是把这题A了 题解见链接 1 #include map2 #include set3 #include stack4 #include queue5 #include cmath6 #include ctime7 #include vector8 #include cstdio9 #include cctype10 #include cstring11 #include cstdlib12 #include iostream13 #include algorithm14 using namespace std;15 #define INF 0x3f3f3f3f16 #define inf (-((LL)140))17 #define lson k1, L, (L R)118 #define rson k1|1, ((L R)1) 1, R19 #define mem0(a) memset(a,0,sizeof(a))20 #define mem1(a) memset(a,-1,sizeof(a))21 #define mem(a, b) memset(a, b, sizeof(a))22 #define FIN freopen(in.txt, r, stdin)23 #define FOUT freopen(out.txt, w, stdout)24 #define rep(i, a, b) for(int i a; i b; i )25 #define dec(i, a, b) for(int i a; i b; i --)26 27 templateclass T T CMP_MIN(T a, T b) { return a b; }28 templateclass T T CMP_MAX(T a, T b) { return a b; }29 templateclass T T MAX(T a, T b) { return a b ? a : b; }30 templateclass T T MIN(T a, T b) { return a b ? a : b; }31 templateclass T T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }32 templateclass T T LCM(T a, T b) { return a / GCD(a,b) * b; }33 34 //typedef __int64 LL;35 typedef long long LL;36 const int MAXN 110000;37 const int MAXM 110000;38 const double eps 1e-4;39 LL MOD 1000000007;40 41 struct SufArray {42 char s[MAXN];43 int sa[MAXN], t[MAXN], t2[MAXN], c[MAXN], n, m;44 int rnk[MAXN], height[MAXN];45 int mi[MAXN][20], idxK[MAXN];46 47 void init() {48 mem0(s);49 mem0(height);50 }51 void read_str() {52 gets(s);53 m 128;54 n strlen(s);55 s[n] ;56 }57 void build_sa() {58 int *x t, *y t2;59 rep (i, 0, m - 1) c[i] 0;60 rep (i, 0, n - 1) c[x[i] s[i]] ;61 rep (i, 1, m - 1) c[i] c[i - 1];62 dec (i, n - 1, 0) sa[--c[x[i]]] i;63 for(int k 1; k n; k 1) {64 int p 0;65 rep (i, n - k, n - 1) y[p] i;66 rep (i, 0, n - 1) if(sa[i] k) y[p] sa[i] - k;67 rep (i, 0, m - 1) c[i] 0;68 rep (i, 0, n - 1) c[x[y[i]]] ;69 rep (i, 0, m - 1) c[i] c[i - 1];70 dec (i, n - 1, 0) sa[--c[x[y[i]]]] y[i];71 swap(x, y);72 p 1;73 x[sa[0]] 0;74 rep (i, 1, n - 1) {75 x[sa[i]] y[sa[i - 1]] y[sa[i]] y[sa[i - 1] k] y[sa[i] k] ? p - 1 : p;76 }77 if(p n) break;78 m p;79 }80 }81 void get_height() {82 int k 0;83 rep (i, 0, n - 1) rnk[sa[i]] i;84 rep (i, 0, n - 1) {85 if(k) k --;86 int j sa[rnk[i] - 1];87 while(s[i k] s[j k]) k ;88 height[rnk[i]] k;89 }90 }91 void rmq_init(int *a, int n) {92 rep (i, 0, n - 1) mi[i][0] a[i];93 for(int j 1; (1 j) n; j ) {94 for(int i 0; i (1j) - 1 n; i ) {95 mi[i][j] min(mi[i][j - 1], mi[i (1 (j - 1))][j - 1]);96 }97 }98 rep (len, 1, n) {99 idxK[len] 0;
100 while((1 (idxK[len] 1)) len) idxK[len] ;
101 }
102 }
103 int rmq_min(int l, int r) {
104 int len r - l 1, k idxK[len];
105 return min(mi[l][k], mi[r - (1 k) 1][k]);
106 }
107 void lcp_init() {
108 get_height();
109 rmq_init(height, n);
110 }
111 int get_lcp(int a, int b) {
112 if(a b) return n - a - 1;
113 return rmq_min(min(rnk[a], rnk[b]) 1, max(rnk[a], rnk[b]));
114 }
115 void solve() {
116 get_height();
117 LL ans 0, pre 0;
118 rep (i, 1, n - 1) {
119 if(height[i] pre) ans height[i] - pre;
120 pre height[i];
121 }
122 cout ans endl;
123 }
124 };
125
126 int T;
127 SufArray sa;
128
129 int main()
130 {
131 while(~scanf(%d%*c, T)) while(T--){
132 sa.init();
133 sa.read_str();
134 sa.build_sa();
135 sa.solve();
136 }
137 return 0;
138 }
139 /**************************************************************
140 Problem: 1632
141 User: csust_Rush
142 Language: C
143 Result: Accepted
144 Time:880 ms
145 Memory:13192 kb
146 ****************************************************************/ View Code FLandline Telephone Network题意就是求一颗最小生成树但是任意两个点之间的唯一路径上不能通过任何一个 坏点 题目告诉你哪些是坏点 其实就是先不管坏点求一遍最小生成树然后把坏点加进去注意细节地方 1 #include stdio.h2 #include iostream3 #include cmath4 #include cstdlib5 #include vector6 #include algorithm7 #include cstring8 #define mem0(a) memset(a, 0, sizeof(a))9 #define rep(i,a, b) for(int i a; i b; i )
10 using namespace std;
11
12 int fa[1100];
13 struct Edge {
14 int u, v, w;
15 Edge(int _u 0, int _v 0, int _w 0) {
16 u _u; v _v; w _w;
17 }
18 bool operator (const Edge A) const {
19 return w A.w;
20 }
21 }e[110000];
22 int n, m, p, x, b[1100], u, v, w;
23 int t[1100];
24
25 int findFa(int x) {
26 return x fa[x] ? x : fa[x] findFa(fa[x]);
27 }
28
29 int main()
30 {
31 //freopen(in.txt, r, stdin);
32 while(~scanf(%d %d %d, n, m, p) n) {
33 mem0(b); mem0(t);
34 rep (i, 1, n) fa[i] i;
35 rep (i, 1, p) scanf(%d, x), b[x] 1;
36 rep (i, 1, m) {
37 scanf(%d %d %d, u, v, w);
38 e[i] Edge(u, v, w);
39 }
40 if(n 2) {
41 cout w endl;
42 continue;
43 }
44 sort(e 1, e m 1);
45 int ans 0;
46 rep (i, 1, m) {
47 u e[i].u, v e[i].v, w e[i].w;
48 if(b[u] || b[v]) continue;
49 int x findFa(u), y findFa(v);
50 if(x ! y) {
51 ans w;
52 fa[x] y;
53 }
54 }
55 int imposs 0;
56 rep (i, 1, m) {
57 u e[i].u, v e[i].v, w e[i].w;
58 if(!(b[u] ^ b[v])) continue;
59 t[u]; t[v] ;
60 if(b[u] t[u] 2) continue;
61 if(b[v] t[v] 2) continue;
62 int x findFa(u), y findFa(v);
63 if(x ! y) {
64 ans w;
65 fa[x] y;
66 }
67 }
68 int cnt 0;
69 rep (i, 1, n) if(findFa(fa[i]) i) {cnt ; }
70 if(imposs || cnt 1) puts(impossible);
71 else cout ans endl;
72 }
73 return 0;
74 }
75
76 /**************************************************************
77 Problem: 1633
78 User: csust_Rush
79 Language: C
80 Result: Accepted
81 Time:84 ms
82 Memory:2792 kb
83 ****************************************************************/ View Code GAquarium Tank简单计算几何 1 #include map2 #include set3 #include stack4 #include queue5 #include cmath6 #include ctime7 #include vector8 #include cstdio9 #include cctype10 #include cstring11 #include cstdlib12 #include iostream13 #include algorithm14 using namespace std;15 #define INF 0x3f3f3f3f16 #define inf (-((LL)140))17 #define lson k1, L, (L R)118 #define rson k1|1, ((L R)1) 1, R19 #define mem0(a) memset(a,0,sizeof(a))20 #define mem1(a) memset(a,-1,sizeof(a))21 #define mem(a, b) memset(a, b, sizeof(a))22 #define FIN freopen(in.txt, r, stdin)23 #define FOUT freopen(out.txt, w, stdout)24 #define rep(i, a, b) for(int i a; i b; i )25 #define dec(i, a, b) for(int i a; i b; i --)26 27 templateclass T T CMP_MIN(T a, T b) { return a b; }28 templateclass T T CMP_MAX(T a, T b) { return a b; }29 templateclass T T MAX(T a, T b) { return a b ? a : b; }30 templateclass T T MIN(T a, T b) { return a b ? a : b; }31 templateclass T T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }32 templateclass T T LCM(T a, T b) { return a / GCD(a,b) * b; }33 34 //typedef __int64 LL;35 typedef long long LL;36 const int MAXN 110000;37 const int MAXM 110000;38 const double eps 1e-6;39 LL MOD 1000000007;40 41 int n;42 double D, L;43 struct Point {44 double x, y;45 Point(double _x 0, double _y 0) {46 x _x; y _y;47 }48 };49 50 double cross(Point a, Point b) {51 return a.x * b.y - a.y * b.x;52 }53 54 struct Polygon {55 Point p[MAXN];56 int cnt;57 double get_area() {58 int pre cnt;59 double ans 0;60 rep (i, 1, cnt) {61 ans cross(p[pre], p[i]);62 pre i;63 }64 return fabs(ans / 2);65 }66 67 }pol, po;68 69 Point get_point(Point a, Point b, double y0) {70 if(fabs(a.x - b.x) eps) return Point(a.x, y0);71 double bi (y0 - a.y) / (b.y - a.y);72 return Point(a.x bi * (b.x - a.x), a.y bi * (b.y - a.y));73 }74 75 double find_area(double y0) {76 int cnt 0, pre po.cnt;77 rep (i, 1, po.cnt) {78 if((y0 - po.p[pre].y) * (y0 - po.p[i].y) 0) {79 pol.p[cnt] get_point(po.p[pre], po.p[i], y0);80 }81 if(po.p[i].y y0) pol.p[cnt] po.p[i];82 pre i;83 }84 pol.cnt cnt;85 return pol.get_area();86 }87 88 int main()89 {90 //FIN;91 while(~scanf(%d, po.cnt)) {92 cin D L;93 L * 1000;94 double mx_y 0.0;95 rep (i, 1, po.cnt) {96 scanf(%lf %lf, po.p[i].x, po.p[i].y);97 mx_y max(mx_y, po.p[i].y);98 }99 double low 0.0, high mx_y;
100 while(high - low eps) {
101 double mid (low high) / 2.0;
102 if(find_area(mid) * D L) low mid;
103 else high mid;
104 }
105 printf(%.2lf\n, low);
106 }
107 return 0;
108 }
109
110 /**************************************************************
111 Problem: 1634
112 User: csust_Rush
113 Language: C
114 Result: Accepted
115 Time:12 ms
116 Memory:4920 kb
117 ****************************************************************/ View Code HRestaurant Ratings 一个数位的简单DPDP[i][j]表示i个人打j分的方案数 1 #include map2 #include set3 #include stack4 #include queue5 #include cmath6 #include ctime7 #include vector8 #include cstdio9 #include cctype
10 #include cstring
11 #include cstdlib
12 #include iostream
13 #include algorithm
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)140))
17 #define lson k1, L, (L R)1
18 #define rson k1|1, ((L R)1) 1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen(in.txt, r, stdin)
23 #define FOUT freopen(out.txt, w, stdout)
24 #define rep(i, a, b) for(int i a; i b; i )
25 #define dec(i, a, b) for(int i a; i b; i --)
26
27 templateclass T T CMP_MIN(T a, T b) { return a b; }
28 templateclass T T CMP_MAX(T a, T b) { return a b; }
29 templateclass T T MAX(T a, T b) { return a b ? a : b; }
30 templateclass T T MIN(T a, T b) { return a b ? a : b; }
31 templateclass T T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
32 templateclass T T LCM(T a, T b) { return a / GCD(a,b) * b; }
33
34 //typedef __int64 LL;
35 typedef long long LL;
36 const int MAXN 51000;
37 const int MAXM 110000;
38 const double eps 1e-4;
39 LL MOD 1000000007;
40
41 LL dp[110][110];
42
43 void init_dp(int n) {
44 dp[0][0] 1;
45 rep (i, 1, n) {
46 rep (j, 0, n) {
47 rep (k, 0, j) {
48 dp[i][j] dp[i - 1][j - k];
49 }
50 }
51 }
52 }
53
54 int n, a[110];
55
56 int main()
57 {
58 init_dp(100);
59 while(~scanf(%d, n) n) {
60 int sum 0;
61 rep (i, 1, n) {
62 scanf(%d, a[i]);
63 sum a[i];
64 }
65 LL ans 1;
66 rep (i, 0, sum - 1) {
67 ans dp[n][i];
68 }
69 rep (i, 1, n) {
70 rep (j, 0, a[i] - 1) {
71 ans dp[n - i][sum - j];
72 }
73 sum - a[i];
74 }
75 cout ans endl;
76 }
77 return 0;
78 }
79
80 /**************************************************************
81 Problem: 1635
82 User: csust_Rush
83 Language: C
84 Result: Accepted
85 Time:16 ms
86 Memory:1580 kb
87 ****************************************************************/ View Code ILocked Treasure 据说是看样例找规律然后发现ansC(n, m-1)不过也有类似的完美证明 JYet Satisfiability Again! 比赛时最后几分钟用暴力交了一发发现AC了赛后看其他人时间大概都是暴利做的 最后干脆连题解都是用暴力啊 1 #include stdio.h2 #include iostream3 #include cmath4 #include cstdlib5 #include vector6 #include algorithm7 #include cstring8 #define mem0(a) memset(a, 0, sizeof(a))9 #define rep(i,a, b) for(int i a; i b; i )
10 using namespace std;
11
12 int t, n, m;
13 struct Node {
14 int a[21], f[21], cnt;
15 bool judge(int s) {
16 int ans 0, p 0;
17 while(p cnt !ans) {
18 ans | a[p] ^ (((1f[p]) s) ? 1 : 0);
19 p ;
20 }
21 return ans;
22 }
23 }mt[110];
24 char s[111100];
25
26 void handle(char *s, int id) {
27 int len strlen(s), cnt 0;
28 rep (i, 0, len - 1) {
29 if(s[i] X) {
30 int num 0, p i;
31 while(isdigit(s[p])) num num * 10 s[p] - 0;
32 mt[id].a[cnt] i 0 s[i - 1] ~;
33 mt[id].f[cnt] num - 1;
34 }
35 }
36 mt[id].cnt cnt;
37 }
38
39 int main()
40 {
41 //freopen(in.txt, r, stdin);
42 while(cin t) while(t--) {
43 scanf(%d %d, n, m);
44 gets(s);
45 rep (i, 1, m) {
46 gets(s);
47 handle(s, i);
48 }
49 int ok 0, h (1 n) - 1;
50 rep (s, 0, h) {
51 int p 1;
52 rep (i, 1, m) {
53 p mt[i].judge(s);
54 if(!p) break;
55 }
56 ok | p;
57 if(ok) {
58 break;
59 }
60 }
61 if(ok) puts(satisfiable);
62 else puts(unsatisfiable);
63 }
64 return 0;
65 }
66
67 /**************************************************************
68 Problem: 1637
69 User: csust_Rush
70 Language: C
71 Result: Accepted
72 Time:1768 ms
73 Memory:1612 kb
74 ****************************************************************/ View Code KContinued Fraction 做了两次了第一次以为超LL后来队友用BigInt自己写的模板过了 后来又听说LL可以过再回头看自己代码发现有用LL*LL这必然超啊。。。改了后发现立马AC 1 #include stdio.h2 #include iostream3 #include cmath4 #include cstdlib5 using namespace std;6 7 typedef long long LL;8 9 int n, m;
10 LL a1[100], a2[100];
11
12 LL gcd(LL a, LL b) {
13 return b 0 ? a : gcd(b, a % b);
14 }
15
16 void dfs1(LL a, LL b, LL *arr, int i, int n)
17 {
18 if(i n - 1) {
19 a 1; b arr[i]; return ;
20 }
21 dfs1(a, b, arr, i 1, n);
22 LL tmp a;
23 a b; b arr[i] * b tmp;
24 LL g gcd(a, b);
25 a / g; b / g;
26 }
27
28 void add(LL A1, LL B1, LL A2, LL B2, LL x, LL y) {
29 x A1 * B2 A2 * B1;
30 y B1 * B2;
31 LL g gcd(x, y);
32 x / g; y / g;
33 }
34 void sub(LL A1, LL B1, LL A2, LL B2, LL x, LL y) {
35 x A1 * B2 - A2 * B1;
36 y B1 * B2;
37 LL g gcd(x, y);
38 x / g; y / g;
39 }
40 void mul(LL A1, LL B1, LL A2, LL B2, LL x, LL y) {
41 x A1 * A2; y B1 * B2;
42 LL g gcd(x, y);
43 x / g; y / g;
44 }
45 void div(LL A1, LL B1, LL A2, LL B2, LL x, LL y) {
46 x A1 * B2; y A2 * B1;
47 LL g gcd(x, y);
48 x / g; y / g;
49 }
50
51 void print(LL x, LL y) {
52 if (x 0 y 0 || x 0 y 0) {
53 if (x % y ! 0) cout x / y - 1 ;
54 else {
55 cout x / y endl;;
56 return;
57 }
58 x abs(y) - abs(x) % abs(y);
59 print(abs(y), x);
60 return ;
61 }
62 cout x / y;
63 if(x % y) {
64 printf( );
65 print(y, x % y);
66 }
67 else printf(\n);
68 }
69
70 int main()
71 {
72 //freopen(in.txt, r, stdin);
73 int cas 0;
74 while(~scanf(%d %d, n, m)) {
75 for(int i 0; i n; i ) cin a1[i];
76 for(int i 0; i m; i ) cin a2[i];
77 LL A1 0, B1 1, A2 0, B2 1;
78 if (n 1) dfs1(A1, B1, a1, 1, n);
79 if (m 1) dfs1(A2, B2, a2, 1, m);
80 A1 a1[0] * B1 A1;
81 A2 a2[0] * B2 A2;
82 LL x, y;
83 //printf(Case %d:\n, cas);
84 add(A1, B1, A2, B2, x, y); print(x, y);
85 sub(A1, B1, A2, B2, x, y); print(x, y);
86 mul(A1, B1, A2, B2, x, y); print(x, y);
87 div(A1, B1, A2, B2, x, y); print(x, y);
88 }
89 return 0;
90 }
91 View Code 转载于:https://www.cnblogs.com/gj-Acit/p/4527661.html
