NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » b821213 的個人資料 » 顯示文章
 文章

顯示文章

這裡允許您檢視這個會員的所有文章。請注意, 您只能看見您有權限閱讀的文章。

文章 - b821213

頁: [1] 2
1
此外本題中要注意到題目所謂的"一筆畫"是就邊而言,不一定每個點都要有走到。
所以在判定連通塊的時候要特別注意,假如輸入沒有任何邊,也算是YES。反正就是有邊的點才必須在連通塊內就是了。

還有上面忘記提到,如果奇點有兩個,因為不知道哪個是起點哪個是終點,我們必須枚舉然後添邊。例如說確定 x 是起點而 y 是終點,我們就加一條邊 y->x,這樣子原圖就變回沒有奇點的圖,並且因為這條邊在原圖中不會用到,所以不影響解。

最後提供另一種想法,基於可行流的啟發。

如果我們找出一條路徑從 a 到 b
其中 delta(a) > 0 ,delta(b) < 0
把這條路徑上的邊統統反轉,那麼路徑上除了 a,b 兩點以外的點 delta 都不會變
而兩點的 delta 絕對值都會 -1
這樣子的代價就是該條路徑的長度(每條路徑的權重都是 1)
想辦法把整張圖的 delta 都消到 0 ,圖上就存在一筆劃方案了
然而要特別注意的是,一條邊只能夠用一次(不然就不是一筆劃了)

因此可以想成是 "找若干點出發到若干點的路徑,路徑彼此不交錯且總權最短" 的問題
顯然這就是 flow 的經典應用。

於是新增一個 s 和一個 t,對於每個 delta > 0 的點 x
從 s 出發連出一條邊權是 0 ,容量是 delta(x)/2 的邊
對於每個 delta < 0 的點 y,連出一條邊權是 0 ,容量是 -delta(y)/2 的邊
然後將所有其他邊的容量設為 1,做 s->t 的最小費用最大流
解的值就是所花費的費用

和上面的算法相比,複雜度當然主要取決於min_cost_max_flow的算法
但是就點數和邊數來看

上面 點數 e+n+2 邊數 3*e+n
下面 點數 n+2     邊數 e+n

因此複雜度下者較優。假使原圖是完全圖,兩者的差異就很明顯了。

2
以前我是新手時老實說看不懂樓上為什麼要那樣做。現在看懂了來獻醜解說一下:

樓上的作法事實上是把整張圖視為無向圖,全部重新決定每條邊的方向,使得圖滿足任意一點x

in_degree(x) = out_degree(x)

假設每個點x的度數為 deg(x) (包含原圖的入度和出度)
那麼設計一個匯點 t ,把每個原圖上的點x連接一條容量是 deg(x)/2 的邊到匯點
這樣就可以保證該點的出度是正確的,進而保證入度數量也正確

而每條邊都一定要走過一次,所以把每條邊視為一個點y,設計一個源點s連到每個y,該條新增邊的容量設為1。
對於每個y,把逆轉視為"成本",於是假如原先邊的方向是u->v
建立一條新邊 y->v ,代表照原本的方向走即可,所以成本是0
建立另一條新邊 y->u,代表要逆轉,所以成本是1
因為兩條邊只能選一條並且該條只能走一次,容量當然設定為1。

最後就是最小花費最大流,總成本當然就是解。

3
NPSC2011高中組初賽 / Re: pF. 英雄 Fantasy for you
« 於: 十一月 30, 2011, 06:42:25 pm »
引用
這題時限相當寬鬆,離散化後用BIT維護的笨方法也可以過.......

這樣做的複雜度錯了嗎?

當然沒錯,但是常數和編程複雜度大錯特錯XDD

4
NPSC2011高中組初賽 / Re: pF. 英雄 Fantasy for you
« 於: 十一月 28, 2011, 09:31:03 pm »
這題時限相當寬鬆,離散化後用BIT維護的笨方法也可以過.......

今年的出題團隊真是超級好心。

期待pB的補完

5
NPSC2011高中組初賽 / Re: pC. 摩斯密碼
« 於: 十一月 26, 2011, 06:18:02 pm »
這種類型的題目,構造trie感覺是比較正直一點的作法......就算密碼超級長也可以很快XD

