| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 11/12 | O | Ø | . | O | Ø | Ø | O | O | Ø | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
题目来源：Egyptian Collegiate Programming Contest 2017 (ACM ECPC 2017)
沙雕比赛，沙雕数据（手动再见
A Assessments
题目描述
$n$个人站一排，有$k$轮，每轮有$p$的概率交换某两个相邻的人，问经过这些轮之后，$x$和$y$两人互换位置的概率。
解题思路
设$dp[i][j][k]$表示第$i$轮后，$x$的位置在$j$，$y$的位置在$k$的概率，转移显然。
口头AC，还没写代码，扔个队友的算了
AC代码 - by qxforever
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
using namespace std;
const int maxn = 52;
const int maxk = 3e3+23;
double dp[maxk][maxn][maxn];
int n,x,y,k,T;
double p;
int main()
{
freopen("assessment.in","r",stdin);
scanf("%d",&T);int cas=1;
while(T--){
printf("Case %d: ",cas++);
memset(dp,0,sizeof(dp));
scanf("%d%lf%d%d%d",&n,&p,&x,&y,&k);
if(n==1) {printf("1.00000\n");continue;}
dp[0][x][y]=1;
if(x==y){
for(int i=1;i<=k;i++){
for(int j=0;j<n;j++){
int cnt=0;
if(j>=1) dp[i][j][x]+=dp[i-1][j-1][x],cnt++;
if(j<n-1) dp[i][j][x]+=dp[i-1][j+1][x],cnt++;
dp[i][j][x]+=dp[i-1][j][x]*(n-1-cnt);
dp[i][j][x]=(dp[i][j][x]*p)/(n-1);
dp[i][j][x]+=dp[i-1][j][x]*(1-p);
}
}
printf("%.5lf\n",dp[k][x][x]);
continue;
}
dp[0][x][y]=1;
for(int i=1;i<=k;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
if(j==k) continue;
int cnt=0;
if(abs(j-k)!=1){
if(j>=1) dp[i][j][k]+=dp[i-1][j-1][k],cnt++;
if(j<n-1) dp[i][j][k]+=dp[i-1][j+1][k],cnt++;
if(k>=1) dp[i][j][k]+=dp[i-1][j][k-1],cnt++;
if(k<n-1) dp[i][j][k]+=dp[i-1][j][k+1],cnt++;
}
else{
if(j-k==1){
dp[i][j][k]+=dp[i-1][k][j],cnt++;
if(j<n-1) dp[i][j][k]+=dp[i-1][j+1][k],cnt++;
if(k>=1) dp[i][j][k]+=dp[i-1][j][k-1],cnt++;
}
else{
dp[i][j][k]+=dp[i-1][k][j],cnt++;
if(k<n-1) dp[i][j][k]+=dp[i-1][j][k+1],cnt++;
if(j>=1) dp[i][j][k]+=dp[i-1][j-1][k],cnt++;
}
}
dp[i][j][k]+=(dp[i-1][j][k]*(n-cnt-1));
dp[i][j][k]=(dp[i][j][k]*p)/(n-1);
dp[i][j][k]+=dp[i-1][j][k]*(1-p);
//printf("%d %d %d\n",j,k,cnt);
}
}
}
printf("%.5lf\n",dp[k][y][x]);
}
}
B Breaking the Curse
题目描述
给两个字符串，$q$次询问，每次询问$s$中一个区间$[l,r]$，问有多少个$[l,r]$的子区间$[l_i,r_i]$满足$s[l_i,r_i]\in t$。
解题思路
我们假设$s$中以$s_i$结尾的串中，能够匹配的最长串的左端点为$left_i$，最长串的长度为$length_i$。很容易得出结论：$left_i$是单调不减的。（如果后面的比前面匹配的更靠前，那么显然前面也应当往前匹配）
考虑如何求$length_i$。对$t$建一个后缀自动机，根据后缀自动机的性质，从根节点任意沿着匹配边走的路径都是一个后缀的前缀，所以从根节点开始跑，每次如果有匹配边那就沿着匹配边走，匹配长度$+1$；否则沿着父亲边走，匹配长度更新为节点对应的最大长度$len[p]$。这样可以线性的求出$length_i$，$left_i$也可顺带求出。
处理询问的时候，一个区间中可以找到一个分界点$x$，在$x$左边的点都是最左端延伸到左端点之外的，而在$x$右边的点是可以把所有合法区间都加入答案贡献中的。于是每次二分一下$x$，两边分别用组合数和前缀和计算一下即可。
复杂度$O(T(n+q\log n))$。
AC代码
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
typedef long long ll;
using namespace std;
char s[N],t[N];
ll sum[N],lef[N];
struct SAM{
int tr[N<<1][P],fa[N<<1],len[N<<1],siz[N<<1];
int cnt,last;
void init(){
cnt=last=1;
memset(tr[1],0,sizeof(tr[1]));
fa[1]=len[1]=0;
}//dont forget!!!
void add(int c){
int p=last,np=++cnt;
memset(tr[cnt],0,sizeof(tr[cnt]));
siz[np]=1;
last=np;
len[np]=len[p]+1;
while(p&&!tr[p][c])tr[p][c]=np,p=fa[p];
if(!p)fa[np]=1;
else{
int q=tr[p][c];
if(len[q]==len[p]+1)fa[np]=q;
else{
int nq=++cnt;
len[nq]=len[p]+1;
memcpy(tr[nq],tr[q],sizeof(tr[q]));
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
while(tr[p][c]==q)tr[p][c]=nq,p=fa[p];
}
}
}
void insert(char a[]){
int i;
for(i=0;a[i];i++)add(a[i]-'a');//can be changed
}
void process(char a[]){
int i,now=1,l=0;
for(i=0;a[i];i++){
while(now!=1&&!tr[now][a[i]-'a'])now=fa[now],l=len[now];
if(tr[now][a[i]-'a'])now=tr[now][a[i]-'a'],l++;
lef[i+1]=i+2-l;
sum[i+1]=sum[i]+l;
}
}
}sam;
int main(){
int i,T,q,Cas;
freopen("curse.in","r",stdin);
scanf("%d",&T);
for(Cas=1;Cas<=T;Cas++){
sam.init();
printf("Case %d:\n",Cas);
scanf("%s%s",s,t);
sam.insert(t);
sam.process(s);
scanf("%d",&q);
while(q--){
int l,r;
scanf("%d%d",&l,&r);
int L=l,R=r+1;
while(L<R){
int mid=(L+R)>>1;
if(lef[mid]<l)L=mid+1;
else R=mid;
}
printf("%lld\n",sum[r]-sum[L-1]+1LL*(L-l+1)*(L-l)/2);
}
}
return 0;
}
C Cheering Parabolas
题目描述
解题思路
AC代码
2
D Dream Team
题目描述
解题思路
见上面链接的E题。
AC代码
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
using namespace std;
int n,a[100010],f[100010],map[100010];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int main(){
int i,j,k,l,t,m;
scanf("%d",&t);
while(t--){
long long ans=0,max;
int temp,p,q,u[2]={0},now=0,cnt=0;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
max=a[n];
for(i=1;i<n;i++)if(a[i]==a[i+1])ans+=a[i],cnt++;
for(i=1;i<=n;i++)map[a[i]]=i;
for(i=1;i<=n;i++)f[i]=i;
for(i=max;i;i--){
now=u[0]=u[1]=0;
for(j=1;j*i<=max;j++){
if(map[j*i]){
u[now]=map[j*i];
if(u[now^1]){
p=find(u[now]);
q=find(u[now^1]);
if(p!=q){
ans+=i;
f[p]=q;
cnt++;
}
}
now^=1;
}
}
if(cnt==n-1)break;
}
printf("%lld\n",ans);
memset(map,0,sizeof(map));
}
return 0;
}
E Evaluations
题目描述
给一棵有边权的树，定义两点$u,v$之间的一个函数$f(u,v)$为$u$到$v$路径权值的积，问有多少对$u,v$满足$f(u,v)$为两个不同质数的乘积。
解题思路
可以考虑点分治，记录通过根节点的边权乘积分别为$1$、质数、两不同质数乘积的个数即可求出。但这个方法貌似是$O(Tn\log n)$的，会$T$掉。考虑线性做法。
对边做文章，把连续的边权为$1$的通过并查集并起来，记录$1$的数量$cnt$，方便查询。对于某个边权为$w$的边$(u,v)$，计算其对答案的贡献$x$。如果$w$为两个不同质数的乘积，答案即为$cnt_u\times cnt_v$；如果$w$为质数，答案即为前面统计过的$sz_u\times cnt_v+sz_v\times cnt_u$，其中$sz_i$表示已计算的$i$连出的边权乘积一个质数的个数。为了保证结果是两个不同的质数的乘积，用一个$map$去掉重复的即可。
没来得及写，扔一个队友的代码：
AC代码 - by qxforever
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
using namespace std;
typedef long long ll;
const int maxn = 1e5+23;
typedef pair<int,int> pii;
int T,n;
int f[maxn];
int u[maxn],v[maxn],w[maxn],cnt[maxn];
int pri[maxn],vis[maxn],tot=0;
int sat[maxn],sz[maxn];
map<int,int> m[maxn];
void sieve()
{
int N=1e5+3;
vis[0]=vis[1]=1;
for(int i=2;i<=N;i++){
if(!vis[i]) pri[tot++]=i;
for(int j=0;j<tot&&(pri[j]*i)<=N;j++){
vis[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
for(int i=0;i<tot;i++){
for(int j=0;j<tot&&(pri[i]*pri[j])<=N;j++){
if(j==i) continue;
sat[pri[i]*pri[j]]=1;
}
}
}
void init()
{
for(int i=1;i<=n;i++) f[i]=i;
memset(sz,0,sizeof(sz));
}
int find(int x)
{
return x==f[x] ? x : f[x]=find(f[x]);
}
void count()
{
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++){
cnt[find(i)]++;
}
}
int main()
{
freopen("evaluations.in","r",stdin);
cin >> T ;
int cas=1;
sieve();
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++) m[i].clear();
printf("Case %d: ",cas++);
init();
for(int i=0;i<n-1;i++){
scanf("%d%d%d",u+i,v+i,w+i);
if(w[i]==1){
int x=find(u[i]),y=find(v[i]);
f[x]=y;
}
}
count();
ll ans=0;
for(int i=0;i<n-1;i++){
int x=find(u[i]),y=find(v[i]);
if(sat[w[i]]){
ans+=(1LL*cnt[x]*cnt[y]);
}
if(!vis[w[i]]){
ans+=1LL*(sz[x]-m[x][w[i]])*cnt[y];
ans+=1LL*(sz[y]-m[y][w[i]])*cnt[x];
sz[x]+=cnt[y];
sz[y]+=cnt[x];
m[x][w[i]]+=cnt[y];
m[y][w[i]]+=cnt[x];
}
}
printf("%lld\n",ans);
}
}
F Forgot the Flag!
题目描述
给一个凸多边形，两个点，问其中一个点到凸多边形边界再到另一个点总路径最小值是多少。
解题思路
没计算几何板子，就暴力对于每个边每个点求…求镜像点，求两直线交点…
细节有点多，不赘述了，肯定有套板子的好方法。
AC代码
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
typedef long long ll;
using namespace std;
double x[50010],y[50010];
double dis(int ind,double X,double Y){
return (X-x[ind])*(X-x[ind])+(Y-y[ind])*(Y-y[ind]);
}
int main(){
int i,j,n,T,q;
freopen("flags.in","r",stdin);
scanf("%d",&T);
for(i=1;i<=T;i++){
printf("Case %d:\n",i);
scanf("%d",&n);
for(j=0;j<n;j++)scanf("%lf%lf",&x[j],&y[j]);
x[n]=x[0],y[n]=y[0];
scanf("%d",&q);
while(q--){
double A,B,C,D;
scanf("%lf%lf%lf%lf",&A,&B,&C,&D);
double ans=4e18,tx,ty;
for(j=0;j<n;j++){
double dist=dis(j,A,B);
double t=sqrt(dist)+dis(j,C,D);
if(ans>t){
ans=t;
tx=x[j];
ty=y[j];
}
double x1=x[j],y1=y[j],x2=x[j+1],y2=y[j+1];
double a,b,c;
if(abs(x1-x2)<1e-9)a=1,b=0,c=-x1;
else{
double k=(y2-y1)/(x2-x1);
double b2=y2-x2*k;
a=k;b=-1;c=b2;
}
double ds=abs(a*A+b*B+c)/sqrt(a*a+b*b),mx,my;
if(abs(x1-x2)<1e-9){
mx=x1;
my=B;
}else{
double k=(y2-y1)/(x2-x1);
double dx=sqrt(dist-ds*ds)/sqrt(1+k*k);
double dy=dx*k;
if(dis(j,A,B)+(x[j]-x[j+1])*(x[j]-x[j+1])+(y[j]-y[j+1])*(y[j]-y[j+1])<dis(j+1,A,B)){//钝角
mx=x1-(x2<x1?-dx:dx);
my=y1-(x2<x1?-dy:dy);
}else{
mx=x1+(x2<x1?-dx:dx);
my=y1+(x2<x1?-dy:dy);
}
}
double refx=2*mx-A,refy=2*my-B;
double inx,iny;
double a2,b2,c2;
if(abs(refx-C)<1e-9)a2=1,b2=0,c2=-x1;
else{
double k=(D-refy)/(C-refx);
double b3=D-C*k;
a2=k;b2=-1;c2=b3;
}
iny=(a2*c-a*c2)/(a*b2-a2*b);
inx=(b2*c-b*c2)/(b*a2-b2*a);
if((inx-x1)*(x2-x1)<-1e-9)continue;
t=sqrt((C-refx)*(C-refx)+(D-refy)*(D-refy));
if(ans>t){
ans=t;
tx=inx;
ty=iny;
}
}
printf("%.7f %.7f %.7f\n",ans,tx,ty);
}
}
return 0;
}
G Glorious Stadium
题目描述
圆和多边形互相套，求阴影部分面积。
解题思路
推出式子等比数列求和即可。
AC代码 - by qxforever
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
using namespace std;
const double pi = acos(-1.0);
int n,r,k,T;
double qpow(double a,int b)
{
double ans=1,base=a;
while(b!=0){
if(b&1!=0) ans*=base;
base*=base;
b>>=1;
}
return ans;
}
int main()
{
freopen("glorious.in","r",stdin);
cin >> T;
int cas=1;
while(T--){
scanf("%d%d%d",&k,&r,&n);
double the = pi*(n-2)/n;
double a=(2*1.0*r)/tan(the/2);
double phi=pi/n;
double h=a/(2*tan(phi));
double s1=(a*h/2)*n-pi*r*r;
double q=1/(tan(the/2)*sin(phi));
q=q*q;
double S=s1*(1-qpow(q,k))/(1-q);
printf("Case %d: %.5f\n",cas++,S);
}
}
H Half Nice Years
题目描述
给一个区间，问区间中存不存在一个数，这个数左右两部分不互质。
解题思路
暴力从大到小枚举处理左端。
AC代码
I Important matches
题目描述
$q$次询问某个问子矩阵中位数。
解题思路
不会$cdq$分治，暴力三维树状数组卡常通过。
$cdq$分治留坑
AC代码
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
typedef long long ll;
int bit[202][202][2003],n,m,mx;
void upd(int px,int py,int pz){
int i,j,k;
for(i=px;i<=n;i+=lb(i))for(j=py;j<=m;j+=lb(j))for(k=pz;k<=mx;k+=lb(k))
++bit[i][j][k];
}
void upd2(int px,int py,int pz){
int i,j,k;
for(i=px;i<=n;i+=lb(i))for(j=py;j<=m;j+=lb(j))for(k=pz;k<=mx;k+=lb(k))
--bit[i][j][k];
}
int que(int px,int py,int pz){
int i,j,k,ans=0;
for(i=px;i;i-=lb(i))for(j=py;j;j-=lb(j))for(k=pz;k;k-=lb(k))
ans+=bit[i][j][k];
return ans;
}
int num(int a,int b,int c,int d,int mid){
int q1=que(c,d,mid);
int q2=que(a-1,d,mid);
int q3=que(c,b-1,mid);
int q4=que(a-1,b-1,mid);
return q1-q2-q3+q4;
}
inline int read() {
char ch=getchar();int x=0,f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
char buf[100];
void print(const int& x) {
int tmp=x,s=0;
while(tmp>0){
buf[s++]=tmp%10+'0';
tmp/=10;
}
while(s>0)putchar(buf[--s]);
}
int mt[210][210];
int main(){
int Cas,i,j,t,q,a,b,c,d;
freopen("important.in","r",stdin);
t=read();
for(Cas=1;Cas<=t;Cas++){
mx=1;
printf("Case %d:\n",Cas);
n=read();m=read();q=read();
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
mt[i][j]=read();
mx=std::max(mx,mt[i][j]+1);
}
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
upd(i,j,mt[i][j]+1);
}
}
while(q--){
a=read();b=read();c=read();d=read();
int sz=(d-b+1)*(c-a+1);
sz=(sz+2)/2;
int l=1,mid,r=mx;
while(l<r){
mid=(l+r)>>1;
int nm=num(a,b,c,d,mid);
if(nm>=sz)r=mid;
else if(nm<sz)l=mid+1;
}
print(l-1);puts("");
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
upd2(i,j,mt[i][j]+1);
}
return 0;
}
J Jacked Tickets
题目描述
给一个凸函数$f$，给定$n,p$，求把$n$分为$a_1,a_2…a_p$，满足$\sum_{i=1}^p a_i=n$且$a_i\geq 1$，最小化$\sum_{i=1}^pf(a_i)$。
解题思路
显然尽量平均分就是满足条件的。
AC代码 - by Mogg
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
using namespace std;
typedef long long ll;
const int ms = 1e5 + 15;
int n, tmp;
ll p[ms];
int main()
{
int t;
freopen("jacking.in", "r", stdin);
scanf("%d", &t);
int cas = 0;
while (t--)
{
cas++;
printf("Case %d:\n", cas);
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%lld", &p[i]);
}
int k, l, r;
scanf("%d", &k);
for (int i = 0; i < k; ++i)
{
scanf("%d%d", &l, &r);
if (l < r)
{
printf("impossible\n");
continue;
}
tmp = l / r;
printf("%lld\n", p[tmp + 1] * (l - tmp * r) + p[tmp] * ((tmp + 1)*r - l));
}
}
}
K Katryoshka
题目描述
给几个原材料和配方，求最多能做物品的个数。
解题思路
签到，贪心即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef long long ll;
using namespace std;
int main(){
int i,n,a,b,c;
freopen("katryoshka.in","r",stdin);
scanf("%d",&n);
for(i=1;i<=n;i++){
int ans=0;
scanf("%d%d%d",&a,&b,&c);
ans+=min(a,min(b,c));
a-=ans,b-=ans,c-=ans;
ans+=min(a/2,c);
printf("Case %d: %d\n",i,ans);
}
return 0;
}
L Lazy ERCD
题目描述
比赛规则是每场比赛淘汰失败的队伍，问一共要看多少场比赛。
解题思路
签到，显然是$n-1$场。
AC代码
2
3
4
5
6
7
8
9
10
11
12
typedef long long ll;
using namespace std;
int main(){
int i,n,T;
freopen("lazy.in","r",stdin);
scanf("%d",&T);
for(i=1;i<=T;i++){
scanf("%d",&n);
printf("Case %d: %d\n",i,n-1);
}
}