layout: post
title: Codeforces Round 538 (Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
A.Got Any Grapes? (水题)
手冷把y写成x被fst了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int x,y,z,a,b,c;
cin>>x>>y>>z;
cin>>a>>b>>c;
if(a<x){
cout<<"NO"<<endl;exit(0);
}
a-=x;
b=a+b;
if(b<y){
cout<<"NO"<<endl;return 0;
}
b-=y;
c+=b;
if(c<z){
cout<<"NO"<<endl;return 0;
}
cout<<"YES"<<endl;
return 0;
}
B.Yet Another Array Partitioning Task (毒瘤？)
题意
让你分出k个区间，每个区间至少m个数，然后取每个区间的前m个最大值相加，使值最大
思路
本质就是求前m*k大的数,然后我们就可以把前m×k大的数求出来 然后记录坐标，然后连续m个分为一组即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{
ll value;
int id;
bool operator<(const node &a)const{
return value>a.value;
}
}my[maxn];
bool f[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
ll m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)cin>>my[i].value,my[i].id=i;
sort(my+1,my+1+n);
ll ans=0;
for(ll i=1;i<=m*k;i++){
ans+=my[i].value;f[my[i].id]=1;
}
cout<<ans<<endl;
for(int i=1,t=0,p=0;i<=n;i++){
if(f[i]){
t++;
if(t==m){
cout<<i<<" ";t=0;
p++;
if(p==k-1)return 0;
}
}
}
return 0;
}
C. Trailing Loves (or L'oeufs?) (质因子分解)
题意
求n!在b进制下末尾0的个数
思路
只要会十进制下求n！的就会这题了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll prime[maxn][2];
int tot;
ll hello(ll n,ll p){
ll ans=0;
while(n){
ans+=n/p;
n/=p;
}
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll n,m;
cin>>n>>m;
for(ll i=2;i<=sqrt(m);i++){
if(m%i==0){
prime[++tot][0]=i;
while(m%i==0){
m/=i;
prime[tot][1]++;
}
}
}
if(m!=1){
prime[++tot][0]=m;prime[tot][1]=1;
}
ll ans=inf;
for(int i=1;i<=tot;i++){
ans=min(ans,hello(n,prime[i][0])/prime[i][1]);
}
cout<<ans<<endl;
return 0;
}
D.Flood Fill (区间DP，本质求LCS，记忆化搜索)
题意
一个颜色序列，每个位置有一个颜色，选择一个起始位置，每次可以改变左右的一段颜色段（如果左边和右边颜色一样就一起改变），把整段变成一种颜色， 问最少操作多少次。n<=5000
思路
首先一整段颜色段肯定没用,我们可以缩点，简化题意
然后想到区间DP（石子合并） 但是石子合并是可以任意起点，而这题固定起点了，
所以可以把区间DP的n3变成n2了，我区间DP很差所以比赛只想出来记忆化搜索
记忆化搜索对付这种只有终点没有起点的题真的是屡试不爽
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int c[maxn];
int a[maxn];
int dp[5500][5500];
int dfs(int l,int r){
if(dp[l][r]!=-1)return dp[l][r];
int ans=0;
if(l==r)return 0;
if(a[l]==a[r])ans=dfs(l+1,r-1)+1;
else ans=min(dfs(l+1,r),dfs(l,r-1))+1;
dp[l][r]=ans;
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
}
a[1]=c[1];int cnt=1;
for(int i=2;i<=n;i++){
if(a[cnt]!=c[i]){
a[++cnt]=c[i];
}
}
/* for(int i=1;i<=cnt;i++){
cout<<a[i]<<" ";
}*/
memset(dp,-1,sizeof(dp));
cout<<dfs(1,cnt)<<endl;
return 0;
}
E.Arithmetic Progression (mt19937+交互题+二分找最大值+随机数取GCD)
题意
你电脑中有一个等差数列,你有两种循环
1.问这个数列的第x项的值
2.问是否有一个项的值比X大
让你在60次内找出这个等差数列的首项和公差
思路
很明显可以在32次内得出最大值，然后就是求公差了，
我们既然有了最大值，那我们就可以求出任意一项和最大值的差值肯定是公差的倍数
然后我们就直接对这些差值求GCD
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,k,m,ti=60;
mt19937_64 lwt(time(0));
int ask(int x){
cout<<"? "<<x<<endl;
cin>>k;
return k;
}
int ask2(int x){
cout<<"> "<<x<<endl;
cin>>k;
ti--;
return k;
}
int find_max(){
int l=-1,r=1e9;
int ans;
while(r-l>=0){
int mid=(l+r)/2;
if(ask2(mid))l=mid+1;else r=mid-1,ans=mid;
}
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n;
m=find_max();
int d=0;
for(int i=1;i<=ti;i++){
int id=lwt()%n+1;
int x=ask(id);
if(x!=m)d=__gcd(d,m-x);
}
cout<<"! "<<m-(n-1)*d<<" "<<d<<endl;
return 0;
}
F.Please, another Queries on Array? (线段树区间乘+欧拉函数+bitset)
题意
两个操作
1.把一个区间乘上一个值X
2.求一个区间的欧拉函数
思路
看到区间乘法很容易想到线段树
那么欧拉函数怎么求，很明显欧拉函数和素因子个数有关
发现每个x都小于等于300 打表发现300内的素因子只有62个
然后就是怎么记录这几个素因子的问题了，你可以用LL的位数或者bitset记录
（或者用数组？那可能会超时吧）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=4e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,q;
bool isprime[500];
ll prime[500];
ll inv[500];
ll Pow(ll a,ll i){
ll s=1LL;
while(i){
if(i&1)s=1LL*s*a%mod;
a=1LL*a*a%mod;
i>>=1;
}
return s;
}
int init(int n){
int p=0;
for(int i=0;i<=n;i++)isprime[i]=true;
isprime[0]=isprime[1]=false;
for(int i=2;i<=n;i++){
if(isprime[i])prime[p++]=i*1LL;
for(int j=0;j<p;j++){
if(prime[j]*i>n)break;
isprime[prime[j]*i]=false;
if(i%prime[j]==0)break;
}
}
return p;
}
ll a[maxn];
struct segtree{
bitset<62>has[maxn<<2];
bitset<62>laz[maxn<<2];
ll ans[maxn<<2];
ll lazy[maxn<<2];
void pushup(int o){
ans[o]=1LL*ans[o<<1]*ans[o<<1|1]%mod;
has[o]=has[o<<1]|has[o<<1|1];
}
void pushdown1(int o,int l,int r){
if(lazy[o]==1)return;
int mid=(l+r)/2,len1=mid-l+1,len2=r-mid;
lazy[o<<1]=1LL*lazy[o<<1]*lazy[o]%mod;
ans[o<<1]=1LL*ans[o<<1]*Pow(lazy[o],len1)%mod;
lazy[o<<1|1]=1LL*lazy[o<<1|1]*lazy[o]%mod;
ans[o<<1|1]=1LL*ans[o<<1|1]*Pow(lazy[o],len2)%mod;
lazy[o]=1;
}
void pushdown2(int o){
laz[o<<1]|=laz[o];
has[o<<1]|=laz[o];
laz[o<<1|1]|=laz[o];
has[o<<1|1]|=laz[o];
laz[o].reset();
}
void build(int o,int l,int r){
lazy[o]=1;has[o].reset();laz[o].reset();
if(l==r){
ans[o]=a[l];
for(int i=0;i<62;i++)if(a[l]%prime[i]==0)has[o].set(i);
return;
}
int mid=(l+r)/2;
build(o<<1,l,mid);build(o<<1|1,mid+1,r);
pushup(o);
}
void update(int o,int l,int r,int ql,int qr,ll v,bitset<62> bit){
if(ql<=l&&r<=qr){
lazy[o]=1LL*lazy[o]*v%mod;
ans[o]=1LL*ans[o]*Pow(v,r-l+1)%mod;
laz[o]|=bit;has[o]|=bit;
return;
}
pushdown1(o,l,r);
pushdown2(o);
int mid=(l+r)/2;
if(ql<=mid)update(o<<1,l,mid,ql,qr,v,bit);
if(qr>mid)update(o<<1|1,mid+1,r,ql,qr,v,bit);
pushup(o);
}
ll query1(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return ans[o];
pushdown1(o,l,r);
int mid=(l+r)/2;
ll ans=1;
if(ql<=mid)ans=ans*query1(o<<1,l,mid,ql,qr)%mod;
if(qr>mid)ans=ans*query1(o<<1|1,mid+1,r,ql,qr)%mod;
return ans;
}
bitset<62> query2(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return has[o];
pushdown2(o);
int mid=(l+r)/2;
bitset<62> ans;ans.reset();
if(ql<=mid)ans|=query2(o<<1,l,mid,ql,qr);
if(qr>mid)ans|=query2(o<<1|1,mid+1,r,ql,qr);
return ans;
}
}seg;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int p=init(300);
for(int i=0;i<p;i++)inv[i]=Pow(1LL*prime[i],mod-2);
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
seg.build(1,1,n);
while(q--){
int l,r;
ll x;char str[10];
cin>>str;
if(str[0]=='T'){
cin>>l>>r;
ll res=seg.query1(1,1,n,l,r);
bitset<62> bit=seg.query2(1,1,n,l,r);
for(int j=0;j<62;j++)
if(bit[j])res=(1LL*res*inv[j]%mod*(prime[j]-1+mod)%mod)%mod;
cout<<res<<endl;
}
else{
cin>>l>>r>>x;
bitset<62>bit;bit.reset();
for(int j=0;j<62;j++)if(x%prime[j]==0)bit.set(j);
seg.update(1,1,n,l,r,x,bit);
}
}
return 0;
}