感慨

爬到青名的第一战，结果B题没有过system test又掉回到了1390+，这次越南出题组出的题还是比较有意思的

A Got Any Grapes?(模拟)

分析

根据题意我们可以进行模拟
首先第一个人只吃绿色的，第二个人吃绿色和紫色的，第三个人通吃
所以就可以得出我们先把绿色给第一个人吃，剩下的绿色和紫色给第二个人，最后剩下的给第三个人
只要哪一步出现了问题，也就是说不够吃那么就是NO都可以就输出YES

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m,k,x,y,z;
  cin>>n>>m>>k>>x>>y>>z;
  x-=n;
  if(x<0)
  return cout<<"NO",0;
  int t1=x+y-m;
  if(t1<0)
  return cout<<"NO",0;
  int t2=t1+z-k;
  if(t2<0)
  return cout<<"NO",0;
  cout<<"YES";
}

B Yet Another Array Partitioning Task(贪心+模拟)

分析

这个题操作很感人啊，当时我一看不就是把前mk个数加起来求和么，结果发现还有第二步找断点
断点的寻找也是比较的难想，这里我分享一个简单的实现
首先就是要找单位区间内的最大的理想值，我们需要把所有的前km项都要用上
所以说我们要看看区间内是否符合当前m个要找的数
操作方法就是把每个数先记下原来的坐标然后降序排列，定义一个新的数组用降序排列的顺序把原来的坐标定位到当前坐标也就是说要

1	bk[pre[i].id]=i;

然后走一遍原先的坐标的顺序，就可以知道当前坐标是不是满足且合适的数了

代码

#include <bits/stdc++.h>
using namespace std;
struct node
{
  long long sum,id;
}num[666666];
bool cmp(node a,node b)
{
  return a.sum>b.sum;
}
int bk[666666];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n,m,k,te=0,cnt=0,ans=0;
  cin>>n>>m>>k;
  for(int i=1;i<=n;i++)
  cin>>num[i].sum,num[i].id=i;
  sort(num+1,num+n+1,cmp);
  for(int i=1;i<=m*k;i++)
  ans+=num[i].sum;
  for(int i=1;i<=n;i++)
  bk[num[i].id]=i;
  cout<<ans<<"\n";
  for(int i=1;i<=n;i++)
  {
    if(bk[i]<=k*m)
    te++;
    if(te==m)
    {
      cnt++;
      if(cnt<k)
      cout<<i<<" ";
      te=0;
    }
  }
}

C Trailing Loves (or L’oeufs?)(数论)

分析

很巧妙的一个题，用到数论的知识
首先n!可以分解质因数并且b也能分解质因数所以我们可以用木桶原理看看这些阶乘里面最少能装几组质因数的次方
首先我们要明白一个概念一个十进制有一个0代表这个十进制能整除10有两个0代表他能被10^2整除同样b进制也一样如果有一个0代表能被b整除有两个代表能被b^2整除
且这是一个木桶原理也就是说找最小值就是能找到几个0
然后就是分解质因数这里有一个十分巧妙的方法分解n!
首先分解单个数的要寻找的质因数就是去寻找能被整除的次数也就是说如果找150有几个0就是循环2*5的分解质因数也就是

while(b%2==0)
{
  b/=2;
  cnt++;
}

然后求出最小值即可这样就能找到0的个数是1

1	ans=min(ans1,ans2);

同样如果是n!那么我们会发现1-n总共有n个数所以说呢，我们需要进行一种特殊的方法同样以150为例不过这次是150!后有多少个0我们就需要寻找150能被2整除的多少次能被5整除的多少次也就是说

while(b/2)
{
  cnt+=b/2;
  b/=2;
}

最后取min即可
最终我们结合两个步骤先质因数分解b然后接着分解a最后找floor(ai/bi)的最小值即可
这里还需要注意有一个小小的优化那就是我们需要如果当前走的i*i>b那么i=b
因为一个数n的因子最大是sqrt(n)
这里也是b在慢慢的缩小也是一种优化

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ll n,b;
  cin>>n>>b;
  ll ans=ll(1e18);
  for(ll i=2;i<=b;i++)
  {
    if(1LL*i*i>b)
    i=b;
    ll cnt=0;
    while(b%i==0)
    {
      b/=i;
      cnt++;
    }
    if(cnt==0)
    continue;
    ll tmp=0,now=n;
    while(now/i)
    {
      tmp+=now/i;
      now/=i;
    }
    ans=min(ans,tmp/cnt);
  }
  cout<<ans;
}

D Flood Fill(DP)

分析

有二维的解法但是我太蒟蒻了，只会三维的。这个上来还容易re
实际上就是定义两个：
dp[l][r][0]代表最少需要多少步能够使l,r区域内都是num[l]颜色
dp[l][r][1]代表最少需要多少步能够使l,r区域内都是num[r]颜色
那么转移方程就是：
dp[l-1][r][0]=min(dp[l-1][r][0],dp[l][r][t(当前的开关)]+左边的颜色与当前的颜色一样?1:0)
第二个同理
还有就是要注意这种枚举区间的方式

代码

#include <bits/stdc++.h>
using namespace std;
int num[5001];
int dp[5001][5001][2];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  cin>>num[i];
  for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
  dp[i][j][0]=dp[i][j][1]=(i==j?0:999999);
  for(int r=1;r<=n;r++)
  for(int l=r;l>=1;l--)
  for(int t=0;t<2;t++)
  {
    int now=t==0?num[l]:num[r];
    if(l>1)
    dp[l-1][r][0]=min(dp[l-1][r][0],dp[l][r][t]+(now!=num[l-1]));
    if(r<n)
    dp[l][r+1][1]=min(dp[l][r+1][1],dp[l][r][t]+(now!=num[r+1]));
  }
  cout<<min(dp[1][n][0],dp[1][n][1]);
}