Solution A. Alice 的车牌号 字符串匹配, 只要在所给字符串中查找是否出现 "13" 这个子串即可, 关键代码如下 bool judge(char str[]) return strstr(str, "13") == NULL; Code: #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> using namespace std; #define ONLINE_JUDGE const int MAX_LENGTH = 16; void solve() int test; int cas = 1; char str[max_length]; for (cin >> test; test--; ++cas) cin >> str; cout << "Case #" << cas << ": "; if (NULL == strstr(str, "13")) cout << "Yes, I like it!" << endl; else cout << "No, it's terrible!" << endl; return ; int main(int argc, char *argv[]) #ifndef ONLINE_JUDGE freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #endif solve(); return EXIT_SUCCESS;
B. Bella 的冒险之旅 Solution 图论, 树的最小表示, 解法是先用二进制数枚举所有可能的联通子树, 然后判断是否为联通子树, 然后枚举该联通子树中的每个点, 开始从该点开始进行 dfs 搜索, 在 dfs 过程中, 设置一个字符串记录 dfs 的路径, 方法是, 入点将路径字符串 +"0", 出点将路径字符串 +"1", 同时对于每次搜索到的节点, 对其后续搜索到的节点的路径进行排序, 之后再合并入该点的路径, 当搜索完整个连通子图后, 用 Trie 对路径字符串判重 最后统计即可 Code: #include <iostream> #include <functional> #include <algorithm> #include <complex> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <sstream> #include <utility> #include <bitset> #include <cctype> #include <cstdio> #include <limits> #include <memory> #include <string> #include <vector> #include <cmath> #include <ctime> #include <queue> #include <stack> #include <list> #include <map> #include <set> using namespace std; #define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) ) #define CLR(x, k) memset((x), (k), sizeof(x)) #define CPY(t, s) memcpy((t), (s), sizeof(s)) #define SC(t, s) static_cast<t>(s) #define LEN(s) static_cast<int>( strlen((s)) ) #define SZ(s) static_cast<int>( (s).size() ) typedef double LF; typedef int64 LL; //VC typedef unsigned int64 ULL; typedef pair<int, int> PII; typedef pair<ll, LL> PLL; typedef pair<double, double> PDD;
typedef vector<int> VI; typedef vector<char> VC; typedef vector<double> VF; typedef vector<string> VS; template <typename T> T sqa(const T & x) return x * x; template <typename T> T ll(const T & x) return x << 1; template <typename T> T rr(const T & x) return x << 1 1; template <typename T> T gcd(t a, T b) if (!a!b) return max(a, b); T t; while (t = a % b) a = b; b = t; return b; ; const int INF_INT = 0x3f3f3f3f; const LL INF_LL = 0x7fffffffffffffffLL; const double oo = 10e9; const double eps = 10e-7; const double PI = acos(-1.0); //15f #define ONLINE_JUDGE const int MAXV = 10004; const int MAXN = 200004; int test, n; struct Node Node * next[2]; bool end_sign; trie[maxn], * const root = trie; int ncnt; VI G[MAXV]; bool hs[maxv]; void inittrie()
ncnt = 1; for (int i = 0; i < 2; ++i) root->next[i] = NULL; root->end_sign = false; return ; Node * createnode() for (int i = 0; i < 2; ++i) trie[ncnt].next[i] = NULL; trie[ncnt].end_sign = false; return &trie[ncnt++]; bool inserttrie(const string & str) Node * ptr = root; int len = SC(int, str.length()); for (int i = 0; i < len; ++i) int t = str[i] - '0'; if (NULL == ptr->next[t]) ptr->next[t] = createnode(); ptr = ptr->next[t]; if (ptr->end_sign) return false; ptr->end_sign = true; return true; void addedge(int u, int v) G[u].push_back(v); return ; void search(int u, int state) hs[u] = true; for (VI::iterator it = G[u].begin(); it!= G[u].end(); ++it) int v = *it;
if ((1 << v) & state) if (!hs[v]) search(v, state); return ; bool connectedjudge(int state) CLR(hs, false); for (int i = 0; i < n; ++i) if ((1 << i) & state) search(i, state); break ; for (int i = 0; i < n; ++i) if ((1 << i) & state) if (!hs[i]) return false; return true; string dfs(int u, string str, int state) VS vs; hs[u] = true; for (VI::iterator it = G[u].begin(); it!= G[u].end(); ++it) int v = *it; if ((1 << v) & state) if (!hs[v]) vs.push_back(dfs(v, "0", state) + "1"); sort(vs.begin(), vs.end());
for (VS::iterator it = vs.begin(); it!= vs.end(); ++it) str += *it; return str; bool insertjudge(int state) bool sign = false; for (int u = 0; u < n; ++u) if ((1 << u) & state) CLR(hs, false); if (inserttrie(dfs(u, "", state))) sign = true; return sign; void ace() int cas = 1; int u, v; int res; for (scanf("%d", &test); test--; ++cas) scanf("%d", &n); for (int i = 0; i < n; ++i) G[i].clear(); inittrie(); for (int i = 0; i < n - 1; ++i) scanf("%d %d", &u, &v); addedge(u, v); addedge(v, u); res = 0; for (int state = 1; state < (1 << n); ++state) if (!connectedjudge(state)) continue ; if (insertjudge(state))
++res; printf("case #%d: %d\n", cas, res); return ; int main() #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif ace(); return 0;
Solution C. Catherine 的魔法符文 杂题, 注意控制输出即可, 不要在输出图案后面输出空格 Code: #include <cstdio> #include <cstdlib> #include <iostream> using namespace std; #define ONLINE_JUDGE void solve() int test, n; int cas = 1; for (cin >> test; test--; ++cas) cin >> n; cout << "Case #" << cas << ": " << endl; if (1 == n) cout << "1" << endl << endl; continue ; for (int i = 1; i <= n; ++i) for (int j = 0; j < 2 * (n - i); ++j) cout << " "; cout << "1"; for (int j = 2; j <= i; ++j) cout << " " << j; for (int j = i - 1; j >= 1; --j) cout << " " << j; cout << endl; for (int i = n - 1; i >= 1; --i) for (int j = 0; j < 2 * (n - i); ++j) cout << " "; cout << "1"; for (int j = 2; j <= i; ++j)
cout << " " << j; for (int j = i - 1; j >= 1; --j) cout << " " << j; cout << endl; cout << endl; return ; int main(int argc, char *argv[]) #ifndef ONLINE_JUDGE freopen("c.in", "r", stdin); freopen("c.out", "w", stdout); #endif solve(); return EXIT_SUCCESS;
Solution D. Diana 的组队烦恼 组合数学 + 动态规划, 注意当 k>n 时, 没有对应的分组策略, 应输出 0,k=1 或者 k=n 时, 分组方案只有 1 种, 否 则,n 个人分成 k 个小组, 都可以看成是原先 n-1 个人分成 k 个小组, 再将 1 个人插入原先的 k 个小组, 以及原先 n-1 个人分成 k-1 个小组, 再让 1 个人独立组成一个小组, 所以有状态转移方程 dp[n][k] = dp[n - 1][k - 1] + k * dp[n - 1][k]; Code: #include <cstdio> #include <cstdlib> #include <iostream> using namespace std; #define ONLINE_JUDGE typedef long long LL; const int MAX_SIZE = 20; void solve() int test, n, k; LL dp[max_size][max_size]; int cas = 1; for (int i = 0; i < MAX_SIZE; ++i) dp[i][1] = 1; dp[i][i] = 1; for (int i = 3; i < MAX_SIZE; ++i) for (int j = 2; j < i; ++j) dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1]; for (cin >> test; test--; ++cas) cin >> n >> k; cout << "Case #" << cas << ": "; if (k > n) cout << 0 << endl; else cout << dp[n][k] << endl;
return ; int main(int argc, char *argv[]) #ifndef ONLINE_JUDGE freopen("d.in", "r", stdin); freopen("d.out", "w", stdout); #endif solve(); return EXIT_SUCCESS;
Solution E. 最低等级 可以用将 n 转换为二进制数后再找最低比特位, 更好的方法是直接用位运算, int lowbit(const int &x) return x & (-x); Code: #include <cstdio> #include <cstdlib> #include <iostream> using namespace std; #define ONLINE_JUDGE void solve() int test; int cas = 1; int n; for (cin >> test; test--; ++cas) cin >> n; cout << "Case #" << cas << ": " << ((n) & (-n)) << endl; return ; int main(int argc, char *argv[]) #ifndef ONLINE_JUDGE freopen("e.in", "r", stdin); freopen("e.out", "w", stdout); #endif solve(); return EXIT_SUCCESS;
F. 寻找砝码集 Solution 数论, 可以证明可以组成砝码集的物品的最大公约数和所有物品的最大公约数相等 所以本题即求对每个物品除以所有物品最大公约数后, 最大公约数为 1 的物品集合 由于所有物品重量都小于 10000000, 所有可能的物品集合的最大公约数都不超过 10000000, 又因为 n 很小, 所以可以开一个容量为 10000000 的整形数组 d 记录每个可能的最大公约数最少由多少个物品构成, 然后借助队列, 逐步枚举由 1 个物品 2 个物品直到 n 个物品构成的所有最大公约数即可,d[1] 的值就是所求数量 Code: #include <iostream> #include <cstdlib> #include <cstdio> #include <memory> #include <cstring> #include <cmath> #include <ctime> #include <algorithm> #include <set> #include <vector> #include <set> #include <map> #include <queue> #include <stack> using namespace std; int gcd(int a, int b) int t; while(b!= 0) t = b; b = a % b; a = t; return a; int d[10000005]; class BalanceScale public: int takeweights(vector <int> w) int i, tmp; int n = w.size(); tmp = w[0]; for(i = 1; i < n; ++i) tmp = gcd(tmp, w[i]); for(i = 0; i < n; ++i)
w[i] /= tmp; sort(w.begin(), w.end()); if(w[0] == 1) return 1; memset(d, 1, sizeof(d)); queue<int> q; for(i = 0; i < n; ++i) q.push(w[i]); d[w[i]] = 1; while(!q.empty() && d[1] == 0x01010101) int top = q.front(); q.pop(); for(i = 0; i < n; ++i) tmp = gcd(top, w[i]); if(d[tmp] == 0x01010101) d[tmp] = d[top] + 1; q.push(tmp); return d[1]; ; int main() int n; vector<int> w; BalanceScale solution; while (cin >> n, n) w.clear(); int data; for (int i = 0; i < n; ++i) cin >> data; w.push_back(data); cout << solution.takeweights(w) << endl; return 0;
Solution G. 奇怪的电梯 图论, 以楼层为节点, 如果一个楼层可达另一个楼层则添加一条有向边, 建图后用任意一个最短路径算法求解 Code: #include <iostream> #include <cstdlib> #include <cstdio> #include <memory.h> #include <cstring> #include <algorithm> #include <cmath> #include <set> #include <vector> #include <set> #include <map> #include <queue> #include <stack> using namespace std; #define ONLINE_JUDGE const int inf = 0x7fffffff; struct Edge int from, to, nxt; e[505]; int idx, n, a, b, d[205], head[205]; void addedge(int from, int to) e[idx].from = from; e[idx].to = to; e[idx].nxt = head[from]; head[from] = idx++; void Bellman_Ford() int i, j; for(i = 1; i <= n; ++i) d[i] = inf; d[a] = 0; for(i = 1; i <= n - 1; ++i)
for(j = 0; j < idx; ++j) if(d[e[j].from]!= inf) if(d[e[j].to] > d[e[j].from] + 1) d[e[j].to] = d[e[j].from] + 1; if(d[b] == inf) printf("-1\n"); else printf("%d\n", d[b]); int main() #ifndef ONLINE_JUDGE freopen("g.in", "r", stdin); freopen("g.out", "w", stdout); #endif int i, tmp; while(scanf("%d", &n)!= EOF) if(!n) break; scanf("%d%d", &a, &b); idx = 0; memset(head, -1, sizeof(head)); for(i = 1; i <= n; ++i) scanf("%d", &tmp); if(i - tmp > 0) addedge(i, i - tmp); if(i + tmp <= n) addedge(i, i + tmp); Bellman_Ford(); return 0;
Solution H. 宝盒密码 若存在这样的 x, 则其必然是 a 的约数, 因而可以枚举 a 的约数找出满足条件的最小的 x, 时间复杂度 O(sqrt(a)) Code: #include <stdio.h> #include <time.h> int main( int argc, char *argv[] ) //clock_t t1 = clock(); //freopen( "a.in", "r", stdin ); //freopen( "a.out", "w", stdout ); int x, d, l, h, a, b, cas = 0, t, r; scanf( "%d", &t ); while ( t-- ) scanf( "%d%d%d%d", &l, &h, &a, &b ); r = -1; if ( ( a % b ) == 0 && a >= l && a <= h ) r = a; for ( x = 1; x * x <= a && x <= h; ++x ) if ( a % x ) continue; if ( ( x % b ) == 0 ) if ( x >= l && x <= h ) d = a / x; r = x; break; if ( ( d % b ) == 0 ) if ( d >= l && d <= h ) r = d; printf( "Case #%d: %d\n", ++cas, r ); //clock_t t2 = clock(); //printf( "%.3f ms\n", ( t2 - t1 ) * 1.0 / CLOCKS_PER_SEC * 1000.0 ); return 0;
Solution I. 法默尔的农场 用线段树, 按水位的不断增高查询线段树, 一边查询一边更新线段树, 线段树节点 : struct Node ; int lm, cm, rm; Node() Node( int l, int c, int r ):lm(l), cm(c), rm(r) struct TREE ; int min, max; Node node; max 表示当前区间最高的山丘高度, min 表示当前区间最低的尚没有被水淹没的山丘高度 lm 表示本区间的左端山丘是否被水淹没, rm 表示本区间的右端山丘是否被水淹没, cm 表示本区间有多少小岛 更新的时候, 除 max 域外, 其它四个域都要更新 核心思想是当水位小于 min 或大于 max 时, 则不需要分解此区间 Code: 离线 : #include <stdio.h> #include <algorithm> #include <time.h> using namespace std; struct Node ; int lm, cm, rm; Node() Node( int l, int c, int r ):lm(l), cm(c), rm(r) struct TREE ; int l, r, min, max; Node node; struct Num ; int q, id; TREE tree[400006]; int h[100005], n, re[100005]; Num num[100005]; bool cmp( const Num &a, const Num &b ) return a.q < b.q; inline int _min( int a, int b ) if ( a > b ) return b; return a;
inline int _max( int a, int b ) if ( a > b ) return a; return b; void build( int l, int r, int id ) tree[id].l = l; tree[id].r = r; tree[id].node.cm = 1; tree[id].node.lm = 1; tree[id].node.rm = 1; int mid = ( l + r ) >> 1; if ( mid == l ) tree[id].min = h[l]; tree[id].max = h[l]; return; build( l, mid, id << 1 ); build( mid, r, (id<<1)^1 ); tree[id].max = _max( tree[id<<1].max, tree[(id<<1)^1].max ); tree[id].min = _min( tree[id<<1].min, tree[(id<<1)^1].min ); return; inline Node up( const Node &a, const Node &b ) return Node( a.lm, a.cm + b.cm - ( a.rm & b.lm ), b.rm ); const Node& query( int h, int id ) if ( h < tree[id].min ) return tree[id].node; if ( h >= tree[id].max ) tree[id].min = h + 1; tree[id].node.cm = 0; tree[id].node.lm = 0; tree[id].node.rm = 0; return tree[id].node; tree[id].node = up( query( h, id << 1 ), query( h, (id<<1)^1 ) ); if ( tree[id<<1].min > tree[id<<1].max ) tree[id].min = tree[(id<<1)^1].min; else if ( tree[(id<<1)^1].min > tree[(id<<1)^1].max ) tree[id].min = tree[id<<1].min; else tree[id].min = _min( tree[id<<1].min, tree[(id<<1)^1].min ); return tree[id].node;
int main( int argc, char *argv[] ) //clock_t t1 = clock(); //freopen( "b.in", "r", stdin ); //freopen( "b_off.out", "w", stdout ); int i, q; scanf( "%d", &n ); for ( i = 0; i < n; ++i ) scanf( "%d", h + i ); build( 0, n, 1 ); scanf( "%d", &q ); for ( i = 0; i < q; ++i ) scanf( "%d", &num[i].q ); num[i].id = i; sort( num, num + q, cmp ); for ( i = 0; i < q; ++i ) re[num[i].id] = query( num[i].q, 1 ).cm; for ( i = 0; i < q; ++i ) printf( "%d\n", re[i] ); //clock_t t2 = clock(); //printf( "%.3f ms\n", ( t2 - t1 ) * 1.0 / CLOCKS_PER_SEC * 1000.0 ); return 0; 在线 : #include <stdio.h> #include <algorithm> #include <time.h> using namespace std; struct Node ; int lm, cm, rm; Node() Node( int l, int c, int r ):lm(l), cm(c), rm(r) struct TREE ; int l, r, min, max; Node node; TREE tree[400006]; int h[100005], n, re[100005]; inline int _min( int a, int b ) if ( a > b ) return b; return a; inline int _max( int a, int b ) if ( a > b ) return a; return b;
void build( int l, int r, int id ) tree[id].l = l; tree[id].r = r; tree[id].node.cm = 1; tree[id].node.lm = 1; tree[id].node.rm = 1; int mid = ( l + r ) >> 1; if ( mid == l ) tree[id].min = h[l]; tree[id].max = h[l]; return; build( l, mid, id << 1 ); build( mid, r, (id<<1)^1 ); tree[id].max = _max( tree[id<<1].max, tree[(id<<1)^1].max ); tree[id].min = _min( tree[id<<1].min, tree[(id<<1)^1].min ); return; inline Node up( const Node &a, const Node &b ) return Node( a.lm, a.cm + b.cm - ( a.rm & b.lm ), b.rm ); const Node& query( int h, int id ) if ( h < tree[id].min ) return tree[id].node; if ( h >= tree[id].max ) tree[id].min = h + 1; tree[id].node.cm = 0; tree[id].node.lm = 0; tree[id].node.rm = 0; return tree[id].node; tree[id].node = up( query( h, id << 1 ), query( h, (id<<1)^1 ) ); if ( tree[id<<1].min > tree[id<<1].max ) tree[id].min = tree[(id<<1)^1].min; else if ( tree[(id<<1)^1].min > tree[(id<<1)^1].max ) tree[id].min = tree[id<<1].min; else tree[id].min = _min( tree[id<<1].min, tree[(id<<1)^1].min ); return tree[id].node; int bin_search( int l, int r, int x ) int mid; while ( l < r ) mid = ( l + r ) >> 1;
if ( h[mid] > x ) r = mid; else l = mid + 1; return re[l-1]; int main( int argc, char *argv[] ) //clock_t t1 = clock(); //freopen( "b.in", "r", stdin ); //freopen( "b_on.out", "w", stdout ); int i, q; scanf( "%d", &n ); h[0] = 0; for ( i = 1; i <= n; ++i ) scanf( "%d", h + i ); build( 1, n + 1, 1 ); sort( h + 1, h + n + 1 ); int j; for ( i = 2, j = 1; i <= n; ++i ) if ( h[i]!= h[j] ) ++j; if ( j!= i ) h[j] = h[i]; re[0] = 1; for ( i = 1; i <= j; ++i ) re[i] = query( h[i], 1 ).cm; scanf( "%d", &q ); int x; ++j; while ( q-- ) scanf( "%d", &x ); printf( "%d\n", bin_search( 0, j, x ) ); //clock_t t2 = clock(); //printf( "%.3f ms\n", ( t2 - t1 ) * 1.0 / CLOCKS_PER_SEC * 1000.0 ); return 0;
J. 银河系 5A 风景区 Solution 计算几何 + 随机算法, 模拟退火的经典应用, 根据空间中的四个点确定其球心, 时限很宽, 需要注意把握好火候, 火候太大会超时, 太小则达不到要求的精度 Code: #include <stdio.h> #include <stdlib.h> #include <time.h> #include <memory.h> #include <math.h> #include <sys/timeb.h> const double rate = 0.99; const double rad = 1000.0; const double eps = 0.01; const double nts = 30; const double pi2 = 2.0 * acos( -1.0 ); struct point double x, y, z; ; inline double dis( const point &a, const point &b ) return sqrt( (a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y) + (a.z-b.z) * (a.z-b.z) ); double buf[4]; double cal_dif( point p[], const point &tp ) int i; double sum = 0, x; for ( i = 0; i < 4; ++i ) buf[i] = dis( tp, p[i] ); sum += buf[i]; x = sum / 4.0; double re = 0; for ( i = 0; i < 4; ++i ) re += ( buf[i] - x ) * ( buf[i] - x ); return re; int main( int argc, char *argv[] ) //timeb t1; //ftime( &t1 ); //freopen( "c.out", "w", stdout ); //freopen( "c.in", "r", stdin ); srand( unsigned( time( NULL ) ) ); point p[4], o, to; double d, dif, td; int t, i, cas = 0;
scanf( "%d", &t ); while ( t-- ) for ( i= 0; i < 4; ++i ) scanf( "%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z ); o.x = 0; o.y = 0; o.z = 0; for ( i = 0; i < 4; ++i ) o.x += p[i].x; o.y += p[i].y; o.z += p[i].z; o.x /= 4.0; o.y /= 4.0; o.z /= 4.0; dif = cal_dif( p, o ); d = rad; double a1, a2; while ( d > eps ) for ( i = 0; i < nts; ++i ) a1 = (double)( rand() ) * pi2 / 32767.0; a2 = (double)( rand() ) * pi2 / 32767.0; to.x = o.x + d * cos( a2 ) * cos( a1 ); to.y = o.y + d * cos( a2 ) * sin( a1 ); to.z = o.z + d * sin( a2 ); if ( fabs( to.x ) > 500 fabs( to.y ) > 500 fabs( to.z ) > 500 ) continue; td = cal_dif( p, to ); if ( td < dif ) dif = td; o = to; d *= rate; if ( fabs( o.x ) < 0.01 ) o.x = fabs( o.x ); if ( fabs( o.y ) < 0.01 ) o.y = fabs( o.y ); if ( fabs( o.z ) < 0.01 ) o.z = fabs( o.z ); printf( "Case #%d: ", ++cas ); printf( "%.1f %.1f %.1f\n", o.x, o.y, o.z ); //timeb t2; //ftime( &t2 ); //printf( "%d ms\n", t2.millitm - t1.millitm + 1000 * ( t2.time - t1.time ) ); return 0;