C++ 动态规划 前缀和

2022牛客寒假算法基础集训营3

Posted by zhangmh on 2022-02-05
Estimated Reading Time 15 Minutes
Words 2.9k In Total
Viewed Times

按照出题人认为的难度顺序排序

A - 智乃的Hello XXXX

img

思路： 签到。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cout<<"hello chino"<<'\n';
	return 0;
}

os：一开始没看这个题以为这次比赛也不会有这种签到题，先看了看别的，结果一刷新已经上千人做完了这个了hhhhhh

D - 智乃的01串打乱

img

思路：签到， 从头开始遍历字符串，找到某个0和某个1，交换即可。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
string s;
int a,b,len;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>len;
	cin>>s;
    for(int i=0;i<len;i++)
    {
    	if(a==0||b==0) 
    	{
    		if(s[i]=='0') a=i;
    	    else if(s[i]=='1') b=i;
		}
    	else break;
	}
	swap(s[a],s[b]);
	cout<<s<<'\n';
	return 0;
}

os：一开始想写找到第一个0和第一个1来着，结果写着写着发现找的不是第一个0和1，不过不重要hhh，swap()函数对于字符串处理之前用过，特别good！

B - 智乃买瓜

img

思路：01背包DP，注意分情况讨论，f[i][j]表示到第i个瓜可以凑够j元的种类，j>a[i]和j=a[i]分别有两种情况，注意区分。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e3+5;
int n,m,a[N];
ll f[N],res1,res2,res;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
    	for(int j=m;j>=1;j--)
    	{
    		f[j]=f[j]%mod;
    		if(j==a[i]/2) f[j]=(f[j]+1)%mod;
    		if(j<a[i]&&j>a[i]/2) f[j]=(f[j]%mod+f[j-a[i]/2]%mod)%mod;
    		if(j==a[i])
			{
				f[j]=(f[j]+1)%mod;
				f[j]=(f[j]%mod+f[j-a[i]/2]%mod)%mod;
			} 
    		if(j>a[i])
			{
				if(f[j-a[i]]!=0)
				res1=f[j-a[i]]%mod;
				else res1=0;
				if(f[j-a[i]/2]!=0)
				res2=f[j-a[i]/2]%mod;
				else res2=0;
				res=(res1%mod+res2%mod)%mod;
				f[j]=(f[j]%mod+res%mod)%mod;
			} 
		}
	}
	for(int i=1;i<=m;i++)
	cout<<f[i]<<" \n"[i==m];
	return 0;
}

os:代码一维优化了一波。当时做这个题的时候因为这两个有两种情况的范围卡了好久好久

I - 智乃的密码

img

思路：尺取法应用，注意尺取法写法。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e5+5;
int a[N],cnt[10],n,L,R;
char s[N];
  
int find(char c)
{
    if('a'<=c&&c<='z') return 1;
    if('A'<=c&&c<='Z') return 2;
    if('0'<=c&&c<='9') return 3;
    return 4;
}
int pan()
{
    int tot=0;
    for(int i=1;i<=4;i++)
    {
    	if(cnt[i]) tot++;
	}
    return tot;
}
  
int main()
{
    cin>>n>>L>>R;
    scanf("%s",s);
    for(int i=0;i<n;i++) a[i]=find(s[i]);
    ll ans=0;
    for(int i=0,j=0;i<n;i++)
    {
        while(j<=n&&pan()<3)//找到第一个满足条件的值，固定右端点
        {
            if(j<n) cnt[a[j]]++;
            j++;
        }
        int l=max(j,L+i);//max，min函数确保满足长度要求
        int r=min(n,i+R);
        ans+=max(0,r-l+1);
        cnt[a[i]]--;
    }
    cout<<ans<<'\n';
    return 0;
}

L - 智乃的数据库

img点击并拖拽以移动编辑

img

思路：模拟题，map套vector用法。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e3+5;
int n,m;
int g[N*2][N];
string s[N],ss;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>s[i];
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
        cin>>g[i][j];
	}
	getchar();
	getline(cin,ss);//读入一行字符（包括空格）
	int len=ss.length();
	vector<string>ves;
	for(int i=0;i<len;i++)//截取分类关键词
	{
		if(ss[i]==','||ss[i]==';')
		{
			string t="";
			int j=i;
			while(1)
			{
				j--;
				if(ss[j]==' '||ss[j]==',') break;
				t+=ss[j];
			}
			reverse(t.begin(),t.end());
			ves.push_back(t);
		}
	}
	vector<int>vei;
	len=ves.size();
	for(int i=0;i<len;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(ves[i]==s[j]) vei.push_back(j);
		}
	}
	sort(vei.begin(),vei.end());//vector内也可以排序
	map<vector<int>,int>mp;
	len=vei.size();
	for(int i=1;i<=n;i++)
	{
		vector<int>vec;
		for(int j=0;j<len;j++)
		{
			vec.push_back(g[i][vei[j]]);
		}
		mp[vec]++;
	}
	cout<<mp.size()<<'\n';
	for(auto&t:mp)//输出，之前我经常用迭代器，这样也可以
	{
		cout<<t.second<<' ';
	}
	return 0;
}

