noip2013提高组_左归丸组方解析
题目描述：
铺地毯 选择客栈 Mayan游戏 计算系数 聪明的质检员 观光公交
day1：
铺地毯：
只有一个需要注意的地方：给出的g和k不是右下角的坐标，右下角坐标应是（a+g,b+k)
倒序判断即可。
参考程序：
#include<cstdio>
#include<algorithm>
#define maxn 1100000
using namespace std;
int x1[maxn],x2[maxn];
int y1[maxn],y2[maxn];
int n;
int main(){
freopen("carpet.in","r",stdin);
freopen("carpet.out","w",stdout);
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
int x0,y0;
scanf("%d%d",&x0,&y0);
for (int i=n-1;i>=0;i--)
if (x1[i]<=x0 && x0<=x1[i]+x2[i] && y1[i]<=y0 && y0<=y1[i]+y2[i]){
printf("%d",i+1);
return 0;
}
printf("-1");
return 0;
}选择客栈：
看似需要两层循环，实际上细细分析只是简单的推理模拟。
读入col和p
令a[i]=top[col]表示当前颜色的前一次出现实在几号。
b[i]表示前一个价格小于标准的是在几号。
cnt[i]=top2[col]++表示当前颜色是第几次出现。
第二次扫瞄：
若a[i]<=b[i]即当前与之前同颜色的之间必然有一个客栈价格小于标准，ans[i]+=cnt[i]
反之，当前客栈与之前同颜色的之间是否有客栈价格小于标准，只需看ans[a[i]],
所以此时ans[i]=ans[a[i]];
最后将ans求和即可。
参考程序：
#include<cstdio>
#include<algorithm>
#define maxn 211000
using namespace std;
int cnt[maxn],top[maxn];
int top2[maxn],a[maxn],b[maxn],c[maxn];
int n,k,cost;
int main(){
freopen("hotel.in","r",stdin);
freopen("hotel.out","w",stdout);
scanf("%d%d%d",&n,&k,&cost);
for (int i=0;i<n;i++){
int col,p;
scanf("%d%d",&col,&p);
a[i]=top[col];top[col]=i;
if (p<=cost)b[i]=i;else b[i]=b[i-1];
cnt[i]=top2[col]++;
}
for (int i=0;i<n;i++)
if (a[i]<=b[i])c[i]=cnt[i];
else c[i]=c[a[i]];
int ans=0;
for (int i=0;i<n;i++)
ans+=c[i];
printf("%d",ans);
return 0;
}Mayan游戏：
此问题裸裸搜索即可，
只需注意几个剪枝：
1.左右相同则不搜
2.只考虑右，除非当前点的左边是0才考虑左。
然后就可以过了。
参考程序：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int a[10][10],b[10][10],c[10][10];
bool d[10][10];
int x[10],y[10],t[10];
bool ok(){
for (int i=1;i<=5;i++)
if (b[1][i])return false;
return true;
}
void print(){
for (int k=1;k<=n;k++)
printf("%d %d %d\n",y[k]-1,x[k]-1,t[k]);
exit(0);
}
void dfs(int step);
void remain(int step){
bool still=true;
/*printf("%d,\n",step);
for (int i=1;i<=7;i++){
for (int j=1;j<=5;j++)
printf("%d ",b[i][j]);
printf("\n");
}*/
while (still){
still=false;
memset(d,0,sizeof(d));
for (int i=1;i<=7;i++)
for (int j=1;j<=5;j++)
if (b[i][j]){
if (j+2<=5 && b[i][j]==b[i][j+1] && b[i][j]==b[i][j+2]){
d[i][j]=d[i][j+1]=d[i][j+2]=true;
}
if (i+2<=7 && b[i][j]==b[i+1][j] && b[i][j]==b[i+2][j]){
d[i][j]=d[i+1][j]=d[i+2][j]=true;
}
}
for (int i=1;i<=7;i++)
for (int j=1;j<=5;j++)
if (d[i][j])b[i][j]=0;
for (int j=1;j<=5;j++)
for (int i=1;i<=7;i++)
if (!b[i][j]){
int tt=i;
while ((b[tt][j]==0) && tt<=7)tt++;
if (tt>7)break;
for (int k=0;k<=tt-i;k++){
b[i+k][j]=b[tt+k][j];
b[tt+k][j]=0;
}
still=true;
}
if (!still)break;
}
/*printf("%d,\n",step);
for (int i=1;i<=7;i++){
for (int j=1;j<=5;j++)
printf("%d ",b[i][j]);
printf("\n");
}*/
if (step==n+1 && ok())print();
if (step!=n+1 && ok())return;
dfs(step);
}
void dfs(int step){
if (step>n)return;
int c[10][10];
memcpy(c,b,sizeof(c));
//printf("%d\n",step);
for (int j=1;j<=5;j++){
for (int i=1;i<=7;i++)
if (b[i][j]&& b[i][j] != b[i][j+1]){
//if (step==1)printf("pay attention to (%d,%d)\n",i,j);
//if (x[1]==2 && y[1]==3 && x[2]==2 && y[2]==4)printf("pay attention to (%d,%d)!\n",i,j);
if (j<5 ){
x[step]=i;y[step]=j;t[step]=1;
swap(b[i][j],b[i][j+1]);
remain(step+1);
memcpy(b,c,sizeof(b));
}
if (j==1)continue;
if (b[i][j-1])continue;
if (b[i][j-1]==b[i][j])continue;
x[step]=i;y[step]=j;t[step]=-1;
swap(b[i][j],b[i][j-1]);
remain(step+1);
memcpy(b,c,sizeof(b));
}
}
}
int main(){
freopen("mayan.in","r",stdin);
freopen("mayan.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=5;i++){
int x,j=0;
while (scanf("%d",&x)==1 && x)a[++j][i]=x;
}
for (int i=1;i<=7;i++){
for (int j=1;j<=5;j++)
b[i][j]=a[i][j];//printf("%d ",a[i][j]);
//printf("\n");
}
dfs(1);
//remain(1);
printf("-1");
return 0;
}day2：
计算系数：
将ax，by看成整体（其实就是裸裸的二项式）
参考程序：
#include<cstdio>
#include<algorithm>
#define Mod 10007
using namespace std;
int f[Mod];
int main(){
freopen("factor.in","r",stdin);
freopen("factor.out","w",stdout);
int a,b,k,n,m;
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
a%=Mod;b%=Mod;
int x=1;
for (int i=0;i<n;i++){
x*=a;x%=Mod;
}
int y=1;
for (int i=0;i<m;i++){
y*=b;y%=Mod;
}
f[1]=1;
for (int i=2;i<=k+1;i++)
for (int j=i;j>=2;j--){
f[j]+=f[j-1];
f[j]%=Mod;
}
printf("%d",x*y%Mod*f[m+1]%Mod);
return 0;
}聪明的质检员：
根据题目明显可以知道，W越大，Y越小，所以二分W，使Y逐渐靠近S即可。
在计算Y的时候用到了小小的前缀和预处理思想，也就没什么了。
参考程序：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define maxn 210000
using namespace std;
long long s1[maxn],s2[maxn];
int l[maxn],r[maxn];
int w[maxn],v[maxn];
int n,m;
long long S;
long long check(int x){
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
for (int i=1;i<=n;i++){
s1[i]=s1[i-1];s2[i]=s2[i-1];
if (w[i]>=x){
s1[i]+=1;
s2[i]+=v[i];
}
}
long long res=0;
for (int i=0;i<m;i++)
res+=(s1[r[i]]-s1[l[i]-1])*(s2[r[i]]-s2[l[i]-1]);
return res;
}
int main(){
freopen("qc.in","r",stdin);
freopen("qc.out","w",stdout);
cin>>n>>m>>S;
for (int i=1;i<=n;i++)
scanf("%d%d",&w[i],&v[i]);
for (int i=0;i<m;i++)
scanf("%d%d",&l[i],&r[i]);
int left=0,right=*max_element(w+1,w+n+1);
while (left+1<right){
int mid=(left+right)/2;
if (check(mid)<=S)right=mid;
else left=mid;
}
cout<<min(abs(check(left)-S),abs(S-check(right)));
return 0;
}观光公交：
根据题目可以知道每一个加速器的选择是独立的，都满足选择时间最多的一段路，所以将贪心重复几次即可。
贪心策略：
首先计算出车到各个站的时间get[i]，以及离开各个站的时间last[i]（最后一个到的乘客的时间）,因为如果get[i]<last[i]，即车到这里要等乘客，所以在此之前不论用多少的加速器，到这里就会失去效果，所以据此计算出从i站到g[i]站后就会失去效果，用sum表示到某个站的乘客所等的总时间，取sum[g[i]]-sum[i]最大的第i段路用一个加速器，重新计算get与g。
参考程序：
#include<cstdio>
#include<algorithm>
#define maxn 110000
using namespace std;
int last[maxn],get[maxn];
int d[maxn],sum[maxn];
int b[maxn],t[maxn],a[maxn];
int n,m,k;
int g[maxn];
int ans=0;
int main(){
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<n;i++)
scanf("%d",&d[i]);
for (int i=0;i<m;i++){
scanf("%d%d%d",&t[i],&a[i],&b[i]);
sum[b[i]]++;
last[a[i]]=max(last[a[i]],t[i]);
}
for (int i=1;i<=n;i++)
get[i]=max(get[i-1],last[i-1])+d[i-1];
g[n-1]=g[n]=n;
for (int i=n-2;i>0;i--)
if (get[i+1]<=last[i+1])g[i]=i+1;
else g[i]=g[i+1];
for (int i=1;i<=n;i++)
sum[i]+=sum[i-1];
for (int i=0;i<m;i++)
ans+=get[b[i]]-t[i];
while (k--){
int reduce=0;
int l,r;
for (int i=1;i<=n;i++)
if (sum[g[i]]-sum[i]>reduce && d[i]>0){
reduce=sum[g[i]]-sum[i];
l=i;r=g[i];
}
if (r>=n)r=n-1;
d[l]--;
ans-=reduce;
for (int i=l;i<=r;i++)
get[i]=max(get[i-1],last[i-1])+d[i-1];
for (int i=r;i>=l;i--)
if (get[i+1]<=last[i+1])g[i]=i+1;
else g[i]=g[i+1];
}
printf("%d",ans);
return 0;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/193467.html原文链接：https://javaforall.cn
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022年9月15日 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
