這是前天成都網(wǎng)賽的題，比賽時(shí)候確實(shí)一點(diǎn)思路也沒有。比完之后看了人家的解題報(bào)告，還是不會(huì)怎么搜出答案，太弱了。
題意是給出N,K，求M，使得M是N的正倍數(shù)，而且M用K進(jìn)制表示后所需要的不同數(shù)字(0,1,2,3,...,k-1)最少，如果有多組
這樣的情況，求出最小的M。
很數(shù)學(xué)的題意。用到了一個(gè)結(jié)論，就是任意數(shù)字的正倍數(shù)均可以用不超過2個(gè)不同數(shù)字的數(shù)得到。
證明如下：
任意數(shù)M % N 總共有N種結(jié)果，假如有N+1個(gè)不同的M，那么肯定有2個(gè)M對(duì)N取模后的結(jié)果是相同，這個(gè)是所謂鴿巢原理。
那么，我取a,aa,aaa,...,aaaaaaaaaa....，總共N+1個(gè)，同樣滿足上面的結(jié)論。那么我取那2個(gè)對(duì)N取模相同的數(shù)字相減得到
數(shù)字aaaaa...000....，這個(gè)數(shù)字肯定是N的倍數(shù)。
綜合上面的證明，只能得到2個(gè)數(shù)字肯定能表示N的倍數(shù)。但是不能說形式就是aaaaa...000....。
到了這里我還是一點(diǎn)思路都沒有，一點(diǎn)都不知道怎么搜索。。。
想了1個(gè)多小時(shí)，無頭緒，問過了這題的同學(xué)，還是無頭緒?？唇忸}報(bào)告，他們的代碼寫得太牛了，完全看不懂，無頭緒。
也許也是我對(duì)bfs理解太淺，才看不懂他們的搜索代碼。而且，我連可以搜索的地方都沒有找到，都不知道搜什么了。
想了好久，昨天吃飯的時(shí)候，終于發(fā)現(xiàn)可以對(duì)余數(shù)進(jìn)行搜索。
對(duì)于任意的N，其余數(shù)就是范圍是[0, N -1]。這個(gè)其實(shí)就可以代表狀態(tài)了，或者代表bfs中的點(diǎn)了。從當(dāng)前余數(shù)轉(zhuǎn)移到其它
余數(shù)的是MOD * K + A 或者 MOD * K + B，如果要轉(zhuǎn)移到得余數(shù)以前沒被搜過，那就可以轉(zhuǎn)移過去。這個(gè)剛好就是一個(gè)
優(yōu)化了。也可以看成是子問題了。但是，dfs完全不行。剛開始用dfs，絕對(duì)的超時(shí)。
用dfs也是我對(duì)思路理解不深，僥幸認(rèn)為能過。。。后面發(fā)現(xiàn)，這題完全和bfs吻合。[0, N -1]剛好代表N個(gè)點(diǎn)，我要通過
從外面的一個(gè)點(diǎn)，最短的遍歷到點(diǎn)0，可以bfs或者最短路算法。這題我覺得還有個(gè)難點(diǎn)就是保存答案，因?yàn)榇鸢缸铋L的長度
可能是N(N<=10000)，所以把答案直接放到節(jié)點(diǎn)里面肯定不行的。但是，我還仔細(xì)看過算法導(dǎo)論。因此想到了可以利用bfs
搜索出來的那顆樹或者最短路算法跑出來的那顆樹，從目標(biāo)節(jié)點(diǎn)逆序?qū)ふ掖鸢?，找到出發(fā)節(jié)點(diǎn)之后，再把答案reverse一下就行了。
這題還得注意0不能是N的倍數(shù)，所以注意bfs(0,i)這種情況的處理。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_N = 10010;
int nOut[MAX_N];
int nOLen;
int nAns[MAX_N];
int nALen;
bool bMod[MAX_N];
int nFather[MAX_N];
int nChoose[MAX_N];
int nN;
int nK;
bool bFind;
int Cmp(
int* A,
int nLA,
int* B,
int nLB)
{
if (nLA != nLB)
{
return nLA - nLB;
}
for (
int i = 0; i < nLA; ++i)
{
if (A[i] != B[i])
{
return A[i] - B[i];
}
}
return 0;
}
void Bfs(
int nA,
int nB)
{
memset(bMod,
false,
sizeof(bMod));
queue<
int> que;
que.push(0);
int nTemp;
bool bFirst =
true;
bFind =
false;
if (nA > nB)swap(nA, nB);
//printf("nA:%d, nB:%d\n", nA, nB);
while (!que.empty())
{
//printf("nMod:%d\n", que.front());
int nMod = que.front();
que.pop();
if (nMod == 0)
{
if (bFirst)bFirst =
false;
else {
bFind =
true;
break;
}
}
nTemp = (nMod * nK + nA) % nN;
if (!(nMod == 0 && nA == 0) && !bMod[nTemp])
{
nFather[nTemp] = nMod;
nChoose[nTemp] = nA;
que.push(nTemp);
bMod[nTemp] =
true;
//printf("nTemp:%d\n", nTemp);
}
if (nA == nB)
continue;
nTemp = (nMod * nK + nB) % nN;
if (!bMod[nTemp])
{
nFather[nTemp] = nMod;
nChoose[nTemp] = nB;
que.push(nTemp);
bMod[nTemp] =
true;
//printf("nTemp:%d\n", nTemp);
}
}
if (bFind)
{
int nF = 0;
nALen = 0;
do {
nAns[nALen++] = nChoose[nF];
nF = nFather[nF];
}
while (nF);
reverse(nAns, nAns + nALen);
}
}
int main()
{
while (scanf("%d%d", &nN, &nK) == 2)
{
bool bOk =
false;
nOLen = 0;
for (
int i = 1; i < nK; ++i)
{
Bfs(i, i);
if (bFind)
{
if (nOLen == 0 || Cmp(nOut, nOLen, nAns, nALen) > 0)
{
nOLen = nALen;
memcpy(nOut, nAns,
sizeof(
int) * nALen);
}
bOk =
true;
}
}
if (!bOk)
for (
int i = 0; i < nK; ++i)
{
for (
int j = i + 1; j < nK; ++j)
{
Bfs(i, j);
if (bFind)
{
if (nOLen == 0 || Cmp(nOut, nOLen, nAns, nALen) > 0)
{
nOLen = nALen;
memcpy(nOut, nAns,
sizeof(
int) * nALen);
}
}
}
}
for (
int k = 0; k < nOLen; ++k)
{
printf("%d", nOut[k]);
}
printf("\n");
}
return 0;
}
用線段樹成段更新不能立即全部更新，必須搞延遲操作。其實(shí)，就是針對(duì)每個(gè)節(jié)點(diǎn)，另外搞一個(gè)域表示延遲
更新的數(shù)目。然后，在更新操作和查找操作的時(shí)候都把父親節(jié)點(diǎn)的延遲域往2個(gè)兒子走。
這個(gè)題是要成段增加值，所以在寫PushDown函數(shù)的時(shí)候要注意，只能給兒子節(jié)點(diǎn)加上父親節(jié)點(diǎn)壓過來的值
乘以兒子區(qū)間的長度。這題貌似用樹狀數(shù)組也可以做，不過解法肯定意思不是那么直白的。不過速度肯定會(huì)快。
樹狀數(shù)組解法：
http://kenby.iteye.com/blog/962159 線段樹網(wǎng)上流行的解法都是開最多節(jié)點(diǎn)數(shù)目4倍的數(shù)組。以位置1作為根，每個(gè)位置其實(shí)代表的是一個(gè)區(qū)間。
某人位置1代表1-N或者0-(N-1)區(qū)間，具體看題目了。那么2就代表區(qū)間1-(1+N)/2，3就代表區(qū)間(1+N)/2+1 - N了。
至于lazy標(biāo)記還是搞個(gè)大數(shù)組，意義和線段樹數(shù)組一樣，搞清楚之后寫起來都比較簡單，最重要的是變形來
解決一些要求奇怪的題目。
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
typedef
long long INT;
const INT MAX_N = 100010;
const INT INF = 0x7ffffffffffffffLL;
INT nTree[MAX_N << 2];
INT nAdd[MAX_N << 2];
INT nN, nQ;
void PushUp(INT nRt)
{
nTree[nRt] = nTree[nRt << 1] + nTree[nRt << 1 | 1];
}
void BuildTree(INT nL, INT nR, INT nRt)
{
nAdd[nRt] = 0;
if (nL == nR)
{
scanf("%I64d", &nTree[nRt]);
return;
}
INT nMid = (nL + nR) >> 1;
BuildTree(nL, nMid, nRt << 1);
BuildTree(nMid + 1, nR, nRt << 1 | 1);
PushUp(nRt);
}
void PushDown(INT nL, INT nR, INT nRt)
{
INT nMid = (nL + nR) >> 1;
INT nLs = nRt << 1;
INT nRs = nLs | 1;
if (nAdd[nRt])
{
nAdd[nLs] += nAdd[nRt];
nAdd[nRs] += nAdd[nRt];
nTree[nLs] += (nMid - nL + 1) * nAdd[nRt];
nTree[nRs] += (nR - nMid) * nAdd[nRt];
nAdd[nRt] = 0;
}
}
void Update(INT nL, INT nR, INT nRt, INT nX, INT nY, INT nV)
{
if (nL >= nX && nR <= nY)
{
nTree[nRt] += nV * (nR - nL + 1);
nAdd[nRt] += nV;
return;
}
PushDown(nL, nR, nRt);
INT nMid = (nL + nR) >> 1;
if (nX <= nMid) Update(nL, nMid, nRt << 1, nX, nY, nV);
if (nY > nMid) Update(nMid + 1, nR, nRt << 1 | 1, nX, nY, nV);
PushUp(nRt);
}
INT Query(INT nL, INT nR, INT nRt, INT nX, INT nY)
{
if (nL >= nX && nR <= nY)
{
return nTree[nRt];
}
PushDown(nL, nR, nRt);
INT nAns = 0;
INT nMid = (nL + nR) >> 1;
if (nX <= nMid) nAns += Query(nL, nMid, nRt << 1, nX, nY);
if (nY > nMid) nAns += Query(nMid + 1, nR, nRt << 1 | 1, nX, nY);
return nAns;
}
int main()
{
INT nTemp;
while (scanf("%I64d%I64d", &nN, &nQ) == 2)
{
BuildTree(1, nN, 1);
while (nQ--)
{
char szCmd[10];
INT nX, nY, nV;
scanf("%s", szCmd);
if (szCmd[0] == 'Q')
{
scanf("%I64d%I64d", &nX, &nY);
printf("%I64d\n", Query(1, nN, 1, nX, nY));
}
else {
scanf("%I64d%I64d%I64d", &nX, &nY, &nV);
Update(1, nN, 1, nX, nY, nV);
}
}
}
return 0;
}
直接模擬約瑟夫環(huán)是N^2，況且這題每次移動(dòng)的距離和方向都是不確定的，只能模擬，如果加快查找和移動(dòng)的話，
可以提高速度，果斷用線段樹維護(hù)當(dāng)前位置前面有多少個(gè)人。
至于反素?cái)?shù)指的是求一個(gè)小于等于N的數(shù)字，使得其因子個(gè)數(shù)在1-N中是最大的。這個(gè)利用一個(gè)必要條件暴力搜索即可。
其實(shí)就是利用下面這2個(gè)性質(zhì)搜索的。
性質(zhì)一:一個(gè)反素?cái)?shù)的質(zhì)因子必然是從2開始連續(xù)的質(zhì)數(shù)。性質(zhì)二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <math.h>
#include <algorithm>
using namespace std;
int nPrime[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int nAns;
int nCN;
const int MAX_N = 500010;
//nPow不會(huì)超過20
void InitBest(
int nCur,
int nI,
int nMax,
int nN,
int nNum)
{
if (nCur > nN)
return;
if (nNum > nCN){nAns = nCur;nCN = nNum;}
if (nNum == nCN){nAns = min(nAns, nCur);}
for (
int i = 1; i <= nMax; ++i)
{
nCur *= nPrime[nI];
if (nCur > nN)
return;
//不加這句優(yōu)化會(huì)超時(shí)
if (nI < 15)
InitBest(nCur, nI + 1, i, nN, nNum * (i + 1));
}
}
char szNames[MAX_N][10];
int nValue[MAX_N];
int nTree[MAX_N << 2];
void PushUp(
int nRt)
{
nTree[nRt] = nTree[nRt << 1] + nTree[nRt << 1 | 1];
}
void BuildTree(
int nL,
int nR,
int nRt,
int nV)
{
if (nL == nR)
{
nTree[nRt] = nV;
return;
}
int nMid = (nL + nR) >> 1;
BuildTree(nL, nMid, nRt << 1, nV);
BuildTree(nMid + 1, nR, nRt << 1 | 1, nV);
PushUp(nRt);
}
void Add(
int nL,
int nR,
int nRt,
int nP,
int nV)
{
if (nL == nR)
{
nTree[nRt] += nV;
}
else {
int nMid = (nL + nR) >> 1;
if (nP <= nMid)Add(nL, nMid, nRt << 1, nP, nV);
else Add(nMid + 1, nR, nRt << 1 | 1, nP, nV);
PushUp(nRt);
}
}
int Query(
int nL,
int nR,
int nRt,
int nSum)
{
if (nL == nR)
{
return nL;
}
int nMid = (nL + nR) >> 1;
int nLs = nRt << 1;
int nRs = nLs | 1;
if (nTree[nLs] >= nSum)
return Query(nL, nMid, nLs, nSum);
else return Query(nMid + 1, nR, nRs, nSum - nTree[nLs]);
}
int main()
{
//InitBest(1, 0, 15);
int nN, nK;
while (scanf("%d%d", &nN, &nK) == 2)
{
nK--;
nAns = 2;
nCN = 0;
InitBest(1, 0, 20, nN, 1);
//printf("ans:%d cn:%d\n", nAns, nCN);
for (
int i = 0; i < nN; ++i)
{
scanf("%s%d", szNames[i], &nValue[i]);
}
BuildTree(0, nN - 1, 1, 1);
int nTotal = nN;
int nPos;
for (
int i = 0; i < nAns; ++i)
{
nPos = Query(0, nN - 1, 1, nK + 1);
//printf("nK:%d %s %d\n", nK, szNames[nPos], nValue[nPos]);
nTotal--;
Add(0, nN - 1, 1, nPos, -1);
if (!nTotal)
break;
if (nValue[nPos] >= 0)
{
nK = (nK - 1 + nValue[nPos] + nTotal) % nTotal;
}
else {
nK = ((nK + nValue[nPos]) % nTotal + nTotal) % nTotal;
}
}
printf("%s %d\n", szNames[nPos], nCN);
}
return 0;
}
此題是求一個(gè)數(shù)字序列中，長度為3的子序列(a,b,c)，且滿足條件a<=b<=c或者c<=b<=a的子序列的個(gè)數(shù)。
明顯枚舉每個(gè)b，求每個(gè)b左邊的a的個(gè)數(shù)和右邊c的個(gè)數(shù)，以及左邊c的個(gè)數(shù)和右邊a的個(gè)數(shù)，然后累加左右乘積求和即可。
剛開始只求了滿足條件a<=b<=c的部分，而且忘記用64位了。wa了幾次。求左邊a的個(gè)數(shù)其實(shí)就是求小于等于b的數(shù)字
的個(gè)數(shù)，這個(gè)剛好可以用樹狀數(shù)組或者線段樹求。具體見代碼。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
typedef
long long INT;
const INT MAX_N = 100010;
const INT N = 20010;
INT nN;
INT nNum[N];
INT nTree[MAX_N + 10];
INT nLeft[2][N], nRight[2][N];
INT LowBit(INT nI)
{
return nI & (-nI);
}
void Add(INT nI, INT nAdd)
{
while (nI <= MAX_N)
{
nTree[nI] += nAdd;
nI += LowBit(nI);
}
}
INT Query(INT nPos)
{
INT nAns = 0;
while (nPos > 0)
{
nAns += nTree[nPos];
nPos -= LowBit(nPos);
}
return nAns;
}
int main()
{
INT nT;
scanf("%I64d", &nT);
while (nT--)
{
scanf("%I64d", &nN);
memset(nTree, 0,
sizeof(nTree));
for (INT i = 1; i <= nN; ++i)
{
scanf("%I64d", &nNum[i]);
nLeft[0][i] = Query(nNum[i]);
nLeft[1][i] = Query(MAX_N) - Query(nNum[i] - 1);
Add(nNum[i], 1);
}
memset(nTree, 0,
sizeof(nTree));
for (INT i = nN; i >= 1; --i)
{
nRight[0][i] = Query(MAX_N) - Query(nNum[i] - 1);
nRight[1][i] = Query(nNum[i]);
Add(nNum[i], 1);
}
INT nAns = 0;
for (INT i = 1; i <= nN; ++i)
{
nAns += nLeft[0][i] * nRight[0][i] + nLeft[1][i] * nRight[1][i];
}
printf("%I64d\n", nAns);
}
return 0;
}
這個(gè)題意思是翻轉(zhuǎn)一個(gè)01立方體。翻轉(zhuǎn)多次后再查詢某個(gè)點(diǎn)的值。
還是利用上一篇文章的思想，把翻轉(zhuǎn)操作轉(zhuǎn)換為單點(diǎn)更新操作。把查詢操作轉(zhuǎn)換為利用樹狀數(shù)組查詢和的方式。
這樣每次操作的復(fù)雜度都是logN的3次。而直接翻轉(zhuǎn)立方體的復(fù)雜度是N的3次。
這個(gè)題最麻煩的地方是空間想象能力。因?yàn)橐D(zhuǎn)8個(gè)點(diǎn)才能完成一次立方體翻轉(zhuǎn)。比如，翻轉(zhuǎn)(x,y,z)相當(dāng)于
以該點(diǎn)作為左上角做一個(gè)無限立方體，把該立方體翻轉(zhuǎn)。這樣就會(huì)翻轉(zhuǎn)多余的部分，那么需要把多翻轉(zhuǎn)的部分翻轉(zhuǎn)
回來。最后的思考結(jié)果發(fā)現(xiàn)，只要對(duì)每個(gè)頂點(diǎn)翻轉(zhuǎn)一次即可。至于為什么這樣，自己去計(jì)算重復(fù)翻轉(zhuǎn)的部分就會(huì)明白
了。剛好確實(shí)是把每個(gè)點(diǎn)翻轉(zhuǎn)了一次。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
const int MAX_N = 110;
int nSum[MAX_N + 10][MAX_N + 10][MAX_N + 10];
int nN, nM;
int LowBit(
int nPos)
{
return nPos & (-nPos);
}
void Add(
int nX,
int nY,
int nZ)
{
for (
int i = nX; i <= nN; i += LowBit(i))
{
for (
int j = nY; j <= nN; j += LowBit(j))
{
for (
int k = nZ; k <= nN; k += LowBit(k))
{
nSum[i][j][k]++;
}
}
}
}
int Query(
int nX,
int nY,
int nZ)
{
int nAns = 0;
for (
int i = nX; i > 0; i -= LowBit(i))
{
for (
int j = nY; j > 0; j -= LowBit(j))
{
for (
int k = nZ; k > 0; k -= LowBit(k))
{
nAns += nSum[i][j][k];
}
}
}
return nAns;
}
int main()
{
int nCmd;
int nX, nY, nZ;
int nX1, nY1, nZ1;
int nX2, nY2, nZ2;
while (scanf("%d%d", &nN, &nM) == 2)
{
memset(nSum, 0,
sizeof(nSum));
while (nM--)
{
scanf("%d", &nCmd);
if (nCmd == 0)
{
scanf("%d%d%d", &nX, &nY, &nZ);
printf("%d\n", Query(nX, nY, nZ) % 2);
}
else {
scanf("%d%d%d%d%d%d", &nX1, &nY1, &nZ1, &nX2, &nY2, &nZ2);
if (nX1 > nX2)swap(nX1, nX2);
if (nY1 > nY2)swap(nY1, nY2);
if (nZ1 > nZ2)swap(nZ1, nZ2);
Add(nX1, nY1, nZ1);
Add(nX2 + 1, nY1, nZ1);
Add(nX1, nY2 + 1, nZ1);
Add(nX1, nY1, nZ2 + 1);
Add(nX1, nY2 + 1, nZ2 + 1);
Add(nX2 + 1, nY1, nZ2 + 1);
Add(nX2 + 1, nY2 + 1, nZ1);
Add(nX2 + 1, nY2 + 1, nZ2 + 1);
}
}
}
return 0;
}
這個(gè)題的意思是給定一個(gè)長為N的區(qū)間。不斷的給某個(gè)子區(qū)間[A,B]中的每個(gè)點(diǎn)涂一次色。最后問每個(gè)點(diǎn)的涂色次數(shù)。
這個(gè)題貌似可以擴(kuò)展到多維的情況，但是多維的情況下必須用樹狀數(shù)組求和以加快速度，一維的情況直接求和即可。
假如，第一次涂色是對(duì)區(qū)間[A,B]涂色一次，可以讓nNum[nA]++,nNum[nB+1]--即可。因?yàn)檫@樣對(duì)于區(qū)間[0,nA-1]的任意值i有
都要nNum[1]+nNum[2]+...+nNum[i] = 0。而對(duì)于區(qū)間[nA,nB]的任意值i有nNum[1]+nNum[2]+...+nNum[i] = 0。
對(duì)于區(qū)間[nB+1, nN]的任意值i有nNum[1]+nNum[2]+...+nNum[i] = 0。
那么重復(fù)多次了。如果上述求和nNum[1]+nNum[2]+...+nNum[i] 剛好代表每個(gè)結(jié)點(diǎn)i的涂色次數(shù)，那么這個(gè)題就可解了。
用例子驗(yàn)證一下，發(fā)現(xiàn)肯定是這樣的。證明略了。
至于樹狀數(shù)組網(wǎng)上一大堆資料。樹狀數(shù)組模板單一，敲代碼太方便了。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
int nNum[100000 + 10];
int nN;
int LowBit(
int nI)
{
return nI & (-nI);
}
void Add(
int nI,
int nAdd)
{
while (nI <= nN)
{
nNum[nI] += nAdd;
nI += LowBit(nI);
}
}
int GetSum(
int nI)
{
int nAns = 0;
while (nI > 0)
{
nAns += nNum[nI];
nI -= LowBit(nI);
}
return nAns;
}
int main()
{
int nA, nB;
while (scanf("%d", &nN), nN)
{
memset(nNum, 0,
sizeof(nNum));
for (
int i = 1; i <= nN; ++i)
{
scanf("%d%d", &nA, &nB);
Add(nA, 1);
Add(nB + 1, -1);
}
for (
int i = 1; i <= nN; ++i)
{
printf("%d%s", GetSum(i), i == nN ? "\n" : " ");
}
}
return 0;
}
這個(gè)題是求次短路。有個(gè)不錯(cuò)的解法，是根據(jù)一個(gè)結(jié)論，替換調(diào)最短路里面的一條邊肯定能得到次短路。
那么，只要枚舉所有邊就可以了。比如，假設(shè)開始點(diǎn)為s，目標(biāo)點(diǎn)是d，設(shè)最短路為dis(s,d)。對(duì)于邊(u,v)，
dis(s, u) + w(u, v) + dis(v, d) 大于dis(s, d)，則該路徑就可能是次短路。求出最小的大于dis(s,d)的值就可以了。
方式是從s開始和從d開始進(jìn)行2次單源多終點(diǎn)最短路徑算法。然后枚舉邊即可。
該算法可以這樣理解。因?yàn)樘鎿Q最短路徑里面的邊，路徑的長度只會(huì)變大或者不變。如果存在讓更短路徑變小的邊，
這本身就與最短路徑是矛盾的。所以替換2條或者更多的邊只會(huì)讓路徑變得更大。因此，只需考慮替換一條邊的情況
即可。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAX_N = 5000 + 10;
struct Edge
{
int nE;
int nDis;
Edge(
int e,
int d):nE(e), nDis(d) {}
};
vector<Edge> graph[MAX_N];
bool bVisit[MAX_N];
int nSDis[MAX_N];
int nEDis[MAX_N];
struct Node
{
int nN;
int nDis;
bool operator < (
const Node& node)
const {
return nDis > node.nDis;
}
};
int ShortestPath(
int nS,
int nE,
int* nDis,
int nN)
{
priority_queue<Node> pq;
memset(bVisit,
false,
sizeof(bVisit));
for (
int i = 1; i <= nN; i++)
{
nDis[i] = 0x7fffffff;
}
nDis[nS] = 0;
Node head;
head.nDis = 0, head.nN = nS;
pq.push(head);
while (pq.empty() ==
false)
{
Node head = pq.top();
pq.pop();
int nU = head.nN;
if (bVisit[nU])
continue;
bVisit[nU] =
true;
for (
int i = 0; i < graph[nU].size(); ++i)
{
int nV = graph[nU][i].nE;
int nLen = head.nDis + graph[nU][i].nDis;
if (nLen < nDis[nV])
{
nDis[nV] = nLen;
Node node;
node.nDis = nLen;
node.nN = nV;
pq.push(node);
}
}
}
return nDis[nE];
}
int Second(
int nS,
int nE,
int nN)
{
int nShortest = ShortestPath(nS, nE, nSDis, nN);
ShortestPath(nE, nS, nEDis, nN);
int nAns = 0x7fffffff;
for (
int i = 1; i <= nN; ++i)
{
for (
int j = 0; j < graph[i].size(); ++j)
{
int nU = i;
int nV = graph[i][j].nE;
int nLen = nSDis[i] + graph[i][j].nDis + nEDis[nV];
if (nLen != nShortest)
{
nAns = min(nAns, nLen);
}
}
}
return nAns;
}
int main()
{
int nN, nR;
int nA, nB, nD;
while (scanf("%d%d", &nN, &nR) == 2)
{
for (
int i = 1; i <= nN; ++i)
{
graph[i].clear();
}
while (nR--)
{
scanf("%d%d%d", &nA, &nB, &nD);
graph[nA].push_back(Edge(nB, nD));
graph[nB].push_back(Edge(nA, nD));
}
printf("%d\n", Second(1, nN, nN));
}
return 0;
}
這道題的意思是給定一個(gè)長N的整數(shù)序列，用一個(gè)大小為K的窗口從頭開始覆蓋，問第1-第N-K次窗口里面最大的數(shù)字和最小的數(shù)字。
剛開始還以為優(yōu)先級(jí)隊(duì)列可以做，發(fā)現(xiàn)無法刪除最前面的元素。估計(jì)用線段樹這個(gè)題也是可以解得。用這個(gè)題學(xué)了下單調(diào)隊(duì)列。
單調(diào)隊(duì)列正如其名，是一個(gè)從小到大排序的隊(duì)列，而且能夠保證所有的元素入隊(duì)列一次出隊(duì)列一次，所以平攤到每個(gè)元素的復(fù)雜度
就是O(1)。
對(duì)于這個(gè)題單調(diào)隊(duì)列的使用。以序列
1 3 -1 -3 5 3 6 7舉例。 1）元素類型：一個(gè)結(jié)構(gòu)體，包含數(shù)字大小和位置，比如(1，1），（3，2）。
2）插入操作：從隊(duì)尾開始查找，把隊(duì)尾小于待插入元素的元素全部刪除，再加入待插入的元素。這個(gè)操作最壞的
情況下是O(n)，但是我們采用聚集分析的方法，知道每個(gè)元素最多刪除一次，那么N個(gè)元素刪除N次，平攤到每一次
操作的復(fù)雜度就是O(1)了。
3）刪除隊(duì)首元素：比如本文給的那個(gè)題，窗口一直往后移動(dòng)，每一次移動(dòng)都會(huì)刪除一個(gè)元素，所以很可能隊(duì)首會(huì)是要
刪除的元素，那么每次移動(dòng)窗口的元素要進(jìn)行一次檢查，如果隊(duì)首元素失效的話，就刪掉隊(duì)首元素。
代碼的實(shí)現(xiàn)，我是包裝deque實(shí)現(xiàn)了一個(gè)模版類。速度很不好，居然跑了11s多才過，幸虧給了12s的時(shí)間，看status又500多ms
就過了的。估計(jì)數(shù)組實(shí)現(xiàn)會(huì)快很多。
代碼如下：
#include <stdio.h>
#include <deque>
#include <algorithm>
using namespace std;
#define MAX_N (1000000 + 100)
int nNum[MAX_N];
int nN, nK;
struct Small
{
int nValue;
int nIndex;
Small(
int nV,
int index):nValue(nV), nIndex(index) {}
bool operator < (
const Small& a)
const {
return nValue < a.nValue;
}
};
struct Big
{
int nValue;
int nIndex;
Big(
int nV,
int index):nValue(nV), nIndex(index) {}
bool operator < (
const Big& a)
const {
return nValue > a.nValue;
}
};
//單調(diào)隊(duì)列
template <typename T>
class Monoque
{
deque<T> dn;
public:
void Insert(T node)
{
int nPos = dn.size() - 1;
while (nPos >=0 && node < dn[nPos])
{
--nPos;
dn.pop_back();
}
dn.push_back(node);
}
int Top()
{
return dn.front().nValue;
}
void Del(
int nBeg,
int nEnd)
{
if (dn.size() > 0)
{
if (dn.front().nIndex < nBeg || dn.front().nIndex > nEnd)
{
dn.pop_front();
}
}
}
};
int main()
{
while (scanf("%d%d", &nN, &nK) == 2)
{
int i;
for (i = 0; i < nN; ++i)
{
scanf("%d", &nNum[i]);
}
Monoque<Small> minQ;
Monoque<Big> maxQ;
for (i = 0; i < nK; ++i)
{
minQ.Insert(Small(nNum[i], i));
}
for (i = 0; i < nN - nK; ++i)
{
printf("%d ", minQ.Top());
minQ.Insert(Small(nNum[i + nK], i + nK));
minQ.Del(i + 1, i + nK);
}
printf("%d\n", minQ.Top());
for (i = 0; i < nK; ++i)
{
maxQ.Insert(Big(nNum[i], i));
}
for (i = 0; i < nN - nK; ++i)
{
printf("%d ", maxQ.Top());
maxQ.Insert(Big(nNum[i + nK], i + nK));
maxQ.Del(i + 1, i + nK);
}
printf("%d\n", maxQ.Top());
}
return 0;
}
這是一個(gè)動(dòng)態(tài)規(guī)劃題，據(jù)說是背包問題的變形。我動(dòng)態(tài)規(guī)劃做得很少，解法一直按照算法導(dǎo)論的思想分解重疊子問題。
題意是用錢盡可能多的買物品，每種物品買一個(gè)，問有多少種買法。
我也想不出這是什么背包問題的變形，沒做過幾個(gè)背包問題，也沒看過背包九講。還是堅(jiān)持認(rèn)為正確的用狀態(tài)描述成子問題
就一定能解題的。今天和隊(duì)友在做專題時(shí)候做到這個(gè)題，我一直做了一上午都沒出來。
后面發(fā)現(xiàn)了個(gè)性質(zhì)就可以直接轉(zhuǎn)換為類似最簡單的背包問題了。排序物品價(jià)值，從最大物品開始分解子問題，用剩余物品數(shù)
和錢描述問題的狀態(tài)。
當(dāng)前物品是否必須取，是根據(jù)當(dāng)前的錢把剩下的物品全買了之后剩下的錢還是否大于當(dāng)前物品的價(jià)值，
如果大于就必須買，否則可以買或者不買。 為了正確描述問題的狀態(tài)，必須事先排序價(jià)值數(shù)組，因?yàn)榕判蛑罂梢员ＷC不能買當(dāng)前物品的時(shí)候一定不能買前面的物品，
那么我們對(duì)前面物品的處理就是正確的了。至此可以進(jìn)行最簡單的子問題分解了。到最后物品處理完之后（物品數(shù)為0），如果錢
一點(diǎn)都沒減少，那么(0, M) = 0，否則(0, M) = 1。注意這個(gè)邊界處理，否則會(huì)wa。
所以，需要先對(duì)價(jià)值數(shù)組排序，并計(jì)算出表示前N個(gè)物品價(jià)值和的數(shù)組。
做不出來的時(shí)候，翻了下別人的解法，一頭霧水?？磥磉€是算法導(dǎo)論的思想指導(dǎo)意義大多了。。。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
typedef
long long INT;
INT nAns[40][1010];
INT nValue[100];
INT nSum[100];
INT nN, nM;
INT GetAns(INT nNum, INT nMoney)
{
if (nAns[nNum][nMoney] == -1)
{
if (nNum == 0)
{
nAns[nNum][nMoney] = 1;
if (nMoney == nM)
{
nAns[nNum][nMoney] = 0;
}
}
else {
INT nRet = 0;
if (nMoney - nSum[nNum - 1] >= nValue[nNum])
{
nRet = GetAns(nNum - 1, nMoney - nValue[nNum]);
}
else {
if (nMoney >= nValue[nNum])
{
nRet += GetAns(nNum - 1, nMoney - nValue[nNum]);
}
nRet += GetAns(nNum - 1, nMoney);
}
nAns[nNum][nMoney] = nRet;
}
}
return nAns[nNum][nMoney];
}
int main()
{
INT nT;
scanf("%I64d", &nT);
for (INT i = 1; i <= nT; ++i)
{
scanf("%I64d%I64d", &nN, &nM);
for (INT j = 1; j <= nN; ++j)
{
scanf("%I64d", &nValue[j]);
}
memset(nAns, -1,
sizeof(nAns));
sort(nValue + 1, nValue + nN + 1);
nSum[0] = 0;
for (INT j = 1; j <= nN; ++j)
{
nSum[j] = nSum[j - 1] + nValue[j];
}
printf("%I64d %I64d\n", i, GetAns(nN, nM));
}
return 0;
}
題意比較糾結(jié)，搜索了把題意。
給你一個(gè)素?cái)?shù)P(P<=30000)和一串長為n的字符串str[]。字母'*'代表0，字母a-z分別代表1-26，這n個(gè)字符所代表的數(shù)字分別代表
f(1)、f(2)....f(n)。定義: f (k) = ∑
0<=i<=n-1a
ik
i (mod p) (1<=k<=n,0<=ai<P)，求a0、a1.....an-1。題目保證肯定有唯一解。
解題思路：高斯消元。根據(jù)上面的公式顯然可以列出有n個(gè)未知數(shù)的n個(gè)方程式：
a0*1^0 + a1*1^1+a2*1^2+........+an-1*1^(n-1) = f(1)
a0*2^0 + a1*2^1+a2*2^2+........+an-1*2^(n-1) = f(2)
..............
a0*n^0 + a1*n^1+a2*n^2+........+an-1*n^(n-1) = f(n)
然后采用高斯消元法來解上面的方程組即可。
典型的高斯消元題，只是多了個(gè)modP，因此計(jì)算過程中可能需要擴(kuò)展歐幾里德算法。
說下所謂的高斯消元的思路，其實(shí)可以參看維基百科，
http://zh.wikipedia.org/wiki/%E9%AB%98%E6%96%AF%E6%B6%88%E5%8E%BB%E6%B3%95，大致過程是一直消變量。
比如剛開始，消第一個(gè)變量，消完之后只讓第一個(gè)方程含有第一個(gè)變量，然后消第二個(gè)變量，消完之后只讓第二個(gè)方程含第二個(gè)變量，以此
下去讓最后的方程含最后一個(gè)變量，而且最后一個(gè)方程中對(duì)于前N-1個(gè)變量的系數(shù)都是0，這樣就能解出這N個(gè)變量了。
關(guān)于自由元指的是這個(gè)變量可以取任何值，得出這樣的結(jié)論是在消變量的過程中發(fā)現(xiàn)該變量的在第row個(gè)方程到第N方程中的系數(shù)都是0了，
所以可以取任何值。判斷無解的方式是，第row+1到第N個(gè)方程在高斯消元之后所有的系數(shù)必定是0，所以方程的值也必須是0。
求方程的解得過程是從N個(gè)解開始逆推，第N-1個(gè)方程也就包含2個(gè)變量了，第N個(gè)變量和第N-1個(gè)變量，以此下去，就可以解出方程組了。
具體的可以參照維基百科和代碼仔細(xì)分析。還有演算法筆記上也有高斯消元的解釋。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
#define MAX (70 + 10)
int nMatrix[MAX][MAX];
int nAns[MAX];
void InitMatrix(
char* szStr,
int nN,
int nP)
{
memset(nMatrix, 0,
sizeof(nMatrix));
for (
int i = 0; i < nN; ++i)
{
nMatrix[i][nN] = (szStr[i] == '*' ? 0 : szStr[i] - 'a' + 1);
}
for (
int i = 0; i < nN; ++i)
{
int nTemp = 1;
for (
int j = 0; j < nN; ++j)
{
nMatrix[i][j] = nTemp;
nTemp = (nTemp * (i + 1)) % nP;
}
}
}
int egcd(
int nA,
int nB,
int& nX,
int& nY)
{
if (nA < nB)swap(nA, nB);
if (nB == 0)
{
nX = 1, nY = 0;
return nA;
}
int nRet = egcd(nB, nA % nB, nX, nY);
int nT = nX;
nX = nY;
nY = nT - (nA / nB) * nY;
return nRet;
}
int Gauss(
int nN,
int nP)
{
int nR, nC;
for (nR = nC = 0; nR < nN && nC < nN; ++nR, ++nC)
{
if (nMatrix[nR][nC] == 0)
{
for (
int i = nR + 1; i < nN; ++i)
{
if (nMatrix[i][nC])
{
for (
int j = nC; j <= nN; ++j)
{
swap(nMatrix[nR][j], nMatrix[i][j]);
}
break;
}
}
}
if (nMatrix[nR][nC] == 0)
{
nR--;
//自由元
continue;
}
int nA = nMatrix[nR][nC];
for (
int i = nR + 1; i < nN; ++i)
{
if (nMatrix[i][nC])
{
int nB = nMatrix[i][nC];
for (
int j = nC; j <= nN; ++j)
{
nMatrix[i][j] = (nMatrix[i][j] * nA - nMatrix[nR][j] * nB) % nP;
}
}
}
}
for (
int i = nR; i < nN; ++i)
{
if (nMatrix[i][nN])
{
return -1;
//無解
}
}
int nX, nY;
for (
int i = nN - 1; i >= 0; i--)
{
int nSum = 0;
for (
int j = i + 1; j < nN; ++j)
{
nSum = (nSum + nMatrix[i][j] * nAns[j]) % nP;
}
nSum = (nMatrix[i][nN] - nSum + nP * nP) % nP;
egcd(nP, (nMatrix[i][i] + nP) % nP, nX, nY);
nY = (nY + nP) % nP;
nAns[i] = (nY * nSum + nP) % nP;
//第i個(gè)解
}
return 1 << (nN - nR);
//返回解的個(gè)數(shù),本題有唯一解
}
int main()
{
int nT;
scanf("%d", &nT);
while (nT--)
{
int nP;
int nN;
char szStr[MAX];
scanf("%d%s", &nP, szStr);
nN = strlen(szStr);
InitMatrix(szStr, nN, nP);
Gauss(nN, nP);
for (
int i = 0; i < nN; ++i)
{
printf("%d%s", nAns[i], i == nN - 1 ? "\n" : " ");
}
}
return 0;
}