Codeforces Round #538 (Div. 2)
题目链接：https://codeforces.com/contest/1114
A. Got Any Grapes?
题意：
有三个人，有三种食物，食物对应的数量为a,b,c，三个人需要的食物量分别为x,y,z。
现在第一个人只吃第一种食物，第二个人只吃前两种食物，第三个人都要吃。问准备的食物数量是否能够满足这三个人。
题解：
简单模拟一下就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int x,y,z;
int a,b,c; int main(){
cin>>x>>y>>z>>a>>b>>c;
if(a>=x && a-x+b>=y && a+b+c-x-y>=z) cout<<"YES";
else cout<<"NO";
return ;
}
B. Yet Another Array Partitioning Task
题意：
给出n个数，现在要将其划分为k个区间，要求从每个区间选出的m个最大值的和最大。问最大值以及怎样划分区间。
题解：
可以发现，最终选出来的数就是最大的那些数。
所以我们排下序，并且记录一下数原来的位置，贪心地选顺便标记一下位置就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+;
ll a[N];
int n,m,k;
int vis[N];
struct node{
ll v,pos;
bool operator < (const node &A)const{
return v<A.v;
}
}b[N];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++){
scanf("%I64d",&a[i]);
b[i]=node{a[i],i};
}
sort(b+,b+n+);
ll ans = ;
for(int i=n;i>=n-m*k+;i--){
ans+=b[i].v;
vis[b[i].pos]=;
}
int cnt = ;
int num=;
cout<<ans<<endl;
for(int i=;i<=n;i++){
if(vis[i]){
cnt++;
if(cnt==m){
num++;
if(num==k) break ;
cout<<i<<" ";
cnt=;
}
}
}
return ;
}
C. Trailing Loves (or L'oeufs?)
题意：
给出n和b，问n!在b进制下，后面有多少个连续的0？
其中1<=n<=1018,2<=b<=1012。
题解：
可以通过类比在十进制下的情况来进行思考。
根据唯一分解定理，假设b可以分解为p1q1 * p2q2 *...* pmqm，其中p1,p2...pm为质数。
同时，n!也可以分解成相应的形式：K * p1r1 * p2r2 *...* pmrm，K为一个常数，这个常数可能很大，但没必要去管。
那么，最终的答案即为min{ri/pi}，这个类比一下十进制就可以发现了。
这里面{pm},{qm}都比较好求，可以不用把素数给筛出来。主要是{rm}，这里的求法比较巧妙，详见代码吧：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,b; int main(){
cin>>n>>b;
ll ans = 2e18;
for(ll i=;i*i<=b;i++){
ll a=,c=;
if(b%i!=) continue ;
while(b%i==) b/=i,c++;
ll m=n;
while(m) a+=m/i,m/=i;
ans=min(ans,a/c);
}
if(b>){
ll a=;
while(n) a+=n/b,n/=b;
ans=min(ans,a);
}
cout<<ans<<endl;
return ;
}
D. Flood Fill
题意：
给出n个数，现在你可以任选一个数作为起点，然后每次将起点所在的连通块(连续的数相等即可成为连通块)变为一个数。问最少需要多少次操作，能让所有的数相等。
题解：
考虑动态规划，可以发现，每次的变化，要么连通块中的数都变为与左边相等，要么都变为与右边相等。
定义状态dp[l][r][0/1]:区间[l,r]内的数都与c[l/r]相等，我们可以不用管起点在哪，直接类似于区间dp那样进行转移就行了。
代码如下：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = ;
int n;
int c[N];
int dp[N][N][];
int main(){
cin>>n;
for(int i=;i<=n;i++) scanf("%d",&c[i]);
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
dp[i][j][]=dp[i][j][]=(i==j)?:INF;
}
}
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
int j=i+k-;
if(j>n) break ;
if(i<n){
dp[i][j][]=min(dp[i][j][],dp[i+][j][]+(c[i]!=c[i+]));
dp[i][j][]=min(dp[i][j][],dp[i+][j][]+(c[i]!=c[j]));
}
if(j>){
dp[i][j][]=min(dp[i][j][],dp[i][j-][]+(c[j]!=c[i]));
dp[i][j][]=min(dp[i][j][],dp[i][j-][]+(c[j]!=c[j-]));
}
}
}
int ans=min(dp[][n][],dp[][n][]);
cout<<ans;
return ;
}
E. Arithmetic Progression
题意：
交互题。题目要你猜出一个等差数列的首项以及公差，题目中会给出一共有多少项。
然后你有两种询问：1."> x"，即询问数列中是否有大于x的数，最后会返回0或1；2.“? i”，询问第i个位置的数，会返回第i个位置的数。
要求你用最多60次询问机会，得到等差数列的首项以及公差。
题解：
这也是一个比较有意思的交互题，我想的是直接二分求出数列中的最大最小值，但最后发现只能求出数列中的最大值。
做法就是先用不超过30次的询问机会找出最大值是什么，然后用剩余的机会随机询问数列中的某些项的值为多少(新技能mt19937 get)。
最后将得到的项排序，求出两两之间的差值的gcd就行了。因为这里差值都为公差d的倍数。
做法就是上面这样...但是这并不能保证100%正确，可能会存在差错，但几率会非常小，具体证明我也不会...
代码如下：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f;
using namespace std;
typedef long long ll;
const int N = 1e6+;
int n,Max,cnt,d;
mt19937 rnd(time(NULL));
int query1(int x){
printf("> %d\n",x);
fflush(stdout);
int ans;
scanf("%d",&ans);
return ans ;
}
void getMAX(){
int l=,r=1e9+,mid;
while(l<r){
mid=l+r>>;
cnt++;
if(query1(mid)) l=mid+;
else r=mid;
}
Max=l;
}
int query2(int pos){
printf("? %d\n",pos);fflush(stdout);
int ans;
scanf("%d",&ans);
return ans ;
}
void getD(){
vector <int> lst;
while(){
++cnt;
if(cnt>)break;
int now=query2(rnd()%n+);
lst.push_back(now);
}
sort(lst.begin(),lst.end());
lst.erase(unique(lst.begin(),lst.end()),lst.end());
if(lst.back()!=Max) lst.push_back(Max);
d=lst[]-lst[];
for(int i=;i<lst.size();i++){
d=__gcd(lst[i]-lst[i-],d);
}
}
int main(){
scanf("%d",&n);
getMAX();
getD();
int Min = Max-(n-)*d;
printf("! %d %d",Min,d);
return ;
}