头像

dpkun

正在刷《挑战程序设计竞赛》中全部习题,详情见分享(第一章[1/1], 第二章[70/70], 第三章[23/102], 第四章[0/82])


访客:16283

离线:2小时前


活动打卡代码 LeetCode 6. Z 字形变换

dpkun
2个月前
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        int w = numRows * 2 - 2;
        int len = s.length();
        string ans;
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < len; j += w) {
                if (j + i < len) {
                    ans += s[j + i];
                }
                if (0 < i && i < numRows - 1) {
                    int pos = j + w - i;
                    if (pos < len) {
                        ans += s[pos];
                    }
                }
            }
        }
        return ans;
    }
};


新鲜事 原文

dpkun
2个月前
这里是Ac博吗?


活动打卡代码 LeetCode 9. 回文数

dpkun
2个月前
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        long long xx = x;
        long long y = 0;
        while (xx) {
            y *= 10;
            y += xx % 10;
            xx /= 10;
        }
        return x == y;
    }
};


活动打卡代码 LeetCode 7. 整数反转

dpkun
2个月前
class Solution {
public:
    int reverse(int xx) {
        long long x = xx;
        int sg = 1;
        if (x < 0) {
            sg = -1;
            x = -x;
        }
        long long res = 0;
        while (x) {
            res *= 10;
            res += x % 10;
            x /= 10;
        }
        res *= sg;
        long long w = 1LL << 31;
        if (-w <= res && res <= w - 1) {
            return res;
        } else {
            return 0;
        }
    }
};


活动打卡代码 LeetCode 1. 两数之和

dpkun
2个月前
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        int n = (int)nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    ans.push_back(i);
                    ans.push_back(j);
                    return ans;
                }

            }
        }
        return ans;
    }
};



dpkun
3个月前

题目链接

Physics Experiment POJ - 3684

思路

$$
弹性碰撞问题\\
1.每个球都相当于从高度为h处下落,原因是第i(i 从 0 开始)个球的高度为h+i × 2 × r,\\
下边有i个球,因为下边每有一个球,都相当于下落的距离减少2×r.\\
2.先当r为0求完后再把高度加回去
$$

时间复杂度

$$
O(Nlog(N))
$$

代码

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;


vector<double> vec;

int g = 10;

double gao(double h, int t) {
    if (t <= 0) {
        return h;
    }
    double t1 = sqrt(2.0 * h / g);
    int k = t / t1;
    if (k & 1) {
        double d = k * t1 + t1 - t;
        return h - g * d * d / 2;
    } else {
        double d = t - k * t1;
        return h - g * d * d / 2;
    }
}

int main() {
    int T;
    scanf("%d", &T);// don't forget &
    while (T--) {
        int n, h, r, t;
        scanf("%d%d%d%d", &n, &h, &r, &t);// don't forget &
        vec.resize(n);
        for (int i = 0; i < n; i++) {
            vec[i] = gao(h, t - i);
        }
        sort(vec.begin(), vec.end());
        for (int i = 0; i < n; i++) {
            printf("%.2f%c", vec[i] + 2.0 * i * r / 100, " \n"[i == n - 1]);
        }
    }

    return 0;
}





dpkun
3个月前

题目链接

EXTENDED LIGHTS OUT POJ - 1222

思路

$$
反转问题,枚举第一行的情况,第一行确定,整个反转也就确定了
$$

时间复杂度

$$
O(2^N*M * N)
$$

代码

#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 20;
int a[MAXN][MAXN], b[MAXN][MAXN], c[MAXN][MAXN];
int n, m;

void gao(int x, int y) {
    b[x][y] ^= 1;
    b[x + 1][y] ^= 1;
    b[x - 1][y] ^= 1;
    b[x][y - 1] ^= 1;
    b[x][y + 1] ^= 1;
}

int check(int x) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            b[i][j] = a[i][j];
            c[i][j] = 0;
        }
    }
    int cnt = 0;
    for (int i = m - 1; i >= 0; i--) {
        if ((x >> i) & 1) {
            gao(1, i + 1);
            c[1][i + 1] = 1;
            cnt++;
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (b[i - 1][j] == 1) {
                gao(i, j);
                c[i][j] = 1;
                cnt++;
            }
        }
    }
    for (int j = 1; j <= m; j++) {
        if (b[n][j] == 1) {
            return INF;
        }
    }
    return cnt;
}


