title: CodeForces-Round#684-Div.2
tags:

  • ACM
  • CF
    abbrlink: 676fcf4a
    date: 2020-11-18 11:52:18

A. Buy the String

  1. #include<iostream>
  2. #include<cstdio>
  4. using namespace std;
  6. char c[1005];
  8. int main(){
  9.     int T;
  10.     int sum_1=0,sum_0=0,ans;
  11.     cin>>T;
  12.     while(T--)
  13.     {
  14.         int n,c0,c1,h;
  15.         cin>>n>>c0>>c1>>h;
  16.         for(int i=0;i<n;i++)
  17.         {
  18.             cin>>c[i];
  19.             if(c[i]=='1')   sum_1++;
  20.             else    sum_0++;
  21.         }
  22.         //cout<<sum_0<<endl<<sum_1<<endl;
  23.         ans=c0*sum_0+c1*sum_1;
  24.         /*if(c0==c1)
  25.             ans=c0*sum_0+c1*sum_1;
  26.         if(c0>c1)
  27.             ans=min((c1*(sum_1+sum_0))+sum_0*h, ans);
  28.         if(c0<c1)
  29.             ans=min(c0*(sum_1+sum_0)+sum_1*h, ans);*/
  30.         for(int i=1;i<=sum_0;i++)
  31.         {
  32.             int now=(i*h)+((sum_1+i)*c1)+(sum_0-i)*c0;
  33.             ans=min(ans, now);
  34.         }
  35.         for(int i=1;i<=sum_1;i++)
  36.         {
  37.             int now=(i*h)+((sum_0+i)*c0)+(sum_1-i)*c1;
  38.             ans=min(ans, now);
  39.         }
  40.         cout<<ans<<endl;
  41.         ans=0;  sum_1=0;    sum_0=0;
  42.     }
  43. }

B. Sum of Medians

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<vector>
  6. using namespace std;
  8. char c[1005];
  10. int main(){
  11.     int T;
  12.     int sum_1=0,sum_0=0,ans;
  13.     cin>>T;
  14.     while(T--)
  15.     {
  16.         int n,k;
  17.         cin>>n>>k;
  18.         int m=n*k;
  19.         vector<int>a(m);
  20.         for(int i=0;i<m;i++)
  21.         { 
  22.             cin>>a[i];
  23.          }   
  24.         long long tot=0;
  25.         if(n==2)
  26.         {
  27.             for(int i=0;i<m;i+=2)
  28.                 tot+=a[i];
  29.             cout<<tot<<endl;
  30.             continue;
  31.         }
  32.         int inter=(n+1)/2;
  33.         int left=n-inter;
  34.         left+=1;
  35.         int x=1,in=0;
  36.         for(int i=m-1;i>=0;i--)
  37.         {
  38.             if(x%left==0)
  39.             {
  40.                 tot+=a[i];
  41.                 in++;
  42.             }
  43.             x+=1;
  44.             if(in>=k)   break;
  45.         }
  46.         cout<<tot<<endl;
  47.     }
  48.     return 0;
  49. }

