Chengrui's Blog

0%

发表于 分类于 Disqus：

做Good Bye 2014那个晚上做着练习的。

379A - New Year Candles：

这居然是协会十一时出的一道题，简单题不多说了。

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
int main(){
    int a,b,left,cnt;
    while(scanf("%d%d",&a,&b)!=EOF){
        cnt=0;
        for(left=a;left>=b;left-=b-1){
            cnt+=b;
        }
        cnt+=left;
        printf("%d\n",cnt);
    }
}

379B - New Year Present：

输入钱包个数，和每个钱包需要放的硬币个数，指挥机器人放硬币，不能在同一个地方连续放，输出操作方法。

因为没有说是最少步数，只是限制在10^6以下，所以从左往右放直到放满所有。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<cstring>
const int maxn=310;
int a[maxn],cur,flag,sum,n;
void put_coin(){
    if(a[cur]&&!flag){
        flag=1,--a[cur],--sum;
        putchar('P');
    }
    else if(a[cur]){
        if(cur!=n-1){
            putchar('R');
            if(a[cur+1]){
                --a[cur+1],--sum;
                putchar('P');
            }
            --a[cur],--sum;
            putchar('L');
            putchar('P');
        }
        else{
            putchar('L');
            putchar('R');
            putchar('P');
            --a[cur],--sum;
        }
    }
    else if(cur!=n-1){
        flag=0,++cur;
        putchar('R');
    }
    else{
        flag=0,--cur;
        putchar('L');
    }
    if(sum) put_coin();
}
int main(){
    while(scanf("%d",&n)!=EOF){
        cur=flag=sum=0;
        memset(a,0,sizeof(a));
        for(int i=0;i<n;++i){
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        put_coin();
        putchar('\n');
    }
    return 0;
}

379C - New Year Ratings Change：

输入人数和每个人当前的rating，求变动后rating，要求不能有人rating相同。

一开始超时了好多次，Ac的这次764ms，也不是很理想。

排序以后为每个人的rating赋值，赋他当前的rating或者之前rating的最大值+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=300010;
struct rating{
    int res,num,rate;
    rating(int res=0,int num=0):res(res),num(num),rate(0){}
};
rating a[maxn];
bool cmp1(rating a,rating b){
    return a.res<b.res;
}
bool cmp2(rating a,rating b){
    return a.num<b.num;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++){
            int k;
            scanf("%d",&k);
            a[i]=rating(k,i);
        }
        sort(a,a+n,cmp1);
        int last=0;
        for(int i=0;i<n;i++){
            if(last>=a[i].res){
                a[i].rate=last;
                ++last;
            }
            else{
                a[i].rate=a[i].res;
                last=a[i].res+1;
            }
        }
        sort(a,a+n,cmp2);
        for(int i=0;i<n;i++){
            if(i) printf(" ");
            printf("%d",a[i].rate);
        }
        printf("\n");
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 Disqus：

做了前三道，感觉这次的前三道不是很难。

507A - Amr and Music：

学乐器，给出乐器数、天数和每个乐器需要的天数。求能学会哪几个。

结构体排序，输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct course{
    int a,b;
    course(int a=0,int b=0):a(a),b(b){}
    bool operator < (const course& x) const {
        return b<x.b;
    }
};
vector<course> a;
vector<int> b;
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;++i){
        int t;
        scanf("%d",&t);
        a.push_back(course(i,t));
    }
    sort(a.begin(),a.end());
    int p=0;
    while(1){
        if(a[p].b<=k){
            k-=a[p].b;
            b.push_back(a[p].a+1);
            ++p;
        }
        else break;
        if(p==n) break;
    }
    printf("%d\n",(int)b.size());
    for(int i=0;i<b.size();++i){
        if(i) printf(" ");
        printf("%d",b[i]);
    }
    return 0;
}

507B - Amr and Pins：

输入圆的半径初始位置、目标位置。求转移需要的最少的次数。

很容易想思路，一次最长能转移的距离等于直径，求位置之间的距离。然后除以直径向上取整。

1
2
3
4
5
6
7
8
9
#include<cstdio>
#include<cmath>
int main(){
    double r,x,y,ax,ay,l;
    scanf("%lf%lf%lf%lf%lf",&r,&x,&y,&ax,&ay);
    l=sqrt((x-ax)*(x-ax)+(y-ay)*(y-ay));
    printf("%d",(int)ceil(l/r/2));
    return 0;
}

