一、反转问题

算法概览:给定一个01串,现有翻转规则:翻转某一个位置时其后面2个位置也会跟着翻转,也就是每次翻转都会翻转3个连续的位置。要将01串全部翻转为0,求最小的翻转次数。形似这类题的问题叫做反转问题,也可以叫开关问题,对于这类题通常有以下的特点,思考一下就可以想到。

1、若某一个位置被翻转了n次,则其实际上被翻转了n%2次,因为翻转2k次相当与没翻转,翻转2k+1次相当于翻转了1次,因为要求最小翻转次数,所以对于某一个位置要么只(主动)翻转一次,要么不(主动)翻转。

2、分析易知翻转的顺序并不影响最终结果。(理解不了可自己举个例子在纸上模拟下)

3、由此,反转问题(也叫开关问题)就转化成求反转区间的集合,常常和枚举一起使用。

POJ 3276

N头牛排列成了一列,每头牛或者向前或者向后站,为了让所有的牛都面向前方,农夫约翰买了一台自动转向的机器,这个机器在购买时就必须设定一个数值K,机器每操作一次恰好使K头连续的牛转向(K头牛分别为当前的牛及其之后的牛,不影响位于它之前的牛,并且每次反转必须是K头牛,不可以少于K头)。请求出为了让所有的牛都能面向前方需要的最少的操作次数M和对应的最小的K。

已知:
1≤N≤5000
sampleinput
N= 7
BBFBFBB(F:面向前方,B:面向后方)
sampleoutput
K= 3
M= 3
(先反转1~3号的三头牛,然后再反转3~5号,最后反转5~7号)
NOIP复赛复习(十八)反转问题与弹性碰撞-少儿编程网NOIP复赛复习(十八)反转问题与弹性碰撞-少儿编程网

思路:

定义 f[i]:区间[i,i+k-1]进行反转的话就为1,否则为0

区间反转部分很好优化:

在考虑第i头牛时候,如果∑i−1j=(i−K+1)f[j]和为奇数,就说明此时这个牛方向与最初相反。

由于 ∑ij=(i+1)−K+1f[j]=∑i−1j=(i−K+1)f[j]+f[i]-f[i-K+1]

所以这个每一次都可以用常数算出来,时间复杂度O(n^2)
#include<cstdio>
#include<cstring>
#include<iostream>
using name space std;
const int N=5000+10;
int f[N],dir[N],n;
int solve(int k){
int cnt=0,sum=0;//sum为f的和
memset(f,0,sizeof(f));
for(int i=1;i<=n-k+1;i++){
if((dir[i]+sum)%2){
cnt++;
f[i]=1;
}
sum+=f[i];
if(i-k+1>=1) sum-=f[i-k+1];
}
for(int i=n-k+2;i<=n;i++){//检查剩下的牛有没有朝后面的情况
if((dir[i]+sum)%2) return n+1;
if(i-k+1>=1) sum-=f[i-k+1];
}
return cnt;
}
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++){
char c;scanf(" %c",&c);
if(c=='B') dir[i]=1;
}
int ansk,ansm=n,t;
for(int i=1;i<=n;i++){
t=solve(i);
if(t<ansm){
ansm=t;ansk=i;
}
}
printf("%d %d\n",ansk,ansm);
}
}

POJ 3279

农夫约翰知道聪明的牛产奶多。于是为了提高牛的智商他准备了如下游戏。有一个M×N 的格子,每个格子可以翻转正反面,它们一面是黑色,另一面是白色。黑色的格子翻转后就是白色,白色的格子翻转过来则是黑色。游戏要做的就是把所有的格子都翻转成白色。不过因为牛蹄很大,所以每次翻转一个格子时,与它上下左右相邻接的格子也会被翻转。因为翻格子太麻烦了,所以牛都想通过尽可能少的次数把所有格子都翻成白色。现在给定了每个格子的颜色,请求出用最小步数完成时每个格子翻转的次数。最小步数的解有多个时,输出字典序最小的一组。解不存在的话,则输出IMPOSSIBLE。

已知:
1≤M,N≤15
sample input
M= 4
N= 4 每个格子的颜色如下:(0表示白色,1表示黑色)
10 0 1
01 1 0
01 1 0
10 0 1
sample output
00 0 0
10 0 1
10 0 1
00 0 0

