JS's Blog
0%

Posted on Edited on In ,

题目链接：
http://acm.hust.edu.cn/vjudge/contest/70017#problem/O
题意：
给定一个正整数N(N<4000000)(N<4000000)， 求G=∑i=1i<N∑j=i+1j≤Ngcd(i,j)G=\sum_{i=1}^{i<N}\sum_{j=i+1}^{j{\leq}N}gcd(i,j)的值
分析
已知f(N)=gcd(1,N)+gcd(2,N)+⋯+gcd(N−1,N)f(N)=gcd(1,N) + gcd (2,N)+{\cdots}+gcd(N-1,N)
即j=N,f(N)=∑i=1i<Ngcd(i,N)j = N , f(N) = \sum_{i=1}^{i<N}gcd(i,N)
则结果为f(2)+f(3)+f(4)+⋯+f(N)f(2) + f(3) + f(4) + {\cdots} + f(N)
即ans=∑i=2i≤Nf(i)ans = \sum_{i=2}^{i{\leq}N}f(i)
根据gcd性质，若gcd(k,n)=igcd(k,n)=i,则必有gcd(k/i,n/i)=1gcd(k/i,n/i)=1，即k/i与n/ik/i与n/i互质，
那么枚举ii的值，$ f(n)等于等于N/i$的欧拉函数值的和

代码：

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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#define MOD 1000000007
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
/*---------------------------head files----------------------------------*/
const int maxn = 4000009 ;

int phi[maxn], prime[maxn / 10];
long long s[maxn],f[maxn];
int tot ;
bool not_prime[maxn];

void init()
{
    int i, j;
    phi[1] = 1;
    for ( int i = 2; i <= 4000000 ; i ++ )
    {
        if ( !not_prime[i] )
        {
            phi[i] = i - 1;
            prime[++tot] = i;
        }
        {
            for ( j = 1; j <= tot && i * prime[j] <= 4000000; j++ )
            {
                not_prime[i * prime[j]] = 1;
                if ( i % prime[j] == 0 )
                {
                    phi[i * prime[j]] = phi[i] * prime[j];
                    break;
                }
                else
                {
                    phi[i * prime[j]] = phi[i] * ( prime[j] - 1 );
                }
            }
        }
        //for ( i = 1; i <= 4000000; i++ ) sum[i] = ( sum[i - 1] + phi[i] ) % mod;
    }
}
//预处理素数与欧拉函数值
int main()
{
    init();
    for (int i = 2 ; i < maxn ; i ++)
    {
        for (int j = 1 ; j * i <maxn ; j ++ )
        {
            f[j*i] += phi[i]*j;
        }
    }
    for (int i = 2 ; i < maxn ; i ++)
    {
        s[i] = s[i-1] + f[i];
    }
    int n;
    while (~scanf("%d",&n)&&n)
    {
        printf("%lld\n",s[n]);
    }
}

Posted on Edited on In ,

题目链接：
http://codeforces.com/problemset/problem/719/C

题目大意：
小明现在得知了自己的考试成绩是一个算上小数点共n位的小数，一共有t秒时间，每秒小明都可以对自己的小数点后的成绩进行一次四舍五入，问小明最大的成绩是多少

分析：
先找到小数点位置，因为四舍五入必须从小数点后进行，然后选择最靠近小数点的一位进位，如此t次，无法进位时退出，但此做法会超时，因为每次重新找要四舍五入的下标再进行进位会消耗很多时间，所以可以在进位的同时加上判断

  1. 进位后当前位>9，进位到下一位
  2. 进位后当前位>4，如果还有时间，直接在此处继续四舍五入
  3. 进位后当前位<=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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n , t ,length;
char str[200009];
char ans[200009];

