Chengrui's Blog

0%

发表于 分类于 Disqus：

计算几何基础部分大部分题目只要有模板就能过了，下面的题也大都是贴模板过的。

HDU 1086：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17612
给出 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>
struct Line{
    double x1,y1,x2,y2;
}a[110];
bool solve(Line a,Line b){
    if(((a.x1-b.x1)*(a.y2-b.y1)-(a.x2-b.x1)*(a.y1-b.y1))*((a.x1-b.x2)*(a.y2-b.y2)-(a.x2-b.x2)*(a.y1-b.y2))>0)return false;
    if(((b.x1-a.x1)*(b.y2-a.y1)-(b.x2-a.x1)*(b.y1-a.y1))*((b.x1-a.x2)*(b.y2-a.y2)-(b.x2-a.x2)*(b.y1-a.y2))>0)return false;
    return true;
}
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        int cnt=0;
        for(int i=0;i<n;++i)
            scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j)
                if(solve(a[i],a[j]))
                    ++cnt;
        printf("%d\n",cnt);
    }
    return 0;
}

HDU 1115：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=16214
按顺序给出多个点，求给出点的的重心坐标。

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
#include<cstdio>
using namespace std;
const int maxn=1000010;
struct node{
    double x,y;
}a[maxn];
node gravity(node *p, int n)
{
    double area = 0;
    node center;
    center.x = 0;
    center.y = 0;
    for (int i = 0; i < n-1; i++)
    {
        area += (p[i].x*p[i+1].y - p[i+1].x*p[i].y)/2;
        center.x += (p[i].x*p[i+1].y - p[i+1].x*p[i].y) * (p[i].x + p[i+1].x);
        center.y += (p[i].x*p[i+1].y - p[i+1].x*p[i].y) * (p[i].y + p[i+1].y);
    }
    area += (p[n-1].x*p[0].y - p[0].x*p[n-1].y)/2;
    center.x += (p[n-1].x*p[0].y - p[0].x*p[n-1].y) * (p[n-1].x + p[0].x);
    center.y += (p[n-1].x*p[0].y - p[0].x*p[n-1].y) * (p[n-1].y + p[0].y);
    center.x /= 6*area;
    center.y /= 6*area;
    return center;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int n;scanf("%d",&n);
        for(int i=0;i<n;++i)
            scanf("%lf%lf",&a[i].x,&a[i].y);
        node ans=gravity(a,n);
        printf("%.2lf %.2lf\n",ans.x,ans.y);
    }
    return 0;
}

HDU 2036：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17490
按顺序给出多个点的坐标，求所构成的凸多边形面积。

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>
const int maxn=110;
struct point{
    double x,y;
}a[maxn];
double area_polygon(int n,point* p){
    double s1=0,s2=0;
    for(int i=0;i<n;++i)
        s1+=p[(i+1)%n].y*p[i].x,s2+=p[(i+1)%n].y*p[(i+2)%n].x;
    return fabs(s1-s2)/2;
}
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;++i)
            scanf("%lf%lf",&a[i].x,&a[i].y);
        printf("%.1lf\n",area_polygon(n,a));
    }
    return 0;
}

HDU 2108：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18631
按顺序给出多个点，判断形成的是凸多边形，还是凹多边形。

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>
const int maxn=110;
struct point{
    double x,y;
}a[maxn];
#define eps 1e-8
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
double xmult(point p1,point p2,point p0){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int is_convex(int n,point* p){
    int i,s[3]={1,1,1};
    for (i=0;i<n&&s[1]|s[2];i++)
        s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0; return s[1]|s[2];
}
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;++i)
            scanf("%lf%lf",&a[i].x,&a[i].y);
        puts(is_convex(n,a)?"convex":"concave");
    }
    return 0;
}

HDU 1392：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18630
给出多个点，求凸包的周长。

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<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=110;
struct point{
    double x,y;
}a[maxn],b[maxn];
bool mult(point p0,point p1,point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)>=(p2.x-p0.x)*(p1.y-p0.y);
}
bool operator<(const point &p1,const point &p2){
    return p1.y<p2.y||(p1.y==p2.y&&p1.x<p2.x);
}
int graham(point pnt[],int n,point res[]){
    int i,len,top=1;
    sort(pnt,pnt+n);
    if(n==0) return 0;
    res[0]=pnt[0];
    if(n==1) return 1;
    res[1]=pnt[1];
    if(n==2) return 2;
    res[2]=pnt[2];
    for(i=2;i<n;i++){
        while(top&&mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top]=pnt[i];
    }
    len=top;res[++top]=pnt[n-2];
    for(i=n-3;i>=0;i--){
        while(top!=len&&mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top]=pnt[i];
    }
    return top;
}
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
        int k=graham(a,n,b);
        double ans=0;
        for(int i=0;i<k-1;++i)
            ans+=sqrt((b[i].x-b[i+1].x)*(b[i].x-b[i+1].x)+(b[i].y-b[i+1].y)*(b[i].y-b[i+1].y));
        if(k>2) ans+=sqrt((b[k-1].x-b[0].x)*(b[k-1].x-b[0].x)+(b[k-1].y-b[0].y)*(b[k-1].y-b[0].y));
        printf("%.2lf\n",ans);
    }
    return 0;
}

HDU 1348：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=32007
求凸包每个顶点向外延伸半径为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
53
54
55
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
struct point{
    double x,y;
}a[maxn],b[maxn];
bool mult(point p0,point p1,point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)>=(p2.x-p0.x)*(p1.y-p0.y);
}
bool operator<(const point &p1,const point &p2){
    return p1.y<p2.y||(p1.y==p2.y&&p1.x<p2.x);
}
int graham(point pnt[],int n,point res[]){
    int i,len,top=1;
    sort(pnt,pnt+n);
    if(n==0) return 0;
    res[0]=pnt[0];
    if(n==1) return 1;
    res[1]=pnt[1];
    if(n==2) return 2;
    res[2]=pnt[2];
    for(i=2;i<n;i++){
        while(top&&mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top]=pnt[i];
    }
    len=top;res[++top]=pnt[n-2];
    for(i=n-3;i>=0;i--){
        while(top!=len&&mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top]=pnt[i];
    }
    return top;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int n,l;scanf("%d%d",&n,&l);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
        int k=graham(a,n,b);
        double ans=0;
        for(int i=0;i<k-1;++i)
            ans+=sqrt((b[i].x-b[i+1].x)*(b[i].x-b[i+1].x)+(b[i].y-b[i+1].y)*(b[i].y-b[i+1].y));
        if(k>2) ans+=sqrt((b[k-1].x-b[0].x)*(b[k-1].x-b[0].x)+(b[k-1].y-b[0].y)*(b[k-1].y-b[0].y));
        ans+=2*acos(-1)*l;
        printf("%.0lf\n",ans);
        if(t) printf("\n");
    }
    return 0;
}

HDU 2150：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=31178
给出多条线段，判断有无相交线段。

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>
struct Line{
    double x1,y1,x2,y2;
    Line(double x1=0,double y1=0,double x2=0,double y2=0):x1(x1),y1(y1),x2(x2),y2(y2){}
};
struct node{
    int k;
    Line l[110];
}a[33];
bool solve(Line a,Line b){
    if(((a.x1-b.x1)*(a.y2-b.y1)-(a.x2-b.x1)*(a.y1-b.y1))*((a.x1-b.x2)*(a.y2-b.y2)-(a.x2-b.x2)*(a.y1-b.y2))>0)return false;
    if(((b.x1-a.x1)*(b.y2-a.y1)-(b.x2-a.x1)*(b.y1-a.y1))*((b.x1-a.x2)*(b.y2-a.y2)-(b.x2-a.x2)*(b.y1-a.y2))>0)return false;
    return true;
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        for(int i=0;i<n;++i){
            scanf("%d",&a[i].k);
            --a[i].k;
            double px1,py1;
            scanf("%lf%lf",&px1,&py1);
            for(int j=0;j<a[i].k;++j){
                double x1,y1;
                scanf("%lf%lf",&x1,&y1);
                a[i].l[j]=Line(px1,py1,x1,y1);
                px1=x1,py1=y1;
            }
        }
        bool flag=false;
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j)
                for(int k=0;k<a[i].k;++k)
                    for(int l=0;l<a[j].k;++l)
                        if(solve(a[i].l[k],a[j].l[l])) {flag=true;goto END;}
    END:
        printf("%s\n",flag?"Yes":"No");
    }
    return 0;
}

