首页 > 其他分享 >小集训 CSP-S 模拟赛

小集训 CSP-S 模拟赛

时间：2024-09-09 12:14:19浏览次数：8  
标签：typedef int long 集训 ans fi CSP 模拟 define

DAY 1

A.喜剧的迷人之处在于

小思维题不必细讲

B. 镜中的野兽

状压+容斥

$ gcd (x) + lcm(x) = m $ ，可以得知 $ gcd(x) $ 一定是 m 的因子，那么就可以枚举 $ gcd(x) $ 和 $ lcm(x) $。

对于已经确定的一对 $ gcd (x) 和 lcm(x) $ ，将他们进行质因数分解，写成 $ \prod{p_{i}^{c_{i}}} $ 的形式，那么对于每个质因子，都需要有至少一个数卡住他的下界，至少一个数卡住他的上界，并且保证最后 n 个数不相等即可。

设 $ h(x,y) $ 表示 $ y $ 分解质因数后，质因子 $ x $ 的幂。

令 $ d = \frac{lcm(x)}{gcd(x)} $ ，问题也就转化成，选择出 n 个数 $ x[i] $，对于 d 的每个质因子 $ p $ ，都至少有一个数卡了他的上界和下界，即 $ \sum_{i}{[ h( p , x[i] ) =0 ]} \ge 1 $ ， $ \sum_{i}{h(p,x[i])=h(p,d)} \ge 1 $ 。

那么就考虑进行容斥，求一个数被卡上界和下界的方案数比较难，那么我们可以求不能卡的方案数，用总方案数减去即可。

考虑状压表示每个数是否不能被卡上界和下界，容斥系数就是 $ popcount(状态) $。

看看码就好了 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define fi first
#define se second
#define ps push_back
#define mk make_pair
#define rint register int
#define G cout<<"-------------------"<<endl
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))(c=='-'?f=-1:0),c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=1e6+10,inf=0x7fffffff;
const ll linf=0x3f7f7f7f7f7f7f7f;
int pr[N],cnt,n,m,mod;
#define mo(x) (x>=mod?x-=mod:0)
#define m(x) (x<=-mod?x+=mod:0)
bool npr[N];
int num[33],cntp[33];
ll jc[N],ny1[N],ny2[N],ans;
inline ll C(int n,int m){
	return n<m?0:jc[n]*ny2[m]%mod*ny2[n-m]%mod;
}
inline void sol(int gcd,int lcm){
	if(gcd>=lcm)return;
	lcm/=gcd;
	int tot=0,k=sqrt(lcm);
	for(int i=1;pr[i]<=k;++i){
		// cout<<pr[i]<<' '<<k<<endl;
		if(lcm%pr[i]==0){
			num[++tot]=pr[i];cntp[tot]=0;
			while(lcm%pr[i]==0)cntp[tot]++,lcm/=pr[i];
		}
	}
	if(lcm!=1)num[++tot]=lcm,cntp[tot]=1;
	int shang=1ll<<(tot<<1),op=0;
	for(int i=0;i<shang;++i){
		int x=1,man=0;
		for(int j=0;j<tot;++j){
			int i1=(i>>j)&1,i2=(i>>j+tot)&1;
			man+=i1+i2;
			if(cntp[j+1]+1-i1-i2<=0){
				x=0;
				break;
			}
			x*=(cntp[j+1]+1-i1-i2);
		}
		// cout<<i<<' '<<man<<' '<<x<<"JIJIJI\n";
		(man&1)?op-=C(x,n),m(op):op+=C(x,n),mo(op);
		if(!i&&x<n)return;
	}
	ans+=op;m(ans),mo(ans);
}
main(){
	// #ifndef ONLINE_JUDGE
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	// #endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read(),m=read(),mod=read();
	int k=sqrt(m),gcd,lcm;
	for(int i=2;i<=min(k,10000);++i){
		if(!npr[i]){
			pr[++cnt]=i;
			for(int j=2;j*i<=min(k,10000);++j)
				npr[i*j]=1;
		}
	}
	pr[++cnt]=1e9;
	jc[0]=jc[1]=ny1[1]=ny2[0]=ny2[1]=1;
	for(int i=2;i<50000;++i){
		jc[i]=jc[i-1]*i%mod;ny1[i]=(mod-mod/i)*ny1[mod%i]%mod,ny2[i]=ny2[i-1]*ny1[i]%mod;
	}
	for(int i=1;i<=k;++i){
		if(m%i==0){
			gcd=i,lcm=m-gcd;
			sol(gcd,lcm);
			if(m!=i*i){
				gcd=m/i,lcm=m-gcd;
				sol(gcd,lcm);
			}
		}
	}
	cout<<(ans+mod)%mod;
}

