怎么仿别人的网站,中山哪家做网站好,淄博网站制作定制改版,沈阳做网站的公司推荐D - Product of Binary Decimals 题意#xff1a; 思路#xff1a;观察到n的范围很小#xff0c;先求出所有可能的二进制十位数#xff0c;然后dp把所有可能的值求出来。注意不能用求因子的方法来求解#xff0c;因为这些二进制十位数不一定是素数#xff0c;先除某个数…D - Product of Binary Decimals 题意 思路观察到n的范围很小先求出所有可能的二进制十位数然后dp把所有可能的值求出来。注意不能用求因子的方法来求解因为这些二进制十位数不一定是素数先除某个数可能会影响整体的分解。此题数据不大可以忽略 setintv;
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);}
}
vectorintpos;
vectorintdp(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 t1;cint;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;}setstringst;mapstring,intmp;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{vectorstringstrr;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];vectorinte(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 vectorint dp(1 n , vectorint(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;
}