HDU 1558：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19356
给出多条线段，输出有几个连通块。判断线段相交之后，用并查集求解。

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>
#include<string>
using namespace std;
const int maxn=1010;
int p[maxn],num[maxn];
struct Line{
    double x1,y1,x2,y2;
    Line(double x1=0,double y1=0,double x2=0,double y2=0):x1(x1),y1(y1),x2(x2),y2(y2){}
}a[maxn];
//有模板就是好！！！
bool solve(Line a,Line b){
    if(((a.x1-b.x1)*(a.y2-b.y1)-(a.x2-b.x1)*(a.y1-b.y1))*((a.x1-b.x2)*(a.y2-b.y2)-(a.x2-b.x2)*(a.y1-b.y2))>0)return false;
    if(((b.x1-a.x1)*(b.y2-a.y1)-(b.x2-a.x1)*(b.y1-a.y1))*((b.x1-a.x2)*(b.y2-a.y2)-(b.x2-a.x2)*(b.y1-a.y2))>0)return false;
    return true;
}
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 t;cin>>t;
    while(t--){
        int n,cnt=0;cin>>n;
        for(int i=0;i<n;++i){
            string s;cin>>s;
            if(s=="P"){
                ++cnt,p[cnt]=cnt,num[cnt]=1;
                Line& k=a[cnt];
                cin>>k.x1>>k.y1>>k.x2>>k.y2;
                for(int j=1;j<cnt;++j){
                    if(find(j)!=find(cnt)&&solve(a[j],k))
                        merge(cnt,j);
                }
            }
            else if(s=="Q"){
                int k;cin>>k;
                cout<<num[find(k)]<<endl;
            }
        }
        if(t) cout<<endl;
    }
    return 0;
}

HDU 1785：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=30271
就是结构体重载运算符的题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<algorithm>
const int maxn=110;
struct node{
    double x,y;
    bool operator < (const node& rhs) const {
        return x*rhs.y>rhs.x*y;
    }
}a[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)&&n>=0){
        for(int i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
        std::sort(a,a+n);
        for(int i=0;i<n;++i) printf("%.1lf %.1lf%c",a[i].x,a[i].y,i==n-1?'\n':' ');
    }
    return 0;
}

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

发表于 分类于 Disqus：

HDU 1028：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18473
输入 n ( n ≤ 120 ) ，求 n 的拆分的个数，直接套用母函数模板。

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

HDU 1398：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=21519
与上题类似，但是数字只能是平方数，所以由 k + = i 变成了 k + = s q , s q = i ∗ i 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
const int maxn=10010;
int c1[maxn],c2[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<=n;++i) c1[i]=1,c2[i]=0;
        for(int i=2;i*i<=n;++i){
            int sq=i*i;
            for(int j=0;j<=n;++j)
                for(int k=0;k+j<=n;k+=sq)
                    c2[j+k]+=c1[j];
            for(int j=0;j<=n;++j) c1[j]=c2[j],c2[j]=0;
        }
        printf("%d\n",c1[n]);
    }
    return 0;
}

HDU 1085：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17611
给出 n 1 个1元硬币， n 2 个3元硬币， n 3 个5元硬币，求最小的不能凑成的金额是多少。
首先求出硬币金额总和，确定循环上届，然后修改母函数模板即可。

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>
#include<cstdlib>
const int maxn=10010;
int v[3]={1,2,5},num[3];
bool vis[maxn],tmp[maxn];
int main(){
    while(~scanf("%d%d%d",&num[0],&num[1],&num[2])){
        int sum=v[0]*num[0]+v[1]*num[1]+v[2]*num[2];
        if(!sum) break;
        memset(vis,0,sizeof(vis));
        memset(tmp,0,sizeof(tmp));
        for(int i=0;i<=v[0]*num[0];i+=v[0]) vis[i]=true;
        for(int i=1;i<3;++i){
            for(int j=0;j<=sum;++j)
                for(int k=0;k+j<=sum&&k<=v[i]*num[i];k+=v[i])
                    tmp[k+j]|=vis[j];
            for(int j=0;j<=sum;++j)
                vis[j]=tmp[j],tmp[j]=0;
        }
        int ans=1;
        while(vis[ans]) ++ans;
        printf("%d\n",ans);
    }
    return 0;
}

HDU 1171：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17611
放在母函数专题里，但是我贴多重背包模板做的。

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<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=250010;
int d[maxn],m[55],w[55],v;
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 n;
    while(~scanf("%d",&n)&&!(n<0)){
        int sum=0;
        for(int i=1;i<=n;++i){
            scanf("%d %d",&w[i],&m[i]);
            sum+=m[i]*w[i];
        }
        v=sum/2;
        for(int i=0;i<=v;++i) d[i]=(i?-inf:0);
        for(int i=1;i<=n;++i) mutiple_pack(d,w[i],w[i],m[i]);
        int ans=0;
        for(int i=0;i<=v;++i) ans=max(ans,d[i]);
        printf("%d %d\n",sum-ans,ans);
    }
}

HDU 1709：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=32231
给出 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
31
32
33
34
#include<cstdio>
#include<cstring>
#include<cstdlib>
const int maxn=10010;
int a[maxn],ans[maxn],tmp[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        memset(ans,0,sizeof(ans));
        int sum=0;
        for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
        for(int i=0;i<=a[1];i+=a[1]) ans[i]=1;
        for(int i=2;i<=n;++i){
            for(int j=0;j<=sum;++j)
                for(int k=0;k+j<=sum&&k<=a[i];k+=a[i])
                    tmp[k+j]+=ans[j],tmp[abs(k-j)]+=ans[j];
            for(int j=0;j<=sum;++j)
                ans[j]=tmp[j],tmp[j]=0;
        }
        int cnt=0;
        for(int i=1;i<=sum;++i){
            if(ans[i]) continue;
            ans[++cnt]=i;
        }
        printf("%d\n",cnt);
        if(!cnt) continue;
        for(int i=1;i<=cnt;++i){
            if(i!=1) printf(" ");
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}

HDU 2082：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=23618
26个字母的价值分别为1～26，给出26个字母各自的个数，求能组成多少个价值小于50的单词，忽略单词的顺序。
有上界的母函数问题，将模板最内层循环次数修改为当前字母个数。

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>
const int maxn=55;
int c1[maxn],c2[maxn],a[30];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        for(int i=1;i<=26;++i) scanf("%d",&a[i]);
        for(int i=0;i<=a[1];++i) c1[i]=1,c2[i]=0;
        for(int i=2;i<=26;++i){
            for(int j=0;j<=maxn;++j)
                for(int k=0;k+j<=maxn&&k<=a[i]*i;k+=i)
                    c2[j+k]+=c1[j];
            for(int j=0;j<=maxn;++j) c1[j]=c2[j],c2[j]=0;
        }
        int ans=0;
        for(int i=1;i<=50;++i) ans+=c1[i];
        printf("%d\n",ans);
    }
    return 0;
}

HDU 2152：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=31180
给出 n 种水果，要买 m 个，每种又下界 a i 上界 b i 。求有多少种买法。
有上下界的母函数，内层循环下界为 a i 个，上界为 b i 个。

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<cstring>
using namespace std;
const int maxn=110;
int c1[maxn],c2[maxn],l[maxn],r[maxn];
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;++i)
            scanf("%d%d",&l[i],&r[i]);
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        c1[0]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<=m;++j)
                for(int k=l[i];j+k<=m&&k<=r[i];++k)
                    c2[j+k]+=c1[j];
            for(int j=0;j<=m;++j) c1[j]=c2[j],c2[j]=0;
        }
        printf("%d\n",c1[m]);
    }
    return 0;
}

HDU 1059：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17678
也是贴多重背包模板过的。

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=5000;
int d[maxn],m[7],v;
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=0;
    while(1){
        v=0;
        for(int i=1;i<=6;++i){
            scanf("%d",&m[i]);
            m[i]%=240,v+=m[i]*i;
        }
        if(!v) break;
        bool ok=true;
        printf("Collection #%d:\n",++t);
        if(v&1) ok=false;
        v/=2;
        for(int i=0;i<=v;++i) d[i]=(i?-inf:0);
        for(int i=1;i<=6;++i) mutiple_pack(d,i,i,m[i]);
        if(d[v]>=0&&ok) printf("Can be divided.\n\n");
        else printf("Can't be divided.\n\n");
    }
}

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

发表于 分类于 Disqus：

