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 ;
}