A Hanoi Tower 递归
题意：
大家都很熟悉汉诺塔的递归程序，现在给你一个组合，询问你这个组合是否会出现在汉诺塔的递归过程中。
题解：
将汉诺塔的递归程序反过来思考，考虑当前最大的那个盘，我们只会将他从from移动到to，他上面的盘都移动到tmp，那么这个最大的盘一定不会在tmp。如果这个盘在from，说明当前正在进行的过程是将他上面的盘从from移动到tmp，如果这个盘在to，那么说明当前正在进行的过程是将他上面的盘从tmp移动到to。递归下去即可。
代码：
#include#include #include using namespace std;string s;int n;bool dfs(char from,char to,char tmp,int i) { if (i == n)return true; if (s[i] == tmp)return false; if (s[i] == from)return dfs(from, tmp, to, i + 1); if (s[i] == to)return dfs(tmp, to, from, i + 1);}int main() { ifstream cin("Input.txt"); ofstream cout("Output.txt"); cin.sync_with_stdio(false); cin >> n; cin >> s; reverse(s.begin(), s.end()); if (s[0] == 'C') { cout << "NO" << endl; return 0; } if (dfs('A', 'B', 'C', 0)) cout << "YES" << endl; else cout << "NO" << endl; return 0;}
B Island 模拟
题意：
给你一个加减号组成的图，问你有多少加号与减号相邻。
题解：
直接模拟就好了。
代码：
#include#include #include #include #include #include #include #include
C Sequence 打表找规律
题意：
给你一个序列生成器，定义$a[0]=1$，对于$i>0$，$a[i]=sort(a[i-1]*2)$，其中sort是按每一位排序，这个序列的前几项是1,2,4,8,16,23,46,29,58....
现在问你第n项是多少。
题解：
就把序列放到OEIS上，然后就知道规律了。
代码：
#include#include #include #define MAX_N 50using namespace std;long long n;long long a[MAX_N]={ 1, 2, 4, 8, 16, 23, 46, 29, 58, 116, 223, 446, 289, 578, 1156, 1223, 2446, 2489, 4789, 5789, 11578, 12356, 12247, 24449, 48889, 77789, 155578, 111356, 122227, 244445};int main() { ifstream cin("Input.txt"); ofstream cout("Output.txt"); cin >> n; n--; if (n < 30)cout << a[n] << endl; else cout << a[(n % 6) + 24] << endl; return 0;}
H Milestones 主席树
题意：
给你一个序列，然后若干次询问，询问从L到R之间有多少不同的值。
题解：
就。。这题是队友做的，貌似就建若干棵主席树，然后搞搞。
代码：
#include#include #include #define maxn 10010using namespace std;int tot, a[maxn], cnt;struct N { int ls, rs, w; } tree[300 * maxn];int roots[maxn], las[300];int build_tree(int l, int r) { int newnode = tot++; tree[newnode].w = 0; if (l != r) { int mid = (l + r) / 2; tree[newnode].ls = build_tree(l, mid); tree[newnode].rs = build_tree(mid + 1, r); } return newnode;}int updata(int rt, int pos, int val) { int newnode = tot++, tmp = newnode; tree[newnode].w = tree[rt].w + val; int l = 1, r = cnt; while (l < r) { int mid = (l + r) / 2; if (pos <= mid) { tree[newnode].ls = tot++; tree[newnode].rs = tree[rt].rs; newnode = tree[newnode].ls; rt = tree[rt].ls; r = mid; } else { tree[newnode].ls = tree[rt].ls; tree[newnode].rs = tot++; newnode = tree[newnode].rs; rt = tree[rt].rs; l = mid + 1; } tree[newnode].w = tree[rt].w + val; } return tmp;}int query(int rt, int k) { int l = 1,r = cnt; int ans = 0; if(k == 0) return tree[rt].w; while(l < r){ int mid = (l + r) / 2; if(k <= mid){ ans += tree[tree[rt].rs].w; rt = tree[rt].ls; r = mid; } else{ rt = tree[rt].rs; l = mid + 1; } } return ans;}int n, q;void print(int rt, int l = 1, int r = cnt) { printf("l = %d r = %d w = %d\n", l, r, tree[rt].w); if (l != r) { int mid = (l + r) / 2; print(tree[rt].ls, l, mid); print(tree[rt].rs, mid + 1, r); } } int main() { freopen("Input.txt", "r", stdin); freopen("Output.txt", "w", stdout); while (scanf("%d %d", &n, &q) != EOF) { for (int i = 1; i <= n; i++) scanf("%d", &a[i]); cnt = n; tot = 0; memset(las, -1, sizeof(las)); roots[0] = build_tree(1, cnt); for (int i = 1; i <= n; i++) { if (las[a[i]] == -1) { roots[i] = updata(roots[i - 1], i, 1); } else { roots[i] = updata(roots[i - 1], las[a[i]], -1); roots[i] = updata(roots[i], i, 1); } las[a[i]] = i; } int l, r; while (q--) { scanf("%d %d", &l, &r); printf("%d\n", query(roots[r], l - 1)); } } return 0;}
J Computer Network Tarjan+dp
题意：
给你一个图，问你加一条边，使得图的桥的数量减少到最少，输出这条边。
题解：
就Tarjan一发，令桥的权值是1，非桥的权值是0，在Tarjan树上寻找直径即可，整个过程可以在Tarjan的时候dp来完成。令dp[i]表示节点i到其子树的某个叶子的最长路径，然后维护每个点dp的最大和次大值，更新答案即可。
代码：
//#include#include #include #include #include #include #include #include #define MAX_N 100004#define MAX_M 100005using namespace std;int dfn[MAX_N],low[MAX_N],ind=0;bool vis[MAX_N];int dp[MAX_N];int pre[MAX_N];int ans = -1;int x,y;struct riGou {public: int u, v, id; riGou(int uu, int vv, int i) : u(uu), v(vv), id(i) { } riGou() { } bool operator<(const riGou &a) const { if (u == a.u) return v < a.v; return u < a.u; }};struct edge {public: int to, id; edge(int t, int i) : to(t), id(i) { } edge() { }};vector G[MAX_N];set se;bool haSame[MAX_N];void Tarjan(int u,int p) { dfn[u] = low[u] = ++ind; vis[u] = 1; int a = 0, b = 0; int nx = u, ny = u; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].to; if (v == p)continue; if (!vis[v]) { Tarjan(v, u); low[u] = min(low[u], low[v]); int ib = 0; if (low[v] > dfn[u] && haSame[G[u][i].id] == 0) ib = 1; if (a <= dp[v] + ib)b = a, a = dp[v] + ib, ny = nx, nx = pre[v]; else if (b <= dp[v] + ib)b = dp[v] + ib, ny = pre[v]; } else low[u] = min(dfn[v], low[u]); } dp[u] = a; pre[u] = nx; if (ans < a + b) { x = nx, y = ny; ans = a + b; }}int n,m;int main() { ifstream cin("Input.txt"); ofstream cout("Output.txt"); cin.sync_with_stdio(false); cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; riGou a(u, v, i); riGou b(v, u, i); auto it = se.find(a); if (it != se.end()) { haSame[it->id] = 1; continue; } it = se.find(b); if (it != se.end()) { haSame[it->id] = 1; continue; } G[u].push_back(edge(v, i)); G[v].push_back(edge(u, i)); se.insert(riGou(u, v, i)); } Tarjan(1, 0); if (x == y) cout << 1 << " " << n << endl; else cout << x << " " << y << endl; //cout << ans << endl; return 0;}