C. 我愿相信由你所描述的童话

其实还没学会正解呢（

但是这道题的暴力也挺难打的，我们要枚举每个点作为中间点的时候，要找出他的左边有多少种方案，右边有多少种方案，然后把它们乘起来就行了， 然后你就会发现他只过了样例 。

那么我们重新看题目的要求：

image

  • 一个序列，满足其中有一个点可以作为中间点，那么他就是一个合法序列，求合法序列的个数。

如果按照上面的方法去求，就会发现有些序列会被统计多次，因为 $ s_i $ 可以是重复的，那么一堆相同的点都可以做中间点，枚举每个中间点的时候，这个序列就会被统计多次。

image

对于上图的这个序列，他就会被统计三次。

考虑如何避免这种情况：我们可以钦定所有相等数都由最左边那个数统计答案，也就是只有下面这种情况是合法的。

image

也就是说，统计一个数的左边方案数时，不能由和他的值相同的数转移过来，但是我们需要开两个数组来统计左边的答案，

$ f_i $ 表示以 $ i $ 为中间点，左边不包含和他相等的数的方案数， $ ff_i $ 表示以 $ i $ 为中间点，左边可以包含和他相等的数的方案数，那么就有转移方程：

\[\large f_i = \sum_{s_j \ or \ s_i =s_i，s_i \ne s_j}{ff_j} \]

\[\large ff_i = \sum_{s_j \ or \ s_i = s_i}{ff_j} \]

为什么一定要这样写，因为一段数作为中间点的时候会统计错误，但一段数不作为中间点的时候是无需钦定的。

image

像这种情况就无法被统计到。

然后就拿到了暴力分。

这是这道题的题解：

image

借助题解的思想，可以写出一个水过数据的码，但很容易被卡。

$\large 水$ 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
	char c=getchar();ll x=0;
	while(!isdigit(c))c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}
const int N=3e5+10;
const int mod=1e9+7;
int f[1<<20],f1[1<<20],ans[N],n,m,a[N],anss;
#define mo(x) (x>=mod?x-=mod:0)
main(){
	// #ifndef ONLINE_JUDGE
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	// #endif
	n=read(),m=read();
	// int k=1<<m;
	for(int i=1;i<=n;i=-~i){
		a[i]=read();
	}
	for(int i=1;i<=n;i=-~i){
		int j=0,w=a[i],lp=max(w&-w,1);ans[i]=1; 
		while(j<w){
			if((w|j)==w){
				ans[i]+=f[j],mo(ans[i]),j+=lp;
				// if(i==10)cout<<j<<"NIU\n";
			}
			else j+=j&-j;
		}
		// (f[w]+=(f[w]+ans[i])%mod)%=mod;
		f[w]<<=1;f[w]>=mod?f[w]-=mod:0;
		f[w]+=ans[i];mo(f[a[i]]);
	}
	for(int i=n;i;i=~-i){
		int j=0,op=1,w=a[i],lp=max(w&-w,1);
		while(j<=w){
			if((w|j)==w)op+=f1[j],mo(op),j+=lp;
			else j+=j&-j;
		}
		(f1[w]+=op);mo(f1[w]);
		(anss+=(ll)ans[i]*op%mod);mo(anss);
		// cout<<i<<' '<<ans[i]<<' '<<op<<endl;
	}
	cout<<anss;
}

D. Baby Doll

躺尸体，做不了一点。

DAY1 总结：

四道数学题，不知道是不是又是 joke3579 雪张出的，有一种被 qj 的无力感。

但也学了一下容斥。

