poj-1068如何通过长尾关键词优化搜索排名？
- 内容介绍
- 文章标签
- 相关推荐
本文共计452个文字，预计阅读时间需要2分钟。
数组都开到100以后，AC了。
数组都开到100以后，AC了。。。
#include <stdio.h>
#include <string.h>
void fillS(char * S, int * P, int Plength, int * Pdst) {
if (P == Pdst + 1) {
return;
}
int leftParentheseNum = P[0];
for (int i = 0; i < leftParentheseNum; i++) {
*(S + i) = '(';
}
*(S + leftParentheseNum) = ')';
for (int i = 0; P + i <= Pdst; i++) {
*(P + i) -= leftParentheseNum;
}
fillS(S + leftParentheseNum + 1, P + 1, Plength, Pdst);
}
void getW(int * P, int Plength) {
char parenthesisArray[100] = {0};
int W[100] = {0};
fillS(parenthesisArray, P, Plength, P + Plength -1);
// printf("Fills");
// printf("%s %d\n", parenthesisArray, (int)strlen(parenthesisArray));
int WId = 0;
for (int i = 0; i < strlen(parenthesisArray); i++) {
if (parenthesisArray[i] == ')') {
for (int k = i-1; k >= 0; k--) {
if (parenthesisArray[k] == '(') {
parenthesisArray[k] = ' ';
int rightNum = 0;
// printf("%d %d\n", k + 1, i - 1);
for (int j = k + 1 ; j <= i-1 ; j++) {
if (parenthesisArray[j] == ')') {
rightNum++;
}
}
// printf("num: %d\n", rightNum + 1);
W[WId] = rightNum + 1;
WId++;
break;
}
}
}
}
for (int i = 0; i < Plength; i++) {
printf("%d ", W[i]);
}
printf("\n");
}
void test() {
int P[21] = {4, 5, 6, 6, 6, 6};
int Plength = 6;
getW(P, Plength);
}
int main() {
int caseNum = 0;
scanf("%d", &caseNum);
for (int i = 0; i < caseNum; i++) {
int P[100] = {0};
int Plength = 0;
char tmp;
scanf("%d", &Plength);
for (int i = 0; i < Plength; i++) {
scanf("%d%c", P + i, &tmp);
}
getW(P, Plength);
}
}
本题不难， 但是可选的方法挺多的，看discuss里很多用stack的，
我在这里从P 推导出 括号内容的时候用了分治法，
然后再由括号内容推P的时候用了最笨的挨个查找（其实这里就可以用栈了， 不过其实也不简单， 还要反复把右括号出进栈， 跟括号有关的很多都应该联想到栈）。
还有就是scanf接受本题这种类型的参数 可以用 %d%c将空格跳过。
发现自己还是太毛躁， 脑子没想清楚， 手就动了， 还做不到完整的在脑中勾勒出整个程序。
标记一下， 看discuss似乎该题有更简单的办法， 回头研究研究。
本文共计452个文字，预计阅读时间需要2分钟。
数组都开到100以后，AC了。
数组都开到100以后，AC了。。。
#include <stdio.h>
#include <string.h>
void fillS(char * S, int * P, int Plength, int * Pdst) {
if (P == Pdst + 1) {
return;
}
int leftParentheseNum = P[0];
for (int i = 0; i < leftParentheseNum; i++) {
*(S + i) = '(';
}
*(S + leftParentheseNum) = ')';
for (int i = 0; P + i <= Pdst; i++) {
*(P + i) -= leftParentheseNum;
}
fillS(S + leftParentheseNum + 1, P + 1, Plength, Pdst);
}
void getW(int * P, int Plength) {
char parenthesisArray[100] = {0};
int W[100] = {0};
fillS(parenthesisArray, P, Plength, P + Plength -1);
// printf("Fills");
// printf("%s %d\n", parenthesisArray, (int)strlen(parenthesisArray));
int WId = 0;
for (int i = 0; i < strlen(parenthesisArray); i++) {
if (parenthesisArray[i] == ')') {
for (int k = i-1; k >= 0; k--) {
if (parenthesisArray[k] == '(') {
parenthesisArray[k] = ' ';
int rightNum = 0;
// printf("%d %d\n", k + 1, i - 1);
for (int j = k + 1 ; j <= i-1 ; j++) {
if (parenthesisArray[j] == ')') {
rightNum++;
}
}
// printf("num: %d\n", rightNum + 1);
W[WId] = rightNum + 1;
WId++;
break;
}
}
}
}
for (int i = 0; i < Plength; i++) {
printf("%d ", W[i]);
}
printf("\n");
}
void test() {
int P[21] = {4, 5, 6, 6, 6, 6};
int Plength = 6;
getW(P, Plength);
}
int main() {
int caseNum = 0;
scanf("%d", &caseNum);
for (int i = 0; i < caseNum; i++) {
int P[100] = {0};
int Plength = 0;
char tmp;
scanf("%d", &Plength);
for (int i = 0; i < Plength; i++) {
scanf("%d%c", P + i, &tmp);
}
getW(P, Plength);
}
}
本题不难， 但是可选的方法挺多的，看discuss里很多用stack的，
我在这里从P 推导出 括号内容的时候用了分治法，
然后再由括号内容推P的时候用了最笨的挨个查找（其实这里就可以用栈了， 不过其实也不简单， 还要反复把右括号出进栈， 跟括号有关的很多都应该联想到栈）。
还有就是scanf接受本题这种类型的参数 可以用 %d%c将空格跳过。
发现自己还是太毛躁， 脑子没想清楚， 手就动了， 还做不到完整的在脑中勾勒出整个程序。
标记一下， 看discuss似乎该题有更简单的办法， 回头研究研究。