HDU 1215：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=22310
给出一个数字 n ( n ≤ 500000 ) ，输出n的所有因子的和 a i 。
筛法打表求出500000以内所有 a i 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
using namespace std;
const int maxn=500010;
int n,a[maxn];
int main(){
    for(int i=1;i<maxn;++i)
        for(int j=i+i;j<maxn;j+=i)
            a[j]+=i;
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        printf("%d\n",a[n]);
    }
    return 0;
}

HDU 1286：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=37852
写解题报告才知道，这原来是求欧拉函数 Φ ( n ) 的题，结果数据水了，我是暴过的。 不贴自己代码了，贴个欧拉函数模板。

1
2
3
4
5
6
7
8
9
int phi[maxn]={0,1};
void phi_table (int n) {
    for(int i=2;i<=n;++i) 
    if(!phi[i])
        for(int j=i;j<=n;j+=i) {
            if(!phi[j]) phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
}

HDU 1406：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=36674
定义完数：如果一个大于1的正整数的所有因子之和等于它的本身，则称这个数是完数。输入 n u m 1 和 n u m 2 ，输出两数之间完数的个数。
打表求出每个数所有因子和，判断是否为完数，求前缀和输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
int a[maxn],b[maxn];
int main(){
    for(int i=1;i<maxn;++i)
        for(int j=i+i;j<maxn;j+=i)
            a[j]+=i;
    for(int i=1;i<maxn;++i)
        if(a[i]==i) b[i]=b[i-1]+1;
        else b[i]=b[i-1];
    int t;scanf("%d",&t);
    while(t--){
        int l,r;scanf("%d%d",&l,&r);
        if(l>r) swap(l,r);
        printf("%d\n",b[r]-b[l-1]);
    }
    return 0;
}

HDU 2007：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=32827
给定一段连续的整数，求出他们中所有偶数的平方和以及所有奇数的立方和。
打表求解。

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;
const int maxn=2510;
int a[maxn],b[maxn];
int main(){
    for(int i=1;i<maxn;++i){
        a[i]=a[i-1],b[i]=b[i-1];
        if(i&1) a[i]+=i*i*i;
        else b[i]+=i*i;
    }
    int l,r;
    while(~scanf("%d%d",&l,&r)){
        if(l>r) swap(l,r);
        printf("%d %d\n",b[r]-b[l-1],a[r]-a[l-1]);
    }
    return 0;
}

HDU 1425：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=21604
输入 n 个数，从大到小输出前 m 大的数，数的范围 [ − 500000 , + 500000 ] 。
感觉题目原意是想让用数组统计的， n ≤ 1000000 的数据量，快排 O ( n l o g 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
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=500010;
int a[maxn*2];
inline 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 k) {
    if(k<0) {putchar('-');k=-k;}
    if(k>=10) Out(k/10);
    putchar(k%10+'0');
}
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        memset(a,0,sizeof(a));
        getchar();
        for(int i=0;i<n;++i){
            int k=Scan();
            ++a[k+maxn];
        }
        bool first=true;
        for(int i=2*maxn-1;i>=0;--i){
            if(!m) break;
            for(int j=a[i];j>0;--j){
                if(first) first=false;
                else putchar(' ');
                Out(i-maxn),--m;
                if(!m)break;
            }
        }
        putchar('\n');
    }
    return 0;
}

HDU 2039：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=32836
输入三个数，判断能否构成三角形。很简单的题，但是坑在题目并没有说是整数，所以要用double。

1
2
3
4
5
6
7
8
9
10
11
#include<cstdio>
using namespace std;
int main(){
    int t;scanf("%d",&t);
    while(t--){
        double a,b,c;
        scanf("%lf%lf%lf",&a,&b,&c);
        puts(a>0&&b>0&&c>0&&a+b>c&&b+c>a&&a+c>b?"YES":"NO");
    }
    return 0;
}

HDU 1170：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17623
每组输入一个符号和两个整数，求他们做这种运算的结果。
简单题，但是有坑，坑在如果是除法，整除不输出无意义的零，否则输出。也就是说计算 1 ÷ 10 时，需要输出0.10而不是0.1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
using namespace std;
int main(){
    int t;scanf("%d",&t);
    while(t--){
        getchar();
        char c=getchar();
        int a,b;scanf("%d%d",&a,&b);
        if(c=='+') printf("%d",a+b);
        if(c=='-') printf("%d",a-b);
        if(c=='*') printf("%d",a*b);
        if(c=='/'){if(a%b==0)printf("%d",a/b);else printf("%.2lf",1.0*a/b);}
        putchar('\n');
    }
    return 0;
}

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

发表于 分类于 Disqus：

HDU 2084：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=23620
数字三角形，简单DP。

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 g[maxn][maxn],d[maxn][maxn];
int main(){
    int t;scanf("%d",&t);
    while(t--){
        memset(d,0,sizeof(d));
        int n;scanf("%d",&n);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=i;++j)
                scanf("%d",&g[i][j]);
        for(int i=n;i>0;--i)
            for(int j=1;j<=i;++j)
                d[i][j]=max(d[i+1][j],d[i+1][j+1])+g[i][j];
        printf("%d\n",d[1][1]);
    }
    return 0;
}

HDU 1176：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=22018
给出馅饼掉落的时间和位置，每次只能移动一格，求最多接到多少个馅饼。简单DP。

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=100010;
int d[maxn][13],g[maxn][13];
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        memset(d,0,sizeof(d));
        memset(g,0,sizeof(g));
        int maxt=0;
        for(int i=1;i<=n;++i){
            int p,t;
            scanf("%d%d",&p,&t);
            ++g[t][p+1],maxt=max(maxt,t);
        }
        for(int i=maxt;i>=0;--i)
            for(int j=1;j<=11;++j)
                d[i][j]=max(max(d[i+1][j-1],d[i+1][j]),d[i+1][j+1])+g[i][j];
        printf("%d\n",d[0][6]);
    }
    return 0;
}

HDU 1087：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17613
求最大上升子序列的和，数据量小，可以 O ( n 2 ) 算法DP求解。

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

HDU 1421：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17361
给出每个物品的重量 a i ，每次可以搬两件，搬物品 a i 和 a j 的疲劳值为 p = a 2 i + a 2 j ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ √ 。给出物品数 n 、要搬的次数 k 、 n 件物品的重量，输出最小疲劳值。
二维DP，排序之后，求相邻两物品重量差 b i ， d [ i ] [ j ] = m i n ( d [ i − 1 ] [ j − 2 ] + b [ j − 1 ] , d [ i ] [ j − 1 ] ) 。

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=2010;
int a[maxn],b[maxn],d[maxn/2][maxn];
int main(){
    int n,k;
    while(~scanf("%d%d",&n,&k)){
        memset(d,0x3f,sizeof(d));
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        for(int i=1;i<n;++i) b[i]=(a[i]-a[i+1])*(a[i]-a[i+1]);
        for(int i=0;i<=k;++i){
            for(int j=2*i;j<=n;++j)
                if(!i) d[i][j]=0;
                else d[i][j]=min(d[i-1][j-2]+b[j-1],d[i][j-1]);
        }
        printf("%d\n",d[k][n]);
    }
    return 0;
}

HDU 1058：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17350
类似于紫书上丑数的生成，统计当前最大数因子中2、3、5、7的个数。然后每次生成最小的数。

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<algorithm>
using namespace std;
const int maxn=5900;
int ans[maxn];
int main(){
    ans[1]=1;
    int a=1,b=1,c=1,d=1;
    for(int i=2;i<=5842;++i){
        ans[i]=min(2*ans[a],min(3*ans[b],min(5*ans[c],7*ans[d])));
        if(ans[i]==2*ans[a]) ++a;
        if(ans[i]==3*ans[b]) ++b;
        if(ans[i]==5*ans[c]) ++c;
        if(ans[i]==7*ans[d]) ++d;
    }
    int n;
    while(~scanf("%d",&n)&&n){
        printf("The %d",n);
        if(n%10==1&&n%100!=11) printf("st");
        else if(n%10==2&&n%100!=12) printf("nd");
        else if(n%10==3&&n%100!=13) printf("rd");
        else printf("th");
        printf(" humble number is %d.\n",ans[n]);
    }
    return 0;
}

