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=;
int a[maxn];
int main()
{
int n;
while(cin>>n)
{
int minx,maxx;
for(int i=;i<=n;i++)
cin>>a[i];
for(int i=;i<=n;i++){
if(a[i]==)
{
minx=i; break;
}
}
for(int i=;i<=n;i++){
if(a[i]==n){
maxx=i; break;
}
}
if(minx>maxx)
swap(minx,maxx);
cout<<maxx-minx+max(minx-,n-maxx)<<endl;
}
return ;
}
B题
题意:给定一些倒香槟的杯子,第一层1个,第二层2个,依此下去,问第t秒有多少个杯子水是满的
分析:为了考虑精度问题,我们将t乘1024,然后进行模拟,对每1秒流下的水,到下下一层以后一定会变成(a[i][j]-1)/2
#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 inf=<<;
int a[maxn][maxn];
int n,t;
int main()
{
while(cin>>n>>t)
{
memset(a,,sizeof(a));
a[][]=t*inf;
int ans=;
for(int i=;i<=n;i++)
for(int j=;j<=i;j++){
if(a[i][j]>=inf){
ans++;
a[i+][j]+=(a[i][j]-inf)/;
a[i+][j+]+=(a[i][j]-inf)/;
}
}
cout<<ans<<endl;
}
return ;
}
C题
题意:给定一个字符串,可以改变其中k个字母,问最大的重复字串长度,字符串只含有a和b
分析:这题是一个原题,对于区间[l,r],看其上0的数量是否大于k,若小于k,则[l+1,r]必然也小于k,统计[1,n]上的最大长度即可。统计的时候用二分思想,然后分别对a和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=;
char s[maxn];
int a[maxn],b[maxn],dp1[maxn],dp2[maxn];
int n,k;
int main()
{
while(cin>>n>>k)
{
memset(dp1,,sizeof(dp1));
//memset(a,0,sizeof(a));
scanf("%s",s);
for(int i=;i<n;i++){
int t=i;
if(s[i]=='a')
a[++t]=;
else
a[++t]=;
}
//for(int i=1;i<=n;i++)
// cout<<a[i];
//cout<<endl;
for(int i=;i<=n;i++){
if(!a[i])
dp1[i]=dp1[i-]+;
else
dp1[i]=dp1[i-]; }
int left1=,right1=,mx1=,j1=;
for(int i=;i<=n;i++){
while(dp1[i]-dp1[j1]>k) j1++;
if(mx1<i-j1){
mx1=i-j1;
left1=j1+;
right1=i;
}
} memset(dp2,,sizeof(dp2));
//memset(b,0,sizeof(b));
for(int i=;i<n;i++){
int h=i;
if(s[i]=='b')
b[++h]=;
else b[++h]=;
} for(int i=;i<=n;i++){
if(!b[i])
dp2[i]=dp2[i-]+;
else
dp2[i]=dp2[i-];
}
int left2=,right2=,mx2=,j2=;
for(int i=;i<=n;i++){
while(dp2[i]-dp2[j2]>k) j2++;
if(mx2<i-j2){
mx2=i-j2;
left2=j2+;
right2=i;
}
}
cout<<max(mx1,mx2)<<endl;
}
return ;
}