Codeforces Round #492 (Div. 1)

解题报告.....

A. Tesla

我是 \(zz\)\(A\) 都不会。这题操作步数特别宽松,只要能用一种方法不会堵住就行了。

把中间两行看作一个环形路,整个车队绕着转,到对应位置就进入......

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
#include<bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
const int maxn=1000005;
int n,m,a[55][55],tot;
pair<int,pii> ans[maxn];
void Next(int &x,int &y){
if(x==2){
if(y==n) x=3, y=n; else y++;
} else{
if(y==1) x=2, y=1; else y--;
}
}
void Pre(int &x,int &y){
if(x==2){
if(y==1) x=3, y=1; else y--;
} else{
if(y==n) x=2, y=n; else y++;
}
}
void toPre(int x,int y){
int _x=x,_y=y; Pre(_x,_y);
if(a[_x][_y]) return;
a[_x][_y]=a[x][y]; ans[++tot]=mp(a[x][y],mp(_x,_y)); a[x][y]=0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=4;i++)
for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
int px=2,py=1,now=0,haha=0;
while(now<m&&haha++<=10000000){
if(a[px][py]){
if(px==2){
if(a[px-1][py]==a[px][py])
ans[++tot]=mp(a[px][py],mp(px-1,py)), a[px][py]=0, now++;
else toPre(px,py);
} else{
if(a[px+1][py]==a[px][py])
ans[++tot]=mp(a[px][py],mp(px+1,py)), a[px][py]=0, now++;
else toPre(px,py);
}
}
Next(px,py);
}
if(now<m){ puts("-1"); return 0; }
printf("%d\n",tot);
for(int i=1;i<=tot;i++) printf("%d %d %d\n",ans[i].X,ans[i].Y.X,ans[i].Y.Y);
return 0;
}

B. Suit and Tie

如果固定了最后的位置,那么最小步数就是逆序对数。

可以看作把每对人重标号,使得逆序和最小。

然后直接贪心,把贡献小的放前面。

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
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn=205;
int n,a[maxn],bit[maxn];
int Update(int x,int val){
for(;x<=(n<<1);x+=(x&-x)) bit[x]+=val;
}
int Query(int x){
int res=0;
for(;x;x-=(x&-x)) res+=bit[x];
return res;
}
bool vis[maxn];
int b[maxn][2],m,lst[maxn];
LL ans;
int Get(int id){
int p1=b[id][0], p2=b[id][1];
return Query(p1-1)*2+Query(p2-1)-Query(p1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=(n<<1);i++){
scanf("%d",&a[i]);
if(lst[a[i]]) b[++m][0]=lst[a[i]], b[m][1]=i;
lst[a[i]]=i;
}
for(int i=1;i<=(n<<1);i++) Update(i,1);
while(m--){
int res=1e9,k;
for(int i=1;i<=n;i++)
if(!vis[i]){
int t=Get(i);
if(t<res) res=t, k=i;
}
Update(b[k][0],-1); Update(b[k][1],-1);
ans+=res; vis[k]=true;
}
printf("%lld\n",ans);
return 0;
}

C. Leaving the Bar

我直接 random_shuffle 然后贪心,莫名其妙就过了。后来看 \(dls\) 也是这么过的2333

题解做法是:

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100005;
int n,ans[maxn];
struct Vec{
int x,y,id;
Vec(int t1=0,int t2=0){ x=t1; y=t2; }
LL Mo(){ return sqrt((LL)x*x+(LL)y*y); }
} a[maxn],p;
Vec operator + (const Vec &A,const Vec &B){ return Vec(A.x+B.x,A.y+B.y); }
Vec operator - (const Vec &A,const Vec &B){ return Vec(A.x-B.x,A.y-B.y); }
bool my_cmp(Vec A,Vec B){ return A.Mo()>B.Mo(); }
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
a[i].id=i;
}
while(1){
random_shuffle(a+1,a+n+1);
p=Vec(0,0);
for(int i=1;i<=n;i++){
if((p+a[i]).Mo()<(p-a[i]).Mo()){
p=p+a[i]; ans[a[i].id]=1;
} else{
p=p-a[i]; ans[a[i].id]=-1;
}
}
if(p.Mo()<=1500000){
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
}
return 0;
}

D. Game

想了好久才懂......

这种带随机过程的博弈,玩家的最优决策应该是看之后局面的期望大小。

考虑当前局面为 \(f\),设 \(f_{s,t}\) 表示 第一步把 \(s\) 位设成 \(t\) ,之后的局面。

\[ E(f)=\frac{\max_{i,j}\{E(f_{i,j})\}+min_{i,j}\{E(f_{i,j})\}}{2} \]

有个结论 \(E(f)=\frac{\sum W(f)}{2}\), \(xjb\) 归纳证明:

\(f\) 只有一位,显然成立。

\(\max_{i,j}\{E(f_{i,j})\}=E(f_{s,t})\) 根据假设,则一定有 \(\min_{i,j}\{E(f_{i,j})\}=E(f_{s,1-t})\)

所以 \(E(f)=\frac{\sum W(f)}{2}\)

