Codeforces Education Round 11

A(模拟＋数学)

题意:在一个数列当中最少添加多少个数可以使它们两两互质，并打印出添加以后的数列

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <bitset>

 #include <cmath>

 #include <queue>

 #include <stack>

 using namespace std;

 const int maxn=;

 const int maxm=;

 int a[maxn];

 int gcd(int a,int b)

 {

     if(b==) return a;

     return gcd(b,a%b);

 }

 int n;

 int main()

 {

     while(cin>>n)

     {

         for(int i=;i<n;i++)

             scanf("%d",&a[i]);

         vector<int>b;

         int cnt=;

         for(int i=;i<n-;i++)

         {

             if(gcd(a[i],a[i+])>=){

                 cnt++;

                 int k;

                 for(int j=;j<=maxm;j++){

                     if(gcd(a[i],j)<&&gcd(j,a[i+])<){

                         k=j; break;

                     }

                 }

                 b.push_back(a[i]);

                 b.push_back(k);

             }

             else{

                 b.push_back(a[i]);

             }

         }

         b.push_back(a[n-]);

         cout<<cnt<<endl;

         for(int i=;i<b.size()-;i++)

             cout<<b[i]<<" ";

         cout<<b[b.size()-]<<endl;

     }

     return ;

 }

B(队列模拟）

题意:根据公交车上下车的顺序，打印下车的顺序

分析:用队列直接进行模拟即可

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <bitset>

 #include <cmath>

 #include <queue>

 #include <stack>

 using namespace std;

 const int maxn=;

 int a[maxn][];

 int n,m;

 int main()

 {

     while(cin>>n>>m)

     {

         queue<int>que[];

         int k=;

         int cnt=;

         for(;;)

         {

             if(cnt>=n) break;

             if(k>m) break;

             que[].push(k);

             k++;

             if(k>m) break;

             que[].push(k);

             k++;

             cnt++;

         }

         for(;;)

         {

             if(k>m) break;

             que[].push(k);

             k++;

             if(k>m)  break;

             que[].push(k);

             k++;

         }

         vector<int>b;

         int t;

         int f1=,f2=,f3=,f4=;

         for(;;)

         {

             if(que[].empty()){

                 f2=;

             }else{

                 t=que[].front();

                 que[].pop();

                 b.push_back(t);

             }

             if(que[].empty()){

                 f1=;

             }else{

                 t=que[].front();

                 que[].pop();

                 b.push_back(t);

             }

              if(que[].empty()){

                 f3=;

             }else{

                 t=que[].front();

                 que[].pop();

                 b.push_back(t);

             }

              if(que[].empty()){

                 f4=;

             }else{

                 t=que[].front();

                 que[].pop();

                 b.push_back(t);

             }

              if(f1&&f2&&f3&&f4) break;

         }

         for(int i=;i<b.size()-;i++)

             cout<<b[i]<<" ";

         cout<<b[b.size()-]<<endl;

     }

     return ;

 }

C(dp+统计)

题意:有一由0与1组成的串，可以将其中的k个0改为1,问最长的连续1的串为多长

分析:这道题看了题解，对于区间[l,r］来说统计其上0的个数是否会大于k，若小于k，则区间[l+1,r]上个数也小于k。所以我们统计区间[1,n]上0个数小于k的最长区间即可。统计的时候才用二分思想，从l和r两个方向同步进行

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <bitset>

 #include <cmath>

 #include <queue>

 #include <stack>

 using namespace std;

 const int maxn=;

 int a[maxn];

 int dp[maxn];

 int main()

 {

     int n,k;

     while(cin>>n>>k)

     {

         memset(dp,,sizeof(dp));

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a[i]);

             if(!a[i])   //统计0到i中0的个数

                 dp[i]=dp[i-]+;

             else

                 dp[i]=dp[i-];

         }

         int left=,right=,mx=,j=;

         for(int i=;i<=n;i++)

         {

             while(dp[i]-dp[j]>k) j++;

             if(mx<i-j)

             {

                 mx=i-j;

                 left=j+;

                 right=i;

             }

         }

         cout<<mx<<endl;

         for(;left<=right;left++) a[left]=;

         for(int i=;i<n;i++)

             printf("%d ",a[i]);

         printf("%d\n",a[n]);

     }

     return ;

 }

巴特西

Codeforces Education Round 11

最新文章

热门文章