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

0%

发表于 更新于 Valine：

题目链接

HDU3974

思路

建立一个时间轴，然后直接模拟即可。
这题也可以使用dfs序线段树，明天补题解。

代码实现

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
64
65
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e4+10;
int fa[maxn];
struct node
{
	int job;
	int time;
	node(){
		job = -1;
		time = 0;
	}
}f[maxn];
int main()
{
	int t;
	scanf("%d",&t);
	string op;
	for(int cas = 1;cas<=t;cas++)
	{
		memset(fa,-1,sizeof(fa));
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)f[i].job=-1,f[i].time=-1;
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d %d",&u,&v);
			fa[u]=v;
		}
		int m;
		scanf("%d",&m);
		cout<<"Case #"<<cas<<":"<<endl;
		int tem = 0;
		while(m--)
		{
			cin>>op;
			if(op[0]=='C')
			{
				int x;
				scanf("%d",&x);
				int y = f[x].job;
				int temp = f[x].time;
				while(x!=-1)
				{
					if(f[x].time>temp)
					{
						temp = f[x].time;
						y= f[x].job;
					}
					x=fa[x];
				}
				printf("%d\n",y);
			}
			else 
			{
				int x,y;
				scanf("%d %d",&x,&y);
				f[x].job=y;
				f[x].time=++tem;
			}
		}
	}
}

发表于 Valine：

题目链接

Gym102222G

思路

首先我们来弄清楚floyd算法，普通的floyd算法我们只用来算最短路，所以通常都省略了一维空间。

1
2
3
4
5
6
7
8
9
10
for(int k=1;k<=n;k++)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
		}
	}
}

阅读全文 »

发表于 更新于 Valine：

题目链接

Codeforces Round #582 (Div. 3)

C

思路

注意到每个的贡献都是一个循环，打个表后，直接取贡献。

代码实现

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;
#define ll long long 
int all[11];
int num[11];
int pre[10][11];
int presum[10][11];
void init()
{
	for(int i=1;i<=9;i++)
	{
		int cnt = i;
		int ccnt = 1;
		while(cnt)
		{
			pre[i][ccnt++]=cnt;
			cnt+=i;
			cnt%=10;
		}
		num[i]=ccnt;
	}
	for(int i=1;i<=9;i++)
	{
		for(int j=2;j<11;j++)
		{
			pre[i][j]+=pre[i][j-1];
		}
		all[i]=pre[i][10];
	}
}
int main()
{
	int q;
	scanf("%d",&q);
	init();
	while(q--)
	{
		ll l,r;
		cin>>l>>r;
		int num1=r%10;
		long long ans = 0;
		long long a = l/r;
		if(a==0||num1==0)
		{
			printf("0\n");
			continue;
		}
		a/=num[num1];
		ans+=(a*all[num1]);
		long long b =(l/r)%num[num1];
		ans+=(pre[num1][b]);
		cout<<ans<<endl;
	}
}
阅读全文 »

发表于 更新于 Valine：

这场确实被教育了，自己的缺点暴露无遗，菜也暴露无遗，给我敲响了一个警钟。

题目链接

Educational Codeforces Round 71 (Rated for Div. 2)

C

思路

DP，dp[0][i]表示第i个位置高度为1的最低花费，dp[1][i]表示第i个位置高度为2的最低花费

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5+10;
ll dp[maxn][2];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,a,b;
		scanf("%d %d %d",&n,&a,&b);
		string s;
		cin>>s;
		for(int i=0;i<=n;i++)
		for(int j=0;j<2;j++)
		dp[i][j]=1e18;
		dp[0][0]=b;
		dp[0][1]=1e18;
		for(int i=1;i<=n;i++)
		{
			if(s[i-1]=='1')
			{
				dp[i][1]=b+b+dp[i-1][1]+a;
			}
			else
			{
				dp[i][1]=min(dp[i-1][1]+b+b+a,dp[i-1][0]+a+a+b+b);
				dp[i][0]=min(dp[i-1][1]+a+b+a,dp[i-1][0]+a+b);
			}
		}
		cout<<dp[n][0]<<endl;
	}
}

发表于 Valine：

题目链接

Tunnel Warfare

题目描述

在抗日战争期间，华北平原广大地区进行了大规模的隧道战。 一般来说，通过隧道连接的村庄排成一列。 除了两端，每个村庄都与两个相邻的村庄直接相连。
入侵者经常对一些村庄发动袭击并摧毁其中的部分隧道。 八路军指挥官要求最新的隧道和村庄连接状态。 如果某些村庄严重隔离，必须立即恢复连接！
输入的第一行包含两个正整数n和m（n，m≤50,000），表示村庄和事件的数量。 接下来的m行中的每一行描述一个事件。
以下所示的不同格式描述了三种不同的事件：
D x：第x个村庄被毁。
Q x：指挥官询问第x个村庄与其直接或间接相关的村庄数量。
R：最后毁坏的村庄被重建了。

阅读全文 »

发表于 Valine：

更改器方法与访问器方法

只访问对象而不更改对象内容的方法被成为访问器方法。

1
2
LocalDate date = LocalDate.now();
date=date.plusDays(1);

上述代码则是访问器方法，因为plusDays访问了原先date中的数据，但是并没有修改。而后date发生改变是因为我们手动重新赋值了。

1
2
GregorianCalendar someDay = new GregorianCalendar(2001,11,22);
        someDay.add(Calendar.DAY_OF_MONTH,1000);

阅读全文 »

发表于 Valine：

数组

java的数组与c++的不同
java的数组需要在堆中申请内存

int[] a = new int[10];

一维数组与Arrays

Arrays是java的一个类，里面的函数能够对数组进行处理，一共有以下几个函数

toString

String toString (type[] a)
作用:把a数组中的全部元素转换成为字符串，中间用“，”隔开

阅读全文 »

发表于 更新于 Valine：

题目连接

Codeforces Round #581 (Div. 2)

A

思路

这题，打比赛的时候没注释freopen，然后自闭半天。
我们可以把二进制转换成四进制，每两个数字看作一个四进制。
然后特判10000这种情况和10001这种情况的差别就可以过了。

代码实现

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 main()
{
	//freopen("test.in","r",stdin);
	string s;
	cin>>s;
	int len = s.size();
	int ans=0;
	bool ok =false;
	if(s.size()%2==0)
	ans=len/2;
	else
	{
		for(int i=1;i<s.size();i++)
		{
			if(s[i]=='1')
			{
				ok=true;
				break;
			}
		}
		if(ok)ans=(len+1)/2;
		else ans=len/2;
	}
	cout<<ans<<endl;
}
阅读全文 »

发表于 更新于 Valine：

输出

java的输入类似于C++的输出一半，形式是一样的，不过内容上略有差别。

1
2
3
4
5
6
7
import java.util.*;
public class helloworld{
  public static void main(String[] args)
    {
        System.out.println("Hello world");
    }
}

阅读全文 »

发表于 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]);

阅读全文 »