所以最后答案就是 \(\frac{\sum w}{2^n}\) ......

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[1<<19],n,m,sum;
int main(){
scanf("%lld%lld",&n,&m);
for(int i=0;i<=(1<<n)-1;i++) scanf("%lld",&a[i]), sum+=a[i];
printf("%.6f\n",(double)sum/(1<<n));
for(int i=0;i<=m-1;i++){
LL x,y; scanf("%lld%lld",&x,&y);
sum+=y-a[x]; a[x]=y;
printf("%.6f\n",(double)sum/(1<<n));
}
return 0;
}

E. Number Clicker

我第一反应是 \(v=\frac{au+b}{cu+d}\) ,考虑随机 \(a,b,c,d\) ,然后判断,感觉不太科学。

结果看题解发现这就是乱搞题。实际上是一个随机图上找一条路径。

可以分别从起点到终点随机若干条链,\(meet\ in\ middle\) , 多试几次就能接上。

题解还有一种做法与我的思路比较接近,就是考虑求 \(v \to 1,1 \to u\) 的路径:

随机一个 \(x\) ,然后把 \(\frac{vx}{x}\) 类似辗转相减那样变到 \(1\) 。多随机几次直到长度符合条件。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int S,T,P,ans[2][10005];
void Solve(int x,int y,int k){
if(x==y||ans[k][0]>200) return;
if(x<y) ans[k][++ans[k][0]]=3, Solve(y,x,k);
else ans[k][++ans[k][0]]=(k?1:2), Solve(x-y,y,k);
}
int main(){
srand(23333);
scanf("%d%d%d",&S,&T,&P);
while(1){
LL x=(LL)rand()*rand()%(P-1)+1;
ans[0][0]=0; if(x*S%P==0) ans[0][++ans[0][0]]=1; else Solve(x*S%P,x,0);
ans[1][0]=0; if(x*T%P==0) ans[1][++ans[1][0]]=2; else Solve(x*T%P,x,1);
if(ans[0][0]+ans[1][0]<=200){
printf("%d\n",ans[0][0]+ans[1][0]);
for(int i=1;i<=ans[0][0];i++) printf("%d\n",ans[0][i]);
for(int i=ans[1][0];i>=1;i--) printf("%d\n",ans[1][i]);
return 0;
}
}
return 0;
}

F. Cowmpany Cowmpensation

简单的 \(DP\) ,题解是插值.....

容易发现其实 \(D\) 这么大没什么卵用,我们求出 \(g(i)\) 表示恰好用 \(i\) 种值的方案。

\[ ans=\sum_{i=1}^D g(i){n\choose i} \]

\(g(i)\) 挺容易的吧,先 \(DP\)\(f(i,j)\) 表示 \(i\) 的子树用不超过 \(j\) 的值的方案,然后 \[ g(i)=f(1,i)-\sum_{j=1}^{i-1}{i \choose j}g(j) \] 就好了。

题解插值做法是:

先是结论:对于一棵 \(n\) 个节点的数,其答案一定是关于 \(D\) 的一个 \(n\) 次多项式。

然后和上面一样 \(DP\)\(n\) 个值,然后拉格朗日插值。

感觉就是分析出来结论之后直接插值,少了上面算的过程。

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<cstdio>
#include<algorithm>
typedef long long LL;
using namespace std;
const int maxn=5005,maxe=maxn,P=1e9+7;
int n,D,a[maxn];
int fir[maxn],nxt[maxe],son[maxe],tot;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int f[maxn][maxn],mdep[maxn],sum[maxn],g[maxn],v[maxn];
LL fac[maxn],inv[maxn],fac_inv[maxn];
LL Pow(LL a,LL b){
LL res=1;
for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;
return res;
}
LL C(int n,int m){ return fac[n]*fac_inv[m]%P*fac_inv[n-m]%P; }
LL _C(int n,int m){
LL res=1;
for(int i=n-m+1;i<=n;i++) res=res*i%P;
return res*fac_inv[m]%P;
}
void dfs(int x){
for(int j=fir[x];j;j=nxt[j]) dfs(son[j]);
v[0]=0; for(int j=fir[x];j;j=nxt[j]) v[++v[0]]=son[j];
for(int i=1;i<=n;i++){
f[x][i]=1;
for(int j=1;j<=v[0];j++) f[x][i]=(LL)f[x][i]*f[v[j]][i]%P;
(f[x][i]+=f[x][i-1])%=P;
}
}
int main(){
scanf("%d%d",&n,&D);
fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%P;
inv[1]=1; for(int i=2;i<=n;i++) inv[i]=(LL)(P-P/i)*inv[P%i]%P;
fac_inv[0]=1; for(int i=1;i<=n;i++) fac_inv[i]=fac_inv[i-1]*inv[i]%P;
for(int i=2;i<=n;i++){
int x; scanf("%d",&x);
add(x,i);
}
dfs(1);
for(int i=1,t=0;i<=n;i++){
g[i]=f[1][i];
for(int j=1;j<=i-1;j++) (g[i]-=C(i,j)*g[j]%P)%=P;
}
int ans=0;
for(int i=1;i<=n&&i<=D;i++) (ans+=_C(D,i)*g[i]%P)%=P;
printf("%d\n",(ans+P)%P);
return 0;
}