\[\]

\[\]

\[\]

\[\]

\[\]

\[\]

\[\]

DAY2:

A. 不相邻集合

发现只需要维护连续段，可以用 set 、并查集，也可以直接维护一个连续段的开头和末尾，直接 $ O(n) $ 做。

码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define fi first
#define se second
#define ps push_back
#define mk make_pair
#define rint register int
#define G cout<<"-------------------"<<endl
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))(c=='-'?f=-1:0),c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=1e6+10,inf=0x7fffffff;
const ll linf=0x3f7f7f7f7f7f7f7f,mod=1e9+7;
struct jj{
	mutable int l,r;
	inline bool operator <(const jj&x)const{
		return l<x.l;
	}
};
int n,a[N],ans;
set<jj> s;
int main(){
	// #ifndef ONLINE_JUDGE
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	// #endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	s.insert({-1,-1});
	for(int i=1;i<=n;++i){
		auto it=s.lower_bound({a[i],a[i]});
		if(it==s.end()||it->l>a[i])--it;
		if(it->r>=a[i]){
			cout<<ans<<' ';
			continue;
		}
		++it;
		if(it!=s.end()&&it->l==a[i]+1)ans-=(it->r-it->l+2)/2,it->l=a[i],ans+=(it->r-it->l+2)/2;
		else it=s.insert({a[i],a[i]}).fi,++ans;
		if(it!=s.begin()){
			--it;
			if(it->r==a[i]-1){
				int l=it->l;
				ans-=(it->r-it->l+2)/2;

				++it;
				s.erase({l,a[i]-1});
				ans-=(it->r-it->l+2)/2;
				it->l=l;
				ans+=(it->r-it->l+2)/2;
			}
		}
		cout<<ans<<' ';
	}
}

B. 线段树

直接递归求解的话肯定会复杂度爆炸，那么我们可以发现很多过程是重复的，对于一个长度固定的区间，我们去跑他的线段树可能要跑很多次，但是每次传进去的初始 k 值不一样，就导致他对答案的贡献不一样，那么我们想办法把一棵树缩成一个函数，只要知道传进去的自变量 k ，就可以直接算出他对答案的贡献，那么我们就可以进行记搜。

然后你就会发现，对于一个长度确定的区间，他的线段树可以转换为和 k 有关的一次函数形式。

可以做做cats 的二分答案，也是只和长度有关的记搜。

码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define int ll
#define fi first
#define se second
#define ps push_back
#define mk make_pair
#define rint register int
#define G cout<<"-------------------"<<endl
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))(c=='-'?f=-1:0),c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}

#define mo(x) (x>=mod?x-=mod:0)
const int N=1e6+10,inf=0x7fffffff;
const ll linf=0x3f7f7f7f7f7f7f7f,mod=1e9+7;
ll ans=0;
unordered_map<int,pair<ll,ll> >ma;
inline pair<ll,ll> dfs(int x){
	if(ma[x].fi)return ma[x];
	pair<ll,ll> q={1,0},zan;
	int l=1,r=x,mid=l+r>>1;
	zan=dfs(mid-l+1);
	q.fi=(q.fi+zan.fi*2)%mod,q.se+=zan.se;mo(q.se);
	zan=dfs(r-mid);
	q.fi=(q.fi+zan.fi*2)%mod,q.se+=zan.fi,mo(q.se),q.se+=zan.se,mo(q.se);
	return ma[x]=q;
}
inline void sol(int k,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		pair<ll,ll> p=dfs(r-l+1);
		ans+=k*p.fi%mod,mo(ans);
		ans+=p.se,mo(ans);
		return;
	}
	int mid=l+r>>1;
	if(L<=mid)sol((k<<1)%mod,l,mid,L,R);
	if(R>mid)sol((k<<1|1)%mod,mid+1,r,L,R);
}
main(){

	// #ifndef ONLINE_JUDGE
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	// #endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t=read();
	ma[1]={1,0};
	while(t--){
		ans=0;
		int n=read(),l=read(),r=read();
		sol(1,1,n,l,r);
		cout<<ans<<'\n';
	}
	// cout<<ma[2].fi<<' '<<ma[2].se<<endl;
}

