Hdu 5385 The path
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5385
题意：有一个联通的有向图，d(x)用来记录从1点到x点的最短路径长度，d(1)=0;一个图可以称之为好图是存在一个x使得d(1)<d(2)<....d(x)>d(x+1)>...d(n)， 现在你要设置每一条边的长度使得这个图是一个好图，注意，满足d(1)<d(2)<..d(n)的也是一个好图。边的长度在1~n的范围内。一定存在解决方案。
思路：按照题解说的模拟构造就行了，如下： 我们可以采取贪心做法，一开始将1号点作为最短路径树的根，然后左边从2开始，右边从n开始，只要之前加入的点有边连向他们就加入，这样一个点加入的时间就是他的dis值，最短路径树上的父亲也可以确定，于是输出时非树边长度为n，树边长度为两个端点dis之差
参考代码：
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
#define M 300010
int dis[M], f[M], head[M];
int cnt;
struct node
{
int from, to, next;
} edge[M * + ];
void addedge(int a, int b)
{
edge[cnt].from = a;
edge[cnt].to = b;
edge[cnt].next = head[a];
head[a] = cnt++;
}
void add(int x)
{
for (int i = head[x]; i!=-; i = edge[i].next)
{
int v = edge[i].to;
if (!f[v])
f[v] = x;
}
}
int main()
{
int T, n, m, a, b;
scanf("%d", &T);
while (T--)
{
memset(f, , sizeof(f));
memset(head, -, sizeof(head));
f[] = -;
dis[] = ;
cnt = ;
scanf("%d%d", &n, &m);
for (int i = ; i < m; i++)
{
scanf("%d%d",&a, &b);
addedge(a, b);
}
int num = , l = , r = n;
while (l <= r)
{
if (f[l])
{
add(l);
dis[l++] = num++;
}
if (f[r])
{
add(r);
dis[r--] = num++;
}
}
for (int i = ; i < cnt; i++)
{
a = edge[i].from;
b = edge[i].to;
if (f[b] != a)//不在最短路树上的边
printf("%d\n", n);
else
printf("%d\n", dis[b] - dis[a]);//最短路树上的边
}
}
return ;
}
Hdu 5386 Cover
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5386
题意：有一个n*n的矩阵，矩阵的每一个方格都有颜色，有以下两种操作：
L x y: for(int i=1;i<=n;i++)color[i][x]=y;
H x y:for(int i=1;i<=n;i++)color[x][i]=y;
现在给你矩阵的初始状态和最终状态，m种操作，写出这些操作的顺序使的经过这些操作后，矩阵从初始状态变成最终状态；
思路：逆向思维。
最后一个操作肯定是把某一行或者某一列变成x,我们倒过来模拟，每次把最后一个操作找出来，即每次找到某一行或者某一列不为0的数都相同的，再找符合操作的。
参考代码：
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
#define M 505
#define N 105
#define MOD 258280327
int n, m, h, l;
#define inf 0x3f3f3f3f
bool vish[M], visl[M];
int G[N][N];
struct node
{
int color, id, x;
} oph[M], opl[M];
int path[M];
int judge(int x, int color, int dix)
{
if (dix == )
{
for (int i = ; i <= n; i++)
{
if (G[x][i] == inf)
continue;
if (G[x][i] != color)
return false;
}
}
else
{
for (int i = ; i <= n; i++)
{
if (G[i][x] == inf)
continue;
if (G[i][x] != color)
return false;
}
}
}
void setcolor(int x, int dix)
{
if (dix == )
{
for (int i = ; i <= n; i++)
G[x][i] = inf;
}
else
{
for (int i = ; i <= n; i++)
G[i][x] = inf;
}
}
void solve()
{
int cnt = ;
while (cnt < m)
{
for (int i = ; i < h; i++)//试每一种没有使用过的纵向操作
{
if (vish[i])
continue;
if (judge(oph[i].x, oph[i].color, ))
{
setcolor(oph[i].x, );
vish[i] = true;
path[cnt++] = oph[i].id;//把操作序号记录下来
}
}
for (int i = ; i < l; i++)
{
if (visl[i])
continue;
if (judge(opl[i].x, opl[i].color, ))
{
setcolor(opl[i].x, );
visl[i] = true;
path[cnt++] = opl[i].id;
}
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
int temp;
//初始状态是不用记录的
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
scanf("%d", &temp);
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
scanf("%d", &G[i][j]);
}
memset(vish, , sizeof(vish));//记录纵向操作是否操作过
memset(visl, , sizeof(visl));//记录横向操作是否操作过
char op[];
int x, color;
h = ;
l = ;
for (int i = ; i <= m; i++)
{
scanf("%s%d%d", op, &x, &color);
if (op[] == 'H')
{
oph[h].x = x;
oph[h].color = color;
oph[h++].id = i;
}
else
{
opl[l].x = x;
opl[l].color = color;
opl[l++].id = i;
}
}
solve();
//打印路径
for (int i = m - ; i >= ; i--)
{
if (i == m - )
printf("%d", path[i]);
else
printf(" %d", path[i]);
}
printf("\n");
}
return ;
}
Hdu 5387 Clock
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5387
题意：给你一个时间，输出时分秒三个指针之间的角度（0~180），注意：实数用最简分数表示，整数直接输出。
思路：简单题。
参考代码：
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
#define ang 3600
typedef long long ll;
int gcd(int a,int b){
return b==?a:gcd(b,a%b);
}
void calangle(int a,int b)
{
int sum;
if(abs(a-b)>**ang)
sum=**ang-abs(a-b);
else
sum=abs(a-b);
if(sum%ang)
{
int d=gcd(sum,ang);
printf("%d/%d ",sum/d,ang/d);
}
else
printf("%d ",sum/ang);
}
int main()
{
int i,j,k,h,m,s,t;
char c;
scanf("%d",&t);
while(t--)
{
scanf("%d%c%d%c%d",&h,&c,&m,&c,&s);
if(h>=)
h=h-;
int ss=ang*s*;
int mm=(*s+ang*m)*;
int hh=((s+*m)*+h*ang*)*;
calangle(hh,mm);
calangle(hh,ss);
calangle(mm,ss);
printf("\n");
}
return ;
}
Hdu 5387 Zero Escape
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5389
题意：给你n个人每个人手里有一个id，然后给你两个数a和b，让你把n个人分为两组，条件是 一组人手里的id和等于a 另一组人的id和等于b，这里的和是指加起来之后对9取余，如果sum等于0 则sum等于9 否则sum = sum；还有一种情况也可以 就是所有人的id和等于a 或者等于b 相当于分为一组。
思路：
dp[i][j]=dp[i-1][j]+dp[i-1][tmp](tmp为j-arr[i],若小于等于0，需加9调整)
dp[i][j]含义为取前i个数字中的若干个，按给定规则，算出来的和为j的方案数
之前有两个细节没考虑到，
一是、当前位和我dp[i][j]中的j值相同，那么对应三种情况。
1.当前位不取，直接取前面dp[i-1][j]的值
2.当前位取，前面取的是dp[i-1][9]的值（因为加9，不变）
3.当前位取，前面都不取，此种情况特殊，直接加一即可。
其实2、3两种情况是一个数分别对应dp[i-1][0]和dp[i-1][9]的特殊情况。
二是、当a+b的和和sum相同时，最后输出结果的时候，按理说只要输出dp[n][a]就可以了，但是这样会遗漏a中都不取，全都放在b中，而b又刚好和sum相同的情况。
参考代码：
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
#define M 100005
#define MOD 258280327
int num[M];
int dp[M][];
int cal(int n)
{
int k=;
while(n)
{
k+=(n%);
n/=;
}
if(k>)
return cal(k);
else
return k;
}
int main()
{
int T,a,b,n,temp,sum;
scanf("%d",&T);
while(T--)
{
memset(dp,,sizeof(dp));
sum=;
scanf("%d%d%d",&n,&a,&b);
for(int i=;i<=n;i++)
{
scanf("%d",&num[i]);
num[i]=cal(num[i]);
sum+=num[i];
}
sum=cal(sum);
int s=a+b;
s=cal(s);
if(sum==s)
{
dp[][num[]]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=;j++)
{
temp=j-num[i];
if(temp<=)
temp+=;
dp[i][j]=(dp[i-][temp]+dp[i-][j])%MOD;
}
}
printf("%d\n",(dp[n][a]+dp[n][b])%MOD);
}
else
{
int ans=;
if(sum==a)
ans++;
if(sum==b)
ans++;
printf("%d\n",ans);
}
}
return ;
}