21.8.7 test

\(NOIP\) 测试

考的一般般。

\(T1\) WOJ4656

签到题，其实就是算 \(\sum\limits_{i=1}^n i^2\)

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int mod=1e9+7;

int n,ans=0,len;

string s;

signed main(){

	cin>>n>>s;

	len=s.length();

	for(int i=1;i<=len;i++)

		ans=(ans+i*i%mod)%mod;

	cout<<ans;

	return 0;

}

当然可以用小学奥数 \(O(1)\) 算

\(T2\) WOJ4657（堆，区间交）

给出 \(n\) 个区间，选出 \(m\) 个区间使得这 \(m\) 个区间的交最大。

打出暴力后又打了一个正确性不保证的 dp，排序后成功过了大样例

区间交的左右端点都是给出区间的左右端点，所以考虑把所有区间按左端点排序后从左往右枚举，同时在堆里加入他们的右端点，对于一个左端点，从右往左数第 \(m\) 个右端点就是它对应交区间的右端点，所以小根堆维护一个从右往左的 \(m\) 个右端点。另外，如果一个区间的右端点小于当前堆顶，那么该区间的答案一定比上个答案劣（因为左端点单调上升），可以直接跳过，对于第二行输出，在维护答案时维护答案对应左右端点，枚举所有区间，完全覆盖答案区间的就输出，一共输出 \(m\) 个，另外答案为 \(0\) 时特判一下随便输出 \(m\) 个就行了。

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define in read()

inline int read(){

	int p=0,f=1;

	char c=getchar();

	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}

	return p*f;

}

const int N=1e6+5;

const int M=5e4+5;

int num,n,m;

struct seq{

	int l,r,o;

}a[N];

bool cmp(seq x,seq y){

	if(x.l!=y.l)return x.l<y.l;

	return x.r<y.r;

}

struct node{

	int x,i;

};

bool operator<(const node &x,const node &y){

	return x.x>y.x;

}

priority_queue<node>q;

signed main(){

	num=in,n=in,m=in;

	for(int i=1;i<=n;i++)

		a[i].l=in,a[i].r=in,a[i].o=i;

	sort(a+1,a+1+n,cmp);

	for(int i=1;i<=m;i++)

		q.push({a[i].r,i});

	int ans=max(0ll,q.top().x-a[m].l),ansl=a[m].l,ansr=q.top().x;

	for(int i=m+1;i<=n;i++){

		if(a[i].r<q.top().x)continue;

		q.push({a[i].r,i});

		q.pop();

		if(ans>max(0ll,q.top().x-a[i].l))continue;

		ans=max(0ll,q.top().x-a[i].l);

		ansl=a[i].l,ansr=q.top().x;

	}

	cout<<ans<<'\n';

	if(ans==0){

		for(int i=1;i<=m;i++)

			cout<<i<<" ";

		return 0;

	}

	int cnt=0;

	for(int i=1;i<=n;i++){

		if(a[i].l<=ansl&&a[i].r>=ansr){

			cout<<a[i].o<<" ";

			cnt++;

		}

		if(cnt==m)break;

	}

	return 0;

}

\(T3\) WOJ4658（容斥）

时间奉献给T2了，打了指数暴力就走了

容斥公式：

\(|A_1\cup A_2 \cup\cdots\cup A_m|=\sum\limits_{1\leq i\leq m}|A_i|-\sum\limits_{1\leq i\leq j\leq m}|A_i\cap A_j|+\sum\limits_{1\leq i\leq j\leq k\leq m}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{m-1}*|A_1\cap A_2 \cap\cdots\cap A_m|\)

在此题中也就是说所有1个话题相同的方案数减去两个话题相同的方案数加上3个话题相同的方案数减去……一直到n个话题。

我们只需要统计 \(2^N\) 个状态分别有多少人的集合或他们的子集，然后算出当前状态 \(1\) 的个数，奇数就加，偶数就减。在统计人数时需要枚举一个二进制数集合的所有子集，这篇blog里有详细的证明。

然后卡卡常（或者不用）就做完了。

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int M=1e5+5;

const int mod=1e9+7;

const int N=1<<20+5;

int num,n,m,k;

int a[M];

int cnt[N];

inline int lowbit(int x){return x&(-x);}

inline int pc(int x){

	int res=0;

	while(x){

		x-=lowbit(x);

		res++;

	}

	return res;

}

inline int qpow(int a,int b){

	int ans=1;

	while(b){

		if(b&1)ans=ans*a%mod;

		a=a*a%mod;

		b>>=1;

	}

	return ans;

}

inline int add(int a,int b){return (a+b)%mod;}

int ans,maxn;

signed main(){

	cin>>num>>n>>m>>k;

	for(int i=1;i<=m;i++){

		cin>>a[i];

		cnt[a[i]]++;

		maxn=max(maxn,a[i]);

	}

	sort(a+1,a+1+m);

	int qn=unique(a+1,a+1+m)-(a+1);

	for(int i=1;i<=qn;i++)

		for(int sub=(a[i]-1)&a[i];sub;sub=(sub-1)&a[i])

			cnt[sub]+=cnt[a[i]];

	for(int i=1;i<=maxn;i++){

		if(cnt[i]){

			qn=pc(i);

			if(qn&1) ans=add(ans,qpow(cnt[i],k));

			else ans=add(mod,ans-qpow(cnt[i],k));

		}

	}

	cout<<ans;

	return 0;

}

巴特西

21.8.7 test

最新文章

热门文章