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

本文主要是介绍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";}elsecout <<"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;
}

        

这篇关于Codeforces Round 937 (Div. 4)（D~G）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---