老年暴力选手

考试经过

开题状态不很好，被昨天T4搞的有点炸现在也没调出来
T1T2貌似都很简单，然而不会做，于是T1写了乱搞T2写了暴力，T3T4都只有爆搜
60+30+30+10=130，意料之中，最后T2的部分分挂了，结果发现把1改成0就50。。。
有全切的，还是应该多思考，多打分

T1.Set

不是dp，不用瞎想，直接输入取模，一个前缀和完事
由于他的取值有限，都是在模意义下的，所以必定有解，而且解一定可以是一个连续段，找到输出就行

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
const int N=1e6+30;
int a[N],sum[N];
int p[N];
signed main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	int n;cin>>n;
	for(int i=1;i<=n;i++)a[i]=read()%n;
	for(int i=1;i<=n;i++)sum[i]=(sum[i-1]+a[i])%n;
	for(int i=1;i<=n;i++)
	{
		int v=sum[i];
		if(p[v])
		{
			cout<<i-p[v]<<endl;
			for(int j=p[v]+1;j<=i;j++)printf("%lld ",j);
			return 0;
		}
		p[v]=i;
	} 
	return 0;
}

T2. Read

设最多的数出现次数为\(s\),答案显然为\(\max(0,s-(n-s)-1)\)
问题是空间小，数组开不下，直接写最多50
题解采用了一种很有意思的方法

最后\(id\)所在就是最终最大值，原因是如果存在出现次数超过一半的，他一定不会被消到0，否则可以消到0
还有彭师傅的神奇做法，用了类似分块预处理的思想，感觉有点类似光速幂的实现，考场AC%%%

#include <bits/stdc++.h>
using namespace std;
const int M=1050;
int c[M],x[M],y[M],z[M],m,k;
inline int gan(int x)
{
	if(x&1)return (x>>1)+1;
	return x>>1;
}
signed main()
{	
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	cin>>m>>k;int sum=0;
	for(int i=1;i<=m;i++)scanf("%d",&c[i]),sum+=c[i];
	for(int i=1;i<=m;i++)scanf("%d",&x[i]);
	for(int i=1;i<=m;i++)scanf("%d",&y[i]);
	for(int i=1;i<=m;i++)scanf("%d",&z[i]);
	int n=0,s=(1<<k)-1;
	int cnt=0,id=-1;
	for(int i=1;i<=m;i++)
	{
		n=n+1;int p=x[i];
		if(!cnt)id=p,cnt=1;
		else if(id==p)cnt++;
		else cnt--;
		long long last=x[i];
		for(int j=1;j<c[i];j++)
		{		
			last=(last*y[i]+z[i])&s;
			n=n+1;p=last;
			if(!cnt)id=p,cnt=1;
			else if(id==p)cnt++;
			else cnt--;
		}
	}
	int ma=0;n=0;
	for(int i=1;i<=m;i++)
	{
		n=n+1;int p=x[i];
		if(p==id)ma++;
		long long last=x[i];
		for(int j=1;j<c[i];j++)
		{		
			last=(last*y[i]+z[i])&s;
			n=n+1;p=last;
			if(p==id)ma++;
		}
	}
	if(ma<=gan(n)){puts("0");return 0;}
	cout<<ma-(n-ma)-1<<endl;
	return 0;
}

T3.题目交流通道

数据又出锅了
先考虑没有0边的情况，如果对于两个点\(u,v\)，存在至少一个\(k\)使得\(d_{u,k}+d_{k,v}=d_{u,v}\)，那么这条路已经形同虚设，可以随便修，答案有\(K-d_{u,v}+1\)的贡献，否则只能按照要求修，贡献为1
考虑一般情况,两点之间距离为0，相当于他们就是一个点，用并查集给缩到一起，形成一种叫做"团"的神奇物质
然后答案分两部分，分别是团内部的和团之间的，对于之间的和刚才类似，相当于有重边，两边集合的\(size\)乘起来就是这里的几重边\(a\),如果存在中转点就有\((K-d_{u,v}+1)^a\)贡献，否则是\((K-d{u,v}+1)^a-(K-d_{u,v})^a\)的贡献，这个好理解，别的都不能大于他
团之间的考虑容斥，设\(g_i\)为构造\(i\)个点的图的合法方案数，\(f_i\)为构造\(i\)个点的团的方案数，那么有

