差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:too_low:cf1395_hj [2020/08/14 16:44]
jim 创建
+++ 2020-2021:teams:too_low:cf1395_hj [2020/08/14 16:46] (当前版本)
jim Codeforces Round #664 (Div. 2)
@@ 行 1: / 行 1: @@
-= Codeforces Round #664 (Div. 2) =
-== A. [https://codeforces.com/contest/1395/problem/A Boboniu Likes to Color Balls]  ==
-构成回文串的充要条件是，出现奇数次的字符最多有1种。
-进行操作后会使得rgbw四种字符的奇偶性改变。
-分别根据进行操作/不进行操作判断
-<source lang="cpp">#include <bits/stdc++.h>
+<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;
-    cin >> t;
     while (t--) {
         LL r, g, b, w;
+        cin &gt;&gt; r &gt;&gt; g &gt;&gt; b &gt;&gt; w;
-        cin >> r >> g >> b >> w;
+        if ((r == g) &amp;&amp; (r == b)) {
+            cout &lt;&lt; &quot;Yes&quot; &lt;&lt; endl;
-        if ((r == g) && (r == b)) {
-            cout << "Yes" << endl;
         } else {
+            int c1 = (r &amp; 1) + (g &amp; 1) + (b &amp; 1);
-            int c1 = (r & 1) + (g & 1) + (b & 1);
+            int c2 = w &amp; 1;
+            int cnte = c1 + (w &amp; 1);
-            int c2 = w & 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))) {
-            int cnte = c1 + (w & 1);
+                cout &lt;&lt; &quot;Yes&quot; &lt;&lt; endl;
-            int cnt2 = 3 - c1 + 1 - (w & 1);
-            if (cnte == 1 || cnte == 0 || (r > 0 && g > 0 && b > 0 && (cnt2 == 1 || cnt2 == 0))) {
-                cout << "Yes" << endl;
             }
+            else cout&lt;&lt;&quot;No&quot;&lt;&lt;endl;
-            else cout<<"No"<<endl;
         }
     }
+}
-}</source>
+</code></pre>
+<p>&nbsp;</p>
+<h2>B.  <a href='https://codeforces.com/contest/1395/problem/B'>Boboniu Plays Chess</a></h2>
-== B. [https://codeforces.com/contest/1395/problem/B Boboniu Plays Chess] ==
+<p>这里给出的覆盖策略是先走完当前行，再按顺序走完1-n行，跳过已走过的值。</p>
+<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
-这里给出的覆盖策略是先走完当前行，再按顺序走完1-n行，跳过已走过的值。
-<source lang="cpp">#include <bits/stdc++.h>
 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);
