http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29405#problem/A
这场比赛可能题目有点难,只出了一个水题,郁闷啊! 另外还可以做的题有这么几个!
H题,告诉你多组比赛,还有胜败情况,看有多少人能够确定最终名次! 当时想到拓扑排序,但是无论正着拍,逆向拍都不对,我后来又改成迭代,但是仍然不对,郁闷啊!
自己想了测试数据,想了好几个都没测出问题了,后来还是老卜告诉我一组数据,但是没有对题目理解透彻,即便知道了测试数据仍然没有做对! 后来想想也是,怎么才能把一个人的最终名次确定了呢, 那就是在总人数为n的前提下,赢他的有m人,输他的有k人,m+k=n-1那么他的名词就一定能确定了呢! 当然,很多关系是能传递的,1》2,2》3 那么1》3 赢不一定是直接赢,简介赢也行,那么就需要用floyd处理一下…… 然后记录入度和出度就好,每找出一个人就把这个人从总人数中去掉,然后把他在人数中的关系也都去掉,这样再次迭代下去,直到没有不能更新答案为止……
G 这是到DP,很明显的DP,而且是纯粹的DP,枉我搞DP快一暑假了,仍然一点头绪没有,后来才知道自己陷入误区了
先介绍下题意吧,n个时间1W,然后给每个时间能跑的距离,没跑动一次疲劳就上升一个值,最多到M,如果休息的话,每停一次疲劳下降1,但是疲劳下降的时候不能终止,必须降到0才能开始下一次运动…… 疲劳从0开始,但是最后在n时刻,疲劳必须要降到0,否则很难做下一次训练,休息不好时不行的!
当时各种想法都出来了,就是没有一个靠谱的,要不就是不知道该记录那个状态,要不就是没法记录状态,再就是没法转移,对状态把握不清楚,当时想用dp[i][0/1]的形式,就是每个点选还是不选的形式,但是后来怎么弄都不对,因为还有个疲劳值不超过m限制在这里…… 而且dp里面记录跑的最远的距离或者最小疲劳值都不对啊…… 知道看到别人的讲解才恍然大悟。我可以这样开dp[n][m] 的形式啊,最终需要的结果就是时间为n,疲劳为0的状态
当然这里转移的时候需要注意,dp[i][0]可能有上一个的1疲劳转移过来,也可能由前两个的2疲劳转移过来,或者前k个k疲劳转移过来…… 这样就很清楚了,因为他要连续休息知道j个疲劳回复到0啊!
F题是个图论题,就是给一些边,然后建图,类似于求最短路一样,把节点1和节点n连接起来,然是有k条边是不用自己花钱的,剩下的边由jhon自己掏钱,花费是,最长的一条的长度! 当时没读明白题,到现在其实也不是很明白,我以为k是长度,而不是边的数目!
这样题意明确之后就应该知道,尽量在求解修路的时候使得长的边算到k里面,剩下的自己搞;可是把那些边算到k里面不花钱,那些需要算到Jhon的头上,确实不好搞啊,怎么办呢? 难道枚举,爆搜,贪心,orDP ,而且不知道怎么判断是否是用那些边不用那些边; 后来看了别人的讲解有点明白了,二分啊,二分长度,看至少有k条边大于L,然后用这些边修路看能否修好,怎么算是修好了,而且恰好用了那几条选中的边呢? 修改权值,超过L的设成1,其他的弄成0; 若如果修好的最短路答案恰恰是k,那么正好全用了…… 这样来验证…… 通过修改权值的办法;这样在最短路里面把无关的边设成0消除其影响!
当然,貌似也有用DP+搜所做出来的,貌似思路是枚举这条边看能否归0,就是让通讯公司掏钱而不是让可怜Jhon掏钱,然后DP记录最优值,减少枚举搜索次数http://hi.baidu.com/lxxstar1226/item/d036b2e45b534a334cdcaf65
B题是大水题。披着计算几何的外衣,而且里面的词汇全是计算几何里面碰到的词汇。要不是哥刚做过几个计算几何,连题目大意都读不懂啊,给你一个矩形,然后看最小的等腰三角形把矩形套起来,使矩形上的点要么在内部要么在边上上,而且等腰三角形的两边已经确定了,和XX重合,花花图,三角形相似,直接利用题目中所给的值就好,都不用计算的,只不过坐标得处理下,分类讨论加上正负号就好了……
G题:
#include <iostream>
#include<cstdio>
using namespace std;
#define N 100000
#define M 500
int dp[N+10][M+10];
int cnt[N+10][2];
int d[N+10];
int sum[N+10];
int n,m;
int main()
{
///该死的DP,做了这么久的DP还是别难住了,悲剧啊,都不好意思说自己是搞DP的,
///做DP貌似有点盲目了,丢掉了思考,最近做多了dp[i][0/1] 这一位放还是不放的形式忽略了一般的二维数组形式的DP
///忘记了最终状态是需要时间是n,但是疲劳值是0的最终状态,因为每个状态需要积累疲劳值啊,当时光盲目的开两个数组
///却忽略最基本的二维数组的形式啊,哎,忽略了二维数组的形式导致好多状态没法记录啊
cin>>n>>m;
for(int i=1; i<=n; ++i)
{
scanf("%d",&d[i]);
sum[i]=sum[i-1]+d[i];
}
dp[1][0]=0;
dp[1][1]=d[1];
for(int i=1;i<=m;++i)
{
dp[1][i]=d[1];
}
for(int i=2;i<=n;++i)
{
dp[i][0]=max(dp[i-1][0],dp[i][0]);
for(int j=1;j<=m;++j)
{
dp[i][j]=max(dp[i-1][j-1]+d[i],dp[i][j]);
///下面这句有点难理解,为什么呢,就是说如果i时消耗为0的话,那么消耗为为j的就得从i-j开始转移,
///因为这段必须是是连续的休息时间
if(i>j)dp[i][0]=max(dp[i-j][j],dp[i][0]);
}
}
cout<<dp[n][0]<<endl;
return 0;
}
#include <iostream>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
int n,m;
int cnt2[110];///表示出度
int cnt1[110];///表示入度
int vis[110];
int map[110][110];
int u,v,ans;
int a1=0,a2=0;
void floyd()
{///floyd一边是关系传递……
for(int k=1; k<=n; ++k)
{
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=n; ++j)
{
if(map[i][k]&&map[k][j])map[i][j]=1;
}
}
}
}
void slove()
{
int t=n;
int tmp=-1;
while(tmp!=t)
{///迭代的过程,直到不能找到为止
tmp=t;
for(int i=1;i<=n;++i)
{
if(!vis[i]&&cnt1[i]+cnt2[i]==t-1)
{///如何赢的人输的人还有他自己是总人数的话,那么一定能确定他的名词了
ans++;vis[i]=1;
t--;
for(int j=1;j<=n;++j)
{
if(map[j][i])cnt2[j]--;
if(map[i][j])cnt1[j]--;
}
}
}
}
}
void init()
{
memset(map,0,sizeof(map));
memset(cnt1,0,sizeof(cnt1));
memset(cnt2,0,sizeof(cnt2));
memset(vis,0,sizeof(vis));
ans=0;
}
int main()
{///如何根据一个人的比赛情况确定排名呢,那就是根据他赢的人数还有输的人数!!! 就是入度和出度
///当年usaco月赛上曾经有一个题是将带编号打乱编号在重新排列,告诉你每个牛左边有多少个比他编号小的,然后输出
///每个牛的编号,怎么办呢? 倒着推啊,比如说全班有多少个人比他成绩高,那么他是倒数第几不就很好确定了吗
///可惜当时没想明白,而且怎么找数据就是没有找出来,后来老卜给了我一组 1,2都打败3,3打败4,5
///那么3号的名词一定是确定了, 我原来是正向一边拓扑排序,逆向一边拓扑排序;光想着从两头找了,没有想到中间也是有可能的
cin>>n>>m;
for(int i=0; i<m; ++i)
{
cin>>u>>v;
map[u][v]=1;
}
floyd();///传递
///统计入度出度
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=n; ++j)
if(map[i][j]&&i!=j)cnt1[j]++,cnt2[i]++;;
}
slove();
cout << ans << endl;
return 0;
}