\(g\)是乱连好理解，\(f\)是用所有的减不合法的，后面先钦定一个\(i\)点的合法团(f)，剩下的点内部随便连(g)，他们之间要连非0边(K的幂)，注意那个组合数之所以要减1是因为由于不能算重，所以钦定\(i\)个点的时候强制他们都与同一个点连边，相当于拿出来一个作为基准点，在整个过程中都是这样，否则由于后面乱连的时候可能有0，会造成重复
还有就是判无解，四种情况 \(d_{i,j}>K,d_{i,i}!=0,d_{i,j}!=d_{j,i},d_{i,j}>d_{i,k}+d_{k,j}\)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=405;
const int mod=998244353;
int d[N][N],n,p;
inline int ksm(int x,int y)
{
	int s=1;x%=mod;
	for(;y;y>>=1)
	{
		if(y&1)s=s*x%mod;
		x=x*x%mod;
	}
	return s;
}
inline bool check()
{
	for(int i=1;i<=n;i++)
	{
		if(d[i][i]!=0)return 0;
		for(int j=i+1;j<=n;j++)
		{
			if(d[i][j]!=d[j][i]||d[i][j]>p)return 0;
			for(int k=1;k<=n;k++)
			 if(d[i][j]>d[i][k]+d[k][j])return 0;
		}
	}
	return 1;
}
int inv[N],jc[N],jcny[N];
inline int C(int x,int y)
{
	if(x<y)return 0;
	if(!y)return 1;
	return jc[x]*jcny[y]%mod*jcny[x-y]%mod;
}
int fa[N],size[N],f[N],g[N];
inline int find(int x)
{
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
bool v[N],vv[N][N];
signed main()
{
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  scanf("%lld",&d[i][j]);
	if(!check()){puts("0");return 0;}
	inv[1]=jc[0]=jc[1]=jcny[0]=jcny[1]=1;
	for(int i=2;i<=n;i++)
	{
		jc[i]=jc[i-1]*i%mod;
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		jcny[i]=jcny[i-1]*inv[i]%mod;
	}
	for(int i=1;i<=n;i++)g[i]=ksm(p+1,C(i,2));
	f[1]=1;
	for(int i=2;i<=n;i++)
	{
		f[i]=g[i];
		for(int j=1;j<i;j++)
		 f[i]=(f[i]-f[j]*g[i-j]%mod*C(i-1,j-1)%mod*ksm(p,j*(i-j))%mod+mod)%mod;
	}
	for(int i=1;i<=n;i++)fa[i]=i,size[i]=1;
	for(int i=1;i<=n;i++)
	 for(int j=i+1;j<=n;j++)
	  if(d[i][j]==0)
	  {
	  	 int fi=find(i),fj=find(j);
	  	 if(fi==fj)continue;
	  	 fa[fi]=fj;size[fj]+=size[fi];
	  }
	int ans=1;
	for(int i=1;i<=n;i++)
	{
		int ff=find(i);
		if(v[ff])continue;
		ans=ans*f[size[ff]]%mod;	
		v[ff]=1;
	}
	for(int i=1;i<=n;i++)
	 for(int j=i+1;j<=n;j++)
	 {
	 	int f1=find(i),f2=find(j);
		if(f1==f2)continue;
		if(vv[f1][f2])continue;
		int s=size[f1]*size[f2];
		bool flag=0;
		for(int k=1;k<=n;k++)
		{
			int kk=find(k);
			if(kk==f1||kk==f2)continue;
			if(d[i][k]+d[k][j]==d[i][j]){flag=1;break;}
		}	 	
		if(flag)ans=ans*ksm(p-d[i][j]+1,s)%mod;
		else ans=(ksm(p-d[i][j]+1,s)-ksm(p-d[i][j],s)+mod)%mod*ans%mod;
		vv[f1][f2]=vv[f2][f1]=1;
	 }
	cout<<ans;
	return 0;
}

思路很好，细节和式子的处理要学习一下

T4.题目难度提升

其实没那么难，感觉题解说复杂了
要保证新放一个数之后新的中位数不仅要比之前大，而且不能大太多，要让当前最小值不比中位数小
所以你就有一种策略，用set维护，中位数可以写一个对顶堆，具体就是题解说的方法

注意最后这里的\(m\)左边是闭区间，因为后边有相同元素
如果相同的也好说，只要你在中位数左边找到两个相同的，那么他就能一直反复横跳，你一直填全局最大值——左边最大值直到左边空了为止，剩下一样，右边重了不用管，因为他们肯定不是中位数
细节还比较多，尤其是边界相关

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=100050;
struct Q{
	priority_queue <int> q1;
	priority_queue <int,vector <int>,greater<int> >q2;
	int size=0;
	inline int gan(int x)
	{
		if(x&1)return (x+1)>>1;
		return x>>1;
	}
	inline double get()
	{
		if(!size)return 0;
		if(size&1)return q2.top();
		else return (q1.top()+q2.top())/2.0;
	}
	inline void insert(int x)
	{
		if(x<get())q1.push(x);
		else q2.push(x);
		size++;
		while(q1.size()>gan(size))q2.push(q1.top()),q1.pop();
		while(q2.size()>gan(size))q1.push(q2.top()),q2.pop();
	}
}q;
int a[N],b[N];
multiset <int> s,t;
inline void de(int x)
{	
	auto it=t.find(x);
	if(it!=t.end())t.erase(it);
}
vector <int> ans;
inline void ins(int x)
{
	s.insert(x);q.insert(x);
	ans.push_back(x);de(x);
}
inline void print()
{
	for(int i=0;i<ans.size();i++)
	 printf("%lld ",ans[i]);
	exit(0);
}
signed main()
{
	freopen("d.in","r",stdin);
	freopen("d.out","w",stdout);
	int n;cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)b[i]=a[i],t.insert(a[i]);
	sort(b+1,b+1+n);double mid;
	if(n&1)mid=b[(n+1)>>1];
	else mid=(b[n>>1]+b[(n>>1)+1])/2.0;
	int pp;for(int i=n;i>=1;i--)if(b[i]<=mid&&(b[i+1]>mid||i==n)){pp=i;break;}
	for(int j=pp;j>1;j--)
	{
		if(b[j]==b[j-1])
		{
			ins(b[j]),ins(b[j-1]);
			while(t.size()&&(*t.begin())<=b[j])
			{
				ins(*t.rbegin());
				if(t.size())ins(*--t.upper_bound(b[j]));
			}
			break;
		}
	}		
	if(!s.size())ins(b[1]);
	if(ans.size()<n&&(!(ans.size()&1)))
	{
		int m=q.get();
		int l=*t.lower_bound(m);
		auto ga1=s.lower_bound(m);
		if(ga1!=s.end()&&(*ga1)<l)ins(*t.rbegin());
		else ins(l);
	}
	while(ans.size()<n)
	{
		double m=q.get();
		int k=*t.upper_bound(m);
		auto ga1=s.upper_bound(m);
		if(ga1!=s.end()&&(*ga1)<k)ins(*t.rbegin());
		else 
		{
			double r=2*k-m;
			auto ga2=s.upper_bound(m);
			if(ga2!=s.end()&&(*ga2)<=r)ins(*t.rbegin());
			else ins(*--t.upper_bound(r));
		}		
		if(ans.size()==n)print();
		m=q.get();
		int l=*t.lower_bound(m);
		ga1=s.lower_bound(m);
		if(ga1!=s.end()&&(*ga1)<l)ins(*t.rbegin());
		else ins(l);
	}
	print();
	return 0;
}

考试总结

这场该有的暴力有了，现在的问题是部分分不稳，对于T1T2这种题不好拍就不太容易保证正确性
所以还是要把基本盘保住，往上再冲一冲，像T3的60还是可以做到的
没有正解就把暴力打满，至少要占一头