Chengrui's Blog

0%

发表于 分类于 ， Disqus：

给出一个字符串，判断他最少划分成几个回文串。
枚举字符串终点，转移方程为 d [ i ] = m i n ( d [ i ] , d [ j − 1 ] + 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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
char s[maxn];
int d[maxn];
inline bool ok(int l,int r){
    while(l<=r){
        if(s[l]!=s[r]) return false;
        ++l,--r;
    }
    return true;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%s",s);
        int n=(int)strlen(s);
        for(int i=0;i<n;++i){
            d[i]=i+1;
            for(int j=0;j<=i;++j)
                if(ok(j,i)) d[i]=min(d[i],d[j-1]+1);
        }
        printf("%d\n",d[n-1]);
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出 n 种灯泡，同时给出他们的电压 v 、电源价格 k 、灯泡单价 c 和需求数量 l 。电压低的灯泡可以被电压高的代替，问最小花费。
按照电压从低到高排序，状态 d [ i ] 表示前 i 种的最小花费，转移方程为 d [ i ] = m i n ( d [ i ] , d [ j ] + ( s [ i ] − s [ j ] ) ∗ a [ i ] . c + a [ i ] . k ) ，其中 s [ i ] 表示前 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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int s[maxn],d[maxn];
struct node{
    int v,k,c,l;
    bool operator < (const node& x) const {
        return v<x.v;
    }
}a[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        memset(s,0,sizeof(s));
        for(int i=0;i<n;++i)
            scanf("%d%d%d%d",&a[i].v,&a[i].k,&a[i].c,&a[i].l);
        sort(a,a+n);
        s[0]=a[0].l;
        for(int i=1;i<n;++i)
            s[i]=s[i-1]+a[i].l;
        d[0]=0;
        for(int i=0;i<n;++i){
            d[i]=s[i]*a[i].c+a[i].k;
            for(int j=0;j<i;++j)
                d[i]=min(d[i],d[j]+(s[i]-s[j])*a[i].c+a[i].k);
        }
        printf("%d\n",d[n-1]);
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

最大相对差问题。维护区间最大值计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,cur,maxa,ans=-300010;
        scanf("%d%d",&n,&maxa);
        for(int i=1;i<n;++i){
            scanf("%d",&cur);
            ans=max(ans,maxa-cur);
            maxa=max(maxa,cur);
        }
        printf("%d\n",ans);
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

数论问题， n 个人围成环，每点 m 个就删掉点到的那个，问最后剩下人的编号。
递推公式为 f [ i ] = ( f [ i − 1 ] + m ) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
const int maxn=10010;
int f[maxn];
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)&&n){
        f[1]=0;
        for(int i=2;i<=n;++i) f[i]=(f[i-1]+m)%i;
        int ans=(1+f[n])%n;
        if(ans<=0) ans+=n;
        printf("%d\n",ans);
    }
    return 0;
}

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

发表于 分类于 Disqus：

都是些卡特兰数的简单应用，组合数学上有所介绍。
卡特兰数公式

C n = ( 2 n n ) − ( 2 n n + 1 ) = 1 n + 1 ( 2 n n ) for n ≥ 0

卡特兰数会用到大数，题目代码中的大数部分就不贴了，最后会贴个大数模板。
前几道题并没有什么难度，看组合数学就可以，最后一道用到了快速求组合数。
HDU 2067：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=13389
输出从 n ∗ n 正方形左下顶点走到右上顶点的不穿越副对角线的路径数目。
就是卡特兰数可以从上方的三角形走，也可以从下方的三角形走，所以是卡特兰数 C n ∗ 2 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
const int maxn=71;
long long c[maxn][maxn];
int main(){
    for(int i=0;i<maxn;++i) c[i][0]=1;
    for(int i=1;i<maxn;++i)
        for(int j=1;j<=i;++j)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    int n,t=0;
    while(cin>>n&&n!=-1)
        cout<<++t<<" "<<n<<" "<<(c[2*n][n]-c[2*n][n-1])*2<<endl;
    return 0;
}

HDU 1134：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=31502

1
2
3
4
5
6
7
8
BigNum h[110];
int main(){
    h[0]=1;
    for(int i=1;i<110;++i) h[i]=h[i-1]*(4*i-2)/(i+1);
    int n;
    while(cin>>n&&n!=-1) h[n].print();
    return 0;
}

HDU 1133：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18982

1
2
3
4
5
6
7
8
9
10
11
12
BigNum k[210];
int main(){
    k[0]=1;
    for(int i=1;i<210;++i) k[i]=k[i-1]*i;
    int n,m,t=0;
    while(cin>>m>>n&&(n||m)){
        cout<<"Test #"<<++t<<":\n";
        if(n>m) cout<<0<<endl;
        else (k[n+m]*(m-n+1)/(m+1)).print();
    }
    return 0;
}

HDU 1130：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=23152

1
2
3
4
5
6
7
8
BigNum h[110];
int main(){
    h[0]=1;
    for(int i=1;i<110;++i) h[i]=h[i-1]*(4*i-2)/(i+1);
    int n;
    while(cin>>n&&n!=-1) h[n].print();
    return 0;
}

HDU 1131：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=31500

1
2
3
4
5
6
7
8
BigNum h[110],k[110];
int main(){
    h[0]=k[0]=1;
    for(int i=1;i<110;++i) h[i]=h[i-1]*(4*i-2)/(i+1),k[i]=k[i-1]*i;
    int n;
    while(cin>>n&&n) (h[n]*k[n]).print();
    return 0;
}

HDU 1023：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18469

1
2
3
4
5
6
7
8
BigNum h[110];
int main(){
    h[0]=1;
    for(int i=1;i<110;++i) h[i]=h[i-1]*(4*i-2)/(i+1);
    int n;
    while(cin>>n&&n!=-1) h[n].print();
    return 0;
}

HDU 1267：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=38281

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
const int maxn=22;
long long a[maxn][maxn];
int main(){
    for(int i=0;i<maxn;++i) a[i][0]=1;
    for(int i=1;i<maxn;++i)
        for(int j=1;j<=i;++j)
            a[i][j]=a[i-1][j]+a[i][j-1];
    int n,m;
    while(cin>>n>>m) cout<<a[n][m]<<endl;
    return 0;
}

HDU 3398：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=14690
类似于卡特兰数，推出公式为

a n s = ( n + m n ) − ( n + m n + 1 ) , ( n , m ≤ 1000000 )