思路:在上面的那道题,让最左端的奶牛反转的情况只有一种,于是直接判断的方法就可以确定,但是这里不一样,比如,看最左上面的角,除了反转(1,1),(1,2),(2,1)都可以导致他翻装。

于是不妨我们先确定最上面一行的反装方式,此时能反转(1,1)只有(2,1),

所以如果已知第一行就可以知道第二行那些点需要反转。这样反复下去,只要最后一行全部为白,就说明可行。

那么这个算法时间复杂度是(N*M*2^N).

NOIP复赛复习(十八)反转问题与弹性碰撞-少儿编程网
#include<cstdio>
#include<cstring>
using name space std;
const int dx[5]={-1,0,0,0,1};
const int dy[5]={0,-1,0,1,0};
int m,n,M[20][20],tmp[20][20],ans[20][20],cnt;
int get(int x,int y){
int t=M[x][y];
for(int i=0;i<5;i++){
int tx=dx[i]+x,ty=dy[i]+y;
if(tx>=0&&tx<m&&ty>=0&&ty<n)t+=tmp[tx][ty];
}
return t%2;
}
int cal(){
for(int i=1;i<m;i++){
for(int j=0;j<n;j++){
if(get(i-1,j)) tmp[i][j]=1;
}
}
for(int j=0;j<n;j++){
if(get(m-1,j)!=0) return n*m+1;
}
int res=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
res+=tmp[i][j];
}
}
return res;
}
int main(){
while(~scanf("%d%d",&m,&n)){
cnt=n*m+1;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
scanf("%d",&M[i][j]);
}
}
for(int i=0;i<(1<<n);i++){
memset(tmp,0,sizeof(tmp));
for(int j=0;j<n;j++){
tmp[0][j]=i>>j&1;
}
int t=cal();
if(t<cnt){
cnt=t;
memcpy(ans,tmp,sizeof(tmp));
}
}
if(cnt==n*m+1){
printf("IMPOSSIBLE\n");
}
else{
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
printf("%d%c",ans[i][j],j+1==n ? '\n':' ');
}
}
}
}
}

POJ 3185

翻盖有奖:将一列碗翻成口朝上,一把下去可能同时反转3个或2个(首尾),求最小翻转次数。

思路:这题分析一下,可以知道选择从第一个开始翻,还是聪第二个开始翻,会导致两种不同的状态和结果,但都是唯一的。所以就枚举第一个还是第二个开始翻,然后从左往右依次判断,接下来每个点需不需要翻转取决它左边是不是朝下。
#include<cstdio>
#include<cstring>
#include<algorithm>
using name space std;
int dir[25],f[25];
int main(){
while(~scanf("%d",&dir[0])){
int tmp=0,ans=20;
memset(f,0,sizeof(f));
for(int i=1;i<20;i++)scanf("%d",&dir[i]);
f[0]=1;tmp++;
for(int i=1;i<20;i++){
if(f[i]=(f[i-2]^f[i-1]^dir[i-1]))tmp++;
}
if((f[18]^f[19]^dir[19])==0&&tmp<ans) ans=tmp;
tmp=0;f[0]=0;
for(int i=1;i<20;i++){
if(f[i]=(f[i-2]^f[i-1]^dir[i-1]))tmp++;
}
if(f[18]^f[19]^dir[19]==0&&tmp<ans) ans=tmp;
printf("%d\n",ans);
}
}

总结:往往反转问题(开关问题)可以转换成矩阵求解一组方程的解是否存在,用高斯消元求解,并且通过这些分析知道,当自由变员不超过N个时候,也可以用来求解最优解。

二、弹性碰撞

在理想情况下,物体碰撞后,形变能够恢复,不发热、发声,没有动能损失,这种碰撞称为弹性碰撞(elastic collision),又称完全弹性碰撞。生活中,硬质木球或钢球发生碰撞时,动能的损失很小,可以忽略不计,通常也可以将它们的碰撞看成弹性碰撞。

发生弹性碰撞后,两个物体在碰撞后相比碰撞前,相对速度大小相等方向相反;两个物体在发生弹性碰撞前后,动量的矢量和、能量的和都不变;如果两个物体质量相同,速度大小方向都互换,相当于未碰撞。

