几道线段树水题……hdu2795 ，3303
一些常用头文件及调试用代码（3.17）

表示首次做完一套比赛的题目，HDU2010省赛集训队选拔赛（校内赛），纪念下。

苗条 posted @ 2010年3月15日 19:22 in acm , 1840 阅读

 

杭电的集训队选拔赛，基本都是模拟题……

没什么算法之类的东西，做起来挺有感觉，俗称刷水题。

3343脑筋急转弯。。蚂蚁速度不为0就能走到。

3344看懂题意即可，水题，完全感觉不到这题原版的鸭梨。

 

?
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#pragma warning(disable:4786)
#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "iomanip"
#include "bitset"
#include "list"
#include "ctime"
using namespace std;
  
typedef __int64                 LL;
typedef unsigned __int64        ULL;
typedef unsigned char           uchar;
#define CC(m,what)              memset(m,what,sizeof(m))
#define FOR(i,a,b)              for( i = (a); i < (b); ++i )
#define FF(i,a)                 for( i = 0; i < (a); ++i )
#define FFD(i,a)                for( i = (a)-1; i >= 0; --i )
#define FORD(i,a,b)             for( i = (a)-1; i >= (b); --i )
#define LEFT(a)                 ((a)<<1)
#define RIGHT(a)                (((a)<<1)+1)
#define SZ(a)                   ((int)a.size())
#define PP(n,m,a)               puts("---");FF(i,n){FF(j,m)printf("%10d", a[i][j]);puts("");}
const double eps = 1e-11;
const double Pi = acos(-1.0);
const int    dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
 
int     map[110][110];
 
void hexie() {
    int n, m, i, j, k, ix, iy;
    char x;
    bool mark;
    scanf("%d%d%*c", &n, &m);
    FF (i, n) {
        FF (j, m) {
            scanf("%c%*c", &x);
            if ( x == '_' ) map[i][j] = -1;
            else map[i][j] = x-'0';
        }
    }
    FF (i, n) {
        FF (j, m) {
            if ( map[i][j] != -1 ) {
                printf( j == m-1 ? ".......\n" : "....... ");
                continue;
            }
            ix = i+dir[1][0];
            iy = j+dir[1][1];
            if ( ix < 0 || iy < 0 || ix >= n || iy >= m || map[ix][iy] == -1 ) {
                mark = false;
                printf("XXX");
            } else {
                k = 0;
                mark = true;
                while ( map[ix][iy] != -1 ) {
                    k += map[ix][iy];
                    ix += dir[1][0];
                    iy += dir[1][1];
                    if ( ix < 0 || iy < 0 || ix >= n || iy >= m || map[ix][iy] == -1 ) {
                        printf("%03d", k);
                        break;
                    }
                }
            }
            ix = i+dir[0][0];
            iy = j+dir[0][1];
            if ( ix < 0 || iy < 0 || ix >= n || iy >= m || map[ix][iy] == -1 ) {
                if ( !mark )
                    printf(j == m-1 ? "XXXX\n" : "XXXX ");
                else
                    printf(j == m-1 ? "\\XXX\n" : "\\XXX ");
            } else {
                k = 0;
                while ( map[ix][iy] != -1 ) {
                    k += map[ix][iy];
                    ix += dir[0][0];
                    iy += dir[0][1];
                    if ( ix < 0 || iy < 0 || ix >= n || iy >= m || map[ix][iy] ==-1 ) {
                        printf( j == m-1 ? "\\%03d\n" : "\\%03d ", k);
                        break;
                    }
                }
            }
        }
    }
}
 
int main() {
    int T, res, t;
    scanf("%d%*c", &T);
    while ( T-- ) {
        hexie();
        puts("");
    }
    return 0;
}

 

3345优先队列，如果要用队列的话要重复标记

 

?
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "iomanip"
#include "bitset"
#include "list"
#include "ctime"
using namespace std;
 
typedef unsigned char           uchar;
#define CC(m,what)              memset(m,what,sizeof(m))
#define FOR(i,a,b)              for( i = (a); i < (b); ++i )
#define FF(i,a)                 for( i = 0; i < (a); ++i )
#define FFD(i,a)                for( i = (a)-1; i >= 0; --i )
#define FORD(i,a,b)             for( i = (a)-1; i >= (b); --i )
#define LEFT(a)                 ((a)<<1)a
#define RIGHT(a)                (((a)<<1)+1)
#define SZ(a)                   ((int)a.size())
#define P(n,a)                  printf("---");FF(i,n){printf("%d:%4d\n", i,a[i]);printf("");}
#define PP(n,m,a)               printf("---");FF(i,n){FF(j,m)printf("%10d", a[i][j]);printf("");}
#define PPc(n,m,a)              printf("---");FF(i,n){FF(j,m)printf("%c", a[i][j]);printf("");}
const double eps = 1e-11;
const double Pi = acos(-1.0);
const int   intmax = 2147483647;
const int   dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
 
