首页 > 代码库 > NOIP2011
NOIP2011
NOIP2011 DAY1,DAY2 数据，标程，题目，题解合集：
http://download.csdn.net/detail/junjie435/8054741
DAY1：
p1：铺地毯
这是一道模拟题目Ž：只需要询问一个点所以，从头到尾扫一遍就行了
#include<cstdio>
#include<cstring>
#include<iostream>
#define maxn 10010
using namespace std;
/*
模拟
*/
struct carpet
{
int x,y;
int lx,ly;
}ca[maxn];
int x,y,ans,n;
void init()
{
freopen("carpet.in","r",stdin);
freopen("carpet.out","w",stdout);
}
void readdate()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d%d%d%d",&ca[i].x,&ca[i].y,&ca[i].lx,&ca[i].ly);
cin>>x>>y;
}
void work()
{
ans=-1;
for(int i=1;i<=n;i++)
if(ca[i].x<=x&&ca[i].y<=y&&ca[i].x+ca[i].lx>=x&&ca[i].y+ca[i].ly>=y)
ans=i;
printf("%d\n",ans);
}
int main()
{
init();
readdate();
work();
return 0;
}p2：选择客栈
/*这道题考试的时候抽了，样例都没过*/
给几种代码：
#include<cstdio>
#include<cstdlib>
#define maxk 51
#define maxn 200010
int sum[maxn],color[maxn],value[maxn],f[maxk+1][4];
int main()
{
freopen("hotel.in","r",stdin);
freopen("hotel.out","w",stdout);
int n,k,p,ans=0;sum[0]=0;
scanf("%d%d%d",&n,&k,&p);
for(int i=1,x;i<=n;i++)
{
scanf("%d%d",&color[i],&value[i]);
sum[i]=sum[i-1]+(value[i]<=p);//可行前缀和；
}
color[0]=maxk+1;//边界判断；
for(int i=1;i<=n;i++)
{
int tot=f[color[i]][1];
if(f[color[i]][3]<sum[i]){
tot+=f[color[i]][2];
f[color[i]][1]+=f[color[i]][2];
f[color[i]][2]=0;
}
ans+=tot;
f[color[i]][2]++;
f[color[i]][3]=sum[i]-(value[i]<=p);
}
printf("%d\n",ans);
return 0;
}#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
/*
用dp[i]维护i这种颜色在当前客栈颜色为i时可行的方案数。
*/
int n,k,p;
long long ans=0;
int num[50+10],dp[50+10];
int main()
{
freopen("hotel.in","r",stdin);
freopen("hotel.out","w",stdout);
int color,price;
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&color,&price);
if(price<=p)//当前客栈价格小于p时，之前color有多少就增加多少方案。
{
ans+=num[color];
for(int j=0;j<k;j++)dp[j]=num[j];//之后的客栈与之前的都可以配对了。
dp[color]++;//特别的，当前这个也要算上。
}
else//不然的话，当前客栈增加的方案数只有dp[color]。
{
ans+=dp[color];
}
num[color]++;
}
cout<<ans<<endl;
return 0;
}
#include <cstdio>
#include <iostream>
using namespace std;
///////////////////////////////////////
const int MAXN = 200000 + 10;
///////////////////////////////////////
int n,k,p;
int col[MAXN];
int a[MAXN];
int cnt[60];
int num[MAXN];
int head[60];
int next[MAXN];
int res;
struct tree
{
int l,r,mini;
}t[800040];
///////////////////////////////////////
void fre()
{
freopen("hotel.in","r",stdin);
freopen("hotel.out","w",stdout);
}
///////////////////////////////////////
void read_pre()
{
scanf("%d %d %d",&n,&k,&p);
for(int i = 1;i <= n;i++)
{
int color;
int price;
scanf("%d %d",&color,&price);
col[i] = color; //////记录i位置的颜色
a[i] = price; //////记录i位置的价格
cnt[color]++; //////颜色color出现了多少次
num[i] = cnt[color]; //////当前位置的color颜色出现的个数
next[head[color]] = i; //////上一个颜色为color的点的下一个点为i点
head[color] = i; //////颜色color的最后一个点为i点
}
}
///////////////////////////////////////
void up(int u)
{
t[u].mini = min(t[u << 1].mini,t[u << 1 | 1].mini);
}
///////////////////////////////////////
void build(int u,int l,int r)
{
t[u].l = l;
t[u].r = r;
if(l == r)
{
t[u].mini = a[l];
return;
}
int mid = (l + r) >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
up(u);
}
///////////////////////////////////////
int que(int u,int l,int r)
{
if(l <= t[u].l && t[u].r <= r) return t[u].mini;
int mid = (t[u].l + t[u].r) >> 1;
int ans;
if(l > mid) ans = que(u << 1 | 1,l,r);
else if(r <= mid) ans = que(u << 1,l,r);
else ans = min(que(u << 1,l,r),que(u << 1 | 1,l,r));
return ans;
}
///////////////////////////////////////
int main()
{
fre();
read_pre();
build(1,1,n);
for(int i = 1;i <= n;i++)
{
int j = next[i];
while(j)
{
if(que(1,i,j) <= p)
{
res += cnt[col[i]] - num[j] + 1;
break;
}
j = next[j];
}
}
printf("%d\n",res);
return 0;
}p3：mayan 游戏
这就是一道裸DFS，看都数据范围，整个人都好了
代码中有详细解释
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define MAXN 6
#define MAXH 8
using namespace std;
/*
崩溃：结构体未清零
特殊数据
in
1
2 2 3 2 0
4 4 3 4 0
3 3 0
5 5 3 5 3 5 0
4 4 3 4 4 0
out
3 4 -1
*/
struct node
{
int h[MAXN];//当前竖列高度
int c[MAXN][MAXH];//当前列方块的map
}map;
int n,ans[MAXN][3];//用ans来记录路径
bool flag,b[MAXN][MAXH],ok=false;
void init()
{
freopen("mayan.in","r",stdin);
freopen("mayan.out","w",stdout);
}
void readdate()
{
int x;
scanf("%d",&n);
for(int i=1;i<=5;i++)
{
scanf("%d",&x);
while(x!=0)
{
map.h[i]++;
map.c[i][map.h[i]]=x;
scanf("%d",&x);
}
}
}
node clear_struct(node now)
{
for(int i=1;i<=5;i++)
{
now.h[i]=0;
for(int j=1;j<=8;j++)
now.c[i][j]=0;
}
return now;
}
bool check(node now)//是否完成
{
for(int i=1;i<=5;i++)
{
if(now.h[i]!=0)
{
return false;
}
}
return true;
}
void print()//输出路径
{
//printf("\n");
for(int i=1;i<=n;i++)
printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
ok=true;
return;
}
node move(node now)
{
node next;
next=clear_struct(next);
for(int i=1;i<=5;i++)
{
for(int j=1;j<=now.h[i];j++)
{
if(now.c[i][j]!=0&&!b[i][j])
{
next.h[i]++;
next.c[i][next.h[i]]=now.c[i][j];
}
}
}
return next;
}
node clear(node now)
{
node next;
//next=clear_struct(next);
bool flag=false;//是否进行了消除更改了地图
memset(b,0,sizeof(b));
for(int i=1;i<=5;i++)
{
for(int j=1;j<=now.h[i];j++)
{
if(i<=3)
{
if(now.c[i][j]==now.c[i+1][j]&&now.c[i][j]==now.c[i+2][j])
{
b[i][j]=b[i+1][j]=b[i+2][j]=true;
flag=true;
}
}
if(j<=now.h[i]-2)
{
if(now.c[i][j]==now.c[i][j+1]&&now.c[i][j]==now.c[i][j+2])
{
b[i][j]=b[i][j+1]=b[i][j+2]=true;
flag=true;
}
}
}
}
if(flag)
{
next=move(now);
//print();
return clear(next);//可能同时被消除所以需要再处理
}
else return now;
}
void dfs(node now,int step)
/*
对于每个节点（枚举[i][j]）进行搜索
当i==5时不可向右移
当i==1时不可向左移
右移时：
当右边一列的格子高度不足j时
当前列的高度-1，右边一列的高度+1；
格子右移——>[i][j]=0;[i+1][j]=格子的数
把当前列的格子从j到h[i]都下移一位
进行消除操作
更新ans
dfs(next,step+1)
当右边一列的格子高度足够j时
把两个格子的值进行交换
进行消除操作
更新ans
dfs(next,step+1)
左移时：【与右移类似】
当左边一列的格子高度不足j时
......
当左边一列的格子高度足够j时
//其实，我们可以发现
// 当左格子与右格子交换和右格子与左格子交换是一样的
//所以为了防止TLE 于是就可以把此情况删掉
......
*/
{
node next;
//next=clear_struct(next);
flag=check(now);
if(flag==true)
{
if(step>n) print();
else return;
}
if(ok==true) return;
if(step>n) return;
for(int i=1;i<=5;i++)
{
for(int j=1;j<=now.h[i];j++)
{
if(i<5)
{
if(j>now.h[i+1])
{
next=now;
next.h[i+1]++;
next.c[i+1][next.h[i+1]]=next.c[i][j];
next.c[i][j]=0;
next.h[i]--;
for(int k=j;k<=next.h[i];k++)
next.c[i][k]=next.c[i][k+1];
next=clear(next);
ans[step][0]=i-1;
ans[step][1]=j-1;
ans[step][2]=1;
dfs(next,step+1);
if(ok==true) return;
}
else
{
next=now;
int t=next.c[i][j];
next.c[i][j]=next.c[i+1][j];
next.c[i+1][j]=t;
next=clear(next);
ans[step][0]=i-1;
ans[step][1]=j-1;
ans[step][2]=1;
dfs(next,step+1);
if(ok==true) return;
}
}
if(i>1)
{
if(j>now.h[i-1])
{
next=now;
next.h[i-1]++;
next.c[i-1][next.h[i-1]]=next.c[i][j];
next.c[i][j]=0;
next.h[i]--;
for(int k=j;k<=next.h[i];k++)
next.c[i][k]=next.c[i][k+1];
next=clear(next);
ans[step][0]=i-1;
ans[step][1]=j-1;
ans[step][2]=-1;
dfs(next,step+1);
if(ok==true) return;
}
/*
else
{
next=now;
int t=next.c[i][j];
next.c[i][j]=next.c[i-1][j];
next.c[i-1][j]=t;
next=clear(next);
ans[step][0]=i-1;
ans[step][1]=j-1;
ans[step][2]=-1;
dfs(next,step+1);
if(ok==true) return;
}
*/
}
}
}
}
int main()
{
init();
readdate();
dfs(map,1);
if(ok==false) printf("-1\n");
return 0;
}
DAY2：
p1：计算系数
明显的二次项展开；最后X^n*Y^m的系数应该为
a^n*b^m*杨辉三角中对应的系数，再取模
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXN 1010
#define MOD 10007
using namespace std;
int a,b,k,n,m;
int YH[MAXN][MAXN];
int ans;
void init()
{
freopen("factor.in","r",stdin);
freopen("factor.out","w",stdout);
}
void readdate()
{
cin>>a>>b>>k>>n>>m;
YH[1][0]=1; YH[1][1]=1;
for(int i=2;i<=k;i++)//杨辉三角计算
{
YH[i][0]=1;YH[i][i]=1;
for(int j=0;j<=i-1;j++)
YH[i][j]=(YH[i-1][j-1]+YH[i-1][j])%MOD;
}
/*
for(int i=1;i<=k;i++)
{
for(int j=0;j<=i;j++)
printf("%d ",YH[i][j]);
printf("\n");
}
*/
}
void solve()
{
//计算原有系数
a%=MOD;
b%=MOD;
int temp=a;
for(int i=1;i<=n-1;i++)
a=(a*temp)%MOD;
temp=b;
for(int i=1;i<=m-1;i++)
b=(b*temp)%MOD;
ans=(a*b)%MOD;
//计算原有系数
//原有系数*杨辉三角对应的那个值
ans=(ans*YH[k][n])%MOD;
printf("%d\n",ans);
}
int main()
{
init();
readdate();
solve();
return 0;
}p2：聪明的质监员
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 200000 + 10;
int n, m, w[N], v[N], l[N], r[N];
long long s = 1e18, a[N], b[N], Y, S;
bool calc(int W) {
a[0] = b[0] = Y = 0;
for(int i=1; i<=n; i++) {
a[i] = a[i-1] + (w[i] >= W);
b[i] = b[i-1] + (w[i] >= W) * v[i];
}
for(int i=1; i<=m; i++)
Y += abs((a[r[i]] - a[l[i]-1]) * (b[r[i]] - b[l[i]-1]));
s = min(s, abs(S - Y));
return Y > S;
}
int main() {
freopen("qc.in", "r", stdin);
freopen("qc.out", "w", stdout);
scanf("%d %d %I64d", &n, &m, &S);
int p = 0, q = N, c = 1;
for(int i=1; i<=n; i++) {
scanf("%d %d", w+i, v+i);
p = min(p, w[i]), q = max(q, w[i]);
}
for(int i=1; i<=m; i++)
scanf("%d %d", l+i, r+i);
while(q - p > 1)
if(calc(c = (p + q) / 2)) p = c; else q = c;
printf("%I64d\n", s);
return 0;
}p3：观光公交
在这里我只上代码，也有较详细的注释。
至于贪心的论述将在我下一篇博文中详细解答
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 1000+10
#define MAXM 10000+10
using namespace std;
/*
贪心!!!
*/
struct NODE
{
long long t;
int from;
int to;
}person[MAXM];
int n,m,k;
int d[MAXN];//i—>i+1需要的时间
long long oversum[MAXN];//在该站点i以前有多少人下车
long long reach_time[MAXN];//车到达站点i的时间
long long latest[MAXN];//在站点i 最晚乘客到达的时间
long long s[MAXN];//如更改d[i]会影响到的站点从[i+1——>s[i]]
long long ans;
void init()
{
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
}
void readdate()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<n;i++)
scanf("%d",&d[i]);
for(int i=1;i<=m;i++)
{
scanf("%I64d%d%d",&person[i].t,&person[i].from,&person[i].to);
oversum[person[i].to]++;
latest[person[i].from]=max(latest[person[i].from],person[i].t);
}
return;
}
void pre()//处理最开始的reach_time,s,ans,oversum
{
//当第i-1个站台有乘客需要上车时，reach_time=latest[i-1]+d[i];
//当第i-1个站台无乘客需要上车时，reach_time=reach_time[i-1]+d[i];
//故可以得到公式：reach_time[i]=max(reach_time[i-1],latest[i-1])+d[i-1];
reach_time[1]=0;
for(int i=1;i<=n;i++)
reach_time[i]=max(reach_time[i-1],latest[i-1])+d[i-1];
//若reach_time[i+1]<=latest[i+1]时 s[i]=i+1;
//若reach_time[i+1]>latest[i+1]时 s[i]=s[i+1];
s[n]=n;s[n-1]=n;//初始最后两个站台，进行倒推
for(int i=n-2;i>1;i--)
if(reach_time[i+1]<=latest[i+1])
s[i]=i+1;
else s[i]=s[i+1];
//初始化ans；ans=(第i个人到达目的地的时间-他出发的时间)的总和
for(int i=1;i<=m;i++)
ans+=reach_time[person[i].to]-person[i].t;
//因为读入时oversum不确定，所以在这里处理oversum
for(int i=1;i<=n;i++)
oversum[i]=oversum[i-1]+oversum[i];
return;
}
void solve()
/*
每次找到最大的oversum[s[i]]-oversum[i]
在这时d[i]若减小会得到最优的ans减少
*/
{
long long maxval=0,index;
//找到最优使用加速器的地方
for(int i=1;i<=n;i++)
if(maxval<oversum[s[i]]-oversum[i])
if(d[i]>=1)
{
maxval=oversum[s[i]]-oversum[i];
index=i;
}
long long L=index,R=s[index];
d[index]--;//使用加速器
ans-=maxval;//更改ans
if(R==n) R=n-1;//特判
//再次更新reach_time
for(int i=L;i<=R;i++)
reach_time[i]=max(reach_time[i-1],latest[i-1])+d[i-1];
//再次更新s[i]
for(int i=R;i>=L;i--)
if(reach_time[i+1]<=latest[i+1])
s[i]=i+1;
else s[i]=s[i+1];
return;
}
void work()
{
//对于每一个加速器进行一次贪心
for(int i=1;i<=k;i++)
solve();
printf("%I64d\n",ans);
return;
}
int main()
{
init();
readdate();
pre();
work();
return 0;
}小结
对于此次考试，中等题掌握较差，两天都错在了第二题。
所以，在接下来的训练中要更加注重会的题和中等题的细致。
！！！！！！
NOIP2011
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。