Educational Codeforces Round 83

Educational Codeforces Round 83"/>

Educational Codeforces Round 83

Portal.

A. Two Regular Polygons

Portal.

正 n n n 边形中心角为 36 0 ∘ n \dfrac{360^\circ}{n} n360∘​，正 m m m 边形中心角为 36 0 ∘ m \dfrac{360^\circ}{m} m360∘​，若能包含显然要 ( 36 0 ∘ n ) ∣ ( 36 0 ∘ m ) (\dfrac{360^\circ}{n})|(\dfrac{360^\circ}{m}) (n360∘​)∣(m360∘​)，则需要 n ∣ m n|m n∣m。

正多边形的中心角：每一条边所对的外接圆的圆心角。

#include <bits/stdc++.h>
using namespace std;int main()
{int t;cin>>t;while(t--){int n,m;cin>>n>>m;if(n%m) cout<<"NO"<<endl;else cout<<"YES"<<endl;}return 0;
}

B. Bogosort

Portal.

第一反应是移项，把限制条件转化为 j − i ≠ a j − a i j-i\neq a_j-a_i j−i=aj​−ai​。

由于 i < j i<j i<j，左边一定大于 0 0 0，所以只需要右边小于等于 0 0 0 即可。即 a j − a i ≤ 0 a_j-a_i\leq 0 aj​−ai​≤0，由此可知 a i ≥ a j a_i\geq a_j ai​≥aj​。将原序列降序排序即可。

#include <bits/stdc++.h>
using namespace std;int a[105];void solve()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);for(int i=n;i;i--) cout<<a[i]<<' ';cout<<endl;
}int main()
{int t;cin>>t;while(t--) solve();return 0;
}

C. Adding Powers

Portal.

对 a i a_i ai​ 做 k k k 进制拆解。统计 a a a 数组中每一位 k k k 进制下是否有值，若有值将该位的 c n t i cnt_i cnti​ 累加。最后统计是否有 c n t i > 1 cnt_i>1 cnti​>1 的情况。若有，则不存在方案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;ll cnt[105];void solve()
{int n,k;cin>>n>>k;memset(cnt,0,sizeof cnt);int mxlen=0,len;for(int i=1;i<=n;i++){ll a;cin>>a,len=1;while(a) cnt[len]+=a%k,a/=k,mxlen=max(mxlen,++len);}    for(int i=1;i<=mxlen;i++) if(cnt[i]>1){cout<<"NO"<<endl;return;}cout<<"YES"<<endl;
}int main()
{int T;cin>>T;while(T--) solve();return 0;
}

D. Count the Arrays

sol.

E. Array Shrinking

Portal.

区间 DP。

设计状态 f ( l , r ) f(l,r) f(l,r) 表示区间 [ l , r ] [l,r] [l,r] 合并之后的最小长度，用 s l , r s_{l,r} sl,r​ 表示区间 [ l , r ] [l,r] [l,r] 合并之后的新数的值。

显然有转移：
f ( l , r ) = min ⁡ k ∈ [ l , r ] ( f ( l , k ) + f ( k + 1 , r ) ) f(l,r)=\min_{k\in[l,r]}(f(l,k)+f(k+1,r)) f(l,r)=k∈[l,r]min​(f(l,k)+f(k+1,r))
对于可以合并的两个元素，有：
f ( l , r ) = 1 , s l , r = s l , k + 1 f(l,r)=1,s_{l,r}=s_{l,k}+1 f(l,r)=1,sl,r​=sl,k​+1

#include <bits/stdc++.h>
using namespace std;const int maxn=505;
int f[maxn][maxn],s[maxn][maxn];int main()
{memset(f,0x3f3f3f,sizeof f);int n;cin>>n;for(int i=1;i<=n;i++) cin>>s[i][i],f[i][i]=1;for(int len=2;len<=n;len++)for(int i=1;i<=n-len+1;i++){int j=len+i-1;for(int k=i;k<j;k++){f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);if(f[i][k]==1&&f[k+1][j]==1&&s[i][k]==s[k+1][j]) f[i][j]=1,s[i][j]=s[i][k]+1;}}cout<<f[1][n];return 0;
}

G. Autocompletion