ZZSR#1游记兼题解（？）

༺ཌༀཉི༒白·羊༒༃ༀད༻

2026-01-02 14:53:25

发布于：上海

95阅读

0回复

0点赞

如你所见，这其实也可以当做一篇题解……
看到题目，因为出题人保证按难度顺序，于是选择倒开~~准备骗分~~

T4

好的T4一眼瞪出答案为 $\sum_{i=1}^{n} \frac{A_i}{B_i}$
秒了……吗？嗯好的快速幂忘取模了，嗯。
附代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int MOD=1e9+7; 
int ksm(int a,int b){
	int ans=1,xx=a;
	while(b){
		if(b&1)
			ans*=xx,ans%=MOD;
		xx*=xx,xx%=MOD;
		b/=2;
	}
	return ans;
}
int n,a[109],b[109],ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	for(int i=1;i<=n;i++){
		int x=ksm(b[i],MOD-2);
		int y=a[i]*x%MOD;
		ans+=y;
		ans%=MOD;
	}
	cout<<ans;
	return 0;
}

T3

好的T3……嗯？这不是凸包吗？前两天刚学，直接求上凸壳下凸壳……诶不是怎么样例全错了第二问？哦哦哦我糖了，下凸壳不用求直接一个循环秒了……吗？
一测大样例全错第一问……
哦哦原来符号打反了~~这还能过小样例~~
OK啊大样例全过
这是我的赛时代码（注意此处有伏笔）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n;
double a[100009],S[100009];
double js(int i,int j){
	int dx=j*j-i*i;
	if(dx==0)
		return 1e30;
	return (S[j]-S[i])/(1.0*dx);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		S[i]=S[i-1]+a[i]*a[i];
	}
	vector<int> up;
	for(int j=0;j<=n;j++){
		while(up.size()>=2){
			int k=up.back();
			int l=up[up.size()-2];
			double dy1=S[k]-S[l];
			double dx1=k*k-l*l;
			double dy2=S[j]-S[k];
			double dx2=j*j-k*k;
			if(dy1*dx2<=dy2*dx1)
				up.pop_back();
			else
				break;
		}
		up.push_back(j);
	}
	double maxn=-1e30;
	for(int i=1;i<up.size();i++){
		maxn=max(maxn,js(up[i-1],up[i]));
	}
	double minn=1e30;
	for(int i=0;i<n;i++)
		minn=min(minn,js(i,i+1));
	cout<<fixed<<setprecision(3)<<maxn<<" "<<minn;
	return 0;
}

T2

嗯，嗯？这么快开到T2了？哇袄！居然是二分！我们有救了
样例全错……
彳亍
哦哦哦左边界卡的太极限了
过了
代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,s,a[100009],sum;
bool check(int k){
	priority_queue<int> q;
	for(int i=1;i<=k;i++)
		q.push(s);
	for(int i=1;i<=n;i++){
		int top=q.top();
		q.pop();
		if(top<a[i])
			return false;
		q.push(top-a[i]);
	}
	return true;
}

void solve(){
	cin>>n>>s;
	sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	int l=(sum+s-1)/s,r=n,ans=r;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid))
			ans=mid,r=mid-1;
		else
			l=mid+1;
	}
	cout<<ans<<endl;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}

T1

太好叻开到T1叻！
补豪！是字符串！此时我的脑中：哈希……KMP……AC自动机……（越来越离谱）
很好，此时出现了我赛时最糖的操作：我卡了半小时
直到我看见了那行字：

……
于是我气愤地糊了个暴力~~在出题人的脸上~~
code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n;
char a[1005],b[1005],tmp[1005];
void init(){
	int half=n/2;
	for(int i=1;i<=half;i++)
		tmp[2*i-1]=a[i];
	for(int i=half+1;i<=n;i++)
		tmp[2*(i-half)]=a[i];
	for(int i=1;i<=n;i++)
		a[i]=tmp[i];
}
bool flag(){
	for(int i=1;i<=n;i++)
		if(a[i]!=b[i])
			return false;
	return true;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	int k=1;
	init();
	while(!flag()){
		init();
		k++;
	}
	cout<<k<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}