2017 清北济南考前刷题Day 2 morning

期望得分：100+30+60=190

实际得分：100+30+30=160

T1

最优方案跳的高度一定是单调的

所以先按高度排序

dp[i][j] 跳了i次跳到j

枚举从哪儿跳到j转移即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 51

struct node
{
    int c,h;
}e[N];

int dp[N][N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

bool cmp(node p,node q)
{
    return p.h<q.h;
}

int main()
{
    freopen("meet.in","r",stdin);
    freopen("meet.out","w",stdout);
    int n;
    read(n); 
    for(int i=1;i<=n;i++) read(e[i].c);
    for(int i=1;i<=n;i++) read(e[i].h);
    sort(e+1,e+n+1,cmp);
    memset(dp,63,sizeof(dp));
    for(int i=1;i<=n;i++) dp[0][i]=e[i].c;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<j;k++)
                dp[i][j]=min(dp[i][j],dp[i-1][k]+e[j].h-e[k].h);
            dp[i][j]+=e[j].c;
        }
    int t;
    read(t);
    for(int i=n;i>=0;i--)
        for(int j=1;j<=n;j++)
            if(dp[i][j]<=t) { printf("%d",i+1); return 0; }
}

View Code

T2

设给出的数是b1，b2，……

解为a1，a2……

那么可以得到 b1=a1+a2，b2=a1+a3

如果再知道 a2+a3=X，就可以解出a1，a2，a3

在b中把b1 b2 X 删去

剩下的最小的一定是 a1+a4，解出a4

再把a2+a4 ，a2+a4 删去,剩下的最小的一定是a1+a5

以此类推，解出所有的a

即

每确定一个ai
就把 aj+ai j∈[1,i) 全删去
剩下的最小的一定是a1 和ai+1 的和

#include<cstdio>
#include<cstring> 
#include<iostream>
#include<algorithm>

using namespace std;

int n,m,tot;

#define N 302

int b[N*N];

int ans[N*N][N],t[N];

bool use[N*N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar();     }
}

void work(int x)
{
    if((b[1]+b[2]+b[x])&1) return;
    t[2]=b[1]-b[2]+b[x]>>1;
    t[1]=b[1]-t[2];
    t[3]=b[2]-t[1];
    memset(use,false,sizeof(use));
    use[1]=use[2]=use[x]=true;
    int r,pos;
    for(int i=3,k=4;i<=m;++i)
    {
        if(use[i]) continue;
        t[k]=b[i]-t[1];
        for(int j=1;j<k;++j)
        {
            r=t[j]+t[k];
            pos=lower_bound(b+1,b+m+1,r)-b;
            if(b[pos]!=r) return;
            while(pos<m && use[pos] && b[pos]==r) pos++;
            if(b[pos]!=r) return;
            use[pos]=true;
        }
        k++;
    }
    tot++;
    for(int i=1;i<=n;i++) ans[tot][i]=t[i];
}

int main()
{
    freopen("city.in","r",stdin);
    freopen("city.out","w",stdout);
    read(n);
    m=n*(n-1)/2;
    for(int i=1;i<=m;++i) read(b[i]);
    sort(b+1,b+m+1);
    for(int i=3;i<=m;++i) 
    {
        if(i>1 && b[i]==b[i-1]) continue;
        work(i);
    }
    printf("%d
",tot);
    for(int i=1;i<=tot;++i) 
    {
        for(int j=1;j<=n;++j) printf("%d ",ans[i][j]);
        printf("
");
    } 
}

View Code

T3

分块

因为街灯上的数不超过1e4，所以p最多有1e4个

用vector[i][j] 存下%i=j 的数的位置 i<=100

当p<=100 时，直接在vector[p][v] 里二分在区间[l,r]内的最左位置和最右位置

再用一个vector[i] 存下所有的街灯数位i的位置

当p>100 时，%p=v 的数有v，v+p，v+2p……

直接枚举这些数，最多100个，在vector[i] 里二分在区间[l,r]内的最左位置和最右位置

#include<cstdio>
#include<vector>
#include<iostream>

using namespace std;

#define N 100001

int a[N];

vector<int>V1[101][101];
vector<int>V2[10001];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar();  }
}

int main()
{
    freopen("light.in","r",stdin);
    freopen("light.out","w",stdout);
    int n,m;
    read(n); read(m);
    for(int i=1;i<=n;++i) read(a[i]),V2[a[i]].push_back(i);
    for(int i=1;i<=100;++i)
        for(int j=1;j<=n;++j)
            V1[i][a[j]%i].push_back(j);
    int l,r,p,v;
    int L,R,MID,TMP1,TMP2;
    int pos,tot;
    while(m--)
    {
        read(l); read(r); read(p); read(v);
        if(p<=100)
        {
            L=0; R=V1[p][v].size()-1;
            TMP1=TMP2=-1;
            while(L<=R)
            {
                MID=L+R>>1;
                if(V1[p][v][MID]>=l) TMP1=MID,R=MID-1;
                else L=MID+1; 
            }
            if(TMP1==-1) { puts("0"); continue; }
            L=TMP1; R=V1[p][v].size()-1;
            while(L<=R)
            {
                MID=L+R>>1;
                if(V1[p][v][MID]<=r) TMP2=MID,L=MID+1;
                else R=MID-1; 
            }
            if(TMP2==-1) { puts("0"); continue; }
            printf("%d
",TMP2-TMP1+1);
        }
        else
        {
            pos=v; tot=0;
            while(pos<=10000)
            {
                L=0; R=V2[pos].size()-1;
                TMP1=TMP2=-1;
                while(L<=R)
                {
                    MID=L+R>>1;
                    if(V2[pos][MID]>=l) TMP1=MID,R=MID-1;
                    else L=MID+1;
                }
                if(TMP1==-1) { pos+=p; continue; }
                L=TMP1; R=V2[pos].size()-1;
                while(L<=R)
                {
                    MID=L+R>>1;
                    if(V2[pos][MID]<=r) TMP2=MID,L=MID+1;
                    else R=MID-1;
                } 
                if(TMP2==-1) { pos+=p; continue; }
                tot+=TMP2-TMP1+1;
                pos+=p;
            }
            printf("%d
",tot);
        }
    }
}

View Code

60分暴力

#include<vector>
#include<cstdio>
#include<iostream>

using namespace std;

#define N 100001

int n,m,a[N];

int P;

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

namespace solve1
{
    int l,r,p,v,ans;
    void work()
    {
        while(m--)
        {
            read(l); read(r); read(p); read(v);
            ans=0;
            for(int i=l;i<=r;i++)
                if(a[i]%p==v) ans++;
            printf("%d
",ans);
        }
        
    }
}

namespace solve2
{
    vector<int>V[10001];
    void work()
    {
        int l,r,p,v;
        int L,R,MID,TMP1,TMP2;
        for(int o=1;o<=m;o++)
        {
            read(l); read(r); read(p); read(v);
            if(o==1)
            {
                P=p;
                for(int i=1;i<=n;i++) V[a[i]%P].push_back(i);
            }
            if(v>10000 || !V[v].size()) { puts("0"); continue; }
            L=0,R=V[v].size()-1; TMP1=-1;
            while(L<=R)
            {
                MID=L+R>>1;
                if(V[v][MID]>=l) TMP1=MID,R=MID-1;
                else L=MID+1;
            } 
            if(TMP1==-1 || V[v][TMP1]>r) { puts("0"); continue; }
            L=TMP1,R=V[v].size()-1; TMP2=-1;
            while(L<=R)
            {
                MID=L+R>>1;
                if(V[v][MID]<=r) TMP2=MID,L=MID+1;
                else R=MID-1;
            }
            if(TMP2==-1) { puts("0"); continue; }
            printf("%d
",TMP2-TMP1+1);
        }
    }
}

void init()
{
    read(n); read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    if(1ll*n*m<=1e6) solve1::work();
    else solve2::work();
}

int main()
{
    freopen("light.in","r",stdin);
    freopen("light.out","w",stdout);
    init();
}

View Code