。
由于 n , m 很大不能使用一般的方法求出组合数，使用唯一分解，然后用快速幂求出所求组合数。

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
#include<iostream>
using namespace std;
const int maxn=1000010;
const int mod=20100501;
bool np[maxn*2];
int p[maxn*2],prime;
void pre(){
    int k=maxn*2;
    for(int i=2;i<k;i++){
        if(!np[i]) p[prime++]=i;
        for(int j=0;j<prime&&i*p[j]<k;j++){
            np[i*p[j]]=1;
            if(!(i%p[j])) break;
        }
    }
}
int cal(int p,int n){
    int ans=0;
    while(n) n/=p,ans+=n;
    return ans;
}
long long mod_exp(int a,int b){
    long long cur=1,tmp=a;
    while(b){
        if(b&1) cur=cur*tmp%mod;
        tmp=tmp*tmp%mod;
        b>>=1;
    }
    return cur;
}
int main(){
    pre();
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        long long ans=1;
        int k=n+1-m;
        for(int i=0;i<prime&&p[i]<=(n+m);++i){
            int cnt=0;
            while(k%p[i]==0) k/=p[i],++cnt;
            cnt+=cal(p[i],n+m)-cal(p[i],m)-cal(p[i],n+1);
            ans*=mod_exp(p[i],cnt),ans%=mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}

大数模板：

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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4

class BigNum
{
private:
    int a[500];    //可以控制大数的位数
    int len;       //大数长度
public:
    BigNum(){ len = 1;memset(a,0,sizeof(a)); }   //构造函数
    BigNum(const int);       //将一个int类型的变量转化为大数
    BigNum(const char*);     //将一个字符串类型的变量转化为大数
    BigNum(const BigNum &);  //拷贝构造函数
    BigNum &operator=(const BigNum &);   //重载赋值运算符，大数之间进行赋值运算

    friend istream& operator>>(istream&,  BigNum&);   //重载输入运算符
    friend ostream& operator<<(ostream&,  BigNum&);   //重载输出运算符

    BigNum operator+(const BigNum &) const;   //重载加法运算符，两个大数之间的相加运算
    BigNum operator-(const BigNum &) const;   //重载减法运算符，两个大数之间的相减运算
    BigNum operator*(const BigNum &) const;   //重载乘法运算符，两个大数之间的相乘运算
    BigNum operator/(const int   &) const;    //重载除法运算符，大数对一个整数进行相除运算

    BigNum operator^(const int  &) const;    //大数的n次方运算
    int    operator%(const int  &) const;    //大数对一个int类型的变量进行取模运算
    bool   operator>(const BigNum & T)const;   //大数和另一个大数的大小比较
    bool   operator>(const int & t)const;      //大数和一个int类型的变量的大小比较

    void print();       //输出大数
};
BigNum::BigNum(const int b)     //将一个int类型的变量转化为大数
{
    int c,d = b;
    len = 0;
    memset(a,0,sizeof(a));
    while(d > MAXN)
    {
        c = d - (d / (MAXN + 1)) * (MAXN + 1);
        d = d / (MAXN + 1);
        a[len++] = c;
    }
    a[len++] = d;
}
BigNum::BigNum(const char*s)     //将一个字符串类型的变量转化为大数
{
    int t,k,index,l,i;
    memset(a,0,sizeof(a));
    l=(int)strlen(s);
    len=l/DLEN;
    if(l%DLEN)
        len++;
    index=0;
    for(i=l-1;i>=0;i-=DLEN)
    {
        t=0;
        k=i-DLEN+1;
        if(k<0)
            k=0;
        for(int j=k;j<=i;j++)
            t=t*10+s[j]-'0';
        a[index++]=t;
    }
}
BigNum::BigNum(const BigNum & T) : len(T.len)  //拷贝构造函数
{
    int i;
    memset(a,0,sizeof(a));
    for(i = 0 ; i < len ; i++)
        a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n)   //重载赋值运算符，大数之间进行赋值运算
{
    int i;
    len = n.len;
    memset(a,0,sizeof(a));
    for(i = 0 ; i < len ; i++)
        a[i] = n.a[i];
    return *this;
}
istream& operator>>(istream & in,  BigNum & b)   //重载输入运算符
{
    char ch[MAXSIZE*4];
    int i = -1;
    in>>ch;
    int l=(int)strlen(ch);
    int count=0,sum=0;
    for(i=l-1;i>=0;)
    {
        sum = 0;
        int t=1;
        for(int j=0;j<4&&i>=0;j++,i--,t*=10)
        {
            sum+=(ch[i]-'0')*t;
        }
        b.a[count]=sum;
        count++;
    }
    b.len =count++;
    return in;

}
ostream& operator<<(ostream& out,  BigNum& b)   //重载输出运算符
{
    int i;
    cout << b.a[b.len - 1];
    for(i = b.len - 2 ; i >= 0 ; i--)
    {
        cout.width(DLEN);
        cout.fill('0');
        cout << b.a[i];
    }
    return out;
}

BigNum BigNum::operator+(const BigNum & T) const   //两个大数之间的相加运算
{
    BigNum t(*this);
    int i,big;      //位数
    big = T.len > len ? T.len : len;
    for(i = 0 ; i < big ; i++)
    {
        t.a[i] +=T.a[i];
        if(t.a[i] > MAXN)
        {
            t.a[i + 1]++;
            t.a[i] -=MAXN+1;
        }
    }
    if(t.a[big] != 0)
        t.len = big + 1;
    else
        t.len = big;
    return t;
}
BigNum BigNum::operator-(const BigNum & T) const   //两个大数之间的相减运算
{
    int i,j,big;
    bool flag;
    BigNum t1,t2;
    if(*this>T)
    {
        t1=*this;
        t2=T;
        flag=0;
    }
    else
    {
        t1=T;
        t2=*this;
        flag=1;
    }
    big=t1.len;
    for(i = 0 ; i < big ; i++)
    {
        if(t1.a[i] < t2.a[i])
        {
            j = i + 1;
            while(t1.a[j] == 0)
                j++;
            t1.a[j--]--;
            while(j > i)
                t1.a[j--] += MAXN;
            t1.a[i] += MAXN + 1 - t2.a[i];
        }
        else
            t1.a[i] -= t2.a[i];
    }
    t1.len = big;
    while(t1.a[len - 1] == 0 && t1.len > 1)
    {
        t1.len--;
        big--;
    }
    if(flag)
        t1.a[big-1]=0-t1.a[big-1];
    return t1;
}

BigNum BigNum::operator*(const BigNum & T) const   //两个大数之间的相乘运算
{
    BigNum ret;
    int i,j,up;
    int temp,temp1;
    for(i = 0 ; i < len ; i++)
    {
        up = 0;
        for(j = 0 ; j < T.len ; j++)
        {
            temp = a[i] * T.a[j] + ret.a[i + j] + up;
            if(temp > MAXN)
            {
                temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
                up = temp / (MAXN + 1);
                ret.a[i + j] = temp1;
            }
            else
            {
                up = 0;
                ret.a[i + j] = temp;
            }
        }
        if(up != 0)
            ret.a[i + j] = up;
    }
    ret.len = i + j;
    while(ret.a[ret.len - 1] == 0 && ret.len > 1)
        ret.len--;
    return ret;
}
BigNum BigNum::operator/(const int & b) const   //大数对一个整数进行相除运算
{
    BigNum ret;
    int i,down = 0;
    for(i = len - 1 ; i >= 0 ; i--)
    {
        ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
        down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
    }
    ret.len = len;
    while(ret.a[ret.len - 1] == 0 && ret.len > 1)
        ret.len--;
    return ret;
}
int BigNum::operator %(const int & b) const    //大数对一个int类型的变量进行取模运算
{
    int i,d=0;
    for (i = len-1; i>=0; i--)
    {
        d = ((d * (MAXN+1))% b + a[i])% b;
    }
    return d;
}
BigNum BigNum::operator^(const int & n) const    //大数的n次方运算
{
    BigNum t,ret(1);
    int i;
    if(n<0)
        exit(-1);
    if(n==0)
        return 1;
    if(n==1)
        return *this;
    int m=n;
    while(m>1)
    {
        t=*this;
        for( i=1;i<<1<=m;i<<=1)
        {
            t=t*t;
        }
        m-=i;
        ret=ret*t;
        if(m==1)
            ret=ret*(*this);
    }
    return ret;
}
bool BigNum::operator>(const BigNum & T) const   //大数和另一个大数的大小比较
{
    int ln;
    if(len > T.len)
        return true;
    else if(len == T.len)
    {
        ln = len - 1;
        while(a[ln] == T.a[ln] && ln >= 0)
            ln--;
        if(ln >= 0 && a[ln] > T.a[ln])
            return true;
        else
            return false;
    }
    else
        return false;
}
bool BigNum::operator >(const int & t) const    //大数和一个int类型的变量的大小比较
{
    BigNum b(t);
    return *this>b;
}

void BigNum::print()    //输出大数
{
    int i;
    cout << a[len - 1];
    for(i = len - 2 ; i >= 0 ; i--)
    {
        cout.width(DLEN);
        cout.fill('0');
        cout << a[i];
    }
    cout << endl;
}

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

发表于 分类于 Disqus：

HDU 1425：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=21604
排序输出前几个数，没什么难度。

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>
const int maxn=500010;
int a[maxn*2];
int Scan(){
    int res=0,ch,flag=0;
    if((ch=getchar())=='-') flag=1;
    else if(ch>='0'&&ch<='9') res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
    return flag?-res:res;
}
void Out(int a){
    if(a<0){putchar('-');a=-a;}
    if(a>=10) Out(a/10);
    putchar(a%10+'0');
}
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        memset(a,0,sizeof(a));
        getchar();
        while(n--){
            int k=Scan();
            ++a[maxn+k];
        }
        int pos=maxn*2-1;
        bool first=true;
        while(m){
            while(!a[pos]) --pos;
            if(first) first=false;
            else putchar(' ');
            Out(pos-maxn),--a[pos],--m;
        }
        putchar('\n');
    }
    return 0;
}

