HDU 3713 Double Maze

代码写了很久才调通——！双迷宫搜索 不过状态数不大 只有6^4次 主要是地图的处理 以及居然要相邻两个地图都要求解一次 还有用到掩码也就是位运算来确定当前位置的四个方向是否有墙以及是否是洞…

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
123
124
125
126
127
128
129
130
131
132
133
134
135

#include <stdio.h>
#include <string.h>
#include <stack>
using std::stack;
int hash[6][6][6][6], dirx[] = {0,1,0,-1}, diry[] = {-1,0,1,0}, map1[6][6], map2[6][6], choice[4] = {1,0,2,3};
char dirc[] = "LDRU";
struct Point
{
    int x, y;
    void operator = (const Point & p)
    {
        x = p.x;
        y = p.y;
    }
    bool operator == (const Point & p)
    {
        return x == p.x && y == p.y;
    }
}pnt[2];
struct State
{
    Point a, b;
    int father, drt;
    bool operator == (const State &cmp)
    {
        return a == cmp.a && b == cmp.b;
    }
    bool valid()
    {
        return (map1[a.x][a.y] & (1<< 4)) != 0&& (map2[b.x][b.y] & (1<< 4)) != 0 && a.x >= 0 && a.y >= 0 && b.x >= 0 && b.y >=0 && a.x < 6 && a.y < 6 && b.x < 6 && b.y < 6;
    }
    State trans(int dir, int idx)
    {
        State ret;
        ret.drt = dir;
        ret.father = idx;
        if((map1[a.x][a.y] & (1 << dir)) == 0)
        {
            ret.a.x = a.x + dirx[dir];
            ret.a.y = a.y + diry[dir];
        }
        else
        {
            ret.a.x = a.x;
            ret.a.y = a.y;
        }
        if((map2[b.x][b.y] & (1 << dir)) == 0)
        {
            ret.b.x = b.x + dirx[dir];
            ret.b.y = b.y + diry[dir];
        }
        else
        {
            ret.b.x = b.x;
            ret.b.y = b.y;
        }
        return ret;
    }
    void set(Point p1, Point p2)
    {
        a = p1, b = p2;
    }
    State()
    {
        father = -1;
    }
}s1,s2,tmp,queue[1300],ns;
inline void makehash(State s)
{
    hash[s.a.x][s.a.y][s.b.x][s.b.y] = 1;
}
inline bool checkhash(State s)
{
    return hash[s.a.x][s.a.y][s.b.x][s.b.y] == 0;
}
void read(int map[6][6])
{
    for(int i = 0; i < 6; ++ i)
    for(int j = 0; j < 6; ++ j)
    {
        scanf("%d",map[i]+j);
        if((map[i][j] &(1 << 5)) != 0) pnt[0].x = i, pnt[0].y = j;
        if((map[i][j] & (1 << 6)) != 0) pnt[1].x = i, pnt[1].y = j;
    }
}
int main()
{
    int n, head, tail;
    scanf("%d", &n);
    read(map1);
    s1.a = pnt[0];
    s2.a = pnt[1];
    while(--n)
    {
        memset(hash, 0, sizeof(hash));
        stack<char> stk;
        read(map2);
        s1.b = pnt[0];
        s2.b = pnt[1];
        head = tail = 0;
        queue[tail++] = s1;
        makehash(s1);
        while(head < tail)
        {
            tmp = queue[head];
            if(tmp == s2)
            {
                for(int f = head; f > 0; f = queue[f].father)
                stk.push(dirc[queue[f].drt]);
                while(!stk.empty())
                {
                    putchar(stk.top());
                    stk.pop();
                }
                puts("");
                break;
            }
            for(int i = 0; i < 4; ++ i)
            {
                ns = tmp.trans(choice[i], head);
                if(ns.valid() && checkhash(ns))
                {
                    queue[tail++] = ns;
                    makehash(ns);
                }
            }
            ++ head;
        }
        if(head >= tail) puts("-1");
        memcpy(map1, map2, sizeof(map1));
        s1.a = s1.b;
        s2.a = s2.b;
    }
    return 0;
}
十一月 5th, 2011 in HDU_Number Theory | No Comments

