2020牛客暑期多校训练营（第二场）

wenzhuan

发布于 2022-08-15 12:28:39

2780

发布于 2022-08-15 12:28:39

文章被收录于专栏：你会烧尽还是结冰

7.13 补了好多好多题的牛客2

A-All with Pairs

题意

定义函数 f(s,t) 为 s 前缀和 t 后缀的最长相同长度。给定 n 个串，求两两 f 和。

思路

对每个前缀后缀进行哈希，计算每个前缀对应的后缀有几个，但是直接算有重复，要靠 next 去重（题解讲得挺清楚的其实）。

坑点

卡单模数哈希，气死了，贴了双哈希代码，堂堂正正过题好吧

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 5;
const int mod = 998244353;
const ll inf = 1e9;
int seed[2]={18052103,27174403},bas[2][maxn];
ll hs[maxn];
char s[maxn];
int len[maxn],ind[maxn],nex[maxn],sub[maxn];
map<ll,int>aaa;
int solve(){
    int n,ans(0); sc(n); ind[1]=bas[0][0]=bas[1][0]=1;
    rep(j,0,2) rep(i,1,maxn) bas[j][i]=1ll*bas[j][i-1]*seed[j]%mod;
    rep(i,1,n+1){
        scs(s+ind[i]);
        len[i]=strlen(s+ind[i]);
        ind[i+1]=ind[i]+len[i];
        ll th[2]={0,0}; dep(j,len[i]-1,0){
            rep(k,0,2){
                th[k]=1ll*th[k]*seed[k]%mod+(s[j+ind[i]]-'a'+1);
                if(th[k]>=mod) th[k]-=mod;
            } aaa[th[0]*inf+th[1]]++;
        } mst(th,0); rep(j,0,len[i]){
            rep(k,0,2){
                th[k]+=1ll*bas[k][j]*(s[j+ind[i]]-'a'+1)%mod;
                if(th[k]>=mod) th[k]-=mod;
            } hs[ind[i]+j]=th[0]*inf+th[1];
        }
    }
    rep(i,1,n+1){
        int k=0,tl=len[i]; nex[ind[i]]=0;
        rep(j,ind[i]+1,ind[i+1]){
            while(k&&s[j]!=s[k+ind[i]]) k=nex[k+ind[i]-1];
            if(s[j]==s[k+ind[i]]) k++; nex[j]=k;
        }
        dep(j,ind[i+1]-1,ind[i]){
            ans+=1ll*(aaa[hs[j]]-sub[j])*tl%mod*tl%mod;
            if(ans>=mod) ans-=mod; tl--;
            sub[nex[j]+ind[i]-1]+=aaa[hs[j]]; // 直接减也会减重复
        }
    } return pf("%d\n",ans);
}
int main(){
    /* int _; sc(_); while(_--) */ solve();
}

B-Boundary

题意

给定 n 个点，问最多有几个点能在过原点的同一个圆上。

思路

先枚举一个点 P ，再枚举所有点 A ，根据角度和 A 相对 OP 位置统计个数，取最大值。

坑点

mx 初始值要 1 ，保证至少有一个点。我代码在一个点/全部点共线的情况执行不到 mx 的赋值
(double)tmp1 / tmp2 不要写成 1.0 * tmp1 / 1.0 * tmp2（小庄血泪之痛呜呜呜）

代码

#include<bits/stdc++.h>
#define pf printf
#define scl(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
struct point{
    ll x,y,d;
}p[2005];
void solve(){
    ll n,mx=1; scl(n); rep(i,0,n){
        ll x,y; scl(x),scl(y);
        p[i].x=x,p[i].y=y;
        p[i].d=x*x+y*y;
    } rep(i,0,n){
        map<double,ll>aaa;
        rep(j,0,n){
            if(i==j) continue;
            ll cr=p[i].x*p[j].y-p[j].x*p[i].y;
            if(!cr) continue; cr=cr<0?-1:1;
            ll tx=p[i].x-p[j].x;
            ll ty=p[i].y-p[j].y;
            ll dt=tx*tx+ty*ty; // |AP|
            ll del=p[j].d+dt-p[i].d,re=4ll*dt*p[j].d; // 余弦定理
            ll op=del<0?-1:del?1:0,ff=1;
            ff=op*cr==1?-1:op*cr?1:0; del*=ff*del;
            double tt=(double)del/re;
            ll res=++aaa[tt];
            mx=max(mx,res+1);
        }
    } pf("%lld\n",mx);
}
int main(){
    /* int _; sc(_); while(_--) */ solve();
}