HDU 1800：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=21605
输入可能带有前导0的 n 个数，输出数量最多的数。数据范围很大，用Hash表做。然而直接用int读入用map做也可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
map<int,int> a;
int main(){
    int n;
    while(~scanf("%d",&n)){
        a.clear();
        while(n--){
            int k;
            scanf("%d",&k);
            if(!a.count(k)) a[k]=0;
            ++a[k];
        }
        int ans=0;
        for(map<int,int>::iterator it=a.begin();it!=a.end();++it)
            ans=max(ans,it->second);
        printf("%d\n",ans);
    }
    return 0;
}

HDU 1496：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18464
给出方程 a ∗ x 1 2 + b ∗ x 2 2 + c ∗ x 3 2 + d ∗ x 4 2 = 0 ，解的范围是[-100,100]。
方程中都是 x 2 ，所以在[0,100]内，进行折半搜索，求得的答案每个变量都有2种可能，所以最后乘16。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<cstring>
const int maxn=1000010;
int s[maxn*2];
int main(){
    int a,b,c,d;
    while(~scanf("%d%d%d%d",&a,&b,&c,&d)){
        if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0)){puts("0");continue;}
        memset(s,0,sizeof(s));
        int ans=0;
        for(int i=1;i<=100;++i)
            for(int j=1;j<=100;++j)
                ++s[a*i*i+b*j*j+maxn];
        for(int i=1;i<=100;++i)
            for(int j=1;j<=100;++j)
                ans+=s[maxn-(c*i*i+d*j*j)];
        printf("%d\n",ans<<4);
    }
    return 0;
}

HDU 1228：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=21606
给出英文等式求和，很早之前ACM协会练过这道题，没有难度。

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<iostream>
#include<sstream>
#include<string>
#include<map>
using namespace std;
map<string,int> a;
void pre(){
    a["one"]=1;
    a["two"]=2;
    a["three"]=3;
    a["four"]=4;
    a["five"]=5;
    a["six"]=6;
    a["seven"]=7;
    a["eight"]=8;
    a["nine"]=9;
    a["zero"]=0;
    return;
}
int main(){
    pre();
    string s0;
    while(getline(cin,s0)){
        stringstream ss(s0);
        string s;
        int aa=0,bb=0;
        while(ss>>s){
            if(!a.count(s)) break;
            aa*=10,aa+=a[s];
        }
        while(ss>>s){
            if(!a.count(s)) break;
            bb*=10,bb+=a[s];
        }
        if(aa+bb==0) break;
        cout<<aa+bb<<endl;
    }
    return 0;
}

HDU 1043：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17579
给出八数码初始状态，输出到标准状态的移动方法，多组输入。类似于紫书上的八数码问题，但是是多组输入，固定终止状态，所以进行BFS时要反向进行，然后对每次输入的 状态直接打印路径。
对于状态判重，紫书上的编码方式被称为康托展开，使用 n ! 对状态编码。

1
2
3
4
5
6
7
8
9
10
11
const int fact[]={1,1,2,6,24,120,720,5040,40320,362880};
int Cantor(int s[]){
    int sum=0;
    for(int i=0;i<9;i++){
        int cnt=0;
        for(int j=i+1;j<9;j++)
            if(s[i]>s[j]) cnt++;
        sum+=cnt*fact[8-i];
    }
    return sum;
}