6
NPSC2010國中組決賽 / Re: [Pascal]C.魔法气泡
« 於: 十一月 25, 2011, 11:00:39 pm »
在ZJ上看到有些人的程序有點慢,也不知道原因為何......

我的作法中不全然是H*W^C,因為還要建邊決定可行轉移對象們

最差的狀況可能會到達 H*(W^C)^2 (如果任兩個狀態都可以轉移的話),但速度依舊夠快

在ZJ上執行時間8ms,補個C++ code給不懂pascal的人參考

代碼: [選擇]
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

vector <int> e[1000];

long long dp[14][1000];
int now[6];
int nv;
int m[6];
int h,w,c;

void match(int s){

if( s==w ){
int v = 0;
for(int i=0;i<w;++i)
v = v*3 + m[i];
e[nv].push_back(v);
}

else {
bool ok[3]={1,1,1};
if( s > 0 ) ok[m[s-1]] = 0;
ok[now[s]] = 0;
for(int i=0;i<3;++i)
if( ok[i] )
m[s] = i , match(s+1);
}

}

void dfs(int s){

if( s==w ){
nv = 0;
for(int i=0;i<w;++i)
nv = nv*3 + now[i];
dp[0][nv] = 1;
match(0);
}

else {
for(int i=0;i<3;++i)
if( !s || i != now[s-1] )
now[s] = i , dfs(s+1);
}

}

int main(){

int t;

scanf("%d",&t);

while(t--){

scanf("%d %d %d",&h,&w,&c);
if( c==1 ) puts("0");
else if( c==2 ) puts("2");
else {

int max = 1;
for(int i=0;i<w;++i)
max*=3;

for(int i=0;i<h;++i)
memset(dp[i],0,sizeof(long long)*max);

for(int i=0;i<max;++i)
e[i].clear();

dfs(0);

//for(int i=0;i<max;++i)
// printf("%d %d\n",i,dp[0][i]);

for(int i=1;i<h;++i)
for(int j=0;j<max;++j)
for(int k=0;k<e[j].size();++k)
dp[i][j] += dp[i-1][e[j][k]];

long long ans = 0;
for(int i=0;i<max;++i)
ans += dp[h-1][i];

printf("%lld\n",ans);
}

}

return 0;
}


是說國中組就考DP,而且還是狀態壓縮的,有點變態......

果然擋不住現代的國中生了嘛 0.0

7
NPSC2005高中組決賽 / NPSC 2005 高中組 決賽 D. 道具整理
« 於: 十一月 13, 2011, 08:39:31 pm »
基本上就是把每個物品分開算的暴力搜尋,我寫得不是很好,因此作法僅供參考。

首先如果我們直接枚舉每次把哪兩個合在一起

那麼複雜度是 O((n^2)*n!),其中n最大到10,顯然有點卡。

可行性剪枝很基本,這裡就不提了。

優化1.

我們觀察一下問題,發現重點是決定哪些物品欄最後應該合在一起成為一群。

而同一群中的物品符合交換律,可以亂合一通,所以我們總是枚舉當前第一個物品要跟誰結合,如此一來複雜度就降到了n*(n!)

優化2.

在觀察一下問題,我們發現除非兩個加起來剛好是該物品的最大容量,否則已經處理好的格子每次只會+1,而前述狀況會+2。所以說當現在的情況中能找到兩個合起來剛剛好的,那就一定要這樣做比較好。可是如果序列沒有序,這個檢查的動作就要n^2,因此我們必須維護整個序列是有序的,複雜度跟優化1情形一樣。

優化3.

嚴格說起來這也不算優化......就是優化1其實是有瑕疵的。一種特殊情況下優化1會丟失解,就是第一項物品再也不需要跟別人合了,這意味著格子1的物品數量必須剛好是剩下的渣渣。這種情況下視為把格子1丟掉照樣求解。注意要記錄丟過渣渣了沒,不然可能會丟兩次三次造成wa。

優化4經實驗似乎沒什麼效果,就是先把小的跟大的合在一起,實驗結果顯示無差別......

底下附代碼提供debug