HDU 1160：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=30429
给出 n 个老鼠的体重 w 和速度 v ，求最长的老鼠 w 增大， v 减小的序列长度，并输出这个序列。
对 w 排序后，对 v 求LIS。

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<algorithm>
#include<stack>
using namespace std;
const int maxn=1010;
int d[maxn],pre[maxn];
struct node{
    int w,v,id;
    bool operator < (const node& rhs) const {
        return w==rhs.w?v<rhs.v:w<rhs.w;
    }
}a[maxn];
int main(){
    int n=0;
    while(~scanf("%d%d",&a[n+1].w,&a[n+1].v)) ++n,a[n].id=n,d[n]=1;
    sort(a+1,a+n+1);
    int best=1,pos=1;
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            if(a[i].w<a[j].w&&a[i].v>a[j].v){
                if(d[i]+1>d[j]) d[j]=d[i]+1,pre[a[j].id]=a[i].id;
                if(d[j]>best){
                    best=d[j];
                    pos=a[j].id;
                }
            }
    printf("%d\n",best);
    stack<int> ans;
    while(pos) ans.push(pos),pos=pre[pos];
    while(!ans.empty()) printf("%d\n",ans.top()),ans.pop();
    return 0;
}

HDU 1159：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=30429
求两个字符串的LCS长度。 O ( n 2 ) 的DP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=550;
int d[maxn][maxn];
char s1[maxn],s2[maxn];
int main(){
    while(~scanf("%s%s",s1+1,s2+1)){
        memset(d,0,sizeof(d));
        int l1=(int)strlen(s1+1),l2=(int)strlen(s2+1);
        for(int i=1;i<=l1;++i)
            for(int j=1;j<=l2;++j){
                if(s1[i]==s2[j]) d[i][j]=d[i-1][j-1]+1;
                else d[i][j]=max(d[i-1][j],d[i][j-1]);
            }
        printf("%d\n",d[l1][l2]);
    }
    return 0;
}

HDU 1003：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=15514
求数列最大连续和，简单DP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
const int inf=0x3f3f3f3f;
int main(){
    int t,tt=0;scanf("%d",&t);
    while(t--){
        int n;scanf("%d",&n);
        int sum=-inf,best=-inf,st=1,ed=1,cur=1;
        for(int i=1;i<=n;i++){
            if(sum<0) cur=i,sum=0;
            int k;scanf("%d",&k);
            sum+=k;
            if(best<sum) best=sum,st=cur,ed=i;
        }
        printf("Case %d:\n%d %d %d\n",++tt,best,st,ed);
        if(t) printf("\n");
    }
    return 0;
}

HDU 4540：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=37953
给出所有时刻地鼠的位置，共有 m ≤ 500 个位置， O ( m 2 ) ，求简单DP。

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>
#include<algorithm>
#include<cstdlib>
using namespace std;
int d[25][15],g[25][15];
int main(){
    int n,k;
    while(~scanf("%d%d",&n,&k)){
        memset(g,0,sizeof(g));
        memset(d,0x3f,sizeof(d));
        for(int i=1;i<=n;++i)
            for(int j=1;j<=k;++j)
                scanf("%d",&g[i][j]);
        int ans=0x3f3f3f3f;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=k;++j){
                if(i==1) d[i][j]=0;
                else for(int l=1;l<=k;++l)
                    d[i][j]=min(d[i][j],d[i-1][l]+abs(g[i][j]-g[i-1][l]));
                if(i==n) ans=min(ans,d[i][j]);
            }
        printf("%d\n",ans);
    }
    return 0;
}

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

发表于 分类于 Disqus：

学长给开题做的，随机队员时运气不好，把自己队的随走了一个，就剩zcy和我两个人打的。开局还行，但是毕竟人少，没法很快连续出题，后来出题速度就慢了。
A：
FZU 2054
水题，判断最大值在哪边，输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=10010;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int t1,t2;
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        t1=max(a,b),t1=max(t1,c);
        scanf("%d%d%d",&a,&b,&c);
        t2=max(a,b),t2=max(t2,c);
        printf("%d\n",t1>t2?1:2);
    }
    return 0;
}

B：
FZU 2055
一开始我敲，敲了一半发现错了，后来zcy敲的。发现自己之前想麻烦了，数据量少，直接暴力就行。

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
#include<iostream>
#include<string>
using namespace std;
string s[108],p,t;
int n,op;
bool path(string p,string d){
    int len=p.length();
    if(len>=d.length()) return false;
    for(int i=0;i<len;++i){
        if(p[i]!=d[i]) return false;
    }
    return true;
}
bool duc(string t,string d){
    int lt=t.length(),ld=d.length();
    if(lt>ld) return false;
    for(int i=lt-1,j=ld-1;i>=0;--i,--j){
        if(t[i]!=d[j]) return false;
    }
    return true;
}
void judge(string p,string t){
    for(int i=0;i<n;++i)
        if(path(p,s[i])&&duc(t,s[i]))
            cout << s[i] <<endl;
    return ;
}
int main(){
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--){
        cin >> n >> op;
        for(int i=0;i<n;++i)
            cin >> s[i];
        for(int i=0;i<op;++i){
            cin >> p >> t;
            judge(p,t);
        }
    }
    return 0;
}

C：
FZU 2056
比赛时没想到，赛后问了学长思路，DP所有矩形的面积，二分搜索最大边长。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int n,m,lim;
int d[maxn][maxn];
bool ok(int h){
    for(int i=h;i<=n;++i)
        for(int j=h;j<=m;++j)
            if(d[i][j]-d[i-h][j]-d[i][j-h]+d[i-h][j-h]<=lim) return true;
    return false;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        memset(d,0,sizeof(d));
        scanf("%d%d%d",&n,&m,&lim);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j){
                int k;
                scanf("%d",&k);
                d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+k;
            }
        int top=min(n,m),bott=0,best=0;
        while(bott<=top){
            int mid=(top-bott)/2+bott;
            if(ok(mid)) best=max(best,mid*mid),bott=mid+1;
            else top=mid-1;
        }
        printf("%d\n",best);
    }
    return 0;
}

D：
比赛时看成是1w＊1w的数据量，要写类似并查集的树。赛后补题时发现是1w * 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10010;
int ch[maxn],len;
bool sex[maxn];
char ans[maxn];
bool f(int k,int x,int y){
    len=0;
    while(ch[y]){
        ans[len++]=sex[y]?'M':'F';
        if(x==(y=ch[y])){
            printf("%d ",k);
            for(int i=len-1;i>=0;--i) putchar(ans[i]);
            puts("");
            return true;
        }
    }
    return false;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        memset(ch,0,sizeof(ch));
        memset(sex,0,sizeof(sex));
        int n;scanf("%d",&n);
        int num=n/2;
        for(int i=0;i<num;++i){
            int cur,f,m;
            scanf("%d%d%d",&cur,&f,&m);
            ch[f]=ch[m]=cur,sex[m]=true;
        }
        int q;scanf("%d",&q);
        while(q--){
            int x,y;
            scanf("%d%d",&x,&y);
            if(!f(1,x,y)&&!f(0,y,x)) printf("Relative\n");
        }
    }
    return 0;
}

E：
FZU 2058
比赛时用STL写的O(nlogn)算法超时，最后没改数组写。
赛后得知可以用O(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
31
32
33
34
35
36
37
38
39
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100010;
int a[maxn];
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;
}
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        getchar();
        for(int i=0;i<n;++i) a[i]=Scan();
        sort(a,a+n);
        LL ans=0;
        int l=0,r=n-1;
        while(l<=r){
            if(a[l]==a[r]){
                if(a[l]+a[r]==m) ans+=LL(r-l)*(r-l+1)/2;
                break;
            }
            if(a[l]+a[r]==m){
                int ll=l,rr=r;
                while(a[l]==a[ll]) ++l;
                while(a[r]==a[rr]) --r;
                ans+=LL(l-ll)*(rr-r);
            }
            else if(a[l]+a[r]>m) --r;
            else ++l;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

H：
FZU 2061
比赛时准备找规律过掉这道题，快结束了得知找钱可以找好几张，之前推的不对。看也来不及推了，就和zj交流经验，再后来zcy按照zj说的过掉了这道题。。
打30~3n和的表。对每个输入遍历计数，输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
#include<math.h>
int main(){
    int num[36];
    num[0]=1;
    for(int i=1;i<20;++i)
        num[i]=num[i-1]+pow(3,i);
    int n;
    while(~scanf("%d",&n)){
        int ans=1;
        for(int i=0;i<20;++i){
            if(n>num[i]) ++ans;
            else break;
        }
        printf("%d\n",ans);
    }
    return 0;
}

I：
FZU 2062
开场我翻题时看到题目配图说是水题，就跟zcy说了，我提出思路，他感觉正确，就打了交过了。
一开始思路不太对，导致最后代码很挫。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=10010;
int d(int k){
    if(k==1) return 1;
    return d(k>>1)+1;
}
int main(){
    int n;
    while(~scanf("%d",&n))
        printf("%d\n",d(n));
    return 0;
}

J：
FZU 1859
zcy读到说是个画图的水题，我写出来，一块Debug之后过的。
对每个图分四份递归，然后输出就好。

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>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1030;
char g[maxn][maxn];
void draw(int n,int l1,int l2,int r1,int r2){
    if(n==1){g[l1][r1]='@';return;}
    int k=1<<(n-2);
    draw(n-1,l1,l1+k,r1,r1+k);
    draw(n-1,l2-k,l2,r1,r1+k);
    draw(n-1,l2-k,l2,r2-k,r2);
    return;
}
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        memset(g,' ',sizeof(g));
        draw(n,0,1<<(n-1),0,1<<(n-1));
        int k=1<<(n-1);
        for(int i=0;i<k;++i){
            for(int j=k-1;j>=0;--j)
                if(g[i][j]=='@') {g[i][j+1]=0;break;}
            puts(g[i]);
        }
        puts("");
    }
    return 0;
}

