نوع سوال: احتمالا يا برنامه سازی پویا یاامتحان تمام حالات با حرص کردن

توضیح راه حل :

3214 - Bussiness Rules Management System

لینک سوال: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3214

نوع سوال: پیاده سازی

توضیح راه حل : برای حل این سوال تنها باید آن چیزی که در صورت سوال خواسته شده است را پیاده سازی کنید. برای نگهداری شماره ی هر فرد بر اساس اسم احتمالا نوع داده ی Map در ++C کافی باشد، ولی من از ساختار داده ی Trie استفاده کردم تا کمی سریع تر باشد. در زیر کد من برای حل این مساله را مشاهده می کنید:

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
#include <set>
#include <list>
using namespace std;
 
const int N = 11000;
#define P pair<char, Trie*>
 
struct Trie {
   int mark;
   list<P > childs;
   Trie() {
      mark = -1;
   }
   void add(char* s, int v) {
      if( s[0] == 0 )
         mark = v;
      else {
         Trie* t = 0;
         for( list<P >::iterator it = childs.begin(); it != childs.end(); it ++ )
            if( it->first == s[0] ) {
               t = it->second;
               break;
            }
         if( t == 0 ) {
            t = new Trie();
            childs.push_back( P(s[0], t) );
         }
         t->add(s + 1, v);
      }
   }
   int find(char* s) {
      if( s[0] == 0 )
         return mark;
      else {
         Trie* t = 0;
         for( list<P >::iterator it = childs.begin(); it != childs.end(); it ++ )
            if( it->first == s[0] )
               return it->second->find(s+1);
         return -1;
      }
   }
   ~Trie() {
      for( list<P >::iterator it = childs.begin(); it != childs.end(); it ++ )
         delete it->second;
   }
};
 
int pr[N], t[N], n;
char names[N][30];
 
struct rule {
   int id;
   rule( int id ): id(id) {}
   bool operator<(const rule& r ) const {
      if( pr[id] != pr[r.id] )
         return pr[id] > pr[r.id];
      return t[id] > t[r.id];
   }
};
 
int main() {
   int tst;
   for(scanf("%d", &tst); tst--; ) {
      scanf("%d", &n);
      Trie trie;
      for( int i = 0; i < n; i ++ ) {
         scanf("%s %d", names[i], &pr[i]);
         trie.add(names[i], i);
      }
      set<rule> st;
      int m;
      scanf("%d", &m);
      for( int i = 0; i < m; i ++ ) {
         char cmd[10], sid[30];
         scanf("%s", cmd);
         if( cmd[0] == 'g' ) {
            if( st.size() == 0 )
               printf("<empty>\n");
            else {
               int id = st.begin()->id;
               printf("%s\n", names[id]);
               st.erase( rule(id) );
            }
         } else {
            scanf("%s", sid);
            int id = trie.find(sid);
            if( cmd[0] == 'a' ) {
               t[id] = i;
               st.insert( rule(id) );
            } else {
               st.erase( rule(id) );
            }
         }
      }
   }
   return 0;
}

3215 - Cartoon

لینک سوال: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3215

نوع سوال: برنامه سازی پویا

توضیح راه حل : از آنجایی که اینکه پیکسلی در کجای عکس قرار داشته باشد فرقی در نتیجه سوال نمی کند، در نتیجه رنگ ها را می توانیم بر اساس مقدار مرتب کنیم و در آرایه ی arr[N] قرار دهیم. با کمی دقت می توان متوجه شد که حالت بهینه ای وجود دارد که در آن رنگ های نگاشت شده به یک رنگ مجاور باشند.

فرض کنید dp[i][j] برابر با کمترین هزینه ی انتخاب رنگ برای تقریب رنگ های arr[i..n-1] باشد. فرض کنید best[i][j] برابر کمترین هزینه ی انتخاب یک رنگ برای نگاشت رنگ های arr[i..j] باشد. واضح است که dp[i][1] = best[i][n-1] است.

برای محاسبه ی بقیه مقادیر dp[i][j] ، فرض کنید رنگ i تا p را با یک رنگ تقریب بزنیم. در این صورت، بهترین هزینه برابر خواهد بود با best[i][p] + dp[p+1][j-1] . برای پیدا کردن مقدار ، می توان این مقدار را برای تمام مقادیر p=i..n-1 امتحان کرد و کمترین مقدار ممکن را انتخاب کرد.

برای محاسبه ی best[i][j] ، با کمی دقت متوجه می شویم که این مقدار به صورت تابعی درجه ی دو است که برای پیدا کردن کمترین مقدار آن می توانیم از مشتق گیری استفاده کنیم. بنابراین، این آرایه را می توان به صورت زیر محاسبه کرد:

