普及转提高模拟赛第四场

这次是我打的最伤心的一次。。。

本来预计有300的，结果错误百出，主要有以下几点：

1.freopen注释掉了

2.using namespace std多加了一个D

总之来说就是比赛经验太少了。。。

T1：

贪心，比较水的题，大概就是sort一遍，然后取奇数位上的数

code:

scanf("%d",&n);

n*=2; 

for(int i=1;i<=n;i++)scanf("%d",&a[i]);

sort(a+1,a+n+1);

for(int i=1;i<=n;i+=2)ans+=a[i];

printf("%lld",ans);

T2:

这是一道最小生成树的模板题，prim，kruskal都可以

code:

int n,len,fa[10010],x,t;

long long ans;

struct node{

int x,y,z;

}v[10010];

int getfa(int x){

if(fa[x]==x) return x;

else{

    fa[x]=getfa(fa[x]);

    return fa[x];

}

}

bool cmp(node x,node y){

return x.z<y.z;

}

int main(){

freopen("net.in","r",stdin);

freopen("net.out","w",stdout);

scanf("%d",&n);

for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

        scanf("%d",&x),v[++len]=(node){i,j,x};

sort(v+1,v+len+1,cmp);

for(int i=1;i<=n;i++)fa[i]=i;

for(int i=1;i<=len;i++){

    if(t==n-1) break;

    int fx=getfa(v[i].x),fy=getfa(v[i].y);

    if(fx!=fy){t++;ans+=v[i].z;fa[fx]=fy;} 

}

printf("%lld",ans);

return 0;

}

T3:

这道题目的确比较考思维，可惜我只想到了树的做法。。。

分类讨论：

1.假如当前集合是一棵树（点数=边数+1），那么将ans乘上边数点数

2.假如当前集合是一个环加外向树（点数=边数），那么只有两种方案，ans*=2

3.假如边数>点数，那么就没有解，ans=0

code:

int n,m,x,y,e[100010],d[100010],fa[100010],ans=1;

int getfa(int x){

if(fa[x]==x) return x;

return fa[x]=getfa(fa[x]);

}

int main(){

freopen("girl.in","r",stdin);

freopen("girl.out","w",stdout);

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)fa[i]=i,d[i]=1; 

for(int i=1;i<=m;i++){

    scanf("%d%d",&x,&y);

    int fx=getfa(x),fy=getfa(y);

    if(fx==fy) e[fx]++; 

    else{

        fa[fx]=fy;

        d[fy]+=d[fx];

        e[fy]+=e[fx]+1;

    }

}

for(int i=1;i<=n;i++)

    if(fa[i]==i){

        if(e[i]>d[i]) ans=0;

        else if(e[i]==d[i]) ans=ans*2%mod;

        else ans=1ll*ans*d[i]%mod;

    }

printf("%d",ans%mod);

return 0;

}

T4:

这是一道找规律题，暴力能够40分（从0~n枚举，进制转换判断），但是我们是有梦想的人。。

经过找规律（其实是证明）发现，当i（k进制）=i（-k进制）时，只有偶数位上会有值（因为负数的偶次方等于正数）

然后通过数学方法求得方案数（其实就是数字个数）

code:

long long n,k,ans;

int a[110],m;

int main(){

freopen("endless.in","r",stdin);

freopen("endless.out","w",stdout);

scanf("%lld%lld",&n,&k);

while(n){

    a[++m]=(int)n%k;

    n/=k;

} 

for(int i=m;i>=1;i--){

    if(!a[i]) continue;

    if(!(i&1)){ans+=(long long)pow(k,(i+1)/2);break;}

    else ans+=(long long)pow(k,i/2)*a[i];

}

printf("%lld",ans);

return 0;

}

T5:

这本来说是线段树的水题，结果一看不是模板就不会做了啊，。

刚开始真的以为是什么可持久化线段树。。。

其实k<=10是可以用很暴力的方法做出来的。。

与区间求最值没有什么区别，只是还需要储存区间最值的位置，然后当我们求得区间最值时，将区间裂为两个，使得最大值不在其中

T6：

这是防AK题，所以很难。。

每次二分出一段区间，然后搜索一遍，判断是否能从1~n，知道不行，就能得出最长的区间（因为要求最少分组）

然后还需要求r的范围，但是由于我太弱，不打了。。

但是要注意，如果每次都要用memset来清空图的话，复杂度会达到O(n^2)。。

所以只需要每次将以l~mid为起点的边给删了就好了。。

code:

int l,r,mid,u,v,n,m,cnt,t,ans,vis[200010];

struct node{

int a,b;

}e[500010];

vector ed[200010];

void dfs(int x,int y){

if(vis[x]==t) return;

if(x==y){cnt++;return;}//编号相同，就到达了 

vis[x]=t;

for(int i=0;i<ed[x].size();i++)dfs(ed[x][i],y);//这应该是DFS吧。。 

//puts("1");

}

bool check(int x,int y){

for(int i=x;i<=y;i++)ed[e[i].a].push_back(e[i].b);//建图 

cnt=0;//cnt代表从1~n的方案数 

t++;//时间戳？ 

dfs(1,n);//开始搜 

//puts("2");

for(int i=x;i<=y;i++)ed[e[i].a].clear();

return cnt>0;//方案数大于0说明可以到达

}

void read(int &x){

char ch=getchar();

x=0;

while(ch<'0'||ch>'9') ch=getchar();

while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();

}

int main(){

freopen("road.in","r",stdin);

freopen("road.out","w",stdout);

read(n);read(m);

for(int i=1;i<=m;i++){

    read(u);read(v);

    e[i]=(node){u,v};

}

for(int i=1;i<=m;i++){

    l=i;r=m;

    while(l<=r){

        mid=l+r>>1;

        if(check(i,mid)) r=mid-1;

        else l=mid+1;  

    }

    i=r;

    ans++;

    //printf("%d\n",ans);

}

printf("%d",ans);

return 0;

}

这只是60分的代码。。

过几天加上预处理r的范围，就可以A了吧。。

heqingyu的博客

博客

评论