【题目链接】点击打开链接
【HDU 5090 A】 水题，可以贪心调整好符合条件的，然后排序之后判断。其实仔细思考发现，这就是一个裸二分匹配！可以看下图： 对应第二个样例。。
【代码1 贪心】
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int a[110];
bool vis[110];
int m, n, k;
int main()
{
scanf("%d",&m);
while(m--){
scanf("%d%d",&n,&k);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++){
while(1){
if(a[i] > n) break;
if(!vis[a[i]]){
vis[a[i]] = 1;
break;
}
a[i] += k;
}
}
//xx
sort(a+1, a+n+1);
bool ok = 1;
for(int i = 1; i <= n; i++){
if(a[i] != i){
ok = 0;
break;
}
}
if(ok){
puts("Jerry");
}
else{
puts("Tom");
}
}
return 0;
}【代码2 最大匹配】
bool con[110][110], vis[110];
int match[maxn], n, k, x;
bool dfs(int x)
{
for(int i = 1; i <= n; i++){
if(!vis[i] && con[x][i]){
vis[i] = 1;
if(match[i] == -1 || dfs(match[i]))
{
match[i] = x;
return true;
}
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
memset(con, 0, sizeof(con));
memset(match, -1, sizeof(match));
for(int i = 1; i <= n; i++){
scanf("%d", &x);
while(x <= n)
{
con[x][i] = 1;
x += k;
}
}
int ans = 0;
for(int i = 1; i <= n; i++){
memset(vis, 0, sizeof(vis));
if(dfs(i)) ans++;
}
if(ans == n){
printf("Jerry\n");
}
else{
printf("Tom\n");
}
}
return 0;
}
【B HDU 5091 】和今年在大连热身赛的题目一样，都可以转化成线段树扫描线来解！可以参考：点击打开链接
【代码】
int n, w, h;
struct node{
int l, r;
int num, lazy;
node(){}
node(int num, int lazy) : num(num), lazy(lazy){}
}Tree[20*maxn];
struct seg{
int x, y, v;
seg(){}
seg(int x, int y, int v) : x(x), y(y), v(v){}
bool operator<(const seg &rhs){
if(x == rhs.x) return v > rhs.v;
return x < rhs.x;
}
}seg[maxn*4];
void pushup(int rt)
{
Tree[rt].num = max(Tree[rt*2].num, Tree[rt*2+1].num);
}
void pushdown(int rt)
{
if(Tree[rt].lazy != 0){
Tree[rt*2].lazy += Tree[rt].lazy;
Tree[rt*2+1].lazy += Tree[rt].lazy;
Tree[rt*2].num += Tree[rt].lazy;
Tree[rt*2+1].num += Tree[rt].lazy;
Tree[rt].lazy = 0;
}
}
void Build(int l, int r, int rt)
{
Tree[rt].l = l, Tree[rt].r = r, Tree[rt].lazy = Tree[rt].num = 0;
if(l == r){
return ;
}
int mid = (l + r) / 2;
Build(l, mid, rt*2);
Build(mid+1, r, rt*2+1);
}
void update(int i, int rt)
{
if(Tree[rt].l >= seg[i].y && Tree[rt].r <= seg[i].y + h){
Tree[rt].num += seg[i].v;
Tree[rt].lazy += seg[i].v;
return ;
}
pushdown(rt);
int mid = (Tree[rt].l + Tree[rt].r) / 2;
if(seg[i].y <= mid) update(i, rt*2);
if(mid < seg[i].y + h) update(i, rt*2+1);
pushup(rt);
}
//void update(int i, int l, int r, int rt)
//{
// if(l >= seg[i].y && r <= seg[i].y + h){
// Tree[rt].num += seg[i].v;
// Tree[rt].lazy += seg[i].v;
// return ;
// }
// pushdown(rt);
// int mid = (Tree[rt].l + Tree[rt].r) / 2;
// if(seg[i].y <= mid) update(i, l, mid, rt*2);
// if(mid < seg[i].y + h) update(i, mid+1, r, rt*2+1);
// pushup(rt);
//}
int main()
{
while(scanf("%d",&n) != EOF && n > 0)
{
scanf("%d%d", &w, &h);
for(int i = 1; i <= n; i++){
int x, y;
scanf("%d%d", &x, &y);
seg[2*i - 1].x = x;
seg[2*i - 1].y = y + 2*maxn;
seg[2*i - 1].v = 1;
seg[2*i].x = x + w;
seg[2*i].y = y + 2*maxn;
seg[2*i].v = -1;
}
sort(seg+1, seg+2*n+1);
Build(1, 4*maxn, 1);
int ans = 0;
for(int i = 1; i <= 2*n; i++){
update(i, 1);
ans = max(ans, Tree[1].num);
}
printf("%d\n",ans);
}
return 0;
}
【C HDU 5092】题意是：给一个N*M的矩阵，让你用一条线 从第1行连到第N行（每行只能选一个元素），要求这条线所经过的元素之和最小。
有以下规定——
1，若你选择了位置（i，j）的元素，那么下一行的元素你只能选择（i+1，j-1）、（i+1，j）、（i+1，j+1）三个之一（当然边界只能选两个）。
2，若可以找到多条 路径上元素之和最小 的线，那么你要优先选择最右边的线。
3，最后从第一行开始 输出线上元素的纵坐标。
【解题方法】 简单DP+路径输出。。其实就是数塔问题的一个变形嘛，dp[i][j]表示经过i,j点可以得到的最小值！转移过程就是:
if(j != m && dp[i][j] > dp[i-1][j+1] + a[i][j]){
dp[i][j] = dp[i-1][j+1] + a[i][j];
path[i][j] = j+1;
}
if(dp[i][j] > dp[i-1][j] + a[i][j]){
dp[i][j] = dp[i-1][j] + a[i][j];
path[i][j] = j;
}
if(j != 1 && dp[i][j] > dp[i-1][j-1] + a[i][j]){
dp[i][j] = dp[i-1][j-1] + a[i][j];
path[i][j] = j-1;
}
【AC代码】
int dp[maxn][maxn], path[maxn][maxn], a[maxn][maxn], n, m;
void solve(int x, int y)
{
if(x == 1){
printf("%d ",y);
return ;
}
solve(x-1, path[x][y]);
if(x == n) printf("%d",y);
else printf("%d ",y);
}
int main()
{
int T, ks = 1;
scanf("%d",&T);
while(T--){
//memset(path, -1, sizeof(path));
for(int i = 0; i < maxn; i++){
for(int j = 0; j < maxn; j++){
dp[i][j] = inf;
}
}
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d",&a[i][j]);
}
}
for(int i = 1; i <= m; i++){
dp[1][i] = a[1][i];
path[1][i] = i;
}
for(int i = 2; i <= n; i++){
for(int j = 1; j <= m; j++){
if(j != m && dp[i][j] > dp[i-1][j+1] + a[i][j]){
dp[i][j] = dp[i-1][j+1] + a[i][j];
path[i][j] = j+1;
}
if(dp[i][j] > dp[i-1][j] + a[i][j]){
dp[i][j] = dp[i-1][j] + a[i][j];
path[i][j] = j;
}
if(j != 1 && dp[i][j] > dp[i-1][j-1] + a[i][j]){
dp[i][j] = dp[i-1][j-1] + a[i][j];
path[i][j] = j-1;
}
}
}
int ans = inf, pos;
for(int i = m; i >= 1; i--){
if(ans > dp[n][i]){
ans = dp[n][i];
pos = i;
}
}
printf("Case %d\n",ks++);
solve(n, pos);
printf("\n");
}
return 0;
}
【D HDU 5093】题意：给你一个n*m的图，图中有冰山 ‘# ’,浮冰 ‘o’ 以及普通海 ‘ * ’,现在要在海中布置尽可能多的炮弹，炮弹不能突波冰山，不能让炮弹互相攻击到，问最大能不知多少个？【解题方法】二分图的经典题目，关键在于怎么建图，图进行两次编号，按行编号，每一行中能攻击到的一块编号成相同的数，每一列同样，然后对行和列有编号的地方进行连边，求一次最大匹配即可，我用最大流求的最大匹配。
【AC代码】
int mp[2510][2510];
char s[52][52];
bool vis[2510];
int match[2510];
int x[52][52], y[52][52], n, m, cnt1, cnt2;
bool dfs(int x)
{
for(int i = 1; i < cnt2; i++){
if(mp[x][i] && !vis[i]){
vis[i] = 1;
if(match[i] == -1 || dfs(match[i])){
match[i] = x;
return true;
}
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
memset(mp, 0, sizeof(mp));
scanf("%d%d",&n,&m);
for(int i = 0; i < n; i++) scanf("%s",s[i]);
cnt1 = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(s[i][j] == '*') x[i][j] = cnt1;
if(s[i][j] == '#') cnt1++;
}
cnt1++;
}
cnt2 = 1;
for(int j = 0; j < m; j++){
for(int i = 0; i < n; i++){
if(s[i][j] == '*') y[i][j] = cnt2;
if(s[i][j] == '#') cnt2++;
}
cnt2++;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(s[i][j] == '*'){
mp[x[i][j]][y[i][j]] = 1;
}
}
}
memset(match, -1, sizeof(match));
int ans = 0;
for(int i = 1; i < cnt1; i++){
memset(vis, 0, sizeof(vis));
if(dfs(i)) ans++;
}
printf("%d\n",ans);
}
return 0;
}
【E HDU 5094】【题意】有一个N*M的地图，图里面有p种门。
下一行输入一个k，代表有k个门 (或墙)。下面k行给出它们所在的位置，样例（x1，x2，y1，y2，op）意义：前四个数值分别代表两个位置的坐标，当op为0时说明两位置之间是一堵墙，当op大于0时说明两位置之间是一扇门且op代表门的型号。
然后输入一个S，代表钥匙的数目，接下来S行每行三个数（x，y，op）代表位置（x，y）有 一把型号op的门 的钥匙。
问你能够从（1，1）出发到达（N，M），若可以输出最小步数，否则输出-1。当然每个点是可以无限走的。
【解体方法】简单BFS + 状态压缩。注意状态压缩处理二进制时，对门和钥匙的编号要减一处理。=注意此题有坑处：
1：每个点可能有 很多把 相同型号或者不同型号的钥匙。我是开了二维数组记录没个点的钥匙状态！
2：起点可能有钥匙，注意初始状态的处理。
【AC 代码】
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
int n, m, p;
int g[maxn][maxn][maxn][maxn], key[maxn][maxn];
bool vis[maxn][maxn][maxm];
struct node{
int x, y, state, step;
node(){}
node(int x, int y, int state, int step):x(x), y(y), state(state), step(step){}
};
bool check(int x, int y)
{
if(x >= 1 && x <= n && y >= 1 && y <= m) return true;
else return false;
}
int bfs();
int main()
{
while(scanf("%d%d%d",&n,&m,&p)!=EOF)
{
memset(key, 0, sizeof(key));
memset(g, -1, sizeof(g));
memset(vis, false, sizeof(vis));
int k;
scanf("%d",&k);
while(k--)
{
int x1, y1, x2, y2, st;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&st);
g[x1][y1][x2][y2] = g[x2][y2][x1][y1] = st;
}
int s;
scanf("%d",&s);
while(s--)
{
int x, y, q;
scanf("%d%d%d",&x,&y,&q);
q--;
key[x][y] |= (1<<q);
}
int ans = bfs();
printf("%d\n", ans);
}
return 0;
}
int bfs()
{
queue<node>q;
node now, nex;
now = node(1, 1, key[1][1], 0);
vis[1][1][key[1][1]] = 1;
q.push(now);
while(!q.empty())
{
now = q.front();
q.pop();
int x = now.x, y = now.y, sta = now.state, s = now.step;
if(x == n && y == m) return s;
for(int i = 0; i < 4; i++){
int dx = x + dir[i][0];
int dy = y + dir[i][1];
int sta2 = sta | key[dx][dy];
int t = g[x][y][dx][dy];
if(check(dx, dy) && ((t == -1) || ((1<<(t-1))&sta2 && t > 0)) && !vis[dx][dy][sta2]){
vis[dx][dy][sta2] = 1;
q.push(node(dx, dy, sta2, s+1));
}
}
}
return -1;
}【F HDU 5095】模拟不说，就是题意很恶心，细心读。
【AC代码】
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[11];
char s[11] = {' ','p','q','r','u','v','w','x','y','z'};
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int pos;
memset(a, 0, sizeof(a));
for(int i = 1; i <= 10; i++){
scanf("%d",&a[i]);
}
for(int i = 1; i <= 10; i++){
if(a[i] != 0){
pos = i;
break;
}
}
if(a[pos] == 0){
printf("\n");
continue;
}
if(pos != 10){
if(a[pos] == -1){
printf("-%c",s[pos]);
}
else {
if(a[pos] == 1){
printf("%c",s[pos]);
}else printf("%d%c",a[pos],s[pos]);
}
}
else{
printf("%d", a[pos]);
}
for(int i = pos+1; i <= 10; i++){
if(i < 10){
if(a[i] == 0) continue;
if(a[i] > 0){
if(a[i] == 1){
printf("+%c",s[i]);
}else
printf("+%d%c",a[i],s[i]);
}
else{
if(a[i] == -1){
printf("-%c",s[i]);
}
else
printf("%d%c",a[i],s[i]);
}
}
else if( i == 10){
if(a[i] == 0) break;
else if(a[i] > 0) printf("+%d",a[i]);
else printf("%d",a[i]);
}
}
printf("\n");
}
return 0;
}
【G和H不会】
【I HDU 5098】题意：软件在安装之后需要重启才能发挥作用，现在给你一堆软件(有的需要重启有的不需要)以及安装这个软件之前需要哪些软件发挥作用，求最少的重启次数？【解法】来自斌神的解法：可以看出是拓扑排序，但是需要用两个队列q1，q2分别来存 不需要重启的software 和 需要重启的software。根据题目输入建好图后，按照拓扑序规则，首先将入度的0的点加进队列，不需要重启的进q1，需要的进q2。然后处理q1中的所有节点（即要删除这些点），那么要让与他们相连的节点的入度减1，如果发现减完入度为0，再判断其是否需要重启，并加进q1 or q2。一旦发现q1为空，那么使答案加1（不能继续任何安装即重启一次），把q2中所有元素加入q1，q2清空。如此循环直到q1，q2均为空即可。还有一种解法：就是DAG的最长路。有兴趣可以搜来学习一下。
【AC代码】
//
//Created by just_sort 2016/12/4
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define MP(x,y) make_pair(x,y)
const int maxn = 1020;
const int maxm = 1<<12;
const int inf = 0x3f3f3f3f;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
map <string, int> mp;
int cnt, edgecnt, reboot[maxn], out[maxn], in[maxn];
int head[maxn], vis[maxn];
struct edge{
int v, next;
}E[maxn*maxn];
void addedge(int u, int v)
{
E[edgecnt].v = v, E[edgecnt].next = head[u], head[u] = edgecnt++;
}
void init()
{
mp.clear();
memset(reboot, 0, sizeof(reboot));
memset(out, 0, sizeof(out));
memset(in, 0, sizeof(in));
memset(head, -1, sizeof(head));
cnt = edgecnt = 0;
}
int topsort()
{
queue<int>q1, q2;
for(int i = 1; i <= cnt; i++){
if(in[i] == 0){
if(reboot[i] == 0) q1.push(i);
else q2.push(i);
}
}
int ans = 0;
while(!q1.empty() || !q2.empty()){
if(q1.empty() && !q2.empty()){
ans++;
while(!q2.empty()){
q1.push(q2.front());
q2.pop();
}
}
while(!q1.empty()){
int u = q1.front(); q1.pop();
for(int i = head[u]; ~i; i = E[i].next){
int v = E[i].v;
in[v]--;
if(in[v] == 0){
if(reboot[v] == 0){
q1.push(v);
}
else{
q2.push(v);
}
}
}
}
}
return ans;
}
int main()
{
string s;
char name[1010];
int T, ks = 1;
scanf("%d",&T);
getchar();
getchar();
while(T--){
init();
while(getline(cin, s)){
if(s[0] == '\0') break;
istringstream sin(s);
sin >> name;
int len = strlen(name);
int flag = 0;
if(name[len - 2] == '*'){
flag = 1;
name[len - 2] = '\0';
}
else{
name[len - 1] = '\0';
}
string a, b;
a = name;
if(mp.find(a) == mp.end()) mp[a] = ++cnt;
reboot[mp[a]] = flag;
while(sin >> b){
if(mp.find(b) == mp.end()) mp[b] = ++cnt;
addedge(mp[b], mp[a]);
out[mp[b]]++;
in[mp[a]]++;
}
}
int ans = topsort();
printf("Case %d: %d\n", ks++, ans);
}
return 0;
}
【代码】
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
char a[10], b[10];
char c[10], d[10];
int main()
{
int T, ks = 1;
scanf("%d",&T);
while(T--){
memset(c, '\0', sizeof(c));
memset(d, '\0', sizeof(d));
scanf("%s %s", a, b);
printf("Case %d: ",ks++);
if(a[0] < b[0]) printf("< ");
else if(a[0] == b[0]) printf("= ");
else printf("> ");
if(a[1] == b[1]){
strncpy(c, a+2, 4);
strncpy(d, b+2, 4);
if(strcmp(c, d) > 0) printf(">");
else if(strcmp(c, d) == 0) printf("=");
else printf("<");
}
else{
strncpy(c, a+2, 3);
strncpy(d, b+2, 3);
if(strcmp(c, d) > 0) printf(">");
else if(strcmp(c, d) == 0) printf("=");
else printf("<");
}
printf("\n");
}
return 0;
}
京公网安备 11010502036488号