|
|
題目大意：
給出一個序列，長度為N，均為正數。
找出一段連續的區間，此區間的平均值最大，長度必須大于F。
好像還是有點實際用途的，這個問題。
看完題之后，基本上就知道是做不出來的了。只想得到那種最簡單的O(N^2)的解法，但是N = 100,000。這種解法必然超時。
在網上搜了兩個解題報告，發現此題的解法相當牛逼！
兩種解法是完全不同類型的。
二分法
我們可以比較容易得出答案的最大值和最小值，即為序列中最大元素和最小元素。
二分法的關鍵在于判斷“一個可能的解跟正確答案相比是大了還是小了”。網上給的方法是：
如果要判斷val這個解，那就讓序列里所有元素的值都減去val。
然后試圖尋找一段連續的區間，該區間的長度大于F，并且區間大于0。
可見，問題一下轉化成統計數字的和，而不是數字的平均值，問題變得明朗了。
尋找這種區間的算法是一個很簡單的動態規劃，復雜度為O(N)。
用 f[a, b] 表示在區間 [a, b] 中，所有子區間的最大值。
那么
當 b - a = F 時，f[a, b] 為序列中對應的和。
當 b - a > F 時，f[a, b] = max{ f[a, b - 1] + arr[b], f[b - f + 1, b] }
我們要求的是 f[0, N]。 因此，二分法的復雜度是 O(NlgN)。代碼跑了接近300ms。
  /**//*
 * 代碼大量參考這份解題報告
* http://blog.sina.com.cn/s/blog_5c95cb070100dd47.html
* 原作者代碼寫得很不錯！贊一個！
 */
 #include <stdio.h>
