[数据结构与算法]【AtCoder】【Beginner Contest 233】A-D

题意：X是已贴邮票的价值，Y是需要贴邮票的价值。缺少的部分只能用价值为10的邮票补齐。问至少需要多少张价值为10的邮票。
思路：简单计算就行。

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int x,y;
	cin>>x>>y;
	if(x<y){
		if((y-x)%10){//有余数需要多补一张
			cout<<(y-x)/10+1<<endl;
		} else {
			cout<<(y-x)/10<<endl;
		}
	} else {
		cout<<0<<endl;
	}
	return 0;
}

题意：给定一个字符串，约定字符串的下标从1开始。将给定范围[L,R]的子字符串反向输出，其余部分正常输出。
思路：正常模拟。

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n,m;
	cin>>n>>m;
	m=m-n+1;//区间长度
	n--;
	string s,t;
	cin>>s;
	t=s.substr(n,m);//区间内的部分
	reverse(t.begin(),t.end());
	cout<<s.substr(0,n)<<t<<s.substr(m+n)<<endl;
	return 0;
}

题意：从每行选取一个数相乘，直至乘到最后一行。问：最终结果为X有多少种方式？
思路：裸深搜从第一行往最后一行搜即可。dfs(x,mult)第一个参数表示第几行，第二个参数表示乘积。
剪枝：当乘积为0或大于X时直接退出。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<ll> >v;
ll n,tar,ans=0;

void dfs(int x,ll mult)
{
	//剪枝 
	if(!mult || mult>tar) return;
	if(x == n){//最后一层的下一层 
		if(mult == tar) ans++;
		return;
	}
	for(int i=0;i<v[x].size();i++){
		dfs(x+1, mult * v[x][i]);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>tar;
	for(int i=0;i<n;i++){
		int k; 
		cin>>k;
		vector<ll>a(k);
		for(int j=0;j<k;j++){
			cin>>a[j];
		}
		v.push_back(a);
	}
	dfs(0,1);
	cout<<ans<<endl;
	return 0;
}

题意：求有多少个连续区间和等于给定数字K。
思路：由题意区间和等于K所以就有前缀和数组s[r]-s[l-1]=k，就变成 s[r]-k=s[l-1]。然后对于每个r只需要求下 s[r]-k的个数，也就是s[l-1]的个数。s[l-1]也是个前缀和,所以循环的时候顺便把前缀和个数自增 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(false);
	ll n,k;
	cin>>n>>k;
	vector<ll>a(n+1),s(n+1,0);
	map<ll,ll>mp;
	ll ans=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		mp[s[i-1]]++;
		ans+=mp[s[i]-k];
	}
	cout<<ans<<endl;
	return 0;
}