此博客停更

真不该作选了场$div1$打，你tm有空打vp怎么不去填坑！

这场的感觉十分玄妙，现场的话估计不会写$C$会去插人

$Claris$都是看了$C$和$D$然后决定跑不跑路...然而我太弱了就按$A$->$B$->$C$的顺序做下去

A. GCD Table

题意是给你一个$n×n$的矩阵，这个矩阵是由一个长度为$n$的数列$g_{ij}=gcd(a_{i},a_{j})$这样起来的，随机顺序给出这个矩阵里的每个数，让你还原数组$a$

这题感觉很不错，有很多优美的东西，比如要求的数组$a$就是对角线上的数

给出的数由于是矩阵所以重复了一遍，于是把重复的去掉

矩阵里最大的那个数一定是原数组里最大的数，次大的也一定是次大的，但是第三大就说不准了，可能是次大和最大的$gcd$

然后就有很显然的做法，每次取出剩下里最大的，然后把这个与之前确定的数都取个$gcd$，这些$gcd$累计一下等下一次出现那么跳过，一直做下去就能得到原数组了

想到是$div2$的$C$，果断直接写了，随便想一下就能证明这个是对的吧

#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define ll long long
int i,j,k,m,n,x,a[510*510],y,d[510],cnt;priority_queue<int>q;
map<int,int>mp;
int main(){
	for(cnt=0,n=read(),i=1;i<=n*n;++i)a[i]=read(),++mp[a[i]];
	for(i=1;i<=n*n;++i){
		int o=mp[a[i]]+1>>1;
		for(j=1;j<=o;++j)q.push(a[i]);
		mp[a[i]]=-1;
	}
	mp.clear();
	while(!q.empty()){
		int now=q.top();q.pop();
		while(mp[now]&&!q.empty())--mp[now],now=q.top(),q.pop();
		if(!mp[now]){
			for(i=1;i<=cnt;++i)++mp[__gcd(d[i],now)];
			d[++cnt]=now;
		}
	}
	for(i=1;i<=n;++i)printf("%d ",d[i]); 
}

B. Once Again...

给你一个长度为$n$的序列，然后重复$T$次，就是$a_{n+i}=a_{i}$，然后在这个长度是$n×T$的序列里求最长不下降子序列

注意到数据范围$n<=100$和$a_{i}<=300$就觉得突破口肯定在这里，然后开始猜结论，在辣么长的序列里，最长不下降子序列是怎样的呢。。应该是什么先上升，然后一直一个数不变吧，因为只有$300$，然后再变大？诶我写写看

先把串长变成$n^2$，然后搞出每个位置前面最多多长，后面最多多长然后加一下再加上这个数重复的次数。。过样例了然后交$WA6$，觉得不会来了

然后发现大小写弄错了嘿嘿嘿

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
int i,j,k,m,n,x,y,a[110*110],t,T,sm[310],len,f[110*110],g[110*110],ans;
int main(){
	for(n=read(),T=read(),i=1;i<=n;++i)a[i]=read(),++sm[a[i]];
	for(len=min(T,n)*n,i=n+1;i<=len;++i)a[i]=a[(i-1)%n+1];
	for(i=1;i<=len;f[i]=t+1,++i)for(t=0,j=1;j<i;++j)if(a[j]<=a[i])t=max(t,f[j]);
	for(i=len;i>=1;g[i]=t+1,--i)for(t=0,j=len+1;j>i;--j)if(a[j]>=a[i])t=max(t,g[j]);
	if(n*T<=len)for(i=1;i<=n*T;++i)ans=max(ans,f[i]+g[i]-1);
	else for(i=1;i<=len;++i)ans=max(ans,f[i]+g[i]-1+sm[a[i]]*(T-n));
	printf("%d\n",ans);
}

C. Superior Periodic Subarrays

好题，给你一个数列。。找到连续的子序列使得从那个子序列的位置开始重复叠加子序列叠加出来的子序列每位都比原序列上的数大，问有多少这样的子序列（语死早

设序列长度为$s$，辣么需要满足$a_{i}>=a_{i+k*n}$和$a_{i}>=a_{i+k*s}$那也就是满足$a_{i}>=a_{i+k*(d=gcd(s,n))}$

然后枚举$d$，求出$f_{i}$表示$i$结尾最长能有多长，满足条件的$a_{i}$显然要是一些数里的最大值，再求出$1~i$中$gcd$上$n$等于$d$的数的个数$cnt_{i}$，贡献就是$cnt_{f_{i}}$

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 400020
#define ll long long
int i,j,k,m,n,x,y,a[N],cnt[N],f[N],mx[N];bool vis[N];ll ans;
inline void solve(int d){
	memset(vis,0,sizeof vis),memset(mx,0,sizeof mx),memset(cnt,0,sizeof cnt);int i;
	for(i=0;i<d;++i){
		for(int j=i;j<(n<<1);j+=d)mx[i]=max(mx[i],a[j]);
		for(int j=i;j<(n<<1);j+=d)if(a[j]==mx[i])vis[j]=1;
	}
	for(f[0]=vis[0],i=1;i<(n<<1);++i)(f[i]=vis[i]?f[i-1]+1:0),f[i]=min(f[i],n-1);
	for(i=d;i<n;i+=d)cnt[i]=(__gcd(n,i)==d);
	for(i=1;i<n;++i)cnt[i]+=cnt[i-1];
	for(i=n;i<(n<<1);++i)ans+=cnt[f[i]];
}
int main(){
	for(n=read(),i=0;i<n;++i)a[i+n]=a[i]=read();
	for(i=1;i<n;++i)if(n%i==0)solve(i);
	printf("%I64d\n",ans);
}

D. Number of Binominal Coefficients 没看过

E. Boolean Function 没看过

还是回去乖乖打$div2$吧

loading..