你最愿意做的哪件事，才是你的天赋所在

0%

牛客假日团队赛11

发表于 Valine：

题目链接

牛客假日团队赛11

B

思路

很明显的一道背包题目，首先对游戏平台做0,1背包，然后再游戏平台里得游戏做条件背包。
dp[i][j]表示前i个游戏平台j钱得最大贡献
首先针对游戏平台，先处理dp[i][j]=dp[i][j-pi];
然后再游戏平台中dp[i][j]=max(dp[i][j],dp[i][j-cost]+val)
最后再更新dp[i][j]=max(dp[i][j],dp[i-1][j]);

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int dp[60][100005];
//dp[i][j]表示前i个平台花费j钱的最大值
//状态转移，对每个游戏平台单独考虑做01背包。
//dp[i][j]=max(dp[i][j],dp[i][j]+val);
//对平台内的游戏做条件背包 
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int pi,cnt;
        scanf("%d %d",&pi,&cnt);
        for(int j=pi;j<=m;j++)dp[i][j]=dp[i-1][j-pi];
        for(int j=0;j<cnt;j++)
        {
            int cost,pro;
            scanf("%d %d",&cost,&pro);
            for(int k=m;k>=cost+pi;k--)dp[i][k]=max(dp[i][k],dp[i][k-cost]+pro);
        }
 
        for(int j=0;j<=m;j++)dp[i][j]=max(dp[i][j],dp[i-1][j]);
    }
    cout<<dp[n][m]<<endl;
}

C

思路

这道题可以bfs，但是这里介绍一种传递闭包得做法，就是先判断1-9中每个数能变成得数有几个。
然后答案就等于n每个位数上得数相乘。可以用floyd传递闭包。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
#define ll __int128
string n;
int k;
bool mp[10][10];
inline __int128 read()
{
   int X=0,w=0; char ch=0;
   while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
   while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
   return w?-X:X;
}
void print(__int128 x)
{
	if (!x) return ;
	if (x < 0) putchar('-'),x = -x;
	print(x / 10);
	putchar(x % 10 + '0');
}
void folyd()
{
	for(int k=0;k<10;k++)
	{
		for(int i=0;i<10;i++)
		{
			for(int j=0;j<10;j++)
			{
				mp[i][j]=(mp[i][k]&&mp[k][j])||mp[i][j];//这里就是传递闭包
			}
		}
	}
}
int a[10];
int main()
{
	cin>>n;
	scanf("%d",&k);
	ll ans = 1;
	for(int i=0;i<k;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		mp[x][y]=true;
	}
	folyd();
	for(int i=0;i<10;i++)
	{   a[i]++; 
		for(int j=0;j<10;j++)
		{
			if(i==j)continue;
			if(mp[i][j])a[i]++;
		}
    }
    if(n[0]=='0')return 0*printf("%d\n",a[0]);
    for(int i=0;i<n.size();i++)
    {
    	ans*=a[n[i]-'0'];
	}
	print(ans);
}

D

思路

拓扑排序，首先，单向边入列，并且入度加，双向边不加入读。
然后拓扑排序的时候，每次把入读为0的点所连接的边删除，然后与这个点所连接的双向边，方向为该点发散。
如果一开始就存在环，那么这个环不可能入列，所以最后判断是否存在没有访问过的点来确定是否存在环

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int in[maxn];
bool vis[maxn];
int head[maxn*4]; 
int cnt = 0;
struct node
{   int from;
	int next;
	int to;
	int val;
}edge[maxn*4];
void add(int s,int t,int val)
{   edge[cnt].from=s;
	edge[cnt].to=t;
	edge[cnt].val=val;
	edge[cnt].next=head[s];
	head[s]=cnt++;
}
int main()
{
	int n,m,l;
	//freopen("test2.in","r",stdin);
	memset(head,-1,sizeof(head));
	scanf("%d %d %d",&m,&n,&l);
	for(int i=0;i<n;i++)
	{
		int s,t;
		scanf("%d%d",&s,&t);
		add(s,t,0);
		in[t]++;
	} 
	queue<int>q;
	for(int i=1;i<=m;i++)
	if(in[i]==0)q.push(i);
	for(int i=1;i<=l;i++)
	{
		int s,t;
		scanf("%d %d",&s,&t);
		add(s,t,1);
		add(t,s,1);
	}
	while(!q.empty())
	{
		int s=q.front();q.pop();
		vis[s]=true;
		for(int i=head[s];i!=-1;i=edge[i].next)
		{   
			if(edge[i].val==0)
			{
				in[edge[i].to]--;
				if(in[edge[i].to]==0)q.push(edge[i].to);
			}
		}
		for(int i=head[s];i!=-1;i=edge[i].next)
		if(edge[i].val==1)edge[i^1].val=2;
	}
	for(int i=1;i<=m;i++)
	if(!vis[i])return 0*printf("-1\n");
	for(int i=0;i<cnt;i++)
	if(edge[i].val==1)printf("%d %d\n",edge[i].from,edge[i].to);
}

