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

撰写于 2020-07-16 修改于 2020-07-16 分类 ACM 标签 训练

A All with Pairs

因为是si的前缀去匹配sj的后缀，正好，AC自动机的fail指针是由后缀指向前缀，我们只需要根据fail指针反向建图，然后在从根节点去遍历， 但是只有最长的才有贡献，所以要不断地更新他的长度，当一个点根据fail指针指向另一个点时，这时可以在res上加上临时的贡献这个时候是指si到sj的匹配和sj本身对自己的匹配，最后别忘记回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define se second
#define fi first
#define pb push_back
#define mp make_pair
using namespace std;
const int N = 1e6 + 10;
const int mod =998244353;
int n;

struct ACtree {
int tr[N][26], tot;
int e[N], fail[N],len[N],c[N];
vector<int> q[N],g[N];
stack<pii> st;
ll res=0,ans=0;
void insert(char *s,int x) {
  int u = 0;
  for (int i = 1; s[i]; i++) {
    if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot;
    u = tr[u][s[i] - 'a'];
    len[u]=i;//u节点的长度
    q[u].pb(x);//看看u这个点都属于哪个字符串
  }
  e[u]++;
}

void build() 
{
    queue<int> q;
    for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]);
    while (q.size()) 
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) 
        {
            if (tr[u][i]) fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
            else tr[u][i] = tr[fail[u]][i];
        }
    }
    for(int i=1;i<=tot;i++) g[fail[i]].pb(i);
}
void dfs(int u)//遍历
{
    for(int x:q[u])
    {
        st.push(mp(x,c[x]));//放入，回溯时会用到
        res=(res-c[x]+mod)%mod;
        c[x]=1ll*len[u]*len[u]%mod;
        res=(res+c[x]+mod)%mod;
    }
    ans=(ans+1ll*res*e[u]%mod)%mod;
    for(int x:g[u])
    {
        dfs(x);//将根据fail指针建图的点遍历；
    }
    {
        for(int x:q[u])
        {
            pii tmp = st.top();
            st.pop();
            res=((res-c[tmp.fi])+mod)%mod;
            c[tmp.fi]=tmp.se;
            res=(res+c[tmp.fi]+mod)%mod;
        }
    }
}
    ll begin()
    {
        dfs(0);
        return ans;
    }

} AC; // namespace AC

char s[N];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%s", s + 1), AC.insert(s,i);
  scanf("%s", s + 1);
  AC.build();
  printf("%lld", AC.begin());
  return 0;
}

B Boundary

三个点可以确定一个圆心，因为毕竟过（0，0），所以只需要记录他的圆心，然后在找哪个圆心最多就行了(qrnb)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99


#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define read(x) scanf("%d",&x)
typedef long long ll;
typedef double dl;
using namespace std;
 
const int N=2e4+7;
const int M=1e9+7;
const int INF=0x3f3f3f3f;
 
int n,m;
 
struct poi{
    ll x,y;
}pos[N];
 
ll cnt[N];
 
vector<pair<dl,dl> > ls;
 
ll a,b,c,d,e,f;
 
inline void getCenterPos(ll x2,ll y2,ll x3,ll y3){
    ll x1=0,y1=0;
   
  dl x=((y2-y1)*(y3*y3-y1*y1+x3*x3-x1*x1)-(y3-y1)*(y2*y2-y1*y1+x2*x2-x1*x1))/(2.0*((x3-x1)*(y2-y1)-(x2-x1)*(y3-y1)));
  dl y=((x2-x1)*(x3*x3-x1*x1+y3*y3-y1*y1)-(x3-x1)*(x2*x2-x1*x1+y2*y2-y1*y1))/(2.0*((y3-y1)*(x2-x1)-(y2-y1)*(x3-x1)));
    ls.push_back({x,y});
//  printf("%lf %lf\n",x,y);
    return;
}
 
int ans=1,base=0;
 
int cal(int x){
    int sum=0;
    for(int i=1;;i++){
        sum+=i;
        if (x<sum) return i;
    }
}
 
const double eps = 1e-6;
 
bool cmp(pair<dl,dl> a,pair<dl,dl> b){
    if (abs(a.first-b.first)<eps)
        if (abs(a.second-b.second)<eps)
            return true;
    return false;
}
 
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&pos[i].x,&pos[i].y);
        if (pos[i].x==0&&pos[i].y==0){
            n--;
            i--;
            base++;
            continue;
        }
    }
     
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
//          printf("%d %d: ",i,j);
            getCenterPos(pos[i].x,pos[i].y,pos[j].x,pos[j].y);
        }
    }
    sort(ls.begin(),ls.end());
    pair<dl,dl> pre={0,0};
    int cnt=0;
    ls.push_back({0,0});
    for(auto x:ls){
//      printf("%lf %lf\n",x.first,x.second);
        if (cmp(x,pre)==true){
            cnt++;
        }
        else{
            ans=max(ans,cal(cnt));
//          cout<<cnt<<endl;
            cnt=1;
            pre=x;
        }
    }
    printf("%d",ans+base);