2011 ACM/ICPC 北京现场赛J题 dfs剪枝

游戏规则是Same Gnome的变形 自身是个NP问题 所以只能暴力
为了能比较快的求解 所以规定了8连通以及至少要3块以上才能消去
一开始以为纯暴力 但是发现tle 所以想了一个自己认为比较弱的剪枝 统计每个数字出现的次数 消去一连通块之后 更新出现的该数字出现的次数 然后将score + 该连通块能得到的分数 + 剩下连通块能得到的最多的分数 与当前max值比较 如果大于max值则继续搜索 否则不拓展当前节点 加上这个优化之后居然2.+s就ac了 稍微修改了一些不必要的参数 下面的程序只用1.6s就能跑完数据 据说还有状态压缩的优化 表示不会了… 另外要注意memcpy的时候不要把形参当作sizeof的参数

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

#include <stdio.h>
#include <string.h>
int m, n, k, max, hash[7], mat[8][8], tmat[8][8], dir[3]= {-1,0,1};
struct Point
{
    int x, y;
    inline void set(int a, int b)
    {
        x = a, y = b;
    }
};
int evaluate()//估值函数
{
    int eval = 0;
    for(int i = 1; i <= k; ++ i)
        eval +=  hash[i] * hash[i];
    return eval;
}
void modify()//方块的左移和掉落
{
    int head;
    for(int i = 0; i < m; ++ i)
    {
        head = n - 1;
        while(head >= 0)
        {
            if(mat[head][i] == 0) break;
            else -- head;
        }
        if(head > 0)
        {
            for(int j = head - 1; j >= 0; -- j)
                if(mat[j][i] != 0)
                {
                    mat[head--][i] = mat[j][i];
                    mat[j][i] = 0;
                }
        }
    }
    bool zerocol;
    for(head = 0; head < m ; ++ head)
    {
        zerocol = true;
        for(int i = 0; i < n; ++ i)
            if(mat[i][head] != 0) zerocol = false;
        if(zerocol) break;
    }
    if(head < m - 1)
    {
        for(int i = head + 1; i  < m; ++ i)
        {
            zerocol = true;
            for(int j = 0; j < n; ++ j)
                if(mat[j][i] != 0) zerocol = false;
            if(!zerocol)
            {
                for(int j = 0; j < n; ++ j)
                {
                    mat[j][head] = mat[j][i];
                    mat[j][i] = 0;
                }
                ++ head;
            }
        }
    }
}
int travese(int x, int y, int mat[8][8], int val)//在mat上将和(x,y)点值相同且(x,y)连通的点标记成val
{
    Point queue[64], tmp;
    int head = 0, tail = 0, v = mat[x][y];
    queue[tail++].set(x,y);
    mat[x][y] = val;
    while(head < tail)
    {
        tmp = queue[head++];
        for(int i = 0; i < 3; ++ i)
            for(int j = 0; j < 3; ++ j)
            {
                if(mat[tmp.x + dir[i]][tmp.y + dir[j]] == v && tmp.x + dir[i] >= 0 && tmp.x + dir[i] < n && tmp.y + dir[j] >= 0 && tmp.y + dir[j] < m)
                {
                    mat[tmp.x + dir[i]][tmp.y + dir[j]] = val;
                    queue[tail++].set(tmp.x + dir[i] , tmp.y + dir[j]);
                }
            }
    }
    return tail;
}
int link(Point * p)
{
    memcpy(tmat, mat, sizeof(tmat));
    int cnt = 0;
    for(int i  = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
        {
            if(tmat[i][j] > 0)
            {
                if(travese(i,j,tmat,-1)>= 3)
                    p[cnt++].set(i,j);
            }
        }
    return cnt;
}
void dfs(int score)//暴力搜索
{
    Point pnt[21];
    int cnt = link(pnt);
    if(cnt == 0)
        max = max > score ? max : score;
    else
    {
        int ta[8][8];
        for(int i = 0; i < cnt; ++ i)
        {
            memcpy(ta, mat, sizeof(ta));
            int t = travese(pnt[i].x, pnt[i].y, mat, 0);
            hash[ta[pnt[i].x][pnt[i].y]]-= t;
            if(evaluate() + score + t * t > max)//估值函数
            {
                modify();
                dfs(score+ t * t);
            }
            hash[ta[pnt[i].x][pnt[i].y]]+= t;
            memcpy(mat, ta, sizeof(ta));
        }
    }
}
int main()
{
    while(scanf("%d%d%d", &n, &m , & k) != EOF)
    {
        memset(hash,0,sizeof(hash));
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < m; ++ j)
            {
                scanf("%d", mat[i]+j);
                ++hash[mat[i][j]];
            }
        max = 0;
        dfs(0);
        printf("%d\n",max);
    }
    return 0;
}
十月 24th, 2011 in Gain in ACM | No Comments

