正文

第六届福建省大学生程序设计竞赛（FZU2213—FZU2221）

IP云
IP云V管理员/1 阅读
12/01
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

from:piaocoder

Common Tangents（两圆之间的公公切线）

题目链接：

http://acm.fzu.edu.cn/problem.php?pid=2213

解题思路：

告诉你两个圆的圆心与半径，要你找出他们的公共切线的个数。

套模板即可。

http://blog.csdn.net/piaocoder/article/details/41649089 

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

struct Point{

    double x,y;

    Point(double x = 0,double y = 0):x(x),y(y){} // 构造函数，方便代码编写

};

typedef Point Vector;  //从程序实现上，Vector只是Point的别名

struct Circle{

    Point c;

    double r;

    Circle(Point c,double r):c(c),r(r){}

    Point getPoint(double a){

        return Point(c.x+cos(a)*r,c.y+sin(a)*r);

    }

};

//返回切线的条数。-1表示无穷条切线

//a[i]和b[i]分别是第i条切线在圆A和圆B上的切点

int getTangents(Circle A,Circle B){

    int cnt = 0;

    if(A.r < B.r)

        swap(A,B);

    int d2 = (A.c.x-B.c.x)*(A.c.x-B.c.x)+(A.c.y-B.c.y)*(A.c.y-B.c.y);

    int rdiff = A.r-B.r;

    int rsum = A.r+B.r;

    if(d2 < rdiff*rdiff)

        return 0;       //内含

    if(d2==0 && A.r==B.r)

        return -1;      //无限条切线

    if(d2 == rdiff*rdiff){//内切，1条切线

        return 1;

    }

    //有外公切线

    cnt += 2;

    if(d2 == rsum*rsum){//一条公切线

        ++cnt;

    }

    else if(d2 > rsum*rsum){//两条公切线

        cnt += 2;

    }

    return cnt;

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        Point p1,p2;

        double r1,r2;

        scanf("%lf%lf%lf",&p1.x,&p1.y,&r1);

        Circle c1(p1,r1);

        scanf("%lf%lf%lf",&p2.x,&p2.y,&r2);

        Circle c2(p2,r2);

        printf("%d\n",getTangents(c1,c2));

    }

    return 0;

}

Knapsack problem（动态规划）

题目链接：

http://acm.fzu.edu.cn/problem.php?pid=2214

解题思路：

题目大意：

给你一个背包，容量为10^9，物品个数为500，价值和小于5000，求最大价值。

算法思想：

因为容量太大，所以不能按0-1背包问题去求解。注意到物品个数较小，而且价值和最大只有5000，所以可以逆向思维，求得对应价值下最小的重量，即dp[i]表示总价值为i的最小重量是多少，则dp[j] = min(dp[j] , dp[j-val[i]]+vol[i]);最后从sum（物品总价值开始判断）开始，找到第一个小于等于b（容量）的v即可 

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

int dp[5005];

int w[505],v[505];

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        int n,b;

        int sum = 0;

        scanf("%d%d",&n,&b);

        for(int i = 0; i < n; ++i){

            scanf("%d%d",&w[i],&v[i]);

            sum += v[i];

        }

        for(int i = 1; i <= sum; ++i)

            dp[i] = INF;

        dp[0] = 0;

        for(int i = 0; i < n; ++i){

            for(int j = sum; j >= v[i]; --j){

                if(dp[j-v[i]] != INF){

                    dp[j] = min(dp[j],dp[j-v[i]]+w[i]);

                }

            }

        }

        for(int i = sum; i >= 0; --i){

            if(dp[i] <= b){

                printf("%d\n",i);

                break;

            }

        }

    }

    return 0;

}

Simple Polynomial Problem（中缀表达式）

题目链接：

http://acm.fzu.edu.cn/problem.php?pid=2215

解题思路：

中缀表达式求值，数字栈存的是多项式。 

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

struct Poly{

    ll a[1005];

    Poly operator + (const Poly &p) const{

        Poly tmp = {0};

        for(int i = 0; i < 1005; ++i){

            tmp.a[i] = (a[i]+p.a[i])%1000000007;

        }

        return tmp;

    }