for( int i = 0; i < n; i ++ ) {
   double a = 0, b = 0, c = 0;
   for( int j = i; j < n; j ++ ) {
      a += 1;
      b -= 2 * arr[j];
      c += pow((double)arr[j], 2);
      double x = -b / (2 * a);
      best[i][j] = a * x * x + b * x + c;
   }

اگر الگوریتم بالا را پیاده سازی کنید، پیچیدگی زمانی راه حل از مرتبه ی O(N^2 K) خواهد بود، با اینکه خیلی کند نیست و در کامپیوتر من بدترین حالت حدود 1 ثانیه طول می کشد. ولی با این حال این سرعت کافی نیست، و باید الگوریتم را کمی بهتر کنیم.

پس از مدتی تلاش برای پیدا کردن راه حلی متفاوت، بالاخره تصمیم گرفتم تا حدس بزنم اگر چه قضیه ای درست باشد سرعت الگوریتم را می توان بیشتر کرد. پس از چندین حدس اشتباه و رد کردن آن ها، بالاخره قضیه ای را حدس زدم که درست بود و آن این است که دنباله ی اعداد best[i-1][j] - best[i][j] به ازای j=i..n-1 ، صعودی است. بنابراین به راحتی می توان فهمید که برای پیدا کردن بهترین مقدار dp[i][j] ، لازم نیست تمام p=i..n-1 را امتحان کنیم، و تنها امتحان کردن p=i..dp2[i+1][j] ، که dp2[i][j] برابر با مکانی است که بهترین نتیجه برای رخ می دهد، کافی است!

3216 - Compositions

لینک سوال: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3216

نوع سوال: برنامه سازی پویا، ضرب ماتریس

توضیح راه حل : فرض کنید dp[i] تعداد تجزیه های باشد. به راحتی می توان دید که dp[i] = dp[0] + ... + dp[i-k] است. ولی همانطور که می بینید، در این صورت مقدار dp[i] به i-k+1 مقدار بستگی خواهد داشت که این تعداد ممکن است بسیار زیاد باشد. می توان این معادله را به صورت dp[i] = total[i-1] - (dp[i-1] + ... + dp[i-k+1]) تغییر داد، که total[i] = dp[0] + ... + dp[i] است، که در این صورت مقدار dp[i] تنها به k مقدار بستگی خواهد داشت. بنابراین اگر این k مقدار را نگهداری کنیم، می توان مقدار جدید dp[i] را محاسبه کنیم.

فرض کنيد برداری 1 * (k+2) بصورت v[i] = (dp[i], dp[i+1], ..., dp[i+k], total[i+k]) داریم. می خواهیم ماتریسی طراحی کنیم به نام mat به طوریکه v[i] * mat = v[i+1] باشد. همانطور که مشخص است، ابعاد ماتریس mat باید برابر با (k+2) * (k+2) باشد (تا ضرب این بردار در این ماتریس برداری با همان اندازه بدهد).

عنصر اول بردار جدید، از ضرب بردار در ستون اول ماتریس بدست می آید، بنابراین باید ستون اول را طوری طراحی کنیم که این حاصل ضرب برابر با باشد. بنابراین، ستون اول باید بصورت باشد. ستون های دوم تا دو تا مانده به آخری را نیز با همین استدلال طراحی می کنیم، يعنی ستون دوم برابر با است، …، و ستون دو تا مانده به آخر برابر است.
عنصر قبل آخر در بردار جدید باید برابر با باشد. چون این عنصر برابر با است، ستون قبل آخر را برابر با قرار می دهیم.
عنصر آخر در بردار جدید باید برابر با باشد. چون این عنصر برابر با است، ستون آخر را شبیه ستونی یکی به آخر طراحی می کنیم و تنها آخرین 1 را به 2 تبدیل می کنیم: .

حال، برای بدست آوردن dp[n] می توانیم ابتدا v[n] = v[0] * mat^n را محاسبه کنیم، و سپس عنصر اول این بردار را که برابر با dp[n] است را به عنوان خروجی چاپ کنیم. بردار v[0] هم همانطور که معلوم است، برابر است با (1,0,0,...,0,1,2) (چون dp[0] = dp[k] = 1 و total[k] = dp[0] + ... + dp[k] = 2 است). برای محاسبه ی mat^n هم می توانیم از الگوریتمی که نیاز به O(log n) عمل ضرب دارد استفاده کنیم. بنابراین پیچیدگی کل الگوریتم از مرتبه ی O(n^3 log n) خواهد شد.

برای محاسبه ی توان ماتریس در O(log n) قدم از الگوریتم زیر استفاده می کنیم:

(ماتریس واحد)، و .
اگر بیت اول n برابر با 1 است، قرار بده .
قرار بده ، و
اگر n برابر با صفر است، نتیجه برابر با result است، در غیر اینصورت برو به قدم 1.

پس می توان مساله را بصورت زیر حل کرد:

void BuildMatrix() {
   memset(mat, 0, sizeof mat);
   for( int i = 0; i <= k; i ++ )
      mat[i + 1][i] = 1;
   for( int i = 1; i < k; i ++ )
      mat[i+1][k] = mat[i+1][k+1] = -1;
   mat[k+1][k+1] = 2;
}
 
int solve( int L ) {
   memset( result, 0, sizeof result );
   memcpy( tmat, mat, sizeof tmat );
   for( int i = 0; i < SIZE; i ++ )
      result[i][i] = 1;
   while( L ) {
      if( L % 2 )
         multiply( result, tmat, k + 2 );
      multiply( tmat, tmat, k + 2 );
      L /= 2;
   }
   int x = (result[0][0] + result[k][0] + (long long)result[k+1][0] * 2) % X;
   return x;
}