os：第一次用STL嵌套，，，涨知识了

E - 智乃的数字积木(easy version)

img

img

思路：未改变染色前，只能改变相邻的相同颜色区域，所以ans1为把原相连相同颜色的色块从大到小排序；看到数据范围，染色处理就用暴力染色，后再与得到ans1一样处理即可得到ans2。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e5+5;
int n,m,k,u,v;
int col[N];
char s[N];

ll cut()
{
	for(int l=1,r=1;l<=n;l=r+1,r=l)//数组切段写法
	{
		while(r<n&&col[r+1]==col[l]) r++;
		sort(s+l,s+1+r,[](const char&A,const char&B) 
		{
            return A>B;//排序，cmp函数不是多次使用可以这样写
        });
	}
	ll res=0;
	for(int i=1;i<=n;i++)
	{
		res=res*10+(s[i]-'0');
		res%=mod;
	}
	return res;
}

void pan(int a,int b)
{
	for(int i=1;i<=n;i++)
	{
		if(col[i]==a)col[i]=b;
	}
	return;
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++) scanf("%d",&col[i]);
    printf("%lld\n",cut());
    while(k--)
    {
    	scanf("%d%d",&u,&v);
    	pan(u,v);
    	printf("%lld\n",cut());
	}
	return 0;
}

os：一开始看这个题的时候读错题了

C - 智乃买瓜(another version)

img

img

思路：在easy version中，转化方程为dp[i][j]=dp[i−1][j−wi]+dp[i−1][j−wi/2]+dp[i−1][j]，这个题很显然是它的逆过程，那么转化方程就是dp[i][j]=dp[i+1][j]−dp[i][j−wi]−dp[i][j−wi/2]，vector的用处是对于可能取一半瓜的情况直接得到原来瓜的重量，然后在dp数组中减去该重量瓜对于所有情况的影响，而这两个步骤必是同时进行的。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e3+5;
int m;
ll f[N]; 

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>m;
    f[0]=1;
    vector<int>vec;
	for(int i=1;i<=m;i++) cin>>f[i];
	for(int i=1;i<=m;i++)
	{
		while(f[i])
		{
			vec.push_back(i*2);
			for(int j=0;j<=m;j++)
			{
				if(j+i<=m) f[j+i]-=f[j];
				while(j+i<=m&&f[j+i]<0) f[j+i]+=mod;
				if(j+i*2<=m) f[j+i*2]-=f[j];
				while(j+i*2<=m&&f[j+i*2]<0) f[j+i*2]+=mod;
			}
		}
	}
	cout<<vec.size()<<'\n';
	for(int i=0;i<vec.size();i++)
	printf("%d%c",vec[i]," \n"[i+1==vec.size()]);//写法可以学习
	return 0;
}

os：vector使用还是挺方便的，尤其是这种未知规模的数据。

G - 智乃的树旋转

img

imgimg

思路：首先读清题意，树旋转就是父子关系的改变，原来的父节点变成了原来子节点的子节点，这里使用结构体和结构体指针的一点知识。建立两棵二叉树，遍历节点，父子关系不同的就是旋转节点。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e3+5;
int n,ra,rt;

struct tree
{
	int fa,ch[2];
} t[N],a[N];

int build(tree*t,int n)
{
	int x,y;
	vector<bool>v(n+1,true);
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y;
		v[x]=v[y]=false;
		t[i].ch[0]=x;
		t[i].ch[1]=y;
		if(x) t[x].fa=i;
		if(y) t[y].fa=i;
	}
	for(int i=1;i<=n;i++)
	if(v[i]) return i;
	return -1;
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    ra=build(a,n);
    rt=build(t,n);
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=n;j++)
    	{
    		if(t[i].fa==j&&a[j].fa==i)
    		{
    			cout<<"1"<<'\n';
    			cout<<i<<'\n';
    			return 0;//在某些代码中，return 0的位置可以很灵活
			}
		}
	}
	cout<<"0"<<'\n';
	return 0;
}

J - 智乃的C语言模除方程

img

思路： 建模过程的学习。标解：

img

imgimg

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
ll P,r,l,L,R,ans;

ll calx(ll x,ll y)
{
	x=min(P-1,x);
	ll round=(y+1)/P;
	ll last=(y+1)%P;
	return (x+1)*round+min(last,x+1)-1;
}

ll cal(ll l,ll r,ll L,ll R)
{
	return calx(r,R)-calx(l-1,R)-calx(r,L-1)+calx(l-1,L-1);
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>P>>l>>r>>L>>R;
    P=abs(P);
    if(l<=0&&0<=r)
    {
    	ll base=((ll)1e10)/P*P;
    	ans+=(base+R)/P-(base+L-1)/P;
	}
	if(R>0&&r>0)
	ans+=cal(max(1ll,l),r,max(1ll,L),R);
	if(L<0&&l<0)
	ans+=cal(max(1ll,-r),-l,max(1ll,-R),-L);
	cout<<ans<<'\n';
	return 0;
}

os：建模过程是问题转化的过程吧，这个题中模除倒不是一个重点去处理，而是如何求这个个数。

若有错误请指教orz

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
C++ 动态规划 前缀和
FRIENDS
ESC