#define MAX_N 100032
double S[MAX_N], A[MAX_N];
int N, F;
int check(double val)
 {
double cur, pre;
int i;
pre = S[F - 1] - val * (F - 1);
  for (i = F; i <= N; i++) {
cur = S[i] - S[i - F] - val * F;
pre = pre + A[i] - val;
if (cur > pre)
pre = cur;
if (pre > -1e-6)
return 1;
 }
return 0;
}
int main()
{
int i;
double l, r, m;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &F);
l = 1e50;
r = 0;
A[0] = S[0] = 0;
for (i = 1; i <= N; i++) {
scanf("%lf", &A[i]);
if (A[i] > r)
r = A[i];
if (A[i] < l)
l = A[i];
S[i] = S[i - 1] + A[i];
}
while (r - l >= 1e-6) {
m = (l + r) / 2;
if (check(m))
l = m;
else
r = m;
}
printf("%d\n", (int)(r * 1000));
return 0;
}
這個方法不是真的求點的凸包，是用了求凸包時候的技巧。 首先把序列轉化成一個圖，一共有N個點，第 i 個點的坐標為 (i, S[i])，其中 S[i] 為序列的前 i 項和。 在圖上，能觀察到，點a點b之間的斜率就是區間[a, b]的平均值。 當 N = 6, F = 3 的時候，按照最簡單的 O(N^2) 的做法，計算每兩個點之間的斜率，計算的順序為： [1, 3] [1, 4] [2, 4] [1, 5] [2, 5] [3, 5] [1, 6] [2, 6] [3, 6] [4, 6] 在算第6個點的時候，依次算了1，2，3，4跟點6的斜率。 為了避免不必要的計算，我們要沒必要計算的點剔除。 用類似凸包的計算更新方法，在點1，2，3。。。中維護一條“下凸折線”。 這樣，可以保證末尾的點跟折線中的點的斜率是先遞增再遞減的關系。 就能比較快的找出最大的斜率了。 這個算法的復雜度，網上的人說是O(N)，但我覺得好像不是O(N)啊，也不知道是什么。 但是，絕對不能單單以復雜度來評價算法的啦。 代碼跑了150ms左右。比2分的還是快一點。
/**//*
* 思路參考此解題報告
* http://hi.baidu.com/ultramanzhy/blog/item/a8cb4efa1ecf2e1aa9d31123.html
* 解法牛逼！贊一個！
*/
#include <stdio.h>
#define MAX_N 100032
int S[MAX_N], stack[MAX_N], N, F, sp;
__inline int turn_right(int a, int b, int c)
{
int x1, y1, x2, y2;
x1 = b - a;
y1 = S[b] - S[a];
x2 = c - b;
y2 = S[c] - S[b];
return x1*y2 - x2*y1 <= 0;
}
__inline double calc_k(int a, int b)
{
return (double)(S[b] - S[a]) / (double)(b - a);
}
int main()
{
int i, j;
double max_val, val;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &F);
for (i = 1; i <= N; i++) {
scanf("%d", &j);
S[i] = S[i - 1] + j;
}
max_val = 0;
for (i = 0; i <= N - F; i++) {
while (sp >= 2 && turn_right(stack[sp - 2], stack[sp - 1], i))
sp--;
stack[sp++] = i;
for (j = sp;
j >= 2 && turn_right(stack[j - 2], stack[j - 1], i + F);
j--
);
val = calc_k(stack[j - 1], i + F);
if (val > max_val)
max_val = val;
}
printf("%d\n", (int)(max_val * 1000));
return 0;
}
思路：
事先計算出第1500個數為859963392，枚舉2，3，5的所有乘積，過濾掉所有大于859963392的數。
積攢到1500個的時候停止計算。然后快排就行了。速度還挺快呢。0ms。
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 859963392
__int64 arr[1501];
int cnt;
int cmp(const void *a, const void *b)
{
return *(__int64 *)a - *(__int64 *)b;
}
int main()
{
__int64 a, b, c;
int i;
/**//*
cnt = 0;
for (i = 1; cnt < 1500; i++) {
val = i;
while (!(val & 1))
val >>= 1;
while (!(val % 3))
val /= 3;
while (!(val % 5))
val /= 5;
if (val == 1) {
printf("#%d %d\n", cnt, i);
cnt++;
}
}
*/
for (a = 1; a <= MAX_N; a *= 2) {
for (b = 1; a*b <= MAX_N; b *= 3) {
for (c = 1; a*b*c <= MAX_N; c *= 5) {
arr[++cnt] = a*b*c;
if (cnt >= 1500)
goto done;
}
}
}
done:
qsort(arr + 1, 1500, sizeof(arr[0]), cmp);
while (scanf("%d", &i), i)
printf("%d\n", arr[i]);
return 0;
}
思路： 每個節點記錄兩個值： 所有子節點的增量和 該節點的增量 代碼爛，1500+ms。 為了避免爆棧，實現計算好了左右邊界和中間值。
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100032
int N;
struct {
__int64 up, down;
int rl, rr, rm;
} tree[MAX_N*4];
enum OP {
INSERT,
SUM,
} op;
__int64 val;
void tree_op(int idx, int l, int r)
{
if (op == INSERT) {
if (tree[idx].rl == l && tree[idx].rr == r) {
tree[idx].up += val;
return ;
}
tree[idx].down += val * (r - l + 1);
} else {
val += tree[idx].up * (r - l + 1);
if (tree[idx].rl == l && tree[idx].rr == r) {
val += tree[idx].down;
return ;
}
}
if (r <= tree[idx].rm) {
// all in left
tree_op(idx*2, l, r);
} else if (l > tree[idx].rm) {
// all in right
tree_op(idx*2+1, l, r);
} else {
// in left and right
tree_op(idx*2, l, tree[idx].rm);
tree_op(idx*2+1, tree[idx].rm + 1, r);
}
}
int main()
{
int i, j, q;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
tree[1].rl = 1;
tree[1].rm = (MAX_N + 1) / 2;
tree[1].rr = MAX_N;
for (i = 2; i < _countof(tree); i++) {
if (i & 1) {
tree[i].rl = tree[i/2].rm + 1;
tree[i].rr = tree[i/2].rr;
} else {
tree[i].rl = tree[i/2].rl;
tree[i].rr = tree[i/2].rm;
}
tree[i].rm = (tree[i].rl + tree[i].rr) / 2;
}
scanf("%d%d", &N, &q);
op = INSERT;
for (i = 1; i <= N; i++) {
scanf("%I64d", &val);
tree_op(1, i, i);
}
while (q--) {
scanf("%s%d%d", str, &i, &j);
if (str[0] == 'Q') {
val = 0;
op = SUM;
tree_op(1, i, j);
printf("%I64d\n", val);
} else {
scanf("%I64d", &val);
op = INSERT;
tree_op(1, i, j);
}
}
return 0;
}
題目大意： 給出一個01字符串。將其循環移位，將所有移位后的串列舉出來，并按字典序排序。 比如“abcd”，可以移位成“bcda”，“cdab”，“dabc”。排序以后，為 “abcd” “bcda” “cdab” “dabc” 將最后一列的字母抽取出來，即“dabc”。 然后，讓你還原出第一行的字符。 這是一個看上去很蛋疼的問題，沒事研究這個干啥呢。 想了半天，做不出來。看到discuss里面有人給了一個鏈接： http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform發現居然是一個壓縮算法！ 據說，將最后一列抽取出來，較原字符串相比，能夠 “easy to compress a string that has runs of repeated characters by techniques such as move-to-front transform and run-length encoding.” 這個就不理解了。。 這題簡化了一下條件，字符串只包含01。 看了它的還原方法。如果直接這樣寫：
def ibwt(r):
"""Apply inverse Burrow-Wheeler transform."""
table = [""] * len(r) # Make empty table
for i in range(len(r)):
table = [r[i] + table[i] for i in range(len(r))] # Add a column of r
table.sort()
s = [row for row in table if row.endswith("\0")][0] # Find the correct row (ending in "\0")
return s.strip("\0") # Get rid of trailing null character
還是復雜度很高，為 O(N*N*lgN)。 那disscus里面說的O(N)的方法和那么多0ms是咋來的呢？ 想了一下。發現每一次添加列然后再排序的操作，都是做一樣的置換。 因為每次添加的列都一樣，排序的結果當然也是一樣（比如是穩定排序）。 所以，第i列的結果就是置換i次的結果。我們只需要第一行的數據。 經過一次排序之后，就知道每一個行置到了哪個地方，如果第三行到了第一行，第五行到了第三行。 那么： 第一列第一行的就是未排序數據的第三行 第二列第一行的就是未排序數據的第五行 由于數據中只有01，完全可以在O(N)內完成排序操作，之后得出第一行的操作也是 O(N) 完成的。 可惜代碼實現出來，也沒有到 0ms ，好像是 79ms 。代碼寫得爛！高手改改也是0ms了。 代碼里也包括了一個求普通字符串的BWT操作。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(const void *a, const void *b)
{
return strcmp(*(char **)a, *(char **)b);
}
void bwt(char *in, char *out)
{
static char arr[32][32], *sorted[32];
int len, i, j;
len = strlen(in);
for (i = 0; i < len; i++) {
sorted[i] = arr[i];
for (j = 0; j < len; j++)
sorted[i][j] = in[(i + j) % len];
sorted[i][len] = 0;
}
qsort(sorted, len, sizeof(sorted[0]), cmp);
for (i = 0; i < len; i++)
printf("%s\n", sorted[i]);
for (i = 0; i < len; i++)
out[i] = sorted[i][len - 1];
out[i] = 0;
}
int cmp2(const void *a, const void *b)
{
if (*(int *)a == *(int *)b)
return *((int *)a + 1) - *((int *)b + 1);
else
return *(int *)a - *(int *)b;
}
void ibwt(char *in, char *out)
{
struct {
int ch, idx;
} arr[32];
int i, len, j;
len = strlen(in);
for (i = 0; i < len; i++) {
arr[i].ch = in[i];
arr[i].idx = i;
}
qsort(arr, len, sizeof(arr[0]), cmp2);
for (i = 0; i < len; i++)
printf("%c %d\n", arr[i].ch, arr[i].idx);
j = arr[0].idx;
for (i = 0; i < len - 1; i++) {
out[i] = in[j];
j = arr[j].idx;
}
out[len - 1] = in[0];
out[len] = 0;
printf("%s\n", out);
}
void test()
{
char in[32], out[32], res[32];
strcpy(in, "banana");
bwt(in, out);
printf("out:\n%s\n", out);
ibwt(out, res);
}
int main()
{
static int map[3032], arr[3032], n, val, one[3032], one_cnt, zero_cnt, i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &val);
arr[i] = val;
if (val)
one[one_cnt++] = i;
else
map[zero_cnt++] = i;
}
for (i = 0; i < one_cnt; i++)
map[zero_cnt + i] = one[i];
val = map[0];
for (i = 0; i < n - 1; i++) {
printf("%d ", arr[val]);
val = map[val];
}
printf("%d\n", arr[0]);
return 0;
}
題目大意：
兩個人玩游戲。輪流取數字，范圍在1~20之間。
規定：
1. 取過的數字不能再取。
2. 取過的數字的倍數不能再取。
3. 任意個(2)的和不能再取。
當某個人發現沒有數字可取時，他就輸了。
給出一個“殘局”。問，我現在應該怎么取，才能保證勝利。
思路：
其實這個也不是很難的博弈問題。只是搜索就可以解決了。要用位來表示當前剩余數字的狀態，
方便保存動態規劃的結果。
#include <stdio.h>
#define N 20
char dp[2][1 << (N + 1)];
__inline int use(int visited, int idx)
{
int i;
for (i = 0; i + idx <= N; i++) {
if (visited & (1 << i))
visited |= 1 << (i + idx);
}
return visited;
}
int dfs(int my_step, int visited)
{
int i, r;
if (visited == (1 << (N + 1)) - 1)
return !my_step;
r = dp[my_step][visited];
if (r)
return r - 1;
for (i = 2; i <= N; i++) {
if (visited & (1 << i))
continue;
r = dfs(!my_step, use(visited, i));
if (my_step && r)
return 1;
if (!my_step && !r)
return 0;
}
dp[my_step][visited] = !my_step + 1;
return !my_step;
}
int main()
{
int n, v, i, arr[24], cnt, t;
freopen("e:\\test\\in.txt", "r", stdin);
for (t = 1; scanf("%d", &n), n; t++) {
v = ((1 << (N + 1)) - 1) & ~2;
while (n--) {
scanf("%d", &i);
v &= ~(1 << i);
}
cnt = 0;
for (i = 2; i <= N; i++) {
if (v & (1 << i))
continue;
if (dfs(0, use(v, i)))
arr[cnt++] = i;
}
printf("Test Case #%d\n", t);
if (cnt) {
printf("The winning moves are:");
for (i = 0; i < cnt; i++)
printf(" %d", arr[i]);
printf("\n");
} else
printf("There's no winning move.\n");
printf("\n");
}
return 0;
}
#include <stdio.h>
#include <string.h>
void swap(char *a, char *b)
{
char t = *a;
*a = *b;
*b = t;
}
void rev(char *str)
{
int i, len;
len = strlen(str);
for (i = 0; i < len/2; i++)
swap(&str[i], &str[len - i - 1]);
}
int str2int(char *str)
{
int i;
for (i = 0; *str; str++)
i = i * 10 + *str - '0';
return i;
}
int main()
{
int n, i, j;
char a[16], b[16];
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &n);
while (n--) {
scanf("%s%s", a, b);
rev(a);
rev(b);
i = str2int(a) + str2int(b);
sprintf(a, "%d", i);
rev(a);
i = str2int(a);
printf("%d\n", i);
}
return 0;
}
思路：
先快排，然后用公式計算出總的volume值。
#include <stdio.h>
typedef unsigned __int64 u64;
__inline void swap(u64 *a, u64 *b)
{
u64 t = *a;
*a = *b;
*b = t;
}
void qs(u64 *arr, int len)
{
int p, r, l;
if (len < 2)
return ;
l = 0;
r = len - 2;
p = len - 1;
while (1) {
while (l < p && arr[l] < arr[p])
l++;
while (r >= 0 && arr[r] >= arr[p])
r--;
if (l > r)
break;
swap(&arr[l], &arr[r]);
}
swap(&arr[l], &arr[p]);
qs(arr, l);
qs(arr + l + 1, len - l - 1);
}
u64 in[10024];
int N;
int main()
{
int i;
u64 s;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &N);
for (i = 0; i < N; i++)
scanf("%llu", &in[i]);
qs(in, N);
s = 0;
for (i = 1; i <= N - 1; i++)
s += 2 * i * (N - i) * (in[i] - in[i - 1]);
printf("%llu\n", s);
return 0;
}
#include <stdio.h>
#include <string.h>
char map[26], rev_map[26], res[26];
int N, pre[26];
void dfs(int idx, int used)
{
int i;
if (idx == N) {
for (i = 0; i < N; i++)
printf("%c", map[res[i]] + 'a');
printf("\n");
return ;
}
for (i = 0; i < N; i++) {
if (used & (1 << i))
continue;
if ((pre[i] & used) != pre[i])
continue;
res[idx] = i;
dfs(idx + 1, used | (1 << i));
}
}
int main()
{
char a, b;
int i;
freopen("e:\\test\\in.txt", "r", stdin);
while (1) {
memset(rev_map, 0, sizeof(rev_map));
while (1) {
a = getchar();
if (a == EOF)
return 0;
if (a == '\n')
break;
if (a >= 'a' && a <= 'z')
rev_map[a - 'a'] = 1;
}
for (i = N = 0; i < 26; i++)
if (rev_map[i]) {
map[N] = i;
rev_map[i] = N++;
}
memset(pre, 0, sizeof(pre));
i = 0;
while (1) {
a = getchar();
if (a == '\n' || a == EOF)
break;
if (a < 'a' || a > 'z')
continue;
if (i & 1)
pre[rev_map[a - 'a']] |= 1 << rev_map[b - 'a'];
else
b = a;
i++;
}
dfs(0, 0);
printf("\n");
}
return 0;
}
摘要:
#define ICON_SIZE 32static int _HBitmapToBmp32Bits(HBITMAP hBitmap, U8 *out, int out_len){ /**//* &nb... 閱讀全文
|