NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃
 最新文章
頁: [1] 2 3 ... 10
 1 
 於: 十二月 07, 2020, 08:32:59 am 
作者 sagit - 最新文章 由 sagit
如題,有需要備份文章的請儘早。

 2 
 於: 十一月 25, 2020, 12:56:40 am 
作者 tcy - 最新文章 由 sagit
這一題先用內建的sort排序(O(nlogn)),
然後最大的一個乘上n-1,第二大的乘上n-3,
往後的每一項就是再減2,直到最小的一個乘上-(n-1),
加起來就是答案了。

 3 
 於: 十一月 24, 2020, 11:22:20 pm 
作者 tcy - 最新文章 由 tcy
您好,
想請教B.握手Problem ID: handshake這一題。

我對於題目的理解簡單來說是計算兩兩相減的絕對值總和
所以使用巢狀迴圈
for (i=0;i<n;i++)
{
        for (j=i;j<n;j++)
        {
            if(data>data[j])
            {
               sum+=data;
               sum-=data[j];
            }
       else
       {
               sum-=data;
               sum+=data[j];
       }
        }
}

但上傳判定後判定為超時
有想過其他的方法,例如先排序後再乘上係數後總和
但當天排序只有想到使用bubble sort,雖然知道是O(n^2),應該和上面的方法一樣沒有多大的幫助

今天才突然想到還有其他如Quicksort O(n log n),或許關鍵在於這個?

還是有其他更好的解法,懇請版主、版友能不吝賜教,謝謝。

 4 
 於: 十一月 16, 2020, 02:24:18 pm 
作者 sagit - 最新文章 由 sagit
用一個陣列記錄每個字母出現的次數,
而當出現次數為奇數的字母有兩個以上時就是無解,
而當出現次數為奇數的字母有一個以下時,
先從A~Z印出每個字母出現次數的一半,
接著印出出現次數為奇數的字母,
最後再從Z~A印出每個字母出現次數的一半即可。
例如A、B、C、D、E的出現次數分別為3、4、6、8、10,
則輸出ABBCCCDDDDEEEEEAEEEEEDDDDCCCBBA。

 5 
 於: 十一月 14, 2020, 12:12:40 am 
作者 sagit - 最新文章 由 sagit
如果是現場比賽,n=5時是無法即時運算出來的,
所以這題的做法是「本地建表」,
因為輸入只有1~5,寫一個程式去求出這5個數字即可。

而如果是事後要解題的,
其實維基百科有答案,可以直接抄。

 6 
 於: 十一月 12, 2020, 03:12:37 pm 
作者 sagit - 最新文章 由 sagit
就是要你實作出一顆樹,因為有 go back 的操作,所以你的指標要是雙向的,
比較容易超時的操作是在用一個節點下新增非常多的子節點,
然後請你輸出該點的所有子節點(註:題目要求只要輸出前100個),
因此子節點的記錄,我是使用 map 來完成這個操作,
整個程式主要用到的陣列如下:
代碼: [選擇]
int parent[50001];
string name[50001], path[101];
map<string,int> child[50001];
parent[ i ]記錄第 i 號節點的上層編號,
name[ i ] 記錄第 i 號節點的名字,
child[ i ]則是記錄第 i 號節點的子節點有哪些,
path是 where am I 或 where can I go 時用來輸出用的。