bool change(int pos)
{
    int cpos = -1;
    for (int i = pos ; i < length ; i ++)
    {
        if (str[i]>='5')
        {
            cpos = i-1;
            str[i] = '\0';   //截断后面的小数部分
            length = i;
            break;
        }
    }
    int add = 1;
    if (cpos !=-1） //如果有可四舍五入的地方
    {
        for (int i = cpos ; i >= 0 ; --i)
        {
            if (str[i]=='.')
                continue;
            str[i] = str[i] + add ;
            if (str[i]>'9')    //大于9，直接进位
            {
                str[i] = '0';
                continue;
            }
            else if (str[i]>='5'&&t>0&&i>pos) //大于等于5且剩余进位次数不为0，且[当前位置在小数范围内]
            {
                --t;
                str[i] = '\0';
                length = i;
                continue;
            }
            else
            {
                add = 0;
                break;
            }
        }
        if (str[length-1]=='.')
        {
            str[length-1] = '\0';
            length -= 1;
        }
        if (add)
        {
            memcpy(ans+1,str,length);
            ans[0] = '1';
            length += 1;
            memcpy(str,ans,length);   //可能最高位在进位后>9，需要再前面再添1，由于这种情况只可能发生一次，所以两次memcpy也无妨
        }
        return true;
    }
    else
        return false;
}

int searchpoint()	//找到小数点所在位置
{
    for (int i = 0 ; i < length ; i ++)
        if (str[i]=='.')
            return i+1;

}
int main()
{
    scanf("%d%d",&n,&t);
    scanf("%s",str);
    length = strlen(str);
    int pos = searchpoint();
    while (--t>=0)
    {
        if (!change(pos))
            break;
    }
    cout<<str<<endl;
    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hust.edu.cn/vjudge/contest/70017#problem/V

题目大意：
读入一行数，求出所有数间最大的GCD值

分析：
根据GCD性质，N个数的GCD不大于N−1个数的GCDN个数的GCD不大于N-1个数的GCD，所以最大GCD一定出现于两个数间，由于只有至多100个数，100组样例，O（N2）O（N^2）暴力，但是注意读入，一开始用字符串流一直WA，看了题解发现用C语言的字符读入就过了，玄学AC

代码：

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 <cstdio>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#define MOD 1000000007
using namespace std;
typedef unsigned long long ull;
typedef long long ll;


/*---------------------------head files----------------------------------*/

bool num[150000];


void fd()
{
    for (int i = 2 ; i <= 100000 ; i ++)
    {
        if (!num[i])
        {
            for (int j = 2*i ; j <= 100000 ; j += i)
                num[j] = true;
        }
    }
    num[1]=true;
    num[2]=true;
}
inline ll max(ll a , ll b)
{
    return a>b? a: b;
}

ll gcd (ll a , ll b)
{
    return b==0? a : gcd(b,a%b);
}
int arr[6666];

int main()
{
    string str;
    ios::sync_with_stdio(false);
    ll n,a;
    char buf;
    scanf("%d",&n);
    while (getchar() != '\n');
    while (n--)
    {
        int cnt=0;
        ll maxx=0;
        while ((buf = getchar()) != '\n')
            if (buf >= '0' && buf <= '9') {
                ungetc(buf,stdin);
                scanf("%d",&arr[cnt ++]);
            }
        for (int i = 0 ; i < cnt ; i ++)
        {
            for (int j = i+1; j <cnt ; j ++)
            {
                if (i!=j)
                    maxx = max(maxx, gcd(arr[i],arr[j]));
            }
        }
        cout<<maxx<<endl;
    }
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5584

题目大意：
在一个无限大的棋盘上，若起点为(x,y)(x,y)，则人每次可以选择向上走或者向右走，长度为lcm(x,y)lcm(x,y)， 即走到(x+lcm(x,y),y)(x+lcm(x,y),y)或者(x,y+lcm(x,y))(x,y+lcm(x,y)),给定一个终点的坐标，求可以走到此处的合法起点有多少个

分析：

lcm(x,y)=x∗ygcd(x,y)lcm(x,y) = \frac{x*y}{gcd(x,y)}

由于$x = pgcd(x,y) , y = qgcd(x,y) $ 所以lcm(x,y)=p∗q∗gcd(x,y)lcm(x,y) = p*q*gcd(x,y)，每次加上一个gcd(x,y)gcd(x,y)后，两坐标的gcd值不改变

根据此性质，我们可以列出方程，若向右走，则有

{x+lcm(x,y)=ay=b\left\{ \begin{array}{c} x +lcm(x,y) = a \\ y= b \\ \end{array} \right.

代入可得

\begin{align*}x+x*b/gcd(x,y) =a \Longleftrightarrow x = \frac{a}{1+\frac{b}{gcd(x,y)}}\end{align*}

由于之前推得gcd(x,y)=gcd(a,b)gcd(x,y)=gcd(a,b)
已知落点为(a,b)(a,b)，可以推得两种之前一步的位置，当gcd(x,y)≠gcd(a,b)gcd(x,y)\not= gcd(a,b) 或者$x<1 或或y<1$时，即为退出条件，因此直接dfs即可

类似gcd，由于每一次xx或者yy都会减小为之前的11+bgcd(x,y)≤12\frac{1}{1+\frac{b}{gcd(x,y)}}\leq \frac{1}{2}，所以这至多是一个指数级的递归深度，况且实际上远小于log2nlog_2{n}，所以可以放心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
#include<bits/stdc++.h>

using namespace std;

int x,y,g;

int dfs(int x,int y)
{
    if (x<=0||y<=0||__gcd(x,y)!=g)
        return 0;
    int res = 1;
    int a = y/g+1 , b = x/g+1;
    if (x%a==0)
        res += dfs(x/a,y);
    if (y%b==0)
        res += dfs(x,y/b);
    return res;
}

int main()
{
    int T,t=1;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&x,&y);
        g = __gcd(x,y);
        printf("Case #%d: %d\n",t++,dfs(x,y));
    }
    return 0;
}

Posted on Edited on In ,

题目链接：
https://vjudge.net/contest/71746#problem/E

题目大意：
现有一个nk的矩阵A，以及一个kn的矩阵B，在模6域下，求得矩阵C = A*B，并对Cn∗nC^{n*n}的每一个元素求和，输出结果

分析：
直接暴力对C矩阵做快速幂，用类会爆空间，会数组写比较繁琐，且可能超时，所以可以得到以下式子

Cn∗n=(A∗B)n∗n=A∗(B∗A)∗(B∗A)⋯∗(B∗A)∗BC^{n*n} = (A*B)^{n*n}=A*(B*A)*(B*A)\cdots*(B*A)*B

即可写作

Cn∗n=A∗(B∗A)n∗n−1∗BC^{n*n} = A*(B*A)^{n*n-1}*B

而B∗AB*A是一个6*6的矩阵，对它求快速幂便很容易了

代码：
(因为调了好多遍，写的很丑，调试输出也很多，只要#define ONLINE即可不调试输出

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
//#define ONLINE
using namespace std;
const int N = 1200;
struct mart
{
   int n,m;
   int a[12][12];
};

int n,m,x,y,q;
mart now;



int a[N][10],b[10][N],c[10][N],d[N][N];
typedef long long ll;
const int mod = 1000000007;



mart unit;


mart multiply(mart A,mart B)
{
    mart C;
    C.n = A.n;
    C.m = B.m;
#ifndef ONLINE
    cout<<"A.n = "<<A.n<<"   B.m = "<<B.m<<endl;
#endif
    for (int i = 1 ; i <= m ; i ++)
    {
        for (int j = 1  ; j <= m ; j ++ )
        {
            C.a[i][j] = 0;
            for (int k = 1 ; k <= m ; k ++)
            {
                C.a[i][j] += A.a[i][k]*B.a[k][j];
                C.a[i][j] %= 6;
            }
        }
    }
    return C;
}

mart quickpow(mart p,int t)
{
    mart ans = unit;

    while (t)
    {
        if (t&1)
            ans = multiply(ans,p);
        p = multiply(p,p);
        t >>= 1;
    }
#ifndef ONLINE
    for (int i = 1 ; i <= m ; i ++)
    {
        for (int j = 1  ; j<= m ; j ++)
            cout<< ans.a[i][j]<<'\t';
        cout<<endl;
    }
    cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"<<endl;
#endif // ONLINE
    return ans;

}


void init()
{
    memset(now.a,0,sizeof(now.a));
    memset(c,0,sizeof(c));
    memset(d,0,sizeof(d));
    memset(unit.a,0,sizeof(unit.a));
    unit.m=m;
    unit.n=m;
    now.n = m;
    now.m = m;
    for (int i = 0 ; i < 12 ; i ++)
        unit.a[i][i] = 1;          //单位矩阵
    return;
}


void read() //读入
{
    for (int i = 1 ; i <= n ; i ++)
        for (int j = 1; j <= m ; j ++)
            scanf("%d",&a[i][j]);
    for (int i = 1 ; i <= m ; i ++)
        for (int j = 1; j <= n ; j ++)
            scanf("%d",&b[i][j]);
    return;
}

int main()
{
    init();
    while (~scanf("%d%d",&n,&m)&&(n||m)){
        if (n==0&&m==0)
            return 0;
        init();
        read();
                
                
        for (int i = 1 ; i <= m ; i ++)
        {
            for (int j = 1 ; j <= m ; j ++)
            {
                now.a[i][j] = 0;
                for (int k = 1 ; k <= n ; k ++)
                {
                    now.a[i][j] += b[i][k] * a[k][j];
                    now.a[i][j] %= 6;
                }
            }
        }
        
#ifndef ONLINE
        cout<<"---------------------------------------------------"<<endl;
        for (int i = 1 ; i <= m ; i ++)
        {
            for (int j = 1  ; j<= m ; j ++)
                cout<< now.a[i][j]<<'\t';
            cout<<endl;
        }
        cout<<"---------------------------------------------------"<<endl;
#endif // ONLINE

        mart Ans = quickpow(now,n*n-1);
        for (int i = 1 ; i <= m ; i ++)
        {
            for (int j = 1 ; j <= n ; j ++)
            {
                for (int k = 1 ; k <= m ; k ++)
                {
                    c[i][j] += Ans.a[i][k]*b[k][j];
                    c[i][j] %= 6;
                }
            }
        }
        
        for (int i = 1 ; i <= n ; i ++)
        {
            for (int j = 1 ; j <= n ; j ++)
            {
                for (int k = 1 ; k <= m ; k ++)
                {
                    d[i][j] += a[i][k] * c[k][j];
                    d[i][j] %= 6;
                }
            }
        }
        
        int ans = 0;
        for (int i = 1 ; i <= n ; i ++)
        {
            for (int j = 1 ; j <= n ; j ++)
            {
#ifndef ONLINE
                cout<< d[i][j]<<'\t';
#endif // ONLINE
                ans += d[i][j];
            }
#ifndef ONLINE
            cout<<endl;
#endif // ONLINE
        }
        printf("%d\n",ans);
    }

}

Posted on Edited on In ,

题目链接：
http://acm.hust.edu.cn/vjudge/contest/70017#problem/X

题目大意：
给出一个二元一次方程ax+by+c=0ax + by + c = 0，并给出两个范围[x1,x2]、[y1,y2][x1,x2]、[y1,y2]，求x,yx,y均在范围内的解的个数

分析：
1.a=0,b=0,c=0a=0,b=0,c=0时，所有解均成立，共(y2−y1)∗(x2−x1)(y2-y1)*(x2-x1)个解
2.a=0,b=0,c≠0a=0,b=0,c\neq0时，无解
3.a≠0,b=0a\neq0,b=0时，如果c不是a的倍数或c/ac/a不在范围内，显然无解，反之[x1,x2][x1,x2]所有数均可
4.a=0,b≠0a=0,b\neq0时同理
先将方程转化为 ax+by=−cax + by = -c 扩展欧几里得解方程的标准形式
即c取反，如果c此时为负，则需对整个式子取反
如果此时a或b为负，需要对x或y的取值范围反转，变为[−x2,−x1]或[−y2,−y1][-x2,-x1]或[-y2,-y1]
将方程系数a,b代入exgcd（我用的是一个5参数的exgcd模板，中间的参数最后得到gcd(a,b)gcd(a,b)）
然后比较c是否被gcd(a,b)整除，若不能，方程无解，若能x0=x∗c,y0=y∗cx0=x*c,y0=y*c
通解为$ x = x0 + kb ，， y = y0 - ka 那么 那么x1≤x0+kb≤x2x1\leq x0 + kb \leq x2$

−y2≤ka−y0≤−y1-y2 \leq ka - y0 \leq-y1

解得$$\frac{x1}{b} - x0 \leq k \leq \frac{x2}{b} - x0$$

y0−y2a≤k≤y0−y1ay0 - \frac{y2}{a} \leq k \leq y0 - \frac{y1}{a}

最后取并集即可 ， 但是要注意如3.5≤k≤7.53.5 \leq k \leq 7.5 显然 左边需要向上取整
右边需要向下取整 使用floor 和ceil函数即可完成

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include <algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;


void exgcd(ll a , ll b , ll &c , ll &x , ll &y)
{
    if (!b){x=1;y=0;c=a;}
    else{exgcd(b,a%b,c,y,x);y-=a/b*x;}
}

int main()
{
    ll a,b,c,x1,x2,y1,y2,t,x,y,d;
    while (~scanf("%I64d%I64d%I64d",&a,&b,&c))
    {
        ll ans = 0;
        scanf("%I64d%I64d",&x1,&x2);
        scanf("%I64d%I64d",&y1,&y2);
        c = -c;
        if (c<0)
        {
            a = - a ;
            b = - b ;
            c = - c ;
        }
        if (a<0)
        {
            a = - a;
            t = - x1;
            x1 = - x2;
            x2 = t;
        }
        if (b<0)
        {
            b= - b;
            t = - y1;
            y1 = -y2;
            y2 = t;
        }
        if (a==0&&b==0&&c!=0)
            ans = 0;
        else if (a==0&&b==0&&c==0)
            ans = (x2-x1+1)*(y2-y1+1);
        else if (a==0)
        {
            if (c%b||c/b<y1||c/b>y2)
                ans = 0;
            else
                ans = x2 - x1 + 1;
        }
        else if (b==0)
        {
            if (c%a||c/a<x1||c/a>x2)
                ans = 0;
            else
                ans = y2 - y1 + 1;
        }
        else
        {
            exgcd(a,b,d,x,y);
            //cout<<"now  d = "<<d<<endl;
            //cout<<"x =  "<<x<<"  y = "<<y<<endl;
            if (c%d)
                ans = 0;
            else
            {
                //cout<<"a  b  c  = "<<a<<" "<<b<<" "<<c<<endl;
                a /= d;
                b /= d;
                c /= d;
                x *= c;
                y *= c;

                ll l,r,lx,ly,rx,ry;
                lx = ceil((x1 *1.0- x)/b);
                ly = ceil((y- y2 *1.0)/a);
                l = max(lx,ly);
                rx = floor((x2 *1.0- x)/b);
                ry = floor((y - y1 *1.0)/a);
                r = min(rx,ry);
                if (r<l)
                    ans = 0;
                else
                    ans = r - l + 1;
            }
        }
        printf("%lld\n",ans);

    }
}

Posted on Edited on In ,

题目链接：
http://acm.hust.edu.cn/vjudge/contest/76505#problem/L
题目大意：
每轮有N个球，M个篮筐，P的概率投中，投每个篮筐的概率相同，K轮之后进球数的期望为多少？

分析：
每一轮中，投中求数的期望互相独立，同时一轮进球数为E(X)=NpE(X) = Np（二项分布期望），总进球数期望为E(X)=KNpE(X)=KNp，由于只是进球数且给定(M≥1M\geq1)，所以与篮筐数无关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
typedef long long ll;

int main()
{
    int n,m,k;
    double p;
    int T,ca=1;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d%lf",&n,&m,&k,&p);
        printf("Case %d: %.12f\n",ca++,n*1.0*k*p);
    }
}

Posted on Edited on In ,

题目链接：
http://acm.hust.edu.cn/vjudge/contest/70017#problem/T
题目大意：
读入两个01串，分别表示两个数X，Y
比如1101001表示 Fib = F0 + F3 + F5 + F6 = 1 + 5 + 13 + 21 = 40.
求这两个数的和，同样用01串表示结果 最后输出一个加法算式
如11101 1101
输出：
100101

  • 10001
    - - - - - - -
    1001000
    假设三个串长度分别为len1,len2,len3
    第一行：先输出len3+2-len1个空格，再输出第一个串
    第二行：先输出一个加号，再输出len3+1-len2个空格，再输出第二个串
    第三行：先输出两个空格，再输出len3个−-字符
    第四行：先输出两个空格，再输出第三个串

注意：
1.输入的串可能有前导零
2.可能有0 0 这样的极端数据
3.输入的两个串也需要处理，样例里没有给出，但是题意里有
比如输入111111应该输出10011001

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include <algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,ans,y;
ll Fb[100];
void init()
{
    Fb[0]=1;
    Fb[1]=2;
    for (int i = 2; i <= 44 ; i ++)
        Fb[i]=Fb[i-1]+Fb[i-2];
}

char s1[100],s2[100],s3[100];
int main()
{
    init();
    ll n1,n2;
    while (~scanf("%s%s",s1,s2))
    {
        n1=n2=0;
        int l1 = strlen(s1),l2=strlen(s2);
        for (int i = l1 -1  ; i >= 0 ; --i )
        {
            if (s1[i]=='1')
                n1 += Fb[l1-1-i];
        }
        for (int i = l2 -1  ; i >= 0 ; --i )
        {
            if (s2[i]=='1')
                n2 += Fb[l2-1-i];
        }
        ll ans = n1 + n2 ,tmp;
        {
            tmp = 0;
            int pos = lower_bound(Fb,Fb+45,n1)-Fb;
            if (Fb[pos]>n1) pos--;
            //printf("now pos = %d\n",pos);
            if (pos==-1)
            {
                s1[0]='0';
                pos= 0;
            }
            for (int i = pos ; i >=0 ; --i)
                if (tmp+Fb[i]<=n1)
                {
                    s1[pos-i]='1';
                    tmp += Fb[i];
                }
                else
                    s1[pos-i]='0';

            s1[pos+1]='\0';
            l1 = strlen(s1);
        }
        {
            tmp = 0;
            int pos = lower_bound(Fb,Fb+45,n2)-Fb;
            if (Fb[pos]>n2) pos--;
            //printf("now pos = %d\n",pos);
            if (pos==-1)
            {
                s2[0]='0';
                pos= 0;
            }
            for (int i = pos ; i >=0 ; --i)
                if (tmp+Fb[i]<=n2)
                {
                    s2[pos-i]='1';
                    tmp += Fb[i];
                }
                else
                    s2[pos-i]='0';

            s2[pos+1]='\0';
            l2 = strlen(s2);
        }
        tmp = 0;
        int pos = lower_bound(Fb,Fb+45,ans)-Fb;
        if (Fb[pos]>ans) pos--;
        //printf("now pos = %d\n",pos);
        if (pos==-1)
        {
            s3[0]='0';
            pos= 0;
        }
        for (int i = pos ; i >=0 ; --i)
            if (tmp+Fb[i]<=ans)
            {
                s3[pos-i]='1';
                tmp += Fb[i];
            }
            else
                s3[pos-i]='0';

        s3[pos+1]='\0';
        int l3 = strlen(s3);
        for (int i = 1 ; i <= l3+2 - l1 ; i ++)
	    putchar(' ');
        printf("%s\n",s1);
        putchar('+');
        for (int i = 1 ; i <=l3+1-l2;i++)
            putchar(' ');
        printf("%s\n",s2);
        printf("  ");
        for (int i = 1; i <= l3;i ++)
            putchar('-');
        putchar('\n');
        printf("  ");
        printf("%s\n\n",s3);
        }
    }
}

Posted on Edited on In ,

题目链接：
https://vjudge.net/contest/170743#problem/E

题目大意：
一个人要从x=0,x=1000,y=1000,y=0x=0,x=1000,y=1000,y=0在第一象限包围出的矩形的左侧走到右侧，途中会遇到很多圆，不能走入圆内，求出发点和到达点yy坐标最大的方案，若不可能输出IMPOSSIBLE

分析：
分析是否可行比较简单，从接触上边界的圆开始，dfs继续找所有与当前圆相交或者相切的圆，（内含理论上不必包含，但是这里包含并不影响正确性，而且代码逻辑更简单，所以没有特判），若发现接触下边界的圆，则说明不可能。

实际上这个过程用并查集也可以实现，设计一个up和down数组，表示该集合的最大坐标上界和下界，若两圆相交，则合并两圆的集合，最后fa[i]==ifa[i] == i 的即是根，遍历所有根查找是否上界超出1000且下界低于0，即可判定可行性。

比较麻烦的是找出yy坐标最大的解，实际上，画图可以发现，除了接触上界且接触左右界的圆集合，其他对答案都没有影响，可以通过"绕路"绕过，所以只要在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
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
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

typedef long long ll;


double sqr(double x)
{
    return x*x;
}

struct Point{
    double x,y;
    Point(){}
    Point (double _x,double _y)
    {
        x = _x;
        y = _y;
    }
    void read()
    {
        scanf("%lf%lf",&x,&y);
    }
    double distance(Point a)
    {
        return hypot(x-a.x,y-a.y);
    }


};

struct Circle{
    Point p;
    double r;
    Circle(){}
    Circle(double _x,double _y,double _r)
    {
        p = Point(_x,_y);
        r = _r;
    }
    void read()
    {
        p.read();
        scanf("%lf",&r);
    }
    bool cross(Circle a)
    {
        double dis = p.distance(a.p);
        return dis<=r+a.r;
    }

}c[1200];

int n;
int vis[1200];
double a1,a2;

bool dfs(int k)
{
    //printf("now dfs(%d)\n",k);
    //cross left
    if (c[k].p.x<=c[k].r)
    {
        double t = sqrt(sqr(c[k].r)-sqr(c[k].p.x));
        a1 = min(a1,c[k].p.y-t);
    }
    //cross right
    if (1000-c[k].p.x<=c[k].r)
    {
        double t = sqrt(sqr(c[k].r)-sqr(1000-c[k].p.x));
        a2 = min(a2,c[k].p.y-t);
    }
    //cross bottom
    if (c[k].p.y<=c[k].r)
        return false;
    bool res = true;
    for (int i = 1 ; i <= n ; i ++)
    {
        if (!vis[i]&&c[k].cross(c[i]))
        {
            vis[i] = 1;
            if (!dfs(i))
            {
                res = false;
                break;
            }
            
        }
    }
    return res;
}



int main()
{
    while (~scanf("%d",&n))
    {
        memset(vis,0,sizeof(vis));
        a1 = a2 = 1000.0;

        for (int i = 1 ; i <= n ; i ++)
        {
            c[i].read();
        }
        int f = 1;
        for (int i = 1 ; i <= n ; i ++)
        {
            if (!vis[i]&&c[i].p.y+c[i].r>=1000.0)
            {
                vis[i] = 1;
                if (!dfs(i))
                {

                    printf("IMPOSSIBLE\n");
                    f = 0;
                    break;
                }
            }
        }
        if (f)
            printf("%.2f %.2f %.2f %.2f\n",0.0,a1,1000.0,a2);

    }
    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1075

题目大意：
先给出一些单词的英文翻译，然后给出一篇文章，存在标点，若文章中单词存在翻译，则转换成英文单词，若没有则不变，然后输出翻译后的文章

分析：
建立一个译文数组，在字典树中插入单词时，即可在单词结点处添加对应译文在数组中的下标，然后遍历文章，遇到标点与空格切分单词，特判最后末尾不是标点的情况，在树中查找是否出现过当前单词即可，存在即将单词的译文输出，否则输出原文，然后将当前遍历的标点直接输出

代码：

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
144
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;

typedef long long ll;


struct Trie{
    Trie *next[26];
    int val;
    Trie(){
        val = -1;
        for (int i = 0 ; i < 26 ; i ++)
            next[i] = NULL;
    }
};

void addword(char *str,Trie* node,int i)
{
    if (node->next[str[0]-'a']==NULL)
    {
        node->next[str[0]-'a'] = new Trie;
        node = node->next[str[0]-'a'];
    }
    else
    {
        node = node->next[str[0]-'a'];
    }
    str++;
    if (*str)
        addword(str,node,i);
    else
    {
        node->val = i;
        return;
    }
}


int query(char *str ,Trie *node)
{
    if (node->next[*str-'a']==NULL)
        return -1;
    else
        node= node->next[*str-'a'];
    ++str;
    if (*str)
        return query(str,node);
    else
        return node->val;
}

char str[4000];
char temp[4000],tw[4000];
char word[1200000][20];


int main()
{
    int T,n,i;
    int cnt = 0;
    Trie* head = new Trie;
    scanf("%s",str);
    getchar();
    gets(str);
    while (strcmp(str,"END")!=0)
    {
        for (i = 0 ; ; i ++)
        {
            if (str[i]==' ')
            {
                word[cnt][i++] = 0;
                break;
            }
            else
                word[cnt][i] = str[i];
        }
        cnt++;
        addword(str+i,head,cnt-1);
        gets(str);
    }
    scanf("%s",str);
    getchar();
    gets(str);
    int lw;
    while (strcmp(str,"END")!=0)
    {
        cnt =0;
        int tp = 0;
        memset(temp,0,sizeof(temp));
        for (i = 0; str[i]; i ++)
        {
            if (str[i]>='a'&&str[i]<='z')
            {
                tw[cnt++] = str[i];
            }
            else
            {
                if (cnt!=0)
                {
                    tw[cnt] = 0;
                    int pos = query(tw,head);
                    if (pos!=-1)
                    {
                        strcat(temp,word[pos]);
                        tp += strlen(word[pos]);
                    }
                    else
                    {
                        strcat(temp,tw);
                        tp += strlen(tw);
                    }
                    cnt = 0;
                }
                temp[tp++] = str[i];
            }
        }
        if (cnt!=0)
        {
            tw[cnt] = 0;
            int pos = query(tw,head);
            if (pos!=-1)
            {
                strcat(temp,word[pos]);
                tp += strlen(word[pos]);
            }
            else
            {
                strcat(temp,tw);
                tp += strlen(tw);
            }
            cnt = 0;
        }
        temp[tp] = 0;
        printf("%s\n",temp);
        gets(str);
    }

    return 0;
}