Gauss XOR Elimination Template

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

int gauss_XOR_Elimination(int aug_mat[MAXN][MAXN], int sol_vec[MAXN], int equ, int var)
{
    int row, col, max_row, tmp;
    for(row = col = 0; row < equ && col < var; ++ row , ++col)
    {
        max_row = row;
        for(int i = row + 1; i < equ; ++ i)
            max_row = mabs(aug_mat[max_row][col]) > mabs(aug_mat[i][col]) ? max_row : i;
        if(aug_mat[max_row][col] == 0) --row;
        else
        {
            for(int i = col; i <= var; ++ i)
            {
                tmp = aug_mat[max_row][i];
                aug_mat[max_row][i] = aug_mat[row][i];
                aug_mat[row][i] = tmp;
            }
            for(int i = row + 1; i < equ; ++ i)
                if(aug_mat[i][col])
                    for(int j = col; j < var + 1; ++ j)
                        aug_mat[i][j] ^= aug_mat[row][j];
        }
    }
    for(int i = row; i < equ; ++ i)
    if(aug_mat[i][var]) return -1;
    if(row < var) return var - row;
    else
    {
        for(int i = row - 1; i >= 0; -- i)
        {
            sol_vec[i] = aug_mat[i][var];
            for(int j = i - 1; j >= 0; -- j)
            if(aug_mat[j][i])
            aug_mat[j][var] ^= sol_vec[i];
        }
        return 0;
    }
}

经过弱数据检验 正在准备用强数据来检验

十月 19th, 2011 in ACM Template | No Comments

Java 大数分数模板[Testing]

略水的大分数模板

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

static class Fraction
    {
        static Fraction ZERO = new Fraction(BigInteger.ZERO, BigInteger.ONE);
        BigInteger numerator,denominator;
        Fraction()
        {
            numerator = BigInteger.ZERO;
            denominator = BigInteger.ONE;
        }
        void simplify()
        {
            BigInteger g = numerator.gcd(denominator);
            numerator = numerator.divide(g);
            denominator = denominator.divide(g);
            if(denominator.compareTo(BigInteger.ZERO) < 0)
            {
                denominator = denominator.multiply(new BigInteger("-1"));
                numerator = numerator.multiply(new BigInteger("-1"));
            }
        }
        Fraction(BigInteger numer)
        {
            numerator = numer;
            denominator = BigInteger.ONE;
        }
        Fraction(BigInteger numer, BigInteger deno)
        {
            if(deno.compareTo(BigInteger.ZERO) >= 0)
            {
                numerator = numer;
                denominator = deno;
            }
            else
            {
                numerator = numer.multiply(new BigInteger("-1"));
                denominator =  deno.multiply(new BigInteger("-1"));
            }
        }
        Fraction(Fraction copy)
        {
            numerator = new BigInteger(copy.numerator.toString());
            denominator = new BigInteger(copy.denominator.toString());
        }
        Fraction subtract(Fraction sub)
        {
            BigInteger g = denominator.gcd(sub.denominator);
            Fraction ret = new Fraction();
            ret.denominator = sub.denominator.divide(g).multiply(denominator);
            ret.numerator = numerator.multiply(sub.denominator.divide(g)).subtract(sub.numerator.multiply(denominator.divide(g)));
            simplify();
            return ret;
        }
        Fraction add(Fraction ad)
        {
            BigInteger g = denominator.gcd(ad.denominator);
            Fraction ret = new Fraction();
            ret.denominator = ad.denominator.divide(g).multiply(denominator);
            ret.numerator = numerator.multiply(ad.denominator.divide(g)).add(ad.numerator.multiply(denominator.divide(g)));
            simplify();
            return ret;
        }
        Fraction multiply(Fraction mult)
        {
            Fraction ret = new Fraction();
            ret.denominator = denominator.multiply(mult.denominator);
            ret.numerator = numerator.multiply(mult.numerator);
            ret.simplify();
            return ret;
        }
        Fraction divide(Fraction div)
        {
            Fraction ret = new Fraction();
            ret.denominator = denominator.multiply(div.numerator);
            ret.numerator = numerator.multiply(div.denominator);
            ret.simplify();
            return ret;
        }
        int compareTo(Fraction cmp)
        {
            return this.subtract(cmp).numerator.compareTo(BigInteger.ZERO);
        }
        Fraction abs()
        {
            Fraction ret = new Fraction(this);
            ret.numerator = ret.numerator.abs();
            return ret;
        }
        public String toString()
        {
            if(denominator.equals(BigInteger.ONE)) return numerator.toString();
            else return numerator.toString()+"/"+denominator.toString();
        }
    }
