2020牛客暑期多校第二场
MorphLing
7月 20, 2020
F.Fake_Maxpooling
两次单调队列维护k*k区间的最大值，滑动窗口问题。
#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=5000+5;
int T,n,m,k;
int a[N][N],ro[N][N];
int q[N],l,r;
int now;
ll tot;
int main()
{
cin>>n>>m>>k;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (!a[i][j]){
a[i][j]=i*j/__gcd(i,j);
for (int k=2;k*i<=n && k*j<=n;k++)
a[i*k][j*k]=a[i][j]*k;
}
for (int i=1;i<=n;i++)
{
l=1,r=0;
for (int j=1;j<=m;j++)
{
while(l<=r && a[i][j]>=a[i][q[r]]) r--;
q[++r]=j;
if (j>=k) {
while(q[l]<=j-k) l++;
ro[i][j]=a[i][q[l]];
}
}
}
for (int j=k;j<=m;j++)
{
l=1,r=0;
for (int i=1;i<=n;i++)
{
while(l<=r && ro[i][j]>=ro[q[r]][j]) r--;
q[++r]=i;
if (i>=k) {
while(q[l]<=i-k) l++;
tot+=ro[q[l]][j];
}
}
}
printf("%lld\n",tot);
return 0;
}
C.Cover_the_Tree
选择度数>=2的点为根跑一次dfs，按顺序记录叶子结点（dfs序），叶子结点记为$l_1,l_2,…l_s$，若s为偶数，则连接$(l_1,l_{\frac{s}{2}+1}),(l_2,l_{\frac{s}{2}+2}),…,(l_{\frac{s}{2}},l_s)$。若s为奇数，则将正中间的点与根相连。
正确性证明：考虑任意一条边，若这条边的儿子节点中，叶子结点的区间是[L,R]，
若R<$\frac{s}{2}$，则能被$(R,R+\frac{s}{2})$覆盖
若L>$\frac{s}{2}$，则能被$(L-\frac{s}{2},L)$覆盖
若都不满足，则$\frac{s}{2}$在区间[L,R]中，若L>1，则该边被$(l_1,l_{\frac{s}{2}+1})$覆盖，若R
#include<bits/stdc++.h>
#define REP(i,x,y) for (auto i=(x);i<=(y);++i)
#define DEP(i,x,y) for (auto i=(x);i<=(y);++i)
#define debug(x) cerr<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=2e5+5;
vector<int>G[N];
vector<int>ans;
int n,m,u,v,root;
void dfs(int x,int fa)
{
if (G[x].size()==1)
{
ans.push_back(x);
return;
}
for (auto to:G[x])
{
if (to!=fa)
dfs(to,x);
}
}
int main()
{
cin>>n;
if (n==2)
{
scanf("%d %d",&u,&v);
printf("1\n%d %d",u,v);
return 0;
}
REP(i,2,n) {
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
if (G[u].size()>=2 &&!root) root=u;
if (G[v].size()>=2 &&!root) root=v;
}
dfs(root,-1);
int l=0,r=(ans.size()+1)/2;
printf("%d\n",(ans.size()+1)/2);
REP(i,1,ans.size()/2) {
printf("%d %d\n",ans[l],ans[r]);
l++,r++;
}
if (ans.size()%2==1) printf("%d %d\n",root,ans[ans.size()/2]);
return 0;
}
B.Boundary
计算出每个点和原点的中垂线，两两枚举中垂线的交点，用map记录交点的重合情况。
将交点作为map键值需要重载小于号（<），判断大小关系时需要计算绝对值与eps的大小，若小于eps则视为相等，返回0（实际上任何有关浮点数的比较都必须这样操作）。
顺便备一下计算几何的板子，从求两点直线、中垂线和直线交点这些简单的开始吧。
#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
using namespace std;
const int MAXN=2e3+5;
const double eps=1e-6;
class Point {
public:
double x,y;
Point(double a=0,double b=0):x(a),y(b){}
};
class Line {
public:
bool ifk;
double k,b;
//求过两点的直线
void mkline (Point A,Point B) {
ifk=true;k=b=0;
if (A.x==B.x) {
ifk=0;
b=A.x;
} else {
if (A.y==B.y) {
k=0;
// b=(A.x+B.x)/2;
b=A.y;
} else {
k=(B.y-A.y)/(B.x-A.x);
b=A.y-k*A.x;
}
}
}
//求两点中垂线
void mkbisector (Point A,Point B) {
ifk=true;k=b=0;
if (A.x==B.x) {
k=0;
b=(A.y+B.y)/2;
} else if (A.y==B.y) {
ifk=0;
b=(A.x+B.x)/2;
} else {
k=-1/(B.y-A.y)*(B.x-A.x);
b=(A.y+B.y)/2-k*(A.x+B.x)/2;
}
}
bool operator == (Line &T) {
return (ifk==T.ifk) && fabs(k-T.k)<eps && fabs(b-T.b)<eps;
}
};
//求两直线交点
struct Intersection {
bool parallel,coincide;
double x,y;
bool operator < (const Intersection &T) const {
if (fabs(x-T.x)>eps) return x<T.x;
else if (fabs(y-T.y)>eps) return y<T.y;
else return 0;
}
};
Intersection getIntersection (Line A,Line B) {
Intersection ans;
ans.parallel=ans.coincide=0;
ans.x=ans.y=0;
if (A==B) {
ans.coincide=1;
return ans;
}
if (!A.ifk && !B.ifk || A.ifk && B.ifk && fabs(A.k-B.k)<eps) {
ans.parallel=1;
return ans;
}
if (!A.ifk && B.ifk) return getIntersection(B,A);
if (A.ifk && !B.ifk) {
ans.x=B.b;
ans.y=A.k*ans.x+A.b;
} else {
ans.x=(B.b-A.b)/(A.k-B.k);
ans.y=A.k*ans.x+A.b;
}
return ans;
}
Point p[MAXN];
Line l[MAXN];
int n,m,ans;
map<Intersection,int>CNT;
int main()
{
cin>>n;
Point ori(0,0);
for (int i=1;i<=n;i++)
{
cin>>p[i].x>>p[i].y;
l[i].mkbisector(ori,p[i]);
}
ans=1;
for (int i=1;i<=n-1;i++)
{
CNT.clear();
for (int j=i+1;j<=n;j++)
{
Intersection inter=getIntersection(l[i],l[j]);
if (!inter.coincide && !inter.parallel) CNT[inter]++;
}
for (auto it:CNT) ans=max(ans,it.second+1);
}
printf("%d\n",ans);
return 0;
}
J.Just_Shuffle
对于长度为len的环，每置换len次都会回到初始状态，因此只需要考虑t=k%len
已知{1,2,3,…,n}经过P置换k次为A，即$P^t=A$，根据题意已知A，要求出P。
令$z$使得$(zk)\%len=1$，可知$A^z=P^{tz}=P^{(zk)\%len}=P$，因此P就是A自身置换z次后的结果，且由$(zk)\%len=1$可知z是k在mod len意义下的逆元，对于一个环，每置换一次后的结果是整体旋转一位，因此只要通过求逆元的方法求出z，并将该环整体旋转z位就能得到答案。
环与环之间是独立的，因此只要分别处理序列中每个环即可。
因为这里模数不一定是质数所以不能用费马小定理快速幂求逆元。朴素的O(n)求法应该都可以。
#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N];
int ans[N];
int n,m,k;
int main()
{
cin>>n>>k;
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
{
if (!ans[i])
{
vector<int>G;
ll now=i,cnt=0;
G.push_back(now);
now=a[now];
while(now!=i)
{
G.push_back(now);
now=a[now];
}
int sz=G.size();
if (sz==1) { ans[i]=a[i];continue; }
ll inv;
for (int i=1;i<=sz;i++)
{
if (1ll*i*k%sz==1)
{
inv=i;break;
}
}
for (int j=0;j<sz;j++)
ans[G[j]]=G[(j+inv)%sz];
}
}
for (int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
A.All-with-Pairs
可以通过map记录所有后缀出现的次数，并对每个前缀都计算它出现在后缀的次数，复杂度O(n)。但需要考虑到重复计算的情况（比如每当aba前后缀匹配时，会有一个a被重复计算）。
解决方法是预处理出类似于kmp算法中的nxt数组，从前往后扫一遍cnt[nxt[j]]-=cnt[j]。细节要扣清楚还是挺麻烦的。
使用map时不能直接将string作为键值（会爆内存），需要对字符串取不同的参数做两次哈希，把一对哈希值作为键值。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int MAXN=1e6+5,MOD=998244353,MOD1=998244353,MOD2=1e9+7;
const int b1=131,b2=29;
ll base1,base2;
int n;
string s[MAXN];
map<pii,int>CNT;
int cnt[MAXN],nxt[MAXN];
ll ans;
void getNext(string &s,int *nxt)//求失配nxt
{
nxt[0] = -1;
for (int i=1,j=-1;i<=s.length();i++)
{
while(j!=-1 && s[i-1]!=s[j]) j=nxt[j];
nxt[i]=++j;
}
}
ll hashv1,hashv2;
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>s[i];
base1=1,base2=1,hashv1=hashv2=0;
for (int j=s[i].length()-1;j>=0;j--)
{
hashv1=((1ll*(s[i][j])*base1)%MOD1+hashv1)%MOD1;
base1=(1ll*base1*b1)%MOD1;
hashv2=((1ll*(s[i][j])*base2)%MOD2+hashv2)%MOD2;
base2=(1ll*base2*b2)%MOD2;
CNT[{hashv1,hashv2}]++;
}
}
for (int i=1;i<=n;i++)
{
hashv1=hashv2=0;
for (int j=0;j<s[i].length();j++)
{
hashv1=((1ll*hashv1*b1)+(s[i][j]))%MOD1;
hashv2=((1ll*hashv2*b2)+(s[i][j]))%MOD2;
cnt[j+1]=CNT[{hashv1,hashv2}];
}
getNext(s[i],nxt);
for (int j=1;j<=s[i].length();j++)
{
cnt[nxt[j]]-=cnt[j];
}
for (int j=1;j<=s[i].length();j++)
{
ans=(ans+((1ll*cnt[j]*j)%MOD*j)%MOD)%MOD;
cnt[j]=0;
}
}
printf("%lld\n",ans);
return 0;
}
G.Greater-and-Greater
本质上是dp。用dp[i][j]表示$\forall k \in[0,m]$满足$a_{i+k}>b_{j+k}$ (考虑$[a_i,a_{i+1},…,a_{i+m-j}]和[b_j,b_{j+1},…,b_{m}]$)
画张图表示一下，dp[i][j]=1就表示第一段的每一位都大于等于第二段：
接下来考虑转移，在已知dp[i][j]=1的情况下，要确定dp[i-1][j-1]（即图中的三、四两段），只需要再比较a[i-1]和b[i-1]的大小即可
写成代码就是
if (dp[i][j] && a[i-1]>=b[j-1]) dp[i-1][j-1]=1;
最后只要统计dp[i][1]的数量就是答案了。
但如果用常规方法来实现这个dp，无论空间还是时间上都是不可做的，然而bitset可以。（bit比bool节约八倍空间，位运算节约时间）思想其实就是上面dp的思路，只不过要实现出来真的只能说是神仙操作。
#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
using namespace std;
const int N=1.5e5+5,M=4e4+5;
bitset<M>cur,S[M],ns,I;
int T,n,m,ans;
int A[N],B[M],ord[M];
int fd(int x)
{
int l=0,r=m;
while(l<r)
{
int mid=(l+r)>>1;
if (B[ord[mid+1]]<=x)
l=mid+1;
else r=mid;
}
return l;
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++) scanf("%d",&A[i]);
for (int i=1;i<=m;i++)
{
scanf("%d",&B[i]);
ord[i]=i;
}
sort(ord+1,ord+1+m,[&](int u,int v){
return B[u]<B[v];
});
for (int i=1;i<=m;i++)
{
S[i]=S[i-1];
S[i].set(ord[i]);
}
I.set(m);
for (int i=n;i>=1;i--)
{
ns=S[fd(A[i])];
cur=((cur>>1)|I)&ns;
if (cur[1]) ans++;
}
printf("%d\n",ans);
return 0;
}