2011noip解题报告
noco
2018-10-16 21:57:05
## Day1T1 铺地毯（搜索 枚举）
给定一堆矩形 求最后覆盖地面某个点的最上面的那张矩形的编号
~~似乎不需要题解~~
粘上一年前的丑代码
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,x,y,ans=-1;
struct dt
{
int x,y,df,ds;
}a[10000+10];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y>>a[i].df>>a[i].ds;
cin>>x>>y;
for(int i=1;i<=n;i++)
{
int tmpx=a[i].x+a[i].df;
int tmpy=a[i].y+a[i].ds;
if(x<=tmpx&&x>=a[i].x&&y<=tmpy&&y>=a[i].y)ans=i;
}
cout<<ans<<endl;
return 0;
}
```
### Day1T2选择客栈（贪心 思维）
**请最好在LOJ上完成此题**~~注意开long long~~
丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0~k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p 。
他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。
刚开始读题的时候总给我一个感觉，那就是k可以不用。因为我们有时根本没必要去关心它的编号具体是什么。后来发现还真是。
如果是暴力枚举客栈的话，不能同时枚举两个客栈，那样会超时，所以只能同时枚举一个。我们枚举第二个客栈，然后用第二个客栈反推出前面的方案数。
思路就是，从1到n枚举，输入color和price的值，我们需要记录一个距离第二个客栈最近的咖啡厅价钱合理的客栈位置，用一个now变量记录。
开三个辅助数组，last[i]表示最后一个以i为颜色的客栈的位置，cnt[i]表示以i为颜色的客栈总数，sum[i]可以看作是一个临时数组，用来存储当前的方案数。
可以这么想，当前枚举到一个客栈i，这个i是第二个客栈，那么显然第一个客栈一定在第二个客栈之前，编号必定是0~i-1之间的一个数。如果我发现枚举的时候在某一个客栈前面有一个价钱合理的咖啡厅，那么在这之前的任何一个同色客栈都是第一个客栈可以选的，那么统计一下数量，这就是当前的方案数。
然后更新last数组，更新ans，让cnt[color]++，这样从左到右地推过来就好了。
这个解法简化于暴力算法，暴力算法要循环三层，一层1客栈，二层2客栈，3层合理的位置，这样做显然不行，而我们做的就是去优化掉两层，而是从枚举2客栈出发推出1客栈的位置和所有可行方案，所以这样做是正确的。最后输出即可。
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e6+500;
int n,k,p;
int color,price;
int last[N];
int cnt[N];
int sum[N];
int ans,now;
int main(){
scanf("%d%d%d",&n,&k,&p);
for(register int i=1;i<=n;i++){
scanf("%d%d",&color,&price);
if(price<=p)now=i;
if(now>=last[color])sum[color]=cnt[color];
last[color]=i;
ans+=sum[color];
cnt[color]++;
}
printf("%d\n",ans);
return 0;
}
```
### Day1T3Mayan游戏（搜索 模拟 剪枝 码农）
题目过长 此处略去
**DFS的剪枝**：
1.相同颜色的方块可以跳过（显而易见）；
2.还有一个比较难想的剪枝：
结论：只有右边有方块才move，左边没有方块才move；
证明（自己瞎写的）：
（你正在搜i列）若左面有方块，那么你会在搜i-1列时将其右移，和你在i列时左移是等效的，所以可以减掉；
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=10;
int n;
int mp[N][N];
int last[N][N][N];
bool del[N][N];
int ans[N][N];
inline void build(int idx){
for(register int i=1;i<=5;i++){
for(register int j=1;j<=7;j++){
last[i][j][idx]=mp[i][j];
}
}
}
inline void pushdown(){
int zero;
for(register int i=1;i<=5;i++){
zero=0;
for(register int j=1;j<=7;j++){
if(!mp[i][j]){
zero++;
continue;
}
if(!zero)continue;
mp[i][j-zero]=mp[i][j];
mp[i][j]=0;
}
}
}
inline bool delete_it(){
bool flag=false;
for(register int i=1;i<=5;i++){
for(register int j=1;j<=7;j++){
if(2<=i&&i<=4){
if(mp[i][j]&&mp[i][j]==mp[i-1][j]&&mp[i][j]==mp[i+1][j]){
flag=true;
del[i][j]=true;
del[i-1][j]=true;
del[i+1][j]=true;
}
}
if(2<=j&&j<=6){
if(mp[i][j]&&mp[i][j]==mp[i][j-1]&&mp[i][j]==mp[i][j+1]){
flag=true;
del[i][j]=true;
del[i][j-1]=true;
del[i][j+1]=true;
}
}
}
}
if(!flag)return flag;
for(register int i=1;i<=5;i++){
for(register int j=1;j<=7;j++){
if(del[i][j]){
del[i][j]=false;
mp[i][j]=0;
}
}
}
return flag;
}
inline void move(int i,int j,int g){
int x=mp[i][j];
mp[i][j]=mp[i+g][j];
mp[i+g][j]=x;
pushdown();
while(delete_it())pushdown();
}
inline bool check(){
for(register int i=1;i<=5;i++)
if(mp[i][1])
return false;
return true;
}
inline void clear(int idx){
for(register int i=1;i<=5;i++){
for(register int j=1;j<=7;j++){
mp[i][j]=last[i][j][idx];
}
}
ans[idx][1]=-1;
ans[idx][2]=-1;
ans[idx][3]=-1;
}
void dfs(int x){
if(check()){
for(register int i=1;i<=n;i++){
for(register int j=1;j<=3;j++){
printf("%d ",ans[i][j]);
}
printf("\n");
}
exit(0);
}
if(x>=n+1)return;
build(x);
for(register int i=1;i<=5;i++){
for(register int j=1;j<=7;j++){
if(mp[i][j]){
if(i<=4&&mp[i][j]!=mp[i+1][j]){
move(i,j,1);
ans[x][1]=i-1;
ans[x][2]=j-1;
ans[x][3]=1;
dfs(x+1);
clear(x);
}
if(i>=2&&mp[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);
clear(x);
}
}
}
}
}
int main(){
int a;
scanf("%d",&n);
for(register int i=1;i<=5;i++){
for(register int j=1;j<=8;j++){
scanf("%d",&a);
if(a==0)break;
mp[i][j]=a;
}
}
memset(ans,-1,sizeof(ans));
dfs(1);
printf("-1\n");
return 0;
}
```
------------
### Day2T1计算系数（数学）
给定一个多项式$(by+ax)^k$请求出多项式展开后$x^n \times y^m$项的系数。
杨辉三角+组合数递推
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int mod=1e4+7;
const int N=1e3+500;
int a,b,k,n,m;
int p;
int ans;
int c[N][N];
int qpow(int a,int b){
int ret=1;
while(b){
if(b&1)ret=(ret*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ret%mod;
}
inline void prepare(){
a=qpow(a,n);
b=qpow(b,m);
for(register int i=1;i<=k;i++){
c[i][0]=1;
c[i][i]=1;
}
}
inline void solve(){
p=(n<m)?n:m;
for(register int i=2;i<=k;i++){
for(register int j=1;j<=p;j++){
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
}
inline void get_ans(){
ans=(a*b)%mod;
ans=(ans*c[k][p])%mod;
}
int main(){
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
a%=mod;b%=mod;
prepare();
solve();
get_ans();
printf("%d\n",ans);
return 0;
}
```
### Day2T2聪明的质检员（二分+分析）
使W取一个最合适的值，使每一个所给区间内满足条件的矿石的数量乘上价值之和，最后计算总和使与S最近
本题是一个比较明显的二分题，显然可以看出来这个标准值S是可以二分的，之后如果暴力$O(nmlog1e6)$就是50分。
但我们显然不用暴力，这里我们可以先预扫一遍数组，并用前缀和存w和v，之后再一个$O(m)$暴力判断就可以了。
和大于标准时加大l以加大mid，小于时减少r。
并一定要注意l和r的初始大小，l为所有值中最小-1~~虽然貌似不减也可以过~~，r为最大值+1。
再次放上一年前的丑代码QAQ
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
int n,m;
ll s;
ll ans;
int w[200500],v[200500];
int l[200500],r[200500];
ll lmin(ll x,ll y)
{
if(x>y)
return y;
if(x<y)
return x;
}
ll lmax(ll p,ll q)
{
if(p>q)
return p;
if(p<q)
return q;
}
ll labs(ll a)
{
if(a<0)
return -a;
else return a;
}
bool yes(int k)
{
int g[200500],t[200500];
ll re=0;
memset(g,0,sizeof(g));
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++)
{
if(w[i]>=k)
{
g[i]=g[i-1]+v[i];
t[i]=t[i-1]+1;
}
else{
g[i]=g[i-1];
t[i]=t[i-1];
}
}
ll u,v;
for(int i=1;i<=m;i++)
{
u=g[r[i]]-g[l[i]-1];
v=t[r[i]]-t[l[i]-1];
re+=u*v;
}
ans=lmin(ans,labs(re-s));
return re-s>0;
}
int main()
{
ll lf=0,ri=-1;
scanf("%d%d%lld",&n,&m,&s);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&v[i]);
ri=lmax(ri,(ll)w[i]);
}
for(int i=1;i<=m;i++)scanf("%d%d",&l[i],&r[i]);
ll mid;
ri++;
ans=1e20;
while(ri>lf)
{
mid=(ri+lf)>>1;
if(!yes(mid))ri=mid;
else lf=mid+1;
}
printf("%lld",ans);
return 0;
}
```
### Day2T3观光公交（贪心+思维+优先队列）
风景迷人的小城$Y$市，拥有$n$个美丽的景点。由于慕名而来的游客越来越多，$Y$市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。
用优先队列优化一下...
取出加速器收益最大的左端点,再加入被劈开的若干部分...
复杂度分析:
首先考虑进入优先队列中的元素个数,观察doit(),只会拆区间或荒废左端点,$n$级别的元素个数...
每个元素需要区间修改与区间查询,暴力$O(n)...$(写数据结构可以变$log..$,)
最坏$n^2$...
```cpp
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
void read(int &x){
x=0; int fff=0; char c=getchar();
for ( ;!(c>='0'&&c<='9');c=getchar()) if (c=='-') fff=1;
for ( ; (c>='0'&&c<='9');c=getchar()) x=(x<<3)+(x<<1)+c-'0';
if (fff) x=-x;
}
int n,m,k,a[1010],d[1010],b[1010],v[1010],t,x,y,ans;
struct Node{
int l,r,tim,val;
}tmp;
struct cmp{
bool operator ()(Node nd1,Node nd2){
return nd1.val < nd2.val;
}
};
priority_queue<Node,vector<Node>,cmp>q;
void doit(int l,int r){
if (l>=r) return;
if (d[l]==0){ doit(l+1,r); return; }
for (int i=l+1;i<r;i++) if (a[i]>=b[i]){
doit(l,i); doit(i,r); return;
}
int mn=d[l],val=v[r];
for (int i=l+1;i<r;i++) mn=min(mn,b[i]-a[i]), val+=v[i];
d[l]-=mn; for (int i=l+1;i<r;i++) b[i]-=mn;
q.push((Node){l,r,mn,val});
}
int main(){
read(n); read(m); read(k);
for (int i=1;i<n;i++) read(d[i]);
for (;m--;){
read(t), read(x), read(y);
a[x]=max(a[x],t), ans-=t;
v[y]++;
}
for (int i=1;i<n;i++) b[i+1]=max(b[i],a[i])+d[i];
for (int i=2;i<=n;i++) ans+=v[i]*b[i];
for (doit(1,n);!q.empty()&&k;){
tmp=q.top(); q.pop();
ans-=tmp.val*min(tmp.tim,k);
k-=min(tmp.tim,k);
if (k) doit(tmp.l,tmp.r);
}
printf("%d",ans);
}
```