#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;

char s[10][20]={
   "RedWater","OrangeWater","BlueWater","WhiteWater",
   "Arrow","Bolt","BrozenArrow","BrozenBolt","IronArrow","IronBolt"
};

int tellme(char* p){
   for(int i=0;i<10;++i)
      if( !strcmp(p,s) ) return i;
   return -1;
}

int item[10][10];
int is[10];
int now[10];
int best;
int m;
int sp;
bool sped = 0;

void dfs(int lv,int nown){
   
   if( lv + nown/2 >= best ) return;
   if( nown <= 1 ){
      if( lv < best ) best = lv;
      return;
   }
   
   for(int i=0,j=nown-1;i<j;++i){
      while( now+now[j] > m && i<j ) --j;
      if( i!=j && now+now[j] == m ){
         --nown ,swap(now[j],now[nown]);
         --nown ,swap(now,now[nown]);
         dfs(lv+1,nown);
         swap(now,now[nown]),++nown;
         swap(now[j],now[nown]),   ++nown;
         return;
      }
   }
   
   
   if( now[0]==sp && !sped ){
      for(int i=0;i<nown-1;++i)
         now = now[i+1];
      sped = 1;
      dfs(lv,nown-1);
      sped = 0;
      for(int i=nown-1;i>0;--i)
         now = now[i-1];
      now[0] = sp;
      return;
   }
      
   int ori = now[0];
   
   for(int i=nown-1;i>0;--i){
      
      if( i<nown-1 && now == now[i+1] ) continue;
      int hold = now;

      if( now[0]+now > m ){ //now[0]搬到now還有剩,但一定比原本的少,序列依舊有序
         
         now[0] -= m-now;
         
         for(int j=i;j<nown-1;++j)
            now[j] = now[j+1];   
               
         dfs(lv+1,nown-1);
         
         for(int j=nown-1;j>i;--j)
            now[j] = now[j-1];
         
         now = hold ,now[0] = ori;
      }
      
      else {               //now[0]+now < m         
         
         now[0] += now , now = 0;
         
         for(int j=i;j<nown-1;++j)
            now[j] = now[j+1];   
         
         int ns = 0;
         while( ns < nown-2 ){
            if( now[ns] <= now[ns+1] ) break;
            else swap(now[ns],now[ns+1]),++ns;
         }
         
         dfs(lv+1,nown-1);
         
         for(int j=ns;j>0;--j)
            now[j] = now[j-1];
         
         
         for(int j=nown-1;j>i;--j)
            now[j] = now[j-1];
         
         now[0] = ori,now = hold;
      }
   }   
}

int main(){
   
   int T;
   scanf("%d",&T);
   
   while(T--){
      
      memset(is,0,sizeof(is));
      
      int k,w;
      char in[100];
      
      scanf("%d",&k);
      
      for(int i=0;i<k;++i){
         scanf("%s %d",in,&w);
         int tmp = tellme(in);
         if( tmp<4 && w==100 ) continue;
         if( tmp>=4 && w==1000 ) continue;
         item[tmp][is[tmp]++] = w;
      }
      
      int ans = 0;
      
      for(int i=0;i<10;++i){   
         int size = is;
         if( size <= 1 ) continue;
         
         for(int j=0;j<size;++j)
            now[j] = item[j];
         
         sort(now,now+size);
         
         m = ( i<4 ) ? 100 : 1000;
         
         int sum = 0;
         for(int j=0;j<size;++j)
            sum+=now[j];
         sp = sum%m;
         
         best = 200000;         
         dfs(0,size);
         ans += best;
      }
      
      printf("%d\n",ans);
   
   }
   
   return 0;   
}


8
NPSC2007高中組決賽 / 回覆: NPSC 2007 高中組 決賽 F.交換禮物
« 於: 十二月 10, 2010, 07:14:59 pm »
因為範圍只在1~100之間,實際上可以開一個陣列紀錄每個禮物數還有多少人持有,變成O(n)排序。
14ms通過,快很多。

代碼: [選擇]
#include <iostream>

int g[101];

