CVBB ACM Team

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

<html>
<head>
<meta charset='UTF-8'><meta name='viewport' content='width=device-width initial-scale=1'>
<title>Codeforces Round #664 (Div. 2)</title></head>
<body><h1>Codeforces Round #664 (Div. 2)</h1>
<h2>A.  <a href='https://codeforces.com/contest/1395/problem/A'>Boboniu Likes to Color Balls</a> </h2>
<p>构成回文串的充要条件是，出现奇数次的字符最多有1种。</p>
<p>进行操作后会使得rgbw四种字符的奇偶性改变。</p>
<p>分别根据进行操作/不进行操作判断</p>
<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
 
using namespace std;
typedef long long LL;
 
int main() {
    int t;
    cin &gt;&gt; t;
    while (t--) {
        LL r, g, b, w;
        cin &gt;&gt; r &gt;&gt; g &gt;&gt; b &gt;&gt; w;
        if ((r == g) &amp;&amp; (r == b)) {
            cout &lt;&lt; &quot;Yes&quot; &lt;&lt; endl;
        } else {
            int c1 = (r &amp; 1) + (g &amp; 1) + (b &amp; 1);
            int c2 = w &amp; 1;
            int cnte = c1 + (w &amp; 1);
            int cnt2 = 3 - c1 + 1 - (w &amp; 1);
            if (cnte == 1 || cnte == 0 || (r &gt; 0 &amp;&amp; g &gt; 0 &amp;&amp; b &gt; 0 &amp;&amp; (cnt2 == 1 || cnt2 == 0))) {
                cout &lt;&lt; &quot;Yes&quot; &lt;&lt; endl;
            }
            else cout&lt;&lt;&quot;No&quot;&lt;&lt;endl;
        }
    }
}
</code></pre>
<p>&nbsp;</p>
<h2>B.  <a href='https://codeforces.com/contest/1395/problem/B'>Boboniu Plays Chess</a></h2>
<p>这里给出的覆盖策略是先走完当前行，再按顺序走完1-n行，跳过已走过的值。</p>
<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
 
using namespace std;
typedef long long LL;
 
int p[200][200] = {};
int pr(int x, int y){
    p[x][y] = 1;
    printf(&quot;%d %d\n&quot;, x, y);
}
 
int main() {
    int n, m, x, y;
    cin&gt;&gt;n&gt;&gt;m&gt;&gt;x&gt;&gt;y;
    p[x][y] = 1;
    pr(x, y);
    int xx = x;
    if(y &gt; 1){
        y = 1;
        pr(x, y);
    }
 
    int y1 = y;
    for (y = 1; y &lt;= m; ++y) {
        if(!p[x][y]){
            y1 = y;
            pr(x, y);
        }
    }
    y = y1;
 
    for (int i = 1; i &lt;= n; ++i) {
        if(i == xx){
            continue;
        }
        x = i;
        pr(x, y);
        if(y &gt; 1){
            y = 1;
            pr(x, y);
        }
        y1 = y;
        for (y = 1; y &lt;= m; ++y) {
            if(!p[x][y]){
                y1 = y;
                pr(x, y);
            }
        }
        y = y1;
    }
}
</code></pre>
<p>&nbsp;</p>
<h2>C. <a href='https://codeforces.com/contest/1395/problem/C'>Boboniu and Bit Operations</a></h2>
<p>贪心，使高位尽可能多地为0。从高位到低位枚举。如果结果中一位可以得到0，则清除所有使这一位得不到0的选项。</p>
<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
 
using namespace std;
typedef long long LL;

int main() {
    int n, m;
    int a[300], b[300], mi[300];
    cin&gt;&gt;n&gt;&gt;m;
    for (int i = 0; i &lt; n; ++i) {
        scanf(&quot;%d&quot;, a+i);
    }
    set&lt;int&gt; poss[300] = {};
    for (int i = 0; i &lt; m; ++i) {
        scanf(&quot;%d&quot;, b+i);
        for (int j = 0; j &lt; n; ++j) {
            poss[j].insert(b[i]);
        }
    }
    int ans = 0;
    for (int k = 8; k &gt;= 0; --k) {
        int kk = 1 &lt;&lt; k;
        bool okA = true;
        for (int i = 0; i &lt; n; ++i) {
            bool ok = false;
            for(int p : poss[i]){
                if((p &amp; a[i] &amp; kk) == 0){
                    ok = true;
                    break;
                }
            }
            if(!ok){
                okA = false;
                break;
            }
        }
 
        if(!okA){
            ans |= kk;
        }
        else{
            for (int i = 0; i &lt; n; ++i) {
                for(auto it = poss[i].begin(); it != poss[i].end(); ){
                    if(*it &amp; a[i] &amp; kk){
                        poss[i].erase(it++);
                    }else it++;
                }
            }
        }
    }
    cout&lt;&lt;ans&lt;&lt;endl;
}
</code></pre>
<p>&nbsp;</p>
<h2>D.  <a href='https://codeforces.com/contest/1395/problem/D'>Boboniu Chats with Du</a></h2>
<p>这道题不同情况下，最优解中被禁言的次数不一定...</p>
<p>因此需要枚举被禁言次数的可能情况。</p>
<p>在禁言次数一定时，取尽可能大的值放入未被禁言的部分中，求前缀和后可以O(1)得到结果。</p>
<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
 
using namespace std;
typedef long long LL;
 
 
int a[100006];
LL sum[100006] = {};
 
int main() {
    int n, m, d;
    cin &gt;&gt; n &gt;&gt; d &gt;&gt; m;
    for (int i = 0; i &lt; n; ++i) {
        scanf(&quot;%d&quot;, a + i);
    }
 
    sort(a, a + n);
    int cnt1 = 0;
    for (int j = 0; j &lt; n; ++j) {
        sum[j+1] = sum[j] + a[j];
        if (a[j] &gt; m)cnt1++;
    }
 
    LL ans = 0;
    for (int i = 0; n &gt;= (i - 1) * (d + 1) + 1; ++i) {
        if (cnt1 &lt; i) continue;
        if (cnt1 &gt; i * (d + 1)) continue;
        int extra = i == 0  ? n : n - (i - 1) * (d + 1) - 1;
        int s = n - cnt1;
        ans = max(ans, sum[n] - sum[n - i] + sum[s] - sum[max(0, s - extra)]);
    }
 
    cout&lt;&lt;ans&lt;&lt;endl;
}
</code></pre>
<p>&nbsp;</p>
</body>
</html>
CVBB ACM Team

用户工具

站点工具

页面工具