C. 魔法师

尝试转化题意，只可以用 $ \max (a_i + a_j , b_i + b_j) $ （接下来以 i 为坐标的表示法杖，以 j 为坐标的表示法咒），来更新答案，那么就去分情况什么时候 用a，什么时候用b。

$ a_i + a_j < b_i + b_j $ ，移项，做到下标一样的在同一侧（这是一种移项很重要的思想），$ a_i - b_i \lt b_j - a_j $。

设 $ a_i - b_i $ 为 $ k1 $ ， $ b_j - b_i $ 为 $ k2 $ 。

当 $ k1 \lt k2 $ 时，应该用 $ b $ 去更新答案，否则用 $ a $ 去更新答案。

这样我们就可以建一颗线段树，维护对应的 $ k1,k2 $ 的位置上的 $ a_i,b_i,a_j,b_j $（ $ a_i 与a_j ， b_i 与 b_j $ 是不一样的） 的最小值和答案。对于魔杖，在 $ k1 $ 的位置上去更新 $ a_i ,b_i $ 的最小值，顺便更新答案，对于法咒就在 $ k2 $ 的位置上进行相应的操作。

统计答案时，对于一个节点的左子树和右子树来说，左子树的任何一个权值都小于右子树的权值，所以用左子树的 $ b_i $ + 右子树的 $ b_j $ 来更新答案（此时左边代表 $ k1 $，右边是 $ k2 $ ，$ k1 \lt k2 $ ，用 $ b $ 更新答案），以及左子树的 $ a_j $ + 右子树的 $ a_i $ 来更新答案（和前者相反）。

处理的很巧妙，但首先要想到把下标一样的移项到同一侧。

细节看代码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define fi first
#define se second
#define ps push_back
#define mk make_pair
#define rint register int
#define G cout<<"-------------------"<<endl
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))(c=='-'?f=-1:0),c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=1e6+10,inf=0x3f3f3f3f,B=25e4;
const ll linf=0x3f7f7f7f7f7f7f7f,mod=1e9+7;
int sum[N][2][2],ans[N];
multiset<int> s[500001][2][2];// 因为有删除操作，所以用multiset 维护
inline void add(int k,int l,int r,int pos,int va,int vb,int op){
	if(l==r){
		if(!s[l][0][0].size())s[l][0][0].insert(1e8),s[l][0][1].insert(1e8),s[l][1][0].insert(1e8),s[l][1][1].insert(1e8);
		if(op<0){
			auto pos=s[l][-op-1][0].lower_bound(va);
			if((*pos)==va)s[l][-op-1][0].erase(pos);
			pos=s[l][-op-1][1].lower_bound(vb);
			if((*pos)==vb)s[l][-op-1][1].erase(pos);
		}
		else s[l][op-1][0].insert(va),s[l][op-1][1].insert(vb);
		sum[k][0][0]=*(s[l][0][0].begin()),sum[k][0][1]=*(s[l][0][1].begin()),sum[k][1][0]=*(s[l][1][0].begin()),sum[k][1][1]=*(s[l][1][1].begin());
		ans[k]=min(sum[k][0][0]+sum[k][1][0],sum[k][0][1]+sum[k][1][1]);
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid)add(k<<1,l,mid,pos,va,vb,op);
	else add(k<<1|1,mid+1,r,pos,va,vb,op);
	sum[k][0][0]=min(sum[k<<1][0][0],sum[k<<1|1][0][0]),sum[k][0][1]=min(sum[k<<1][0][1],sum[k<<1|1][0][1]);
	sum[k][1][0]=min(sum[k<<1][1][0],sum[k<<1|1][1][0]),sum[k][1][1]=min(sum[k<<1][1][1],sum[k<<1|1][1][1]);
	ans[k]=min({ans[k<<1],ans[k<<1|1],sum[k<<1][0][1]+sum[k<<1|1][1][1],sum[k<<1][1][0]+sum[k<<1|1][0][0]});
}
int main(){
	// #ifndef ONLINE_JUDGE
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	// #endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int q=read(),t=read();
	memset(sum,0x3f,sizeof(sum));
	memset(ans,0x3f,sizeof(ans));
	for(int i=1,op,opp,x,y,anss=0;i<=q;++i){
		op=read(),opp=read(),x=read(),y=read();
		if(t)x^=anss,y^=anss;
		if(op==1){
			int k=opp?y-x:x-y;
			add(1,1,5e5,k+B,x,y,opp+1);
			anss=ans[1]>1e6?0:ans[1];
			cout<<anss<<'\n';
		}
		else{
			int k=opp?y-x:x-y;
			add(1,1,5e5,k+B,x,y,-opp-1);
			anss=ans[1]>1e6?0:ans[1];
			cout<<anss<<'\n';
		}
	}
}

