HDU-ACM“菜鸟先飞”冬训系列赛—

Problem A

题意

一对兔子每月生一对兔子，兔子在\(m\)月后成熟，问\(d\)月后有多少兔子

分析

可以发现，第i月的兔子数量取决于第i-1月与i-m月，故

\(a[i]=a[i-1]+a[i-m],a[0]=1\)

然后还需要高精度（捂脸），于是找了个高精度板子就好了

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cassert>

#include<cstdio>

#include<vector>

#include<string>

#include<map>

#include<set>

using std::cin;

using std::max;

using std::cout;

using std::endl;

using std::map;

using std::string;

using std::istream;

using std::ostream;

#define sz(c) (int)(c).size()

#define all(c) (c).begin(), (c).end()

#define iter(c) decltype((c).begin())

#define cls(arr,val) memset(arr,val,sizeof(arr))

#define cpresent(c, e) (find(all(c), (e)) != (c).end())

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define fork(i, k, n) for (int i = (int)k; i <= (int)n; i++)

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)

#define pb(e) push_back(e)

#define mp(a, b) make_pair(a, b)

struct BigN {

    typedef unsigned long long ull;

    static const int Max_N = 2010;

    int len, data[Max_N];

    BigN() { memset(data, 0, sizeof(data)), len = 0; }

    BigN(const int num) {

        memset(data, 0, sizeof(data));

        *this = num;

    }

    BigN(const char *num) {

        memset(data, 0, sizeof(data));

        *this = num;

    }

    void clear() { len = 0, memset(data, 0, sizeof(data)); }

    BigN& clean(){ while (len > 1 && !data[len - 1]) len--;  return *this; }

    string str() const {

        string res = "";

        for (int i = len - 1; ~i; i--) res += (char)(data[i] + '0');

        if (res == "") res = "0";

        res.reserve();

        return res;

    }

    BigN operator = (const int num) {

        int j = 0, i = num;

        do data[j++] = i % 10; while (i /= 10);

        len = j;

        return *this;

    }

    BigN operator = (const char *num) {

        len = strlen(num);

        for (int i = 0; i < len; i++) data[i] = num[len - i - 1] - '0';

        return *this;

    }

    BigN operator + (const BigN &x) const {

        BigN res;

        int n = max(len, x.len) + 1;

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

            int c = data[i] + x.data[i] + g;

            res.data[res.len++] = c % 10;

            g = c / 10;

        }

        return res.clean();

    }

    BigN operator * (const BigN &x) const {

        BigN res;

        int n = x.len;

        res.len = n + len;

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

            for (int j = 0, g = 0; j < n; j++) {

                res.data[i + j] += data[i] * x.data[j];

            }

        }

        for (int i = 0; i < res.len - 1; i++) {

            res.data[i + 1] += res.data[i] / 10;

            res.data[i] %= 10;

        }

        return res.clean();

    }

    BigN operator * (const int num) const {

        BigN res;

        res.len = len + 1;

        for (int i = 0, g = 0; i < len; i++) res.data[i] *= num;

        for (int i = 0; i < res.len - 1; i++) {

            res.data[i + 1] += res.data[i] / 10;

            res.data[i] %= 10;

        }

        return res.clean();

    }

    BigN operator - (const BigN &x) const {

        assert(x <= *this);

        BigN res;

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

            int c = data[i] - g;

            if (i < x.len) c -= x.data[i];

            if (c >= 0) g = 0;

            else g = 1, c += 10;

            res.data[res.len++] = c;

        }

        return res.clean();

    }

    BigN operator / (const BigN &x) const {

        BigN res, f = 0;

        for (int i = len - 1; ~i; i--) {

            f *= 10;

            f.data[0] = data[i];

            while (f >= x) {

                f -= x;

                res.data[i]++;

            }

        }

        res.len = len;

        return res.clean();

    }

    BigN operator % (const BigN &x) {

        BigN res = *this / x;

        res = *this - res * x;

        return res;

    }

    BigN operator += (const BigN &x) { return *this = *this + x; }

    BigN operator *= (const BigN &x) { return *this = *this * x; }

    BigN operator -= (const BigN &x) { return *this = *this - x; }

    BigN operator /= (const BigN &x) { return *this = *this / x; }

    BigN operator %= (const BigN &x) { return *this = *this % x; }

    bool operator <  (const BigN &x) const {

        if (len != x.len) return len < x.len;

        for (int i = len - 1; ~i; i--) {

            if (data[i] != x.data[i]) return data[i] < x.data[i];

        }

        return false;

    }

    bool operator >(const BigN &x) const { return x < *this; }

    bool operator<=(const BigN &x) const { return !(x < *this); }

    bool operator>=(const BigN &x) const { return !(*this < x); }

    bool operator!=(const BigN &x) const { return x < *this || *this < x; }

    bool operator==(const BigN &x) const { return !(x < *this) && !(x > *this); }

    friend istream& operator >> (istream &in, BigN &x) {

        string src;

        in >> src;

        x = src.c_str();

        return in;

    }

    friend ostream& operator << (ostream &out, const BigN &x) {

        out << x.str();

        return out;

    }

}A[101];

