7.6 模拟赛

, , , ,

Day 3

T1. rail

Description

$n,m\le 10^5$

1s 512MB

Solution

正着做会有问题，考虑反着做。（有人可能会问为什么有问题？找几个刁钻数据手玩一下，我不想写了）

记录每个区间向左一步可以到达（即右端点在这个区间内的）的最左端。然后倍增。倒数第二步的时候特判。细节看代码。

Code

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,m;
int f[maxn][21];
struct node{
	int l,r,id;
}a[maxn],b[maxn];  
inline bool cmp(node x,node y) {return x.l<y.l;}
int minn[maxn][21],g[maxn],tot,lg[maxn];
inline int query(int l,int r) {
	int z=lg[r-l+1];
	if (b[minn[l][z]].l<b[minn[r-(1<<z)+1][z]].l) return minn[l][z];
	else return minn[r-(1<<z)+1][z];
}
signed main(void){
  	freopen("rail.in","r",stdin);
	freopen("rail.out","w",stdout);
	int i,j,x,y,tmp1,tmp2;
	read(n);read(m);
	for (i=1;i<=n;i++) {
		read(a[i].l),read(a[i].r),a[i].id=i;
		g[++tot]=a[i].l;g[++tot]=a[i].r;
	}
	sort(g+1,g+1+tot);
	tot=unique(g+1,g+1+tot)-g-1;
	for (i=1;i<=n;i++) a[i].l=lower_bound(g+1,g+1+tot,a[i].l)-g,a[i].r=lower_bound(g+1,g+1+tot,a[i].r)-g;
	for (i=1;i<=n;i++) b[i]=a[i];
	b[0].l=1e9;
	sort(a+1,a+1+n,cmp);
	for (i=1;i<=n;i++) 
		if (b[minn[a[i].r][0]].l>a[i].l) minn[a[i].r][0]=a[i].id;
	for (i=2;i<=tot;i++) lg[i]=lg[i/2]+1;
	
	for (j=1;j<=20;j++) {
		for (i=1;i+(1<<j)-1<=tot;i++) {
			if (b[minn[i][j-1]].l<b[minn[i+(1<<j-1)][j-1]].l) minn[i][j]=minn[i][j-1];
			else minn[i][j]=minn[i+(1<<j-1)][j-1];
		}
	}
	for (i=1;i<=n;i++) {
		int x=query(a[i].l,a[i].r);
		if (x<0||a[i].l<=b[x].l) f[a[i].id][0]=0;
		else f[a[i].id][0]=x;
	}
	for (j=1;j<=20;j++) {
		for (i=1;i<=n;i++) {
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
	while (m--) {
		read(x),read(y);
		if (b[y].r<b[x].r) {puts("impossible");continue;}
		if (x==y) {puts("0");continue;} 
		int ans=0;
		for (int i=20;i>=0;i--) {
			if (f[y][i]&&b[f[y][i]].l>b[x].l) y=f[y][i],ans+=(1<<i);
		}
//		gdb(f[y][0],b[f[y][0]].l,b[x].l,b[x].r);
//      y=(1 3) x=(2 3) 根本没有 f[y][0] 就ji了 
//		if (b[f[y][0]].l>b[x].r) {puts("impossible");continue;}
		if (b[y].r>=b[x].r&&b[y].l<=b[x].r) printf("%d\n",ans+1);
		else {
			y=f[y][0];
			if (b[y].r>=b[x].r&&b[y].l<=b[x].r) printf("%d\n",ans+2);
			else puts("impossible");
		}
	}
	return 0;
}

T2. wifi

Description

有 $n$ 个点，每个点的权值为 $w_i$。可以选择一些点。每个点的贡献是左右两个最近的被选的点的权值和。求权值和最大。

$n\le 2\times 10^6$

1s 512MB

Solution

很妙的一道题。

考虑 $n^2$ dp，$f[i]=\max f_i+(i-j)*(w_i+w_j)$，$1$ 和 $n$ 必须选。

观察到本质上是把每个点抽象成 $(i,w_i)$ ，选出一些点，求相邻两个与 $x$ 轴构成的梯形的面积之和最大。模拟一下，这些点即为原图的上凸包。

Code

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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 2000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int f[maxn],w[maxn],n,ans;
namespace STD{
	int q[maxn],head,tail;
	int ans;
	struct node{
		int x,y;
	}a[maxn];
	int stac[maxn];
	inline double cross(node x,node y) {return 1.0*(x.y-y.y)/(x.x-y.x);}
	inline void main(void) {
		int i;
		int tot=0;
		for (i=1;i<=n;i++) a[i].x=i,a[i].y=w[i];
		for (i=1;i<=n;i++) {
			while (tot>=2&&cross(a[stac[tot]],a[stac[tot-1]])<cross(a[i],a[stac[tot]])) tot--;
			stac[++tot]=i;
		} 
		for (i=2;i<=tot;i++) ans+=(a[stac[i]].x-a[stac[i-1]].x)*(a[stac[i]].y+a[stac[i-1]].y);
		printf("%lld",ans); 
	}
}
signed main(void){
  	freopen("wifi.in","r",stdin);
    freopen("wifi.out","w",stdout); 
	int i,j;
	read(n);
	for (i=1;i<=n;i++) read(w[i]);
	STD::main();
	return 0;
}

T3. chatnoi

Description

$n,q\le 5\times 10^5,k\le 10$

3s , 512MB

Solution

把每连续 $k$ 个单词抽象成一个点，每个似然度为一条边。后面加一个单词为一个转移。这样建出来一张图。

对于每一次询问，就是从这个点（没有点就是 $0$）出发，至少经过 $m$ 条边的路径上的最小值的最大值。如果在一个大小不为 $1$ 的强连通分量（或者有自环），就可以走无数次。

一个很重要的性质，就是所有边的边权之和为 $n$。这种边的种类只有 $\sqrt n$ 种。对每种边的边权构成的图跑答案。查询时二分即可。这样的复杂度为 $O(n\sqrt n)$

另外的一种想法，就是大于等于 $i$ 的边权最多只有 $\dfrac{n}{i}$ 种，复杂度是调和级数 $O(n\log n)$。

但事实上，上面的跑不满，所以跑的更快。

Code

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 500005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,k,q;
string s;
map<string,int>mp;
int w[maxn],cnt,cnt2;
map<int,int>O[maxn];
map<pair<ll,ll>,int>g;
const int mod=1e9+7,base=37,base2=41,mod2=998244353;
int head=1,h[maxn];
struct yyy{
	int to,z;
	inline void add(int x,int y) {
		to=y;z=h[x];h[x]=head;
	}
}a[maxn*2];
struct edges{int x,y,w;}e[maxn];
inline bool cmp(edges x,edges y) {return x.w>y.w;}
#define fi first
#define se second
int enums,now;
int dfn[maxn],low[maxn],stac[maxn],tot,vis[maxn],times;
int v[maxn],id[maxn],idnum;
vector<int>to[maxn];
int dccnums,dcc[maxn],siz[maxn],f[maxn],Max[maxn];
inline void tarjan(int x,int pre) {
	int i;
	dfn[x]=low[x]=++times;vis[x]=1;stac[++tot]=x;
	for (i=h[x];i;i=a[i].z)  {
		if (!dfn[a[i].to]) {
			tarjan(a[i].to,x);
			low[x]=min(low[a[i].to],low[x]);
		}
		else if (vis[a[i].to]) low[x]=min(dfn[a[i].to],low[x]);
	}
	if (low[x]==dfn[x]) {
		++dccnums;
		while (1) {
			vis[stac[tot]]=0;
			dcc[stac[tot]]=dccnums;
			siz[dccnums]++;
			if (stac[tot--]==x) return ;
		}
	} 
}
inline void add(int x) {if (!v[x]) id[++idnum]=x,v[x]=1;}
struct node{
	int x,w;
	bool operator <(const node &a) const {return w<a.w;}
};
vector<node>Ans[maxn];
int len[maxn],flag[maxn];
inline void solve(int minn) {
	int i,x,j;
	int las=now; 
	while (now<enums&&e[now+1].w>=minn) now++,a[++head].add(e[now].x,e[now].y),add(e[now].x),add(e[now].y);
	if (now==las) return ;
	dccnums=0;
	for (i=1;i<=idnum;i++) {
		x=id[i];
		dfn[x]=low[x]=vis[x]=dcc[x]=stac[i]=0;
		siz[i]=f[i]=0;to[i].clear();
	}
	for (i=1;i<=idnum;i++) if (!dfn[id[i]]) tarjan(id[i],0);
	for (i=1;i<=idnum;i++) {
		for (j=h[id[i]];j;j=a[j].z) 
			if (id[i]==a[j].to) siz[dcc[id[i]]]++;
			else if (dcc[id[i]]!=dcc[a[j].to]) 
				to[dcc[a[j].to]].push_back(dcc[id[i]]);
	}
	for (i=1;i<=dccnums;i++) {
		if (siz[i]>1) f[i]=5e5;
		for (auto y:to[i]) f[y]=max(f[y],f[i]+1);
	}
	for (i=1;i<=idnum;i++) {
		x=id[i];
		Ans[x].push_back((node){minn,f[dcc[x]]}),len[x]++;
	}
}
pair<ll,ll>c[maxn];
vector<int>cc;
signed main(void){
//	freopen("GB-04.in","r",stdin);
	freopen("chatnoi.in","r",stdin);
  	freopen("chatnoi.out","w",stdout);
	int i,j,nums,tmp;ll sum1,sum2,sum;
	cin.tie(0);std::ios::sync_with_stdio(0);
	cin>>n>>k;
	for (i=1;i<=n;i++) {
		cin>>s;
		if (!mp[s]) mp[s]=++cnt;
		w[i]=mp[s];
	}
	for (i=1;i<=n-k+1;i++) {
		sum1=0,sum2=0;
		for (sum=0,j=i;j<=i+k-1;j++) sum1=(sum1*base+w[j])%mod,sum2=(sum2*base2+w[j])%mod2;
		c[i]=make_pair(sum1,sum2);
		if (!g[c[i]]) g[c[i]]=++cnt2;
	}
	for (i=1;i<=n-k;i++) O[g[c[i]]][g[c[i+1]]]++;
	for (i=1;i<=cnt2;i++) {
		for (auto tmp:O[i]) {
			++enums;
			e[enums].x=i;
			e[enums].y=tmp.fi;
			e[enums].w=tmp.se;
		} 
	}
	sort(e+1,e+1+enums,cmp);
	for (i=n;i>=1;i--) solve(i);
	cin>>q;
	while (q--) {
		cin>>nums;sum=0;
		sum1=0,sum2=0;
		for (i=1;i<=k;i++) cin>>s,sum1=(sum1*base+mp[s])%mod,sum2=(sum2*base2+mp[s])%mod2;
		sum=g[make_pair(sum1,sum2)];
		if (sum==0) {puts("0");continue;}
		auto it=lower_bound(Ans[sum].begin(),Ans[sum].end(),(node){0,nums});
		if (it==Ans[sum].end()) puts("0");
		else printf("%d\n",(*it).x); 
	}
	return 0;
}

T4. snow

P8182 有点难，待补。