int main(){
 
 int n;
 int t;
 while(1){
   scanf("%d",&n);
   if(!n) break;
   
   memset(g,0,sizeof(g));
   
   int total=0;
   bool legal=1;
   for(int i=0;i<n;++i)
     scanf("%d",&t),++g[t],total+=t;
   
   if(total%2) legal=0;
 
   for(int i=100;legal&&i>0;--i)
     while(g[i]){
       
       int now=i;
       int last=0;
       int tlast;
       --g[i];
       
       for(int j=i;now>0&&j>0;--j){
         if(now>g[j]) tlast=g[j],now-=g[j],g[j]=0;
         else g[j]-=now,g[j-1]+=now,now=0;
         g[j]+=last;
         last=tlast;
       }           
       
     
       if(now) {legal=0;break;}
     }
   
   if(legal) printf("yes\n");
   else printf("no\n");
 }
 
 return 0;   
}


9
NPSC2010高中組初賽 / 回覆: NPSC 2010 高中組 初賽 C.
« 於: 十二月 10, 2010, 10:46:49 am »
willyliu大的解法貌似得先看看劉汝佳的習題指導才能看得懂
不過跟書上寫的又有點不一樣(事實上,書上後面的部分我看不懂XD)
由於我不太會估計複雜度 有沒有大大可以說明一下willyliu大的算法複雜度大約是多少呢?

10
感謝yuscvscv大的指導 這題用了類似線段數的作法後真的快了很多(雖然還是不知道ZJ上面1.X秒的是怎麼回事...好像直接輸出解答不會這麼慢XDD)

以下是程式碼
代碼: [選擇]
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

struct line{
  int s,t;
};

struct data{
  int a,b,c;
};

int sum[50000];
line t[50000];
data sa[10000];
data sb[10000];

int getn(void){
  int temp=0;
  char in;
  while(1){
    scanf("%c",&in);
    if(in==10||in==32) return temp;
    temp=temp*10+in-'0';
  }       
}

void build_t(int s,int f,int no){  //先把每個子葉上的範圍定好
 
  t[no].s=s;
  t[no].t=f;
  if(s==f-1) return;
  build_t(s,(s+f)/2,no*2);
  build_t((s+f)/2,f,no*2+1);       

}

void t_push(int s,int f,int no){   //插入數值 途中經過的所有葉子都要+1
 
  ++sum[no];   
  if(t[no].s==s && t[no].t==f) return;
  int mid=(t[no].s+t[no].t)/2;
  if(s>=mid) t_push(s,f,no*2+1);
  else t_push(s,f,no*2);

}

int t_find(int s,int f,int no){   //二分搜尋合法的c值
 
  if(s==t[no].s && f==t[no].t) return sum[no];
  int mid=(t[no].s+t[no].t)/2;
  if(s>=mid) return t_find(s,f,no*2+1);
  else if(f<=mid) return t_find(s,f,no*2);
  else return t_find(s,mid,no*2)+t_find(mid,f,no*2+1);

}

bool cmpa(data t1,data t2){return t1.a > t2.a;}
bool cmpb(data t1,data t2){return t1.b < t2.b;}
     
int main(){
 
  build_t(0,10001,1); 
 
  int n;
  n=getn();
  while(n--){   
    memset(sum,0,sizeof(sum));
    int k;
    int ans=0;
    k=getn(); 
    for(int i=0;i<k;++i)
      sa[i].a=getn(),sa[i].b=getn(),sa[i].c=getn();
   
    memcpy(sb,sa,sizeof(sa));
    sort(sa,sa+k,cmpa);
    sort(sb,sb+k,cmpb);
 
    int bk[10000];
    int bn=0;
    for(int i=0;i<k;++i)   //把要考慮的b值存起來 因為會調用很多次所以另外開陣列
      if(bn==0 || sb[i].b != bk[bn-1]) bk[bn++]=sb[i].b;
   
    for(int i=0;i<k;++i){
      if(i&&sa[i].a==sa[i-1].a) continue;
      int a=sa[i].a;
      int bp=0;  //以b值作排序的陣列指針 記錄現在已經到哪個位置 下次就從這裡開始繼續插入c值
      memset(sum,0,sizeof(sum));       
      for(int j=0; j<bn && a+bk[j]<=10000;++j){
         int b=bk[j];
         for(;bp<k && sb[bp].b<=b;++bp)
           if(sb[bp].a <= a) t_push(sb[bp].c,sb[bp].c+1,1);    //a合法 插入c
         int c=10000-a-b;
         ans=max(ans,t_find(0,c+1,1)); //定義任一個c值等價於一段(c,c+1)的單位長線段   
      }
    }   
 
    printf("%d\n",ans);
         
  }
  return 0;   
}