G

思路

首先，要从后面往前面扫一遍，扫出每个节点的最小速度。因为如果当前节点速度太大，后面可能刹不住车
然后增加两个点，一个是第一个点，长度为0，速度为1，第二个是最后一个点长度为len，速度为max。
每次计算两个点之间的最大速度，可以列出一个方程
设$v_0$为起始速度，$v_1$为结束速度,x为加速的距离，y为减速的距离那么

可以求出
那么最大速度就等于$v_0+x$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
	int len,speed;
}a[100100];
int cmp(node a,node b)
{
	 return a.len<b.len;
}
int main()
{
	int l,n;
//	freopen("test2.in","r",stdin);
	scanf("%d %d",&l,&n);
	for(int i=1;i<=n;i++)scanf("%d %d",&a[i].len,&a[i].speed);
	a[0].len=0;
	a[0].speed=1;
	a[n+1].len=l;
	a[n+1].speed=a[n+1].len+1;
	sort(a+1,a+n+1,cmp);
	int maxx = 1;
	int end=1;
	for(int i=n;i>=1;i--)
	{
		a[i-1].speed=min(a[i-1].speed,a[i].speed+a[i].len-a[i-1].len);
	}
	for(int i=0;i<=n;i++)
	{
		//计算i~i+1这段路上最大速度为多少 
		//3种情况，1.全部加速，2.加速后减速，3.减速
		if(end+a[i+1].len-a[i].len<=a[i+1].speed) 
		{
			end+=a[i+1].len-a[i].len;
		}
		else if(end+a[i+1].len-a[i].len>=a[i+1].speed)
		{
			end+=(a[i+1].len-a[i].len-end+a[i+1].speed)/2;
		}
		maxx=max(maxx,end);
		end=min(end,a[i+1].speed);
	}
	cout<<maxx<<endl;
}

H

思路

一道简单的dp题目
dp[i][j]=dp[i-1][j]+dp[i][j-1];
如果马占领了该格子，则dp[i][j]=0;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
long long dp[25][25];
bool mp[25][25];
int ans = 0;
int n,m,x,y;
int main()
{
	scanf("%d %d %d %d",&m,&n,&y,&x);
	x++;y++;n++;m++;
	mp[x-1][y-2]=mp[x-2][y-1]=mp[x-2][y+1]=mp[x-1][y+2]=true;
	mp[x][y]=mp[x+1][y-2]=mp[x+1][y+2]=mp[x+2][y-1]=mp[x+2][y+1]=true;
	dp[1][1]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(mp[i][j])
			{
				dp[i][j]=0;
				continue;
			}
			else
			{
				dp[i][j]+=dp[i-1][j]+dp[i][j-1];
			}
		}
	}
	cout<<dp[n][m]<<endl;
}

K

思路

这道题，发现N很小，所以我们考虑用floyd。
floyd的最外层循环枚举的是经过k个点时dis[i][j]，i与j之间的最短路，那么我们可以先排序。
这样经过的k点最能够从小到大，所以当前的k点就是最大的点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
const int maxn =255;
int mp[maxn][maxn];
int dp[maxn][maxn];
int Hash[255];
struct node
{
	int x,val;
}a[maxn];
void folyd()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
				dp[i][j]=min(dp[i][j],mp[i][j]+max(max(a[i].val,a[j].val),a[k].val));
			}
		}
	}
}
int cmp(node a,node b)
{
	return a.val<b.val;
}
int main()
{   memset(mp,0x3f,sizeof(mp));
    memset(dp,0x3f,sizeof(dp));
	scanf("%d %d %d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].val);
		a[i].x=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)Hash[a[i].x]=i;
	for(int i=1;i<=m;i++)
	{
		int s,t,v;
		scanf("%d %d%d",&s,&t,&v);
		mp[Hash[s]][Hash[t]]=mp[Hash[t]][Hash[s]]=min(v,mp[Hash[s]][Hash[t]]);
	}
	folyd();
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",dp[Hash[l]][Hash[r]]);
	}
}
-------------你最愿意做的哪件事才是你的天赋所在-------------