10.27 正睿提高9

目录

2018.10.27 正睿提高9

期望得分：?+?+?
实际得分：10+20+100

比赛链接

T1 T2做得真是傻啊==。。

A 数分考试(拓扑 贪心)

题目链接

容易想到用堆来维护拓扑序。假设从排名小的开始放。
对于当前排名(now)，先把(l_i=now)且排名限制（拓扑序）允许的人加入堆，然后从堆中找到(r_i)最小的作为排名为(now)的人。
注意在此之前要收紧所有人(r)的限制，比如(u)比(v)排名低，那么(r_u=min{r_u,r_v-1})。
那么用两个堆就做完了（一个堆+一个vector也行。事实上因为常数更大差不了多少。。慢了）。

两个堆：

//1938ms	17588kb
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define fir first
#define sec second
#define mp std::make_pair
#define pr std::pair<int,int>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=3e5+5,M=1e6+5;

int Enum,H[N],nxt[M],to[M],L[N],R[N],dgr[N];
char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline void AE(int v,int u)
{
	++dgr[v], to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
}
bool Solve(int n)
{
	static int q[N],dgr2[N],Ans[N];
	static std::priority_queue<pr,std::vector<pr>,std::greater<pr> > q1,q2;

	int h=0,t=0;
	memcpy(dgr2,dgr,sizeof dgr2);
	for(int i=1; i<=n; ++i) if(!dgr2[i]) q[t++]=i;
	while(h<t)
	{
		int x=q[h++];
		for(int i=H[x]; i; i=nxt[i])
			if(!--dgr2[to[i]]) q[t++]=to[i];
	}
	if(t<n) return 0;
	for(int i=n-1,x; ~i; --i)//从0开始。。
	{
		for(int j=H[x=q[i]]; j; j=nxt[j])
			R[x]=std::min(R[x],R[to[j]]-1);
		if(L[x]>R[x]) return 0;
	}

	for(int i=1; i<=n; ++i) if(!dgr[i]) q1.push(mp(L[i],i));
	for(int now=1,x; now<=n; ++now)
	{
		while(!q1.empty()&&q1.top().fir<=now)
			q2.push(mp(R[q1.top().sec],q1.top().sec)), q1.pop();
		if(q2.empty()) return 0;
		Ans[now]=x=q2.top().sec, q2.pop();
		if(R[x]<now) return 0;
		for(int i=H[x]; i; i=nxt[i])
			if(!--dgr[to[i]]) q1.push(mp(L[to[i]],to[i]));
	}
	for(int i=1; i<=n; ++i) printf("%d
",Ans[i]);
	return 1;
}

int main()
{
	int n=read(),m=read();
	for(int i=1; i<=n; ++i) L[i]=read(),R[i]=read();
	for(int i=1; i<=m; ++i) AE(read(),read());
	if(!Solve(n)) puts("-1");

	return 0;
}

一个堆+vector：

//2399ms	30732kb
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define fir first
#define sec second
#define mp std::make_pair
#define pr std::pair<int,int>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=3e5+5,M=1e6+5;

int Enum,H[N],nxt[M],to[M],L[N],R[N],dgr[N];
std::vector<int> vec[N];
char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline void AE(int v,int u)
{
	++dgr[v], to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
}
bool Solve(int n)
{
	static int q2[N],dgr2[N],Ans[N];
	static std::priority_queue<pr,std::vector<pr>,std::greater<pr> > q;

	int h=0,t=0;
	memcpy(dgr2,dgr,sizeof dgr2);
	for(int i=1; i<=n; ++i) if(!dgr2[i]) q2[t++]=i;
	while(h<t)
	{
		int x=q2[h++];
		for(int i=H[x]; i; i=nxt[i])
			if(!--dgr2[to[i]]) q2[t++]=to[i];
	}
	if(t<n) return 0;
	for(int i=n-1,x; ~i; --i)
	{
		for(int j=H[x=q2[i]]; j; j=nxt[j])
			R[x]=std::min(R[x],R[to[j]]-1);
		if(L[x]>R[x]) return 0;
	}

	for(int i=1; i<=n; ++i) if(!dgr[i]) vec[L[i]].push_back(i);
	for(int now=1,x; now<=n; ++now)
	{
		for(int i=0,l=vec[now].size(); i<l; ++i) x=vec[now][i],q.push(mp(R[x],x));
		if(q.empty()) return 0;
		Ans[now]=x=q.top().sec, q.pop();
		if(R[x]<now) return 0;
		for(int i=H[x],v; i; i=nxt[i])
			if(!--dgr[v=to[i]])
				if(L[v]<=now) vec[now+1].push_back(v);
				else vec[L[v]].push_back(v);
	}
	for(int i=1; i<=n; ++i) printf("%d
",Ans[i]);
	return 1;
}

int main()
{
	int n=read(),m=read();
	for(int i=1; i<=n; ++i) L[i]=read(),R[i]=read();
	for(int i=1; i<=m; ++i) AE(read(),read());
	if(!Solve(n)) puts("-1");

	return 0;
}

B 集合(MillerRabin 容斥)

题目链接

显然集合里的数一定都是(n)的约数。考虑对(n)分解质因数。
设(n=prod_{i=1}^kp_i^{a_i})。显然(k)不会很大（最大是(15)）。
(n)的每个约数自然是对每个(p_i)选一个次数(t_iin[0,a_i])，然后全乘起来得到。
注意到(gcd=1,mathbb{lcm}=n)的限制，实际上是，对于每个(p_i)，对集合中的数分解质因数后，存在至少一个数的(t_i=0)，且存在至少一个数的(t_i=a_i)。（也就是(min{t_i}=0,max{t_i}=a_i)）

可以想到容斥。这就是(2k)个条件，不妨先(2^{2k})枚举这些条件。
即最初有(L_i=0,R_i=a_i)。
若要求不存在一个数的(t_i=0)，则令(L_i)加一；
若要求不存在一个数的(t_i=a_i)，则令(R_i)减一。
对于(n)的约数的每个质因子有(R_i-L_i+1)种选择，即当前一共有(prod R_i-L_i+1)个约数，所以此时的贡献是((-1)^s(2^{prod R_i-L_i+1}-1))（(s)为违反条件数）。
这样是(2^{2k}=4^{k})的，过不去。

再考虑对于每个(p_i)的选择：

  1. 什么也不做；
  2. 最小值没有满足，最大值满足了，令(L_i+1)；
  3. 最大值没有满足，最小值满足了，令(R_i-1)；
  4. 最小值最大值都没有满足，(L_i+1)且(R_i-1)。

情况(2,3)对答案的贡献其实是一样的，所以对于(2,3)可以放在一起算。
这样就是(3^{k})了。

还有一个问题是怎么对(n)分解质因数。显然可以直接(Pollard Rho)。
实际上，如果我们处理出(leq10^6)的质数分解，(n)只可能再由两个(>10^6)的质数相乘得到。即此时(n)只有三种可能：(n)，(p^2)，(pq)。
对于第一种情况可以(Miller Rabin)判；对于第二种情况可以对(n)开平方根判断；如果不是这两种，那么一定是第三种。因为我们不关心(p_i)是多少，只需要知道还有两个(a_i=1)的质因数就可以了。

//8ms	596kb
#include <cmath>
#include <cstdio>
#include <algorithm>
#define mod 998244353
typedef long long LL;
const int N=233;

int tm[N];
LL Ans;

namespace Math
{
	const int P[8]={2,3,5,7,11,13,17};//7
	inline LL Mult(LL a,LL b,LL p)
	{
		LL tmp=a*b-(LL)((long double)a/p*b+1e-8)*p;
		return tmp<0?tmp+p:tmp;
	}
	inline LL FP(LL x,LL k,LL p)
	{
		LL t=1;
		for(; k; k>>=1,x=Mult(x,x,p))
			if(k&1) t=Mult(t,x,p);
		return t;
	}
	inline int FP(int x,int k)
	{
		int t=1;
		for(; k; k>>=1,x=1ll*x*x%mod)
			if(k&1) t=1ll*t*x%mod;
		return t;
	}
	bool Miller_Rabin(LL p)
	{
		if(p==2) return 1;
		if(!(p&1)||p==1) return 0;
		for(int i=0; i<7; ++i)
			if(p==P[i]) return 1;
			else if(!(p%P[i])) return 0;
		LL u=p-1; int t=0;
		while(!(u&1)) u>>=1,++t;
		for(int i=0; i<7; ++i)
		{
			LL now=FP(P[i],u,p),las;
			for(int j=1; j<=t; ++j)
			{
				las=now, now=Mult(now,now,p);
				if(now==1&&las!=1&&las!=p-1) return 0;
			}
			if(now!=1) return 0;
		}
		return 1;
	}
}

void DFS(int x,int coef,int sum)
{
	if(!x)
	{
		Ans+=1ll*coef*(Math::FP(2,sum)-1)%mod;
		return;
	}
	DFS(x-1,coef,1ll*sum*(tm[x]+1)%(mod-1));
	DFS(x-1,-2*coef,1ll*sum*tm[x]%(mod-1));
	if(tm[x]>=2) DFS(x-1,coef,1ll*sum*(tm[x]-1)%(mod-1));
}

int main()
{
	LL n; scanf("%lld",&n);
	int cnt=0;
	for(int i=2; 1ll*i*i<=n&&i<=1e6; ++i)
		if(!(n%i))
		{
			n/=i, tm[++cnt]=1;
			while(!(n%i)) n/=i, ++tm[cnt];
		}
	if(n>1)
	{
		if(Math::Miller_Rabin(n)) tm[++cnt]=1;
		else if(1ll*sqrt(n)*sqrt(n)==n) tm[++cnt]=2;
		else tm[++cnt]=1, tm[++cnt]=1;
	}
	DFS(cnt,1,1), printf("%lld
",(Ans%mod+mod)%mod);

	return 0;
}

C 主地斗(思路)

题目链接

如果有一张王在先手手里或在牌堆里，那么后手可以一直不出牌，这样先手最后会拿着王出不出去然后gg。
否则，如果两张王都在后手手里，我猜是先手必胜。确实是这样，为啥我不知道（让后手变成先手？）。

#include <cstdio>
#include <cctype>
#include <iostream>
#include <algorithm>
#define gc() getchar()
using std::cin;
using std::string;
typedef long long LL;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
bool Solve()
{
	string str;
	for(int i=1; i<=6; ++i) cin>>str;
	int cnt=0;
	for(int i=1; i<=6; ++i)
	{
		cin>>str;
		if(str=="RJ"||str=="BJ") ++cnt;
	}
	for(int i=1; i<=42; ++i) cin>>str;
	cin>>str;
	return cnt==2;
}

int main()
{
	for(int T=read(); T--; puts(Solve()?"First":"Second"));
	return 0;
}

考试代码

A

明显不对的拓扑。我怎么觉得那么对。。

#include <queue>
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=3e5+5,M=1e6+5;

int Enum,H[N],nxt[M],to[M],dgr[N];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Node
{
	int l,r,id;
	bool operator <(const Node &x)const
	{
		return l==x.l?r<x.r:l<x.l;
	}
}A[N];

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline void AE(int u,int v)
{
	++dgr[v], to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
}
bool Solve(int n)
{
	static int Ans[N];
	static std::priority_queue<Node> q;
	for(int i=1; i<=n; ++i) if(!dgr[i]) q.push(A[i]);
	if(q.empty()) return 0;
	int now=n;
	while(!q.empty())
	{
		Node tmp=q.top(); q.pop();
		int x=tmp.id,l=tmp.l,r=tmp.r;
//		printf("x:%d l:%d r:%d now:%d
",x,l,r,now);
		if(l>now||r<now) return 0;
		Ans[now--]=x;
		for(int i=H[x]; i; i=nxt[i])
			if(!--dgr[to[i]]) q.push(A[to[i]]);
	}
	if(now) return 0;
	for(int i=1; i<=n; ++i) printf("%d
",Ans[i]);
	return 1;
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);

	int n=read(),m=read();
	for(int i=1; i<=n; ++i) A[i]=(Node){read(),read(),i};
	for(int i=1; i<=m; ++i) AE(read(),read());
	if(!Solve(n)) puts("-1");

	return 0;
}/*
5 2
4 5
3 5
3 5
2 5
1 2
2 3
4 3
*/

B

瞎容斥失败。告辞。

#include <cmath>
#include <cstdio>
#include <algorithm>
#define mod 998244353
#define Mod(x) x>=mod&&(x-=mod)
typedef long long LL;
const int N=1e6+5;

int A[N],mu[N],p[N],pw[N],Ans;
bool not_p[N],vis[233];

void Init(int n)
{
	mu[1]=1; int tot=0;
	for(int i=2; i<=n; ++i)
	{
		if(!not_p[i]) p[++tot]=i,mu[i]=-1;
		for(int j=1,v; j<=tot&&(v=i*p[j])<=n; ++j)
		{
			not_p[v]=1;
			if(i%p[j]) mu[v]=-mu[i];
			else {mu[v]=0; break;}
		}
	}
}
int Divide(int n)
{
	int cnt=1,lim=sqrt(n);
	for(int i=2; i<=lim; ++i)
		if(!(n%i))
		{
			++cnt;
			if(i*i!=n) A[++cnt]=n/i;
		}
	printf("%d:%d
",n,cnt+1);
}
int Gcd(int x,int y)
{
	return y?Gcd(y,x%y):x;
}
void DFS(int x,int lim,int n)
{
	if(x>lim)
	{
		int g=0;
		for(int i=1; i<=lim; ++i)
			if(vis[i])
				if((g=g?Gcd(g,A[i]):A[i])==1) break;
		if(g!=1) return;
		int lcm=1;
		for(int i=2; i<=lim; ++i)
			if(vis[i]) lcm=lcm*A[i]/Gcd(lcm,A[i]);
		Ans+=lcm==n;
		return;
	}
	DFS(x+1,lim,n), vis[x]=1, DFS(x+1,lim,n), vis[x]=0;
}
void Subtask3(LL n)
{
	if(n==1) return (void)printf("%d
",1);
	int lim=sqrt(n),cnt=0; A[++cnt]=1;
	for(int i=2; i<=lim; ++i)
		if(!(n%i))
		{
			A[++cnt]=i;
			if(i*i!=n) A[++cnt]=n/i;
		}
	A[++cnt]=n;
	printf("n:%d cnt:%d ",n,cnt);
	if(cnt<=21||1)
	{
		Ans=0, DFS(1,cnt,n), printf("%d
",Ans);
		return;
	}

	Init(n), pw[0]=1;
	for(int i=1; i<=cnt; ++i) pw[i]=pw[i-1]<<1, Mod(pw[i]);
	LL ans=pw[cnt-1]-1;
	for(int i=2; i<=cnt; ++i)
	{
		if(!mu[A[i]]) continue;
		int s=0,tmp=A[i];
		for(int j=i; j<cnt; ++j) s+=!(A[j]%tmp);
		ans+=1ll*mu[tmp]*pw[s]%mod;
	}
	printf("%d
",(int)((ans%mod+mod)%mod));
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);

	LL n; scanf("%lld",&n);
	if(n<=1e8||1) return Subtask3(n),0;
//	for(int n=1; n<=40; ++n) Subtask3(n);
//	for(int n=99000; n<=100000; ++n) Divide(n);
	
	return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/SovietPower/p/9867184.html