学步园

Codeforces Round #230 (Div. 2)

A，B

简单题

C

题意：

定义两个点为相连的，则：

1，两点间的欧式距离等于1，并且这两点的任意一个点都没有被锁上

2，如果A,B相连，B,C相连，那么A,C相连。

定义特殊点为距离坐标原点的欧式距离不超过n的整数点。

让你锁上一些点，使得任意特殊点不能和任意非特殊点相连。

求出锁得的最少的点。

n == 0,  ans = 1;

计算四分之一圆,然。乘以4，

#include <iostream>
using namespace std;
int main()
{
    long long n, i, j, part, nn;
    while(cin>>n) {
        if(n==0) {
            cout<<1<<endl;
            continue;
        }
        part = j = n;
        nn = n*n;
        for(i=1; i<n&&j>=i; ++i)
        if(nn < i*i + j*j) j--;
        else part++;
        cout<<part*4<<endl;
    }
    return 0;
}

直接用公式： ans = floor(n*sqrt(2))*4(n>0);

D

题目大意：给出一个3*3的矩阵，表示从i移动到j的代价，现在给出n，表示有n个碟子在1柱，需要移动到3柱，要求给出最小的花费。

汉诺塔只有两种移动方式。
1，把n-1个从a通过c移到b上，然后把第n个从l移到c上，最后把n-1个从b通过a移到c上。
2，把n-1个从a通过b移到c上，然后把第n个从a移到b上，然后把n-1个从c通过b移到a上，然后把第n个从b移到c上，最后把n-1个从a通过b移到c上。

DP 记忆化搜索

状态:dp[n][i][j][k]:把n个汉诺塔从i通过j移到k上所花费的最小耗能。

#include <iostream>
#include <algorithm>
using namespace std;
const long long inf = 1LL<<60;
int cost[4][4];
long long dp[50][4][4];

long long dfs(int n, int a, int c)
{
    if(n==0) return 0;
    if(dp[n][a][c] !=inf) return dp[n][a][c];
    int b = 6 - a - c;
    long long t, ans = inf;
    t = dfs(n-1,a,b) + cost[a][c] + dfs(n-1,b,c);
    ans = min(t, ans);
    t = 2*dfs(n-1,a,c) + cost[a][b] + dfs(n-1,c,a) + cost[b][c];
    ans = min(t, ans);
    dp[n][a][c] = ans;
    return ans;
}
int main()
{
    int i, j, k, n;
    for(i=1; i<=3; ++i)
        for(j=1; j<=3; ++j)
            cin>>cost[i][j];
    cin>>n;
    for(i=0; i<=n; ++i)
    for(j=1; j<=3; ++j)
    for(k=1; k<=3; ++k)
        dp[i][j][k] = inf;

    cout<<dfs(n,1,3)<<endl;
    return 0;
}

E

F[i]   Fibonacci数

A[i]  = F[i]*i^k

求 sum(A[i]) {0<i<=n} % (10^9+ 7) 的值

矩阵快速幂

弱菜还不会~~