那個getn函式是拿來測試IO優化的加速有多少的
不過不知道是我寫的不好還是優化相對起來太渺茫了
和用scanf的時間完全一樣XDD

11
雖然這個主題都快過期了...還是來發表一下我的看法
我個人是從c入門 後來轉c++的
基本上學c++只是為了他強大的stl
而且如果只是為了競賽的話 學會基本輸出輸入(這部分C的scanf printf強大多了) array function和struct
然後再補一些stl就可以上場了 所以個人覺得選的語言書不是那麼重要...
多code增加熟練度和debug能力才是更要緊的 ;)

12
遞迴的解法會跟包含括號的四則運算有點像 不過簡單多了
程序可以這樣寫
1.找最外層的括號
2.從該左括號的後一位開始一直找 並且紀錄左右括號各自出現的次數
3.等到左右括號出現次數一樣的時候 就是左邊全部的部分 把這部分丟入遞迴
4.右半邊也是一樣的解法
5.要注意的是 可以設一個全域變數 記錄是否已經確定無法平衡 如果確定無法平衡就一直跳出函式直到回到main 並且輸出解
6.否則的話 遞迴本身傳回的值就是傳入的字串的價值總合

個人覺得比含括號四則運算還簡單 也許直接去寫那題(zj有)會學到更多.....

13
恩恩 謝謝sagit大的講解 :)

說到優化的暴搜 老實說我覺得嚴格說起來這也算是很難的一個部分
怎麼說呢 因為它沒有一定的法則 也無法看書學會(當然經驗是有差別的)
有些cut甚至還要看個人的創意
就像acm的一題木棍原長的問題 dfs以外還要加一大堆剪枝才過得了
這類的問題如果限制嚴格一點 也許競賽期間要解出來反而會比困難的算法還要難

14
那最壞狀況下這樣子是不是反而會更糟糕呢?
我的意思是 如果每次新加入的c值都剛好是新的最小值的話
就變成說每次都要花n的時間插入 跟直接搜尋反而一樣了
還是我的理解有錯誤?

15
不好意思 想問一下

// 將 c 的值插入已排序的 C 陣列

這句本身以及之後的程序不是很了解意思
能夠幫忙說明一下嗎?


16
NPSC2008高中組初賽 / 回覆: NPSC 2008 高中組 初賽 D.郵輪
« 於: 九月 30, 2010, 07:55:47 am »
以下轉自ZJ討論區 asleepy大的發言:

是的,這是一個 NP 的問題。意思也就是說,如果告訴你哪幾間房間是準備室的話,檢查這樣有無符合限制僅需要 P 的時間。(先檢查每條邊是否至少有一的頂點是準備室,檢查的時候順便將另外一個頂點標記,然後再檢查所有的頂點是不是都有標記或是自己就是準備室, n + m)


先看簡單一點的,如果整能有一間準備室。 那麼隨便挑一個邊,這個邊的兩邊至少有一個頂點得要是準備室。那先試試看把其中一個頂點當準備室,這樣合不合法,不行的話再把另外一個頂點當準備室看看合不合法。如果兩個放法都不行,這圖鐵定無解。

那麼如果可以擺放兩間準備室呢?隨便挑兩個沒有重疊到的邊 (v1, v2), (v3, v4) ,v1 ~ v4 都不相等,分別嘗試  [v1, v3], [v1, v4], [v2, v3], [v2, v4] 當準備室,如果這四種方法都不行,那這圖肯定無法解。

不管你取出哪兩條邊,只要這兩條邊的四個頂點都不相等,就可以得出這樣的推論。