    Poly operator * (const Poly &p) const{

        Poly tmp = {0};

        for(int i = 0; i < 1005; ++i){

            if(a[i] == 0)

                continue;

            for(int j = 0; j < 1005; ++j){

                if(p.a[j] == 0)

                    continue;

                tmp.a[i+j] += a[i]*p.a[j];

                tmp.a[i+j] %= 1000000007;

            }

        }

        return tmp;

    }

}pstk[1005];

char ostk[1005] = {'#'};

int ptop,otop,pri[350];

char str[1005];

void push(char op){

    if(ostk[otop]=='#' && op=='#')

        return;

    if(ostk[otop]=='(' && op==')'){

        --otop;

        return;

    }

    if(pri[ostk[otop]]<pri[op] || ostk[otop]=='('){

        ostk[++otop] = op;

        return;

    }

    if(ostk[otop--] == '+'){

        Poly p = pstk[ptop]+pstk[ptop-1];

        ptop -= 2;

        pstk[++ptop] = p;

    }else{

        Poly p = pstk[ptop]*pstk[ptop-1];

        ptop -= 2;

        pstk[++ptop] = p;

    }

    push(op);

}

void output(Poly &p){

    int i = 1000;

    while(i>=0 && p.a[i] == 0)

        --i;

    if(i == -1){

        puts("0");

        return;

    }

    for(int j = i; j >= 0; --j){

        printf("%lld",p.a[j]);

        if(j)

            putchar(' ');

    }

    putchar('\n');

}

int main(){

    pri['+'] = 2; pri['*'] = 3;

    pri['('] = 4; pri[')'] = 1;

    pri['#'] = 1;

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%s",str);

        ptop = 0; otop = 1;

        for(int i = 0; str[i]; ++i){

            if(str[i]>='0' && str[i]<='9'){

                Poly p = {0};

                p.a[0] = str[i]-'0';

                pstk[++ptop] = p;

            }else if(str[i]=='x'){

                Poly p = {0};

                p.a[1] = 1;

                pstk[++ptop] = p;

            }else{

                push(str[i]);

            }

        }

        push('#');

        output(pstk[ptop]);

    }

    return 0;

}

The Longest Straight

题目链接：

http://acm.fzu.edu.cn/problem.php?pid=2216

解题思路：

pre[i]代表数字i的前面0的总数目， 对于每个i找出符合条件的j ，使得i-j之间有恰好有m个0，然后更新答案ans。 

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int N = 100005;

int a[N],pre[N];

void solve(int n,int m){

    for(int i = 1; i <= n; ++i)

        pre[i] = pre[i-1]+(!a[i]);

    int ans = 0;

    int j = 1;

    for(int i = 1; i <= n; ++i){

        for(; j <= n; ++j){

            if(pre[j]-pre[i-1] > m)

                break;

        }

        if(j-i > ans){

            ans = j-i;

        }

    }

    printf("%d\n",ans);

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        memset(a,0,sizeof(a));

        int x,n,m;

        scanf("%d%d",&n,&m);

        int k = 0;

        for(int i = 0; i < n; ++i){

            scanf("%d",&x);

            if(!x) k++;

            a[x] = 1;

        }

        solve(m,k);

    }

    return 0;

}

Simple String Problem（状态压缩dp）

题目链接：

http://acm.fzu.edu.cn/problem.php?pid=2218

解题思路：

题目大意：

一个长为n(n<=2000)的字符串，由前k(k<=16)个小写字母组成，求两段子串A和B，A和B中间没有共用的字母类型，求len(A)*len(B)的最大值。

算法思想：

二进制状态压缩，每一位的状态表示第i个字母存在状态，n^2的时可以枚举出所有子串的状态和长度。然后每次与（1<<k -1)异或就是不含相同的子串状态。但是不能直接对每一种状态枚举他的子集和异或值，这样太大了，肯定会超时，因此我们可以用dp[tmp]表示tmp状态所有子集的最大长度。

先状态转移一下，最后遍历所有的状态和其异或状态就可以更新出答案。 

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int N = 2005;

char str[N];