K：
比赛时以为是用线段树做，所以敲了线段树，用书上模板坑了好久。赛后学长说可以DP求，补了一个用DP过的。
n=1000，m=100000。
线段树的建树复杂度O(nlogn)，查询复杂度O(mlogn)，总复杂度O(mlogn)。
DP处理数据复杂度O(n2)，查询复杂度O(1)，总复杂度O(n2)。
还是DP更快一些。
更重要的是，个人感觉DP好写，写线段树容易出错。

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
//DP版：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int d[maxn][maxn];
int main(){
    int tt=0,n;
    while(~scanf("%d",&n)){
        memset(d,0,sizeof(d));
        for(int i=1;i<=n;++i) scanf("%d",&d[i][i]);
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j)
                d[i][j]=max(d[i][j-1],d[j][j]);
        }
        int q;scanf("%d",&q);
        printf("Case #%d:\n",++tt);
        while(q--){
            int l,r;scanf("%d%d",&l,&r);
            printf("%d\n",l<=r?d[l][r]:max(d[1][r],d[l][n]));
        }
        puts("");
    }
    return 0;
}


//线段树版：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1010;
int cnt,n,d[(1<<12)-1];
void init(int n_){
    cnt=0,n=1;
    while(n<n_) n<<=1,++cnt;
    memset(d,-1,sizeof(d));
}
int q(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return -1;
    if(a<=l&&r<=b) return d[k+1];
    return max(q(a,b,2*k+1,l,(l+r)/2),q(a,b,2*k+2,(l+r)/2,r));
}
int main(){
    int tt=0;
    while(~scanf("%d",&n)){
        int tmp=n;
        init(n);
        for(int i=1<<cnt;i<(1<<cnt)+tmp;++i) scanf("%d",&d[i]);
        int t=cnt-1;
        while(t>=0){
            int num=1<<(cnt-t);
            for(int i=1<<t;i<1<<(t+1);++i)
                d[i]=max(d[i*2],d[i*2+1]);
            --t;
        }
        int m;
        scanf("%d",&m);
        printf("Case #%d:\n",++tt);
        for(int i=0;i<m;++i){
            int l,r;
            scanf("%d%d",&l,&r);
            --l,--r;
            int ans=-1;
            if(l>r) ans=max(q(0,r+1,0,0,n),q(l,n,0,0,n));
            else ans=q(l,r+1,0,0,n);
            printf("%d\n",ans);
        }
        printf("\n");
    }
    return 0;
}

写在后面：
开场我从前往后读，zcy从后往前读。
前面的中文，读得快，我看A水，直接打了交，A1y(3)。然后继续看B是模拟，不想写模拟，跳过。C不会，D以为要建树，跳过。
E～K是英文题，挨个点着看了一遍。看到I，图上说这是水题，我就读了一遍，跟zcy讲了题意。我们感觉可做，但因为是数学，准备先放一放，一会再做。继续读题。
读别的题时，灵光乍现，感觉是二分一类的做法，跟zcy说了一下，他感觉对。就敲了，一开始想成分奇偶讨论了，所以写成递归，后来发现只需要数位数就行。提交I1y( 13)。
再后来，我敲B，zcy读题，读到J水，跟我说了。原本准备敲完B之后再弄，但是后来发现B敲错了。就开始做J，一块Debug之后过了，提交，交在E题上了，重交J 1y(55)。至此打得还不错，三道都是1y，都是FB。
再往后就有点乱了，开始看E，用map写的，不过脑补复杂度O(nlogn)，应该是STL差个常数。跳过，看其他题。
zcy给我讲K题意，我以为是线段树，我开始敲K。敲了好久样例不过。下机器，zcy敲B。Debug过程中，zcy在我的多次干扰下过掉了B，B1y(150)。
之后我继续上机改K，两次WA之后，K3y(168)。
再往后我们几乎没正经打了，尝试了使用hash_map／hash_set过E，CE，找CB头文件粘上，依然CE。后来的时间大部分都在猜H题解法，直到最后与其他 队成员交流经验，莫名其妙的过掉了，中途CE两次，H3y(295)。
赛后问了学长其他几道题的做法，补了几道题。

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

发表于 分类于 Disqus：

挺久之前做的题了，具体过程忘掉了，最近终于看懂了划分树，补了一道模版题。
A：
HDU 4245
一开始理解错了题意，以为只能是单向映射，没想到是双向的，在原代码基础上修改导致代码打的很渣。

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<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
map<string,string> a;
void pre(){
    a["Ab minor"]="G# minor";
    a["G# minor"]="Ab minor";
    a["A# major"]="Bb major";
    a["Bb major"]="A# major";
    a["A# minor"]="Bb minor";
    a["Bb minor"]="A# minor";
    a["C# major"]="Db major";
    a["Db major"]="C# major";
    a["Db minor"]="C# minor";
    a["C# minor"]="Db minor";
    a["D# major"]="Eb major";
    a["Eb major"]="D# major";
    a["D# minor"]="Eb minor";
    a["Eb minor"]="D# minor";
    a["Gb major"]="F# major";
    a["F# major"]="Gb major";
    a["Gb minor"]="F# minor";
    a["F# minor"]="Gb minor";
    a["G# major"]="Ab major";
    a["Ab major"]="G# major";
    return;
}
int main(){
    ios::sync_with_stdio(false);
    pre();
    string s;
    int t=0;
    while(getline(cin,s)){
        cout<<"Case "<<++t<<": ";
        if(a.count(s)) cout<<a[s]<<endl;
        else cout<<"UNIQUE"<<endl;
    }
    return 0;
}

C：
HDU 4247

1
2
3
4
5
6
7
8
9
10
11
12
13
14
读题之后感觉是这么做，就交了，然后就过了。
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    long long a[4],t=0;
    while(cin>>a[0]>>a[1]>>a[2]>>a[3]){
        sort(a,a+4);
        cout<<"Case "<<++t<<": ";
        cout<<a[2]+a[3]<<endl;
    }
    return 0;
}

G：
求区间的中位数，用划分树就能过。
为了补这道题，去学了划分树和线段树。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100010;
int tree[20][MAXN];//表示每层每个位置的值
int sorted[MAXN];//已经排序好的数
int toleft[20][MAXN];//toleft[p][i]表示第i层从1到i有数分入左边
void build(int l,int r,int dep){
    if(l==r)return;
    int mid=(l+r)>>1;
    int same=mid-l+1;//表示等于中间值而且被分入左边的个数
    for(int i=l;i<=r;i++)//注意是l,不是one
        if(tree[dep][i]<sorted[mid]) same--;
    int lpos=l;
    int rpos=mid+1;
    for(int i=l;i<=r;i++){
        if(tree[dep][i]<sorted[mid]) tree[dep+1][lpos++]=tree[dep][i];
        else if(tree[dep][i]==sorted[mid]&&same>0){
            tree[dep+1][lpos++]=tree[dep][i];
            same--;
        }
        else tree[dep+1][rpos++]=tree[dep][i];
        toleft[dep][i]=toleft[dep][l-1]+lpos-l;
    }
    build(l,mid,dep+1);
    build(mid+1,r,dep+1);
}
//查询区间第k大的数,[L,R]是大区间,[l,r]是要查询的小区间
int query(int L,int R,int l,int r,int dep,int k){
    if(l==r)return tree[dep][l];
    int mid=(L+R)>>1;
    int cnt=toleft[dep][r]-toleft[dep][l-1];
    if(cnt>=k){
        int newl=L+toleft[dep][l-1]-toleft[dep][L-1];int newr=newl+cnt-1;
        return query(L,mid,newl,newr,dep+1,k);
    }
    else{
        int newr=r+toleft[dep][R]-toleft[dep][r],newl=newr-(r-l-cnt);
        return query(mid+1,R,newl,newr,dep+1,k-cnt);
    }
}
int main(){
    int n,m,t=0;
    while(~scanf("%d",&n)){
        memset(tree,0,sizeof(tree));
        for(int i=1;i<=n;i++){
            scanf("%d",&tree[0][i]);
            sorted[i]=tree[0][i];
        }
        sort(sorted+1,sorted+n+1);
        build(1,n,0);
        scanf("%d",&m);
        printf("Case %d:\n",++t);
        int s,t,k;
        while(m--){
            scanf("%d%d",&s,&t);
            k=(t-s+2)/2;
            printf("%d\n",query(1,n,s,t,0,k));
        }
    }
    return 0;
}

