dpkun

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个月前

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;
}
};


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;
}
}
};


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;
}