Znzryb's Blog

CF-1023-C. Maximum Subarray Sum

Posted on 2025-05-06 Edited on 2026-04-06

思路讲解

赛时差一点想到AC，主要是needVal为负数的情况没有想到（减着减着变负数了）

其实只改一个数就行，其他数全部赋为-INF。

AC代码

https://codeforces.com/contest/2107/submission/318579760

源代码

// Problem: C. Maximum Subarray Sum
// Contest: Codeforces - Codeforces Round 1023 (Div. 2)
// URL: https://codeforces.com/contest/2107/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)-3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];
char S[MAXN];
// ll preA[MAXN];
ll mxA[MAXN],smxA[MAXN];//sumA[MAXN];

inline void solve(){
	cin>>N>>K;
	FOR(i,0,N+5){
		S[i]='0';
		A[i]=0;
		smxA[i]=0;
		mxA[i]=0;
		// sumA[i]=0;
	}
	FOR(i,1,N){
		cin>>S[i];
	}
	ll pos=0;
	FOR(i,1,N){
		cin>>A[i];
		if(S[i]=='0') A[i]=-INF,pos=i;
		// sumA[i]=sumA[i-1]+A[i];
	}
	// preA[0]=0;
	ll maxA=-INF;
	FOR(i,1,N){
		if(S[i]=='1'){
			mxA[i]=mxA[i-1]+A[i];
			maxA=max(maxA,mxA[i]);
			if(mxA[i]<0){
				mxA[i]=0;
			}
		}else{
			mxA[i]=0;
		}
	}
	smxA[N+1]=0;
	ROF(i,N,1){
		if(S[i]=='1'){
			smxA[i]=smxA[i+1]+A[i];
			maxA=max(maxA,smxA[i]);
			if(smxA[i]<0){
				smxA[i]=0;
			}
		}else{
			smxA[i]=0;
		}
	}
	if(maxA>K){
		cout<<"No\n";
		return;
	}else if(maxA==K){
		cout<<"Yes\n";
		FOR(i,1,N){
			if(S[i]=='0') A[i]=-INF;
			cout<<A[i]<<" ";
		}
		cout<<"\n";
		return;
	}
	A[pos]=K-smxA[pos+1]-mxA[pos-1];
	ll check=-INF;
	mxA[0]=0;
	FOR(i,1,N){
		mxA[i]=mxA[i-1]+A[i];
		check=max(check,mxA[i]);
		if(mxA[i]<0){
			mxA[i]=0;
		}
	}
#ifdef LOCAL
    cerr << "T:"<<T << '\n';
    cerr<<"check:"<<check<<" K:"<<K<<"\n";
    FOR(i,1,N){
    	cerr<<A[i]<<" ";
    }
    cerr<<"\n";
#endif
	if(check==K){
		cout<<"Yes\n";
		FOR(i,1,N){
			cout<<A[i]<<" ";
		}
		cout<<"\n";
	}else{
		cout<<"No\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2107/submission/318579760
*/

心路历程（WA，TLE，MLE……）

CF-1019-D. Local Construction

Posted on 2025-05-05 Edited on 2026-04-06

思路讲解

// 要求你构造一个数组，符合A中的要求，如果A[1]=1，那么就说明这个
// 构造数组中的这个元素需要于第一次操作时去除。A[2]=-1，说明第二个元素被剩下了。
// 奇数次操作只留下局部最小值，偶数次操作只留下局部最大值（严格）。

AC代码

https://codeforces.com/contest/2103/submission/318747498

源代码

// Problem: D. Local Construction
// Contest: Codeforces - Codeforces Round 1019 (Div. 2)
// URL: https://codeforces.com/contest/2103/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];
vector<ll> g[MAXN];
ll pos_=0;

inline void solve(){
	cin>>N;
	pos_=0;
	FOR(i,1,N) g[i].clear();
	FOR(i,1,N){
		cin>>A[i];
		if(A[i]==-1) pos_=i;
		g[A[i]].pb(i);
	}
	ll Low=1,Up=N;
	FOR(i,1,ceil(log2(N)) ){
		ll bp=INF;
		FOR(j,0,SZ(g[i])-1){
			ll node=g[i][j];
			if(node>pos_){
				bp=j;
				break;
			}
			if(i%2==1){
				A[node]=Up--;
			}else{
				A[node]=Low++;
			}
		}
		ROF(j,SZ(g[i])-1,bp){
			ll node=g[i][j];
			if(i%2==1){
				A[node]=Up--;
			}else{
				A[node]=Low++;
			}
		}
	}
	A[pos_]=Low++;
	FOR(i,1,N){
		cout<<A[i]<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2103/submission/318747498
*/

心路历程（WA，TLE，MLE……）

CF-1019-C. Median Splits

Posted on 2025-05-05 Edited on 2026-04-06

思路讲解

首先，注意到，这道题目我们是不在意这个段的中位数到底是几的，我们只在意这个段的中位数是 $>K$ 还是 $≤K$ 。因此我们只需要通过记录 $≤K$ 的数的数量，就可以知道符不符合要求。

那么前缀和后缀可以用这种方法比较简便的求得，那么中间的怎么办呢？

以前缀为例，在处理的时候，直接判断该位置和最近的前缀合法位置能不能组合为两个合法段。（贪心地，我们认为总是和最近的段组合为两个合法段）

vector<ll> pres;
	FOR(i,1,N){
		preA[i]=preA[i-1];
		if(A[i]<=K){
			++preA[i];
		}
		if(!pres.empty()){
			// 将这个点和之前合法的前缀组合一下，看看呢能不能凑出两个合法段
			ll len=i-pres.back();
			ll num=preA[i]-preA[pres.back()];
			if(num>=ceil(len/2.0)){
				cout<<"YES\n";
				return;
			}
		}
		if(preA[i]>=ceil(i/2.0l)){
			pres.pb(i);
		}
	}

AC代码

https://codeforces.com/contest/2103/submission/318394685

源代码

// Problem: C. Median Splits
// Contest: Codeforces - Codeforces Round 1019 (Div. 2)
// URL: https://codeforces.com/contest/2103/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];
// 比K小的计数（前序，后序）
ll sufA[MAXN],preA[MAXN];

inline void solve(){
	cin>>N>>K;
	// vector<ll> posK;
	FOR(i,1,N){
		cin>>A[i];
		// if(A[i]<=K){
			// posK.pb(i);
		// }
	}
	preA[0]=0,sufA[N+1]=0;
	vector<ll> pres;
	FOR(i,1,N){
		preA[i]=preA[i-1];
		if(A[i]<=K){
			++preA[i];
		}
		if(!pres.empty()){
			ll len=i-pres.back();
			ll num=preA[i]-preA[pres.back()];
			if(num>=ceil(len/2.0)){
				cout<<"YES\n";
				return;
			}
		}
		if(preA[i]>=ceil(i/2.0l)){
			pres.pb(i);
		}
	}
	vector<ll> sufs;
	ROF(i,N,1){
		sufA[i]=sufA[i+1];
		if(A[i]<=K){
			++sufA[i];
		}
		if(!sufs.empty()){
			ll len=sufs.back()-i;
			ll num=sufA[i]-sufA[sufs.back()];
			if(num>=ceil(len/2.0)){
				cout<<"YES\n";
				return;
			}
		}
		if(sufA[i]>=ceil((N-i+1)/2.0l)){
			sufs.pb(i);
		}
	}
	if(!pres.empty()){
		if(!sufs.empty()){
			if(sufs.front()-pres.front()>=2){
				cout<<"YES\n";
				return;
			}
		}
	}
	// if(!pres.empty()){
// 		
	// }
	cout<<"NO\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2103/submission/318394685
*/

心路历程（WA，TLE，MLE……）

ABC-404-D - Goin' to the Zoo

Posted on 2025-05-03 Edited on 2026-04-06

思路讲解

jiangly的代码利用了状压dp的思想，我汲取一下思想，来写一波

AC代码

https://atcoder.jp/contests/abc404/submissions/65496213

源代码

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e3)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,Cost[MAXN];
vector<ll> g[MAXN];
ll pw[20];

inline void solve(){
	cin>>N>>M;	// M个动物，N个动物园
	FOR(i,1,N){
		cin>>Cost[i];
	}
	FOR(i,1,M){
		cin>>K;
		FOR(j,1,K){
			ll u;
			cin>>u;
			g[u].pb(i);
		}
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<"zoo:"<<i<<" animial:";
    	// FOR(j,0,SZ(g[i])-1){
    		// cerr<<g[i][j]<<" ";
    	// }
    	// cerr<<"\n";
    // }
// #endif
	pw[0]=1;
	FOR(i,1,N){
		pw[i]=pw[i-1]*3;
	}
	ll ans=INF;
	FOR(i,0,pw[N]){
		ll opi=i,idx=1,ct=0;
		vector<ll> Cnt(M,0);
// #ifdef LOCAL
    // cerr <<"status:"<<i <<" rem:";
// #endif
		while(opi){
			ll rem=opi%3;
			if(rem!=0){
				ct+=Cost[idx]*rem;
				FOR(j,0,SZ(g[idx])-1){
					Cnt[g[idx][j]-1]+=rem;
				}
			}
			++idx;
// #ifdef LOCAL
    // cerr << rem;
// #endif
			opi/=3;
		}
// #ifdef LOCAL
    // cerr  << '\n';
// #endif
// #ifdef LOCAL
	// cerr<<"Cnt:";
	// FOR(i,0,M-1){
		// cerr<<Cnt[i]<<" ";
	// }
	// cerr<<"\n";
// #endif
		if(*min_element(all(Cnt))>=2){
			ans=min(ct,ans);
// #ifdef LOCAL
    // cerr << "OK" << '\n';
// #endif
		}
// #ifdef LOCAL
    // cerr<<"status:"<<i << "Cost:"<<ct << '\n';
// #endif
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

ABC-404-C - Cycle Graph?

Posted on 2025-05-03 Edited on 2026-04-06

思路讲解

只要大家入度都为2就行了。

但是注意，上面这句话成立的条件是在联通图下。

AC代码

https://atcoder.jp/contests/abc404/submissions/65464102

源代码

// Problem: C - Cycle Graph?
// Contest: AtCoder - AtCoder Beginner Contest 404
// URL: https://atcoder.jp/contests/abc404/tasks/abc404_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T;
vector<ll> g[MAXN];
struct DSU {  // refer jiangly
  vector<int> fa, siz;
  int ln;
  DSU(int n) {
    ln = n;
    fa.resize(ln + 5, 0), siz.resize(ln + 5, 0);
    FOR(i, 1, n) {
      fa[i] = i;
      siz[i] = 1;
    }
  }
  int find(int x) {
    while (fa[x] != x) {
      x = fa[x];
      fa[x] = fa[fa[x]];
    }
    return x;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    siz[x] += siz[y];
    fa[y] = x;
    return true;
  }
  int size(int x) { return siz[find(x)]; }
  int countFa() {
    int res = 0;
    FOR(i, 1, ln) {
      if (fa[i] == i) ++res;
    }
    return res;
  }
};

inline void solve(){
	cin>>N>>M;
	// vector<arr> ls;
	DSU dsu(N);
	FOR(i,1,M){
		ll u,v;
		cin>>u>>v;
		if(u>v) swap(u,v);
		g[u].pb(v);
		g[v].pb(u);
		dsu.merge(u,v);
	}
	if(dsu.countFa()!=1){
		cout<<"No\n";
		return;
	}
	if(M==N){
		// sort(all(ls));
		// if(ls[0][0]==1 && ls[0][1]==2){
			// if(ls[1][0]==1 && ls[1][1]==N){
				// FOR(i,2,SZ(ls)-2){
					// if(ls[i][0]==i && ls[i][1]==i+1){
// 						
					// }else{
						// cout<<"No\n";
						// return;
					// }
				// }
				// cout<<"Yes\n";
				// return;
			// }
		// }
		FOR(i,1,N){
			if(SZ(g[i])!=2){
				cout<<"No\n";
				return;
			}
		}
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
	
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/