2017.09.10校内训练

T1：CCT

 

题解：对于一个特征a₁a₂a₃…a_m,我们可以用(a₁-a₁)(a₂-a₁)…(a_m-a₁)来表示它。然后再做对每一位前缀和(s₁-s₁)(s₂-s₁)(s₃-s₁)…(s_m-s₁)。易发现：当两个位置i,j前缀和相同时，i+1到j或i到j-1即是一种可行的选法。用set记住每个前缀和最早出现的位置，对每个位置在set中查询并更新答案即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
int n,x,ans=0,k;
struct node{
    int num;
    int dif[31];
    bool operator <(const node &b)const{
        int i;
        for(i=1;i<k;++i){
            if(dif[i]!=b.dif[i])  return dif[i]<b.dif[i];
        }
        return false;
    }
}t;
std::set<node> s;
std::set<node>::iterator it;
int sum[100001][31];
int max(int a,int b){
    return a>b?a:b;
}
int main(){
    freopen("cct.in","r",stdin);
    freopen("cct.out","w",stdout);
    scanf("%d%d",&n,&k);
    int i,j;
    for(i=1;i<=n;++i){
        scanf("%d",&x);
        for(j=1;j<=k;++j){
            sum[i][j]=sum[i-1][j];
            if(x&(1<<(j-1))) sum[i][j]++;
        }
    }
    ans=0;t.num=0;
    for(i=1;i<k;++i){
        t.dif[i]=0;
    }
    s.insert(t);
    for(i=1;i<=n;++i){
        t.num=i;
        for(j=1;j<k;++j){
            t.dif[j]=sum[i][j]-sum[i][j+1];
        }
        it=s.find(t);
        if(it==s.end()) s.insert(t);
        else ans=max(ans,i-(*it).num);
    }
    printf("%d\n",ans);
    return 0;
}

- - - - - - - - - - - - - - - - - 

T2：MHM

 

题解：二分上课的节数并check。类似题目请参考NOIP2015跳石头。注意在输入完要先排序。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,k,l,r,mid,ans;
int a[50010],wake[50010];
bool check(int x){
    int cnt=0,now=0;
    for(int i=1;i<=m;++i){
        if(wake[i]+now<x){
            now+=wake[i]+1;
            cnt++;
        }
        else  now=0;
    }
    if(cnt>k)  return false;
    else  return true;
}
int main(){
    freopen("mhm.in","r",stdin);
    freopen("mhm.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    int i,j;
    for(i=1;i<=m;++i){
        scanf("%d",a+i);
    }
    a[0]=0;a[++m]=n;
    sort(a,a+m+1);
    for(i=1;i<=m;++i){
        wake[i]=a[i]-a[i-1]-1;
    }
    l=0;r=n;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid))  l=mid;
        else  r=mid-1;
    }
    if(check(r))  ans=r;
    else  ans=l;
    printf("%d\n",ans);
    return 0;
}

- - - - - - - - - - - - - - - - 

T3：AAFA

 

题解：按照截至时间排序从前往后选。当选到第i个时，若已经选择的题目数量小于t_i，则该时间选择它必定比不选更优。若已经选择的题目数量等于t_i，则比较第i题的收益和已选择题目的最小收益，取更优者。已选择的题目用优先队列维护。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
struct node{
    ll t,w;
}te[100010];
int n,ti=0;
ll ans=0,s;
bool cmp(node a,node b){
    if(a.t==b.t)  return a.w>b.w;
    return a.t<b.t;
}
priority_queue<int,vector<int>,greater<int> > pq;
int main(){
    freopen("aafa.in","r",stdin);
    freopen("aafa.out","w",stdout);
    scanf("%d",&n);
    int i,j;
    for(i=1;i<=n;++i){
        scanf("%lld%lld",&te[i].t,&te[i].w);
        //ti=max(ti,te[i].t);
    }
    sort(te+1,te+n+1,cmp);
    int cnt=1;
    ans=0;
    for(i=1;i<=n;++i){
        s=pq.size();
        if(s<te[i].t)  pq.push(te[i].w);
        else{
            if(s==te[i].t){
                if(pq.top()<te[i].w){
                    pq.pop();
                    pq.push(te[i].w);
                }
            }
        }
    }
    ans=0;
    while(!pq.empty()){
        ans+=pq.top();pq.pop();
    }
    printf("%lld\n",ans);
    return 0;
}

- - - - - - - - - - - - - 

T4：ZZI

 

题解：在一个房子造发电机可以看作把它和已经通电的房子连边，权值为0，因此改变边权直接跑最小生成树即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
int n,ans,minn=inf;
int v[310],dist[310];
int a[310][310];
bool used[310];
int min(int a,int b){
    return a<b?a:b;
}
int prim(){
    int next,maxn,res=0;
    int i,j;
    for(;;){
        next=-1;maxn=inf;
        for(i=1;i<=n;++i){
            if(!used[i] &&dist[i]<maxn){
                maxn=dist[i];next=i;
            }
        }
        if(next==-1)  break ;
        used[next]=true;
        res+=dist[next];//dist[next]=0;
        for(i=1;i<=n;++i){
            if(!used[i])  dist[i]=min(dist[i],a[next][i]);
        }
    }
    return res;
}
int main(){
    freopen("zzi.in","r",stdin);
    freopen("zzi.out","w",stdout);
    scanf("%d",&n);
    int i,j;
    minn=inf;
    for(i=1;i<=n;++i){
        scanf("%d",dist+i);
    }
    for(i=1;i<=n;++i){
        for(j=1;j<=n;++j){
            scanf("%d",&a[i][j]);
        }
    }
    printf("%d\n",prim());
    return 0;
}