507C - Guess Your Way Out!：

给出完全二叉树的深度，和目标叶子的编号。求在LRLRLR规则下，到目标叶片之前会经过多少叶子。

每走一层就判断是加整个子树再加一还是只加一，因为如果目标方向与当前左右方向不一致，必定要遍历另一棵子树，相同则只需走一个。

同时让n等于在当前子树中的编号。走到第h层就停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main(){
    int h,cur=0;
    long long n,k=0,x=1;
    cin>>h>>n;
    bool l=true;
    while(cur!=h){
        if(n>(x<<(h-cur-1))){
            n-=x<<(h-cur-1);
            if(l) k+=x<<(h-cur);
            else{++k;l=!l;}
        }
        else{
            if(l){++k;l=!l;}
            else k+=x<<(h-cur);
        }
        ++cur;
    }
    cout<<k;
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 Disqus：

终于把紫书刷完一百道了，按教主说的，反正首先这个诚意是有了，可以在机房分配座位了。

从2014.10.12开始112天了，总算结束了这个任务了。。

总感觉之前刷题过于追求题数，有的题其实还没理解就跟着书上生扯出来了；还有的就是水过去了，卡着时间过的。

以后准备先重看紫书前几章，把巩固知识基础。然后再来回顾自己之前做的题，看看别人的解题思路，拓展下思维，顺便把博客分类再按照知识点理一理。再后慢慢看紫书后几章 ，同时看看算法导论。

又是一个新的开始。

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

昨天整理了博客目录，看紫书第九章还没有做的题，就翻书看到了这道水题。

给出r*c的数表代表每个地点的高度，滑雪时高度要严格降低，求最长滑雪路径。

记忆化搜索最长路径，将每个点的最长路径存在数组g中，算完一个点比较维护最长路径就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int maxn=110;
const int x[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int h[maxn][maxn],g[maxn][maxn];
int dp(int a,int b){
    if(g[a][b]>=0) return g[a][b];//计算过的值直接使用。
    bool flag=0;
    for(int i=0;i<4;++i)
        if(h[a][b]>h[a+x[i][0]][b+x[i][1]]&&h[a+x[i][0]][b+x[i][1]]!=-1){
            g[a][b]=max(dp(a+x[i][0],b+x[i][1])+1,g[a][b]);//求当前点的最长滑雪路径。
            flag=1;
        }
    if(!flag) return 0;//无法滑倒其他点路径长为0。
    return g[a][b];
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(h,-1,sizeof(h));
        memset(g,-1,sizeof(g));
        char s[maxn];
        int r,c,best=0;
        scanf("%s%d%d",s,&r,&c);
        for(int i=1;i<=r;++i)
            for(int j=1;j<=c;++j)
                scanf("%d",&h[i][j]);
        for(int i=1;i<=r;++i)
            for(int j=1;j<=c;++j)
                best=max(dp(i,j),best);//边计算边维护最长路径，省去一次遍历。
        printf("%s: %d\n",s,best+1);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 Disqus：

一月最后一场，ACM-ICPC规则，没有pretest，没有hack，原本感觉会比上次简单点。。结果把自己打成绿名了。。。

一共就出了一道题。结束之后，B题改过了。

509A - Maximum in Table:

简单题，不说了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int maxn=11;
int a[maxn][maxn];
int main(){
    for(int i=0;i<maxn;++i){
        a[i][0]=1;
        if(i==0)
            for(int j=1;j<maxn;++j)
                a[i][j]=1;
        else
            for(int j=1;j<maxn;++j)
                a[i][j]=a[i-1][j]+a[i][j-1];
    }
    int n;
    while(cin>>n)
        cout<<a[n-1][n-1]<<endl;
    return 0;
}

509B - Painting Pebbles:

n堆鹅卵石，用k种颜色上色，任意两堆之间的任意颜色的鹅卵石数目差要求绝对值小于1。

思路很简单，当鹅卵石数目最大值减最小值大于数目k时，则无法涂色。最少堆的鹅卵石都用1涂色。然后其他堆涂相同数目的1，剩下的递增一个颜色涂一个。

一开始没注意到可以不用到所有颜色，后来删掉k>maxp之后，忘记修改输出，一直到比赛结束没看出来，我也是神了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=110;
int a[maxn];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
        memset(a,0,sizeof(a));
        scanf("%d",&a[0]);
        int maxp=a[0],minp=a[0];
        for(int i=1;i<n;++i){
            scanf("%d",&a[i]);
            maxp=max(maxp,a[i]);
            minp=min(minp,a[i]);
        }
        if(maxp-minp>k) printf("NO\n");
        else{
            printf("YES\n");
            for(int i=0;i<n;++i){
                bool p=1;
                for(int j=0;j<minp;++j){
                    if(p) p=0;
                    else printf(" ");
                    printf("1");
                }
                for(int j=0;j<a[i]-minp;++j){
                    if(p) p=0;
                    else printf(" ");
                    printf("%d",j+1);
                }
                printf("\n");
            }
        }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出背包大小n，两种宝物的体积s1、s2，两种宝物的价值v1、v2。求能装下的最大价值。

首先进行预处理，使n/s1的值尽可能小，满足O(n)的时间不超时。s2的宝物1与s1个宝物2体积相同，所以s=s1s2的体积只会拿宝物s1或s2中的一种（ 当s2v1>s1*v2时，只拿宝物1，反之亦然），这样就把n转化为n%s。然后为了使n/s1尽量小，当s1<s2时，交换s1、s2和v1、v2的值。

然后从零开始枚举需要拿的v1的个数，上限是n/s1，因为进行过预处理，所以保证不会超时。求出与处理之后的最大价值。

最后加上预处理拿到的价值x就是所求答案。

还要注意一点就是，s1、s2、v1、v2的值在int范围内，但相乘之后可能溢出，所以要使用long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int k,t=0;
    scanf("%d",&k);
    while(k--){
        long long n,s1,s2,v1,v2,x,best=0;
        scanf("%lld%lld%lld%lld%lld",&n,&s1,&v1,&s2,&v2);
        long long s=s1*s2,v=max(s2*v1,s1*v2);//求s=s1*s2时的最大价值v。
        x=n/s*v;//预处理获得的价值。
        n%=s;
        if(s1<s2) swap(s1,s2),swap(v1,v2);
        for(long long i=0;i<=n/s1;++i){
            long long cur=0,m=n;
            cur+=i*v1;
            m-=i*s1;
            cur+=m/s2*v2;
            best=max(best,cur);//枚举维护最大价值。
        }
        best+=x;//二者相加。
        printf("Case #%d: %lld\n",++t,best);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 Disqus：

清理电脑文件找到了圣诞时比赛的代码，就来写写。

比赛一共出了两道水题，第三道坑了好久，但总体来说还是可以的，第三道题虽然没有Ac，但是它确实对了，编译器差异。。

当时的题挂在学校OJ（http://219.218.128.149/JudgeOnline/）上了1628-1632。

Problem A：

一开始没考虑<0的情况，改了之后对了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
int main(){
    int n,m;
    while(cin>>n>>m){
        long long l=0,k;
        while(m--){
            cin>>k;
            l+=n-k;
        }
        cout<<(n-l>0?n-l:0)<<endl;
    }
    return 0;
}

Problem B：

简单几何。

1
2
3
4
5
6
7
8
9
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    double R,r;
    while(cin>>r>>R)
        printf("%.2lf %.2lf\n",(R-r)/r,(R+r)/r);
    return 0;
}

Problem C：

排列组合，求概率。不是很难，但是杭电貌似不认%Lf，比赛时没出。。

学校OJ上改成%lf过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
double n,m,x,y,p,p0;
double get_p(double i0){
    double k=1.0,i=i0;
    int l=i0;
    k*=pow(p,i0);
    if(i>n-i) i=n-i;
    for(int j=n;l>0;--j,--l)
        k*=j,k/=l;
    k*=pow(1.0-p,n-i0);
    return k;
}
int main(){
    while(cin>>n>>m>>x>>y>>p){
        p0=0.0;
        for(int i=0;i<=n;++i){
            if(i*x-(n-i)*y>m) p0+=get_p((double)i);
        }
        printf("%.2lf\n",p0);
    }
    return 0;
}

Problem D：

也是排列组合，求全排列。比赛时没去做，但那一阵子正好在看紫书第十章，于是后来就把这道题做了做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<vector>
using namespace std;
const int mod=1000000007;
const int maxn=1010;
vector<int> num;
long long modn[maxn]={1};
int search(int k){
    int top=(int)num.size()-1,bott=0,mid=0;
    while(top>=bott){
        mid=bott+(top-bott)/2;
        if(k==num[mid]) return mid;
        if(k>num[mid]) bott=mid+1;
        else top=mid-1;
    }
    return mid;
}
int main(){
    for(int i=1;i<maxn;i++)
        modn[i]=modn[i-1]*i%mod;
    int n,k;
    while(cin>>n){
        long long sum=1;
        for(int i=1;i<=n;i++)
            num.push_back(i);
        for(int i=1;i<=n;i++){
            cin>>k;
            int p=search(k);
            sum+=modn[n-i]*p%mod;
            sum%=mod;
            num.erase(num.begin()+p);
        }
        cout<<sum<<endl;
    }
    return 0;
}

Problem E：

当时写了超时，至今没有再去做。不过比赛结束后学长提示过用vector存路径之后暴搜。。

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 Disqus：

学长让去做CF的题，就把前几天的那场做了两道。

508A - Pasha and Pixels：

给出nm的像素，每次选一块，变成黑色，判断有没有出现22的黑像素，输出是第几次出现的。

思路很简单，点一个判断一次就好了。一开始用关了流同步的cin和cout，运行140ms，后来换scanf和printf，运行46ms，差了3倍多。原本以为关 掉同步之后差不了多少，没想到差这么多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<cstdio>
#include<cstring>
const int maxn=1010;
bool g[maxn][maxn];
bool judge(int a,int b){
    if(g[a+1][b]&&g[a][b+1]&&g[a+1][b+1]) return 1;
    if(g[a+1][b]&&g[a][b-1]&&g[a+1][b-1]) return 1;
    if(g[a-1][b]&&g[a][b+1]&&g[a-1][b+1]) return 1;
    if(g[a-1][b]&&g[a][b-1]&&g[a-1][b-1]) return 1;
    return 0;
}
int main(){
    int n,m,k,i;
    while(~scanf("%d%d%d",&n,&m,&k)){
        memset(g,0,sizeof(g));
        bool flag=1;
        for(i=0;i<k;++i){
            int a,b;
            scanf("%d%d",&a,&b);
            g[a][b]=1;
            if(flag&&judge(a,b)){
                printf("%d\n",i+1);
                flag=0;
            }
        }
        if(flag) printf("0\n");
    }
    return 0;
}

508B - Anton and currency you all know：

输入一个奇数，输出交换两位后最大的偶数，没有的话输出-1。

单次循环，寻找最大的位置，flag标记偶数位，flag2标记能否生成偶数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[100010];
int main(){
    while(~scanf("%s",s)){
        int n=(int)strlen(s);
        int p=0,flag=1,flag2=1;
        for(int i=0;i<n;++i){
            if(!(s[i]&1)){
                p=i,flag2=0;
                if(s[i]<s[n-1]){
                    swap(s[i],s[n-1]);
                    flag=0;
                    break;
                }
            }
        }
        if(flag) swap(s[p],s[n-1]);
        if(flag2) printf("-1\n");
        else printf("%s\n",s);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 Disqus：

打完比赛一直没写，今天有时间就来写写吧。
2014年最后一场CF，不分Div.1&2。感觉挺有纪念意义所以就去机房打了。
之前只是做过CF的题，第一次去机房熬夜打比赛，有点小激动。打的成绩还可以吧，就是没想到A题有个判断写错位置被hack之后来不及改了。B、C题都Ac了。而且还 涨分了，要是A题也Ac了估计能涨很多。
500A - New Year Transportation：

单向搜索。一定要注意结束时判断的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=30010;
int a[maxn];
int main(){
    int n,t,flag;
    while(scanf("%d%d",&n,&t)!=EOF){
        flag=0;
        memset(a,0,sizeof(a));
        for(int i=1;i<n;++i)
            scanf("%d",&a[i]);
        int cur=1;
        while(1){
            if(cur==t){
                printf("YES\n");
                flag=1;
                break;
            }
            if(cur>=n) break;
            cur=cur+a[cur];
        }
        if(!flag) printf("NO\n");
    }
    return 0;
}

500B - New Year Permutation：

dfs判连通之后，每个连通的集合内部排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=310;
int a[maxn],n,cnt;
bool g[maxn][maxn];
int vis[maxn];
vector<int> num[maxn][2];
struct pos{
    int a,b;
    pos(int a=0,int b=0):a(a),b(b){}
    bool operator < (const pos &x) const {
        return b<x.b;
    }
};
vector<pos> print;
void dfs(int u){
    for(int v=0;v<n;++v)
        if(vis[v]==-1&&g[u][v]){
            vis[v]=cnt;
            dfs(v);
        }
    return;
}
int main(){
    while(scanf("%d",&n)!=EOF){
        memset(a,0,sizeof(a));
        memset(g,0,sizeof(g));
        memset(vis,-1,sizeof(vis));
        for(int i=0;i<n;++i)
            scanf("%d",&a[i]);
        getchar();
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j)
                if(getchar()=='1') g[i][j]=g[j][i]=true;
            getchar();
        }
        cnt=0;
        for(int i=0;i<n;++i)
            if(vis[i]==-1){
                vis[i]=cnt;
                dfs(i);
                ++cnt;
            }
        for(int i=0;i<n;++i){
            num[vis[i]][0].push_back(a[i]);
            num[vis[i]][1].push_back(i);
        }
        for(int i=0;i<cnt;++i){
            sort(num[i][0].begin(),num[i][0].end());
            for(int j=0;j<num[i][0].size();++j)
                print.push_back(pos(num[i][0][j],num[i][1][j]));
            num[i][0].clear(),num[i][1].clear();
        }
        sort(print.begin(),print.end());
        for(int i=0;i<print.size();++i){
            if(i) printf(" ");
            printf("%d",print[i].a);
        }
        printf("\n");
        print.clear();
    }
    return 0;
}

500C - New Year Book Reading：

模拟，看书的顺序就是堆叠的次序，有了顺序模拟搬书求总重量就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=510;
const int maxm=1010;
int n,m;
int a[maxn],b[maxm];
bool read[maxn];
vector<int> best;
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(read,0,sizeof(read));
        for(int i=0;i<n;++i)
            scanf("%d",&a[i]);
        for(int i=0;i<m;++i){
            scanf("%d",&b[i]);
            if(!read[b[i]]){
                best.push_back(b[i]);
                read[b[i]]=true;
            }
        }
        int sum=0;
        for(int i=0;i<m;i++){
            int j=0;
            while(best[j]!=b[i])
                sum+=a[best[j++]-1];
            best.erase(best.begin()+j);
            best.insert(best.begin(),b[i]);
        }
        printf("%d\n",sum);
        best.clear();
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

昨天统计题数错联系锟神时提到了这道题，给他讲了我的思路，感觉博客写的太简略，正好百题之后准备重新理一遍博客，所以就先来写写这道题。

有v个城市，每个城市间都有道路连通，要检查e个道路，起点终点任选。输入v、e、检查每个道路的时间t。求最少总时间。

求最少总时间，感觉与UVa818切锁链中的环有些神似。

所给的e条道路是必经的，只需要找到最少的路使得给的路形成欧拉道路即可。

首先，对所有的道路判连通，假设形成了n个连通组，那么连起来就需要n-1条路。

然后，统计每组中度数为奇数的点，每一个奇数点都要构造另一条路使之度数为偶数，但是每一组仅需形成一条链而不是环，仅需形成欧拉道路而不是欧拉回路，所以统计个数要 减去链的端点2。

最后，求每组的和，减去一就是需要连成一个整体所用的道路数，加上e，总道路就求出来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=1010;
int v,e,t,cnt;
bool vis[maxn];
vector<int> g[maxn];
bool read(){
    cin>>v>>e>>t;
    if(!v&&!e&&!t) return false;
    for(int i=0;i<maxn;++i)
        g[i].clear();
    memset(vis,0,sizeof(vis));
    for(int i=0;i<e;++i){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    return true;
}
void dfs(int cur){
    if(vis[cur]) return;
    vis[cur]=true;
    cnt+=(int)g[cur].size()&1;//统计度数为奇数的点。
    for(int i=0;i<g[cur].size();++i)
        dfs(g[cur][i]);//DFS求连通。
    return;
}
int solve(){
    int ans=0;
    for(int i=1;i<=v;++i){
        if(!vis[i]&&!g[i].empty()){
            cnt=0;
            dfs(i);
            ans+=max(cnt,2);//每条道路至少需要2个端点，防止出现回路出错。
        }
    }
    return t*(max(ans/2-1,0)+e);//之前求得的和减去初始值任选可以减少的一次，再加上必经的e条道路。
}
int main(){
    ios::sync_with_stdio(false);
    int k=0;
    while(read())
        cout<<"Case "<<++k<<": "<<solve()<<endl;
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **