2014 CodingTrip

1001：可以证明(扩展欧几里得)，只要卡片中有两个卡片互素，旁边点就是可达的。因此只需要算出所有卡片不互素的情况有多少种，可用容斥原理。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 
 7 using namespace std;
 8 
 9 typedef __int64 ll;
10 
11 ll A, B;
12 ll prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
13 ll ans;
14 bool vis[100];
15 
16 vector<ll> yinzi(ll x) {
17     vector<ll> res;
18     for (int i = 0; i < 9; i++) if (0 == x%prime[i]) {
19         res.push_back(prime[i]);
20     }
21     return res;
22 }
23 
24 ll my_pow(ll d, ll n) {
25     ll res = 1;
26     while (n) {
27         if (n&1) res *= d;
28         d *= d;
29         n >>= 1;
30     }
31     return res;
32 }
33 
34 void dfs(const vector<ll> &d, int cnt, ll tmp, ll flag) {
35     if (cnt >= d.size()) return ;
36         int i = cnt;
37         ll t = B/d[i]/tmp;
38         ans += flag * my_pow(t, A);
39         dfs(d, cnt+1, tmp*d[i], -1*flag);
40         dfs(d, cnt+1, tmp, flag);
41 }
42 
43 int main() {
44 //    freopen("1001.txt", "r", stdin);
45 
46     int T;
47     scanf("%d", &T);
48 
49     while (T--) {
50         scanf("%I64d%I64d", &A, &B);
51         ans = my_pow(B, A);
52         dfs(yinzi(B), 0, 1, -1);
53         memset(vis, false, sizeof(vis));
54         printf("%I64d
", ans);
55     }
56 
57     return 0;
58 }

1001

1002: 括号匹配，区间dp

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 const int MAXN = 1005;
 8 
 9 int dp[MAXN][MAXN];
10 char str[MAXN];
11 
12 
13 int dfs(int L, int R) {
14     if (-1!=dp[L][R])
15         return dp[L][R];
16     int &res = dp[L][R] = 0;
17     if (('('==str[L]&&str[R-1]==')') || ('['==str[L]&&str[R-1]==']'))
18         res = dfs(L+1, R-1) + 1;
19     for (int i = L+1; i < R; i++)
20         res = max(res, dfs(L, i)+dfs(i, R));
21     return res;
22 }
23 
24 int main() {
25     #ifdef Phantom01
26         freopen("1002.txt", "r", stdin);
27     #endif // Phantom01
28 
29     int Case;
30     scanf("%d", &Case);
31     gets(str);
32 
33     while (Case--) {
34         gets(str);
35         int len = strlen(str);
36         memset(dp, -1, sizeof(dp));
37         printf("%d
", len - 2*dfs(0, len));
38     }
39 
40     return 0;
41 }

1002

1003：最小生成树

已知经纬度求球面距离连接

代码略。

1004：直接大数模拟。

代码略