Letter Game[USACO]-白红宇

Letter Game[USACO]

阅读量：5324 次

发布时间：2019-06-14

本文共 3605 字，大约阅读时间需要 12 分钟。

这道题感觉没什么困难的。只是注意，不要重复。(也可以在输出的时候控制不输出重复结果)

/*ID: zhangyc1LANG: C++TASK: lgame*/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;char strGiven[10], strDict[10];int nSizeGiven = 0;int arrWeight[26] = {2, 5, 4, 4, 1, 6, 5, 5, 1, 7, 6, 3, 5, 2, 3, 5, 7, 2, 1, 2, 4, 6, 6, 7, 5, 7};int arrCountGiven[26], arrCountDict[26];char dict[40000][10];struct SRecord { int nScore; char strRs[10];};SRecord sArrRecord[40000];int nDictSize = 0, nRsSize = 0;ofstream fileout("lgame.out");int compare(const void* argv1, const void* argv2){ const SRecord* p1 = (const SRecord*)argv1; const SRecord* p2 = (const SRecord*)argv2; if (p1->nScore == p2->nScore) { return strcmp(p1->strRs, p2->strRs); } else return p2->nScore - p1->nScore;}void prepairData(){ ifstream filein("lgame.in"); filein.getline(strGiven, sizeof(strGiven)); filein.close(); memset(arrCountGiven, 0, sizeof(arrCountGiven)); int i = 0; while (strGiven[i] != '\0') { arrCountGiven[strGiven[i] - 'a']++; i++; } nSizeGiven = i; ifstream fileDict("lgame.dict"); while (fileDict >> strDict && strDict[0] != '.') { memset(arrCountDict, 0, sizeof(arrCountDict)); int nSizeStrDict = strlen(strDict); if (nSizeStrDict > nSizeGiven) continue; bool bValid = true; for (i = 0; i < nSizeStrDict; i++) { if (arrCountGiven[strDict[i]-'a'] == 0) { bValid = false; break; } arrCountDict[strDict[i]-'a']++; if (arrCountDict[strDict[i]-'a'] > arrCountGiven[strDict[i]-'a']) { bValid = false; break; } } if (bValid) { strcpy(dict[nDictSize], strDict); nDictSize++; } } fileDict.close();}void process(){ int nSum = 0; for (int i = 0; i < nSizeGiven; i++) { nSum += arrWeight[strGiven[i] - 'a']; } int arrCountTemp1[26], arrCountTemp2[26]; for (int i = 0; i < nDictSize; i++) { memset(arrCountTemp1, 0, sizeof(arrCountTemp1)); int nSizeI = strlen(dict[i]); int j = 0, nSumI = 0; for (; j < nSizeI; j++) { arrCountTemp1[dict[i][j] - 'a']++; nSumI += arrWeight[dict[i][j] - 'a']; } if (nSizeGiven == 6 && nSizeI == 3) j = i; else j = 0; if (nSizeGiven - nSizeI >= 3) { if (nSizeI > nSizeGiven / 2) { continue; } for (; j < nDictSize; j++) { int nSizeJ = strlen(dict[j]), nSumJ = 0; if (nSizeJ + nSizeI > nSizeGiven || (nSizeJ == nSizeI && j < i)) { continue; } memset(arrCountTemp2, 0, sizeof(arrCountTemp2)); for (int k = 0; k < nSizeJ; k++) { arrCountTemp2[dict[j][k] - 'a']++; nSumJ += arrWeight[dict[j][k] - 'a']; } bool bMatch = true; for (int k = 0; k < 26; k++) { if (arrCountTemp1[k] + arrCountTemp2[k] > arrCountGiven[k]) { bMatch = false; break; } } if (bMatch) { sArrRecord[nRsSize].nScore = nSumI + nSumJ; if (strcmp(dict[i], dict[j]) > 0) { strcpy(sArrRecord[nRsSize].strRs, dict[j]); sArrRecord[nRsSize].strRs[nSizeJ] = ' '; strcpy(sArrRecord[nRsSize].strRs + nSizeJ + 1, dict[i]); } else { strcpy(sArrRecord[nRsSize].strRs, dict[i]); sArrRecord[nRsSize].strRs[nSizeI] = ' '; strcpy(sArrRecord[nRsSize].strRs + nSizeI + 1, dict[j]); } nRsSize++; } } } sArrRecord[nRsSize].nScore = nSumI; strcpy(sArrRecord[nRsSize].strRs, dict[i]); nRsSize++; } qsort(sArrRecord, nRsSize, sizeof(SRecord), compare); fileout << sArrRecord[0].nScore << endl; fileout << sArrRecord[0].strRs << endl; for (int i = 1; i < nRsSize && sArrRecord[i].nScore == sArrRecord[0].nScore; i++) { if (strcmp(sArrRecord[i].strRs, sArrRecord[0].strRs) == 0) { continue; } fileout << sArrRecord[i].strRs << endl; }}int main(){ prepairData(); process(); fileout.close(); return 0;}