H：
HDU 4252
给出每个点的高度，求最少有几个建筑。具体记不清了，只记得当时出的很快。

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<algorithm>
#include<set>
using namespace std;
set<int> a;
int main(){
    int n,t=0;
    while(~scanf("%d",&n)){
        a.clear();
        int cnt=0;
        for(int i=0;i<n;++i){
            int cur;
            scanf("%d",&cur);
            if(!cur) ++cnt,a.clear();
            else{
                if(a.count(cur)) ++cnt;
                set<int>::iterator it1=a.lower_bound(cur),it2=a.end();
                a.erase(it1,it2);
                a.insert(cur);
            }
        }
        printf("Case %d: %d\n",++t,n-cnt);
    }
    return 0;
}

J：
HDU 4254
比赛时没推出来公式，赛后听说是这个公式，原理还不知道。。

1
2
3
4
5
6
7
8
#include<cstdio>
int main(){
    int t=0;
    double p,q;
    while(~scanf("%lf%lf%lf",&p,&p,&q))
        printf("Case %d: %.4lf\n",++t,(q+1)/(p+2));
    return 0;
}

K：
HDU 4255
蛇形填数，之后BFS，坑在于，有可能素数连起来一直到了边界，导致判断出错，一开始数组开小了，WA了一次，不知道为什么不是RE，后来改大数组，大力出奇迹就过了 。

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
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
const int maxn=210;
const int go[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int g[maxn][maxn],vis[maxn][maxn];
bool np[maxn*maxn]={1,1};
struct point{
    int x,y;
    point(int x=0,int y=0):x(x),y(y){}
}a[maxn*maxn+1];
queue<point> q;
void pre(){
    int k=maxn*maxn;
    for(int i=2;i<k;++i)
        if(!np[i]) for(int j=i*i;j<k;j+=i) np[j]=true;
    int tot=k;
    int x,y;
    g[x=0][y=maxn-1]=k;a[tot]=point(x,y);
    while(tot>0){
        while(x+1<maxn&&!g[x+1][y]){
            --tot;++x;
            if(!np[tot]) continue;
            g[x][y]=tot;a[tot]=point(x,y);
        }
        while(y-1>=0&&!g[x][y-1]){
            --tot;--y;
            if(!np[tot]) continue;
            g[x][y]=tot;a[tot]=point(x,y);
        }
        while(x-1>=0&&!g[x-1][y]){
            --tot;--x;
            if(!np[tot]) continue;
            g[x][y]=tot;a[tot]=point(x,y);
        }
        while(y+1<maxn&&!g[x][y+1]){
            --tot;++y;
            if(!np[tot]) continue;
            g[x][y]=tot;a[tot]=point(x,y);
        }
    }
    return;
}
int main(){
    pre();
    int st,ed,t=0;
    while(~scanf("%d%d",&st,&ed)){
        memset(vis,-1,sizeof(vis));
        while(!q.empty()) q.pop();
        q.push(a[st]);
        vis[a[st].x][a[st].y]=0;
        while(!q.empty()){
            if(vis[a[ed].x][a[ed].y]!=-1) break;
            point cur=q.front();q.pop();
            for(int i=0;i<4;++i){
                int x=cur.x+go[i][0],y=cur.y+go[i][1];
                if(vis[x][y]!=-1||!g[x][y]) continue;
                q.push(a[g[x][y]]);
                vis[x][y]=vis[cur.x][cur.y]+1;
            }
        }
        printf("Case %d: ",++t);
        if(vis[a[ed].x][a[ed].y]!=-1) printf("%d\n",vis[a[ed].x][a[ed].y]);
        else printf("impossible\n");
    }
    return 0;
}

L：
HDU 4256
水题，打表过。

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<iostream>
#include<string>
#include<map>
using namespace std;
map<string,int> a;
void pre(){
    a["I"]=1;
    a["II"]=2;
    a["III"]=3;
    a["IV"]=4;
    a["V"]=5;
    a["VI"]=6;
    a["VII"]=7;
    a["VIII"]=8;
    a["IX"]=9;
    a["X"]=10;
    a["XI"]=11;
    a["XII"]=12;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    pre();
    string s;
    int t=0;
    while(cin>>s){
        cout<<"Case "<<++t<<": "<<a[s]<<endl;
    }
    return 0;
}

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

发表于 分类于 Disqus：

Rank 2。
开场照着书上敲了一道题，然后就没出题。赛后补了一道数学＋枚举的题。
A：HDU 2333
照着蓝书敲的，书上给的貌似是c++11标准的，CE了一次。

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
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
int cnt;
map<string,int> id;
int ID(string s){
    if(!id.count(s)) id[s]=cnt++;
    return id[s];
}
const int maxn=1010;
struct Com{
    int price;
    int quality;
    Com(int p,int q):price(p),quality(q){}
};
int n,b;
vector<Com> comp[maxn];
bool ok(int q){
    int sum=0;
    for(int i=0;i<cnt;++i){
        int cheapest=b+1,m=(int)comp[i].size();
        for(int j=0;j<m;++j)
            if(comp[i][j].quality>=q) cheapest=min(cheapest,comp[i][j].price);
        if(cheapest==b+1) return false;
        sum+=cheapest;
        if(sum>b) return false;
    }
    return true;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&b);
        cnt=0;
        for(int i=0;i<n;++i) comp[i].clear();
        id.clear();
        int maxq=0;
        for(int i=0;i<n;++i){
            char type[30],name[30];
            int p,q;
            scanf("%s%s%d%d",type,name,&p,&q);
            maxq=max(maxq,q);
            comp[ID(type)].push_back(Com(p,q));
        }
        int L=0,R=maxq;
        while(L<R){
            int M=L+(R-L+1)/2;
            if(ok(M)) L=M;else R=M-1;
        }
        printf("%d\n",L);
    }
    return 0;
}

C：HDU 2335
首先对n处理，使之变为平面矩形的个数，再从1到sqrt(n)枚举求最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL inf=0x3f3f3f3f3f3f3f3f;
int main(){
    LL t,n;
    cin>>t;
    while(t--){
        cin>>n;
        n=(n+4)/5;
        LL ans=inf,last=inf,x=0,y=0;
        for(LL i=1;i*i<=n;++i){
            LL j=(n+i-1)/i,a=10*j+2,b=44*i+4,cur=a*b;
            if(cur<ans||(cur==ans&&abs(a-b)<last)) ans=cur,x=a,y=b,last=abs(a-b);
        }
        if(x<y) swap(x,y);
        cout<<x<<" X "<<y<<" = "<<ans<<endl;
    }
    return 0;
}

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

发表于 分类于 Disqus：

Rank 6。
就出了一道题，是2012年芝加哥大学邀请赛的题，感觉难度不小。
D：HDU 4260
给出汉诺塔当前状态，求移动到B上还需要几步。给出的状态是移动的最优解的中间状态，递归求解，倒着遍历字符串，判断当前完成了多少，用总步数减去已经完成的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<string>
using namespace std;
typedef long long LL;
LL a[65];
LL hanoi(char A,char B,char C,string s){
    LL ans=0;
    int cnt=1;
    while(s[(int)s.length()-cnt]==B) ans+=a[(int)s.length()-cnt]+1,++cnt;
    if(cnt>s.length()) return ans;
    if(cnt&1) ans+=hanoi(A,C,B,s.substr(0,s.length()-cnt));
    else ans+=hanoi(C,A,B,s.substr(0,s.length()-cnt));
    return ans;
}
int main(){
    for(int i=1;i<65;++i) a[i]=(a[i-1]<<1)+1;
    string s;
    while(cin>>s&&s!="X")
        cout<<a[s.length()]-hanoi('A','B','C',s)<<endl;
    return 0;
}

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