inline void work(int m,int d) {

    R(i,0,m) A[i]=i+1;

    F(i,m,d) A[i]=A[i-1]+A[i-m];

    //A[2]=A[1]+A[3]+(A[3]+A[1]-A[0])*(A[1]-A[0])/(A[3]+1);

}

int main() {

    std::ios::sync_with_stdio(false);

    int m,d;

    while (scanf("%d %d",&m,&d),m+d) {

        work(m,d);

        cout<<A[d]<<endl;

    }

    return 0;

}

Problem C

题意

在n*m的图中有B个障碍物，问从(1,1)->(n,m)的最短路径条数

分析

引用一下ChinaCzy的解释

//模拟+递推，感觉这种题不能称之为动态规划，只能叫递推因为每个点只调用了一次，不存在所谓的转移

//题意是从起点到终点，有多少种不同的走法，图中有些路有障碍

//注意到规模是MN <= 1000000,所以直接模拟就得了，数组嘛不能开成二维的会MLE

//把二维的坐标转化成1维的，这样就开的下了，数组的每个位存放的是十字路口的点，记录走到当前点有多少种不同的走法

//X,Y这两个BOOL型数组，记录的是当前这条路是否被阻碍了，每个点左下方都对应着2条路，分别用X,Y来存放，这样对应关系会清晰些

//至于哪条路被堵，这个得自己画个图琢磨琢磨，一开始我搞错了，WA了1次

//最坏情况是10000002+1..所以得开到100W,这样还真蛋疼，初始化的时候慢了好多

代码

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <string>

#include <map>

#include <queue>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

int m,n,num,xx,yy,aa,bb;

bool x[2002000],y[2002000];

ll a[2002000];

int turn(int x,int y) { return x*(n+1)+y; }

int main()

{

    while(scanf("%d %d",&m,&n),m*n)

    {

        mem(x,0);mem(y,0);mem(a,0);

        scanf("%d",&num);

        F(i,1,num)

        {

            scanf("%d %d %d %d",&xx,&yy,&aa,&bb);

            for(int i=xx;i<xx+aa;++i)for(int j=yy;j<yy+bb;++j)

            {

                if(yy+bb-1>j) y[turn(i,j)]=1;

                if(xx+aa-1>i) x[turn(i,j)]=1;

            }

        }

        F(i,1,n) a[i]=1;

        F(i,1,m) a[i*(n+1)]=1;

        F(i,1,m) F(j,1,n)

        {

            if(x[turn(i,j)]&&y[turn(i,j)]) continue;

            a[turn(i,j)]=(y[turn(i,j)]?0:a[turn(i-1,j)]) + (x[turn(i,j)]?0:a[turn(i,j-1)]);

        }

        printf("%lld\n",a[turn(m,n)]);

    }

    return 0;

}

Problem D

题意

给出一张图（森林），判断最大深度与宽度，若有环或一个顶点上有大于1条边相连则\(Invalid\)

分析

DFS一遍即可

代码

#include <vector>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

vector<int> forest[105];

int width[105];

bool visited[105], isloop;

int endPoints[105];

int W, D;

int vertex, edges;

void DFS(int start, int level){

    if (visited[start]) {

        isloop = false;

        return;

    }

    visited[start] = true;

    if (level > D) D = level;

    width[level] ++;

    if (width[level] > W) W = width[level];

    for(int i = 0 ; i < forest[start].size(); i++){

        if (!isloop) return;

        int v = forest[start][i];

        DFS(v, level+1);

    }

}