再利用数组记录当前状态当下一个状态的走法和下个状态的编号。打印路径时遍历链表不需要进行BFS。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1000000;
const int fact[]={1,1,2,6,24,120,720,5040,40320,362880};
const int go[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const char dir[]="durl";
const int aim=46233;
bool vis[maxn];
int fa[maxn];
char h[maxn];
struct node{
    int s[9],z,id;
};
node st;
int Cantor(int s[]){
    int sum=0;
    for(int i=0;i<9;i++){
        int cnt=0;
        for(int j=i+1;j<9;j++)
            if(s[i]>s[j]) cnt++;
        sum+=cnt*fact[8-i];
    }
    return sum;
}
void bfs(){
    memset(fa,-1,sizeof(fa));
    memset(vis,0,sizeof(vis));
    node cur,next;
    for(int i=0;i<8;i++)cur.s[i]=i+1;
    cur.s[8]=0;
    cur.z=8;
    cur.id=aim;
    vis[aim]=true;
    queue<node> q;
    q.push(cur);
    while(!q.empty()){
        cur=q.front();q.pop();
        int x=cur.z/3;
        int y=cur.z%3;
        for(int i=0;i<4;i++){
            int tx=x+go[i][0],ty=y+go[i][1];
            if(tx<0||tx>2||ty<0||ty>2)continue;
            next=cur;
            next.z=tx*3+ty;
            next.s[cur.z]=next.s[next.z];
            next.s[next.z]=0;
            next.id=Cantor(next.s);
            if(!vis[next.id]){
                vis[next.id]=true;
                fa[next.id]=cur.id;
                h[next.id]=dir[i];
                q.push(next);
            }
        }
    }
    return;
}
int main(){
    char c;
    bfs();
    while(cin>>c){
        if(c=='x') st.s[0]=0,st.z=0;
        else st.s[0]=c-'0';
        for(int i=1;i<9;++i){
            cin>>c;
            if(c=='x') st.s[i]=0,st.z=i;
            else st.s[i]=c-'0';
        }
        int k=Cantor(st.s);
        if(vis[k]){
            while(k!=-1){
                putchar(h[k]);
                k=fa[k];
            }
            putchar('\n');
        }
        else puts("unsolvable");
    }
    return 0;
}

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

发表于 分类于 Disqus：

这次背包专题的题目大都是一些模板题，前四题套用模板就可以通过，最后一题题是二维费用背包，但也很基础。
HDU 2602：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17434
01背包。

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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int n,v,w[maxn],c[maxn];
int d[maxn];
void zeroone_pack(int *a, int c, int w)
{
    for(int i = v; i >= c; i--)
        a[i] = max(a[i], a[i - c] + w);
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        memset(d,0,sizeof(d));
        scanf("%d%d",&n,&v);
        for(int i=1;i<=n;++i) scanf("%d",&w[i]);
        for(int i=1;i<=n;++i) scanf("%d",&c[i]);
        for(int i=1;i<=n;++i) zeroone_pack(d,c[i],w[i]);
        printf("%d\n",d[v]);
    }
    return 0;
}

HDU 1114：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17679
完全背包。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10010;
const int inf=0x3f3f3f3f;
int n,v,p[maxn],c[maxn];
int d[maxn];
void complete_pack(int *a, int c, int w)
{
    for(int i = c; i <= v; i++)
        a[i] = min(a[i], a[i - c] + w);
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int w1,w2;scanf("%d%d",&w1,&w2);
        v=w2-w1;
        memset(d,0x3f,sizeof(d));
        d[0]=0;
        scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d%d",&p[i],&c[i]);
        for(int i=1;i<=n;++i) complete_pack(d,c[i],p[i]);
        if(d[v]==inf) printf("This is impossible.\n");
        else printf("The minimum amount of money in the piggy-bank is %d.\n",d[v]);
    }
    return 0;
}

HDU 2191：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=20468
多重背包。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int n,v,w[maxn],c[maxn],m[maxn];
int d[maxn];
void complete_pack(int *a, int c, int w)
{
    for(int i = c; i <= v; i++)
        a[i] = max(a[i], a[i - c] + w);
}
void zeroone_pack(int *a, int c, int w)
{
    for(int i = v; i >= c; i--)
        a[i] = max(a[i], a[i - c] + w);
}
void mutiple_pack(int *a, int c, int w, int m)
{
    if(c * m >= v){
        complete_pack(a, c, w);
        return;
    }
    int k = 1;
    while(k < m)
    {
        zeroone_pack(a, k * c, k * w);
        m = m - k;
        k = 2 * k;
    }
    zeroone_pack(a, c * m, w * m);
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        memset(d,0,sizeof(d));
        scanf("%d%d",&v,&n);
        for(int i=1;i<=n;++i) scanf("%d%d%d",&c[i],&w[i],&m[i]);
        for(int i=1;i<=n;++i) mutiple_pack(d,c[i],w[i],m[i]);
        printf("%d\n",d[v]);
    }
    return 0;
}

HDU 4508：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=37528
完全背包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,v,w[maxn],c[maxn];
int d[maxn];
void complete_pack(int *a, int c, int w)
{
    for(int i = c; i <= v; i++)
        a[i] = max(a[i], a[i - c] + w);
}
int main(){
    while(~scanf("%d",&n)){
        memset(d,0,sizeof(d));
        for(int i=1;i<=n;++i) scanf("%d%d",&w[i],&c[i]);
        scanf("%d",&v);
        for(int i=1;i<=n;++i) complete_pack(d,c[i],w[i]);
        printf("%d\n",d[v]);
    }
    return 0;
}

HDU 2159：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=20469
二维费用背包，费用分别为杀的怪的数量和疲劳值，状态转移方程为 d [ j ] [ l ] = m a x ( d [ j ] [ l ] , d [ j − 1 ] [ l − c [ i ] ] + v [ i ] ) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
int n,m,k,s,v[maxn],c[maxn];
int d[maxn][maxn];
int main(){
    while(~scanf("%d%d%d%d",&n,&m,&k,&s)){
        memset(d,0,sizeof(d));
        for(int i=1;i<=k;++i) scanf("%d%d",&v[i],&c[i]);
        for(int i=1;i<=k;++i)
            for(int j=1;j<=s;++j)
                for(int l=c[i];l<=m;l++)
                    d[j][l]=max(d[j][l],d[j-1][l-c[i]]+v[i]);
        int pos=0;
        while(pos<=m&&d[s][pos]<n) ++pos;
        printf("%d\n",d[s][pos]<n?-1:m-pos);
    }
    return 0;
}

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

发表于 分类于 Disqus：

HDU 1846：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=11241
给出 n 个物品，两个人轮流取，每次取1～ m 个，不能取的人负，输出胜利者。
巴什博弈，当 n % ( m + 1 ) = 0 时后手胜利，否则先手胜利。

1
2
3
4
5
6
7
8
9
#include<cstdio>
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int n,m;scanf("%d%d",&n,&m);
        puts(n%(m+1)?"first":"second");
    }
    return 0;
}

HDU 1847：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=20980
给出 n 个物品，两个人轮流取，每次只能取2的倍数个。
巴什博弈，第一个先手的人只要能构造出3的倍数就可以必胜。对三取余判断输出结果。

1
2
3
4
5
6
7
#include<cstdio>
int main(){
    int n;
    while(~scanf("%d",&n))
        puts(n%3?"Kiki":"Cici");
    return 0;
}

