2012-11-29 20:54:10Morris
[ITSA] 19th 總解答
這次沒有動規題，全是模擬題，雖然沒有很難，但打得很不順。
一個人參賽無助了？
打表不多語
你自己想你自己做過位元運算的二十皇后，再怎麼跑都是鄰近一秒，更不用說一百皇后，更何況你要 hash 九十度的翻轉存在，打表是肯定的。
#include <stdio.h>
int main() {
int n;
while(scanf("%d", &n) == 1) {
switch(n) {
case 1:puts("1");break;
case 2:puts("0");break;
case 3:puts("0");break;
case 4:puts("2");break;
case 5:puts("2");break;
case 6:puts("0");break;
case 7:puts("0");break;
case 8:puts("0");break;
case 9:puts("0");break;
case 10:puts("0");break;
case 11:puts("0");break;
case 12:puts("8");break;
case 13:puts("8");break;
case 14:puts("0");break;
case 15:puts("0");break;
case 16:puts("64");break;
case 17:puts("128");break;
case 18:puts("0");break;
case 19:puts("0");break;
case 20:puts("480");break;
case 21:puts("704");break;
case 22:puts("0");break;
case 23:puts("0");break;
case 24:puts("3328");break;
case 25:puts("3264");break;
case 28:puts("32896");break;
case 29:puts("43776");break;
case 32:puts("406784");break;
case 33:puts("667904");break;
case 36:puts("5845504");break;
case 37:puts("8650752");break;
case 40:puts("77184000");break;
case 41:puts("101492736");break;
case 44:puts("1261588480");break;
case 45:puts("1795233792");break;
case 48:puts("21517426688");break;
case 49:puts("35028172800");break;
default:
puts("0");
}
}
return 0;
}
我相信你只有一筆，別給我偷偷跟上次一樣陰測資。
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> g[100005];
long long A[100005], ans;
long long dfs(int nd) {
long long sum = 0, tmp;
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
tmp = dfs(*it);
if(nd == 0 && tmp > ans)
ans = tmp;
sum += tmp;
}
sum += A[nd];
return sum;
}
int main() {
int n, i, p;
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%lld", &A[i]);
for(i = 1; i < n; i++) {
scanf("%d", &p);
g[p].push_back(i);
}
ans = 0;
dfs(0);
printf("%lld\n", ans);
return 0;
}
10.5% 要四捨五入換算他所在的 percent。
扣稅要無條件進位，不知道會不會 overflow，先計算個 LONG LONG 好了。
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int A[1000];
int main() {
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int mx = 0, i, j;
for(i = 0; i < n; i++) {
scanf("%d", &A[i]);
if(A[i] > mx)
mx = A[i];
}
sort(A, A+n);
int m = n, x;
long long ans = 0;
for(i = n-1; i >= 0; i--)
if(A[i] == mx)
m--, ans += (int)ceil(A[i]*0.4);
for(i = n-m, j = m-1; j >= 0; i++, j--) {
char rank[50];
sprintf(rank, "%.lf", (double)i*100/n);
sscanf(rank, "%d", &x);
if(x >= 11 && x <= 30)
ans += (int)ceil(A[j]*0.3);
else if(x <= 60)
ans += (int)ceil(A[j]*0.2);
else if(x <= 80)
ans += (int)ceil(A[j]*0.1);
}
printf("%lld\n", ans);
}
return 0;
}
其實題目沒有表達得很好，不過大概懂他想作什麼。
#include <stdio.h>
int main() {
int n;
int D[7] = {1000,500,100,50,10,5,1};
while(scanf("%d", &n) == 1) {
int A[7] = {};
int i;
for(i = 0; i < 7; i++) {
A[i] = n/D[i];
n %= D[i];
}
int M[7] = {}, N[7] = {};
for(i = 0; i < 7; i++) {
if(A[i]%2) {
M[i] = A[i]/2+1;
N[i] = A[i]-M[i];
for(i++; i < 7; i++)
N[i] = A[i];
break;
}
M[i] = A[i]/2;
N[i] = A[i]/2;
}
int s1 = 0, s2 = 0;
for(i = 0; i < 7; i++) {
if(i) putchar(' ');
printf("%d", M[i]);
s1 += M[i] * D[i];
}
puts("");
for(i = 0; i < 7; i++) {
if(i) putchar(' ');
printf("%d", N[i]);
s2 += N[i] * D[i];
}
puts("");
printf("%d\n", s1-s2);
}
return 0;
}
找出 LCS，應該已經寫到爛掉了，就不多說了。
#include <stdio.h>
#include <string.h>
char x[105], y[105];
int dp[105][105], arg[105][105];
void print(int i, int j) {
if(dp[i][j] == 0) return;
if(arg[i][j] == 1) {
print(i-1, j-1);
printf("%c", x[i-1]);
} else if(arg[i][j] == 2) {
print(i-1, j);
} else
print(i, j-1);
}
int main() {
int i, j;
while(scanf("%s %s", x, y) == 2) {
int la = strlen(x), lb = strlen(y);
memset(dp, 0, sizeof(dp));
for(i = 1; i <= la; i++) {
for(j = 1; j <= lb; j++) {
if(x[i-1] == y[j-1]) {
dp[i][j] = dp[i-1][j-1]+1;
arg[i][j] = 1;
} else {
if(dp[i-1][j] > dp[i][j-1]) {
dp[i][j] = dp[i-1][j];
arg[i][j] = 2;
} else {
dp[i][j] = dp[i][j-1];
arg[i][j] = 3;
}
}
}
}
if(dp[la][lb] == 0)
puts("none");
else
print(la, lb), puts("");
}
return 0;
}
一個人參賽無助了？
打表不多語
你自己想你自己做過位元運算的二十皇后，再怎麼跑都是鄰近一秒，更不用說一百皇后，更何況你要 hash 九十度的翻轉存在，打表是肯定的。
#include <stdio.h>
int main() {
int n;
while(scanf("%d", &n) == 1) {
switch(n) {
case 1:puts("1");break;
case 2:puts("0");break;
case 3:puts("0");break;
case 4:puts("2");break;
case 5:puts("2");break;
case 6:puts("0");break;
case 7:puts("0");break;
case 8:puts("0");break;
case 9:puts("0");break;
case 10:puts("0");break;
case 11:puts("0");break;
case 12:puts("8");break;
case 13:puts("8");break;
case 14:puts("0");break;
case 15:puts("0");break;
case 16:puts("64");break;
case 17:puts("128");break;
case 18:puts("0");break;
case 19:puts("0");break;
case 20:puts("480");break;
case 21:puts("704");break;
case 22:puts("0");break;
case 23:puts("0");break;
case 24:puts("3328");break;
case 25:puts("3264");break;
case 28:puts("32896");break;
case 29:puts("43776");break;
case 32:puts("406784");break;
case 33:puts("667904");break;
case 36:puts("5845504");break;
case 37:puts("8650752");break;
case 40:puts("77184000");break;
case 41:puts("101492736");break;
case 44:puts("1261588480");break;
case 45:puts("1795233792");break;
case 48:puts("21517426688");break;
case 49:puts("35028172800");break;
default:
puts("0");
}
}
return 0;
}
我相信你只有一筆，別給我偷偷跟上次一樣陰測資。
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> g[100005];
long long A[100005], ans;
long long dfs(int nd) {
long long sum = 0, tmp;
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
tmp = dfs(*it);
if(nd == 0 && tmp > ans)
ans = tmp;
sum += tmp;
}
sum += A[nd];
return sum;
}
int main() {
int n, i, p;
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%lld", &A[i]);
for(i = 1; i < n; i++) {
scanf("%d", &p);
g[p].push_back(i);
}
ans = 0;
dfs(0);
printf("%lld\n", ans);
return 0;
}
10.5% 要四捨五入換算他所在的 percent。
扣稅要無條件進位，不知道會不會 overflow，先計算個 LONG LONG 好了。
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int A[1000];
int main() {
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int mx = 0, i, j;
for(i = 0; i < n; i++) {
scanf("%d", &A[i]);
if(A[i] > mx)
mx = A[i];
}
sort(A, A+n);
int m = n, x;
long long ans = 0;
for(i = n-1; i >= 0; i--)
if(A[i] == mx)
m--, ans += (int)ceil(A[i]*0.4);
for(i = n-m, j = m-1; j >= 0; i++, j--) {
char rank[50];
sprintf(rank, "%.lf", (double)i*100/n);
sscanf(rank, "%d", &x);
if(x >= 11 && x <= 30)
ans += (int)ceil(A[j]*0.3);
else if(x <= 60)
ans += (int)ceil(A[j]*0.2);
else if(x <= 80)
ans += (int)ceil(A[j]*0.1);
}
printf("%lld\n", ans);
}
return 0;
}
其實題目沒有表達得很好，不過大概懂他想作什麼。
#include <stdio.h>
int main() {
int n;
int D[7] = {1000,500,100,50,10,5,1};
while(scanf("%d", &n) == 1) {
int A[7] = {};
int i;
for(i = 0; i < 7; i++) {
A[i] = n/D[i];
n %= D[i];
}
int M[7] = {}, N[7] = {};
for(i = 0; i < 7; i++) {
if(A[i]%2) {
M[i] = A[i]/2+1;
N[i] = A[i]-M[i];
for(i++; i < 7; i++)
N[i] = A[i];
break;
}
M[i] = A[i]/2;
N[i] = A[i]/2;
}
int s1 = 0, s2 = 0;
for(i = 0; i < 7; i++) {
if(i) putchar(' ');
printf("%d", M[i]);
s1 += M[i] * D[i];
}
puts("");
for(i = 0; i < 7; i++) {
if(i) putchar(' ');
printf("%d", N[i]);
s2 += N[i] * D[i];
}
puts("");
printf("%d\n", s1-s2);
}
return 0;
}
找出 LCS，應該已經寫到爛掉了，就不多說了。
#include <stdio.h>
#include <string.h>
char x[105], y[105];
int dp[105][105], arg[105][105];
void print(int i, int j) {
if(dp[i][j] == 0) return;
if(arg[i][j] == 1) {
print(i-1, j-1);
printf("%c", x[i-1]);
} else if(arg[i][j] == 2) {
print(i-1, j);
} else
print(i, j-1);
}
int main() {
int i, j;
while(scanf("%s %s", x, y) == 2) {
int la = strlen(x), lb = strlen(y);
memset(dp, 0, sizeof(dp));
for(i = 1; i <= la; i++) {
for(j = 1; j <= lb; j++) {
if(x[i-1] == y[j-1]) {
dp[i][j] = dp[i-1][j-1]+1;
arg[i][j] = 1;
} else {
if(dp[i-1][j] > dp[i][j-1]) {
dp[i][j] = dp[i-1][j];
arg[i][j] = 2;
} else {
dp[i][j] = dp[i][j-1];
arg[i][j] = 3;
}
}
}
}
if(dp[la][lb] == 0)
puts("none");
else
print(la, lb), puts("");
}
return 0;
}