class node {
public:
    int x, y, value;
};
 
struct cmp {
    bool operator () (const node &a,const node &b){
        return a.value < b.value;
    }
};
 
int         n, m, sx, sy, v;
char        map[110][110];
bool        mark[110][110];
 
bool findE(node t) {
    int i;
    FF (i, 4 ) {
        node q = t;
        q.x += dir[i][0];
        q.y += dir[i][1];
        if ( q.x < 0 || q.y < 0 || q.x >= n || q.y >= m ) continue;
        if ( map[q.x][q.y] == 'E' ) return true;
    }
    return false;
}
 
void bfs() {
    priority_queue<node,vector<node>,cmp> Q;
    node p, q;
    int i, j, k;
    p.x = sx;
    p.y = sy;
    p.value = v;
    Q.push(p);
    mark[p.x][p.y] = true;
 
    while ( !Q.empty() ) {
        p = Q.top();
        Q.pop();
        FF (i, 4) {
            q = p;
            q.x += dir[i][0];
            q.y += dir[i][1];
            if ( q.x < 0 || q.y < 0 || q.x >= n || q.y >= m || mark[q.x][q.y] || map[q.x][q.y] == '#' || map[q.x][q.y] == 'E' ) continue;
            if ( map[q.x][q.y] == '.' || map[q.x][q.y] == 'P' ) {
                --q.value ;
            } else if ( map[q.x][q.y] == 'T' ) {
                q.value -= 2;
            } else if ( map[q.x][q.y] == 'R' ) {
                q.value -= 3;
            }
            if ( q.value < 0 ) continue;
            if ( findE(q) ) q.value = 0;
            if ( map[q.x][q.y] != 'P' )
                map[q.x][q.y] = '*';
            mark[q.x][q.y] = true;
            Q.push(q);
        }
    }
}
 
void hexie() {
    scanf("%d%d%d%*c", &n, &m, &v);
    int i, j, k;
    FF (i, n) gets(map[i]);
    FF (i, n) FF (j, m) {
        if ( map[i][j] == 'Y' ) {
            sx = i;
            sy = j;
        }
    }
    CC(mark,false);
    bfs();
    FF (i, n) puts(map[i]);putchar('\n');
}
 
int main() {
    int T;
    scanf("%d%*c", &T);
    while ( T-- ) {
        hexie();
    }
    return 0;
}

 

3346水题，表示看的时候还用了个大数模板，结果发现不用也能过，按题意来就好了。

3347模拟，表示用stl的map可能简化很多代码，以下是没用map的代码，头文件在上面几个代码里有。

 

?
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
class node {
public:
    char s[1000];
    int value;
};
 
node t[1000], temp;
int  res, n;
char s[1000];
 
void play() {
    int i, j, k;
    int v;
    res = 0;
    bool mark = false;
    for ( i = 0; ; i += strlen(s)+1 ) {
        sscanf(temp.s+i, "%s", s);
//        cout << s << endl;
        if ( s[0] == '=' ) continue;
        else if ( s[0] == '?' ) return;
        else if ( s[0] == '+' ) mark = false;
        else if ( strlen(s) == 1 && s[0] == '-' ) mark = true;
        else {
            if ( sscanf(s, "%d", &v) == 0 ) {
                FFD (j, n) {
                    if ( strcmp(t[j].s, s) == 0 ) {
                        res += mark ? -t[j].value : t[j].value;
                        break;
                    }
                }
            } else {
                res += mark ? -v : v;
            }
        }
    }
}
 
void hexie() {
    int i;
    scanf("%d%*c", &n);
    FF (i, n-1) {
        scanf("%s = %d%*c", temp.s, &temp.value);
        t[i] = temp;
    }
    gets(temp.s);
    play();
    printf("%d\n", res);
}
 
int main() {
    int T;
    scanf("%d%*c", &T);
    while ( T-- ) {
        hexie();
    }
    return 0;
}

 

3348 技巧贪心，表示描述不清楚贪心策略，看代码好点，没优化。

 