C-Cover the Tree

题意

给定一棵树，用最少的链覆盖树的每一条边（不同链可重叠，可只覆盖一个点）。

思路

最少的链数一定是叶节点两两相连，所以最少链数为（叶节点数 +1 ）/2 。然后难就难在怎么将叶节点两两配对，看了题解意识到可以用 DFS 序，将叶节点按 DFS 序排列后分为前后两半按顺序配对就可以啦√

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
int in[maxn],q[maxn],vis[maxn];
vector<int>vv;
int solve(){
    srand(time(0));
    int n; sc(n); rep(i,1,n){
        int u,v; sc(u); sc(v);
        in[u]++; in[v]++;
    } if(n==1) return pf("1 1\n");
    rep(i,1,n+1) if(in[i]==1)
        vv.push_back(i);
    int sz=vv.size(),cnt(0);
    rep(i,0,sz){
        int t=rand()%sz;
        while(vis[t]) t=rand()%sz;
        q[cnt++]=vv[t];
        vis[t]++;
    }
    pf("%d\n",(sz+1)/2);
    rep(i,0,sz){
        pf("%d %d\n",q[i],q[i+1]);
        if(sz%2&&!i) continue; i++;
    } return pf("\n");
}
int main(){
    /* int _; sc(_); while(_--) */ solve();
}

D-Duration

题意

求秒数差

思路

乘一下加一下减一下

代码

#include<bits/stdc++.h>
#define pf printf
using namespace std;
int solve(){
    int a,b,c,t1,t2;
    scanf("%d:%d:%d",&a,&b,&c);
    t1=a*3600+b*60+c;
    scanf("%d:%d:%d",&a,&b,&c);
    t2=a*3600+b*60+c;
    return pf("%d\n",abs(t1-t2));
}
int main(){
    /* int _; sc(_); while(_--) */ solve();
}

E-Exclusive OR

题意

给定长度 n 的数组 a ，求选择 1-n 个数时最大异或和。

思路

数据范围在 2^{18} ，所以 i\geq 20 时有 ans[i]=a[i-2]。前 20 个用异或卷积求（但 fwt 我可能也讲不来）。

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 2e5 + 5;
const int N = 1 << 18;
int a[N],b[N],ans[maxn];
void fwt_xor(int *a,int op){
	for(int i=1;i<N;i<<=1)
		for(int j=0;j<N;j+=i<<1)
			for(int k=0;k<i;++k){
				int x=a[j+k],y=a[i+j+k];
				a[j+k]=x+y,a[i+j+k]=x-y;
				if(op==-1) a[j+k]/=2,a[i+j+k]/=2;
			}
} 
void solve(){
    int n; sc(n); rep(i,1,n+1){
        int t; sc(t); a[t]=1;
    } fwt_xor(a,1); b[0]=1;
    rep(i,1,20){
        fwt_xor(b,1);
        rep(j,0,N) b[j]*=a[j];
        fwt_xor(b,-1);
        rep(j,0,N) if(b[j]) ans[i]=j,b[j]=1;
    } rep(i,20,n+1) ans[i]=ans[i-2];
    rep(i,1,n+1) pf("%d ",ans[i]);
}
int main(){
    /* int _; sc(_); while(_--) */ solve();
}

F-Fake Maxpooling

题意