-    printf("%d %d\n", x, y);
 }
 int main() {
     int n, m, x, y;
+    cin&gt;&gt;n&gt;&gt;m&gt;&gt;x&gt;&gt;y;
-    cin>>n>>m>>x>>y;
     p[x][y] = 1;
     pr(x, y);
     int xx = x;
+    if(y &gt; 1){
-    if(y > 1){
         y = 1;
         pr(x, y);
     }
     int y1 = y;
+    for (y = 1; y &lt;= m; ++y) {
-    for (y = 1; y <= m; ++y) {
         if(!p[x][y]){
             y1 = y;
             pr(x, y);
         }
     }
     y = y1;
+    for (int i = 1; i &lt;= n; ++i) {
-    for (int i = 1; i <= n; ++i) {
         if(i == xx){
             continue;
         }
         x = i;
         pr(x, y);
+        if(y &gt; 1){
-        if(y > 1){
             y = 1;
             pr(x, y);
         }
         y1 = y;
+        for (y = 1; y &lt;= m; ++y) {
-        for (y = 1; y <= m; ++y) {
             if(!p[x][y]){
                 y1 = y;
                 pr(x, y);
             }
         }
         y = y1;
     }
+}
-}</source>
+</code></pre>
+<p>&nbsp;</p>
+<h2>C. <a href='https://codeforces.com/contest/1395/problem/C'>Boboniu and Bit Operations</a></h2>
-== C. [https://codeforces.com/contest/1395/problem/C Boboniu and Bit Operations] ==
+<p>贪心，使高位尽可能多地为0。从高位到低位枚举。如果结果中一位可以得到0，则清除所有使这一位得不到0的选项。</p>
+<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
-贪心，使高位尽可能多地为0。从高位到低位枚举。如果结果中一位可以得到0，则清除所有使这一位得不到0的选项。
-<source lang="cpp">#include <bits/stdc++.h>
 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;
-    cin>>n>>m;
+    for (int i = 0; i &lt; n; ++i) {
+        scanf(&quot;%d&quot;, a+i);
-    for (int i = 0; i < n; ++i) {
-        scanf("%d", a+i);
     }
+    set&lt;int&gt; poss[300] = {};
-    set<int> poss[300] = {};
+    for (int i = 0; i &lt; m; ++i) {
+        scanf(&quot;%d&quot;, b+i);
-    for (int i = 0; i < m; ++i) {
+        for (int j = 0; j &lt; n; ++j) {
-        scanf("%d", b+i);
-        for (int j = 0; j < n; ++j) {
             poss[j].insert(b[i]);
         }
     }
     int ans = 0;
+    for (int k = 8; k &gt;= 0; --k) {
-    for (int k = 8; k >= 0; --k) {
+        int kk = 1 &lt;&lt; k;
-        int kk = 1 << k;
         bool okA = true;
+        for (int i = 0; i &lt; n; ++i) {
-        for (int i = 0; i < n; ++i) {
             bool ok = false;
             for(int p : poss[i]){
+                if((p &amp; a[i] &amp; kk) == 0){
-                if((p & a[i] & kk) == 0){
                     ok = true;
                     break;
                 }
             }
             if(!ok){
                 okA = false;
                 break;
             }
         }
         if(!okA){
             ans |= kk;
         }
         else{
+            for (int i = 0; i &lt; n; ++i) {
-            for (int i = 0; i < n; ++i) {
                 for(auto it = poss[i].begin(); it != poss[i].end(); ){
+                    if(*it &amp; a[i] &amp; kk){
-                    if(*it & a[i] & kk){
                         poss[i].erase(it++);
                     }else it++;
                 }
             }
         }
     }
+    cout&lt;&lt;ans&lt;&lt;endl;
-    cout<<ans<<endl;
+}
+</code></pre>
-}</source>
+<p>&nbsp;</p>
+<h2>D.  <a href='https://codeforces.com/contest/1395/problem/D'>Boboniu Chats with Du</a></h2>
+<p>这道题不同情况下，最优解中被禁言的次数不一定...</p>
-== D. [https://codeforces.com/contest/1395/problem/D Boboniu Chats with Du] ==
+<p>因此需要枚举被禁言次数的可能情况。</p>
+<p>在禁言次数一定时，取尽可能大的值放入未被禁言的部分中，求前缀和后可以O(1)得到结果。</p>
-这道题不同情况下，最优解中被禁言的次数不一定...
+<pre><code class='language-cpp' lang='cpp'>#include &lt;bits/stdc++.h&gt;
-因此需要枚举被禁言次数的可能情况。
-在禁言次数一定时，取尽可能大的值放入未被禁言的部分中，求前缀和后可以O(1)得到结果。
-<source lang="cpp">#include <bits/stdc++.h>
 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;
-    cin >> n >> d >> m;
+    for (int i = 0; i &lt; n; ++i) {
+        scanf(&quot;%d&quot;, a + i);
-    for (int i = 0; i < n; ++i) {
-        scanf("%d", a + i);
     }
     sort(a, a + n);
     int cnt1 = 0;
+    for (int j = 0; j &lt; n; ++j) {
-    for (int j = 0; j < n; ++j) {
         sum[j+1] = sum[j] + a[j];
+        if (a[j] &gt; m)cnt1++;
-        if (a[j] > m)cnt1++;
     }
     LL ans = 0;
+    for (int i = 0; n &gt;= (i - 1) * (d + 1) + 1; ++i) {
-    for (int i = 0; n >= (i - 1) * (d + 1) + 1; ++i) {
+        if (cnt1 &lt; i) continue;
+        if (cnt1 &gt; i * (d + 1)) continue;
-        if (cnt1 < i) continue;
-        if (cnt1 > 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;
-    cout<<ans<<endl;
+}
+</code></pre>
-}</source>
+<p>&nbsp;</p>
+</body>
+</html>

CVBB ACM Team

用户工具

站点工具

差别

页面工具