CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

<html>
<head>
<meta charset='UTF-8'><meta name='viewport' content='width=device-width initial-scale=1'>
<title>abc174</title></head>
<body><h1>A. Air Conditioner</h1>
<p>根据题意输出结果。</p>
<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
using namespace std;
#define MAX 300005
int main() {
    int X;
    cin&gt;&gt;X;
    X &gt;= 30 ? cout&lt;&lt;&quot;Yes&quot; : cout&lt;&lt;&quot;No&quot;;
}
</code></pre>
<p>&nbsp;</p>
<h1>B. Distance</h1>
<p>输出距离在D以下的点的个数</p>
<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
using namespace std;
typedef long long LL;
#define MAX 300005
int main() {
    LL n, d;
    cin&gt;&gt;n&gt;&gt;d;
    int ans = 0;
    for (int i = 0; i &lt; n; ++i) {
        LL x, y;
        scanf(&quot;%lld%lld&quot;, &amp;x,&amp;y);
        if(x * x + y * y &lt;= d * d)ans++;
    }
    cout&lt;&lt;ans;
}
</code></pre>
<p>&nbsp;</p>
<h2>C. Respect</h2>
<p>输出由数字7组成的数7777...中，能被K整除的最小的数。</p>
<p>根据递推式 <span class="MathJax_SVG" tabindex="-1" style="font-size: 100%; display: inline-block;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="24.412ex" height="2.577ex" viewBox="0 -806.1 10510.7 1109.7" role="img" focusable="false" style="vertical-align: -0.705ex;"><defs><path stroke-width="0" id="E105-MJMATHI-61" d="M33 157Q33 258 109 349T280 441Q331 441 370 392Q386 422 416 422Q429 422 439 414T449 394Q449 381 412 234T374 68Q374 43 381 35T402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487Q506 153 506 144Q506 138 501 117T481 63T449 13Q436 0 417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157ZM351 328Q351 334 346 350T323 385T277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q217 26 254 59T298 110Q300 114 325 217T351 328Z"></path><path stroke-width="0" id="E105-MJMATHI-6E" d="M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z"></path><path stroke-width="0" id="E105-MJMAIN-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path><path stroke-width="0" id="E105-MJMAIN-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path stroke-width="0" id="E105-MJMAIN-3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path><path stroke-width="0" id="E105-MJMAIN-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path stroke-width="0" id="E105-MJMAIN-2217" d="M229 286Q216 420 216 436Q216 454 240 464Q241 464 245 464T251 465Q263 464 273 456T283 436Q283 419 277 356T270 286L328 328Q384 369 389 372T399 375Q412 375 423 365T435 338Q435 325 425 315Q420 312 357 282T289 250L355 219L425 184Q434 175 434 161Q434 146 425 136T401 125Q393 125 383 131T328 171L270 213Q283 79 283 63Q283 53 276 44T250 35Q231 35 224 44T216 63Q216 80 222 143T229 213L171 171Q115 130 110 127Q106 124 100 124Q87 124 76 134T64 161Q64 166 64 169T67 175T72 181T81 188T94 195T113 204T138 215T170 230T210 250L74 315Q65 324 65 338Q65 353 74 363T98 374Q106 374 116 368T171 328L229 286Z"></path><path stroke-width="0" id="E105-MJMAIN-30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path><path stroke-width="0" id="E105-MJMAIN-37" d="M55 458Q56 460 72 567L88 674Q88 676 108 676H128V672Q128 662 143 655T195 646T364 644H485V605L417 512Q408 500 387 472T360 435T339 403T319 367T305 330T292 284T284 230T278 162T275 80Q275 66 275 52T274 28V19Q270 2 255 -10T221 -22Q210 -22 200 -19T179 0T168 40Q168 198 265 368Q285 400 349 489L395 552H302Q128 552 119 546Q113 543 108 522T98 479L95 458V455H55V458Z"></path><path stroke-width="0" id="E105-MJMAIN-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path><path stroke-width="0" id="E105-MJMAIN-25" d="M465 605Q428 605 394 614T340 632T319 641Q332 608 332 548Q332 458 293 403T202 347Q145 347 101 402T56 548Q56 637 101 693T202 750Q241 750 272 719Q359 642 464 642Q580 642 650 732Q662 748 668 749Q670 750 673 750Q682 750 688 743T693 726Q178 -47 170 -52Q166 -56 160 -56Q147 -56 142 -45Q137 -36 142 -27Q143 -24 363 304Q469 462 525 546T581 630Q528 605 465 605ZM207 385Q235 385 263 427T292 548Q292 617 267 664T200 712Q193 712 186 709T167 698T147 668T134 615Q132 595 132 548V527Q132 436 165 403Q183 385 203 385H207ZM500 146Q500 234 544 290T647 347Q699 347 737 292T776 146T737 0T646 -56Q590 -56 545 0T500 146ZM651 -18Q679 -18 707 24T736 146Q736 215 711 262T644 309Q637 309 630 306T611 295T591 265T578 212Q577 200 577 146V124Q577 -18 647 -18H651Z"></path><path stroke-width="0" id="E105-MJMATHI-4B" d="M285 628Q285 635 228 637Q205 637 198 638T191 647Q191 649 193 661Q199 681 203 682Q205 683 214 683H219Q260 681 355 681Q389 681 418 681T463 682T483 682Q500 682 500 674Q500 669 497 660Q496 658 496 654T495 648T493 644T490 641T486 639T479 638T470 637T456 637Q416 636 405 634T387 623L306 305Q307 305 490 449T678 597Q692 611 692 620Q692 635 667 637Q651 637 651 648Q651 650 654 662T659 677Q662 682 676 682Q680 682 711 681T791 680Q814 680 839 681T869 682Q889 682 889 672Q889 650 881 642Q878 637 862 637Q787 632 726 586Q710 576 656 534T556 455L509 418L518 396Q527 374 546 329T581 244Q656 67 661 61Q663 59 666 57Q680 47 717 46H738Q744 38 744 37T741 19Q737 6 731 0H720Q680 3 625 3Q503 3 488 0H478Q472 6 472 9T474 27Q478 40 480 43T491 46H494Q544 46 544 71Q544 75 517 141T485 216L427 354L359 301L291 248L268 155Q245 63 245 58Q245 51 253 49T303 46H334Q340 37 340 35Q340 19 333 5Q328 0 317 0Q314 0 280 1T180 2Q118 2 85 2T49 1Q31 1 31 11Q31 13 34 25Q38 41 42 43T65 46Q92 46 125 49Q139 52 144 61Q147 65 216 339T285 628Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E105-MJMATHI-61" x="0" y="0"></use><g transform="translate(529,-150)"><use transform="scale(0.707)" xlink:href="#E105-MJMATHI-6E" x="0" y="0"></use><use transform="scale(0.707)" xlink:href="#E105-MJMAIN-2B" x="600" y="0"></use><use transform="scale(0.707)" xlink:href="#E105-MJMAIN-31" x="1378" y="0"></use></g><use xlink:href="#E105-MJMAIN-3D" x="2234" y="0"></use><use xlink:href="#E105-MJMAIN-28" x="3290" y="0"></use><g transform="translate(3679,0)"><use xlink:href="#E105-MJMATHI-61" x="0" y="0"></use><use transform="scale(0.707)" xlink:href="#E105-MJMATHI-6E" x="748" y="-213"></use></g><use xlink:href="#E105-MJMAIN-2217" x="4954" y="0"></use><g transform="translate(5677,0)"><use xlink:href="#E105-MJMAIN-31"></use><use xlink:href="#E105-MJMAIN-30" x="500" y="0"></use></g><use xlink:href="#E105-MJMAIN-2B" x="6899" y="0"></use><use xlink:href="#E105-MJMAIN-37" x="7899" y="0"></use><use xlink:href="#E105-MJMAIN-29" x="8399" y="0"></use><use xlink:href="#E105-MJMAIN-25" x="8788" y="0"></use><use xlink:href="#E105-MJMATHI-4B" x="9621" y="0"></use></g></svg></span><script type="math/tex">a_{n+1} = (a_n * 10 + 7) \% K</script>寻找循环节。循环节长度不超过K。</p>
<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
using namespace std;
typedef long long LL;
#define MAX 300005
const int maxk = 1e6+5;
bool a[maxk];
int main() {
    LL k;
    cin&gt;&gt;k;
 
    int x = 7;
    int ans = -1;
    int c = 1;
    while(!a[x % k]){
        if(x % k == 0){
            ans = c;
            break;
        }
        a[x % k] = 1;
        c++;
        x = x * 10 + 7;
        x %= k;
    }
 
    cout&lt;&lt;ans&lt;&lt;endl;
 
}
</code></pre>
<h2>D. Alter Alter</h2>
<p>通过交换、修改将一个WR组成的序列修改为不含WR子串的序列。</p>
<p>所有R必须位于W左侧。统计不满足条件字符的个数即可。这里不需要修改操作。</p>
<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
using namespace std;
typedef long long LL;
#define MAX 300005
const int maxk = 1e6+5;
int main() {
    LL n;
    cin&gt;&gt;n;
    string s;
    cin&gt;&gt;s;
 
    int cntR = 0;
    for (int i = 0; i &lt; n; ++i) {
        if(s[i] == &#39;R&#39;)cntR++;
    }
 
 
    int rev = 0;
    for (int j = 0; j &lt; n; ++j) {
        if(j &lt; cntR){
            if(s[j] == &#39;W&#39;)rev++;
        }
        else if(s[j] == &#39;R&#39;) rev++;
    }
 
    cout&lt;&lt;(rev)/2&lt;&lt;endl;
}
</code></pre>
<h2>E. Logs</h2>
<p>将N个木棍进行K次切分，求最长长度向上取整的最小值。</p>
<p>二分查找可行解。如果每个木棍的需要的切分次数之和小于K则可行。</p>
<p>要注意一下二分时中值为0的情况。</p>
<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
using namespace std;
typedef long long LL;
#define MAX 300005
const int maxn = 2e5+10;
int a[maxn];
int main() {
    LL n, k;
    cin&gt;&gt;n&gt;&gt;k;
 
    int cntR = 0;
    int ma = 0;
    for (int i = 0; i &lt; n; ++i) {
        scanf(&quot;%d&quot;, a+i);
        ma = max(ma, a[i]);
    }
    LL l = 0, r = ma;
    while(l &lt; r){
        int p =  0;
        int m = (l + r + 1) / 2;
        if(m == 0) {
            break;
        }
        else for (int i = 0; i &lt; n; ++i) {
            p += (a[i] + m - 1)/ m;
        }
        if(p &gt; d) l = m;
        else r = m - 1;
    }
    if(r == 0){
        cout&lt;&lt;1;
        return 0;
    }
    int p =  0;
    for (int i = 0; i &lt; n; ++i) {
        p += (a[i] + r - 1)/ r;
    }
    if(p &gt; d)cout&lt;&lt;r+1&lt;&lt;endl;
    else cout&lt;&lt;r&lt;&lt;endl;
}
</code></pre>
<h2>F. <strong>Range Set Query</strong></h2>
<p>给定一组数，询问[l, r]区间内不同数的个数</p>
<p>树状数组查询[0,r]、[0,l]区间内的种类的个数。为了防止[0,r)中多计算而[l, r]区间漏计，只将r之前数字的最后一次出现视为唯一出现，倒数第二次出现之前的种类数-1。离线查询得到答案。</p>
<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
 
using namespace std;
const int N = 500020;
int n, q, c[N], ans[N], tree[N &lt;&lt; 1], last[N], h[N &lt;&lt; 1];
struct node {
    int l, r, num;
} qq[N];
 
bool cmp(node x, node y) { return x.r &lt; y.r || (x.r == y.r &amp;&amp; x.l &lt; y.l); }
 
void insert(int x, int y) { for (; x &lt;= n; x += x &amp; -x) tree[x] += y; }
 
int query(int x) {
    int y = 0;
    for (; x; x -= x &amp; -x) y += tree[x];
    return y;
}
 
int main() {
    scanf(&quot;%d%d&quot;, &amp;n, &amp;q);
    for (int i = 1; i &lt;= n; i++) {
        scanf(&quot;%d&quot;, &amp;c[i]);
        last[i] = h[c[i]];
        h[c[i]] = i;
    }
 
    for (int i = 0; i &lt; q; i++) {
        scanf(&quot;%d%d&quot;, &amp;qq[i].l, &amp;qq[i].r), qq[i].num = i;
    }
    sort(qq, qq + q, cmp);
    int tmp = 0;
    for (int i = 0; i &lt; q; i++) {
        while (tmp &lt; qq[i].r) {
            tmp++;
            if (last[tmp]) insert(last[tmp], -1);
            insert(tmp, 1);
        }
        ans[qq[i].num] = query(tmp) - query(qq[i].l - 1);
    }
    for (int i = 0; i &lt; q; i++) {
        printf(&quot;%d\n&quot;, ans[i]);
    }
    return 0;
} 
</code></pre>
<p>&nbsp;</p>
</body>
</html>
CVBB ACM Team

用户工具

站点工具

页面工具
