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

0%

发表于 更新于 Valine：

题目链接

Codeforces Round #580 (Div. 2)

A

思路

直接暴力查询或者直接输出两个最大的即可

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 250;
int a[250],b[250];
bool vis[maxn*2];
int main()
{
	int n,m;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		vis[a[i]]=true;
	}
	cin>>m;
	for(int i=0;i<m;i++)
	{
		scanf("%d",&b[i]);
		vis[b[i]]=true;
	}
	int ans1=0,ans2=0;
	for(int i=0;i<n;i++)
	{   bool ok =false;
		for(int j=0;j<m;j++)
		{
			if(!vis[a[i]+b[j]])
			{
				printf("%d %d\n",a[i],b[j]);
				ok=true;
				break;
			}
		}
		if(ok)break;
	}
	return 0;
}
阅读全文 »

发表于 更新于 Valine：

B

题目链接

B

思路

观察到S(n)=S(n-2)S(n-3)S(n-2),按照位置和长度进行搜索，因为只有1e12长度，先前缀处理出这个长度，就可以搜索了。

代码实现

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll md = 1e12+20;
ll f[501];
string s[5];
int n;
ll k;
void dfs(ll pos,int len,int num)
{
	if(num<=3)
	{
	cout<<s[num].substr(pos,len);
	return;
	}
	if(num>56)
	{
		dfs(pos,len,56);
		return ;
	}
	ll len1=f[num-2],len2=f[num-2]+f[num-3];
	if(pos+len<len1)
	{  
		dfs(pos,len,num-2);
	}
	else if(pos<=len1&&pos+len>=len1)
	{
		if(pos+len>=len2)
		{
			dfs(pos,10,num-2);
		    dfs(0,pos-len1+len,num-3);
		    dfs(0,pos-len2+len,num-2);
		}
		else
		{
		dfs(pos,10,num-2);
		dfs(0,pos-len1+len,num-3);
	    }
	}
	else if(pos+len<=len2)
	{
		dfs(pos-len1,len,num-3);
	}
	else if(pos<len2&&pos+len>=len2)
	{
		dfs(pos-len1,10,num-3);
		dfs(0,pos-len2+len,num-2);
	}
	else if(pos>=len2)
	{
		dfs(pos-len2,len,num-2);
	}
}
int main()
{
	f[1]=6;
	f[2]=7;
	bool ok =false;
	for(int i=3;i<=500;i++)
	{
		f[i]=(f[i-1]+f[i-2])%md;
	}
	for(int i=56;i<=500;i++)f[i]+=md;
	int n;
	scanf("%d",&n);
	s[1]="COFFEE";
	s[2]="CHICKEN";
	s[3]="COFFEECHICKEN";
	int a[34];
	/*for(int i=1;i<=500;i++)
	{   printf("i:%d ",i);
		dfs(i-1,10,499);
		printf("\n");
	}*/
	for(int i=0;i<n;i++)
	{
		ll x,y;
		cin>>x>>k;
		dfs(k-1,10,x);
		printf("\n");
	}
 }
阅读全文 »

发表于 更新于 Valine：

中国剩余定理与扩展中国剩余定理

首先来看这个方程

求出上述x的最小正整数解，即为中国剩余定理。
有两种情况，第一种为$b_1$,$b_2$,$b_3$之间两两互质。
第二种情况为不互质时，也就是扩展中国剩余定理

阅读全文 »

发表于 更新于 Valine：

题目链接

HDU-4507

思路

数位DP，但是需要加上一些数学方法，如何统计平方和呢？
比如abcd是一个满足情况的数，我们拆分成a10^3+b10^2+c10+d;
为了方便就把a=a10^3,b=b10^2类推。
然后这个数就变成了(a+b+c+d)^2,也就是a^2+b^2+c^2+2a(b+c+d)+2b(c+d)+2(cd).
这时候我们发现，是不是可以为何一个sum来统计，用数位DP也正好是递归的思想。
但是，数位DP，我们是针对位数来统计的，如果把abcd中的d换成另一个数e，要怎么统计呢？
这时候我们记录下来满足条件的个数就好了，回溯的时候在乘上个数，sum里面已经包含了e的贡献了。
这样，这题就解决了。

阅读全文 »

发表于 Valine：

题目链接

pair

题目描述

给出三个数字A,B,C。要你从1-A中取一个x，从1-B中取一个y。找出共有多少对(x,y)满足以下至少一个条件
1.x&y>c;
2.x^y<c;

思路

