|
#
stanford open course： machine learning
实变函数
测度论与概率论
随机过程
算法导论
新概念英语
昨晚发过去的，今天一早就给出了反馈信息。可能是之前师兄做得差不多了，所以只有两点针对证明的意见，下面是 Wei_Fan的回信： Some clarifications need to be made to the formal analyses: 1. It is not clearly to me, in Theorem 1, what exactly is b. This needs to be defined formally and clearly. I think that this is the bayesian optimal decision. 2. I do not understand why conf(x) = max p(y|x)? In reality, isn't the confidence of a prediction the estimated probability by a model M, and there is always a dependency on M? In other words, the estimated probability by a model is p(y|x,M) and there is an explicit dependency on M, and normally P(y|x) = P(y|x,M). I think that there is one more step need to be done. That is to assume M is better than random guessing, thus, P(y|x,M) is reasonably close to P(y|x),..
摘要: Dijkstra with Heap 阅读全文
The Perfect Stall
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 2136 |
|
Accepted: 961 |
Description
Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all the stalls in the new barn are different. For the first week, Farmer John randomly assigned cows to stalls, but it quickly became clear that any given cow was only willing to produce milk in certain stalls. For the last week, Farmer John has been collecting data on which cows are willing to produce milk in which stalls. A stall may be only assigned to one cow, and, of course, a cow may be only assigned to one stall.
Given the preferences of the cows, compute the maximum number of milk-producing assignments of cows to stalls that is possible.
Input
The input includes several cases. For each case, the first line contains two integers, N (0 <= N <= 200) and M (0 <= M <= 200). N is the number of cows that Farmer John has and M is the number of stalls in the new barn. Each of the following N lines corresponds to a single cow. The first integer (Si) on the line is the number of stalls that the cow is willing to produce milk in (0 <= Si <= M). The subsequent Si integers on that line are the stalls in which that cow is willing to produce milk. The stall numbers will be integers in the range (1..M), and no stall will be listed twice for a given cow.
Output
For each case, output a single line with a single integer, the maximum number of milk-producing stall assignments that can be made.
Sample Input
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
Sample Output
4
 #include <iostream>
using namespace std;
int map[201][201];
int match[201];
int visit[201];
int n,m;
bool dfs(int p)
   {
 int x;
for(x=0;x<m;x++)
  {
if(map[p][x]==1 && visit[x]==-1)
{
visit[x]=1;
int t=match[x];
match[x]=p;
if(t==-1 || dfs(t)) return true;
match[x]=t;
 }
}
return false;
 }
int find_match()
{
memset(match,-1,sizeof(match));
int i,sum=0;
for(i=0;i<n;i++)
{
memset(visit,-1,sizeof(visit));
if(dfs(i)) sum++;
}
return sum;
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<m;j++) map[i][j]=0;
for(i=0;i<n;i++)
{
int a,b;
scanf("%d",&a);
for(j=0;j<a;j++)
{
scanf("%d",&b);
map[i][b-1]=1;
}
}
int res=find_match();
printf("%d\n",res);
}
return 1;
}
参考了郭嵩山的第三册，用网上的代码似乎有错。
记录一下2007-12-22的事： 昨天开始跟 Wei Fan进行讨论，一个IBM Research的牛人，主要是说出我们在各自的领域里面的想法，以及讨论写论文的东西。 昨天施潇潇师兄讲了domain transfer的一些情况，接着他讲了他的几个想法，主要还是两个领域个性与共性的问题。 另外，Fan老师的一些建议：考虑out-of-domain的active learning；想法必须简单，intuitive，在五分钟内能跟别人说清楚；想大的topic；考虑将graph spectra用在transfer learning上；提的问题要令人exciting，起点要高；优化算法要懂一些；看paper时不要陷入到细节中，要从高的角度来看文章。 最后跟他用英文聊了一会，发现我英文真是烂啊。
poj两个相似的题目，很有代表性。
pku 1828
pku 2726
题目大意是给出平面上的若干点，找出符合某种要求的点(x0, y0)，如要求不存在点(x, y)，使得x>=x0 且 y>=y0，换一种说法就是对任意点(x, y)都有x<x0 或 y<y0. 下面给出pku 1828的代码
#include <stdlib.h>
#include <stdio.h>
struct node{
int x,y;
}a[50001];
int cmp(const void *aa, const void *bb)
{
node* a=(node*)aa;
node* b=(node*)bb;
if(a->x==b->x) return a->y-b->y;
return a->x-b->x;
}
int i,j,k,n;
int main()
{
while(scanf("%d",&n) && n!=0)
{
for(i=0;i<n;i++) scanf("%d%d",&a[i].x, &a[i].y);
qsort(a,n,sizeof(node),cmp);
//for(i=0;i<n;i++) printf("%d %d\n",a[i].x,a[i].y);
int total=1;
int maxi=a[n-1].y;
for(i=n-2;i>=0;i--)
{
if(a[i].y>maxi)
{
maxi=a[i].y;
total++;
}
}
printf("%d\n",total);
}
return 1;
}
|