我想嘗試說明的是,如果你能找出 8 的地方讓你選擇,每個地方必須保證一定會有一個準備室,那麼當你在這 8 個地方爆搜完後發覺還是無解的時候,你就可以肯定這絕對無解。那麼可能會花 2^8 (n + m) = 256(n + m) 。

實際上做的時候到也不用這麼麻煩 :)

17
NPSC2006國中組初賽 / 回覆: [C]2006 NPSC D. 水之都
« 於: 二月 20, 2010, 12:29:15 pm »
09年國中初賽pb的兄弟題,應該是當年殘念導致09出題。與該題方法一樣,一樣不會比較快,但是好code
代碼: [選擇]
#include <iostream>
using namespace std;
int head[1500];

typedef struct{
  int start;
  int end;
  int value;
}Side;

bool cmp(Side a,Side b)
{ if(a.value > b.value) return 1;
  else return 0;     
}

int find(int n)
{if(n!=head[n]) head[n]=find(head[n]);
 return head[n];
}

int main()
{int n;
 int v,s;
 scanf("%d %d",&v,&s);
 while(v+s){
   Side side[s];
   for(int i=0;i<s;i++) scanf("%d %d %d",&side[i].start,&side[i].end,&side[i].value);
   int S,E;
   scanf("%d %d",&S,&E);
   sort(side,side+s,cmp);
   for(int i=0;i<=v;i++) head[i]=i;
   int max;
   int nc=0; //next catched side
   while( find(S)!=find(E) ){
     max=side[nc].value;
     int heada=find(side[nc].start);
     int headb=find(side[nc].end);
     head[headb]=head[heada];
     nc++;
     if(nc==s) {max=0;break;}
   }
   printf("%d\n",max);
   scanf("%d %d",&v,&s);
 }return 0;   
}

18
NPSC2009國中組初賽 / 回覆: [C++]B.水之國的奇幻冒險
« 於: 二月 20, 2010, 12:26:43 pm »
我是用類似最小生成樹的手法,把邊排序過後最小的邊開始抓入圖內,並用union find的技巧來確定起點與終點是否連通。跑起來沒有比較快(因為排序必定得通過nlogn),但是程式碼好code一點點。


代碼: [選擇]
#include <iostream>
using namespace std;
typedef struct{
  int p1;
  int p2;
  int value;
}Side;

bool compare(Side a,Side b)
{
 if(a.value<b.value) return 1;
 else return 0;
}

int head[200];

int find(int n)
{ if(head[n]!=n) head[n]=find(head[n]);
  return head[n]; 
}

int main(){
  int all;
  int n,m;
  scanf("%d",&all);
  while(all--){
     int put=0;
     int min;
     scanf("%d %d",&n,&m);         
     Side s[m]; //street
     for(int i=0;i<m;i++) scanf("%d %d %d",&s[i].p1,&s[i].p2,&s[i].value);
     for(int i=0;i<200;i++) head[i]=i;
     sort(s,s+m,compare);
     while( find(1)!=find(n) ){
       
       int p1boss=find( s[put].p1 );
       int p2boss=find( s[put].p2 );
       
       head[p2boss]=head[p1boss];                         
       min=s[put].value;
       put++;
     }
     printf("%d\n",min);
 
 }
 return 0;   
}

19
NPSC2009高中組決賽 / 回覆: 今年題目
« 於: 一月 09, 2010, 09:52:32 pm »
個人對於yuscvscv的回覆倒是有不同的看法
先前yuscvscv也提到 如果考很多的(或者是複雜的)模擬題 就形同在烤code穩定度 沒意思
但是測試code穩定度的同時其實也正是在測試coder的產率
一個有良好程式設計習慣並且邏輯清楚的人通常code除錯不需要花很多的時間就可以把程式正確的寫出來
相對起來這樣的coder寫程式的速度就快 工作效能也高
尤其這個比賽又有考慮到時間以及錯誤的次數 如此一來很容易便能分出coder在這方面的高下
如此一來既能多添一些"基本題" 也更能符合現實的所需

20
回應 suhorng:
   哎呀  別那麼搞神秘啦...
   這個網站就是在分享演算法的地方阿
   滿好奇怎麼O(n)解的...

頁: [1] 2