还有一开始写完了代码老是MLE，后来发现multiset即使不插数时也会占 183MB 的内存，不太理解他的内存是怎么分配的，有知道的请说说。

D. 园艺

也是一个很好的 idea ， 但一直感觉都是在被题解牵着走，没有找到这道题的切入点，那就直接粘题解了：

image

首先上面的转弯是可以感性理解的，但是后面的 dp 改变成另外一种写法应该是为了 压维 吧，对于其他的操作用双指针和斜率优化即可。

码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define fi first
#define se second
#define ps push_back
#define mk make_pair
#define rint register int
#define G cout<<"-------------------"<<endl
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))(c=='-'?f=-1:0),c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=2e6+10,inf=0x7fffffff;
const ll linf=0x3f7f7f7f7f7f7f7f,mod=1e9+7;
ll n,a[N],s[N],f[N];
ll q1[N],q2[N],l1,r1=-1,l2,r2=-1;
double k1[N],k2[N];
#define Y1(k) (f[k]-2ll*k*s[k]+2ll*s[k])
#define Y2(k) (f[k]+2ll*n*s[k]-2ll*k*s[k])
#define K1(x,y) (((double)Y1(y)-Y1(x))/(-2.0*y+2.0*x))
#define K2(x,y) (((double)Y2(y)-Y2(x))/(-2.0*y+2.0*x))
inline void add1(ll k){
	while(l1<r1&&(K1(q1[r1],k)<=k1[r1-1]))--r1;
	q1[++r1]=k;
	if(r1>l1)k1[r1-1]=K1(q1[r1-1],q1[r1]);
}
inline void add2(ll k){
	while(l2<r2&&K2(k,q2[r2])>=k2[r2-1])--r2;
	q2[++r2]=k;
	if(r2>l2)k2[r2-1]=K2(q2[r2],q2[r2-1]);
}
ll k;
inline void ans1(int i){
	if(l2>r2)return;
	while(l2<r2&&k2[l2]>=s[i])++l2;
	f[i]=f[q2[l2]]+2ll*(n-q2[l2])*(s[q2[l2]]-s[i]);
}
inline void ans2(int j){
	if(l1>r1)return;
	while(l1<r1&&k1[l1]<=s[j])++l1;
	f[j]=f[q1[l1]]+2ll*(q1[l1]-1)*(s[j]-s[q1[l1]]);
}
int main(){
	// #ifndef ONLINE_JUDGE
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	// #endif
	n=read();k=read();
	for(int i=1;i<n;++i){
		a[i]=read();s[i+1]=s[i]+a[i];
	}
	fill(f+1,f+1+n,linf);
	f[k]=0;
	for(int i=1;i<=n;++i)
		f[k]+=abs(s[k]-s[i]);
	ll i=k,j=k;
	while(i>0&&j<=n){
		if(f[i]<=f[j]){
			add1(i);
			ans2(j);
			--i;
			ans1(i);
		}
		else{
			add2(j);
			ans1(i);
			++j;
			ans2(j);
		}
	}
	cout<<min(f[1],f[n]);
}

\[\]

\[\]

\[\]

总结：

其实这两场学的东西还真不少，尤其是DAY2的题，里面的 新trick 不少，也是因为这个才写了这篇博客。

标签：typedef,int,long,集训,ans,fi,CSP,模拟,define
From： https://www.cnblogs.com/GGrun-sum/p/18403505