C1. Binary Table (Easy Version)

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<vector>
  6.         using namespace std;
  8.         void case4(vector<vector<int>>&b , vector<string>& a , int i , int j){
  9.             a[i][j]=a[i+1][j]=a[i][j+1]=a[i+1][j+1]='0';
  10.             vector<int>c;
  11.             c.push_back(i);
  12.             c.push_back(j);
  13.             c.push_back(i+1);
  14.             c.push_back(j);
  15.             c.push_back(i+1);
  16.             c.push_back(j+1);
  17.             b.push_back(c);
  18.             c.clear();
  19.             c.push_back(i);
  20.             c.push_back(j+1);
  21.             c.push_back(i+1);
  22.             c.push_back(j);
  23.             c.push_back(i+1);
  24.             c.push_back(j+1);
  25.             b.push_back(c);
  26.             c.clear();
  27.             c.push_back(i);
  28.             c.push_back(j);
  29.             c.push_back(i);
  30.             c.push_back(j+1);
  31.             c.push_back(i+1);
  32.             c.push_back(j);
  33.             b.push_back(c);
  34.             c.clear();
  35.             c.push_back(i);
  36.             c.push_back(j);
  37.             c.push_back(i);
  38.             c.push_back(j+1);
  39.             c.push_back(i+1);
  40.             c.push_back(j+1);
  41.             b.push_back(c);
  42.         }
  44.         void case1(vector<vector<int>>&b , vector<string>& a , int i , int j){
  45.             vector<int>c;
  46.             if(a[i][j]=='1'){
  47.                 c.push_back(i);
  48.                 c.push_back(j+1);
  49.                 c.push_back(i+1);
  50.                 c.push_back(j);
  51.                 c.push_back(i+1);
  52.                 c.push_back(j+1);
  53.                 b.push_back(c);
  54.             }
  55.             if(a[i][j+1]=='1'){
  56.                 c.push_back(i);
  57.                 c.push_back(j);
  58.                 c.push_back(i+1);
  59.                 c.push_back(j);
  60.                 c.push_back(i+1);
  61.                 c.push_back(j+1);
  62.                 b.push_back(c);
  63.             }
  64.             if(a[i+1][j]=='1'){
  65.                 c.push_back(i);
  66.                 c.push_back(j);
  67.                 c.push_back(i);
  68.                 c.push_back(j+1);
  69.                 c.push_back(i+1);
  70.                 c.push_back(j+1);
  71.                 b.push_back(c);
  72.             }
  73.             if(a[i+1][j+1]=='1'){
  74.                 c.push_back(i);
  75.                 c.push_back(j);
  76.                 c.push_back(i+1);
  77.                 c.push_back(j);
  78.                 c.push_back(i);
  79.                 c.push_back(j+1);
  80.                 b.push_back(c);
  81.             }
  82.         }
  84.         void case2(vector<vector<int>>&b , vector<string>& a , int i , int j){
  85.             vector<int>c;
  86.             if(a[i][j]=='1' && a[i][j+1]=='1'){
  87.                 c.push_back(i);
  88.                 c.push_back(j);
  89.                 c.push_back(i);
  90.                 c.push_back(j+1);
  91.                 c.push_back(i+1);
  92.                 c.push_back(j+1);
  93.                 b.push_back(c);
  94.                 a[i][j]=a[i][j+1]='0';
  95.                 a[i+1][j+1]='1';
  96.             }
  97.             if(a[i][j]=='1' && a[i+1][j]=='1'){
  98.                 c.push_back(i);
  99.                 c.push_back(j);
  100.                 c.push_back(i+1);
  101.                 c.push_back(j);
  102.                 c.push_back(i+1);
  103.                 c.push_back(j+1);
  104.                 b.push_back(c);
  105.                 a[i][j]=a[i+1][j]='0';
  106.                 a[i+1][j+1]='1';
  107.             }
  108.             if(a[i][j]=='1' && a[i+1][j+1]=='1'){
  109.                 c.push_back(i);
  110.                 c.push_back(j);
  111.                 c.push_back(i+1);
  112.                 c.push_back(j+1);
  113.                 c.push_back(i+1);
  114.                 c.push_back(j);
  115.                 b.push_back(c);
  116.                 a[i][j]=a[i+1][j+1]='0';
  117.                 a[i+1][j]='1';
  118.             }
  119.             if(a[i][j+1]=='1' && a[i+1][j]=='1'){
  120.                 c.push_back(i);
  121.                 c.push_back(j+1);
  122.                 c.push_back(i+1);
  123.                 c.push_back(j);
  124.                 c.push_back(i);
  125.                 c.push_back(j);
  126.                 b.push_back(c);
  127.                 a[i][j+1]=a[i+1][j]='0';
  128.                 a[i][j]='1';
  129.             }
  130.             if(a[i][j+1]=='1' && a[i+1][j+1]=='1'){
  131.                 c.push_back(i);
  132.                 c.push_back(j+1);
  133.                 c.push_back(i+1);
  134.                 c.push_back(j+1);
  135.                 c.push_back(i);
  136.                 c.push_back(j);
  137.                 b.push_back(c);
  138.                 a[i][j+1]=a[i+1][j+1]='0';
  139.                 a[i][j]='1';
  140.             }
  141.             if(a[i+1][j]=='1' && a[i+1][j+1]=='1'){
  142.                 c.push_back(i+1);
  143.                 c.push_back(j);
  144.                 c.push_back(i+1);
  145.                 c.push_back(j+1);
  146.                 c.push_back(i);
  147.                 c.push_back(j);
  148.                 b.push_back(c);
  149.                 a[i+1][j]=a[i+1][j+1]='0';
  150.                 a[i][j]='1';
  151.             }
  152.         }
  154.         void solve(){
  155.             int n,m;
  156.             cin>>n>>m;
  157.             vector<string>a(n);
  158.             for(int i=0;i<n;i++){
  159.                 cin>>a[i];
  160.             }
  161.             vector<vector<int>>b;
  162.             for(int i=0;i<n-1;i++){
  163.                 for(int j=0;j<m-1;j++){
  164.                     int total=0;
  165.                     total=(a[i][j]-'0')+(a[i][j+1]-'0')+(a[i+1][j]-'0')+(a[i+1][j+1]-'0');
  166.                     if(total==0)
  167.                         continue;
  168.                     else if(total==3){
  169.                         vector<int>c;
  170.                         if(a[i][j]=='1'){
  171.                             a[i][j]='0';
  172.                             c.push_back(i);
  173.                             c.push_back(j);
  174.                         }
  175.                         if(a[i][j+1]=='1'){
  176.                             a[i][j+1]='0';
  177.                             c.push_back(i);
  178.                             c.push_back(j+1);
  179.                         }
  180.                         if(a[i+1][j]=='1'){
  181.                             a[i+1][j]='0';
  182.                             c.push_back(i+1);
  183.                             c.push_back(j);
  184.                         }
  185.                         if(a[i+1][j+1]=='1'){
  186.                             a[i+1][j+1]='0';
  187.                             c.push_back(i+1);
  188.                             c.push_back(j+1);
  189.                         }
  190.                         b.push_back(c);
  191.                     }
  192.                     else if(total==4){
  193.                         case4(b,a,i,j);
  194.                     }
  195.                     else if(total==1){
  196.                         case1(b,a,i,j);
  197.                         case4(b,a,i,j);
  198.                     }
  199.                     else{
  200.                         case2(b,a,i,j);
  201.                         case1(b,a,i,j);
  202.                         case4(b,a,i,j);
  203.                     }
  204.                 }
  205.             }
  206.             cout<<(int)b.size()<<"\n";
  207.             for(int i=0;i<(int)b.size();i++){
  208.                 for(int j=0;j<6;j++)
  209.                     cout<<b[i][j]+1<<" ";
  210.                 cout<<"\n";
  211.             }
  212.         }
  214.         int main(){
  215.             int T;
  216.             cin>>T;
  217.             while(T--)
  218.             {
  219.                 solve();
  220.             }
  221.             return  0;
  222.         }

PS.这个模拟把人写傻了