十月 1st, 2011 in Number Theory | No Comments

HDU 1299 Diophantus of Alexandria[EASY]

要求满足 1/x + 1/y = 1/n x,y,n都为正整数 的方程的方案数 这题自己没有想出来 上网参考别人的想法的
首先，可以知道x > n, y > n, y = n + k,带入式子,化简后得到 x = n*n/k + n,先不考虑x,y的大小关系，显然x为整数，因此有多少个x对应就有多少式子是符合题意的 但是要注意！ 会出现重复计数,因为x,y在式子中是等价的，因此绝大多数的式子被记录了两次 例如n = 4时 k 可以等于 1，2，4，8，16 得到对应的x是 20，12，8，6，5;对应的y为 5，6，8，12，20，发现除了 k=n的时候的式子 也就是 1/n = 1/2n + 1/2n的式子，其余的式子都被计数了2次，因此需要算出n*n的因子数加一除以2
接下来就是求n*n的因子数了，根据题目数据范围n×n可以达到10^18 因此直接算n*n的因子数素数表大小是装不下的，所以直接对n进行素因子分解，
n = p1^r1 * p2^r2 * p3 &r3 * …pi^ri n的所有因子数是(r1+1)*(r2+1)*…*(ri+1)
n*n的所有因子数就是(2×r1+1)*(2×r2+1)*…*(2×ri+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
47
48
49
50
51
52

#include <stdio.h>
#include <string.h>
const int PRIMERANGE = 40000;
int prime[PRIMERANGE + 1];
int getPrime()
{
    memset (prime, 0, sizeof (int) * (PRIMERANGE + 1));
    for (int i = 2; i <= PRIMERANGE; i++)
    {
        if (!prime[i]) prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0] && prime[j] <= PRIMERANGE / i; j++)
        {
            prime[prime[j]*i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    return prime[0];
}
int factor[100][3], facCnt;
int getFactors(int x)
{
    facCnt = 0;
    int tmp = x;
    for(int i = 1; prime[i] <= tmp / prime[i]; i++)
    {
        factor[facCnt][1] = 1, factor[facCnt][2] = 0;
        if(tmp % prime[i] == 0)
            factor[facCnt][0] = prime[i];
        while(tmp % prime[i] == 0)
            factor[facCnt][2]++, factor[facCnt][1] *= prime[i], tmp /= prime[i];
        if(factor[facCnt][1] > 1) facCnt++;
    }
    if(tmp != 1)
        factor[facCnt][0] = tmp, factor[facCnt][1] = tmp, factor[facCnt++][2] = 1;
    return facCnt;
}
int main()
{
    int t,n, ans;
    getPrime();
    scanf("%d", & t);
    for(int c = 1; c <= t; ++ c)
    {
        scanf("%d", & n);
        getFactors(n);
        ans = 1;
        for(int i = 0; i < facCnt; ++ i)
            ans *= (((factor[i][2])<< 1) + 1);
        printf("Scenario #%d:\n%d\n\n", c, (ans+1) >> 1);
    }
    return 0;
}
九月 30th, 2011 in HDU_Number Theory | No Comments

HDU 1211 RSA[EASY]

一个模拟题 而且数据范围貌似还水了 int居然就能过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <stdio.h>
int main()
{
    long long n,fn;
    int p, q, e, l, d, c, tmp, t, ans;
    while(scanf("%d%d%d%d",&p,&q,&e,&l) != EOF)
    {
        fn = (p - 1) * (q - 1);
        n = p * q;
        for(d = 1; (e*d) % fn != 1; ++d);
        while(l --)
        {
            scanf("%d", & c);
            for(tmp = c, t = d, ans = 1; t ; t >>= 1)
            {
                if(t & 1) ans = (ans * tmp) % n;
                tmp = (tmp * tmp) % n;
            }
            putchar(ans);
        }
        puts("");
    }
    return 0;
}
九月 29th, 2011 in HDU_Number Theory | No Comments

HDU 1153 Magic Bitstrings [Unknown]

没看懂题意..所以不算解决这个问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <stdio.h>
#include <string.h>
char ans[100001];
int main()
{
    long long n;
    while(scanf("%lld",&n),n)
    {
        if(n == 2) puts("Impossible");
        else
        {
            long long i;
            memset(ans,'1',(n+1)*sizeof(char));
            ans[n] = 0;
            for(i = 1 ; i < n ; i++) ans[i*i%n] = '0';
            puts(ans+1);
        }
    }
    return 0;
}
九月 29th, 2011 in HDU_Number Theory | No Comments

HDU 1121 Complete the Sequence[Medium] II

更快的解法，我们参考数列 f(n) = n*(n+1)*(2*n+1)/6 显然这个是平方和的公式
前4项迭代做差 得到
1 1 4 5 2
2 5 9 7
3 14 16
4 30
可以知道 f(5) = 55 = 30 + 16 + 7 + 2 发现这些数都是最外层的数 用f(5)继续往外扩展一层 得到f(6) = 55 + 25 +9 +2 = 91
1 1 4 5 2
2 5 9 7 2
3 14 16 9
4 30 25
5 55
这样就能很快的把数列推出来了～我这个代码还有优化的空间的～

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 <stdio.h>
int main()
{
    int T,s,c,newton[110][110],deg;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&s,&c);
        for(int i = 0; i < s; ++ i)
            scanf("%d",newton[0]+i);
        for(deg = 1; deg < s; ++ deg)
            for(int i = 0; i < s - deg; ++ i)
                newton[deg][i] = newton[deg-1][i+1] - newton[deg-1][i];
        for(int i = s; i < s + c; ++ i)
        {
            newton[0][i] = 0;
            for(int j = 0; j < i; ++ j)
            newton[0][i] += newton[i-1-j][j];
            for(int j = 1; j <= i; ++ j)
            newton[j][i-j] = newton[j-1][i-j+1] - newton[j-1][i-j];
            printf(i == s + c - 1?"%d\n":"%d ",newton[0][i]);
        }
    }
    return 0;
}
九月 28th, 2011 in HDU_Number Theory | No Comments

