2020 ICPC Asia Taipei-Hsinchu Regional Problem B Make Numbers (dfs搜索)

题意:给你四个数字,你可以用这四个数字凑出四个1位数,一个2位数和两个1位数,或一个3位数和一个1位数,你可以用你凑出的数字进行\(+,-,x\)运算(所有运算符号至少出现一次),问你一共能得到多少个不同的数字.
题解:dfs瞎搞,不合法乘法的细节特别多,在dfs函数里面用flag和mult来分别去除出现\((a+b)*c\)和\((a*b)*10\)的情况.
代码:

#include <bits/stdc++.h>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

#define rep(a,b,c) for(int a=b;a<=c;++a)

#define per(a,b,c) for(int a=b;a>=c;--a)

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int a[10];

bool st[10];

bool vis[N];

void dfs(int t,int sum,int flag,int mult){

	if(t==4){

		vis[sum]=true;

		return;

	}

	int mul=1;

	vector<int> v;

	rep(i,1,4){

		if(!st[i]){

			if(t==2) v.pb(a[i]);

			mul*=a[i];

		}

	}

	if(t==2){

		int cnt1=v[0]*10+v[1];

		int cnt2=v[1]*10+v[0];

		if(!flag){

		vis[sum*cnt1]=true;

		vis[sum*cnt2]=true;

		vis[sum+cnt1]=true;

		vis[sum+cnt2]=true;

		}

		vis[abs(sum-cnt1)]=true;

		vis[abs(sum-cnt2)]=true;

	}

	vis[sum+mul]=true;

	if(sum-mul>=0)  vis[sum-mul]=true;

	if(!flag) vis[sum*mul]=true;

	rep(i,1,4){

		if(!st[i]){

			st[i]=true;

			dfs(t+1,sum+a[i],1,0);

			if(sum-a[i]>=0)  dfs(t+1,sum-a[i],1,0);

			if(!flag)  dfs(t+1,sum*a[i],0,1);

			if(!flag && t<3 && !mult)

			dfs(t+1,sum*10+a[i],0,0);

			st[i]=false;

		}

	}

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>a[1]>>a[2]>>a[3]>>a[4];

	rep(i,1,4){

		me(st,false,sizeof(st));

		st[i]=true;

		dfs(1,a[i],0,0);

	}

	int ans=0;

	rep(i,0,100000){

		if(vis[i]){

			ans++;

		}

	}

	cout<<ans<<'\n';

    return 0;

}

巴特西

2020 ICPC Asia Taipei-Hsinchu Regional Problem B Make Numbers (dfs搜索)

最新文章

热门文章