zhangas

Pay more attention

0%

7.24SDKDACM

Posted on

P1114 “非常男女”计划

题目链接

N^2暴力 60pts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   int n=read();
for(int i=1;i<=n;i++){
	t[i]=read();
	if(t[i])a[i]=1;
	else b[i]=1;
}
for(int i=1;i<=n;i++){
	a[i]+=a[i-1];
	b[i]+=b[i-1];
}
int ans=0;
for(int i=1;i<=n;i++){
	for(int j=i+1;j<=n;j++){
		int aa=a[j]-a[i-1];
		int bb=b[j]-b[i-1];
		if(aa==bb)
			ans=max(ans,j-i+1);
	}
}
cout<<ans<<endl;

借助局部答案优化内层循环 100pts 不是正解,数据大仍可hack

1
2
3
4
5
6
7
8
   for(int i=1;i<=n;i++){
    int k=max(1,ans);
    for(int j=i+k;j<=n;j++){
		int aa=a[j]-a[i-1];
		int bb=b[j]-b[i-1];
			ans=max(ans,j-i+1);
	}
}

正解： 边读入边处理 分两种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unordered_map<int,int>mp;
int n=read();
int ans=0;
for(int i=1;i<=n;i++){
	t[i]=read();
	if(!t[i])
           t[i]=-1;//女生标注为-1
	t[i]+=t[i-1];
	if(!t[i])//当人数相等时 即和为0
		ans=i;
	else{//有-1 和 1两种可能
		if(mp[t[i]]){//减去第一次出现-1 或者1 的下标
			ans=max(ans,i-mp[t[i]]);
		}
		else mp[t[i]]=i;
	}
}
cout<<ans;

P3074 [USACO13FEB] Milk Scheduling S

题目链接
有M个要求：奶牛A必须在奶牛B前挤奶
为了尽量完成挤奶任务，聘请了一大批雇工协助任务，同一时刻足够去给任意数量的奶牛挤奶。然而，尽管奶牛可以同时挤奶，但仍需要满足以上的挤奶先后顺序。请计算挤奶过程中的最小总时间。

找出所有非孤立且入度为0的点dfs即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a[10005];
int ru[10005];
vector<int>d[10005];
int ans;
int t[10005];
int dfs(int u){
	if(t[u]!=0)//记忆化搜索
		return t[u];
	int res=0;
	for(int i=0;i<d[u].size();i++){
		int v=d[u][i];
		//u -> v
		res=max(res,dfs(v));
	}
	return t[u]=res+a[u];
}

1<=N<=10,000 1<=M<=50,000 借助稀疏图存储路径
显然孤立点消耗的时间就是读入的时间，应该在所有孤立点中取最长时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   for(int i=1;i<=n;i++){
	a[i]=read();
}
   while(m--){
       //a -> b
	int a=read(),b=read();
	ru[b]++;
	d[a].push_back(b);//建图
}
   for(int i=1;i<=n;i++){
       if(d[i].size()==0)
           t[i]=a[i];
   }
   for(int i=1;i<=n;i++){
	if(ru[i]==0&&d[i].size()>0){
		dfs(i);
	}
}
   for(int i=1;i<=n;i++){
       ans=max(ans,t[i]);
   }
   cout<<ans<<endl;