External link:
http://codeforces.com/gym/100159
http://www.facebook.com/hackercup/scoreboard?round=225705397509134
Problem A. Checkpoint
Brief description:
。。我们定义到 (m, n) 的经过 (a, b) 的 2 格点路径为。。。
。从 (0, 0) 出发到 (a, b) 再到 (m, n) 的路径。。(a <= m, b <= n)。。
现在询问方案数等于 S 的二阶格点路径最少有多少步。。。。
Analysis:
… 预处理 D[x] 表示到达组合数 x 所需要的最少步数。。
。。之后将 s 分解成 a * b 即可。(。O(sqrt(s))
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 | //}/* .................................................................................................................................. */ const int N = int (1e7); int D[N+1]; int s; int main(){ #ifndef ONLINE_JUDGE freopen ( "in.txt" , "r" , stdin); //freopen("out.txt", "w", stdout); #endif REP_1(i, N) D[i] = i; FOR(i, 2, 30){ // C(j, i) .. . LL x = 1; for ( int j=i;x<=N;++j,x=x*j/(j-i)){ checkMin(D[x], j); } } Rush{ int res = RD(s)+1; for ( int a=1;sqr(a)<=s;++a){ int b=s/a; if (a*b!=s) continue ; checkMin(res, D[a]+D[b]); } OT(res); } } |
Problem B. Recover the Sequence
Note:
… 严格按照题目的要求递归下去就好了。。)
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 | //}/* .................................................................................................................................. */ const int N = int (1e4) + 9; int R[N], P[N]; int n; void gao( int l, int r){ if (l+1 >= r) return ; int m = l + r >> 1; gao(l, m), gao(m, r); int a = l, b = m, i = l; while (a < m && b < r){ if (RC() == '1' ) P[i++] = R[a++]; else P[i++] = R[b++]; } while (a < m) P[i++] = R[a++]; while (b < r) P[i++] = R[b++]; FOR(i, l, r) R[i] = P[i]; } int main(){ #ifndef ONLINE_JUDGE freopen ( "in.txt" , "r" , stdin); //freopen("out.txt", "w", stdout); #endif Rush{ REP_C(i, RD(n)) R[i] = i; gao(0, n); REP(i, n) P[R[i]] = i+1; int res = 1; REP(i, n) MUL(res, 31), INC(res, P[i]); OT(res); } } |
Problem C. Squished Status
Note:
… 暴力 DP 。。注意模数超 int。。
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 | int Case; template < class T> inline void OT( const T &x){ printf ( "Case #%d: %u\n" , ++Case, x); //printf("%.2lf\n", x); //printf("%d\n", x); //cout << x << endl; } //} //}/* .................................................................................................................................. */ const UINT MOD = 0xfaceb00c; inline void INC( UINT &a, UINT b){LL aa = a; aa += b; if (aa >= MOD) aa -= MOD; a = aa;} const int N = 1009; char str[N]; UINT dp[N], n, m; int main(){ #ifndef ONLINE_JUDGE freopen ( "in.txt" , "r" , stdin); //freopen("out.txt", "w", stdout); #endif Rush{ RD(m); n = strlen (RS(str)); REP_S(cur, str) *cur -= '0' ; RST(dp), dp[0] = 1; REP(i, n) if (dp[i] && str[i]){ int x = 0; FOR(j, i, n){ x *= 10, x += str[j]; if (x > m) break ; INC(dp[j+1], dp[i]); } } OT(dp[n]); } } |