Idea:Yugandhar_Master
Let $$$count$$$ be the number of $$$1's$$$ in the given binary string $$$S$$$.
Note that if we perform atleast one operation there will be atleast $$$k$$$ $$$0's$$$. So it is always optimal to get minimum $$$k$$$ $$$0's$$$ once we start doing operations.
Let $$$S$$$ = $$$s_1s_2s_3s_4s_5s_6s_7s_8s_9s_{10}$$$ and $$$k = 3$$$
we can do operations in the following way to get $$$k$$$ $$$0's$$$.
Choose i=3, $$$S$$$ = $$$111000s_7s_8s_9s_{10}$$$
Choose i=6, $$$S$$$ = $$$111111000s_{10}$$$
Choose i=7, $$$S$$$ = $$$1111111000$$$.
By this way we can always get minimum of $$$k$$$ $$$0's$$$ once we start doing operations.
Hence, the answer to the problem is maximum($$$count$$$ , $$$n-k$$$).
Time Complexity : $$$O(n)$$$
solution
code(C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
string s;
cin>>s;
int ans=count(s.begin(),s.end(),'1');
ans=max(ans,n-k);
cout<<ans<<"\n";
}
}
Idea:Yugandhar_Master
solution
code(C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
string s;
cin>>s;
ll ind1=-1,ind2=-1;
for(ll i=0;i<n;i++){
if(s[i]=='0') ind2=i;
}
for(ll i=n-1;i>=0;i--){
if(s[i]=='0') ind1=i;
}
ll cnt=count(s.begin(),s.end(),'1');
for(ll k=1;k<=(n/2);k++){
if(cnt>=(n-k)) cout<<"0 ";
else{
ll l=ind1,r=ind2;
r-=k;
cout<<(r-l+k)/k<<" ";
}
}
cout<<"\n";
}
}
C1: Yet Another Nim Game (Constructive version)
Idea:Yugandhar_Master
solution
code(C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
for(ll i=0;i<n;i++) cout<<i+1<<" ";
cout<<"\n";
}
}
C2: Yet Another Nim Game(Counting version)
Idea:Yugandhar_Master
solution
code(C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
ll mod=1e9+7;
const ll N=3e5+11;
vector<ll> v;
int main(){
fast;
v.resize(N);
v[1]=1;
v[2]=2;
ll val=3,diff=3;
for(ll i=3;i<N;i+=2){
v[i]=(v[i-1]*(val%mod))%mod;
v[i+1]=(v[i]*2)%mod;
val+=diff;
diff++;
}
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
cout<<v[n]<<"\n";
}
}
Idea:Yugandhar_Master
solution
code(C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
ll mod=1e9+7;
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll m,n;
cin>>m>>n;
string s;
cin>>s;
if(m>n) cout<<"0\n";
else{
vector<ll> dp(n+1);
dp[0]=1;
for(ll i=0;i<n;i++){
vector<ll> ndp(n+1);
for(ll j=0;j<=i;j++){
ndp[j+1]=(ndp[j+1]+dp[j])%mod;
if(j>0) ndp[j-1]=(ndp[j-1]+(26*dp[j])%mod)%mod;
else ndp[j]=(ndp[j]+dp[j])%mod;
}
dp=ndp;
}
cout<<dp[m]<<"\n";
}
}
}
Idea:Yugandhar_Master
solution
code(C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
//#define int long long
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=1000000001;
const int B=3000;//100;
int T,n,q;
int a[N],bnum[N];
/*
struct cmp1 //自定义升序
{
bool operator()(pair<int,int> v1,pair<int,int> v2)
{
return v1.first < v2.first;
}
};
struct cmp2 //自定义降序
{
bool operator()(pair<int,int> v1,pair<int,int> v2)
{
return v1.first > v2.first;
}
};
*/
struct block
{
set<pair<int,int> > S;
unordered_map<int,int> cnt;
}blk[N];
void init()
{
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n+4;i++)
{
blk[i].S.clear();
blk[i].cnt.clear();
}
for(int i=1;i<=n;i++)
{
bnum[i]=i/B+1;
blk[bnum[i]].S.insert(make_pair(a[i],i));
blk[bnum[i]].cnt[a[i]]++;
}
}
void solve()
{
for(int i=1;i<=q;i++)
{
int t;
cin>>t;
if(t==1)
{
int l,r,x,mxl=-INF,cl=0,mnr=INF,cr=0; //l:<x,r:>=x
cin>>l>>r>>x;
if(bnum[l]==bnum[r])
{
for(int i=l;i<=r;i++)
{
if(a[i]<x)
{
if(a[i]>mxl) mxl=a[i],cl=1;
else if(a[i]==mxl) cl++;
}
else
{
if(a[i]<mnr) mnr=a[i],cr=1;
else if(a[i]==mnr) cr++;
}
}
}
else
{
for(int i=l;bnum[i]==bnum[l];i++)
{
if(a[i]<x)
{
if(a[i]>mxl) mxl=a[i],cl=1;
else if(a[i]==mxl) cl++;
}
else
{
if(a[i]<mnr) mnr=a[i],cr=1;
else if(a[i]==mnr) cr++;
}
}
for(int i=r;bnum[i]==bnum[r];i--)
{
if(a[i]<x)
{
if(a[i]>mxl) mxl=a[i],cl=1;
else if(a[i]==mxl) cl++;
}
else
{
if(a[i]<mnr) mnr=a[i],cr=1;
else if(a[i]==mnr) cr++;
}
}
for(int i=bnum[l]+1;i<=bnum[r]-1;i++)
{
set<pair<int,int> >::iterator it=blk[i].S.lower_bound(make_pair(x,0));
if(it!=blk[i].S.end())
{
if(it->first<mnr) mnr=it->first,cr=blk[i].cnt[it->first];
else if(it->first==mnr) cr+=blk[i].cnt[it->first];
}
if(it==blk[i].S.begin()) continue;
it--;
if(it->first>mxl) mxl=it->first,cl=blk[i].cnt[it->first];
else if(it->first==mxl) cl+=blk[i].cnt[it->first];
}
}
//
//cout<<"mxl="<<mxl<<" mnr="<<mnr<<'\n';
//
if(mxl==-INF) cout<<cr<<'\n';
else if(mnr==INF) cout<<cl<<'\n';
else if(x-mxl==mnr-x) cout<<cl+cr<<'\n';
else if(x-mxl<mnr-x) cout<<cl<<'\n';
else cout<<cr<<'\n';
}
else
{
int p,v;
cin>>p>>v;
blk[bnum[p]].S.erase(make_pair(a[p],p));
blk[bnum[p]].cnt[a[p]]--;
a[p]=v;
blk[bnum[p]].S.insert(make_pair(a[p],p));
blk[bnum[p]].cnt[a[p]]++;
}
}
}
//-------------------------------------------------------
void gen_data()
{
srand(time(NULL));
}
int bruteforce()
{
return 0;
}
//-------------------------------------------------------
signed main()
{
fastio;
cin>>T;
while(T--)
{
init();
solve();
/*
//Stress Test
gen_data();
auto ans1=solve(),ans2=bruteforce();
if(ans1==ans2) printf("OK!\n");
else
{
//Output Data
}
*/
}
return 0;
}
Idea:Yugandhar_Master
solution
code(C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
ll n;
vector<ll> a;
vector<vector<ll>> adj;
vector<pair<ll,ll>> dfs(ll x, ll p){
vector<pair<ll,ll>> dp;
dp.push_back({0,1e18});
for(auto i:adj[x]){
if(i!=p){
vector<pair<ll,ll>> ndp=dfs(i,x);
ll n1=(ll)ndp.size();
ndp.push_back({1e18,1e18});
for(ll j=n1-1;j>=0;j--){
if(ndp[j].first<1e18 || ndp[j].second<0){
ndp[j+1].first=min((ll)0,ndp[j+1].first);
}
}
ll n2=(ll)dp.size()-1;
vector<pair<ll,ll>> udp(n1+n2+1,{1e18,1e18});
for(ll j=0;j<=n2;j++){
for(ll k=0;k<=n1;k++){
udp[j+k].first=min(udp[j+k].first,dp[j].first+ndp[k].first);
udp[j+k].second=min(udp[j+k].second,dp[j].first+ndp[k].second);
udp[j+k].second=min(udp[j+k].second,dp[j].second+ndp[k].first);
udp[j+k].second=min(udp[j+k].second,dp[j].second+ndp[k].second);
}
}
dp=udp;
}
}
ll n2=(ll)dp.size()-1;
vector<pair<ll,ll>> udp(n2+1);
for(ll i=0;i<=n2;i++){
if(a[x]>0){
udp[i].first=dp[i].first+a[x];
udp[i].second=dp[i].second+a[x];
}
else{
udp[i].first=1e18;
udp[i].second=min(dp[i].first,dp[i].second)+a[x];
}
}
return udp;
}
int main(){
fast;
ll t;
t=1;
while(t--){
cin>>n;
a.clear();
a.resize(n);
for(ll i=0;i<n;i++) cin>>a[i];
string s;
cin>>s;
for(ll i=0;i<n;i++){
if(s[i]=='1') a[i]=-a[i];
}
adj.clear();
adj.resize(n);
for(ll i=0;i<n-1;i++){
ll u,v;
cin>>u>>v;
u--;
v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<pair<ll,ll>> dp=dfs(0,-1);
for(ll i=0;i<n;i++){
if(dp[i].first<1e18 || dp[i].second<0){
cout<<i;
break;
}
}
}
}