//  cout<<base;
}
 
int main(){
//  ios::sync_with_stdio(0);
//  cin.tie(0),cout.tie(0);
//  int T;read(T);
//  for(int i=1;i<=T;i++)
        solve();
}

C Cover the Tree

根据叶子节点去匹配就好了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define read(x) scanf("%d",&x)
typedef long long ll;
typedef double dl;
using namespace std;
 
const int N=3e5+7;
const int INF=0x3f3f3f3f;
 
int n,m;
 
int deg[N];
int fa[N];
int vis[N];
int link[N];
int ls[N],tot=0;
vector<int> G[N];
 
void dfs(int x){
    vis[x]=1;
    if (deg[x]==1){
        ls[++tot]=x;
        return;
    }
    for(auto to:G[x]){
        if (vis[to]==1) continue;
        dfs(to);
    }
    return;
}
 
void out(int a,int b){
    if (a>b) swap(a,b);
    printf("%d %d\n",a,b);
}
 
void solve(){
    scanf("%d",&n);
    int u,v;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        deg[u]++;
        deg[v]++;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if (deg[i]!=1){
            dfs(i);
            break;
        }
    }
    memset(vis,0,sizeof(vis));
    m=(tot+1)/2;
    printf("%d\n",m);
    for(int i=1,j=m+1;i<=tot/2;i++,j+=3){
        if (j>tot){
            j=m+1;
            while(vis[j]==1){
                j++;
            }
        }
//      cout<<i<<" "<<j<<endl;
        vis[i]=vis[j]=1;
        out(ls[i],ls[j]);
    }
    if (tot%2==1) out(ls[1],ls[m]);
}
 
int main(){
//  ios::sync_with_stdio(0);
//  cin.tie(0),cout.tie(0);
//  int T;read(T);
//  for(int i=1;i<=T;i++)
        solve();
}

D Duration

这个都会。

E Exclusive OR

不会

F Fake Maxpooling

这个可以用二维RMQ或者二维单调队列去写

详细的blog可以去看 https://www.luogu.com.cn/problem/solution/P2216 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#define INF 0x3f3f3f3f
#define N 5010
#pragma GCC optimize(2)
using namespace std;
deque<int> Q[N],Q2[N];
typedef long long ll;
ll mz[N][N];
ll mn[N][N],mx[N][N];
 
int a,b,n;
int main() {
 
    scanf("%d%d%d",&a,&b,&n);
    for(int i=1; i<=a; i++) {
        for(int j=1; j<=b; j++) {
             
            mz[i][j]=(1ll)*i/__gcd(i,j)*j; 
            }
    }
 
    for(int i=1; i<=a; i++) {
        for(int j=1; j<=b; j++) {
            ll now=mz[i][j];
      
            while(!Q2[i].empty() && now>=mz[i][Q2[i].back()]) Q2[i].pop_back();
            Q2[i].push_back(j);
            while(Q2[i].back()-Q2[i].front()+1>n) Q2[i].pop_front();
            if(j>=n) mx[i][j]=mz[i][Q2[i].front()];
        }
    }      
    ll ans=0;
    for(int j=n; j<=b; j++) {
        for(int i=1; i+n-1<=a; i++) {
            ll mxv=-1;
            for(int d=0; d<n; d++) mxv=max(mxv,mx[i+d][j]);
            ans+=mxv;
        }
    }
 
    printf("%lld\n",ans);
    return 0;
}

G Greater and Greater

出题人说看下数据就知道bitset（现在我还不知道为什么要用bitset），就是先用bitset在a[i]中找比b[i]大的数将其为1，顺序要按b[i]的大小，同时记录他们的位置，因为要比b数组都大，所以QQ图片20200716195216.png

满足这样就好了，b在哪个位置，就需要向右移动它本身的位置数-1这样才能满足图片上的匹配，只需要最后统计bitset有多少个1.

QQ图片20200716200717.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include<bits/stdc++.h>

using namespace std;

const int MAXN=150010,maxn=40010;

bitset<MAXN>ans,w;

