啥都不会做了。。
做题慢死
A.Grandpa's Walk
签到题。
直接DFS就行。
注意先判断这个点可以作为一个路径的起点不。
然后再DFS。
否则处理起来略麻烦
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#define MAXN 111111
#define INF 1000000007
using namespace std;
int h[55][55];
int dp[55][55];
int n, m;
int xx[] = {0, 0, -1, 1};
int yy[] = {1, -1, 0, 0};
int vis[55][55];
void dfs(int x, int y)
{dp[x][y] = 0;vis[x][y] = 1;int flag = 0;for(int i = 0; i < 4; i++){int tx = x + xx[i];int ty = y + yy[i];if(tx >= 0 && ty >= 0 && tx < n && ty < m ){if(h[x][y] <= h[tx][ty] ) continue;flag = 1;if(!vis[tx][ty])dfs(tx, ty);dp[x][y] += dp[tx][ty];}}if(flag == 0) dp[x][y] = 1;
}
int main()
{int T;int cas = 0;scanf("%d", &T);while(T--){memset(dp, -1, sizeof(dp));scanf("%d%d", &n, &m);memset(vis, 0, sizeof(vis));for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)scanf("%d", &h[i][j]);int ans = 0;//ans += dfs(1, 1);for(int i = 0; i < n; i++)for(int j = 0; j < m; j++){int flag = 0;for(int k = 0; k < 4; k++){int tx = i + xx[k];int ty = j + yy[k];if(tx >= 0 && ty >= 0 && tx < n && ty < m)if(h[tx][ty] > h[i][j])flag = 1;}if(flag) continue;dfs(i, j);ans += dp[i][j];}printf("Case #%d: %d\n", ++cas, ans);}return 0;
}
很容易想到一种贪心的思想
就是一个结点。
从父节点流过来的边。
能跟去往子结点的边流多少 就流多少
然后子结点如果还有留下的流量
就两两配对搞一下
但是可能会出现某个分支流量很大。
别的所有分支跟这个分支配对完，这个分支还有剩余
那么就要特殊判断一下。
所以就要求一下所有分支的流量总和，以及最大值。
然后看sum - max 与max的关系。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#define MAXN 111111
#define INF 1000000007
using namespace std;
vector<pair<int, int> >g[MAXN];
int n, ans;
void dfs(int u, int fa, int pre)
{int sz = g[u].size();int mx = 0;int sum = 0;for(int i = 0; i < sz; i++){int v = g[u][i].first;int w = g[u][i].second;if(v == fa) continue;dfs(v, u, w);sum += w;mx = max(mx, w);}int t = mx + mx - sum;if(t > pre) ans += mx - pre;else if(sum >= pre) ans += (sum - pre + 1) / 2;
}
int main()
{int T, u, v, w;int cas = 0;scanf("%d", &T);while(T--){scanf("%d", &n);ans = 0;for(int i = 1; i <= n; i++) g[i].clear();for(int i = 1; i < n; i++){scanf("%d%d%d", &u, &v, &w);g[u].push_back(make_pair(v, w));g[v].push_back(make_pair(u, w));}dfs(1, 0, 0);printf("Case #%d: %d\n", ++cas, ans);}return 0;
}C.Stop Growing!
签到题。
发现和是翻倍增长即可
D.Retrenchment
没看
E.Bee Tower
简单的一个二维DP
dp[i][j] 表示的是从第i个塔在第j个位置时登上塔所需要得最小花费
注意的是最高的塔不能动！！
所以找答案的时候要找对状态
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#define MAXN 555
#define INF 1000000007
using namespace std;
int dp[MAXN][MAXN];
typedef pair<int, int> P;
P tow[MAXN];
int n, H, W, mx, ans;
void gao()
{tow[0].second = 0;memset(dp, 0x3f, sizeof(dp));for(int i = 1; i <= n; i++){int tmp = tow[i].second - tow[i - 1].second;if(tow[i].second <= H)for(int j = 1; j <= 500; j++)dp[i][j] = min(dp[i][j], abs(tow[i].first - j) * tow[i].second);if(tmp > H) continue;for(int j = 1; j <= 500; j++)for(int k = 1; k <= W; k++){if(j - k < 1) break;dp[i][j] = min(dp[i][j], abs(tow[i].first - j) * tow[i].second + dp[i - 1][j - k]);}}
}
void getans()
{for(int i = 1; i <= n; i++)if(tow[i].second == mx)ans = min(ans, dp[i][tow[i].first]);
}
int main()
{int T, cas = 0;scanf("%d", &T);while(T--){scanf("%d%d%d", &n, &H, &W);mx = 0, ans = INF;for(int i = 1; i <= n; i++){scanf("%d%d", &tow[i].first, &tow[i].second);mx = max(tow[i].second, mx);}sort(tow + 1, tow + 1 + n);gao();getans();for(int i = 1; i <= n; i++) tow[i].first = 501 - tow[i].first;sort(tow + 1, tow + 1 + n);gao();getans();if(ans == INF) ans = -1;printf("Case #%d: %d\n", ++cas, ans);}return 0;
}F.Knots
呃。。神题吧。
G.Unique Path
就是求边的双连通分量。
然后把涉及到的边的两个端点都给标记掉。
其实就是跟求桥相反。 不是桥的边得端点肯定不行。
剩余的点组成了若干个连通块
每个连通块内，点与点之间都符合要求
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#define MAXN 111111
#define INF 1000000007
using namespace std;
int n, m;
struct Edge
{int u, v, next;
}edge[MAXN * 2];
int tmpdfn, e, top, num[MAXN];
int head[MAXN], vis[MAXN * 2];int dfn[MAXN], low[MAXN], fa[MAXN];
int cnt;void init()
{e = 0, tmpdfn = 0, top = -1;cnt = 0;memset(head, -1, sizeof(head));memset(vis, 0, sizeof(vis));memset(dfn, 0, sizeof(dfn));memset(num, 0, sizeof(num));
}
void insert(int x, int y)
{edge[e].u = x;edge[e].v = y;edge[e].next = head[x];head[x] = e++;
}
int find(int x)
{if(x == fa[x]) return x;int t = find(fa[x]);fa[x] = t;return t;
}
void dfs(int u, int fath)
{dfn[u] = low[u] = ++tmpdfn;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;if(!dfn[v]){dfs(v, u);low[u] = min(low[u], low[v]);if(low[v] <= dfn[u])vis[u] = vis[v] = 1;}else if(v != fath) low[u] = min(low[u], dfn[v]);}
}int main()
{int T, u, v;int cas = 0;scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);init();for(int i = 0; i < m; i++){scanf("%d%d", &u, &v);insert(u, v);insert(v, u);}for(int i = 1; i <= n; i++) fa[i] = i, num[i] = 1;for(int i = 1; i <= n; i++)if(!dfn[i]) dfs(i, 0);for(int i = 1; i <= n; i++)for(int j = head[i]; j != -1; j = edge[j].next){int v = edge[j].v;if(!vis[i] && !vis[v]){int fx = find(i);int fy = find(v);if(fx != fy){fa[fy] = fx;num[fx] += num[fy];num[fy] = 0;}}}printf("Case #%d: ", ++cas);memset(vis, 0, sizeof(vis));long long ans = 0;for(int i = 1; i <= n; i++){int t = find(i);if(!vis[t]){vis[t] = 1;ans += (long long)(num[t]) * (long long)(num[t] - 1) / 2;}}printf("%lld\n", ans);}return 0;
}H.Alien Abduction
这题的话。
注意到
操作到的人次不会超过5W
也就是要快速找到这些符合要求的人
那么。
还是那个技巧。
所有点左旋45度
然后坐标转换。
用set给存下来
就能很快的找到这些点了
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
#define INF 100000005
#define MAXN 70000
using namespace std;
int N, Q, W, H;
int X, Y, E, a, b, c, d, e, f, x, y;
typedef pair<int, int> P;
P ans[MAXN];
typedef pair<int, P> PP;
set<P>s[MAXN];
set<int>xx;
vector<PP>g;
typedef set<int>::iterator Iter;
typedef set<P>::iterator Pter;
typedef long long LL;
int getx(int tx, int ty)
{return (tx - H + ty) / 2;
}
int gety(int tx, int ty)
{return (ty - tx + H) / 2;
}
int main()
{int T;int cas = 0;scanf("%d", &T);while(T--){scanf("%d%d%d%d", &N, &Q, &W, &H);for(int i = 0; i <= W + H; i++) s[i].clear();xx.clear();for(int i = 1; i <= N; i++){scanf("%d%d", &x, &y);s[x - y + H].insert(make_pair(x + y, i));xx.insert(x - y + H);}for(int i = 0; i < Q; i++){scanf("%d%d%d%d%d%d%d%d%d", &X, &Y, &E, &a, &b, &c, &d, &e, &f);x = X - Y + H;y = X + Y;Iter it1 = xx.lower_bound(x - E);Iter it2 = xx.upper_bound(x + E);g.clear();for(Iter it = it1; it != it2; it++){int nowx = *it;Pter pt1 = s[nowx].lower_bound(make_pair(y - E, -1));Pter pt2 = s[nowx].upper_bound(make_pair(y + E, INF));for(Pter pt = pt1; pt != pt2; pt++){P tmp = *pt;g.push_back(make_pair(nowx, tmp));}}for(int j = 0; j < g.size(); j++){int tx = g[j].first;int ty = g[j].second.first;int id = g[j].second.second;s[tx].erase(g[j].second);if(s[tx].size() == 0) xx.erase(tx);x = getx(tx, ty);y = gety(tx, ty);LL newx = ((LL)x * (LL)a % W + (LL)y * (LL)b % W + (LL)id * (LL)c % W) % W;LL newy = ((LL)x * (LL)d % H + (LL)y * (LL)e % H + (LL)id * (LL)f % H) % H;tx = (newx - newy + H);ty = newx + newy;s[tx].insert(make_pair(ty, id));xx.insert(tx);}}for(Iter it = xx.begin(); it != xx.end(); it++){int now = *it;for(Pter pt = s[now].begin(); pt != s[now].end(); pt++){P tmp = *pt;ans[tmp.second].first = getx(now, tmp.first);ans[tmp.second].second = gety(now, tmp.first);}}printf("Case #%d:\n", ++cas);for(int i = 1; i <= N; i++)printf("%d %d\n", ans[i].first, ans[i].second);}return 0;
}I.Tiling
这题的话。。
刚开始百思不得其解
然后经zhou神一说就知道了。。
这题的模型可以转化成求某一列相邻两点的距离
首先可以发现第(0,0)点显然是可以的。。
然后求一个尽量小的(X, 0)就行了。
我们先用两个两个向量去凑
对于(x1, y1)和(x2, y2)
我们可以凑成
(x1 * y2 - x2 * y1, y1 * y2 - y2 * y1)
即(x1 * y2 - x2 * y1, 0 )
然后有三个向量就有三种可能
假设这三种分别凑成了(a,0) (b,0) (c,0)
根据线性方程的话。
gcd(a, b, c) 是这三种数能凑成的最小的间隔
就是答案了。。
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
#define INF 100000005
#define MAXN 70000
using namespace std;
int f(int x1, int y1, int x2, int y2)
{return x1 * y2 - y1 * x2;
}
int main()
{int T, cas = 0;int x1, x2, y1, y2, x3, y3;scanf("%d", &T);while(T--){scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);int a = f(x1, y1, x2, y2);int b = f(x1, y1, x3, y3);int c = f(x2, y2, x3, y3);printf("Case #%d: %d\n", ++cas, __gcd(abs(a), __gcd(abs(b), abs(c))));}return 0;
}J. Perfect Matching
貌似最裸的暴力是能在oj上过的。
但是从现场的感觉来看
不应该是那么裸才是