用N个半径为R厘米的球进行如下实验。

在H米高的位置设置一个圆筒,将求垂直放入(从下向上数第i个球的底端距离地面高度为H + 2R)。实验开始时最下面的球开始掉落,此后每一秒又有一个球开始掉落。不计空气阻力,并假设球与球或地面间的碰撞时弹性碰撞。

请求出实验开始后T秒时每个球底端的高度。假设重力加速度为g=10m/s2

已知:
1≤N≤100
1≤H≤10000
1≤R≤100
1≤T≤10000
sample input
N= 1
H= 10
R= 10
T= 100
sample output
4.95
NOIP复赛复习(十八)反转问题与弹性碰撞-少儿编程网

从高位H的位置下落的话需要花费的时间:

NOIP复赛复习(十八)反转问题与弹性碰撞-少儿编程网

因此,在时刻T时,令K 为满足kt≤T的最大整数,那么

NOIP复赛复习(十八)反转问题与弹性碰撞-少儿编程网

当R = 0时,如果认为球是一样的,就可以忽视他们的碰撞,视为直接互相穿过继续运动。由于在有碰撞时球的顺序不会发生改变,所以忽略碰撞,将计算得到的坐标进行排序后,就能知道每个球的最终位置。

那么,R>0是要怎么样?这种情况下的处理方法基本相同,对于下方开始的第i个球,在按照R = 0计算的结果上加上2*R*i就可以了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#define sf scanf
#define pf printf
using name space std;
const int Maxn = 110;
double ans[Maxn];
int main()
{
int cas,N,H,R,T,g = 10;
sf("%d",&cas);
while(cas--)
{
sf("%d%d%d%d",&N,&H,&R,&T);
for(int i = 0;i < N;i ++)
{
double t = sqrt(2.0 * H / g);
int k = floor(T / t);
if(k < 0)
ans[i] = H;
else
{
if(k & 1)
ans[i] = H - 0.5 * g * (t -(T - k * t)) * (t - (T - k * t));
else
ans[i] = H - 0.5 * g * (T -k * t) * (T - k * t);
}
T --;
}
sort(ans,ans + N);
for(int i = 0;i < N;i ++)
pf("%.2lf%c",ans[i] + 2.0* R * i / 100,i + 1 == N ? '\n':' ');
}
return 0;
}
/*
2
110 10 100
210 10 100
*/

POJ 1852

题意:在一根长为L的水平木棍上有一群数量为n的蚂蚁,它们以每秒1cm/s的速度走到木棍一端就会掉下去。现在知道它们的起始位置是距离木根左端点的x处。但是不知道它们爬行的方向。在相向而行的两只蚂蚁相遇后,它们会掉头往反方向走。问所有蚂蚁都落下木棍的最快时间和最慢时间。

题解:一开始觉得可以暴搜,每只蚂蚁只有两种情况,不过掉头的事情感觉很复杂。时间复杂度为2的n次幂。肯定超时。  因为是同时出发的,相遇时的两只蚂蚁用的时间是相同的,我们可以无视蚂蚁的区别,当两只蚂蚁相遇时它们保持原样交错而行。这样每只蚂蚁都是独立运动的,那么只要找每只蚂蚁掉下去的时间就行了。
#include<cstdio>
#define maxn 1000100
int a[maxn],ansmin,ansmax,L,n;
int MIN(int a,int b)
{
return a<b?a:b;
}
intMAX(int a,int b)
{
return a>b?a:b;
}
void ansMIN()
{
int i,min;
ansmin=-1;
for(i=0;i<n;++i)
{
min=MIN(a[i],L-a[i]);
if(min>ansmin)
ansmin=min;
}
printf("%d ",ansmin);
}
void ansMAX()
{
int i,max;
ansmax=-1;
for(i=0;i<n;++i)
{
max=MAX(a[i],L-a[i]);
if(max>ansmax)
ansmax=max;
}
printf("%d\n",ansmax);
}
int main()
{
int i,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&L,&n);
for(i=0;i<n;++i)
scanf("%d",&a[i]);
ansMIN();
//求所有蚂蚁掉下去的最短时间
ansMAX();
//求所有蚂蚁掉下去的最长时间
}
return 0;
}

*