EPOCH予選延期でほげ。
前解いたソースをあげます。結局Cは問題文読むのを放棄したまま読んでいないけどA,Bだけ。
A. 数珠繋ぎ
問題分かりにくいけど、分かったら明らかに何か法則性があることが見えてくる。ていうかn=30の時点で慣れてる人は気づく。
そして、それを考えてみると、二進数で1から順番に列挙したものと等価なことが分かる。
例えば、n=3なら、
000→001→010→011→100→101→110→111→000
よって、ループは2^n周期で発生し、周期内で、2^n-1回目に指パッチンした時全部ライトが点いているのでほげ。
#include <iostream> using namespace std; int main(){ int T,n,k; cin >> n; T = 1; while(cin >> n >> k){ cout << "Case #" << T++ << ": " << ( (k+1)%(1<<n) == 0 ? "ON" : "OFF" ) << endl; } }
B. 数の集合
制約を見てみると区間篩ですよアピールをしている。
篩かけるだけのループだと重複取り除くのがなんかびみょーに困難だったので、数と素因数の関係でグラフを構築して、O(nm)で独立したグラフの個数を数えるという方法でやった。定数項重すぎてLarge1分くらいかかってアレだったがGCJなので良い。
ソース中では素因数なら負、普通に数なら正みたいな感じで辺をつないでいる。
#include <iostream> #include <stack> #include <vector> #include <cstring> using namespace std; int output(int n){ static int T = 1; cout << "Case #" << T++ << ": " << n << endl; } #define PRIME_MAX 1000000 vector<bool> prime(PRIME_MAX+1,true); void init_prime(){ prime[0] = prime[1] = false; for(int i=2;i*i<=PRIME_MAX;i++) if(prime[i]) for(int j=i*i;j<=PRIME_MAX;j+=i)prime[j] = false; } vector<int> graph_[2*(1000001)]; char done_[2*(1000001)]; int main(){ init_prime(); vector<int> *graph = &graph_[1000001]; char *done = &done_[1000001]; int T; cin >> T; long long a,b,p; while(cin >> a >> b >> p){ for(int i = 0 ; i < 2*(1000001) ; i++) graph_[i].clear(); memset(done_,0,sizeof(done_)); int cnt = 0; for(long long i = p ; i <= 1e6 ; i++){ if( prime[i] ){ for(long long j = a+(i-a%i)%i ; j <= b ; j+=i){ graph[j-a].push_back(-i); graph[-i].push_back(j-a); } } } int ans = 0; for(long long i = a ; i <= b ; i++){ if(!done[i-a]){ ans++; done[i-a] = true; stack<int> S; S.push(i-a); while(S.size()){ int s = S.top(); S.pop(); //if(s>=0)cout << s+a << " "; for(int i = 0 ; i < graph[s].size() ; i++){ int t = graph[s][i]; if(!done[t]){ S.push(t); done[t] = true; } } } //cout << endl; } } output(ans); } }
C
日本語難しかった。