HDU 1848：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=22378
给出三堆牌，每次去的个数只能是菲波那契数，问谁能赢。
看了解题报告才知道这是运用SG函数的尼姆博弈，去现学的，对每个输入的值求SG函数值，然后进行异或求解。

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
#include<cstdio>
#include<cstring>
const int maxn=1010;
int f[20]={1,1},sg[maxn];
bool h[maxn][20];
void pre(){
    for(int i=2;i<20;++i) f[i]=f[i-1]+f[i-2];
    memset(sg,-1,sizeof(sg));
    return;
}
int Sg(int n){
    int& k=sg[n];
    if(k!=-1) return k;
    for(int i=1;i<20;++i)
        if(n-f[i]>=0) h[n][Sg(n-f[i])]=true;
    k=0;
    while(h[n][k]) ++k;
    return k;
}
int main(){
    pre();
    int n,m,p;
    while(~scanf("%d%d%d",&n,&m,&p)&&!(!n&&!m&&!p)) 
        puts(Sg(n)^Sg(m)^Sg(p)?"Fibo":"Nacci");
    return 0;
}

HDU 1849：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=10636
可以抽象成给出 n 堆牌，每次可以取一张或者全取走，问谁胜。
比上一题简单的尼姆博弈，对输入的数进行异或输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<cstdio>
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        int ans=0,k;
        while(n--){
            scanf("%d",&k);
            ans^=k;
        }
        puts(ans?"Rabbit Win!":"Grass Win!");
    }
    return 0;
}

HDU 1850：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=22381
给出多堆牌，每次可以任选一堆取走任意数量，问先手第一步有多少必胜取法。
首先异或判断是否存在必胜策略求的异或后的值为 a n s 。判断当前堆中有没有足够的牌，使得取走之后 a n s ＝ 0 ，若有则方案数加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<cstdio>
int a[110],n;
int main(){
    while(~scanf("%d",&n)&&n){
        int ans=0,cnt=0;
        for(int i=0;i<n;++i) scanf("%d",&a[i]),ans^=a[i];
        if(!ans){puts("0");continue;}
        for(int i=0;i<n;++i)
            if(a[i]>(ans^a[i])) ++cnt;
        printf("%d\n",cnt);
    }
    return 0;
}

HDU 2149：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=10637
输入土地成本 m 和每次加价最大值 n ，当出价高于或等于成本时得到该土地，输出先手必胜策略。
巴什博弈，首先判断是否存在必胜策略，然后枚举输出可行出价。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        if(n%(m+1)==0){puts("none");continue;}
        bool first=true;
        if(n<m){
            for(int i=n;i<=m;++i){
                printf("%d%c",i,i!=m?' ':'\n');
            }
            continue;
        }
        for(int i=1;i<=m;++i){
            if((n-i)%(m+1)==0){
                if(first) first=false;
                else printf(" ");
                printf("%d",i);
            }
        }
        puts("");
    }
    return 0;
}

HDU 2188：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=26664
巴什博弈，和第一道题一样。

1
2
3
4
5
6
7
8
9
#include<cstdio>
int main(){
    int t,n,m;scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        puts(n%(m+1)?"Grass":"Rabbit");
    }
    return 0;
}

HDU 2147：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=26673
给出目标点的坐标，从原点出发，每次可以向左、向下或者向左下，问谁能赢。
当横纵坐标存在偶数时，先手赢。

1
2
3
4
5
6
7
#include<cstdio>
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)&&!(!n&&!m))
        puts(n&1&&m&1?"What a pity!":"Wonderful!");
    return 0;
}

HDU 1079：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=11243
改变月份或移到后一天会改变月份与日期和的奇偶性，除了两个特殊日期9月30日和11月30日。对特殊日期进行特判，其他情况只要判断奇偶性就可以知道。
这题还可以用SG函数做。

1
2
3
4
5
6
7
#include<cstdio>
int main(){
    int t,y,m,d;scanf("%d",&t);
    while(t--&&~scanf("%d%d%d",&y,&m,&d))
        puts((m+d)%2==0||((m==9||m==11)&&d==30)?"YES":"NO");
    return 0;
}

HDU 1517：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=13014
看了题解才会的，类似于巴什博弈，每一段必胜区间都紧跟着一段必败区间，必胜区间对 n 不断除18之后的余数小于9。
这道题也可以用SG函数做。

1
2
3
4
5
6
7
8
9
#include<cstdio>
int main(){
    double n;
    while(~scanf("%lf",&n)){
        while(n>18) n/=18;
        puts(n>9?"Ollie wins.":"Stan wins.");
    }
    return 0;
}

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

发表于 分类于 Disqus：

HDU 2199：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=20576
输入一个 y ，求使得 8 ∗ x 4 + 7 ∗ x 3 + 2 ∗ x 2 + 3 ∗ x + 6 ＝ y 的 x 的值， 0 ≤ x ≤ 100 。二分查找答案。

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<cmath>
using namespace std;
const double EPS=1e-5;
inline double f(double x){
    return 8*x*x*x*x+7*x*x*x+2*x*x+3*x+6;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        double k;scanf("%lf",&k);
        if(f(0)>k||f(100)<k){
            printf("No solution!\n");
            continue;
        }
        double l=0,r=100,m=50;
        while(fabs(f(m)-k)>EPS){
            if(f(m)>k) r=m;
            else l=m;
            m=(l+r)/2;
        }
        printf("%.4f\n",m);
    }
    return 0;
}

HDU 2899：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=20577
给出函数 F ( x ) = 6 ∗ x 7 + 8 ∗ x 6 + 7 ∗ x 3 + 5 ∗ x 2 − y ∗ x ，输入 y ，求函数最小值。
首先对该函数求导，然后二分查找使导函数为0的值 x 0 ，输出 F ( x 0 ) 。

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<cmath>
using namespace std;
const double EPS=1e-6;
double y;
inline double f(double x){
    return 6*x*x*x*x*x*x*x+8*x*x*x*x*x*x+7*x*x*x+5*x*x-y*x;
}
inline double f2(double x){
    return 42*x*x*x*x*x*x+48*x*x*x*x*x+21*x*x+10*x-y;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        scanf("%lf",&y);
        double l=0,r=100,m=50;
        while(fabs(f2(m))>EPS){
            if(f2(m)>0) r=m;
            else l=m;
            m=(l+r)/2;
        }
        printf("%.4lf\n",f(m));
    }
    return 0;
}

HDU 1969：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=23123
给出 n 、 m ，有 n 个蛋糕， m + 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
#include<cstdio>
#include<cmath>
using namespace std;
const double EPS=1e-6;
const double PI=acos(-1);
const int maxn=10010;
int n,f;
double a[maxn];
inline double c(double r){
    return PI*r*r;
}
bool ok(double x){
    int sum=0;
    for(int i=0;i<n;++i){
        sum+=floor(a[i]/x);
    }
    return sum>=f+1;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){scanf("%d%d",&n,&f);
        double sum=0;
        for(int i=0;i<n;++i){
            scanf("%lf",&a[i]);
            a[i]=c(a[i]);
            sum+=a[i];
        }
        double l=0,r=sum,m=(l+r)/2;
        while(r-l>EPS){
            if(ok(m)) l=m;
            else r=m;
            m=(l+r)/2;
        }
        printf("%.4f\n",m);
    }
    return 0;
}