相关文章

  • 基于Python的期货交易模拟系统
    基于Python的期货交易模拟系统。开发技术：PyCharm开发环境；Python语言；MySQL数据库；Django框架；B/S架构。项目内容：该系统从三个对象：由管理员和用户、期货公司来对系统进行设计构建。主要功能包括：个人信息修改，对用户信息、期货公司信息、期货投资、取消投资、风险控制、账户资金、......
  • Cesium 展示——静态水添加动态波纹，模拟真实水面效果
    文章目录需求分析材料准备根据几何实例创建贴地面图元将图元添加到集合需求分析材料准备首先我们需要准备水波的图片，放在最后大家自行......
  • 洛谷 P9754 [CSP-S 2023] 结构体 题解
    题目传送门洛谷博客CSDNCSP-S2023T3结构体题解基本思路本题主要考查编码能力，所以直接给出基本思路：由于可以递归式的创建元素，最多可以同时存在\(100^{100}\)个不同的基础类型的元素。即使算上最大地址的限制，元素的数量也能达到\(10^{18}\)。显然，依次构造每个元素，在空......
  • 2024.9.8 CSP-S 模拟赛
    T1现在你站在坐标轴的一个整点上，给你\(n\)种技能，每个技能是整数对\((p,c)\)的形式，学会它需要花费\(c\)，但是学会了可以无限用。用的意思是可以向左或向右\(p\)个单位长度。求最小的学技能开销，使得你可以访问到坐标轴的所有整点。\(n\leq10^5,x\leq10^9\)随便玩了一下......
  • CSP 模拟 29
    T1不相邻集合做法一：设\(f_i\)表示到当前位置以\(i\)结尾的最长长度，\(s_i\)表示以\(i\)开头的最长长度。有\(a>b\Leftrightarrowf_a>f_b\Leftrightarrows_a<s_b\)，有了这个性质就可以直接上线段树维护，时间复杂度\(\mathcal{O}(n\logn)\)。#include<bits/stdc++.h>ty......
  • csp-s模拟2
    A.不相邻集合可以发现，一个数只有在第一次出现才会做贡献，对于一个连续数段\(1,2,3...n\)，它最多提供\(\lceil\frac{n}{2}\rceil\)的贡献，所以只需要维护极长连续段即可点击查看代码#include<bits/stdc++.h>constintmaxn=3e5+10;usingnamespacestd;intn,a[maxn],f......
  • 9.8 模拟赛（炼石计划 11 月 11日 CSP-S 十连测 #9）
    炼石计划11月11日CSP-S十连测#9【补题】-比赛-梦熊联盟(mna.wang)\(100+60+20+15=195\)。复盘顺序开题。T1是二分板子。写之前思考好了所有代码细节直接写代码。一遍过了所有大样例。T2。题意好麻烦。\(35\)分是极易的。跳过\(25\)分部分分，直接想正解。有......
  • csp模拟2
    T1原题根据倒数第二，三个部分分的提示，我们可以发现一个性质，如果两个连续的序列中间被间隔开，如\(1,2,3,4,6,7,8,9\)那这两个序列中选数操作互不影响，那这就比较好办了，一个长度为\(n\)连续序列最多可以选出$\lceil\frac{n}{2}\rceil$个数,那我们只需要维护连续的区间的个......
  • NOIP 模拟赛 Round5
    T1：赛时一眼秒了，然后爆单了。没有什么思路就要想到一些套路比如把模拆成减除，然后发现有个\(k\)，自然思路就出来了，\(k\)必然是一个数的因数。复杂度是根号的。注意特判\(s=0,s<0\)！！！T2：一眼二分贪心……显然不能优化建图按照a排序也是显然的。T3：最唐的地方是所有人都在考虑......
  • csp-s模拟1
    A.喜剧的迷人之处在于切入点在\(a\)，考虑\(a\)是不是完全平方数，是的话直接找最小能匹配的完全平方数即可，不是的话\(a\)一定可以表示成\(kx^2\)的形式，倒着找到最大的平方因子除去，只需要在\(L\)~\(R\)间找到一个最小的数也等于\(kx^2\)即可点击查看代码#include<bits......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99