Codeforces Round 937 (Div. 4)（D~G）

D - Product of Binary Decimals 

        题意：

        思路：观察到n的范围很小，先求出所有可能的二进制十位数，然后dp把所有可能的值求出来。注意不能用求因子的方法来求解，因为这些二进制十位数不一定是素数，先除某个数可能会影响整体的分解。（此题数据不大可以忽略）

set<int>v;
void dfs(int step , int num){
	if(step == 5){
		v.insert(num);
		return;
	}
	for(int i = 0 ; i < 2 ; i ++){
		int k = num * 10 + i;
		dfs(step + 1 , k);
	}
}
vector<int>pos;
vector<int>dp(N , 0);
void solve() 
{
	cin >> n;
	if(dp[n]){
		cout <<"YES\n";
	}
	else
		cout <<"NO\n";
}            
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
	dfs(0 , 0);
	for(auto it : v){
		pos.pb(it);
	}
	dp[0] = dp[1] = 1;
	for(int i = 1 ; i < N ; i ++){
		if(!dp[i]) continue;
		for(auto j : pos){
			if(i * j < N){
				dp[i * j] = 1;
			}
			else{
				continue;
			}
		}
	}
    while(t--)
    {
    	solve();
    }
    return 0;
}

E - Nearly Shortest Repeating Substring  

        题意：

        直接暴力求解，枚举字符串长度,若长度是的因子则将其分成份，看是否满足题意。时间复杂度取决于的因子数量，根据约数个数定理，约数数量约为个，因此复杂度为。

void solve() 
{
	cin >> n;
	string s;
	cin >> s; 
	for(int i = 1 ; i <= n ; i ++){
		if(n % i != 0){
			continue;
		}
		set<string>st;
		map<string,int>mp;
		for(int j = 0 ; j < n ; j += i){
			string str = s.substr(j , i);
			st.insert(str);
			mp[str]++;
			if(st.size() > 2){
				break;
			}
		}
		if(st.size() == 1){
			cout << i << endl;
			return;
		}
		if(st.size() > 2){
			continue;
		}
		else{
			vector<string>strr;
			for(auto it : st){
				strr.pb(it);
			}
			if(mp[strr[0]] > 1 && mp[strr[1]] > 1)
				continue;
			else{
				int cnt = 0;
				for(int j = 0 ; j < i ; j ++){
					if(strr[0][j] != strr[1][j]){
						cnt++;
					}
					if(cnt > 1)
						break;
				}
				if(cnt == 1){
					cout << i <<endl;
					return;
				}
			}
		}
	}	
	cout << n << endl;
}   

F - 0, 1, 2, Tree! 

        题意：

        若一棵树要尽可能的矮，那么每一层的结点要尽可能的多，而只有2个孩子的顶点才能增加每一层的结点个数，因此先放2个孩子的顶点，然后记录每一层的结点数，再将1个孩子的，0个孩子的顶点放进去。

void solve() 
{
	int a , b , c;
	cin >> a >> b >> c;
	if(a * 2 + b != a + b + c - 1){
		cout << -1 << endl;
	}	
	else{
		int t = 0;//层数
		int maxx = 1;//每一层最多有几个点
		while(a > maxx){
			a -= maxx;
			maxx *= 2;
			t++;
		}
		if(a > 0){
			b -= (maxx - a);
			maxx += a;//向下还有这么多
			t++;
		}
		while(b > 0){
			b -= maxx;
			t++;
		}
		cout << t <<endl;
	}
}   

G - Shuffling Songs  

将其看成图，能连着播放的点连边，然后考虑最多能选几个点。观察到n的数量极小，考虑状压DP求解。表示了以为状态,为最后一个点的可能。

void solve() 
{
	cin >> n;
	string a[n] , b[n];
	vector<int>e(n , 0);
	for(int i = 0 ; i < n ; i++){
		cin >> a[i] >> b[i];
	}
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < n; j++){
			if(a[i] == a[j] || b[i] == b[j])
				e[i] |= (1 << j);
		}
	}
	vector< vector<int> > dp(1 << n , vector<int>(n , 0));//第一位状压,第二位表示最后一个
	for(int i = 0 ; i < n ; i ++){
		dp[1 << i][i] = 1;
	}
	for(int mask = 0 ; mask < (1 << n) ; mask++){
		for(int i = 0 ; i < n ; i ++){//最后一个点为i点
			if(!dp[mask][i])	continue;
			for(int j = 0 ; j < n ; j ++){//添加j点进去
				if((mask >> j & 1))//当前点已经选过了
					continue;
				if((e[i] >> j) & 1){//i到j有边存在
					dp[mask | (1 << j)][j] = 1;
				}
			}
		}
	}
	int ans = 0;
    for(int mask = 0; mask < (1 << n); mask ++) {
        for(int i = 0; i < n; i ++) {
            if(dp[mask][i]) {
                ans = max(ans, __builtin_popcount(mask));
            }
        }
    }
    cout << n - ans << endl;
}