A：SUM
水。
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 #define N 100010 6 typedef long long ll; 7 8 int n; 9 ll arr[N]; 10 ll sum[N]; 11 12 int main() 13 { 14 while(~scanf("%d",&n)) 15 { 16 memset(sum, 0, sizeof sum); 17 for(int i = 1; i <= n; ++i) 18 { 19 scanf("%lld",&arr[i]); 20 } 21 for(int i = n; i >= 1; --i) 22 { 23 sum[i] = sum[i + 1] + arr[i] * (n - i + 1); 24 } 25 for(int i = 1;i <= n; ++i) 26 { 27 printf("%lld%c",sum[i]," "[i == n]); 28 } 29 } 30 return 0; 31 }
B：XOR1
思路：枚举ai, 去字典树中找最大值，取max
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define N 100010 6 #define ll long long 7 8 int tree[N * 64][5]; 9 int cnt[N * 64]; 10 int pos; 11 12 inline void Init() 13 { 14 memset(tree, 0, sizeof tree); 15 memset(cnt, 0, sizeof cnt); 16 pos = 0; 17 } 18 19 inline void insert(int x) 20 { 21 bitset <40> b; b = x; 22 int root = 0; 23 for (int i = 39; i >= 0; --i) 24 { 25 int id = b[i]; 26 if (!tree[root][id]) 27 tree[root][id] = ++pos; 28 root = tree[root][id]; 29 cnt[root]++; 30 } 31 } 32 33 inline ll Find(int x) 34 { 35 bitset <40> b; b = x; 36 ll ans = 0; 37 int root = 0; 38 for (int i = 39; i >= 0; --i) 39 { 40 int id = b[i] ^ 1; 41 bool flag = true; 42 if (!tree[root][id] || cnt[tree[root][id]] <= 0) 43 id ^= 1, flag = false; 44 root = tree[root][id]; 45 if (flag) ans += (1 << i); 46 } 47 return ans; 48 } 49 50 int n; 51 int arr[N]; 52 53 int main() 54 { 55 while (scanf("%d", &n) != EOF) 56 { 57 Init(); 58 for (int i = 1; i <= n; ++i) 59 { 60 scanf("%d", arr + i); 61 insert(arr[i]); 62 } 63 ll ans = 0; 64 for (int i = 1; i < n; ++i) 65 { 66 ans = max(ans, Find(arr[i])); 67 } 68 printf("%lld ", ans); 69 } 70 return 0; 71 }
C：XOR2
思路：先DFS跑出DFS序，然后配合可持久化字典树就可以对子树进行区间操作。
我们自底向上推，这样对于一棵树，它的孩子的答案都已经更新，那么先取max, 假设直系孩子有n个，那么只需要枚举n - 1个孩子以及它的子树里的点更新答案就可以。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define N 100010 6 #define ll long long 7 8 int arr[N]; 9 10 struct Edge 11 { 12 int to, nx; 13 inline Edge() {} 14 inline Edge(int to, int nx) : to(to), nx(nx) {} 15 }edge[N << 1]; 16 17 int head[N], pos, cnt; 18 19 inline void Init() 20 { 21 memset(head, -1, sizeof head); 22 pos = 0; cnt = 0; 23 } 24 25 inline void addedge(int u, int v) 26 { 27 edge[++cnt] = Edge(v, head[u]); head[u] = cnt; 28 edge[++cnt] = Edge(u, head[v]); head[v] = cnt; 29 } 30 31 struct Point 32 { 33 int fa, ord, son, id; 34 int ans; 35 inline bool operator < (const Point& r) const 36 { 37 return son - ord < r.son - r.ord; 38 } 39 }point[N]; 40 41 int n; 42 int ford[N]; 43 44 struct node 45 { 46 int son[2], cnt; 47 inline node() 48 { 49 memset(son, 0, sizeof son); 50 cnt = 0; 51 } 52 }tree[N * 64]; 53 54 int root[N]; 55 int tot; 56 57 inline void insert(int id, int x) 58 { 59 root[id] = ++tot; 60 int pre = root[id - 1]; 61 int now = root[id]; 62 tree[now] = tree[pre]; 63 bitset <32> b; b = x; 64 for (int i = 31; i >= 0; --i) 65 { 66 int index = b[i]; 67 tree[++tot] = tree[tree[now].son[index]]; 68 tree[tot].cnt++; 69 tree[now].son[index] = tot; 70 now = tot; 71 } 72 } 73 74 inline int Find(int l, int r, int x) 75 { 76 int ans = 0; 77 l = root[l], r = root[r]; 78 bitset <32> b; b = x; 79 for (int i = 31; i >= 0; --i) 80 { 81 int index = b[i] ^ 1; 82 bool flag = true; 83 if (tree[tree[r].son[index]].cnt - tree[tree[l].son[index]].cnt <= 0) 84 { 85 index ^= 1; 86 flag = false; 87 } 88 if (flag) ans += (1 << i); 89 r = tree[r].son[index]; l = tree[l].son[index]; 90 } 91 return ans; 92 } 93 94 struct Node 95 { 96 int id, cnt; 97 inline Node() {} 98 inline Node(int id, int cnt) : id(id), cnt(cnt) {} 99 inline bool operator < (const Node &r) const 100 { 101 return cnt < r.cnt; 102 } 103 }; 104 105 inline void DFS(int u) 106 { 107 point[u].ord = ++pos; 108 point[u].id = u; 109 point[u].ans = 0; 110 insert(pos, arr[u]); 111 ford[pos] = u; 112 vector <Node> vv; 113 for (int it = head[u]; ~it; it = edge[it].nx) 114 { 115 int v = edge[it].to; 116 if (v == point[u].fa) continue; 117 point[v].fa = u; DFS(v); 118 point[u].ans = max(point[u].ans, point[v].ans); 119 vv.emplace_back(v, point[v].son - point[v].ord); 120 } 121 point[u].son = pos; 122 int l = point[u].ord, r = point[u].son; 123 if (l == r) return; 124 if (l + 1 == r) 125 { 126 point[u].ans = arr[ford[l]] ^ arr[ford[r]]; 127 return; 128 } 129 point[u].ans = max(point[u].ans, Find(l - 1, r, arr[u])); 130 sort(vv.begin(), vv.end()); 131 for (int i = 0, len = vv.size(); i < len - 1; ++i) 132 { 133 int it = vv[i].id; 134 int L = point[it].ord, R = point[it].son; 135 for (int j = L; j <= R; ++j) 136 { 137 point[u].ans = max(point[u].ans, Find(l - 1, r, arr[ford[j]])); 138 } 139 } 140 } 141 142 int main() 143 { 144 while (scanf("%d", &n) != EOF) 145 { 146 Init(); 147 memset(root, 0, sizeof root); 148 tot = 0; 149 for (int i = 1; i <= n; ++i) 150 scanf("%d", arr + i); 151 for (int i = 1, u, v; i < n; ++i) 152 { 153 scanf("%d%d", &u, &v); 154 addedge(u, v); 155 } 156 DFS(1); 157 for (int i = 1; i <= n; ++i) printf("%d%c", point[i].ans, " "[i == n]); 158 } 159 return 0; 160 }
D：String
思路：二分长度。在已经固定子串长度情况下可以做到o（n）枚举子串，通过map记录子串次数。
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 int len, k; 6 string s; 7 8 inline bool check(int mid) 9 { 10 map<string, int>mp; 11 string tmp = ""; 12 for (int i = 0; i < mid; ++i) 13 { 14 tmp += s[i]; 15 } 16 mp[tmp]++; 17 if (mp[tmp] >= k) return true; 18 for (int i = mid; i < len; ++i) 19 { 20 tmp.erase(tmp.begin()); 21 tmp += s[i]; 22 mp[tmp]++; 23 if (mp[tmp] >= k) return true; 24 } 25 return false; 26 } 27 28 int main() 29 { 30 ios::sync_with_stdio(false); 31 cin.tie(0); 32 cout.tie(0); 33 while (cin >> k) 34 { 35 cin >> s; 36 int ans = 0; 37 len = s.length(); 38 int l = 1, r = len / k; 39 while (r - l >= 0) 40 { 41 int mid = (l + r) >> 1; 42 if (check(mid)) 43 { 44 ans = mid; 45 l = mid + 1; 46 } 47 else 48 { 49 r = mid - 1; 50 } 51 } 52 cout << ans << endl; 53 } 54 return 0; 55 }
E：Dirt
思路：
线段与线段：如果相交为0，否则为线段两端点与另一线段间距取min
线段与圆：如果相交为0，否则为圆心与线段间距减去半径
线段与三角形：如果相交为0，否则为线段两端点与三角形三条线段间距以及三角心三个端点与线段间距取min
圆与圆：如果相交为0，否则为两圆心间距减去两圆半径
圆与三角形：如果相交为0，否则圆心与三角形三条线段间距取min
三角形与三角形：如果相交为0，否则为三角形的三个端点到另一个三角形的三条线段的间距取min
点与线段：如果点在线段上为0，否则为点到线段间距
点与圆：如果点在圆内为0，否则为点到圆心间距减去半径
点与三角形：如果点在三角形内为0，否则为点到三角形的三个线段的间距取min
最后跑一遍最短路
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define N 1110 6 7 const int INF = 0x3f3f3f3f; 8 9 const double eps = 1e-8; 10 11 int sgn(double x) 12 { 13 if (fabs(x) < eps) return 0; 14 if (x < 0) return -1; 15 else return 1; 16 } 17 18 struct Point 19 { 20 double x, y; 21 inline Point() {} 22 inline Point(double _x, double _y) 23 { 24 x = _x; 25 y = _y; 26 } 27 28 inline void scan() 29 { 30 scanf("%lf%lf", &x, &y); 31 } 32 33 inline bool operator == (const Point b) const 34 { 35 return sgn(x - b.x) == 0 && sgn(y - b.y) == 0; 36 } 37 38 inline Point operator - (const Point &b) const 39 { 40 return Point(x - b.x, y - b.y); 41 } 42 43 inline double operator ^ (const Point &b) const 44 { 45 return x * b.y - y * b.x; 46 } 47 48 inline double operator * (const Point &b) const 49 { 50 return x * b.x + y * b.y; 51 } 52 53 inline double distance(Point p) 54 { 55 return hypot(x - p.x, y - p.y); 56 } 57 58 }; 59 60 struct Line 61 { 62 Point s, e; 63 inline Line() {} 64 inline Line(Point _s, Point _e) 65 { 66 s = _s; 67 e = _e; 68 } 69 70 inline void scan() 71 { 72 s.scan(); e.scan(); 73 } 74 75 inline double length() 76 { 77 return s.distance(e); 78 } 79 80 inline double dispointtoline(Point p) 81 { 82 return fabs((p - s) ^ (e - s)) / length(); 83 } 84 85 inline double dispointtoseg(Point p) 86 { 87 if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0) 88 return min(p.distance(s), p.distance(e)); 89 return dispointtoline(p); 90 } 91 92 inline bool pointonseg(Point p) 93 { 94 return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0; 95 } 96 97 inline int segcrossseg(Line v) 98 { 99 int d1 = sgn((e - s) ^ (v.s - s)); 100 int d2 = sgn((e - s) ^ (v.e - s)); 101 int d3 = sgn((v.e - v.s) ^ (s - v.s)); 102 int d4 = sgn((v.e - v.s) ^ (e - v.s)); 103 if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 2; 104 return (d1 == 0 && sgn((v.s - s) * (v.e - e)) <= 0) || (d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) || (d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) || (d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0); 105 } 106 107 }line[N]; 108 109 struct Circle 110 { 111 Point p; 112 double r; 113 inline Circle() {} 114 inline Circle(Point _p, double _r) 115 { 116 p = _p; 117 r = _r; 118 } 119 120 inline void scan() 121 { 122 p.scan(); 123 scanf("%lf", &r); 124 } 125 126 }circle[N]; 127 128 struct Triangle 129 { 130 Point a, b, c; 131 inline Triangle() {} 132 inline Triangle(Point _a, Point _b, Point _c) 133 { 134 a = _a; 135 b = _b; 136 c = _c; 137 } 138 139 inline void scan() 140 { 141 a.scan(); b.scan(); c.scan(); 142 } 143 144 }triangle[N]; 145 146 int vis[N]; 147 int n; 148 Point S, T; 149 150 double G[N][N]; 151 152 inline double work11(int i, int j) 153 { 154 if (line[i].segcrossseg(line[j]) > 0) return 0.0; 155 double ans = INF * 1.0; 156 ans = min(ans, line[i].dispointtoseg(line[j].s)); 157 ans = min(ans, line[i].dispointtoseg(line[j].e)); 158 ans = min(ans, line[j].dispointtoseg(line[i].s)); 159 ans = min(ans, line[j].dispointtoseg(line[i].e)); 160 return ans; 161 } 162 163 inline double work12(int i, int j) 164 { 165 return max(0.0, line[i].dispointtoseg(circle[j].p) - circle[j].r); 166 } 167 168 inline double work13(int i, int j) 169 { 170 Point a = triangle[j].a, b = triangle[j].b, c = triangle[j].c; 171 if (line[i].segcrossseg(Line(a, b)) > 0) return 0.0; 172 if (line[i].segcrossseg(Line(a, c)) > 0) return 0.0; 173 if (line[i].segcrossseg(Line(b, c)) > 0) return 0.0; 174 double ans = INF * 1.0; 175 ans = min(ans, line[i].dispointtoseg(a)); 176 ans = min(ans, line[i].dispointtoseg(b)); 177 ans = min(ans, line[i].dispointtoseg(c)); 178 179 Point s = line[i].s, e = line[i].e; 180 181 ans = min(ans, Line(a, b).dispointtoseg(s)); 182 ans = min(ans, Line(a, b).dispointtoseg(e)); 183 184 ans = min(ans, Line(a, c).dispointtoseg(s)); 185 ans = min(ans, Line(a, c).dispointtoseg(e)); 186 187 ans = min(ans, Line(b, c).dispointtoseg(s)); 188 ans = min(ans, Line(b, c).dispointtoseg(e)); 189 190 return ans; 191 } 192 193 inline double work22(int i, int j) 194 { 195 Point c1 = circle[i].p, c2 = circle[j].p; 196 double r1 = circle[i].r, r2 = circle[j].r; 197 return max(0.0, c1.distance(c2) - r1 - r2); 198 } 199 200 inline double work23(int i, int j) 201 { 202 Point p = circle[j].p; double r = circle[j].r; 203 Point a = triangle[i].a, b = triangle[i].b, c = triangle[i].c; 204 double ans = INF * 1.0; 205 ans = min(ans, max(0.0, Line(a, b).dispointtoseg(p) - r)); 206 ans = min(ans, max(0.0, Line(a, c).dispointtoseg(p) - r)); 207 ans = min(ans, max(0.0, Line(b, c).dispointtoseg(p) - r)); 208 return ans; 209 } 210 211 inline double work33(int i, int j) 212 { 213 Point a = triangle[i].a, b = triangle[i].b, c = triangle[i].c; 214 Point aa = triangle[j].a, bb = triangle[j].b, cc = triangle[j].c; 215 216 if (Line(a, b).segcrossseg(Line(aa, bb)) > 0) return 0.0; 217 if (Line(a, b).segcrossseg(Line(aa, cc)) > 0) return 0.0; 218 if (Line(a, b).segcrossseg(Line(bb, cc)) > 0) return 0.0; 219 220 if (Line(a, c).segcrossseg(Line(aa, bb)) > 0) return 0.0; 221 if (Line(a, c).segcrossseg(Line(aa, cc)) > 0) return 0.0; 222 if (Line(a, c).segcrossseg(Line(bb, cc)) > 0) return 0.0; 223 224 if (Line(b, c).segcrossseg(Line(aa, bb)) > 0) return 0.0; 225 if (Line(b, c).segcrossseg(Line(aa, cc)) > 0) return 0.0; 226 if (Line(b, c).segcrossseg(Line(bb, cc)) > 0) return 0.0; 227 228 double ans = INF * 1.0; 229 230 ans = min(ans, Line(a, b).dispointtoseg(aa)); 231 ans = min(ans, Line(a, b).dispointtoseg(bb)); 232 ans = min(ans, Line(a, b).dispointtoseg(cc)); 233 234 ans = min(ans, Line(a, c).dispointtoseg(aa)); 235 ans = min(ans, Line(a, c).dispointtoseg(bb)); 236 ans = min(ans, Line(a, c).dispointtoseg(cc)); 237 238 ans = min(ans, Line(b, c).dispointtoseg(aa)); 239 ans = min(ans, Line(b, c).dispointtoseg(bb)); 240 ans = min(ans, Line(b, c).dispointtoseg(cc)); 241 242 ans = min(ans, Line(aa, bb).dispointtoseg(a)); 243 ans = min(ans, Line(aa, bb).dispointtoseg(b)); 244 ans = min(ans, Line(aa, bb).dispointtoseg(c)); 245 246 ans = min(ans, Line(aa, cc).dispointtoseg(a)); 247 ans = min(ans, Line(aa, cc).dispointtoseg(b)); 248 ans = min(ans, Line(aa, cc).dispointtoseg(c)); 249 250 ans = min(ans, Line(bb, cc).dispointtoseg(a)); 251 ans = min(ans, Line(bb, cc).dispointtoseg(b)); 252 ans = min(ans, Line(bb, cc).dispointtoseg(c)); 253 254 return ans; 255 } 256 257 inline double work01(int vis, int i) 258 { 259 Point a = vis ? T : S; 260 return (line[i].dispointtoseg(a)); 261 } 262 263 inline double work02(int vis, int i) 264 { 265 Point a = vis ? T : S; 266 Point p = circle[i].p; double r = circle[i].r; 267 return max(0.0, a.distance(p) - r); 268 } 269 270 struct Polygon 271 { 272 int n; 273 Point p[3]; 274 Line l[3]; 275 inline Polygon() {} 276 inline Polygon(Triangle r) 277 { 278 n = 3; 279 p[0] = r.a, p[1] = r.b, p[2] = r.c; 280 l[0] = Line(p[0], p[1]); 281 l[1] = Line(p[0], p[2]); 282 l[2] = Line(p[1], p[2]); 283 } 284 285 inline int relationpoint(Point q) 286 { 287 for (int i = 0; i < n; ++i) 288 if (p[i] == q) return 3; 289 290 for (int i = 0; i < n; ++i) 291 if (l[i].pointonseg(q)) return 2; 292 293 int cnt = 0; 294 for (int i = 0; i < n; ++i) 295 { 296 int j = (i + 1) % n; 297 int k = sgn((q - p[j]) ^ (p[i] - p[j])); 298 int u = sgn(p[i].y - q.y); 299 int v = sgn(p[j].y - q.y); 300 if (k > 0 && u < 0 && v >= 0) cnt++; 301 if (k < 0 && v < 0 && u >= 0) cnt--; 302 } 303 return cnt != 0; 304 } 305 }; 306 307 308 inline double work03(int vis, int i) 309 { 310 Point p = vis ? T : S; 311 Polygon tmp = Polygon(triangle[i]); 312 if (tmp.relationpoint(p) > 0) return 0.0; 313 314 double ans = INF * 1.0; 315 316 ans = min(ans, tmp.l[0].dispointtoseg(p)); 317 ans = min(ans, tmp.l[1].dispointtoseg(p)); 318 ans = min(ans, tmp.l[2].dispointtoseg(p)); 319 320 return ans; 321 } 322 323 bool used[N]; 324 double lowcost[N]; 325 326 inline void Dijkstra() 327 { 328 for (int i = 0; i <= n + 1; ++i) 329 { 330 lowcost[i] = INF * 1.0; 331 used[i] = false; 332 } 333 lowcost[0] = 0; 334 for (int j = 0; j <= n + 1; ++j) 335 { 336 int k = -1; 337 double Min = INF * 1.0; 338 for (int i = 0; i <= n + 1; ++i) 339 { 340 if (!used[i] && lowcost[i] < Min) 341 { 342 Min = lowcost[i]; 343 k = i; 344 } 345 } 346 347 if (k == -1) break; 348 used[k] = true; 349 350 for (int i = 0; i <= n + 1; ++i) 351 { 352 if (!used[i] && lowcost[k] + G[k][i] < lowcost[i]) 353 { 354 lowcost[i] = lowcost[k] + G[k][i]; 355 } 356 } 357 } 358 } 359 360 int main() 361 { 362 #ifdef LOCAL 363 freopen("Test.in", "r", stdin); 364 #endif 365 while (scanf("%lf%lf%lf%lf", &S.x, &S.y, &T.x, &T.y) != EOF) 366 { 367 scanf("%d", &n); 368 for (int i = 1; i <= n; ++i) 369 { 370 scanf("%d", vis + i); 371 if (vis[i] == 1) 372 line[i].scan(); 373 else if (vis[i] == 2) 374 circle[i].scan(); 375 else 376 triangle[i].scan(); 377 } 378 for (int i = 1; i <= n; ++i) 379 { 380 for (int j = i + 1; j <= n; ++j) 381 { 382 if (vis[i] == 1) 383 { 384 if (vis[j] == 1) 385 G[i][j] = G[j][i] = work11(i, j); 386 else if (vis[j] == 2) 387 G[i][j] = G[j][i] = work12(i, j); 388 else if (vis[j] == 3) 389 G[i][j] = G[j][i] = work13(i, j); 390 } 391 else if (vis[i] == 2) 392 { 393 if (vis[j] == 1) 394 G[i][j] = G[j][i] = work12(j, i); 395 else if (vis[j] == 2) 396 G[i][j] = G[j][i] = work22(i, j); 397 else if (vis[j] == 3) 398 G[i][j] = G[j][i] = work23(i, j); 399 } 400 else if (vis[i] == 3) 401 { 402 if (vis[j] == 1) 403 G[i][j] = G[j][i] = work13(j, i); 404 else if (vis[j] == 2) 405 G[i][j] = G[j][i] = work23(j, i); 406 else if (vis[j] == 3) 407 G[i][j] = G[j][i] = work33(i, j); 408 } 409 } 410 } 411 412 for (int i = 1; i <= n; ++i) 413 { 414 if (vis[i] == 1) 415 { 416 G[0][i] = G[i][0] = work01(0, i); 417 G[n + 1][i] = G[i][n + 1] = work01(1, i); 418 } 419 else if (vis[i] == 2) 420 { 421 G[0][i] = G[i][0] = work02(0, i); 422 G[n + 1][i] = G[i][n + 1] = work02(1, i); 423 } 424 else if (vis[i] == 3) 425 { 426 G[0][i] = G[i][0] = work03(0, i); 427 G[n + 1][i] = G[i][n + 1] = work03(1, i); 428 } 429 } 430 431 G[0][n + 1] = G[n + 1][0] = S.distance(T); 432 433 //for (int i = 0; i <= n + 1; ++i) 434 // for (int j = 0; j <= n + 1; ++j) 435 // printf("%.2f%c", G[i][j], " "[j == n + 1]); 436 437 Dijkstra(); 438 printf("%d ", (int)floor(lowcost[n + 1])); 439 } 440 return 0; 441 }
F：Poker
水。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define N 100010 6 7 int n; 8 int arr[N]; 9 int brr[N]; 10 int a[N]; 11 12 inline void Init() 13 { 14 memset(a, 0, sizeof a); 15 } 16 17 inline int lowbit(int x) 18 { 19 return x & (-x); 20 } 21 22 inline void update(int x, int val) 23 { 24 for (int i = x; i <= n; i += lowbit(i)) 25 a[i] += val; 26 } 27 28 inline int sum(int x) 29 { 30 int ans = 0; 31 for (int i = x; i > 0; i -= lowbit(i)) 32 ans += a[i]; 33 return ans; 34 } 35 36 inline bool check(int mid, int emp) 37 { 38 int tot = sum(mid); 39 return tot <= emp; 40 } 41 42 int main() 43 { 44 while (scanf("%d", &n) != EOF) 45 { 46 Init(); 47 for (int i = 1; i <= n; ++i) update(i, 1); 48 for(int i = 1; i <= n; ++i) 49 { 50 scanf("%d",&arr[i]); 51 } 52 for (int i = 1; i <= n; ++i) 53 { 54 int index = (int)floor(sqrt(n - i + 1)); 55 int l = 1, r = n, id; 56 while (r - l >= 0) 57 { 58 int mid = (l + r) >> 1; 59 int tot = sum(mid); 60 if (tot == index) 61 id = mid; 62 if (tot >= index) 63 r = mid - 1; 64 else 65 l = mid + 1; 66 } 67 brr[id] = arr[i]; 68 update(id, -1); 69 } 70 for (int i = 1; i <= n; ++i) printf("%d%c", brr[i], " "[i == n]); 71 } 72 return 0; 73 }
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 #define N 100010 6 7 int n; 8 int arr[N]; 9 int brr[N]; 10 11 int main() 12 { 13 while(~scanf("%d",&n)) 14 { 15 for(int i = 1; i <= n; ++i) 16 { 17 scanf("%d",&arr[i]); 18 } 19 vector<int>vec; 20 for(int i = n; i >= 1;--i) 21 { 22 int tmp = floor(sqrt(n - i + 1)); 23 vec.insert(vec.begin() + tmp - 1, arr[i]); 24 } 25 for(int i = 0; i < n; ++i) 26 { 27 printf("%d%c",vec[i]," "[i == n - 1]); 28 } 29 } 30 return 0; 31 }