2023-2024 ICPC, NERC, Northern Eurasia Onsite镜像赛瞎写-526互联

晚饭吃的卷饼，好吃。

L

题意

有 \(n\) 个字符，L 代表面包，O 代表洋葱，你和一个朋友需要分这些食物，需满足以下要求：

每个人至少有一件物品。
你从最左边向右边连续取，剩下的都是那个朋友的。
你们的面包数和洋葱数不能相同。

输出一个方案你分得的物品数，如无解则输出 \(-1\)。

做法

感觉是最简单的，\(n\) 居然在 \(2e2\) 范围内。

如果面包数 \(L\) 是偶数，\(loc_i\) 代表第 \(i\) 个面包的位置，则区间 \(\left[loc_{\frac{L}{2}},loc_{\frac{L}{2}+1}\right]\) 中的数不能选择。
奇数不用考虑。

洋葱同理。

然后看一下这个两个区间的并的补是否是空集，输出就可以了。

#include<bits/stdc++.h>
//#define tests 1
//#define open freopen(".in","r",stdin);freopen(".out","w",stdout);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=2e2+10;
int n,L,O,locl[MAXN],loco[MAXN];
char item[MAXN];
bool flag[MAXN];
int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
	return x;
}
namespace sol{
	void solve(){
		n=read();
		do{
			item[1]=getchar();
		}while(item[1]!='L'&&item[1]!='O');
		if(item[1]=='L')locl[++L]=1;
		else loco[++O]=1;
		for(int i=2;i<=n;++i){
			item[i]=getchar();
			if(item[i]=='L')locl[++L]=i;
			else loco[++O]=i;
		}
		if((~L)&1){
//			cerr<<"debug1\n";
//			cerr<<(L>>1)<<' '<<(L>>1|1)<<'\n';
			for(int i=locl[L>>1];i<locl[(L>>1)+1];++i){
				flag[i]=1;
			}
		}
		if((~O)&1){
//			cerr<<"debug2\n";
			for(int i=loco[O>>1];i<loco[(O>>1)+1];++i){
				flag[i]=1;
			}
		}
		bool ansflag=false;
		for(int i=1;i<n;++i){
			if(!flag[i]){
				printf("%d\n",i);
				ansflag=true;
				break;
			}
		}
		if(!ansflag)puts("-1");
	}
}
int main(){
	sol::solve();
	return 0;
}

A

做这题的时候被迫变量名改成了同学名。

题意

给定 \(x\)，\(k\)，有 \(k\) 个序列，每个序列在开头的数 \(n_i\) 代表接下来这个序列有多少个数，你可以对每个序列从开头的数（不含 \(n_i\)）向后面与 \(x\) 做加操作，期间 \(x\) 不能为 \(0\)，可以先加其他序列的数再回到某序列上继续加。

做法

贪心题。

很明显如果有一段正数需要把正数全加上，那么序列就会被分成前导负数后正数的好几段，相当于 \(x\) 多大的前提下将 \(x\) 加上多少。

直接分出的段可能有负的，所以需要把前面的负的段和后面正的段合成一段来看。
注意这个代价是取左起子序列最小值。

~~将其代价排序后累加至不能相加即可。~~
不能够直接进行排序，因为需要将前面所有的数都加完后才能加后面的数，正确的做法应该是一开始取开头的一段入堆，然后不断取出累加，同序列中后面的一段入堆，直到不能相加为止。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXK=1e5+10;
int k,n;
ll x,tsum,tdaijia;
vector<pair<ll,ll> > a[MAXK];
priority_queue<pair<pair<ll,ll>,pair<int,int> > > q;/*小根堆，所以第一个元素负数*/
int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
	return f*x;
}
namespace sol{
	void solve(){
		x=read();k=read();
		for(int i=1;i<=k;++i){
			n=read();
			ll daiji=0,su=0;
			bool pos=false;
			for(int j=1,temp;j<=n;++j){
				temp=read(); 
				if(temp<=0){
					if(pos){
						pos=false;
						if(su<=0){
							su+=temp;
							daiji=min(su,daiji);
						}else{
							a[i].push_back(make_pair(daiji,su));
							daiji=su=temp;
						}
					}else{
						su+=temp;
						daiji=min(daiji,su);
					}
				}else{
					su+=temp;
					pos=true;
				}
			}
			if(pos&&su>0){
				a[i].push_back(make_pair(daiji,su));
			}
			if(a[i].size())q.push(make_pair(a[i][0],make_pair(i,0)));
		}
		while(!q.empty()&&x+q.top().first.first>=0){
			pair<pair<ll,ll>,pair<int,int> >temp=q.top();q.pop();
			x+=temp.first.second;
			if(temp.second.second+1<a[temp.second.first].size()){
				q.push(make_pair(a[temp.second.first][temp.second.second+1],make_pair(temp.second.first,temp.second.second+1)));
			}
		}
		printf("%lld\n",x);
	}
}
int main(){
	sol::solve();
	return 0;
}