首页 > ACM题库 > HDU-杭电 > HDU 3390-Hotel-连通性问题-[解题报告]HOJ
2014
03-23

HDU 3390-Hotel-连通性问题-[解题报告]HOJ

Hotel

问题描述 :

A new hotel has been built in a city where the citizens believe that the number 13 brings bad luck. The hotel has n rooms which are numbered from 1 to n inclusive. One of the main properties of a room is its unlucky value which depends on the room number. Only number whose decimal forms contain the substring "13" will be considered to be unlucky numbers. For example, 13, 132, 1313, 9130 are unlucky numbers, but 1, 3, 31, 103, 123123 are not. The unlucky value of a room is the square of the room number if the room number is unlucky, and zero otherwise.
A hotel’s unlucky value equals the sum of the unlucky value of all its rooms. Help the manager to calculate the unlucky value of this hotel.

输入:

The first line contains an integer T (T<=100) indicating the number of test cases. T lines follows, each line contains an integer k (1<=k<=100) indicating that this hotel has 10^k (the k-th power of 10) rooms.

输出:

The first line contains an integer T (T<=100) indicating the number of test cases. T lines follows, each line contains an integer k (1<=k<=100) indicating that this hotel has 10^k (the k-th power of 10) rooms.

样例输入:

3
1
2
3

样例输出:

Case 1: 0
Case 2: 169
Case 3: 49582


题目描述:

There are some locations in a park, and some of them are connected by roads. The park manger needs to build some railways along the roads, and he would like to arrange tourist routes to each circuit. If a railway belongs to more than one tourist routes, there might be clash on it, and if a railway belongs to none tourist route, it doesn’t need to build.
Now we know the plan, and can you tell us how many railways are no need to build and how many railways where clash might happen.

Input:

The Input consists of multiple test cases. The first line of each test case contains two integers, n (0 < n <= 10000), m (0 <= m <= 100000), which are the number of locations and the number of the railways. The next m lines, each line contains two integers, u, v (0 <= u, v < n), which means the manger plans to build a railway on the road between u and v.
You can assume that there is no loop and no multiple edges.
The last test case is followed by two zeros on a single line, which means the end of the input.

Output:

Output the number of railways that are no need to build, and the number of railways where clash might happen. Please follow the format as the sample.

sample Input:

8 100 11 22 33 03 44 55 66 77 45 70 0

Output:

1 5

  由题目意思,图中的桥是无用的,那些双连通分量中的边多于节点多,就全是冲突边。

/*
 * @author ipqhjjybj
 * @date  20130622
 */
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>

#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <memory.h>
using namespace std;

#define inf 0x3f3f3f3f
#define MAXN 10007
#define MAXM 100010
#define clr(x,k) memset((x),(k),sizeof(x))
#define cpy(x,k) memcpy((x),(k),sizeof(x))
#define Base 10000

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
struct Edge{
    int st,ed;
    Edge(){};
    Edge(int a,int b){
        st = a,ed = b;
    }
};
int n,m;
vector<int> viMap[MAXN];
vector<Edge> block[MAXN];
stack<Edge> sEtack;
int low[MAXN],dfn[MAXN],vs[MAXN];
int tcc,sig;
int ans1,ans2;
void init(){
    int a,b;
    for(int i = 0;i <= n;i++) viMap[i].clear(),block[i].clear();
    for(int i = 0;i < m;i++){
        scanf("%d %d",&a,&b);
        viMap[a].push_back(b);
        viMap[b].push_back(a);
    }
    clr(low,0);
    clr(dfn,0);
    ans1 = ans2 = sig = tcc = 0;
    while(!sEtack.empty()) sEtack.pop();
}
int Tarjan(int cur,int &sig,int &tcc,int from){
    low[cur] = dfn[cur]=++sig;
    for(vector<int>::iterator it = viMap[cur].begin();it != viMap[cur].end();it++){
            if(!dfn[*it]){
                sEtack.push(Edge(cur,*it));
                Tarjan(*it,sig,tcc,cur);
                low[cur]=min(low[cur],low[*it]);
                if(dfn[cur]<=low[*it]){   // cur<*it 是一个桥, 当dfn[cur]==low[*it]时,说明这是个连通的回路
                    for(Edge temp;!sEtack.empty();){   //sEtack.empty() 栈不可能为空。理论上不会用到
                        temp = sEtack.top();
                        if(dfn[temp.st]<dfn[*it]) break; //说明temp.st在*it之前被遍历到,放进栈中的是那些与由*it查询到的边,即*it的子树(子树中的那些连通向量在之前已在搜索中被排除)
                                                // 也为了防止重复压栈
                        block[tcc].push_back(temp);sEtack.pop();
                    }
                    block[tcc++].push_back(Edge(cur,*it));
                    sEtack.pop();
                    if(dfn[cur]<low[*it]) ans1++; // (cur,*it) 是一个桥,桥是无用的,记录
                }
            }else if(*it != from && dfn[*it]<dfn[cur]){  //因为建立在深搜之上
                low[cur] = min(low[cur],dfn[*it]);
                sEtack.push(Edge(cur,*it));
            }
    }
    return 0;
}
int main(){
    //freopen("3394.in","r",stdin);
    while(scanf("%d %d",&n,&m)){
        if(!n&&!m)
            break;
        init();
        for(int i = 0;i < n;i++)
            if(!dfn[i])
                Tarjan(i,sig,tcc,-1);
        for(int i = 0;i < tcc;i++){
            clr(vs,0);
            int temp=0;
            for(int j = 0;j < block[i].size();j++){
                if(!vs[block[i][j].st]) vs[block[i][j].st]=1,temp++;
                if(!vs[block[i][j].ed]) vs[block[i][j].ed]=1,temp++;
            }
            if(temp<block[i].size()) ans2+=block[i].size();
        }
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}


参考:http://blog.csdn.net/hlyfalsy/article/details/9149657


,
  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  3. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。