【NOIP 2011 提高组】

正向读入，反向遍历

#include
using namespace std;
#define N 10001
int n,x,y,ans = -1;
int a[N],b[N],c[N],d[N];
bool Judge(int x1,int y1,int x2,int y2){return (x1<=x) && (x<=x2) && (y1<=y) && (y<=y2);
}
int main()
{
//	freopen("carpet.in","r",stdin);
//	freopen("carpet.out","w",stdout);scanf("%d",&n);for(int i=1; i<=n; i++)	scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);scanf("%d%d",&x,&y);for(int i=n; i>=1; i--)if(Judge(a[i],b[i],a[i]+c[i],b[i]+d[i])) {ans = i;break;}printf("%d",ans);return 0;
}

• 方法：枚举
• 遍历每2个同色客栈，满足条件则累加
• 优化1：使用前缀和，把判断条↑时间复杂度变为O（1）
• 优化2：当前i到j可以时，则i到j以后的任何同色客栈均可以，当前j计算过后可以直接将i++
• 考场失分：前缀和计算 应注意i->j 应为 pre[i]-pre[j]+a[j]
  码

#include
using namespace std;
typedef long long LL;
#define N 200001
LL ans;
int n,k,p;
int color[N],cost[N],pre[N];
vector <int> same[51];
int main()
{
//	freopen("hotel.in","r",stdin);
//	freopen("hotel.out","w",stdout);scanf("%d%d%d",&n,&k,&p);for(int i=1; i<=n; i++){scanf("%d%d",&color[i],&cost[i]);same[color[i]].push_back(i);if(cost[i] <= p) pre[i]++;pre[i] += pre[i-1];}bool Skip;for(int i=0; i<k; i++){for(int f1=0; f1<same[i].size(); f1++){for(int f2=f1+1; f2<same[i].size();f2++){if(pre[same[i][f2]]-pre[same[i][f1]] + (cost[same[i][f1]]<=p?1:0) >= 1){ans += (same[i].size()-f2);break;}}}}printf("%lld",ans);return 0;
}

模拟！爆搜！函数思想！
注：

1. 不同色时右移
2. 左边无块时左移
   code

#include
using namespace std;
int n,csum;//color types sum
int f[10][10],cs[51],xiao[10][10],ans[10][5],last[10][10][10];
void Read(){scanf("%d",&n);for(int i=1; i<=5; i++)for(int j=1; j<=8; j++){scanf("%d",&f[0][0]);if(!f[0][0]) break;f[i][j] = f[0][0];if(f[i][j]>csum) csum++;cs[f[i][j]]++;}
}bool If_empty(){for(int i=1; i<=5; i++)if(f[i][1]) return false;return true;
}bool To_eliminate(){bool flag = false;for(int i=1; i<=5; i++)for(int j=1; j<=7; j++){if(i-1>=1 && i+1<=5 && f[i][j]==f[i-1][j] && f[i][j]==f[i+1][j] && f[i][j]){xiao[i-1][j]=1;xiao[i+1][j]=1;xiao[i][j]=1;flag=true;}if(j-1>=1 && j+1<=7 && f[i][j]==f[i][j+1] && f[i][j]==f[i][j-1] && f[i][j]){xiao[i][j]=1;xiao[i][j+1]=1;xiao[i][j-1]=1;flag=true;}}if(!flag) return false;for(int i=1;i<=5;i++)for(int j=1;j<=7;j++)if(xiao[i][j]) f[i][j] = xiao[i][j] = 0;return true;
}void To_down(){for(int i=1; i<=5; i++){int blank = 0;for(int j=1; j<=7; j++){if(!f[i][j]) blank++;else if(blank){f[i][j-blank] = f[i][j];f[i][j] = 0;}}}
}void move(int i,int j,int x){swap(f[i][j],f[i+x][j]);To_down();while(To_eliminate()) To_down();
}void copy(int x){for(int i=1;i<=5;i++)for(int j=1;j<=7;j++)last[x][i][j]=f[i][j];
}void dfs(int x){if(If_empty()){for(int i=1;i<=n;i++){if(i!=1)printf("\n");for(int j=1;j<=2;j++)printf("%d ",ans[i][j]);printf("%d",ans[i][3]);}exit(0);}if(x==n+1)return;copy(x);for(int i=1;i<=5;i++)for(int j=1;j<=7;j++){if(f[i][j]){if(i+1<=5&&f[i][j]!=f[i+1][j]){move(i,j,1);					//rightans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=1;dfs(x+1);for(int i=1;i<=5;i++)for(int j=1;j<=7;j++)f[i][j]=last[x][i][j];ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1;}if(i-1>=1&&f[i-1][j]==0){move(i,j,-1);ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=-1;dfs(x+1);for(int i=1;i<=5;i++)for(int j=1;j<=7;j++)f[i][j]=last[x][i][j];ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1;}}}
}
int main()
{
//	freopen("mayan.in","r",stdin);
//	freopen("mayan.out","w",stdout);Read();//spj/*for(int i=1; i<=csum; i++)if(cs[i]<3) {printf("-1");return 0;}*/memset(ans,-1,sizeof(ans));dfs(1);printf("-1");return 0;
}