又到了一年一度的GCJ賽季了！
這個blog也終於要有點動靜了。話說去年因為在Round2比得太爛也沒晉級，後來就沒發文了。
與去年的Qualification Round不一樣，今年決定使用母語C++來完成。
當他數到的數字當中，所有數字(0~9)都出現過，他就會睡著。
給\(N\)，輸出他睡著前最後一個數到的數字，如果沒辦法睡著就輸出"INSOMNIA"(失眠，不含引號)。
(\(T\leq100, N\leq10^6\))
這題讀完之後我遲疑了一下，思考有什麼明確的好方法。
然後就猜除了範測的\(0\)以外應該沒數幾個就會睡著了，但是...
當時讀錯題目，以為輸出的是「數了幾個數字」，然後看到範測有5千多，就卡了一下。
後來看清楚題目之後，就決定先寫個程式乖乖數數，並且測試\(1\)到\(10^6\)，結果沒想到程式瞬間就跑完了！
到這裡這題顯然就解決了XD
時間複雜度：不知道，我這個解法只有「實務」沒有「理論」
AC code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <bits/stdc++.h> #define PB push_back #define MP make_pair #define F first #define S second #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(),(x).end() #ifdef _DEBUG_ #define debug(...) printf(__VA_ARGS__) #else #define debug(...) (void)0 #endif using namespace std; typedef long long ll; typedef pair<int,int> PII; typedef vector<int> VI; bool vis[10]; int cnt; bool add(int x) { while(x) { if(!vis[x%10]) vis[x%10]=1, cnt++; x/=10; } if(cnt==10) return true; return false; } const int tre=1000; int go(int x) { fill(vis,vis+10,0); cnt=0; for(int t=1;t<=tre;t++) { if(add(x*t)) return x*t; } assert(x==0); return -1; } int main() { int all_kase,N; scanf("%d",&all_kase); for(int num_kase=1;num_kase<=all_kase;num_kase++) { scanf("%d",&N); int ans=go(N); printf("Case #%d: ",num_kase); if(ans==-1) puts("INSOMNIA"); else printf("%d\n",ans); } return 0; } |
題意給你一串+,-序列，每次你可以挑選一個前綴，把整段反轉並把每個位置+,-互換，問最少幾次操作可以讓整段都是+？
這題看完之後試了一下，感覺要從前面開始做，於是我就寫了一個DP，定義狀態dp[i][0]表示把前\(i\)個都變成 - 所需操作數、dp[i][1]表示把前\(i\)個都變成 + 所需操作數。
仔細想一下從前面開始做一定比較好，轉移就很順的寫出來（詳見code），並且把輸入用 1-index 存比較好寫。
時間複雜度：\(O(S)\)
AC code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include <bits/stdc++.h> #define PB push_back #define MP make_pair #define F first #define S second #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(),(x).end() #ifdef _DEBUG_ #define debug(...) printf(__VA_ARGS__) #else #define debug(...) (void)0 #endif using namespace std; typedef long long ll; typedef pair<int,int> PII; typedef vector<int> VI; const int MAXS=110; int dp[MAXS][2]; char in[MAXS]; int main() { int all_kase; scanf("%d",&all_kase); for(int num_kase=1;num_kase<=all_kase;num_kase++) { scanf("%s",in+1); int S=strlen(in+1); for(int i=1;in[i];i++) in[i]=(in[i]=='+')?1:0; dp[0][0]=dp[0][1]=0; for(int i=1;i<=S;i++) { for(int j=0;j<=1;j++) { if(in[i]==j) dp[i][j]=dp[i-1][j]; else dp[i][j]=dp[i-1][j^1]+1; } } printf("Case #%d: ",num_kase); printf("%d\n",dp[S][1]); } return 0; } |
剛剛戳了一些認識的人的code，的確大部分人都是這樣寫的！
給你\(N,J\)（其實題目中固定值了，所以這題應該是output only），產生\(J\)個長度為\(N\)的相異 jamcoin ，並附上足以證明他是合數的因數們。
Small:\(N=16, J=50\)
Large:\(N=32, J=500\)
這題對我而言想到解法異常的順利，因為題序中舉例 1001 是jamcoin時，我就聯想到\(x^3+1=(x+1)(x^2-x+1)\)，於是讀完題目之後很快就往因式分解下手。
因為\(x^{15}+1, x^{31}+1\)本來就是\(x+1\)的整係數倍式，所以只要在序列中任意加上 11 ，維持\(x+1\)的倍數就好了。
很快地寫了一個用到XOR的作法，然後WA掉，才發現1100^0110=1010不是11的倍式XD
重新寫最多構造\(2^{N-2/2}\)個jamcoin的code就過了！
傳完重看自己的code，就發現我如果利用二進制寫這題會好寫很多...甚至可以\(2147483649+6k\)這樣構造更多個jamcoin！
時間複雜度：\(O(N\times J)\)
AC code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include <bits/stdc++.h> #define PB push_back #define MP make_pair #define F first #define S second #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(),(x).end() #ifdef _DEBUG_ #define debug(...) printf(__VA_ARGS__) #else #define debug(...) (void)0 #endif using namespace std; typedef long long ll; typedef pair<int,int> PII; typedef vector<int> VI; const int MAXN=50; const int MAXJ=550; const int TH=10; int N,J; int in[MAXN]; int cnt=0; void go(int l) { if(cnt>=J) return; if(l>=N-2) { for(int i=N-1;i>=0;i--) printf("%d",in[i]); for(int i=2;i<=10;i++) printf(" %d",i+1); puts(""); cnt++; return; } go(l+2); in[l]^=1; in[l+1]^=1; go(l+2); } int main() { int all_kase; scanf("%d",&all_kase); for(int num_kase=1;num_kase<=all_kase;num_kase++) { scanf("%d%d",&N,&J); printf("Case #%d:\n",num_kase); cnt=0; in[0]=in[N-1]=1; go(1); } return 0; } |
這題我在自己認識的人當中戳出不同作法的人不少，有趣的地方也不少。
betaveros作法基本上跟我一樣，只是那個神奇(?)的python code看懂之後對我這個python入門者真是一種衝擊XD
tmt514跟Kirino都用把數字們嘗試直到完成為止的做法，寫完聽說small可以硬爆、large會爆long long的時候沒想太多，看到這兩份才想起來可以先指定一個質數，那麼要檢查這個數字能不能被它整除就簡單了！ 這邊tmt514跑二進位的那個方法不難理解，可是對我來講還算新鮮。兩人的差異在於，tmt514用了\(\lt1000\)的所有質數、Kirino只用了\(2,3,5,7\)，只用\(2,3,5,7\)也足夠產生答案，這點也是我意料之外的！
最後一個弄了很久才弄懂的是zolution的code。它是算出數字之後直接用根號算法找因數，這樣想large會爆long long應該慘掉，結果code裡神奇的這一行解決了一切：
if(n==32){ n=16; large=true;}
一開始有一個長度\(K\)、由L,G兩種字元組成的字串，每回合的操作是：把L取代成原始長度\(K\)的那個字串、把G取代成\(K\)個G。
今天告訴你有一個長度為\(K\)，重複進行\(C-1\)回合的操作形成的字串，請你檢查這上面最多\(S\)個位置，以確認整個字串中是否存在任何一格為G？
若可以，輸出那些位置，否則，輸出
\(1\le K,C\le100,~~~ K^C\le10^{18}\)
small:\(S=K\)
large:\(1\le S\leq K\)
small想一下就會做了，但是看到題目特別提醒small過了之後就不能再傳，也覺得這題的special judge好像不容易寫，把small留著讓large測試好了，反正qualification round不管時間。
為了large開始嘗試做一些case的時候想錯了，以為是每回合把L取代成現在這個字串、把G取代成跟現在字串一樣長的G（所以每回合長度都會變成平方OAO），然後就一直卡住QQ
發現這個錯誤之後試了一下還是沒有完整頭緒，於是就回頭想一下：這題的special judge該怎麼寫？
於是就不難想到這份code能把位置\(x\)覆蓋到的原始位置找出來（用0-index）
1 2 3 4 5 6 7 8 9 10 11 12 | void cap(ll x,int K,int C) { printf("%lld:",x); vector<ll> vec; for(int i=0;i<C;i++) { vec.PB(x%K); x/=K; } sort(ALL(vec)); vec.resize( unique(ALL(vec))-begin(vec) ); for(int i=0;i<SZ(vec);i++) printf("%lld%c",vec[i]," \n"[i==SZ(vec)-1]); } |
看了一下程式跑的結果，覆蓋\(0,1,2,...,C-1\)、\(C,C+1,C+2,...,2\times C\)、...的數字都存在！
這時再回頭看一下剛剛這個函式，這根本就是把\(x\)以\(K\)進制拆出來的每位數字嘛XDD
於是就順利地寫程式一次解掉small跟large了。
（戳下來，認識的人當中有過large的人基本上做法都一樣）
時間複雜度：\(O(K)\)
AC code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <bits/stdc++.h> #define PB push_back #define MP make_pair #define F first #define S second #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(),(x).end() #ifdef _DEBUG_ #define debug(...) printf(__VA_ARGS__) #else #define debug(...) (void)0 #endif using namespace std; typedef long long ll; typedef pair<int,int> PII; typedef vector<int> VI; const int MAXK=105; const int MAXL=MAXK*MAXK; int K,C,S; int main() { int all_kase; scanf("%d",&all_kase); for(int num_kase=1;num_kase<=all_kase;num_kase++) { scanf("%d%d%d",&K,&C,&S); printf("Case #%d:",num_kase); if(C*S<K) { puts(" IMPOSSIBLE"); continue; } int cnt=0; int check=0; ll maxn=1; for(int i=0;i<C;i++) maxn*=K; while(cnt<K) { ll out=0; for(int i=0;i<C && cnt<K;i++) { out*=K; out+=cnt++; } assert(out<maxn); printf(" %lld",out+1); check++; } puts(""); assert(check<=S); assert(cnt==K); } return 0; } |
今年第一次寫Qualification Round寫得這麼認真，接下來還要在期中考+期中作業潮當中面對Round1，希望一切順利！
沒有留言:
張貼留言