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 36 37 38 39 40 41 42 43 44 45 | #include<iostream> #include<cstdlib> #include<cstring> #include<ctime> #include<vector> #include<list> #include<cmath> #include<queue> #include<unordered_set> #include<unordered_map> using namespace std; int n, m, e; vector<int> edges[2005]; bool visited[2005]; int match[2005]; bool biFind(int node) { if (visited[node])return false; visited[node] = true; for (int i = 0; i < edges[node].size(); i++) { if (!match[edges[node][i]] || biFind(match[edges[node][i]])) { match[node] = edges[node][i]; match[edges[node][i]] = node; return true; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> e; for (int i = 1; i <= e; i++) { int u, v; cin >> u >> v; if (u > n || v > m)continue; edges[u].push_back(v + n); edges[v + n].push_back(u); } int cnter = 0; for (int i = 1; i <= n; i++) { memset(visited, false, sizeof(visited)); if (biFind(i))cnter++; } cout << cnter; } |
分类目录归档:算法
洛谷 P3379 【模板】最近公共祖先(LCA)重写
朴素算法:洛谷70分,O2 80分
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 36 37 38 | #include<iostream> #include<vector> using namespace std; int n, m, s; vector<int> edges[500005]; int father[500005],depth[500005]; void dfs(int node, int fath) { father[node] = fath; depth[node] = depth[fath] + 1; for (int i = 0; i < edges[node].size(); i++) { if (edges[node][i] == fath)continue; dfs(edges[node][i], node); } } int query(int a, int b) { while (a != b) { if (depth[a] >= depth[b])a = father[a]; else b = father[b]; } return a; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s; for (int i = 1; i <= n - 1; i++) { int x, y; cin >> x >> y; edges[x].push_back(y); edges[y].push_back(x); } dfs(s, s); for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; cout << query(a, b) << "\n"; } } |
倍增:洛谷80分,O2 100分
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 36 37 38 39 40 41 42 43 44 45 | #include<iostream> #include<vector> #include<algorithm> #define MAXLOG 20 using namespace std; int n, m, s; vector<int> edges[500005]; int depth[500005]; int ancestor[500005][MAXLOG+2]; void dfs(int node, int fath) { ancestor[node][0] = fath; depth[node] = depth[fath] + 1; for (int i = 1; i <= MAXLOG; i++)ancestor[node][i] = ancestor[ancestor[node][i - 1]][i - 1]; for (int i = 0; i < edges[node].size(); i++) { if (edges[node][i] == fath)continue; dfs(edges[node][i], node); } } int query(int a, int b) { if (depth[b] > depth[a])swap(a, b); for (int i = MAXLOG; ~i; i--)if (depth[ancestor[a][i]] >= depth[b])a = ancestor[a][i]; if (a == b)return a; for (int i = MAXLOG; ~i; i--) if(ancestor[a][i]!=ancestor[b][i]){ a = ancestor[a][i]; b = ancestor[b][i]; } return ancestor[a][0]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s; for (int i = 1; i <= n - 1; i++) { int x, y; cin >> x >> y; edges[x].push_back(y); edges[y].push_back(x); } dfs(s, s); for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; cout << query(a, b) << "\n"; } } |
Tarjan:洛谷70分,O2 100分
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include<iostream> #include<vector> #include<algorithm> #include<cstring> using namespace std; int n, m, s; vector<int> edges[500005],askPair[500005]; bool visited[500005]; int father[500005]; inline int _find(int node) { if (father[node]==-1)return node; return father[node] = _find(father[node]); } inline void _union(int x, int y) { if(_find(x)!=_find(y))father[_find(x)] = y; } struct ask { int u, v; int ans; }asks[500005]; inline int checkV(int id,int node) { if (asks[id].u != node)return asks[id].u; return asks[id].v; } void dfs(int node,int fath) { for (int i = 0; i < edges[node].size(); i++) { if (edges[node][i] == fath)continue; dfs(edges[node][i],node); _union(edges[node][i], node); } visited[node] = true; for (int i = 0; i < askPair[node].size(); i++) { int v = checkV(askPair[node][i], node); if (visited[v])asks[askPair[node][i]].ans = _find(v); } } int main() { memset(father, -1, sizeof(father)); ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s; for (int i = 1; i <= n - 1; i++) { int x, y; cin >> x >> y; edges[x].push_back(y); edges[y].push_back(x); } for (int i = 1; i <= m; i++) { cin >> asks[i].u >> asks[i].v; askPair[asks[i].u].push_back(i); askPair[asks[i].v].push_back(i); } dfs(s,s); for (int i = 1; i <= m; i++)cout << asks[i].ans << "\n"; } |
计蒜客 Random Access Iterator
原题链接:https://nanti.jisuanke.com/t/41392
竟然做出来一道这么复杂的概率+DFS+逆元题,开心到爆炸,特此发题解一篇^v^
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<string> #include<cstring> #include<algorithm> #include<vector> #define MOD 1000000007 #define ll long long using namespace std; int n; int MDep; vector<int> edges[1000005]; bool visited[1000005]; ll quickpow(ll a, ll b) { if (b == 0)return 1; ll re = quickpow(a, b / 2) % MOD; re = (re * re) % MOD; if (b % 2 == 1)re *= a % MOD; return re % MOD; } inline ll inv(ll x) { return quickpow(x, MOD - 2) % MOD; } inline ll chance1(ll TotNode) { ll ch = (inv(TotNode)) % MOD; return ch; } inline ll chance2(ll onceCh,ll TotNode) { ll onceNonch = (1ll-onceCh+MOD) % MOD; ll nonch = quickpow(onceNonch, TotNode); ll fin = (1ll - nonch + MOD) % MOD; return fin; } int dfsMaxDep(int node) { int maxDep = 1; bool hasChild = false; visited[node] = true; for (int i = 0; i < edges[node].size(); i++) { if (visited[edges[node][i]])continue; hasChild = true; maxDep = max(maxDep, dfsMaxDep(edges[node][i]) + 1); } return maxDep; } ll dfsChance(int depth,int node){ if (depth == MDep)return 1; ll ch = 0,sCh=chance1(node==1?edges[node].size(): edges[node].size()-1); visited[node] = true; for (int i = 0; i < edges[node].size(); i++) { if (visited[edges[node][i]])continue; ll CurCH = dfsChance(depth + 1, edges[node][i]); if (CurCH) { ch += (CurCH * sCh) % MOD; ch %= MOD; } } return chance2(ch, node == 1 ? edges[node].size() : edges[node].size() - 1); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; edges[u].push_back(v); edges[v].push_back(u); } MDep = dfsMaxDep(1); memset(visited, false, sizeof(visited)); ll ch = dfsChance(1, 1); cout << ch; } |
UVA1588 换抵挡装置 Kickdown
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 | #include<iostream> #include<string> #include<map> #include<algorithm> #include<cmath> #include<cstring> #include<typeinfo> using namespace std; int solve(string a, string b) { a.append(b.size(), '0'); for (int i = 0; i < a.size()-b.size()+1; i++) { bool flag = true; for (int j = 0; j < b.size(); j++) { if (a[i+j] + b[j] - '0' > '3') { flag = false; break; } } if (flag) return max(a.size()-b.size(), i + b.size()); } return a.size(); } int main() { ios::sync_with_stdio(false); cin.tie(0); string a, b; while (cin >> a >> b)cout<<min(solve(a, b),solve(b,a))<<'\n'; } |
UVA202 循环小数 Repeating Decimals
模拟除法,当出现余数第二次相同时可以记为一个循环节。
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 36 37 38 39 40 | #include<iostream> #include<string> #include<map> #include<cmath> #include<cstring> #include<typeinfo> using namespace std; void solve(int a, int b) { int OA = a; string strInt = to_string(a / b); a %= b; a *= 10; string strDec = ""; map<int, int> dict; while (dict.count(a) == 0) { dict[a] = strDec.size(); strDec += to_string(a / b); a %= b; a *= 10; } string strDec1 = strDec.substr(0, dict[a]); string strDec2 = strDec.substr(dict[a]); string strDec3 = ""; if (strDec2.size() > 50) { strDec3 = '(' + strDec2.substr(0, 50) + "...)"; } else { strDec3 = '(' + strDec2 + ")"; } cout << OA << "/" << b << " = " << strInt << "." << strDec1 << strDec3 << '\n'; cout << " " << strDec2.size() << " = number of digits in repeating cycle" << '\n'; cout << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(0); int a, b; while (cin >> a >> b)solve(a, b); } |
UVA1368 DNA序列 DNA Consensus String
解题思路是,统计所有字符串对应位置上出现次数最多的字母,并将其拼接起来作为Hamming距离和最小的DNA序列,也可以算作贪心。
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 36 37 38 39 40 | #include<iostream> #include<string> #include<cmath> #include<cstring> #include<typeinfo> using namespace std; int t, m, n; int seq[5]; string strArr[1005]; inline void seqSet(char c) { switch (c) { case 'A':seq[1]++; break; case 'C':seq[2]++; break; case 'G':seq[3]++; break; case 'T':seq[4]++; break; } } char seqGet[6] = " ACGT"; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> t; while (t--) { cin >> m >> n; for (int i = 1; i <= m; i++)cin >> strArr[i]; int cnt = 0; for (int i = 0; i < n; i++) { memset(seq, 0, sizeof(seq)); for (int k = 1; k <= m; k++)seqSet(strArr[k][i]); int Pmax = 1; for (int p = 2; p <= 4; p++) if (seq[p] > seq[Pmax]) Pmax = p; cnt += m - seq[Pmax]; cout << seqGet[Pmax]; } cout << '\n'; cout << cnt << '\n'; } } |
蓝桥杯 历届试题 小计算器
问题描述
模拟程序型计算器,依次输入指令,可能包含的指令有
1. 数字:’NUM X’,X为一个只包含大写字母和数字的字符串,表示一个当前进制的数
2. 运算指令:’ADD’,’SUB’,’MUL’,’DIV’,’MOD’,分别表示加减乘,除法取商,除法取余
3. 进制转换指令:’CHANGE K’,将当前进制转换为K进制(2≤K≤36)
4. 输出指令:’EQUAL’,以当前进制输出结果
5. 重置指令:’CLEAR’,清除当前数字
指令按照以下规则给出:
数字,运算指令不会连续给出,进制转换指令,输出指令,重置指令有可能连续给出
运算指令后出现的第一个数字,表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
重置指令后出现的第一个数字,表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
进制转换指令可能出现在任何地方
运算过程中中间变量均为非负整数,且小于2^63。
以大写的’A’~’Z’表示10~35
输入格式
第1行:1个n,表示指令数量
第2..n+1行:每行给出一条指令。指令序列一定以’CLEAR’作为开始,并且满足指令规则
输出格式
依次给出每一次’EQUAL’得到的结果
样例输入
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
样例输出
2040
可以说样例给的挺恶心。会让人想不到,这玩意要考虑还是不考虑优先级!?最后在测试下是不需要考虑优先级的。直接挨着个的算即可。还有一个点是我进制转换写错了(竟然’A’->11,生无可恋脸)一直在调这里。。。。其他没啥了。
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #include<iostream> #include<deque> #include<algorithm> #include<cassert> #include<cstdlib> #include<string> using namespace std; int n; int radix = 10; string radixS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; deque<long long> sll; deque<string> sop; long long value; inline long long getCorDecimal(char c) { if ('0' <= c && c <= '9')return c - '0'; if ('A' <= c && c <= 'Z')return c - 'A' + 10; assert(false); return -1; } long long Radix2Decimal(string s) { reverse(s.begin(), s.end()); long long cntBase = 1, result = 0; for (int i = 0; i<s.size(); i++) { result += getCorDecimal(s[i])*cntBase; cntBase *= radix; } return result; } string Decimal2Radix(long long v) { string s = ""; while (v) { s.push_back(radixS[v%radix]); v /= radix; } if (s == "")s = "0"; reverse(s.begin(), s.end()); return s; } bool calculate4Back() { if (sop.empty())return false; string & comm = sop.back(); if (comm == "ADD")value += sll.back(); else if (comm == "SUB")value = sll.back() - value; else if (comm == "MUL")value *= sll.back(); else if (comm == "DIV")value = sll.back() / value; else if (comm == "MOD")value = sll.back() % value; else assert(false); sop.pop_back(); sll.pop_back(); sll.push_back(value); return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { string comm, radixV; cin >> comm; if (comm == "NUM") { cin >> radixV; value = Radix2Decimal(radixV); if (!calculate4Back())sll.push_back(value); //cout<<Decimal2Radix(sll.front())<<endl; } else if (comm == "ADD" || comm == "SUB" || comm == "MUL" || comm == "DIV" || comm == "MOD") { sop.push_back(comm); } else if (comm == "CHANGE") { cin >> radix; } else if (comm == "EQUAL") { cout << Decimal2Radix(sll.front()) << endl; } else if (comm == "CLEAR") { sll.clear(); sop.clear(); } } } |
团体程序设计天梯赛-练习集 L3-001 凑零钱
DFS T一个点29分代码:
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 | #include<iostream> #include<cstdio> #include<algorithm> #include<stack> #include<queue> using namespace std; int n,m; int money[10005]; int recorder[10005]; bool dfs(int no,int curPos,int remainValue){ recorder[no]=money[curPos]; if(remainValue==0)return true; int upp=upper_bound(money+1,money+n+1,remainValue)-money; for(int i=curPos+1;i<upp;i++){ if(dfs(no+1,i,remainValue-money[i]))return true; else i=upper_bound(money+1,money+n+1,money[i])-money-1; } recorder[no]=0; //忘加了这个,回溯差点没做好 return false; } int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",money+i); sort(money+1,money+n+1); bool flag=dfs(0,0,m); if(!flag)printf("No Solution"); else{ int i=1; while(recorder[i]!=0){ if(i!=1)printf(" "); printf("%d",recorder[i++]); } } } |
团体程序设计天梯赛-练习集 L3-015 球队“食物链”
如下三个坑点:
1、所给的图非对称,因为每个队打了两场比赛,每一场分别记输赢。所以每行数据都要做处理。
2、要求食物链的字典序最小,而且该食物链是从1到n的排列,因此只要有环,头一个一定从1开始是字典序最小的状况,只需要从1开始DFS即可。
3、剪枝:不剪枝T一个点。在DFS中把经过的点标记,若未标记的点集中不存在与1连通的点,则不可能构成环状结构,直接return false。
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 36 37 38 39 40 41 42 43 44 45 | #include<iostream> #include<stack> #include<queue> using namespace std; int n; char arr[25][25]; deque<int> st; bool visited[25]; bool dfs(int curNode,int visitedNodeCnt){ if(visited[curNode]){ if(visitedNodeCnt==n+1&&curNode==1)return true; else return false; } bool flag=false; for(int i=1;i<=n;i++){ if(!visited[i]&&(arr[i][1]=='W'||arr[1][i]=='L'))flag=true; } if(!flag)return false; visited[curNode]=true; for(int i=1;i<=n;i++){ if(i==curNode)continue; if(arr[curNode][i]=='W'||arr[i][curNode]=='L'){ if(dfs(i,visitedNodeCnt+1)){ st.push_back(i); return true; } } } visited[curNode]=false; return false; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%s",arr[i]+1); bool flag=dfs(1,1); if(!flag)printf("No Solution\n"); else{ printf("%d",st.front()); st.pop_front(); while(!st.empty()){ printf(" %d",st.back()); st.pop_back(); } } } |
高精度模版
最终版本的带符号的和无符号的高精度类:(将来应该不会再更新)
支持高精度加、减、乘、除、模。
继续阅读