HDU 1121 Complete the Sequence[Medium]

题目意思就是给你个数列前s项 它是有规律的 即满足一个多项式的 让你求后面的c项 这个很像小时候奥数里面的找规律题；同时要求你求出的多项式的次数最小 也就是说 给你1 2 3 3项 很显然 你能通过插值 得到一个2阶的多项式 例如我可以通过hermite插值得到一个对于上面例子的多项式：(x-2)*(x-3)/2 – 2*(x-1）×(x-3) + 3 *(x-1) * (x-2) / 2 化简之后得到 x，一开始我还以为能得到一个二阶的多项式，但是经过zzc的提醒，我们可以得到这样的结论，对于一个n次多项式，如果给出大于(n+1)个点，经过插值之后得到的多项式仍是n次，简单的想，如果给一个n多项式曲线上的多于n+1个点的话，你得到的多项式仍然是n次的…
因此我一开始想用牛顿插值保证次数最小是多余的，而且zzc提出了一种更快的方法，暂时先贴上粗暴的java牛顿插值..

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

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        int T, s, c, deg;
        int newton[][] = new int[110][110];
        boolean allzero;
        Scanner scan = new Scanner(System.in);
        T = scan.nextInt();
    while(T-- > 0)
    {
        s = scan.nextInt();
        c = scan.nextInt();
        for(int i = 0; i < s; ++ i)
            newton[0][i] = scan.nextInt();
        for(deg = 1; deg < s; ++ deg)
        {
            allzero = true;
            for(int i = 0; i < s - deg; ++ i)
            {
                newton[deg][i] = newton[deg - 1][i + 1] - newton[deg - 1][i];
                if(newton[deg][i] != 0) allzero = false;
            }
            if(allzero) break;
        }
        for(int k = 1; k <= c; ++ k)
        {
            int n = s + k;
            BigInteger ans = BigInteger.valueOf(newton[0][0]);
            BigInteger tmp = BigInteger.ONE;
            BigInteger f = BigInteger.ONE;
            for(int i = 1; i < deg; ++ i)
            {
                f = f.multiply(BigInteger.valueOf(i));
                tmp = tmp.multiply(BigInteger.valueOf(n-i));
                ans = ans.add(tmp.multiply(BigInteger.valueOf(newton[i][0])).divide(f));
            }
            if(k == c) System.out.println(ans);
            else System.out.print(ans + " ");
        }
    }
    }
}
九月 28th, 2011 in HDU_Number Theory | No Comments