给定一矩阵 A ，其中第 (i, j) 位上对应的数字是 lcm(i, j) ，求对于整个矩阵中的每个k×k大小的子矩阵中最大值之和。

思路

首先对矩阵进行预处理，直接暴力求的复杂度是 O(nmlogn)，看题解之后用线性方法优化到了 O(nm) 。然后滑动窗口对 A 的每一行求出区间 (j-k,j) 的最大值（利用单调队列进行求解），并储存在 g[i,j] 中（因为这题内存卡的比较紧，所以重复利用了一下之前的 g 数组），然后对纵向用同样的方式求出 (g[i-k][j],g[i][j]) 的最大值，所得的结果就是子矩阵的最大值，然后求个和答案就出来啦。

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
int a[5005][5005],q[5005*5005];
int solve(){
    int n,m,k; sc(n); sc(m); sc(k); ll ans(0);
    rep(i,1,n+1) rep(j,1,m+1) a[i][j]=i/__gcd(i,j)*j;
    if(k==1) rep(i,1,n+1) rep(j,1,m+1) ans+=a[i][j];
    if(k==1) return pf("%lld\n",ans);
    q[0]=1e9; rep(i,1,n+1){
        int l=1,r=0; rep(j,1,m+1){
            while(a[i][j]>q[r]) --r;
            q[++r]=a[i][j];
            while(r-l+1>k) l++;
            a[i][j]=q[l];
        }
    }
    rep(j,k,m+1){
        int l=1,r=0; rep(i,1,n+1){
            while(a[i][j]>q[r]) --r;
            q[++r]=a[i][j];
            while(r-l+1>k) l++;
            a[i][j]=q[l];
            if(i>=k) ans+=1ll*a[i][j];
        }
    } return pf("%lld\n",ans);
}
int main(){
    /* int _; sc(_); while(_--) */ solve();
}

G-Greater and Greater

题意

给定长度为 n 的数组 a 和长度为 m 的数组 b ，问 a 有几个长度为 m 的连续子段满足任意 a_{l+i}>b_i

思路

考虑用 bitset 且反向求解。将 a 、b 排序后，枚举 b[i] ，cur 维护 a 中小于 b[i] 的下标，右移对应位数-1 得到在 a 中的状态，或起来得到 ans 。最后计算在 1 ~ (n-m+1) 中 ans 为 0 的个数。

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
pii a[maxn],b[maxn];
bitset<maxn>ans,cur;
#define f first
#define s second
int solve(){
    int n,m; sc(n); sc(m); 
    rep(i,1,n+1) sc(a[i].f),a[i].s=i;
    rep(i,1,m+1) sc(b[i].f),b[i].s=i;
    sort(a+1,a+n+1); sort(b+1,b+m+1);
    int k=1; rep(i,1,m+1){
        while(k<=n&&a[k].f<b[i].f)
            cur.set(a[k].s),k++;
        ans|=cur>>(b[i].s-1);
    } int cnt(0);
    rep(i,1,n-m+2) if(!ans[i]) cnt++;
    return pf("%d\n",cnt);
}
int main(){
    /* int _; sc(_); while(_--) */ solve();
}

J-Just Shuffle

题意

给一个数组 a 求置换 k 次能得到 a 的数组，k 是大质数。

思路

找出 a 的所有环，对每个环求逆元。

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn],ans[maxn],vis[maxn];
void solve(){
	int n,k; sc(n); sc(k);
    rep(i,1,n+1) sc(a[i]);
    rep(i,1,n+1) if(!vis[i]){ 
        vector<int>vv; int q=a[i],cnt(0); // 找环
        while(!vis[q]) vv.push_back(q),vis[q]++,q=a[q];
        int sz=vv.size(),inv; rep(j,0,sz)
            if(1ll*k*j%sz==1) inv=j;
        rep(i,0,sz) ans[vv[i]]=vv[(i+inv)%sz];
    } rep(i,1,n+1) pf("%d ",ans[i]);
}
int main(){
	/* int _; sc(_); while(_--) */ solve();
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度