6月26号下午跟队友打了次virtual test，算是训练吧，把题改一下
按通过数从高到低来写吧
A. Gratitude
一句话题意
给定3n个字符串和参数K，输出这些字符串中出现次数最多的前K个；出现次数相同的字符串，输出最后一次出现最晚的一个。
1≤K≤3N≤100,000
解法
对每个字符串以出现次数为第一关键字，最后一次出现在何时为第二关键字，从大到小进行排序，输出前K个即可
复杂度O(nlogn)
代码
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 <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <unordered_map>
#include <vector>
using namespace std;
#define pa pair<int,int>
typedef long long ll;
template<typename T>void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=(c=='-');c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}
const int maxn=100000+100,maxlen=50+5;
int n,K;
unordered_map<string,pa> mp;
string str[maxn*3];
bool cmp(const pa &a,const pa &b)
{
return a>b;
}
int main()
{
read(n),read(K);
char s[maxlen];
n*=3;
for(int i=0;i<n;i++)
{
gets(s);
pa &t=mp[str[i]=s];
t.first++;
t.second=i;
}
vector<pa> ar;
for(auto i:mp)
ar.push_back(i.second);
sort(ar.begin(),ar.end(),cmp);
K=min(K,(int)ar.size());
for(int i=0;i<K;i++)
printf("%s\n",str[ar[i].second].c_str());
return 0;
}
|
这题是队友过的，这段代码有相当一部分参考了他当时的代码
以前甚少了解更高级的STL用法，之后要好好亮一下这部分科技树了
E. Cakes
不太明白为什么这个题过的人数比A少
一句话题意
n种原料，给定制作一个蛋糕所需要的各种原料的量ai和现有的量bi，求最多能做多少个蛋糕
n≤10
解法
输出min{aibi}
代码
略
K. Unique Activities
改着改着居然把队友的AC代码hack了
不过是小问题
一句话题意
给定字符串，找到字符串中最短的仅出现了一次的子串。若有多个这样的串，输出最早出现的一个
n≤300000
解法
为了改这个题重新亮了后缀数组的科技树
首先，倍增求出后缀数组和height数组
这里称suffix[i]表示以i为起点的后缀
以sa[i]为起点的自出现了一次的串长度应该为maxj=i{lcp(suffix[i],suffix[j])}+1
亦即maxj=i{min{height[j+1]…height[i]}(j<i),min{height[i+1]…height[j]}(j>i)}
进一步地，当j<i时，j减小不会使答案更优；
同理j>i时，j增大也不会使答案更优
于是以sa[i]为起点的只出现了一次的串的长度即为max{height[i],height[i+1]}
扫描height数组，找到最小的串长度即可。若有多个，将起始位置更新为最小的那个
复杂度O(nlogn)
代码
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
| #include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
template<typename T>void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=(c=='-');c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}
const int INF=0x7f7f7f7f;
const int maxn=300000+100;
int n,m;
char s[maxn];
int sa[maxn],rnk[maxn],tp[maxn],height[maxn];
int c[maxn];
void Sort()
{
for(int i=0;i<=m;++i)c[i]=0;
for(int i=1;i<=n;++i)c[rnk[i]]++;
for(int i=1;i<=m;++i)c[i]+=c[i-1];
for(int i=n;i;--i)sa[c[rnk[tp[i]]]--]=tp[i];
}
void GetSA()
{
for(int i=1;i<=n;++i)rnk[i]=s[i],tp[i]=i;
Sort();
for(int w=1,p=0;p<n;m=p,w<<=1)
{
p=0;
for(int i=1;i<=w;++i)tp[++p]=n-w+i;
for(int i=1;i<=n;++i)if(sa[i]>w)tp[++p]=sa[i]-w;
Sort();
swap(tp,rnk);
rnk[sa[1]]=1,p=1;
for(int i=2;i<=n;++i)
rnk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+w]==tp[sa[i-1]+w])?p:++p;
}
for(int i=1,j,k=0;i<=n;++i)
{
if(k)--k;
j=sa[rnk[i]-1];
while(s[i+k]==s[j+k])++k;
height[rnk[i]]=k;
}
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1),m='Z';
GetSA();
for(int i=1;i<=n;++i)
cerr<<sa[i]<<" "<<height[i]<<endl;
pair<int,int> ans(n,n);
for(int i=1;i<=n;++i)
{
int cmp=max(height[i],height[i+1])+1;
if(sa[i]+cmp-1>n)
continue;
ans=min(ans,{cmp,sa[i]});
}
for(int i=0;i<ans.first;++i)
printf("%c",s[ans.second+i]);
return 0;
}
|
C. Safe Distance
一句话题意
给定xOy平面和平面上的若干个点，要从(0,0)出发到达(X,Y)，要求路径距离给出的点尽可能远，求出路径与最近的点的距离的最大值
1≤X,Y≤1000000
1≤n≤1000
解法
考虑二分答案
假设我们二分得到的答案为mid，对其检查可行性
在平面上以所有的点为圆心画半径为mid的圆，那么路径不应该与这些圆有交点
想象将这些圆在平面上挖去，那么如果mid为可行答案，(0,0)与(X,Y)应仍连通
接下来考虑如何表示(0,0)与(X,Y)的连通性
假设我们要将平面沿一条线（可以是曲线）切开，使得(0,0)与(X,Y)不连通，这条线应当与平面的左边界和下边界、或左边界和右边界、或上边界和右边界、或上边界和下边界同时存在交点
那么如果我们画的圆的并能够包含这样的一条线，(0,0)与(X,Y)就是不连通的
我们可以以所有的点为顶点（称为平面点），点之间的距离为边权建立无向图，同时设置四个顶点ut,ub,ul,ur（称为边界点）分别代表上、下、左、右边界，平面点与边界点间的边的边权为点到对应边界的距离
那么，如果在图上存在一条路径分别以ul,ub、或ul,ur、或ut,ur、或ut,ub为起点和终点，满足边界点到平面点的边的边权小于等于mid，平面点之间的边的边权小于等于2∗mid，那么(0,0)与(X,Y)就是不连通的
复杂度O(nlog(X+Y))
代码
实际实现时，边权应为距离的平方以避免开平方根带来的精度误差
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
| #include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
template<typename T>void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=(c=='-');c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}
const double eps=1e-6;
const int maxn=1000+100;
int n;
double X,Y;
double x[maxn],y[maxn];
double tmid;
struct edge
{
int u,v,nxt;
double w;
}g[maxn*maxn*2];
int head[maxn],ecnt;
void eADD(int u,int v,double w)
{
g[++ecnt].u=u;g[ecnt].v=v;g[ecnt].w=w;g[ecnt].nxt=head[u];head[u]=ecnt;
}
inline double dist(int a,int b)
{
double dx=x[a]-x[b],dy=y[a]-y[b];
return dx*dx+dy*dy;
}
int vst[maxn];
bool dfs(int u)
{
vst[u]=1;
if(u==n+2 || u==n+3)
{
return true;
}
for(register int i=head[u];i;i=g[i].nxt)
{
int v=g[i].v;
if(vst[v])continue;
double s=2-(u>n || v>n);
s*=s;
if(g[i].w<=tmid*s)
if(dfs(v))
{
return true;
}
}
return false;
}
bool Check(double mid)
{
tmid=mid*mid;
memset(vst,0,sizeof(vst));
if(dfs(n+1))
{
return false;
}
memset(vst,0,sizeof(vst));
if(dfs(n+4))
{
return false;
}
return true;
}
int main()
{
scanf("%lf%lf",&X,&Y);
read(n);
for(register int i=1;i<=n;++i)
scanf("%lf%lf",&x[i],&y[i]);
for(register int i=1;i<=n;++i)
{
double d=y[i]*y[i];
eADD(n+1,i,d);
eADD(i,n+1,d);
d=x[i]*x[i];
eADD(n+2,i,d);
eADD(i,n+2,d);
d=(Y-y[i])*(Y-y[i]);
eADD(n+3,i,d);
eADD(i,n+3,d);
d=(X-x[i])*(X-x[i]);
eADD(n+4,i,d);
eADD(i,n+4,d);
for(register int j=i+1;j<=n;++j)
{
double d=dist(i,j);
eADD(i,j,d);
eADD(j,i,d);
}
}
register double l=0,r=X+Y,ans;
while(r-l>=eps)
{
double mid=(r+l)/2;
if(Check(mid))
{
ans=mid;
l=mid;
}
else
r=mid;
}
printf("%lf",ans);
return 0;
}
|
D. Jogging
一句话题意
定义一个跑步路径为一条从0号顶点出发再回到0号顶点的路径，跑步路径上允许出现重边，允许在一条边上的任意位置折返。如果一条跑步路径经过了之前未出现过的边，那么这条跑步路径就是“有趣的”。
给定I个点S条边的简单无向带权图，下界L和上界U。现要求每天都要有一条”有趣的"跑步路径，且长度在上界和下界之间，问最多可以跑步多少天。
1≤I,S≤100000
1≤L≤U≤42195（一次马拉松的长度）
1≤边权≤1000
解法
由于我们可以在一条边上来回摩擦，所以不需要关心下界
如果每条跑步路径不原路返回，会使答案更劣，所以原路返回一定是最佳策略
那么题目可以转化成从顶点0出发，行走不大于2U的距离，最多可以到达多少条边
代码
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
| #include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pa;
template<typename T>void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=(c=='-');c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}
const int maxn=100000+100,maxm=100000+100;
int n,m,L,U;
struct edge
{
int u,v,w,nxt;
}g[maxm*2];
int head[maxn],ecnt;
void eADD(int u,int v,int w)
{
g[++ecnt].u=u;g[ecnt].v=v;g[ecnt].w=w;g[ecnt].nxt=head[u];head[u]=ecnt;
}
int dist[maxn],vst[maxn];
void dijkstra()
{
memset(dist,0x3f,sizeof(dist));
dist[0]=0;
priority_queue<pa> q;
q.push({-dist[0],0});
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vst[u])
continue;
vst[u]=1;
for(int i=head[u];i;i=g[i].nxt)
{
int v=g[i].v;
if(!vst[v] && dist[u]+g[i].w<dist[v])
{
dist[v]=dist[u]+g[i].w;
q.push({-dist[v],v});
}
}
}
}
int main()
{
read(n),read(m),read(L),read(U);
for(int i=1;i<=m;++i)
{
int u,v,w;
read(u),read(v),read(w);
eADD(u,v,w);
eADD(v,u,w);
}
dijkstra();
int ans=0;
for(int i=1;i<=ecnt;i+=2)
{
if(min(dist[g[i].u],dist[g[i].v])*2<U)
++ans;
}
printf("%d",ans);
return 0;
}
|
待补完
要填的坑
- STL的各种数据结构的使用
- 字符串后缀相关数据结构