int a[MAXN],b[maxn];
int c[MAXN],p[MAXN];
int n,m;
inline int cmp1(int x,int y){return a[x]>a[y];}
inline int cmp2(int x,int y){return b[x]>b[y];}
int main()
{
	
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i],p[i]=i;
	for(int i=1;i<=n;i++)
	cin>>b[i],c[i]=i;
	sort(p+1,p+1+n,cmp1);
	sort(c+1,c+1+m,cmp2);
	int flag=1;
	ans.set();
	for(int i=1;i<=m;i++)
	{
		while(a[p[flag]]>=b[c[i]]&&flag<=n)
		{
			w[p[flag]]=1;
			++flag;
		}
		ans=ans&(w>>c[i]-1);
	}
	cout<<ans.count();return 0;
}

H Happy Triangle

这个滑稽姐姐的blog写的挺好的肯定能看懂（ https://www.acwing.com/user/myspace/index/2776/ ）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

#include<bits/stdc++.h>

using namespace std;

const int N =2e5+5,inf = 0x3f3f3f3f;

vector<int> v;
int find(int x)
{
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

struct node{
    int l,r;
    int low,h1,h2,b;//low为区间中包含的最小的元素的下标（没有数时为-1）
                    //h1为区间中包含的最大的元素的下标（没有数时为-1）
                    //h2 为区间中包含的次大的元素的下标（没有数时为-1）
    int sz;//为区间中包含的元素个数
}tr[N<<4];

void build(int u,int l,int r)
{
	tr[u]={l,r,-1, -1, -1, inf, 0};
	if(l==r) return ;
	else {
		int mid=l+r>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
	} 
} 

void pushup(node &u,node &left,node &right)
{
	u.sz=left.sz+right.sz;
	if(left.sz) u.low=left.low;
	else u.low=right.low;
	int h[4]={left.h2,left.h1,right.h1,right.h2};
	sort(h,h+4);
	u.h2=h[2];
	u.h1=h[3];
	u.b = min(left.b, right.b);
	if(left.sz and right.sz) u.b=min(u.b,v[right.low]-v[left.h1]);
}
void pushup(int u)
{
	pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void modify(int u,int x,int c)
{
	if(tr[u].l==x&&tr[u].r==x)
	{
		tr[u].sz+=c;
		if(tr[u].sz<=0){
			tr[u].low=-1,tr[u].h1=-1,tr[u].h2=-1;
			tr[u].b=inf;
		}
		else if(tr[u].sz==1)
		{
			tr[u].low=x,tr[u].h1=x,tr[u].h2=-1,tr[u].b=inf;
		}
		else {
			tr[u].b=0;
			tr[u].h1=x,tr[u].h2=x,tr[u].low=x;			
		}
		return ;
	}
	int mid=tr[u].l+tr[u].r>>1;
	if(x<=mid) 	modify(u<<1,x,c);
	else 	modify(u<<1|1,x,c);
	pushup(u);
}
node query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
	else 
	{
		int mid=tr[u].l+tr[u].r>>1;
		if(r<=mid) return query(u<<1,l,r);
		else if(l>mid) return query(u<<1|1,l,r);
		else 
		{
			auto q1=query(u<<1,l,r);
			auto q2=query(u<<1|1,l,r);
			node res;
			pushup(res,q1,q2);
			return res;
		}
			
		
	}
}

int main()
{
    int op[N],x[N];
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
	{
		cin>>op[i]>>x[i];
		v.push_back(x[i]);
	}
	v.push_back(-1);
	sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());//离散化； 
	build(1,0,v.size()-1); 
	for(int i=1;i<=q;i++)
	{
		if(op[i]==1)
		{
			modify(1,find(x[i]),1);
			
			continue;
		}
		else if(op[i]==2)
		{
			modify(1,find(x[i]),-1);
			
			continue; 
		}
		else 
		{
			node q1=query(1,0,find(x[i])-1);
			if(q1.sz>=2&&v[q1.h1]+v[q1.h2]>x[i])
			{
				cout<<"Yes"<<endl;
				continue;
			}
			node q2=query(1,find(x[i]),v.size()-1);
			if(q2.sz)
			{
				q1.b=inf;
				node res;
				pushup(res,q1,q2);
				if(res.b<x[i])
				{
					cout<<"Yes"<<endl;
					continue;
				}
				
			}
			cout<<"No"<<endl;
		}
		 
	}
}

目录

  1. A All with Pairs
  2. B Boundary
  3. C Cover the Tree
  4. D Duration
  5. E Exclusive OR
  6. F Fake Maxpooling
  7. G Greater and Greater
  8. H Happy Triangle
Site by hdy using Hexo & Random

acm

Hide