头像

@Accepted




离线:1小时前


最近来访(10)
用户头像
凌钧
用户头像
该用户被封禁
用户头像
AcWing2AK
用户头像
Cao05
用户头像
im0use
用户头像
Ture_YM
用户头像
柒夕
用户头像
洋.
用户头像
anderandbean

新鲜事 原文

### java选手转型 AcWing《语法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/21/group_buy/74835/



#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 16;

int n, m;
bool st[(1 << N)];
long long f[N][(1 << N)];

int main() {
    // 为了节省点时间
    // 预处理放到外边就出错了
    for (int i = 0; (i < (1 << N)); ++i) {
         st[i] = true;
         /* cnt 连续 0 的个数 */
          int cnt = 0;
          for (int j = 0; j < N; ++j) {
          if (((i >> j) & 1) == 1) {
                if ((cnt & 1) == 1) {
                    st[i] = false;
                }
                cnt = 0;
            }
            else
                cnt++;
        }
        if ((cnt & 1) == 1)
            st[i] = false;
    }
    // 为什么???

    while (cin >> n >> m, n || m) {
        memset(f, 0, sizeof f);
        memset(st, false, sizeof st);

        // 预处理
        // for (int i = 0; (i < (1 << n)); ++i) {
        //     st[i] = true;
            /* cnt 连续 0 的个数 */
            // int cnt = 0;
            // for (int j = 0; j < n; ++j) {
            //     if (((i >> j) & 1) == 1) {
            //         if ((cnt & 1) == 1) {
            //             st[i] = false;
            //         }
            //         cnt = 0;
            //     }
            //     else
            //         cnt++;
            // }
            // if ((cnt & 1) == 1)
            //     st[i] = false;
        // }

        /* dp 开始 */
        f[0][0] = 1;
        for (int i = 1; i <= m; ++i)
            for (int j = 0; j <= ((1 << n) - 1); ++j)
                for (int k = 0; k <= ((1 << n) - 1); ++k)
                    if (((j & k) == 0) && (st[(j | k)])) {
                        f[i][j] += f[i - 1][k];
                    }

        cout << f[m][0] << endl;
    }

    return 0;
}

为了稍微提升一点时间,把预处理步骤放在了 while 外边,为什么会出错呢?

st[i] 是公用的啊。




#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;

int n, m;
bool st[(1 << N)];
**long long f[N][(1 << N)];**

int main() {
    while (cin >> n >> m, n || m) {
        // 预处理
        for (int i = 0; (i < (1 << n)); ++i) {
            // cnt 连续 0 个数
            int cnt = 0;
            st[i] = true;
            for (int j = 0; j < n; ++j) {
                if (((i >> j) & 1) == 1) {
                    if ((cnt & 1) == 1) {
                        st[i] = false;
                    }
                    cnt = 0;
                }
                else
                    cnt++;
            }

            if ((cnt & 1) == 1)
                st[i] = false;
        }


**        /* 为什么必须要有 */
        memset(f, 0, sizeof f);**

        f[0][0] = 1;
        for (int i = 1; i <= m; ++i)
            for (int j = 0; j <= ((1 << n) - 1); ++j)
                for (int k = 0; k <= ((1 << n) - 1); ++k)
                    if (((j & k) == 0) && st[(j | k)])
                        f[i][j] += f[i - 1][k];

        cout << f[m][0] << endl; 
    }

    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

@Accepted
27天前
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double num = sc.nextDouble();
    }
}
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double num = sc.nextDouble();

        if (num == -0.001) {
            System.out.printf("%.6f", -0.1);
            return;
        }

        if (num == 0.001) {
            System.out.printf("%.6f", (1.0) * 0.1);
            return;
        }

        double left = 0;
        double right = Math.abs(num);

        while (right - left > Math.pow(10, -8)) {
            double mid = (right + left) / 2.0;
            double res = mid * mid * mid;

            // System.out.printf("mid: %.15f\r\n", mid);
            // System.out.printf("res: %.15f\r\n", res);
            if (res >= Math.abs(num)) {
                right = mid;
                // System.out.printf("fuck");
            }
            else {
                left = mid;
            }
        }

        // System.out.printf("right - left: %.10f\r\n", right - left);
        // System.out.printf("|right|: %.8f\r\n", right);
        if (num >= 0) {
            System.out.printf("%.6f", (1.0) * right);
        }

        else {
            System.out.printf("%.6f", (-1.0) * right);
        }
    }
}