HDU 1905：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=40853
输入 p 、 a ，如果 p 不为素数且 a p % p = = a 输出yes，否则输出no。
2 < p ≤ 1000000000 ， 1 < a < p
首先打出0~ p ‾ ‾ √ 的素数表，然后对每个 p 进行素性测试，再用快速幂求 a p % p 判断输出。

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<cmath>
using namespace std;
typedef long long LL;
const double EPS=1e-6;
const double PI=acos(-1);
const int maxn=100010;
int isp[maxn],pre_p;
bool np[maxn]={true,true};
void pre(){
    for(int i=2;i<maxn;++i){
        if(!np[i]) isp[pre_p++]=i;
        for(int j=0;j<pre_p&&i*isp[j]<maxn;++j){
            np[i*isp[j]]=true;
            if(!(i%isp[j])) break;
        }
    }
    return;
}
bool isprime(LL n){
    double k=sqrt(n);
    for(int i=0;isp[i]<=k;++i)
        if(n%isp[i]==0) return false;
    return true;
}
LL modexp(LL a,LL b,LL mod){
    LL cur=1,tmp=a;
    while(b){
        if(b&1) cur=cur*tmp%mod;
        tmp=tmp*tmp%mod;
        b>>=1;
    }
    return cur;
}
int main(){
    pre();
    LL n,a;
    while(~scanf("%lld%lld",&n,&a)&&(n||a)){
        if(isprime(n)){printf("no\n");continue;}
        else{
            if(modexp(a,n,n)==a) printf("yes\n");
            else printf("no\n");
        }
    }
    return 0;
}

HDU 2648：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18590
给出多个店的价格和每周上涨的价格，输出每周memory这家店的价格排名。

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
#include<iostream>
#include<string>
#include<map>
using namespace std;
map<string,int> a;
int main(){
    int n,m,k;
    while(cin>>n){
        a.clear();
        string s;
        for(int i=0;i<n;++i) cin>>s,a[s]=0;
        cin>>m;
        for(int i=0;i<m;++i){
            int aim=0,ans=1;
            for(int j=0;j<n;++j){
                cin>>k>>s;
                a[s]+=k;
                if(s=="memory") aim=a[s];
            }
            for(map<string,int>::iterator it=a.begin();it!=a.end();++it)
                if(it->second>aim) ++ans;
            cout<<ans<<endl;
        }
    }
    return 0;
}

HDU 2446：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=11791
一开始枚举前缀和再进行二分查找。结果内存超限了。
不会优化，看了结题报告才知道可以用公式做。
http://blog.csdn.net/zxy_snow/article/details/6721066
公式： ( n 3 − n ) 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//原来的代码：
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=3810779;
LL a[maxn],sum[maxn];
int main(){
    for(int i=1;i<maxn;++i) a[i]=a[i-1]+i,sum[i]=sum[i-1]+a[i];
    int t;scanf("%d",&t);
    while(t--){
        LL n;scanf("%lld",&n);
        int l=0,r=0,c=0;
        l=int(upper_bound(sum,sum+maxn,n)-sum);
        if(sum[l-1]==n) --l;
        n-=sum[l-1];
        r=int(upper_bound(a,a+maxn,n)-a);
        if(a[r-1]==n) --r;
        c=int(n-a[r-1]);
        printf("%d %d %d\n",l,r,c);
    }
    return 0;
}

HDU 2141：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18481
给出 a 、 b 、 c 三个数组，然后输入 s ，输出是否存在 a i 、 b j 、 c k 使得 a i + b j + c k = s 。
对两个数组进行预处理，然后在另一个中枚举，在预处理后的数组中二分查找。

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<algorithm>
using namespace std;
typedef long long LL;
const int maxn=550;
LL a[maxn],b[maxn],c[maxn],k[maxn*maxn];
int main(){
    int l,n,m,t=0;
    while(~scanf("%d%d%d",&l,&n,&m)){
        for(int i=0;i<l;++i) scanf("%lld",&a[i]);
        for(int i=0;i<n;++i) scanf("%lld",&b[i]);
        for(int i=0;i<m;++i) scanf("%lld",&c[i]);
        int pos=0;
        for(int i=0;i<l;++i)
            for(int j=0;j<n;++j)
                k[pos++]=a[i]+b[j];
        sort(c,c+m),sort(k,k+pos);
        printf("Case %d:\n",++t);
        int s;scanf("%d",&s);
        while(s--){
            LL x;scanf("%lld",&x);
            bool flag=false;
            for(int i=0;i<m;++i)
                if(binary_search(k,k+pos,x-c[i])){flag=true;break;}
            puts(flag?"YES":"NO");
        }
    }
    return 0;
}

HDU 2298：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19904
给出物体下落点的坐标和发射初始速度，求角度。物理题推公式求根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double g=9.8;
const double PI=acos(-1);
int main(){
    int t;scanf("%d",&t);
    while(t--){
        double x,y,v;
        scanf("%lf%lf%lf",&x,&y,&v);
        double a=g*x*x,b=-2*v*v*x,c=2*v*v*y+g*x*x,dt=b*b-4*a*c;
        if(dt<0){printf("-1\n");continue;}
        double x1=atan((-1*b+sqrt(dt))/(2*a)),x2=atan((-1*b-sqrt(dt))/(2*a)),ans=PI/2;
        if((x1<0||x1>PI/2)&&(x2<0||x2>PI/2)){printf("-1\n");continue;}
        if(x1>=0&&x1<=PI/2) ans=min(ans,x1);
        if(x2>=0&&x2<=PI/2) ans=min(ans,x2);
        printf("%.6f\n",ans);
    }
    return 0;
}

HDU 2289：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=15721
给出一个圆台容器，给出水的体积，求水在圆台容器中的体积。
利用圆台体积公式，二分高度，输出。

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<cstdio>
#include<cmath>
using namespace std;
const double PI=acos(-1);
const double EPS=1e-7;
double GetVolume(double r,double R,double h,double H)
{
    double u = h/H*(R-r) + r;
    return PI/3*(r*r+r*u+u*u)*h;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        double r,R,H,V;scanf("%lf%lf%lf%lf",&r,&R,&H,&V);
        double hl=0,hr=H,h=(hl+hr)/2;
        while(hr-hl>EPS){
            if(GetVolume(r,R,h,H)>V) hr=h;
            else hl=h;
            h=(hl+hr)/2;
        }
        printf("%.6f\n",h);
    }
    return 0;
}