int dp[(1<<16)+10];

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        int n,m;

        scanf("%d%d",&n,&m);

        scanf("%s",str);

        memset(dp,0,sizeof(dp));

        for(int i = 0; i < n; ++i){

            int tmp = 0;

            for(int j = i; j < n; ++j){

                tmp |= 1<<(str[j]-'a');

                dp[tmp] = max(dp[tmp],j-i+1);

            }

        }

        int len = 1<<m;

        for(int i = 0; i < len; ++i){

            for(int j = 0; j < m; ++j){

                if((1<<j) & i)

                    dp[i] = max(dp[i],dp[i^(1<<j)]);

            }

        }

        int ans = 0;

        for(int i = 0; i < len; ++i){

            ans = max(ans,dp[i]*dp[(len-1)^i]);

        }

        printf("%d\n",ans);

    }

    return 0;

}

StarCraft（哈夫曼树+优先队列）

题目链接：

http://acm.fzu.edu.cn/problem.php?pid=2219

解题思路：

类似于哈夫曼树的合并方式，对于当个农民（工蜂）来说，算上分裂技能，建造是不断两两并行的，建造时间越小，合并的价值就越小。合并后的时间去被合并两者的较大值+K。初始农民的数量就是合并的终点。


然后问题就可以化简为，给你一堆数字，每次把次小值+k，再删除当前最小值，直到剩下m个数字。
使用优先队列求解，将默认排序的大根堆，改成小根堆即可。 

#include <iostream>

#include <cstdio>

#include <queue>

using namespace std;

priority_queue<int,vector<int>,greater<int> > q;

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        int x,n,m,k;

        scanf("%d%d%d",&n,&m,&k);

        for(int i = 0; i < n; ++i){

            scanf("%d",&x);

            q.push(x);

        }

        while(n > m){

            q.pop();

            q.push(q.top()+k);

            q.pop();

            --n;

        }

        while(q.size() != 1)

            q.pop();

        printf("%d\n",q.top());

        q.pop();

    }

    return 0;

}

Defender of Argus（优先队列）

题目链接：

http://acm.fzu.edu.cn/problem.php?pid=2220

解题思路：

类似于炉石传说中的“ 奥古斯守卫者 ”，不断选取最优解即可 

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int N = 100005;

int n,k;

int a[N],l[N],r[N];

bool vis[N];

struct node{

    int l,r,val;

    node(int _l,int _r):l(0),r(0){

        l = _l;

        r = _r;

        val = a[_l]+a[_r];

    }

    bool operator < (const node& no) const{

        return val < no.val;

    }

};

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&k);

        for(int i = 1; i <= n; ++i)

            scanf("%d",&a[i]);

        if(n == 0){

            if(k == 0 || k == 1)

                printf("0\n");

            else

                printf("%d\n",4+(k-2)*5);

            continue;

        }

        if(n == 1){

            printf("%d\n",a[1]+1+(k-1)*5);

            continue;

        }

        memset(vis,false,sizeof(vis));

        for(int i = 1; i <= n; ++i){

            l[i] = i-1;

            r[i] = i+1;

        }

        r[0] = 1;

        l[n+1] = n;

        priority_queue<node> q;

        for(int i = 1; i < n; ++i)

            q.push(node(i,i+1));

        bool put = false;

        int sum = 0,last = n;

        while(!q.empty() && k > 0){

            node cur = q.top(); q.pop();

            if(cur.val <= 3 && put == true)

                break;

            int ll = cur.l,rr = cur.r;

            if(vis[ll] || vis[rr])

                continue;

            sum += (a[ll]+a[rr]+2);

            last -= 2;

            --k;

            vis[ll] = true; vis[rr] = true;

            int _l = l[ll], _r = r[rr];

            l[_r] = _l;

            r[_l] = _r;

            put = true;

            if(_l!=0 && _r!= n+1)

                q.push(node(_l,_r));

        }

        if(k>0 && last==1 && a[r[0]]>3){

            sum += a[r[0]] + 2;

            --k;

        }

        sum += k*5;

        printf("%d\n",sum);

    }

    return 0;

}

RunningMan

题目链接：

http://acm.fzu.edu.cn/problem.php?pid=2221

解题思路：

将跑男n均分为3份，取其中较小两份cnt1,cnt2，如果m>=cnt1+cnt2+2;则跑男不能一定获胜，反之则能。 

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        int n,m;

        scanf("%d%d",&n,&m);

        int cnt1 = n/3;

        n -= cnt1;

        int cnt2 = n/2;

        if(cnt1+cnt2+2 <= m)

            puts("No");

        else

            puts("Yes");

    }

    return 0;

}

相关阅读

目录[+]