比赛的时候以为是数论知识，看了题解发现是数位DP，把A,B都转化为二进制，然后用二维的数位DP写。
dp[pos][and][xor][limit1][limit2]表示第pos位的数上 取和 以及取 异或 的情况。
Note：任何二进制的数位DP，都不能忽略前缀0，所以在统计完答案后，需要减去由于前缀0而产生的贡献。
所以还需要添加二维变成dp[pos][and][xor][limit1][limit2][zero1][zero2];
也可以用数学方法推出来多余的数。实际上应该等于ans=min(a,c-1)+min(b,c-1)+1(不会证明)；

阅读全文 »

发表于 Valine：

题目链接

Treasure Cave

题目描述

实际上就是求二叉树的最短遍历，输出路径

思路

采用递归的方式，先不停的深入下去，找到点后就输出，在递归的过程中输出即可。

代码实现

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
#include<iostream>
using namespace std;
int pre[5010];
int solve(int x,int m)
{
	if(m==1)
	{
		cout<<x<<endl;
		return 1;
	}
	if(solve(x+1,pre[m]))cout<<pre[m]<<endl;
}
int main()
{
	int n,s,t;
	while(cin>>n>>s>>t)
	{
		int mm,u,p;
		for(int i=1;i<=n;i++)pre[i]=i;
		for(int i=1;i<=s;i++)
		{
			cin>>mm>>u>>p;
			pre[u]=pre[p]=mm;
		}
		if(solve(1,t))cout<<t<<endl;
	}
}

发表于 Valine：

题目链接

F(x)

思路

一开始我是用前缀和分开，然后最后判断sum与f(a)的关系的，但是

后来我发现，如果我这样写，对于不同的f(a),需要不停的对dp数组重置为-1.
于是，我们必须要找到一个状态，与f(a)无关。所以我们可以把f(a)移项。
这样我们维护的就是sum-f(a)的值，并且对于每次搜索，我们只需要先把f(a)放进去。
然后出来的时候判断是否大于等于零即可
这样做的好处就是至于要对dp数组初始化一次即可，记忆化搜索可加速。

阅读全文 »

发表于 Valine：

题目链接

B-number

题目描述

求l-r之间满足有13并且能够整除13的数。
dp[pos][mod][is13]表示第i位上，余数为mod,is13是是否满足拥有13.
is13有三种情况。
1.当前没有1
2.当前有1
3.当前有13
然后数位DP的板子套一下就好了

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[20][20][3];
int a[20];
ll dfs(int pos,bool is1,int remain,bool limit,int is13)
{
	if(pos==-1)
	{
		return !remain&&is13==2;
	}
	if(!limit&&dp[pos][remain][is13]!=-1)return dp[pos][remain][is13];
	int up = limit?a[pos]:9;
	ll temp = 0;
	for(int i=0;i<=up;i++)
	{   int ok13 = is13;
	    if(is13==0&&i==1)ok13=1;
	    if(is13==1&&i!=1)ok13=0;
	    if(is13==1&&i==3)ok13=2;
		temp+=dfs(pos-1,i==1,(remain*10+i)%13,limit&&i==up,ok13);
	}
	return limit?temp:dp[pos][remain][is13]=temp;
}
ll solve(ll x)
{
	int p = 0;
	ll ans = 0;
	while(x)
	{
		a[p++]=x%10;
		x/=10; 
	} 
	ans+=dfs(p-1,0,0,1,0);
	return ans;
}
int main()
{
	ll y;
	memset(dp,-1,sizeof(dp));
	while(cin>>y)
	{
		printf("%lld\n",solve(y));
	}
}

发表于 Valine：

题目链接

Balanced Number

题目描述

定义一种数叫做Balanced number，这样子的数满足，选取一个位置后，分成左右两边然后向左向右分别乘上1，2，3，4后相加相等。

思路

能够枚举的位置最多18位，所以可以考虑暴力枚举位置，并且，每一个数至多有一个位置能够满足该定义。
所以我们可以设dp[len][pos][sum],代表第len个位置，pos是我们枚举的中点位置，sum表示该数当前的和，如果len==-1，判断sum是否==0就好。
其中可以剪枝，也就是当sum<0的时候就可以返回0了，因为sum<0后sum后面一定会更小不会更大了。

阅读全文 »

发表于 Valine：

题目链接

Round Numbers

思路

题目要求l~r种满足二进制0的个数大于等于1的数，那么可以对二进制数做数位DP。
dp[pos][num0][num1]表示在pos位置时已确定的0和1的个数。那么到最后一位时我们只需要比较num0和num1就可以确定答案了。
坑点：前导0的判断，这道题可能会出现前导0，因为我们是从高位向低位推，所以前导零的状态也可以一起转移。

阅读全文 »