1007 Naive Operations
还是写的有点冗余。
ai / bi ,ai从0开始增，转换成bi一直减，减到0就说明除法商+1。这样就维护区间最小值，最小值 == 0就说明 +1。这还有个调和级数的概念。
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int maxn = 1e5 + 50; int b[maxn]; #define lson q * 2 #define rson q * 2 + 1 #define mid ((l + r) >> 1) struct node { int minv; int lazy; int sum; ///表示减到0的次数 }tree[maxn * 4]; void push_up(int q) { tree[q].minv = min(tree[lson].minv, tree[rson].minv); tree[q].sum = tree[lson].sum + tree[rson].sum; } void push_down(int q) { if(tree[q].lazy) { tree[lson].lazy += tree[q].lazy; tree[rson].lazy += tree[q].lazy; tree[lson].minv -= tree[q].lazy; tree[rson].minv -= tree[q].lazy; tree[q].lazy = 0; } } void build(int l, int r, int q) { tree[q].lazy = 0; tree[q].sum = 0; if(l == r) { tree[q].minv = b[l]; return; } build(l, mid, lson); build(mid + 1, r, rson); push_up(q); } void update(int sl, int sr, int l, int r, int q) { if(sl <= l &&sr >= r) { if(tree[q].minv > 1) { tree[q].lazy++; tree[q].minv--; return; } if(l == r) ///单点的话，就更新 区间就进入单点 { tree[q].minv = b[l]; ///缩到了单点 tree[q].sum++; return; } } push_down(q); if(sl <= mid) update(sl, sr, l, mid, lson); if(sr >= mid + 1) update(sl, sr, mid + 1, r, rson); push_up(q); } int query(int sl, int sr, int l, int r, int q) { if(sl <= l && sr >= r) { return tree[q].sum; } push_down(q); int sum = 0; if(sl <= mid) sum += query(sl, sr, l, mid, lson); if(sr > mid) sum += query(sl, sr, mid + 1, r, rson); return sum; } char s[15]; int main() { int n, q; while(scanf("%d %d", &n, &q) != EOF) { for(int i = 1; i <= n; i++) { scanf("%d", &b[i]); } build(1, n, 1); int l, r; for(int i = 1; i <= q; i++) { scanf("%s %d %d", s, &l, &r); if(s[0] == 'a') { update(l, r, 1, n, 1); // for(int j = 1; j <= 9; j++) // { // printf("update q = %d sum = %d minv = %d lazy = %d ",j,tree[j].sum,tree[j].minv, tree[j].lazy); // } } else { int ans = query(l, r, 1, n, 1); printf("%d ", ans); } } } return 0; }
1005 Hack It
n = 5时，
10000 10000 10000 10000 10000 +0
10000 01000 00100 00010 00001 +1
10000 00100 00001 01000 00010 +2
10000 00010 01000 00001 00100 +3
10000 00001 00010 00100 01000 +4
01000 01000 01000 01000 01000 +1
……
10000
00001
00010
00100
01000
但看第五个矩阵我们发现他没有重复，实际上是
0 × 4 % 5 = 0
1 × 4 % 5 = 4
2 × 4 % 5 = 3
3 × 4 % 5 = 2
4 × 4 % 5 = 1
如何能保证这种方式不会有四角全为1的矩阵呢？
#include <bits/stdc++.h> using namespace std; int s[2500][2500]; int main() { // memset(s, 0, sizeof(s)); int n = 47; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { for(int k = 0; k < n; k++) { s[i * n + j][k * n + (j * k + i) % n] = 1; } } } printf("2000 "); for(int i = 0; i < 2000; i++) { for(int j = 0; j < 2000; j++) { printf("%d", s[i][j]); } printf(" "); } }
1003 Cover
这题和HDU3018类似，只不过3018没让求具体路径。
HDU3018的做法：
判断联通块个数，对每个联通块，没有奇数点，就用一笔画把他们连起来。
有奇数点，则需要一笔画的个数是 (奇数点个数 / 2)。 因为一条线可以消两个点。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 50; int pre[maxn]; int in[maxn]; int Find(int x) { if(x == pre[x]) return x; return pre[x] = Find(pre[x]); ///路径压缩 } void Merge(int x, int y) { pre[Find(x)] = Find(y); } int calcun[maxn]; int main() { int n, m; while(scanf("%d %d", &n, &m) != EOF) { for(int i = 1; i <= n; i++) pre[i] = i; memset(in, 0, sizeof(in)); for(int i = 1; i <= m; i++) { int x, y; scanf("%d %d", &x, &y); in[x]++; in[y]++; Merge(x, y); } memset(calcun, -1, sizeof(calcun)); for(int i = 1; i <= n; i++) { int fa = Find(i); if(calcun[fa] < 0 && in[i] > 0) ///未记录，并且不孤立 { calcun[fa] = 0; } if(in[i] % 2) { calcun[fa]++; } } int ans = 0; for(int i = 1; i <= n; i++) { if(calcun[i] >= 0) { if(calcun[i] == 0) ans++; ///无奇数的点 else ans += calcun[i] / 2; } } printf("%d ", ans); } }
用前向星写的一直WA，写成Vector后AC，但是输出顺序不同，找了一天WA点也没找到，先放放。
Vector:
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 50; vector<int> point; int degree[maxn]; int vis[maxn]; vector<int> G[maxn]; struct Edge { int from, to, cost, vis; }; vector<Edge> edges; int tot = 0; vector<int> path; vector<int> ans[maxn]; void addedge(int from, int to, int cost) { //printf("%d ", cost); edges.push_back(Edge{from, to, cost, 0}); edges.push_back(Edge{to, from, -cost, 0}); int sz = edges.size(); G[from].push_back(sz - 2); G[to].push_back(sz - 1); degree[from]++; degree[to]++; } void init(int n) { edges.clear(); for(int i = 0; i <= n; i++) { G[i].clear(); degree[i] = 0; vis[i] = 0; ans[i].clear(); } } void dfs1(int u) { vis[u] = 1; if(degree[u] % 2) point.push_back(u); for(int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if(vis[e.to]) continue; dfs1(e.to); } } void dfs2(int u) { for(int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if(e.vis) continue; // printf("u=%d v=%d cost=%d ", u, e.to, e.cost); e.vis = edges[G[u][i] ^ 1].vis = 1; // printf("i = %d %d ", i, edges[i].cost); dfs2(e.to); path.push_back(e.cost); } } int main() { int n, m; while(scanf("%d %d", &n, &m) != EOF) { init(n); for(int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); addedge(u, v, i); } /* for(int i = 1; i <= n; i++) { printf("%d ", degree[i]); } printf(" ");*/ ///先找到联通块，找奇数点，奇数点连边，跑欧拉回路，去掉连的边 int cnt = 0; for(int i = 1; i <= n; i++) { if(vis[i] || degree[i] == 0) continue; point.clear(); path.clear(); dfs1(i); // printf("%d ", point.size()); for(int j = 2; j < (int)point.size(); j += 2) { // printf("%d %d ", point[j], point[j + 1]); addedge(point[j], point[j + 1], 0); ///奇数点连边 } ///确定起点 int s = (point.empty() ? i : point[0]); dfs2(s); //for(int j = 0; j < path.size(); j++) printf("%d ", path[j]); for(int j = path.size() - 1; j >= 0; j--) { cnt++; while(j >= 0 && path[j] != 0) { ans[cnt].push_back(path[j]); j--; } } } printf("%d ", cnt); /* for(int i = 1; i <= cnt; i++) { printf("%d", ans[i].size()); for(int j = 0; j < ans[i].size(); j++) { printf(" %d",ans[i][j]); } printf(" "); }*/ // return 0; } return 0; } /* 3 3 1 2 1 3 2 3 4 6 1 2 1 3 2 3 3 4 4 2 1 4 2 2 6 5 4 4 -3 -1 2 8 7921 8116 */
前向星：
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 50; vector<int> point; int degree[maxn]; int vis[maxn]; struct Edge { int to, cost, Next, vis; }edge[maxn * 2]; int tot = 0; int head[maxn]; vector<int> path; vector<int> ans[maxn]; void add(int from, int to, int cost) { edge[tot].Next = head[from]; edge[tot].to = to; edge[tot].cost = cost; edge[tot].vis = 0; head[from] = tot++; } void addedge(int from, int to, int cost) { add(from, to, cost); add(to, from, -cost); } void dfs1(int u) { vis[u] = 1; if(degree[u] % 2) point.push_back(u); for(int i = head[u]; ~i; i = edge[i].Next) { int v = edge[i].to; if(vis[v]) continue; dfs1(v); } } void dfs2(int u) { for(int i = head[u]; ~i; i = edge[i].Next) { if(edge[i].vis) continue; edge[i].vis = edge[i ^ 1].vis = 1; // printf("u=%d v=%d cost=%d ", u, edge[i].to, edge[i].cost); dfs2(edge[i].to); path.push_back(edge[i].cost); } } int main() { //freopen("1003.txt", "r", stdin); int n, m; while(scanf("%d %d", &n, &m) != EOF) { memset(head, -1, sizeof(head)); tot = 0; for(int i = 1; i <= n; i++) { degree[i] = 0; vis[i] = 0; ans[i].clear(); } for(int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); addedge(u, v, i); ///判断点奇偶 degree[u]++; degree[v]++; } /* for(int i = 1; i <= n; i++) { printf("%d ", degree[i]); } printf(" ");*/ ///先找到联通块，找奇数点，奇数点连边，跑欧拉回路，去掉连的边 int cnt = 0; for(int i = 1; i <= n; i++) { if(vis[i] || degree[i] == 0) continue; point.clear(); path.clear(); dfs1(i); // printf("%d ", point.size()); for(int j = 2; j < (int)point.size(); j += 2) { // printf("%d %d ", point[j], point[j + 1]); addedge(point[j], point[j + 1], 0); ///奇数点连边 } ///确定起点 int s = (point.empty() ? i : point[0]); dfs2(s); //for(int j = 0; j < path.size(); j++) printf("%d ", path[j]); for(int j = path.size() - 1; j >= 0; j--) { cnt++; while(j >= 0 && path[j] != 0) { ans[cnt].push_back(path[j]); j--; } } } printf("%d ", cnt); /* for(int i = 1; i <= cnt; i++) { printf("%d", ans[i].size()); for(int j = 0; j < ans[i].size(); j++) { printf(" %d",ans[i][j]); } printf(" "); }*/ } return 0; } /* 3 3 1 2 1 3 2 3 2 2 6 5 4 4 -3 -1 2 */
1006 Matrix
1008 Odd Shops