2012-10-03 08:39:14Morris
[PTC][201209] ABCE 爛解
Background
PTC 噩夢啊, 比賽過一個小時後, 我才從通識回來 ... 最終結果 4 題, 好不容易看懂 pD 的繁瑣英文, 我悲摧的來不及寫完, 還在 compile, 時間已經抵達終點 ! 神啊, 請再給我一個小時
Problem A
題意很簡單, 先給定平面 n 個點 (POI),然後對每個詢問集輸出, 有多少"次"的 POI 在詢問集的半徑內, 首先先看 n ≦ 100,0000, 直覺告訴我們 O(n*m) 是不可能通過的, 聽 inker 賽後說道這題應該是有一篇論文(range query)的寫法, 當然比賽的時候不可能會想那麼多, 猶豫就輸了。還是 O(n*m) 下吧
#include <stdio.h>
using namespace std;
typedef struct {
long long x, y;
} Pt;
Pt P[1000005], Q[1000005];
int main() {
int n, i, j, m;
long long d;
while(scanf("%d", &n) == 1) {
int tn = 0;
for(i = 0; i < n; i++) {
scanf("%lld %lld", &P[i].x, &P[i].y);
}
while(scanf("%d %lld", &m, &d) == 2) {
if(m == 0 && d == 0) break;
for(i = 0; i < m; i++)
scanf("%lld %lld", &Q[i].x, &Q[i].y);
int ans = 0;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if((P[i].x-Q[j].x)*(P[i].x-Q[j].x)
+ (P[i].y-Q[j].y)*(P[i].y-Q[j].y)
<= d*d) {
ans++;
}
}
}
printf("%d\n", ans);
}
}
return 0;
}
Problem B
簡單的去重問題, 求真正存在的使用者個數
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
int main() {
int t;
char in[50];
scanf("%d", &t);
gets(in);
while(t--) {
set<string> Q;
while(gets(in)) {
if(in[0] == '-') break;
Q.insert(in);
}
printf("%d\n", Q.size());
}
return 0;
}
Problem C
這題會給定一個遞增的序列, 然後挑兩項當做費式數列的首兩項, 然後看最多能再這個序列裡面湊到最多的費式數列, 有人會想說用動態規劃 DP, 直觀想是 O(n*n), 有點類似 LIS 的建法, 那當然也可以, 不過窮舉也是差不多的速度, 差不多是 O(n*n*k), 但是 k 肯定是很小的, 因為以最小的費式數列, k 也頂多 25, 而且窮舉可以剪枝, 說不定比 DP 還快。
#include <stdio.h>
int main() {
int t;
int i, j, n, x, f0, f1;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int f[100000] = {};
int a[50005];
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
f[a[i]] = 1;
}
int ans = 2;
for(i = 0; i < n; i++) {
for(j = i+1; j < n; j++) {
if(n-j+1 <= ans)
break;
f0 = a[i], f1 = a[j];
int cnt = 2;
while(1) {
x = f0+f1;
f0 = f1;
f1 = x;
if(x > a[n-1] || f[x] == 0)
break;
cnt++;
}
if(cnt > ans) ans = cnt;
}
}
printf("%d\n", ans);
}
return 0;
}
Problem E
給一個條件的遞歸圖形, 專有名稱應該是「碎形」, 然後問一個點在幾個長方形中, 那麼直觀的遞迴找出所有長方形, 然後去判斷是否在裡面就好了, 有一題很像的在 UVa, 如果我沒記錯題目應該是「All Square」
#include <stdio.h>
int k, n, m, ans;
void dfs(int x, int y, int k) {
if(k == 0)
return ;
if(x-2*k <= n && x+2*k >= n && y-k <= m && y+k >= m)
ans++;
dfs(x+2*k, y+k, k/2);
dfs(x+2*k, y-k, k/2);
dfs(x-2*k, y+k, k/2);
dfs(x-2*k, y-k, k/2);
}
int main() {
while(scanf("%d %d %d", &k, &n, &m) == 3) {
if(k == 0 && n == 0 && m == 0)
break;
ans = 0;
dfs(1024, 1024, k);
printf("%d\n", ans);
}
return 0;
}
總結 :
這次題目難的可以很難, 不過我想出題教授應該沒有考慮的測試機器的效率, 導致濫做法可以通過, 晚了一個小時, 因此沒解出 pD, 時間上看完題目就耗費了我 30 分鐘, 英文很菜的, 很多題目看不是很懂, 單字量也不夠, 都是拿之前的解題感覺猜測題目想要求我們做些什麼。
一次 PTC 大概有一題是難題, 然而其他題猶豫就輸了, 不仿拿出不合理的複雜度去嘗試吧
PTC 噩夢啊, 比賽過一個小時後, 我才從通識回來 ... 最終結果 4 題, 好不容易看懂 pD 的繁瑣英文, 我悲摧的來不及寫完, 還在 compile, 時間已經抵達終點 ! 神啊, 請再給我一個小時
Problem A
題意很簡單, 先給定平面 n 個點 (POI),然後對每個詢問集輸出, 有多少"次"的 POI 在詢問集的半徑內, 首先先看 n ≦ 100,0000, 直覺告訴我們 O(n*m) 是不可能通過的, 聽 inker 賽後說道這題應該是有一篇論文(range query)的寫法, 當然比賽的時候不可能會想那麼多, 猶豫就輸了。還是 O(n*m) 下吧
#include <stdio.h>
using namespace std;
typedef struct {
long long x, y;
} Pt;
Pt P[1000005], Q[1000005];
int main() {
int n, i, j, m;
long long d;
while(scanf("%d", &n) == 1) {
int tn = 0;
for(i = 0; i < n; i++) {
scanf("%lld %lld", &P[i].x, &P[i].y);
}
while(scanf("%d %lld", &m, &d) == 2) {
if(m == 0 && d == 0) break;
for(i = 0; i < m; i++)
scanf("%lld %lld", &Q[i].x, &Q[i].y);
int ans = 0;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if((P[i].x-Q[j].x)*(P[i].x-Q[j].x)
+ (P[i].y-Q[j].y)*(P[i].y-Q[j].y)
<= d*d) {
ans++;
}
}
}
printf("%d\n", ans);
}
}
return 0;
}
Problem B
簡單的去重問題, 求真正存在的使用者個數
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
int main() {
int t;
char in[50];
scanf("%d", &t);
gets(in);
while(t--) {
set<string> Q;
while(gets(in)) {
if(in[0] == '-') break;
Q.insert(in);
}
printf("%d\n", Q.size());
}
return 0;
}
Problem C
這題會給定一個遞增的序列, 然後挑兩項當做費式數列的首兩項, 然後看最多能再這個序列裡面湊到最多的費式數列, 有人會想說用動態規劃 DP, 直觀想是 O(n*n), 有點類似 LIS 的建法, 那當然也可以, 不過窮舉也是差不多的速度, 差不多是 O(n*n*k), 但是 k 肯定是很小的, 因為以最小的費式數列, k 也頂多 25, 而且窮舉可以剪枝, 說不定比 DP 還快。
#include <stdio.h>
int main() {
int t;
int i, j, n, x, f0, f1;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int f[100000] = {};
int a[50005];
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
f[a[i]] = 1;
}
int ans = 2;
for(i = 0; i < n; i++) {
for(j = i+1; j < n; j++) {
if(n-j+1 <= ans)
break;
f0 = a[i], f1 = a[j];
int cnt = 2;
while(1) {
x = f0+f1;
f0 = f1;
f1 = x;
if(x > a[n-1] || f[x] == 0)
break;
cnt++;
}
if(cnt > ans) ans = cnt;
}
}
printf("%d\n", ans);
}
return 0;
}
Problem E
給一個條件的遞歸圖形, 專有名稱應該是「碎形」, 然後問一個點在幾個長方形中, 那麼直觀的遞迴找出所有長方形, 然後去判斷是否在裡面就好了, 有一題很像的在 UVa, 如果我沒記錯題目應該是「All Square」
#include <stdio.h>
int k, n, m, ans;
void dfs(int x, int y, int k) {
if(k == 0)
return ;
if(x-2*k <= n && x+2*k >= n && y-k <= m && y+k >= m)
ans++;
dfs(x+2*k, y+k, k/2);
dfs(x+2*k, y-k, k/2);
dfs(x-2*k, y+k, k/2);
dfs(x-2*k, y-k, k/2);
}
int main() {
while(scanf("%d %d %d", &k, &n, &m) == 3) {
if(k == 0 && n == 0 && m == 0)
break;
ans = 0;
dfs(1024, 1024, k);
printf("%d\n", ans);
}
return 0;
}
總結 :
這次題目難的可以很難, 不過我想出題教授應該沒有考慮的測試機器的效率, 導致濫做法可以通過, 晚了一個小時, 因此沒解出 pD, 時間上看完題目就耗費了我 30 分鐘, 英文很菜的, 很多題目看不是很懂, 單字量也不夠, 都是拿之前的解題感覺猜測題目想要求我們做些什麼。
一次 PTC 大概有一題是難題, 然而其他題猶豫就輸了, 不仿拿出不合理的複雜度去嘗試吧
你好我是正為了ptc比賽苦惱的大一生，
想要透過e-mail請教一些經驗談，
不曉得方不方便>"<