HDU 1104 Remainder[Easy]

题目大意  给你一个数n你能对n进行(+-*%) m 四种操作 这里的%要保证结果是正数 要求用最少的操作次数 达到与(n+1)%k同余 如果有方法，则输出操作的运算符(若有多种方案，则要输入权值小的方案，规定 + < - < * < % )，如果没有则输出0
题解 看到题目很容易想到宽搜，每个节点按照运算符权值从小到大拓展，当然为了避免重复节点，要hash一下啦，但是这里容易忽略一个问题，对于+-*三种操作 都满足 (a$b)%k = （(a%k)$(b%k))%k $表示运算符 但是对于%就不一样了 比如 (5%5)%6 != ((5%6)%(5%6))%6 因此需要用k*m作为modulo 每次mod k判断是否是target 第一次没有考虑到这点所以wa了

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

#include <stdio.h>
#include <string.h>
#define mod(x,y) (x % y + y) % y
const int MAX = 1000000;
int val[MAX + 20], father[MAX + 20], type[MAX + 20], s[MAX + 20], head, tail, target, step, n, k, m, t, p;
bool visted[MAX + 100], solved;
int main()
{
    char op[5] = "+-*%";
    while(scanf("%d%d%d", & n, & k, & m), n || k || m)
    {
        memset(visted, false,(k*m+1)*sizeof(bool));
        target = mod((n+1), k);
        head = tail = 0;
        solved = false;
        val[tail] = mod(n,(m*k));
        visted[mod(n,(k*m))] = true;
        father[tail] = -1;
        type[tail ++] = -1;
        while(head < tail && !solved)
        {
            t = val[head];
            for(int i = 0;i < 4; ++ i)
            {
                if(i == 0) p = t+m;
                else if(i == 1) p = t-m;
                else if(i == 2) p = t*m;
                else p = mod(t,m);
                p = mod(p,(k*m));
                if(!visted[p])
                {
                    visted[p] = true;
                    val[tail] = p;
                    father[tail] = head;
                    type[tail] = i;
                    if(p%k == target)
                    {
                        solved = true;
                        break;
                    }
                    tail ++;
                }
            }
            ++ head;
        }
        if(solved)
        {
            step = 0;
            for(int i = tail; father[i] >=0; i = father[i])
            s[step++] = type[i];
            printf("%d\n",step);
            for(int i = step - 1; i >= 0; -- i)
            putchar(op[s[i]]);
            puts("");
        }
        else puts("0");
    }
    return 0;
}
九月 25th, 2011 in HDU_Number Theory | No Comments
←Older