发表于 分类于 Disqus：

Rank 5。
2013年通化全国邀请赛的题。比赛时出了2道题，打完之后才知道杭电G++编译器有问题，D题同样的代码C++能AC，G++一直超时。一开始A题交了好久次才过罚 时好多，一着急就乱了，改一个地方就提交，这个必须改。
A：HDU 4493
给出12个月的工资，求平均薪水，貌似是因为数据大和浮点数精度问题WA了好几次，最后用long long过的。

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<cmath>
using namespace std;
typedef long long LL;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        LL sum=0;
        LL tmp1,tmp2;
        for(int i=0;i<12;++i){
            scanf("%I64d.%I64d",&tmp1,&tmp2);
            sum+=tmp1*100;
            sum+=tmp2;
        }
        sum=(LL)floor((double)sum/12.0+0.5);
        printf("$%I64d",sum/100);
        sum%=100;
        if(sum!=0){
            if(sum%10) printf(".%02I64d",sum);
            else printf(".%I64d",sum/10);
        }
        printf("\n");
    }
    return 0;
}

D：HDU 4496
判断连通块个数，倒着做一遍并查集，然后计数储存就好了。比赛时G++编译器超时，赛后用C++补过。

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

H：HDU 4597
博弈问题，有两堆牌，每次可以从堆顶或堆底拿一张，两人都足够聪明，求先手最大得分。DP解决，因为状态没找好，所以直接分类讨论了。赛后看了学长代码重写了一遍。

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
重写后的：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=22;
int n,a[maxn],b[maxn];
int d[maxn][maxn][maxn][maxn];
int dp(int l1,int r1,int l2,int r2,int sum){
    int& k=d[l1][r1][l2][r2];
    if(k!=-1) return k;
    if(l1<=r1){
        k=max(k,sum-dp(l1+1,r1,l2,r2,sum-a[l1]));
        k=max(k,sum-dp(l1,r1-1,l2,r2,sum-a[r1]));
    }
    if(l2<=r2){
        k=max(k,sum-dp(l1,r1,l2+1,r2,sum-b[l2]));
        k=max(k,sum-dp(l1,r1,l2,r2-1,sum-b[r2]));
    }
    return max(0,k);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        memset(d,-1,sizeof(d));
        cin>>n;
        int sum=0;
        for(int i=1;i<=n;++i) cin>>a[i],sum+=a[i];
        for(int i=1;i<=n;++i) cin>>b[i],sum+=b[i];
        cout<<dp(1,n,1,n,sum)<<endl;
    }
    return 0;
}


原代码：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=22;
const int inf=1<<30;
int d[maxn][maxn][maxn][maxn],a[maxn],b[maxn];
int dp(int i,int j,int i2,int j2){
    int &k=d[i][j][i2][j2];
    if(k!=-1) return k;
    if(!(i-i2)&&!(j-j2)) return k=0;
    if(!(i-i2)){
        if(j-j2==1) return k=b[j];
        return k=max(min(dp(i,j-2,i2,j2),dp(i,j-1,i2,j2+1))+b[j],min(dp(i,j,i2,j2+2),dp(i,j-1,i2,j2+1))+b[j2+1]);
    }
    if(!(j-j2)){
        if(i-i2==1) return k=a[i];
        return k=max(min(dp(i-2,j,i2,j2),dp(i-1,j,i2+1,j2))+a[i],min(dp(i-1,j,i2+1,j2),dp(i,j,i2+2,j2))+a[i2+1]);
    }
    if(i-i2==1&&j-j2==1) return k=max(a[i],b[j]);
    if(i-i2==1){
        int cur=0;
        cur=max(cur,min(dp(i-1,j-1,i2,j2),dp(i-1,j,i2,j2+1))+a[i]);
        {
            int ccur=inf;
            ccur=min(ccur,dp(i-1,j-1,i2,j2));
            ccur=min(ccur,dp(i,j-2,i2,j2));
            ccur=min(ccur,dp(i,j-1,i2,j2+1));
            cur=max(cur,ccur+b[j]);
        }
        {
            int ccur=inf;
            ccur=min(ccur,dp(i-1,j,i2,j2+1));
            ccur=min(ccur,dp(i,j-1,i2,j2+1));
            ccur=min(ccur,dp(i,j,i2,j2+2));
            cur=max(cur,ccur+b[j2+1]);
        }
        return k=cur;
    }
    if(j-j2==1){
        int cur=0;
        cur=max(cur,min(dp(i-1,j-1,i2,j2),dp(i,j-1,i2+1,j2))+b[j]);
        {
            int ccur=inf;
            ccur=min(ccur,dp(i-1,j-1,i2,j2));
            ccur=min(ccur,dp(i-1,j,i2+1,j2));
            ccur=min(ccur,dp(i-2,j,i2,j2));
            cur=max(cur,ccur+a[i]);
        }
        {
            int ccur=inf;
            ccur=min(ccur,dp(i-1,j,i2+1,j2));
            ccur=min(ccur,dp(i,j-1,i2+1,j2));
            ccur=min(ccur,dp(i,j,i2+2,j2));
            cur=max(cur,ccur+a[i2+1]);
        }
        return k=cur;
    }
    int cur=0;
    {
        int ccur=inf,ci=i-1;
        ccur=min(ccur,dp(ci-1,j,i2,j2));
        ccur=min(ccur,dp(ci,j-1,i2,j2));
        ccur=min(ccur,dp(ci,j,i2+1,j2));
        ccur=min(ccur,dp(ci,j,i2,j2+1));
        cur=max(cur,ccur+a[i]);
    }
    {
        int ccur=inf,cj=j-1;
        ccur=min(ccur,dp(i-1,cj,i2,j2));
        ccur=min(ccur,dp(i,cj-1,i2,j2));
        ccur=min(ccur,dp(i,cj,i2+1,j2));
        ccur=min(ccur,dp(i,cj,i2,j2+1));
        cur=max(cur,ccur+b[j]);
    }
    {
        int ccur=inf,ci2=i2+1;
        ccur=min(ccur,dp(i-1,j,ci2,j2));
        ccur=min(ccur,dp(i,j-1,ci2,j2));
        ccur=min(ccur,dp(i,j,ci2+1,j2));
        ccur=min(ccur,dp(i,j,ci2,j2+1));
        cur=max(cur,ccur+a[i2+1]);
    }
    {
        int ccur=inf,cj2=j2+1;
        ccur=min(ccur,dp(i-1,j,i2,cj2));
        ccur=min(ccur,dp(i,j-1,i2,cj2));
        ccur=min(ccur,dp(i,j,i2+1,cj2));
        ccur=min(ccur,dp(i,j,i2,cj2+1));
        cur=max(cur,ccur+b[j2+1]);

    }
    return k=cur;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        memset(d,-1,sizeof(d));
        int n;
        cin>>n;
        for(int i=1;i<=n;++i) cin>>a[i];
        for(int i=1;i<=n;++i) cin>>b[i];
        cout<<dp(n,n,0,0)<<endl;
    }
    return 0;
}

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

发表于 分类于 Disqus：

Rank 3。
这次的题是第七届浙江省省赛的题，出了6道，感觉还可以，第一次打组队，配合上稍有欠缺。
当时做题的细节记不清了，大体顺序还记得，开场我看B简单就先做了，CE一次WA一次。。
后来跟榜出了L和A，后来易神说K题类似欧拉回路，开始想K，我开始敲E题。出了E之后，易神过来写K，庄神和我看其他题，除了G太长其他的都看了。。我们感觉F有希 望，看出来是唯一分解和贪心了。易神K题样例没过，我去Debug，他和庄神一块看F。E提出了之后一直在搞F不过，中途看有人出G，就跟了。一直到结束没出F。。
A：ZOJ 3322
读入之后对比，没难度。

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<cstring>
#include<cctype>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int a,b,c;
        int x,y,z;
        scanf("%d%d%d%d%d%d",&a,&b,&c,&x,&y,&z);
        if(a!=x){
            if(a<x) printf("javaman\n");
            else printf("cpcs\n");
        }
        else if(b!=y){
            if(b<y) printf("javaman\n");
            else printf("cpcs\n");
        }
        else if(c==z) printf("same\n");
        else if(c<z) printf("javaman\n");
        else printf("cpcs\n");
    }
    return 0;
}