而主程式的操作如下:
代碼: [選擇]
int n, cur, node, pn, i;
string s, op, obj, t;
stringstream sin;
map<string,int>::iterator it;
name[0]="ground";
parent[0]=-1;
child[0].clear();
node=1;
cur=0;
cin >> n;
getline(cin, s);
while (n--)
{
getline(cin, s);
sin.clear();
sin.str(s);
sin >> op >> obj;
if (op=="dig")
{
it=child[cur].find(obj);
if (it==child[cur].end()) // Not found
{
name[node]=obj;
parent[node]=cur;
child[node].clear();
child[cur].insert(pair<string,int>(obj, node));
//child[cur][obj]=node;
node++;
}
else
{
t="'"+obj+"' exist!";
AddAnswer(t);
}
}
else if (op=="collapse")
{
it=child[cur].find(obj);
if (it==child[cur].end()) // Not found
{
t="'"+obj+"' not exist!";
AddAnswer(t);
}
else
{
child[cur].erase(it);
}
}
else if (op=="go")
{
if (obj=="to")
{
sin >> obj;
it=child[cur].find(obj);
if (it==child[cur].end()) // Not found
{
t="'"+obj+"' not exist!";
AddAnswer(t);
}
else
{
cur=child[cur][obj];
}
}
else // back
{
if (cur==0) // ground
{
t="You are on the ground!";
AddAnswer(t);
}
else cur=parent[cur];
}
}
else // where
{
if (obj=="am")
{
int ccur=cur;
for (pn=0; pn<=100; )
{
path[pn++]=name[ccur];
if (ccur==0) break;
ccur=parent[ccur];
}
if (pn<=100)
{
t=path[pn-1];
for (i=pn-2; i>=0; i--)
{
t+=(" -> "+path[i]);
}
}
else
{
t="-> "+path[99];
for (i=98; i>=0; i--)
{
t+=(" -> "+path[i]);
}
}
AddAnswer(t);
}
else // can
{
for (it=child[cur].begin(), pn=0; it!=child[cur].end(); ++it)
{
path[pn++]=it->first;
if (pn==101)
{
path[100]="...";
break;
}
}
if (pn>0) t=path[0];
else t="";
for (i=1; i<pn; i++)
{
t+=(" "+path[i]);
}
AddAnswer(t);
}
}
}
PrintAnswer();
原始的 AddAnswer 函數使用的是 char 陣列,而我將它改成使用 string。(注意要加一個換行字元)

 7 
 於: 五月 14, 2020, 10:46:38 am 
作者 sagit - 最新文章 由 sagit
每破壞一條邊,就會多一個樹堆出來,
因為只要計算這條路徑有幾條邊,
加一之後則是分散出來的樹堆有幾個。

先以起點 S 做一次 BFS 或DFS 計算出 S 到每個點的距離 Di
再將 i 值從 L 做到 R 計算 Di+1的值即可。

 8 
 於: 五月 14, 2020, 09:18:40 am 
作者 sagit - 最新文章 由 sagit
將所有的邊長相加之後為 S,
答案就是 S*6/(n*(n-1))

 9 
 於: 五月 14, 2020, 09:15:23 am 
作者 sagit - 最新文章 由 sagit
先處理特殊情況 N=1:
S0<K 輸出-1
S0=K 輸出0
S0>K 輸出P0

N>=2的情況:
先依照 S 值由大排到小,S 值相同的則依照 P 值由大排到小
如果前兩個的 S 相加之後小於 K,則輸出 -1,
接下來把這些數字切成兩段,
前面的是 Si > K,後面的則是 Si < K,
如果有找到 Si = K,則輸出 0。
前面 Si > K 的部分只要把該樹堆分裂即可,
因此找 Pi 最小的一個為 P1,
前面 Si < K 的部分則是需要兩個樹堆合併,
S 值相加之後大於 K 時才會有解,將 P 值較小的樹堆分裂,
這邊的最小值為 P2,
而若有一組 S 值相加之後等於 K,則 P2=0,
最後輸出 P1、P2 中較小的那個即可。

 10 
 於: 五月 14, 2020, 09:03:47 am 
作者 sagit - 最新文章 由 sagit
基本上應該沒什麼困難的,
每一行的數字加起來,
就是那個選手可以贏幾場,
用一次的迴圈找出最大值是多少,
再用一次的迴圈找出和最大值相同的有幾個,
最後再用一次的迴圈,印出這些人的名字。

頁: [1] 2 3 ... 10