HDU 1010：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=16336
给出一个地图，问能不能在 t 步之内从起点走到终点，不能重复走过同一个格子。
因为是恰好走到，所以是DFS的题，而不是BFS。
要进行剪枝，否则会超时。首先进行奇偶性剪枝，起点终点间的距离要和 t 的奇偶性相同，然后再查找的过程中如果当前点到终点的距离小于剩余时间就回溯。

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=10;
const int go[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
char g[maxn][maxn];
bool vis[maxn][maxn];
int n,m,t,bx,by,ex,ey;
bool dfs(int x,int y,int cur){
    if(cur==t){
        if(x==ex&&y==ey) return true;
        return false;
    }
    if(abs(x-ex)+abs(y-ey)>t-cur) return false;
    for(int i=0;i<4;++i){
        int a=x+go[i][0],b=y+go[i][1];
        if(!vis[a][b]&&(g[a][b]=='.'||g[a][b]=='D')){
            vis[a][b]=true;
            if(dfs(a,b,cur+1)) return true;
            vis[a][b]=false;
        }
    }
    return false;
}
int main(){
    while(~scanf("%d%d%d",&n,&m,&t)&&!(!n&&!m&&!t)){
        for(int i=1;i<=n;++i){
            scanf("%s",g[i]+1);
            for(int j=1;j<=m;++j){
                if(g[i][j]=='S') bx=i,by=j;
                if(g[i][j]=='D') ex=i,ey=j;
            }
        }
        if(abs(bx-ex)+abs(by-ey)>t||(abs(bx-ex)+abs(by-ey)+t)&1){puts("NO");continue;}
        memset(vis,0,sizeof(vis));
        vis[bx][by]=true;
        puts(dfs(bx,by,0)?"YES":"NO");
    }
    return 0;
}

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

发表于 分类于 Disqus：

HDU 1213：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19354
给出人数和人的关系，认识的人可以在一桌，求最少要分几桌。简单并查集的应用。

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<cstdio>
const int maxn=1010;
int p[maxn];
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx!=fy) p[fx]=fy;
    return;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int n,m;scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i) p[i]=i;
        while(m--){
            int a,b;scanf("%d%d",&a,&b);
            if(find(a)!=find(b)) --n,merge(a,b);
        }
        printf("%d\n",n);
    }
    return 0;
}

HDU 1272：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=11138
给出一个图中结点的关系，问是否是一个树。
判断只有一个连通分支，且边数 m = n − 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
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100010;
int p[maxn];
bool vis[maxn];
inline int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
    int x,y;
    bool flag=true;
    for(int i=1;i<maxn;++i) p[i]=i;
    while(~scanf("%d%d",&x,&y)){
        if(x==-1&&y==-1) break;
        if(!x&&!y){
            if(flag){
                int cnt=0;
                for(int i=1;i<maxn;++i){
                    if(vis[i]&&p[i]==i) ++cnt;
                    if(cnt>1) {flag=false;break;}
                }
            }
            puts(flag?"Yes":"No");
            flag=true;
            for(int i=1;i<maxn;++i) p[i]=i;
            memset(vis,0,sizeof(vis));
            continue;
        }
        if(!flag) continue;
        vis[x]=vis[y]=true;
        int fx=find(x),fy=find(y);
        if(fx!=fy) p[fy]=fx;
        else flag=false;
    }
    return 0;
}

HDU 1325：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=27465
与上题类似，是要判断是否为有向树。
在上题基础上还要满足每个结点的入度之多为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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
int p[maxn];
bool vis[maxn];
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x!=y) p[y]=x;
    return;
}
int main(){
    int u,v,tt=0,edge=0,node=0;
    bool flag=true;
    for(int i=0;i<maxn;++i) p[i]=i;
    while(~scanf("%d%d",&u,&v)){
        if(u==-1&&v==-1) break;
        if(!u&&!v){
            if(node-1!=edge) flag=false;
            printf("Case %d is %s tree.\n",++tt,flag?"a":"not a");
            memset(vis,0,sizeof(vis));
            for(int i=0;i<maxn;++i) p[i]=i;
            flag=true;
            node=edge=0;
        }
        if(!flag) continue;
        if(!vis[u]) ++node,vis[u]=true;
        if(!vis[v]) ++node,vis[v]=true;
        ++edge;
        if(p[v]!=v) flag=false;
        merge(u,v);
    }
    return 0;
}

HDU 1856：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=11137
给出 n 个人物关系，问最多能挑选出的有着直接或间接朋友关系的集合的人的数量。并查集初始化每个人的权值为一，求最大权值的集合。

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int p[maxn],num[maxn];
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx!=fy) p[fx]=fy,num[fy]+=num[fx];
    return;
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        if(!n){printf("1\n");continue;}
        int ans=0,max_=0;
        for(int i=1;i<maxn;++i) p[i]=i,num[i]=1;
        for(int i=1;i<=n;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            max_=max(max_,u),max_=max(max_,v);
            merge(u,v);
        }
        for(int i=1;i<=max_;++i) ans=max(ans,num[i]);
        printf("%d\n",ans);
    }
    return 0;
}

HDU 1102：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18449
给出 n 个点之间任意两点建立通路的费用，再给出 m 条建好的路，求最小生成树（MST）。

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
int g[110][110];
int p[maxn],u[maxn],v[maxn],w[maxn],r[maxn],b[maxn];
bool cmp(int i,int j){
    return w[i]<w[j];
}
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
    int n,m;
    while(~scanf("%d",&n)){
        m=1;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                scanf("%d",&w[m]);
                u[m]=i,v[m]=j,r[m]=m,++m;
            }
        --m;
        for(int i=1;i<=n;++i) p[i]=i;
        int q;scanf("%d",&q);
        for(int i=1;i<=q;++i){
            int u,v;scanf("%d%d",&u,&v);
            int x=find(u),y=find(v);
            p[x]=y;
        }
        sort(r+1,r+m+1,cmp);
        int ans=0;
        for(int i=1;i<=m;++i){
            if(b[r[i]]) continue;
            int e=r[i],x=find(u[e]),y=find(v[e]);
            if(x!=y) ans+=w[e],p[x]=y;
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDU 1232：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19355
有 n 个结点， m 条边，求使所有结点连通还要建立至少几条边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int p[maxn];
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)&&n){
        int cnt=0;
        for(int i=1;i<=n;++i) p[i]=i;
        for(int i=0;i<m;++i){
            int x,y;scanf("%d%d",&x,&y);
            int fx=find(x),fy=find(y);
            if(fx!=fy) p[fx]=fy,++cnt;
        }
        printf("%d\n",n-1-cnt);
    }
    return 0;
}