?
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
73
74
75
76
int        a[5], p, most, mini, t;
int        value[5] = {1, 5, 10, 50, 100};
 
bool getmax() {
    int temp;
    if ( a[0] >= t ) {
        most += t;
        if ( t >= 0 )
            return true;
        else
            return false;
    } else if ( a[0] + a[1]*5 >= t ) {
        temp = a[0];
        int k = (t-temp-1)/5+1;
        t -= k*5;
        most += k;
        return getmax();
    } else if ( a[0] + a[1]*5 + a[2]*10 >= t ) {
        temp = a[0] + a[1]*5;
        int k = (t-temp-1)/10+1;
        t -= 10*k;
        most += k;
        return getmax();
    } else if ( a[0] + a[1]*5 + a[2]*10 + a[3]*50 >= t ) {
        temp = a[0] + a[1]*5 + a[2]*10 ;
        int k = (t-temp-1)/50+1;
        t -= 50*k;
        most += k;
        return getmax();
    } else if ( a[0] + a[1]*5 + a[2]*10 + a[3]*50 + a[4]*100 >= t ) {
        temp = a[0] + a[1]*5 + a[2]*10 + a[3]*50;
        int k = (t-temp-1)/100+1;
        t -= 100*k;
        most += k;
        return getmax();
    }
    return false;
}
 
void getmin() {
    mini = 0;
    int t = p;
    int i;
    FFD (i, 5) {
        if ( t > a[i]*value[i] ) {
            t -= a[i]*value[i];
            mini += a[i];
        } else {
            mini += t/value[i];
            t = t%value[i];
        }
    }
}
 
void hexie() {
    int i, j, k;
    scanf("%d", &p);
    FF (i, 5) scanf("%d", a+i);
    most = mini = 0;
    t = p;
    if ( !getmax() ) {
        puts("-1 -1");
        return;
    }
    getmin();
    printf("%d %d\n", mini, most);
}
 
int main() {
    int T;
    scanf("%d%*c", &T);
    while ( T-- ) {
        hexie();
    }
    return 0;
}

 

3349数学题

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
    int t;
    double lo,a,b,sma,biao;
    cin>>t;
    while(t--) {
        cin>>lo>>a>>b;
        biao = sqrt(2.0)*lo;
        sma = a<b? a: b;
        double mid = sma*1.0/2;
        if(mid<=(biao*1.0/2)) printf("%.4lf\n",mid*mid);
        else if((mid>(biao*1.0)/2)&&(mid<biao*1.0))
            printf("%.4lf\n",lo*lo - (biao-mid)*(biao-mid));
        else printf("%.4lf\n",lo*lo);
         
    }
    return 0;
}

 

 3350按题意模拟

 

?
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
char    st[1010];
 
int dfs(int s, int e, int &num) {
    int i = s, t1, t2, res, j, l, r, k, temp;
    int mark;
    if ( s >= e ) return 0;
    res = l = r = 0;
    mark = 1;
    if ( st[s] == 'M' ) {
        k = 0;
        for ( i = s; i < e && mark; ++i ) {
            if ( st[i] == '(' ) ++k;
            else if ( k == 1 && st[i] == ',' ) {
                t1 = dfs(s+4, i, l);
                j = i;
                for ( i; i < e; ++i ) {
                    if ( st[i] == '(' ) ++k;
                    else if ( st[i] == ')' ) --k;
                    if ( k == 0 ) {
                        t2 = dfs(j+1, i, r);
                        if ( t1 > t2 ) {
                            res = t1;
                            num += l*2 + r;
                        } else {
                            res = t2;
                            num += r*2 + l;
                        }
                        mark = 0;
                        break;
                    }
                }
            }
            else if ( st[i] == ')' ) --k;
        }
    }
    temp = 0;
    for ( ; st[i] != 'M' && i < e; ++i ) {
        if ( st[i] == '+' ) {
            ++num;
            res += temp;
            temp = 0;
            continue;
        }
        else if ( st[i] >= '0' && st[i] <= '9' ) temp = temp*10+st[i]-'0';
    }
    res += temp;
    if ( i < e ) return res + dfs(i,e, num);
    return res;
}
 
int main() {
    int T, res, t;
    scanf("%d%*c", &T);
    while ( T-- ) {
        gets(st);
        res = 0;
        t = dfs(0, strlen(st), res);
        printf("%d %d\n", t, res);
    }
    return 0;
}

 

 

Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter