省常中联测题选III HGOI1020

我根本就没看到附加题!!!!

强烈谴责把附加题单独分开的出题人。

今天的教训让我体会到读题的重要性orz


T1 Factory

题目描述

    机器人的哀嚎传遍了整座工厂,于是,Hobo 决定带着他们一起逃离这里。工
厂的传送带上依次排列着N 个机器人,其中,第i 个机器人的质量为Ai。Hobo
经过仔细观察,发现:
1.来自同一个家族的机器人,在这N 个机器人中一定是连续的一段。
2.如果从第i 个机器人到第j 个机器人都来自同一个家族,那么Ai 到Aj 从
小到大排序后一定是公差大于1 的等差数列的子序列。
Hobo 发现,不同家族的个数越少,机器人就会越团结,成功逃离工厂的概率
就会越高。Hobo 想知道,这N 个机器人最少来自几个不同的家族呢?

解析

  • 一眼题。
  • 若属于同一个等差数列的子序列(公差大于1),则其差值的gcd不等于1.根据这个进行判断,并且用set判重就可以做出来了。

AC程序

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
ll read(){
    ll x=0,w=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
ll gcd(ll a,ll b){
    return (b?gcd(b,a%b):a);
}
ll n,src[100010],xt[100010];
#define ABS(X) ((X)>0?(X):-(X))
int main(){
    //freopen("factory.in","r",stdin);
    //freopen("factory.out","w",stdout);
    n=read();
    for (Rint i=1;i<=n;i++)
        src[i]=read();
    if (n==1){
        puts("1");
        return 0;
    }
    for (Rint i=1;i<n;i++)
        xt[i]=ABS(src[i+1]-src[i]);
    set<ll> st;
    st.clear();
    ll pt=1,res=0;
    while(pt<n&&xt[pt]<=1) pt++,res++;
    st.insert(src[pt]);
    st.insert(src[pt+1]);
    ll rt=xt[pt],tmp;
    for (Rint i=pt+1;i<n;i++){
        tmp=gcd(rt,xt[i]);
        if(tmp==1||st.count(src[i+1])){
            rt=xt[i+1];
            res++;
            st.clear();
        }else
            rt=tmp;
        st.insert(src[i+1]);
    }
    res++;
    printf("%lld",res);
    return 0;
}

T2 Friendship

题目描述

    Eddie 终于意识到了改造计划的本质,恨自己没能阻止这一切的发生。在
Millie 和Simon 的帮助下,他拆开了Hobo 的电路板,决定帮助Hobo 找回记忆。
一开始,Hobo 的中央处理器有N 个元件(编号为1 到N),每一个元件都存
储了一段时间的记忆。也就是说,每个元件都可以看做一个集合。...,组成一个新
的元件,新元件的编号等于融合之前元件的总个数加一。当然,参与融合的K
个元件融合之后依然存在,并且每个元件至多参与一次融合。
由于元件的容量有限,Eddie 没有能力唤醒Hobo 全部的回忆,所以他会用下
列两种方式来融合元件:
1.集合的交:...
2.集合的并:...

解析(std)

  • 考虑离线处理。先将所有的加边操作读进来,建树求DFS序
  • 对于询问操作,若x和y的DFS区间不存在包含关系,则答案为0。
  • 否则,若x是y的祖先,则答案为1当且仅当y的父亲到x都是”交”;若y是x的祖先,则答案为1当且仅当x的父亲到y都是”并”。
  • K = 1时 交 和 并 等价,需特判。
  • 时间复杂度O(N)

AC程序

#include<bits/stdc++.h>
#define rep(i,j,k) for((i)=(j);(i)<=(k);++i)
#define per(i,j,k) for((i)=(j);(i)>=(k);--i)
using namespace std;
const int N = 2100000;
int dfn[N],last[N],f[N][2],low[N],du[N],a[N],dep[N],n,m,tot,x,y,t,op,k,i,j,u,v,cnt,tim;
struct edge{int v,next;}e[N]; 
struct query{int x,y;}Q[N];
int inline read(){
    char ch=getchar();int z=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){z=z*10+ch-'0';ch=getchar();}
    return z*f;
}
void add(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;}
void dfs(int x){
    dfn[x]=++tim;
    for(int i=last[x];i;i=e[i].next){
        if(a[x]==0 || du[x]==1) f[e[i].v][0]=f[x][0]+1; else f[e[i].v][0]=0;
        if(a[x]==1 || du[x]==1) f[e[i].v][1]=f[x][1]+1; else f[e[i].v][1]=0;
        dep[e[i].v]=dep[x]+1; dfs(e[i].v);
    }
    low[x]=tim;
}
int main(){
    freopen("friendship.in","r",stdin);
    freopen("friendship.out","w",stdout);
    n=read();m=read();tot=0;
    rep(i,1,m){
        t=read();
        if(t==0){
            op=read();k=read();++n;
            rep(j,1,k){u=read();add(n,u);}
            a[n] = op; du[n] = k;
        }else{x=read();y=read();Q[++tot]=(query){x,y};}
    }
    per(i,n,1) if(!dfn[i]) dfs(i);
    rep(i,1,tot){
        u = Q[i].x; v = Q[i].y;
        if(dfn[u]<=dfn[v]&&low[v]<=low[u])
            if(f[v][0] >= dep[v] - dep[u]) puts("1");
            else puts("0");
        else if(dfn[v]<=dfn[u]&&low[u]<=low[v])
            if(f[u][1] >= dep[u] - dep[v]) puts("1");
            else puts("0");
        else puts("0");
    }
    return 0;
}

T3 Empire

题目描述

    ...依次排列着(N+1)座城市,0 号城市是出发地,N 号城市是王宫。
...Eddie 和Hobo 可以在当前的城市
上车,并且在之后的某一座城市下车。从第(i-1)座城市乘坐到第i 座城市需要
花费Ai 的费用。同时,在第i 座城市上车需要缴纳Bi 的税款。...
珍娜女王为了促进Sunshine Empire 的繁荣发展,下令:如果连续地乘坐一
段火车的费用大于这次上车前所需缴纳的税款,则这次上车前的税款可以被免
除,否则免去乘坐这段火车的费用。
然而,为了保证火车的正常运行,每一次乘坐都不能连续经过超过K 座城市
(不包括上车时所在的城市),并且,Eddie 和Hobo 的移动范围都不能超出
Sunshine Empire。Eddie 想知道,到达王宫的最小总花费是多少?

解析

  • O(n*k)的dp方程很容易想出来,即为$$f(x)=min(f(j)+max(b(j),a(i)-a(j)))$$
  • 稍微研究一下可以发现,a(i)(已处理为前缀和)单调递增,所以如果max项右边大,之后就一定选择右边。所以考虑用两个小根堆一个维护f[j]+b[j],另一个维护f[j]-a[j]从第一个堆出来放到第二个堆即可注意若超过k的范围也要弹出。

AC程序

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
ll a[500010],b[500010],n,k,f[500010];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q1,q2;
int main(){
    //freopen("empire.in","r",stdin);
    //freopen("empire.out","w",stdout);
    n=read(),k=read();
    for (Rint i=1;i<=n;i++)
        a[i]=read()+a[i-1];
    for (Rint i=1;i<=n;i++)
        b[i-1]=read();
    memset(f,0x7f,sizeof(f));
    f[0]=0;
    q1.push(make_pair(f[0]+b[0],0));
    #define F1 prr.first
    #define F2 prr.second
    #define T1 prr.first
    #define T2 prr.second
    pair<ll,ll> prr;
    for (Rint i=1;i<=n;i++){
        while(!q1.empty()&&((prr=q1.top()).first||1)&&(F2<i-k||F1<f[F2]+a[i]-a[F2])){
            q2.push(make_pair(f[F2]-a[F2],F2));
            q1.pop();
        }
        if (!q1.empty()) 
            f[i]=min(f[i],F1);
        while(!q2.empty()&&((prr=q2.top()).first||1)&&T2<i-k)
            q2.pop();
        if (!q2.empty())
            f[i]=min(f[i],a[i]+T1);
        q1.push(make_pair(f[i]+b[i],i));
    }
    printf("%lld",f[n]);
    return 0;
}

T4 Colony

附加题,太简单,懒得写了。

AC程序

#include<bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
int n,k;
ll cnt=0;
int l[300010],f[300010];
int main(){
    scanf("%d%d",&n,&k);
    char tmp[30];
    for(int i=1;i<=n;i++){
        scanf("%s",tmp);
        l[i]=strlen(tmp);
    }
    for(int i=1;i<=n;i++){
        cnt+=f[l[i]];
        f[l[i]]++;
        if(i>k)f[l[i-k]]--;
    }
    printf("%lld",cnt);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注