int main() {

    n = 5, m = 6;
    int T;
    scanf("%d", &T);// don't forget &
    for (int kase = 1; kase <= T; kase++) {
         for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);// don't forget &
            }
        }
        int ans1 = 0, ans2 = INF;
        for (int i = 0; i < (1 << m); i++) {
            int num = check(i);
            if (num < ans2) {
                ans2 = num;
                ans1 = i;
            }
        }
        printf("PUZZLE #%d\n", kase);
        if (ans2 == INF) {
            puts("IMPOSSIBLE");
        } else {
            check(ans1);
            for (int i = 1; i <= n; i++) { 
                for (int j = 1; j <= m; j++) {
                    printf("%d%c", c[i][j], " \n"[j == m]);
                }
            }
        }
    }

    return 0;
}





dpkun
3个月前

题目链接

The Water Bowls POJ - 3185

思路

$$
反转问题, 第一个反转与否决定全部
$$

时间复杂度

$$
O(N)
$$

代码

#include <cstdio>
#include <algorithm>
using namespace std;

int a[25];
int b[25];

void f(int x) {
    b[x - 1] ^= 1;
    b[x] ^= 1;
    b[x + 1] ^= 1;
}

int gao(int x) {
    int cnt = 0;
    for (int i = 1; i <= 20; i++) {
        b[i] = a[i];
    }
    if (x == 1) {
        f(1);
        cnt++;
    }
    for (int i = 2; i <= 20; i++) {
        if (b[i - 1] == 1) {
            f(i);
            cnt++;
        }
    }
    if (b[20] == 1) {
        return 20;
    } else {
        return cnt;
    }

}

int main() {
    for (int i = 1; i <= 20; i++) {
        scanf("%d", &a[i]);// don't forget &
    }
    printf("%d", min(gao(0), gao(1)));
    return 0;
}




dpkun
3个月前

题目链接

Fliptile POJ - 3279

思路

$$
反转问题,枚举第一行的情况,第一行确定,整个反转也就确定了
$$

时间复杂度

$$
O(2^N*M * N)
$$

代码

#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 20;
int a[MAXN][MAXN], b[MAXN][MAXN], c[MAXN][MAXN];
int n, m;

void gao(int x, int y) {
    b[x][y] ^= 1;
    b[x + 1][y] ^= 1;
    b[x - 1][y] ^= 1;
    b[x][y - 1] ^= 1;
    b[x][y + 1] ^= 1;
}

int check(int x) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            b[i][j] = a[i][j];
            c[i][j] = 0;
        }
    }
    int cnt = 0;
    for (int i = m - 1; i >= 0; i--) {
        if ((x >> i) & 1) {
            gao(1, i + 1);
            c[1][i + 1] = 1;
            cnt++;
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (b[i - 1][j] == 1) {
                gao(i, j);
                c[i][j] = 1;
                cnt++;
            }
        }
    }
    for (int j = 1; j <= m; j++) {
        if (b[n][j] == 1) {
            return INF;
        }
    }
    return cnt;
}


int main() {

    scanf("%d%d", &n, &m);// don't forget &
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);// don't forget &
        }
    }
    int ans1 = 0, ans2 = INF;
    for (int i = 0; i < (1 << m); i++) {
        int num = check(i);
        if (num < ans2) {
            ans2 = num;
            ans1 = i;
        }
    }

    if (ans2 == INF) {
        puts("IMPOSSIBLE");
    } else {
        check(ans1);
        for (int i = 1; i <= n; i++) { 
            for (int j = 1; j <= m; j++) {
                printf("%d%c", c[i][j], " \n"[j == m]);
            }
        }
    }
    return 0;
}




dpkun
3个月前

题目链接

Face The Right Way POJ - 3276

思路

$$
反转问题,用到前缀和优化
$$

时间复杂度

$$
O(N^2)
$$

代码

#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 1e4 + 10;

char str[10];
int a[MAXN];
int b[MAXN];
int n;

int gao(int x) {
    memset(b, 0, sizeof b);
    int cnt = 0;
    for (int i = 1; i + x - 1 <= n; i++) {
        b[i] += b[i - 1];
        int w = a[i] + b[i];
        if (w & 1) {
            cnt++;
            b[i]++;
            b[i + x]--;
        }
    }
    for (int i = n - x + 2; i <= n; i++) {
        b[i] += b[i - 1];
        int w = a[i] + b[i];
        if (w & 1) {
            return n + 1;
        }
    }
    return cnt;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", str);
        if (str[0] == 'B') {
            a[i]++;
        }
    }

    int ans1 = 1, ans2 = n + 1;
    for (int i = 1; i <= n; i++) {
        int tmp = gao(i);
        if (tmp < ans2) {
            ans1 = i;
            ans2 = tmp;
        }
    }
    printf("%d %d", ans1, ans2);
    return 0;
}