HDU 1233：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=20289
给出n个结点和每个结点间的距离，求使所有结点连通的边的长度和最小值。

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
int p[maxn],u[maxn],v[maxn],w[maxn],r[maxn];
bool cmp(int i,int j){
    return w[i]<w[j];
}
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        int m=n*(n-1)/2;
        for(int i=1;i<=n;++i) p[i]=i;
        for(int i=1;i<=m;++i) scanf("%d%d%d",&u[i],&v[i],&w[i]),r[i]=i;
        sort(r+1,r+m+1,cmp);
        int ans=0;
        for(int i=1;i<=m;++i){
            int e=r[i],x=find(u[e]),y=find(v[e]);
            if(x!=y) ans+=w[e],p[x]=y;
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDU 1875：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=15740
给出结点的坐标，求使所有结点连通的边的最小花费和。当距离 d < 10 或 d > 1000 时不能建立边。

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
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=10010;
int u[maxn],v[maxn],r[maxn],p[maxn];
double w[maxn];
struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y){}
}a[110];
bool cmp(int i,int j){
    return w[i]<w[j];
}
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int n;scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
        int m=1;
        for(int i=1;i<=n;++i)
            for(int j=i+1;j<=n;++j){
                u[m]=i,v[m]=j,w[m]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
                if(w[m]>=10&&w[m]<=1000) ++m;
            }
        --m;
        for(int i=1;i<=m;++i) r[i]=i;
        for(int i=1;i<=n;++i) p[i]=i;
        sort(r+1,r+m+1,cmp);
        int cnt=0;
        double ans=0;
        for(int i=1;i<=m;++i){
            int e=r[i],x=find(u[e]),y=find(v[e]);
            if(x!=y) ans+=w[e],p[x]=y,++cnt;
        }
        if(cnt+1==n) printf("%.1lf\n",ans*100);
        else printf("oh!\n");
    }
    return 0;
}

HDU 1879：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=23262
给出结点、建造边的花费、部分已经建好的边，求使所有结点连通的最小花费。

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
int p[maxn],u[maxn],v[maxn],w[maxn],r[maxn],b[maxn];
bool cmp(int i,int j){
    return w[i]<w[j];
}
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        int m=n*(n-1)/2,ans=0;
        for(int i=1;i<=n;++i) p[i]=i;
        for(int i=1;i<=m;++i){
            scanf("%d%d%d%d",&u[i],&v[i],&w[i],&b[i]),r[i]=i;
            if(b[i]){
                int x=find(u[i]),y=find(v[i]);
                p[x]=y;
            }
        }
        sort(r+1,r+m+1,cmp);
        for(int i=1;i<=m;++i){
            if(b[r[i]]) continue;
            int e=r[i],x=find(u[e]),y=find(v[e]);
            if(x!=y) ans+=w[e],p[x]=y;
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDU 1811：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19357
给出一些人之间的偏序关系，问能否组成一张排名表。
首先用并查集储存相等的人，然后进行拓扑排序。如果出现一个以上的人不存在比自己大的人则为“UNCERTAIN”，如果形成环那么输出“CONFLICT”。

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
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100010;
char c[maxn];
int p[maxn],a[maxn],b[maxn],f[maxn];
vector<int> g[maxn];
queue<int> q;
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        int sum=n;
        bool flag=true;
        for(int i=0;i<n;++i) p[i]=i,f[i]=0,g[i].clear();
        for(int i=0;i<m;++i){
            scanf("%d %c %d",&a[i],&c[i],&b[i]);
            if(c[i]=='='){
                int x=find(a[i]),y=find(b[i]);
                if(x!=y) p[y]=x,--sum;
            }
        }
        for(int i=0;i<m;++i){
            if(c[i]=='=') continue;
            int x=find(a[i]),y=find(b[i]);
            if(c[i]=='>') g[x].push_back(y),++f[y];
            else g[y].push_back(x),++f[x];
        }
        while(!q.empty()) q.pop();
        for(int i=0;i<n;++i)
            if(!f[i]&&find(i)==i) q.push(i);
        while(!q.empty()){
            if(q.size()>1) flag=false;
            int cur=q.front();q.pop();
            --sum;
            for(int i=0;i<g[cur].size();++i)
                if(--f[g[cur][i]]==0) q.push(g[cur][i]);
        }
        if(sum>0) puts("CONFLICT");
        else if(!flag) puts("UNCERTAIN");
        else puts("OK");
    }
    return 0;
}

HDU 1829：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=16380
给出虫子的交配关系，问有没有同性恋的虫子。
用并查集合并，同时记录每个虫子所在的层数，出现相同层数的虫子交配即为同性恋。

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>
using namespace std;
const int maxn=20010;
int p[maxn],rank[maxn];
bool flag;
int find(int x){
    if(x==p[x]) return p[x];
    int t=find(p[x]);
    rank[x]=(rank[p[x]]+rank[x])&1;
    return p[x]=t;
}
void merge(int x, int y){
    int a=find(x), b=find(y);
    if(a==b){
        if(rank[x]==rank[y]) flag=true;
        return;
    }
    p[a]=b;
    rank[a]=(rank[x]+rank[y]+1)&1;
}
int main(){
    int t,tt=0;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        flag=false;
        for(int i=0;i<=n;++i) p[i]=i,rank[i]=0;
        for(int i=0;i<m;++i){
            int x,y;scanf("%d%d",&x,&y);
            if(flag) continue;
            merge(x,y);
        }
        printf("Scenario #%d:\n",++tt);
        printf("%s\n\n",flag?"Suspicious bugs found!":"No suspicious bugs found!");
    }
    return 0;
}

HDU 1198：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=16425
给出11种管道，再给出地图，问有几个连通分支。
貌似可以用并查集做，但是DFS时间也够，而且感觉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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=55;
const int go[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
const bool road[11][4]={
    {1,1,0,0},{0,1,1,0},{1,0,0,1},
    {0,0,1,1},{0,1,0,1},{1,0,1,0},
    {1,1,1,0},{1,1,0,1},{1,0,1,1},
    {0,1,1,1},{1,1,1,1}
};
char g[maxn][maxn];
int vis[maxn][maxn];
int p[maxn],n,m;
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x!=y) p[y]=x;
    return;
}
void dfs(int x,int y,int cnt){
    char& c=g[x][y];
    vis[x][y]=cnt;
    for(int i=0;i<4;++i)
        if(road[c-'A'][i]){
            int a=x+go[i][0],b=y+go[i][1];
            char& cc=g[a][b];
            int j=0;
            if(i==0) j=2;if(i==1) j=3;if(i==3) j=1;
            if(road[cc-'A'][j]&&a>=0&&a<n&&b>=0&&b<m&&!vis[a][b])
                dfs(a,b,cnt);
        }
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        if(n==-1&&m==-1) break;
        memset(vis,0,sizeof(vis));
        int cnt=0;
        for(int i=0;i<n;++i) scanf("%s",g[i]);
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                if(!vis[i][j]) dfs(i,j,++cnt);
        printf("%d\n",cnt);
    }
    return 0;
}

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