int main(){

    while (1) {

        cin >> vertex >> edges;

        if (vertex == 0) break;

        W = 0;

        D = 0;

        memset(width, 0, sizeof(width));

        memset(visited, false, sizeof(visited));

        memset(endPoints, 0, sizeof(endPoints));

        memset(forest, 0, sizeof(forest));

        isloop = true;

        if (edges >= vertex) isloop = false;

        int a,b;

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

            cin >> a >> b;

            forest[a].push_back(b);

            endPoints[b] ++;

        }

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

            if (endPoints[i] == 0) {

                DFS(i, 0);

            }

        }

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

            if (!visited[i]) isloop = false;

        }

        if (!isloop) cout << "INVALID" << endl;

        else cout << D << " " << W << endl;

    }

    return 0;

}

Problem E

题意

问匹配串数目，A与T，C与G配对

分析

\(n\)小于100，直接\(O(n^2)\)比较

Problem F（BFS)

传送门

题意

给出\(n\)台主机，\(m\)条路径，目标主机是\(t\),问到\(t\)的路径且交换不大于\(10\)次的最短路径长度

分析

一个简单BFS，注意条件，详情见代码

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <string>

#include <map>

#include <queue>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

const int inf=0x3f3f3f3f;

int ans,n,m,target,u,v,value,mp[1010][1010],vis[1010][1010];

struct node

{

    int num,value,depth;

    node(int _p, int _v,int _dep) :num(_p), value(_v),depth(_dep){}//复制构造函数

    node(){}

    bool operator<(const node &p)const

    {

        return value>p.value;

    }

}point;

void bfs()

{

    priority_queue<node>q;

    q.push(node(0,0,0));

    while(!q.empty())

    {

        point=q.top();q.pop();

        if(point.depth<=10&&point.num==target)

        {

            ans=min(ans,point.value);

        }

        R(i,0,n)

        {

            if(mp[point.num][i]&&vis[point.num][i]==0)

            {

                vis[point.num][i]=vis[i][point.num]=1;

                q.push(node(i,point.value+mp[point.num][i],point.depth+1));

            }

        }

    }

}

int main()

{

    while(scanf("%d %d %d",&n,&m,&target),n+m+target)

    {

        mem(vis,0);mem(mp,0);

        F(i,1,m)

        {

            scanf("%d %d %d",&u,&v,&value);

            mp[u][v]=mp[v][u]=value;

        }

        vis[0][0]=1;ans=inf;

        bfs();

        if(ans!=inf) printf("%d\n",ans);else puts("no");

    }

    return 0;

}

Problem G

题意略，直接模拟即可

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <string>

#include <map>

#include <queue>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

int t,n,num,ret;

int main()

{

    for(scanf("%d",&t);t--;)

    {

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

        ret=(int)sqrt(num);

        if(ret*ret==num)

        {

            if(ret&1) {printf("%d %d\n",1+(n-ret)/2,ret+(n-ret)/2);continue;}

            else { printf("%d %d\n",ret+(n+1-ret)/2,1+(n-ret+1)/2);continue; }

        }

        else

        {

            int low=(int)sqrt(num),high=low+1,x,y;

            if(high&1)

            {

                if(num<=(high*high-high+1))

                {

                    x=1+high*high-high+1-num,y=1;

                    printf("%d %d\n",x+(n-high)/2,y+(n-high)/2);

                    continue;

                }

                else

                {

                    x=1,y=1+num-(high*high-high+1);

                    printf("%d %d\n",x+(n-high)/2,y+(n-high)/2);

                    continue;

                }

            }

            else

            {

                 if(num<=(high*high-high+1))

                {

                    x=num-(low*low),y=high;

                    printf("%d %d\n",x+(n-high+1)/2,y+(n-high+1)/2);

                    continue;

                }

                else

                {

                    x=high,y=1+high*high-num;

                    printf("%d %d\n",x+(n-high+1)/2,y+(n-high+1)/2);

                    continue;

                }

            }

        }

    }

    return 0;

}

巴特西

HDU-ACM“菜鸟先飞”冬训系列赛——第9场