Educational Codeforces Round 176 (Rated for Div. 2)(A-D)
题目链接：Dashboard - Educational Codeforces Round 176 (Rated for Div. 2) - Codeforces
A. To Zero
思路
发现如果一个偶数-偶数结果是偶数，那么n如果是个奇数就让它减去k变成偶数，之后一直减k-1即可直到减为0
代码
void solve(){
int n,k;
cin>>n>>k;
int cnt=0;
if(n%2){
n-=k;
cnt++;
}
if(n%(k-1))
cout<<cnt+n/(k-1)+1<<"\n";
else
cout<<cnt+n/(k-1)<<"\n";
}
B. Array Recoloring
思路
我们发现只有k=1的时候是有限制的，其他的无论什么情况总是能把前k+1个最大的给弄出来，
k=1时，如果k不在两头我们只能在最开始选择最大的，然后再选择两边最大的那个
如果k在两头，我们最开始选择第二大的，然后在让最大的最后染色即可
代码
#include<bits/stdc++.h>
using namespace std;
#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;
const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;
void solve(){
int n,k;
cin>>n>>k;
vi a(n+10);
int mx=0;
for(int i=1;i<=n;i++){
cin>>a[i];
mx=max(a[i],mx);
}
if(k==1){
if(a[1]==mx||a[n]==mx){
sort(a.begin()+1,a.begin()+1+n);
cout<<mx+a[n-1]<<"\n";
}else{
cout<<mx+max(a[1],a[n])<<"\n";
}
}else{
int sum=0;
sort(a.begin()+1,a.begin()+1+n);
for(int i=n;i>=n-k;i--){
sum+=a[i];
}
cout<<sum<<"\n";
}
}
signed main() {
vcoistnt
cout<<fixed<<setprecision(2);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}C. Two Colors
思路
木板要求恰好只有两种颜色，且要求a[i]<=n的，且颜色连续
设当前木板涂有有两种油漆数量为x，y，我们发现 x+y>=n ，其次只涂这两种颜色的方法有 乘2是将两种颜色倒转，但当x==n或y==n我们需要将木板只包含一种颜色的情况给减掉
此题要用到二分以及前后缀和的优化，不然会T4
代码
#include<bits/stdc++.h>
using namespace std;
#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;
const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;
void solve(){
int n,m;
cin>>n>>m;
vi a(m+10);
for(int i=1;i<=m;i++){
cin>>a[i];
}
sort(a.begin()+1,a.begin()+1+m);
vi suf(m+10,0); //表示后缀和
vi ctn(m+10,0); //表示i之后有几个a[i]==n的数
for(int i=m;i>=1;i--){
ctn[i]=ctn[i+1];
if(a[i]==n) ctn[i]++;
suf[i]=suf[i+1]+a[i];
}
int cnt=0;
/*未用后缀和优化的部分*/
// for(int i=1;i<=m;i++){
// int p=lower_bound(a.begin()+1+i,a.begin()+1+m,n-a[i])-a.begin();
// if(p==m+1) continue;
// for(int j=p;j<=m;j++){
// if(a[i]!=n&&a[j]!=n)
// cnt+=(a[i]+a[j]-n+1)*2;
// else{
// cnt+=(a[i]+a[j]-n+1)*2;
// if(a[i]==n) cnt-=2;
// if(a[j]==n) cnt-=2;
// }
// }
// }
for(int i=1;i<=m;i++){
int p=lower_bound(a.begin()+1+i,a.begin()+1+m,n-a[i])-a.begin();
//找到第一个与a[i]相加大于n的数
if(p==m+1) continue;
cnt+=( suf[p]+(m-p+1)*(a[i]-n+1) )*2;
cnt-=ctn[i+1]*2;
if(a[i]==n){
cnt-=(m-p+1)*2;
}
}
cout<<cnt<<"\n";
}
signed main() {
vcoistnt
cout<<fixed<<setprecision(2);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}D. Equalization
思路
此题要变成x=y，可以发现我们要将x与y最终变成二进制下相等的前缀，那么我们现在可以明确目标是求将x二进制下右移i位，y二进制下右移j位，使得x=y的最小代价，不妨设
表示x右移i位，y右移j位的最小代价，此题便变成了01背包求最小代价
代码
#include<bits/stdc++.h>
using namespace std;
#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;
const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;
vector<vi> dp(75,vi(75,inf));
void init(){
dp[0][0]=0;
for(int k=1;k<=60;k++){
for(int i=70;i>=0;i--){
for(int j=70;j>=0;j--){
if(i>=k) dp[i][j]=min(dp[i][j],dp[i-k][j]+(1ll<<k));
if(j>=k) dp[i][j]=min(dp[i][j],dp[i][j-k]+(1ll<<k));
}
}
}
}
void solve(){
int x,y;
cin>>x>>y;
vi ax(75);
vi ay(75);
int ct1=0;
int ct2=0;
while(x){
ax[++ct1]=x&1;
x>>=1;
}
while(y){
ay[++ct2]=y&1;
y>>=1;
}
reverse(ax.begin()+1,ax.begin()+1+ct1);
reverse(ay.begin()+1,ay.begin()+1+ct2);
int res=3e18;
//求得到一样的前缀的最小代价
for(int i=1;i<=ct1 && i<=ct2;i++){
if(ax[i]!=ay[i])break;
res=min(res,dp[ct1-i][ct2-i]);
}
//求全变成0的最小代价
for(int i=ct1;i<=70;i++)
for(int j=ct2;j<=70;j++)
res=min(res,dp[i][j]);
cout<<res<<"\n";
}
signed main() {
vcoistnt
cout<<fixed<<setprecision(2);
init();
int _=1;
cin>>_;
while(_--) solve();
return 0;
}