哎呀~
今年初赛做得太仓促，又犯蠢卡题了，做得不好。
所以现在决定临时训练一下！
下面是今年大区赛的题目信息——
前面什么排序for for for啦，基本stl 搞搞啦，字符串处理啦~
好好读题，想清楚怎么样最好写，最快写！
我发现，多关键字最短路、最小字典序，这些东西CCCC真的好喜欢出啊>.<
也许练一下会有不错的提高哦~
这里贴出几题代码——
【2017年团体程序设计天梯赛-大区赛 2-2】【多项式除法 STL-map】多项式A除以B
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int n, m; map<int, double>a, b, ans; map<int, double>::iterator it; void print(map<int, double> &ans) { for (it = ans.begin(); it != ans.end(); ) { if (fabs(it->second) < 0.05)ans.erase(it++); else it++; } if (ans.size() == 0) { puts("0 0 0.0"); } else { printf("%d", ans.size()); for (it = --ans.end(); ; --it) { printf(" %d %.1f", it->first, it->second); if (it == ans.begin())break; }puts(""); } } int main() { while(~scanf("%d", &n)) { a.clear(); for (int i = 1; i <= n; ++i) { int index; double coeff; scanf("%d%lf", &index, &coeff); a[index] += coeff; } scanf("%d", &m); b.clear(); for (int i = 1; i <= m; ++i) { int index; double coeff; scanf("%d%lf", &index, &coeff); b[index] += coeff; } ans.clear(); while (a.size() && b.size()) { auto A = --a.end(); auto B = --b.end(); double Index = A->first - B->first; if (Index < 0)break; double k = A->second / B->second; for (auto it : b) { int index = it.first + Index; double coeff = it.second * k; a[index] -= coeff; } for (it = a.begin(); it != a.end(); ) { if (fabs(it->second) < 0.0001)a.erase(it++); else it++; } ans[Index] += k; } print(ans); print(a); } return 0; } /* 【trick&&吐槽】 <1> 对于这种离散型的数据，也许最好的方法是使用map等结构 <2> 卡精度、卡精度、卡精度、卡精度、卡精度、卡精度 【题意】 实现多项式除法 【分析】 直接从高项开始，向低项方向处理，一项项处理即可。 */【2017年团体程序设计天梯赛-大区赛 3-2】【多关键字最短路】周游世界
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 10010, M = 100 * 100 * 200 * 2, Z = 1e9 + 7, inf = 0x3f3f3f3f; //最多点数100 * 100 //最多边数100 * 100 * 100 * 2 typedef pair<int, int>P; struct Node { int x, d1, d2; bool operator < (const Node & b)const { if (d1 != b.d1)return d1 > b.d1; return d2 > b.d2; } }; priority_queue<Node>q; int casenum, casei; int num; int first[N], id; int w[M], nxt[M], c_d1[M], c_d2[M], c_c[M]; int a[N]; int D1[N], D2[N], C[N], pre[N]; int ST, ED; void print(int x) { if (x == ST)return; int y = pre[x]; print(y); printf("Go by the line of company #%d from d to d.\n", C[x], y, x); } void ins(int x, int y, int d1, int d2, int c) { w[++id] = y; nxt[id] = first[x]; c_d1[id] = d1; c_d2[id] = d2; c_c[id] = c; first[x] = id; } void inq(int x, int d1, int d2, int c, int y) { if (d1 < D1[x] || d1 == D1[x] && d2 < D2[x]) { D1[x] = d1; D2[x] = d2; C[x] = c; pre[x] = y; q.push({ x,D1[x], D2[x] }); } } bool e[N]; void dijkstra() { for (int i = 0; i <= 10000; ++i) { e[i] = 0; D1[i] = inf; } while (!q.empty())q.pop(); inq(ST, 0, 0, 0, 0); while (!q.empty()) { int x = q.top().x; int d1 = q.top().d1; int d2 = q.top().d2; q.pop(); if (e[x])continue; if (x == ED) { printf("%d\n", D1[x]); print(ED); return; } e[x] = 1; for (int z = first[x]; z; z = nxt[z]) { inq(w[z], D1[x] + c_d1[z], D2[x] + c_d2[z], c_c[z], x); } } puts("Sorry, no line is available."); } int main() { id = 1; scanf("%d", &num); for (int I = 1; I <= num; ++I) { int g; scanf("%d", &g); for (int i = 1; i <= g; ++i) { scanf("%d", &a[i]); if (i != 1)a[i + g - 1] = a[i]; } int top = a[1] == a[g] ? g + g - 1 : g; for (int i = 1; i <= g; ++i) { for (int j = i + 1; j <= top; ++j) { int x = a[i]; int y = a[j]; ins(x, y, j - i, 1, I); ins(y, x, j - i, 1, I); } } } int q; scanf("%d", &q); while (q--) { scanf("%d%d", &ST, &ED); dijkstra(); } return 0; } /* 【trick&&吐槽】 这题给我最大的教训是—— 做题要冷静，先认真读题，理清题目要你做什么 【题意】 有n（100）个联盟公司。 每个公司有m（100）个停经站。 相邻的停经站之间的的边只属于这一家公司（也就是没有重边）。 K（10）次询问。我们想要使得—— <1> 中途经站最少 <2> 换成次数最少 <3> 记录路线 【分析】 这显然是个最短路，最多会有100 * 100个点，于是这里就应该放弃floyd. 然后我们就最好用dijkstra了。 我们需要记录一个二维最短路，同时还要记一个前驱 【时间复杂度&&优化】 */
【2017年团体程序设计天梯赛-大区赛 3-3】【状压DP + 贪心】球队“食物链”
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 24, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; char s[N][N]; bool win[N][N]; int n; int f[1 << 20][20]; int nxt[1 << 20][20]; void print(int sta, int fst) { if (fst == 0)return; printf(" %d", fst + 1); print(sta ^ 1 << fst, nxt[sta][fst]); } void solve() { MS(f, 0); f[1][0] = 1; MS(nxt, 63); int top = (1 << n) - 1; for (int sta = 0; sta <= top; ++sta) { for (int i = 0; i < n; ++i)if ((sta >> i & 1) && f[sta][i]) { for (int j = 0; j < n; ++j)if ((~sta >> j & 1) && win[j][i]) { f[sta | 1 << j][j] = 1; gmin(nxt[sta | 1 << j][j], i); } } } for (int i = 1; i < n; ++i) { if (f[top][i] && win[0][i]) { printf("1"); print(top, i); puts(""); return; } } puts("No Solution"); } int main() { while (~scanf("%d", &n)) { for (int i = 0; i < n; ++i)scanf("%s", s[i]); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { win[i][j] = (s[i][j] == 'W' || s[j][i] == 'L'); } } solve(); } return 0; } /* 【trick&&吐槽】 天梯赛的题目会很喜欢给trick 所以说仔细读题真的是太重要了—— 联赛采用主客场双循环赛制，参赛球队两两之间在双方主场各赛一场。 联赛战罢，结果已经尘埃落定。此时，联赛主席突发奇想，希望从中找出一条包含所有球队的“食物链”，来说明联赛的精彩程度。 “食物链”为一个1至N的排列{ T1 T2 ... TN }，满足：球队T1战胜过球队T2，球队T2战胜过球队T3，……，球队T(N-1)战胜过球队TN，球队TN战胜过球队T1。 这里的"战胜过"的条件非常重要。 【题意】 我们希望找一个最小字典序的哈密顿环 【分析】 哈密顿环可以按照O(2^n * n * n)的复杂度做DP。 而现在要求字典序最小。 于是显然可以—— 把第一个位置和最后一个位置都固定为1 然后按照贪心原则，每次把一个数放在前面做DP 【时间复杂度&&优化】 O(nlogn) */【2016年团体程序设计天梯赛 L3-001】【背包 贪心】凑零钱
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 1e4 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int n, m; int a[N]; bool f[10005][102]; int pre[10005][102]; void print(int n, int m) { if (pre[n][m] == 0)printf("%d\n", m - pre[n][m]); else { if(pre[n][m] != m)printf("%d ", m - pre[n][m]); print(n - 1, pre[n][m]); } } int main() { while(~scanf("%d%d", &n, &m)) { for (int i = 1; i <= n; ++i)scanf("%d", &a[i]); sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1); MS(f[0], 0); f[0][0] = 1; for (int i = 1; i <= n; ++i) { int x = a[i]; for (int j = m; j >= 0; --j) { f[i][j] = f[i - 1][j]; pre[i][j] = j; } for (int j = m; j >= x; --j)if (f[i - 1][j - x]) { f[i][j] = 1; pre[i][j] = j - x; } } if (!f[n][m])puts("No Solution"); else print(n, m); } return 0; } /* 【题意】 n个数中任选若干个构成和为m 输出字典序最小的解 【分析】 字典序最小还是从大到小向前贪心得稳妥！ */【2016年团体程序设计天梯赛 L3-002】【堆栈 双SET查中位数】堆栈
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int n; char op[100]; multiset<int>a, b; #include<stack> stack<int>sta; void update() { while (a.size() > b.size() + 1) { int val = *--a.end(); a.erase(--a.end()); b.insert(val); } while (a.size() < b.size()) { int val = *b.begin(); b.erase(b.begin()); a.insert(val); } } int main() { while(~scanf("%d", &n)) { a.clear(); b.clear(); while (!sta.empty())sta.pop(); for (int i = 1; i <= n; ++i) { scanf("%s", op); if (!strcmp(op, "Pop")) { if (sta.empty())puts("Invalid"); else { int val = sta.top(); sta.pop(); if (a.find(val) != a.end())a.erase(a.find(val)); else if (b.find(val) != b.end())b.erase(b.find(val)); update(); printf("%d\n", val); } } else if (!strcmp(op, "PeekMedian")) { if (a.size())printf("%d\n", *--a.end()); else puts("Invalid"); } else { int val; scanf("%d", &val); sta.push(val); if (a.empty())a.insert(val); else if (val <= *--a.end())a.insert(val); else b.insert(val); update(); } } } return 0; } /* 【trick&&吐槽】 <1> 双set维护中位数时，插入操作是要先做判定的 <2> 如果看代码没找到错，就应该思考算法逻辑的问题了 【题意】 维护栈的同时维护中位数 */【2016年团体程序设计天梯赛 L3-003】【并查集】社交集群
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 1010, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int n; int f[N], d[N]; int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } int main() { while(~scanf("%d", &n)) { for (int i = 1; i <= 1000; ++i) { f[i] = i; d[i] = 0; } for (int i = 1; i <= n; ++i) { int g; scanf("%d%*c", &g); if (!g)continue; --g; int x; scanf("%d", &x); int fa = find(x); ++d[fa]; while (g--) { int x; scanf("%d", &x); x = find(x); if (x != fa) { f[x] = fa; d[fa] += d[x]; } } } vector<int>vt; vt.clear(); for (int i = 1; i <= 1000; ++i)if (find(i) == i && d[i]) { vt.push_back(d[i]); } sort(vt.begin(), vt.end()); printf("%d\n", vt.size()); for (int i = vt.size() - 1; ~i; --i) { printf("%d%c", vt[i], i == 0 ? '\n' : ' '); } } return 0; } /* 【trick&&吐槽】 理解题意非常重要。 【题意】 每个人可能有多个兴趣 如果存在任意一个兴趣相同，则这两个人可以建立朋友关系 问你有多少个极大的朋友关系连通子图 【分析】 直接并查集搞搞就好啦 注意输出的时候是对于连通块的根做输出 */至于后面的几道题，我们也看一下——
L3-004肿瘤诊所 简单的BFS
L3-005 垃圾箱分布 无脑最短路
L3-006 迎风一刀斩，耐心细心分类讨论
L3-007 天梯地图 我的天，debug了一天，发现是priority_queue的运算符搞反了，于是反一反之后就得到了一个dijkstra的板子
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 505, M = N * N * 2, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int n, m; struct Up { LL c1, c2; bool operator < (const Up &b)const { if (c1 != b.c1)return c1 < b.c1; return c2 < b.c2; } Up operator + (const Up &b)const { return{ c1 + b.c1, c2 + b.c2 }; } }; struct Node { int x; Up up; bool operator < (const Node &b)const { return b.up < up;//Be Careful } }; struct Dijkstra { int ST, ED; int first[N], id; int w[M], nxt[M]; Up c[M]; Up f[N]; int pre[N]; bool sure[N]; priority_queue<Node>q; void init() { for (int i = n + 1; i >= 0; --i)first[i] = 0; id = 1; } void ins(int x, int y, Up up) { w[++id] = y; nxt[id] = first[x]; c[id] = up; first[x] = id; } void inq(int x, int y, Up up) { if (up < f[y]) { f[y] = up; pre[y] = x; q.push({ y,f[y] }); } } void dijkstra(int st_, int ed_) { ST = st_; ED = ed_; for (int i = n + 1; i >= 0; --i) { f[i] = { (LL)1e18, (LL)1e18 }; sure[i] = 0; } while (!q.empty())q.pop(); inq(0, ST, { 0,0 }); while (!q.empty()) { int x = q.top().x; q.pop(); if (sure[x])continue; sure[x] = 1; for (int z = first[x]; z; z = nxt[z]) { inq(x, w[z], f[x] + c[z]); } } } void print(int x) { if (x == ST) { printf("%d", ST); return; } print(pre[x]); printf(" => %d", x); } vector<int>rd; void getroad(int x) { if (x == ST)rd.clear(); else getroad(pre[x]); rd.push_back(x); } }d1, d2; int main() { while (~scanf("%d%d", &n, &m)) { d1.init(); d2.init(); for (int i = 1; i <= m; ++i) { int x, y, oneway, len, time; scanf("%d%d%d%d%d", &x, &y, &oneway, &len, &time); d1.ins(x, y, { time, len }); d2.ins(x, y, { len, 1 }); if (!oneway) { d1.ins(y, x, { time,len }); d2.ins(y, x, { len,1 }); } } int st, ed; scanf("%d%d", &st, &ed); d1.dijkstra(st, ed); d2.dijkstra(st, ed); d1.getroad(ed); d2.getroad(ed); if (d1.rd == d2.rd) { printf("Time = %d; ", d1.f[ed].c1); printf("Distance = %d: ", d1.f[ed].c2); d1.print(ed); puts(""); } else { printf("Time = %d: ", d1.f[ed].c1); d1.print(ed); puts(""); printf("Distance = %d: ", d2.f[ed].c1); d2.print(ed); puts(""); } } return 0; } /* 【题意】 直接的多关键字最短路 使用dijkstra的模板写起来更方便哦~ */L3-008 喊山 BFS水题
然后就没有再做啦~~
