AtCoder Beginner Contest 359

目录

A - A Healthy Breakfast

B - Vertical Reading 

C - Move It

D - Ghost Ants

E - Random Swaps of Balls

F.暂无

G - Suitable Edit for LIS

---

A - A Healthy Breakfast

就三个字母直接模拟，只有xRM,RMx,RxM三种

void solve(){string a; cin>>a;if(a.find("RM")!=-1 or (a[0]=='R' and a[2]=='M')) cout << "Yes" << endl;else cout << "No" << endl;return ;
}

B - Vertical Reading 

读懂题目直接按照题目模拟即可，数据范围较小

void solve(){string a,b; cin>>a>>b;n=a.size(),a=' '+a;for(int i=1;i<a.size()-1;i++){vector<string> s;int j = 1;while(j<a.size()){string now;int t = j+i;while(j<a.size() and j<t) now+=a[j],j++;s.push_back(now);}for(int k=1;k<=i;k++){string ans;for(auto&v:s) if(v.size()>=k) ans += v[k-1]; if(ans==b){cout << "Yes" << endl;return ;}}}cout << "No" << endl;return ;
}

C - Move It

明显的一个地方放了多于一个的话需要移动肯定是移动最小的size-1个即可

vector<int> g[N];
int a[N],w[N];void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>w[i];for(int i=1;i<=n;i++){g[a[i]].push_back(w[i]);}   LL ans = 0; for(int i=1;i<=n;i++){sort(g[i].begin(),g[i].end(),greater<int>());if(!g[i].empty()){for(auto&v:g[i]) ans+=v;ans -= g[i][0];}}cout << ans << endl;return ;
}

D - Ghost Ants

左边的可以遇到右边的右边可以遇到左边的，可以考虑固定一边，如固定朝右边走的，那么对于每一个左边的点x可以碰到的点范围就是[x-2*m,x]，观察数据范围使用离散化+前缀和即可

LL w[N],a[N];void solve(){cin>>n>>m;string s; cin>>s; s=' '+s;for(int i=1;i<=n;i++){cin>>a[i];if(s[i]=='0') v.push_back(a[i]-2*m);v.push_back(a[i]);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());auto find = [&](LL x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;};for(int i=1;i<=n;i++){if(s[i]=='1'){w[find(a[i])]++;}}for(int i=1;i<=v.size()+5;i++) w[i] += w[i-1];LL ans = 0;for(int i=1;i<=n;i++){if(s[i]=='0'){ans += w[find(a[i])]-w[find(a[i]-2*m)-1];}}cout << ans << endl;return ;
}

E - Random Swaps of Balls

交换m次,找找性质，我们可以发现除了第一个位置，后面每一个位置的概率是一样的，因为是随机抽取，我们计算概率即可，每一次都是n^2次，然后1.黑黑:1种 2.白白（n-1)^2，剩下的就是黑白，随机的给除了黑点的其他点，然后一个g1表示第一个点概率，g2表示其他点的概率，然后dp即可

LL t,n,m;
LL qmi(LL a,LL b,LL p){LL res = 1;while(b){if(b&1) res=res*a%p;b>>=1;a=a*a%p;}return res;
}
void solve(){cin>>n>>m;LL inv = qmi(n*n%mod,mod-2,mod);LL inv2 = qmi(n-1,mod-2,mod);LL g1 = 1, g2 = 0;if(n==1){cout << 1 << endl;return ;}for(int i=1;i<=m;i++){LL p1 = g1,p2 = g2;LL t1 = (n*n%mod-2*n+2)%mod,t2 =(n-1)*2%mod;g1 = p1*t1%mod*inv%mod + p2*t2%mod*inv%mod;g2 = ((p1+(n - 2)*p2 % mod) % mod * 2 % mod * inv % mod + p2 * ((n * n % mod - n * 2 % mod + 2) % mod + mod) % mod * inv % mod) % mod;g1 %= mod;g2 %= mod;}LL ans = g1 + ((1+n)*n/2-1)%mod*g2%mod;ans = (ans%mod+mod)%mod;cout << ans << endl;return ;
}

F.暂无

G - Suitable Edit for LIS

明显的就是修改一个数的lis，直接维护正序的上升序列，逆序的下降序列，然后就是维护每一个点这个时候的序列长度和最大值或者最小值

注意第一个点的时候不能和a0结合

int a[N];
vector<int> pre,suf;
int plen[N],slen[N];
int pm[N],sm[N];void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){if(pre.empty() or a[i]>pre.back()) pre.push_back(a[i]);else pre[lower_bound(pre.begin(),pre.end(),a[i])-pre.begin()]=a[i];plen[i]=pre.size();pm[i]=pre.back();}	   for(int i=n;i>=1;i--){if(suf.empty() or a[i]<suf.back()) suf.push_back(a[i]);else suf[lower_bound(suf.begin(),suf.end(),a[i],greater<int>())-suf.begin()]=a[i];slen[i]=suf.size();sm[i]=suf.back();} int ans = pre.size();pm[0] = -2e9;for(int i=1;i<=n;i++){ans = max(ans,slen[i+1]+1);ans = max(ans,plen[i-1]+1);if(pm[i-1]+1<sm[i+1]) ans = max(ans,plen[i-1]+slen[i+1]+1);}cout << ans << endl;return ;
}