Codeforces Round #103 (Div. 2) 被虐记

第二次参加cf，饮恨两题了

 

A：大水，分别求出最高的人和最矮的人所在的位置。如果有多个人高度相同且都是最高的话要选靠左边的，有多个人高度相同且都是最矮的话要选靠右边的。然后计算把最高的人和最矮的人分别安排到左边和右边需要走的最短步数即可。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=105;
int num[nMax];
int main(){
    int n,i,j,high,low,h,l,ans;
    while(scanf("%d",&n)!=EOF){
        high=-1;
        low=200;
        for(i=1;i<=n;i++){
            scanf("%d",&num[i]);
            if(num[i]>high){   //大的数在左边
                high=num[i];
                h=i;
            }
            if(num[i]<=low){    //小的数字在右边
                low=num[i];
                l=i;
            }
        }
     //   cout<<high<<' '<<h<<" "<<low<<" "<<l<<endl;
        if(h<l){
            ans=h-1+n-l;
        }
        else{
            ans=h-1+n-l-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

B题代码实在太囧~~发出来怕被bs

 

 

C:这道本来应该能在最后精彩绝杀的题目却最终饮恨了~~这就叫惜哉剑术疏，奇功遂不成吧。

    大致题意就是：如果一个字符串a在打乱排列后可以变成另一个字符串b，则我们称a和b互为anagram，比如“aba”和“aab”就是互为anagram。“aab”和“abc”,“bba”都不互为anagram。

    如果有一个带‘?’的字符串a，在把‘?’替换成一些特定的字符后能和字符串b互为anagram，我们称a为good，比如a为“a??”，b为“abc”，则认为a是good。

    给出两个长度都是10^5数量级的字符串str1和str2，str1由小写字母和'?'组成，str2由小写字母组成。求出str1中可以分离出多少个good的连续子串。

    一开始看到10^5迟迟不敢下手，觉得会tle。后来下了好大决心才写了一个遍历长度为10^5字符串的代码。没想到却pass掉了。比赛测试总数据的时候很囧的被tle掉了。以为是有什么高级牛逼的算法，跟别人对比以后才发现字符串长度的定义少了一个0，杯具啊

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=105;
int cha1[300];
int cha2[300];
bool check(int l){
    int need=0;
    for(int i='a';i<='z';i++){
        if(cha1[i]>cha2[i]){
            return 0;
        }
        need=cha2[i]-cha1[i];
    }
    if(need==0)return 1;
    if(need==cha1['?'])return 1;
}
int main(){
    int i,j,len1,len2,ans;
    char str1[100005],str2[100005];   //这里这里这里！！
    while(scanf("%s%s",str1,str2)!=EOF){
        ans=0;
        memset(cha2,0,sizeof(cha2));
        memset(cha1,0,sizeof(cha1));
        len1=strlen(str1);            //长串
        len2=strlen(str2);            //短串
        if(len2>len1){
            cout<<0<<endl;
            continue;
        }
        for(i=0;i<len2;i++){
            cha1[str1[i]]++;
        }
        for(i=0;i<len2;i++){
            cha2[str2[i]]++;
        }
        for(i=len2-1;i<=len1-1;i++){   //str2尾部所在的位置
           // cout<<len2<<" "<<len1<<endl;
            if(check(i)){
                ans++;
            }
            cha1[str1[i-len2+1]]--;
            cha1[str1[i+1]]++;
        }
        cout<<ans<<endl;
    }
    return 0;
} 

 

D是个最短路好题！可惜等到赛后才ac掉~真囧。

    给出一个由n个点m条带权边组成的无向图。给出图中的一个点s和一个长度值l。求图中到s点最短距离为l的点的数量，包括节点上的点和边上的点。

    首先统计所有节点中距离s最短为l的点的个数，再统计所有边中含有那种点的个数，统计边的时候细节需要特别的注意！！最后输出总和即可。

献上代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=600050;
const int mMax=1000050;
const int inf=1<<28;
struct{
    int u,v, next;
    int  w;
}edge[mMax];
int n, k, head[nMax];
int dis[nMax];
int que[nMax],m,sum[nMax];
bool vis[nMax];

void addedge(int a,int b,int w){
    edge[k].w = w;
    edge[k].u=a;
    edge[k].v=b;
    edge[k].next=head[a];
    head[a]=k;k++;
}

void spfa(int s){      //始点，终点，总点数
    int i, hhead = 0, tail = 1;    //  长注释的地方就是从最小费用改到最大费用时需要变动的地方
    for(i = 0; i <= n; i ++){
        dis[i] = inf;////////////
        vis[i] = false;
    }
    dis[s] = 0;
    que[0] = s;
    vis[s] = true;
    while(hhead != tail){
        int u = que[hhead];
        vis[u] = false;
        for(i=head[u];i!=0;i=edge[i].next){//for(i = head[u]; i != 0; i = edge[i].next){
            int v = edge[i].v;
            if(dis[v] >dis[u] + edge[i].w){////////
                dis[v] = dis[u] + edge[i].w;
                if(!vis[v]){
                    vis[v] = true;
                    que[tail ++] = v;
                    if(tail == nMax) tail = 0;
                    //if(++sum[v] > n) return false;     //  不包含初始的进栈。
                }
            }
        }
        hhead++;
        if(hhead ==nMax) hhead = 0;
    }
}
int main(){
    int i,j,m,s,a,b,c,l,ans,u,v,w,p;
    char str[10];
    while(scanf("%d%d%d",&n,&m,&s)!=EOF){
        k=1;
        ans=0;
        memset(head,0,sizeof(head));
        while(m--){
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
            addedge(b,a,c);
        }
        scanf("%d",&l);
        spfa(s);
        for(i=1;i<=n;i++){
            if(dis[i]==l)ans++;
        }
        for(i=1;i<k;i+=2){
            u=edge[i].u;
            v=edge[i].v;
            w=edge[i].w;
            if(dis[u]<l){
                if(dis[u]+edge[i].w>l){
                    p=l-dis[u];
                    if(dis[v]+w-p>l){
                        ans++;
                    }
                }
            }
            if(dis[v]<l){
                if(dis[v]+edge[i].w>l){
                    p=l-dis[v];
                    if(dis[u]+w-p>l){
                        ans++;
                    }
                    if(dis[u]+w-p==l){
                        ans++;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

评论

2 楼 暴风雪 2012-01-26  

f12345 写道

膜拜，质的改变啊。

嘿嘿，不过这场打得真的很囧，话说你是？

1 楼 f12345 2012-01-26  

膜拜，质的改变啊。