B：ZOJ 3323
读入之后，不是数字的输出。水题出现很大的失误，少头文件CE一次，忘记换行WA一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
const int maxn=30;
char s[maxn];
int main(){
    int t;
    scanf("%d",&t);
    getchar();
    while(t--){
        gets(s);
        int n=strlen(s);
        for(int i=0;i<n;++i)
            if(!isdigit(s[i])) putchar(s[i]);
        printf("\n");
    }
    return 0;
}

E：ZOJ 3326
月份和日子都是素数时能吃糖，求能吃糖的总天数。直接暴力出来的。一开始读错了题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
60
#include<cstdio>
using namespace std;
int mon[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};
int candy[0];
bool np[35]={1,1};
inline bool isrun(int y){
    return y%400==0||(y%4==0&&y%100!=0);
}
inline void pre(){
    for(int i=0;i<35;++i){
        if(!np[i]){
            for(int j=i*i;j<35;j+=i)
                np[j]=true;
        }
    }
    return;
}
int main(){
    pre();
    int t;
    scanf("%d",&t);
    while(t--){
        int cnt=0;
        int year1,mon1,day1,year2,mon2,day2;
        scanf("%d%d%d%d%d%d",&year1,&mon1,&day1,&year2,&mon2,&day2);
        bool flag=true;
        while(1){
            if(!flag) break;
            if(year1>year2) break;
            while(1){
                if(!np[mon1]){
                    if(!flag) break;
                    if(year1==year2&&mon1>mon2) break;
                    while(1){
                        if(year1==year2&&mon1==mon2&&day1>day2){ flag=false;break;}
                        if(!np[day1]) cnt++;
                        day1++;
                        if(day1>mon[isrun(year1)][mon1]){
                            day1%=mon[isrun(year1)][mon1];
                            break;
                        }
                    }
                    mon1++;
                }
                else {
                    mon1++;
                    day1=1;
                }
                if(mon1>12){
                    mon1%=12;
                    break;
                }

            }
            year1++;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

F：ZOJ 3327
后来大部分时间都在想这道题，想到唯一分解和贪心了，可是只是枚举了所有的二元变换，一直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
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
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<cstring>
using namespace std;
string s;
int a[4];
void resolve(char& c){
    switch(c) {
        case '1':break;
        case '2':++a[0];break;
        case '3':++a[1];break;
        case '4':a[0]+=2;break;
        case '5':++a[2];break;
        case '6':++a[0],++a[1];break;
        case '7':++a[3];break;
        case '8':a[0]+=3;break;
        case '9':a[1]+=2;break;
    }
    c='1';
    return;
}
bool make_up(char c){
    switch(c) {
        case '2':if(a[0]>=1){--a[0];return true;}break;
        case '3':if(a[1]>=1){--a[1];return true;}break;
        case '4':if(a[0]>=2){a[0]-=2;return true;}break;
        case '5':if(a[2]>=1){--a[2];return true;}break;
        case '6':if(a[0]>=1&&a[1]>=1){--a[0],--a[1];return true;}break;
        case '7':if(a[3]>=1){--a[3];return true;}break;
        case '8':if(a[0]>=3){a[0]-=3;return true;}break;
        case '9':if(a[1]>=2){a[1]-=2;return true;}break;
    }
    return false;
}
void ev(int pos){
    if(!pos&&s[pos]=='9'){
        s[pos]='0';
        cout<<1;
        return;
    }
    if(s[pos]!='9'){s[pos]+=1;return;}
    s[pos]='0';
    ev(pos-1);
    return;
}
int main(){
    int t;
    cin>>t;
    cin.get();
    while(t--){
        memset(a,0,sizeof(a));
        int pos=-1;
        s.resize(0);
        getline(cin,s);
        for(int i=0;i<(int)s.length();++i){
            if(s[i]!='0') continue;
            if(i!=(int)s.length()-1){
                ev((int)s.length()-1);
                cout<<s<<endl;
                goto END;
            }
            else{
                ev((int)s.length()-2);
                cout<<s<<endl;
                goto END;
            }
        }
        for(int i=(int)s.length()-1;i>=0;--i){
            bool flag=false;
            char c=s[i];
            resolve(s[i]);
            for(char j=c+1;j<='9';++j)
                if(make_up(j)){
                    s[i]=j;
                    pos=i;
                    flag=true;
                    break;
                }
            if(flag) break;
        }
        if(pos==-1) cout<<1;
        for(int i=(int)s.length()-1;i>pos;--i){
            for(char j='9';j>'1';--j)
                if(make_up(j)){
                    s[i]=j;
                    break;
                }
        }
        cout<<s<<endl;
    END:;
    }
    return 0;
}

G：ZOJ 3328
本场最水的一道题，就是n/2，四个多小时的时候，看有人过了，代码很短，跟的。。

1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
int main(){
    int n;
    while(cin>>n&&n)
        cout<<n/2<<endl;
    return 0;
}

H：ZOJ 3329
概率DP，比赛时没出，赛后补的。状态当前点数剩余步数的期望，将期望用 ** dp[i]=a[i]*dp[0]+b[i] ** 代换，然后递归求出a[i]和b[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
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=550;
double p[20],A[maxn],B[maxn];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(p,0,sizeof(p));
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        int n,k1,k2,k3,a,b,c;
        scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
        for(int i=1;i<=k1;++i)
            for(int j=1;j<=k2;++j)
                for(int k=1;k<=k3;++k)
                    if(a!=i||b!=j||c!=k) ++p[i+j+k];
        int sum=k1+k2+k3;
        p[0]=1.0/k1/k2/k3;
        for(int i=3;i<=sum;++i) p[i]/=k1*k2*k3;
        for(int i=n;i>=0;--i){
            A[i]=p[0],B[i]=1;
            for(int j=sum;j>=3;--j)
                A[i]+=p[j]*A[i+j],B[i]+=p[j]*B[i+j];
        }
        printf("%.15lf\n",B[0]/(1-A[0]));
    }
    return 0;
}

J：ZOJ 3331
比赛的时候看出来是个DP了，没想出来状态转移方程，赛后看学长代码才明白应该用当前任务编号和A、B两个机器的工作时间差作为状态。后来补了这道。

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<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
const int inf=0x3f3f3f3f;
int a[maxn],b[maxn],d[maxn][maxn*2];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(d,0x3f,sizeof(d));
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;++i) scanf("%d%d",&a[i],&b[i]);
        d[0][maxn]=0;
        for(int i=0;i<n;++i)
            for(int j=0;j<maxn*2;++j)
                if(j>maxn){
                    d[i+1][j-b[i]]=min(d[i+1][j-b[i]],d[i][j]+max(0,b[i]-(j-maxn)));
                    d[i+1][maxn+a[i]]=min(d[i+1][maxn+a[i]],d[i][j]+a[i]);
                }
                else{
                    d[i+1][maxn-b[i]]=min(d[i+1][maxn-b[i]],d[i][j]+b[i]);
                    d[i+1][j+a[i]]=min(d[i+1][j+a[i]],d[i][j]+max(0,a[i]-(maxn-j)));
                }
        int ans=inf;
        for(int i=0;i<maxn*2;++i) ans=min(ans,d[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}

K：ZOJ 3332
看官方报告，是个竞赛图的哈密顿路，我们是暴力过的。。

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
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
const int maxn=110;
bool g[maxn][maxn];
int cnt[2][maxn],n;
int road[maxn];
bool vis[maxn],find0;
bool pan(int i,int cur){
    road[cur]=i+1;
    if (cur==n) return find0=true;
    for (int j=0;j<n;j++){
        if (g[i][j]&&!vis[j]){
            vis[j]=true;
            if(pan(j,cur+1)) return true;
            vis[j]=false;
        }
    }
    return false;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(g,0,sizeof(g));
        memset(cnt,0,sizeof(cnt));
        memset(vis,0,sizeof(vis));
        scanf("%d",&n);
        int num=n*(n-1)/2;
        for(int i=0;i<num;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            g[u-1][v-1]=true;
        }
        find0=false;
        for (int i=0;i<n;i++){
            memset(vis,0,sizeof(vis));
            vis[i]=true;
            if(pan(i,1)) break;
        }
        if(find0){
            printf("%d",road[1]);
            for (int i=2;i<=n;++i)
                printf(" %d",road[i]);
            printf("\n");
        }
        else printf("impossible\n");
    }
    return 0;
}

L：ZOJ 3333
直接比大小就行，物品价格没有用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(b>c) printf("A\n");
        else printf("B\n");
    }
    return 0;
}

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