Codeforces Round 417(Div. 2)

A. Sagheer and Crossroads

B. Sagheer, the Hausmeister

C. Sagheer and Nubian Market

D. Sagheer and Kindergarten

E. Sagheer and Apple Tree

A. Sagheer and Crossroads

暴力

需要注意:只要该路口有人,则不能有车。

代码如下:

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
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
int q[5];
int c[5];
int x[5];
int main(void){
int l,s,r,p;
scanf("%d%d%d%d",&l,&s,&r,&p);
if(l)c[4]=1;
if(s)c[3]=1;
if(r)c[2]=1;
if(p)q[1]=1;
if(l+s+r)x[1]=1;
scanf("%d%d%d%d",&l,&s,&r,&p);
if(l)c[1]=1;
if(s)c[4]=1;
if(r)c[3]=1;
if(p)q[2]=1;
if(l+s+r)x[2]=1;
scanf("%d%d%d%d",&l,&s,&r,&p);
if(l)c[2]=1;
if(s)c[1]=1;
if(r)c[4]=1;
if(p)q[3]=1;
if(l+s+r)x[3]=1;
scanf("%d%d%d%d",&l,&s,&r,&p);
if(l)c[3]=1;
if(s)c[2]=1;
if(r)c[1]=1;
if(p)q[4]=1;
if(l+s+r)x[4]=1;
bool f=0;
for(int i=1;i<=4;++i)
if((c[i]==1&&1==q[i])||(q[i]==1&&x[i]==1))f=1;
if(f)printf("YES\n");
else printf("NO\n");
}

B. Sagheer, the Hausmeister

题目大意:给定一个楼层的亮灯状态,问从左下角开始灭掉所有灯最少需要走几步。不需要回到起点。

dp

记录最高需要到达的层数$fl$ ,每层楼最左边亮着的灯$l[i]$ 以及最右边亮着的灯$r[i]$ .

定义状态$dp[i][0]$ 表示灭完第$i$ 层灯后在左边楼梯所需要的最少步数,$dp[i][1]$ 表示灭完第$i$ 层灯后在右边楼梯所需要的最少步数。复杂度$O(nm)$.

需要注意:$fl=0$ 时,需要特判。

代码如下:

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
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
int inf=100000000;
int n,m,l[20],r[20],dp[20][2],fl=-1;
char str[20][105];
int main(void){
scanf("%d%d",&n,&m);
for(int i=n-1;i>=0;--i)
scanf("%s",str[i]);
for(int i=0;i<n;++i){
for(int j=0;j<m+2;++j)if(str[i][j]=='1'){
if(l[i]==0)l[i]=r[i]=j;
else r[i]=j;
fl=i;
}
}
if(fl==-1){
printf("0\n");
return 0;
}
dp[0][0]=2*r[0],dp[0][1]=m+1;
for(int i=1;i<n-1&&i<fl;++i){
dp[i][0]=min(dp[i-1][0]+2*r[i],dp[i-1][1]+m+1)+1;
dp[i][1]=min(dp[i-1][0]+m+1,dp[i-1][1]+2*((l[i]!=0)?(m+1-l[i]):0))+1;
}
if(fl!=0)printf("%d\n",min(dp[fl-1][0]+r[fl],dp[fl-1][1]+((l[fl]!=0)?(m+1-l[fl]):0))+1);
else printf("%d\n",r[0]);
}

枚举

注意到该题$n \leqslant 15$ ,故可以用$2^{15}$ 枚举灭完各层灯后所在的楼梯状态,复杂度为$O(nm+n \times 2^n)$.

代码如下from xdujlx

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int l[20],r[20];
char s[105];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=n;i>=1;i--){
scanf("%s",s);
for(int j=1;j<=m;j++)
if(s[j]=='1') r[i]=j;
for(int j=m;j>=1;j--)
if(s[j]=='1') l[i]=j;
}
for(;n>=2&&!l[n];--n);
int ans=1e9;
if(n==0) ans=0;
else for(int i=0;i<(1<<(n-1));i++){
bool pL=1;
int res=n-1;
for(int j=1;j<n;j++){
bool L=(i>>(j-1))&1;
if(pL!=L){
res+=m+1;
pL=L;
}
else if(pL&&r[j]) res+=2*r[j];
else if(!pL&&l[j]) res+=2*(m+1-l[j]);
}
if(pL&&r[n]) res+=r[n];
else if(!pL&&l[n]) res+=(m+1-l[n]);
ans=min(ans,res);
}
cout << ans << endl;
return 0;
}

C. Sagheer and Nubian Market

题目大意:有$n$ 个物品,每个价值$a_i$ 。若购买$k$ 个物品(这些物品下标为$x_1,x_2,…x_k$),则每个物品需要支付$a_{x_i}+kx_i$元 。现有$s$ 元,问最多能买多少个物品。

二分

二分$k$ 值,每次用优先队列检查是否能在$s$ 元内购买$k$ 个物品,复杂度为$O(nlog_2^2(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
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
ll n,s,a[100005],sum;
priority_queue<ll>q;
void init(ll x){
while(!q.empty())q.pop();
for(int i=1;i<=n;++i)q.push(-(a[i]+x*i));
}
bool check(ll x){
init(x);
sum=0;
for(int i=0;i<x;++i){
sum+=-q.top();
q.pop();
if(sum>s)break;
}
return sum<=s;
}
int main(void){
scanf("%I64d%I64d",&n,&s);
for(int i=1;i<=n;++i)
scanf("%I64d",&a[i]);
ll l=0,r=n;ll mid=(l+r)>>1;
while(l<=r){
if(check(mid))l=mid+1;
else r=mid-1;
mid=(l+r)>>1;
}
if(check(r))printf("%I64d %I64d\n",r,sum);
else printf("0 0\n");
}

D. Sagheer and Kindergarten

题目有毒,暂时放弃治疗。

E. Sagheer and Apple Tree

题目大意:给定一颗$n(n \leqslant 10^5)$ 的树,且每个结点上都有$a_i$ 个苹果,每次操作只能将一个结点上的若干个苹果(不能为空)移到它的孩子结点或者将一个孩子结点上的若干个苹果(不能为空)吃掉。现在两人轮流进行操作,后手先将两个不同结点的苹果个数互换后,先手开始操作,直到不能操作为输。问有多少种换苹果的方案,使得先手输。

博弈

考虑一条链的情况

当结点数为1时

该结点上没有苹果时,如下所示:

by_barriery

显然此时$SG$ 值为$0$ 。

该结点上有$n$ 个苹果时,如下所示:

by_barriery

由于其能转移到$0 \sim n-1$ 的任意状态,故此时$SG$ 值为$n$ 。

当结点数为2时

父节点有$n$ 个苹果,孩子上无苹果时,如下图所示:

by_barriery

考虑先手无论从父节点移多少苹果到孩子,后手都将其吃掉,故先手必败,$SG$ 值为$0$ 。

当结点数为3时

父节点有$n$ 个苹果,孩子和孙子结点上无苹果时,如下图所示:

by_barriery

若将$n$ 个苹果全部移到孩子结点,则转移到了上面两个结点的状态($SG=0$),故若设该状态$SG=f(n)$ ,那么$f(n) \geqslant 1$ 。

将$n-m$ 个苹果移到孩子结点,如图:

by_barriery

设该状态$SG=f(m)$ ,而该状态其实是由

by_barriery

by_barriery

组合而成的,设前半部分的$SG$ 值为$f(m^{‘})$ ,后半部分的$SG$ 值为$0$ ,故有$f(m)=f(m^{‘}) \oplus 0=f(m^{‘})$ ,其中$\oplus$ 表示异或操作。

有了上面的结论后,有$f(n)$ 可以转移到$f(m)$ ,故$f(n)=n$ 。

当结点数为更多时

父节点有$n$ 个苹果,后继结点上均无苹果时,不难得到:

  • 当结点数为奇数时,$SG=n$ ;
  • 当结点数为偶数时,$SG=0$ 。
总结

单条链的$SG$ 值为所有奇数结点的苹果个数的异或和。

考虑一颗树的情况

一颗树其实是由若干条链组合而成的,因为题目中说明所有叶节点的深度同奇偶,故一棵树的$SG$ 值为与叶节点同奇偶的所有结点上苹果个数的异或和。

换苹果的方案

设初状态的$SG$ 值为$res$ ,所有层数与叶节点奇偶性相同的结点组成的集合为$S$ ,所有层数与叶节点奇偶性不同的结点组成的集合为$T$。

若$res=0$ ,即没交换前先手已经为输,此时$S$ 中结点可以互相交换,$T$ 中结点也可以互相交换。

之后将$T$ 中每个结点与$res$ 异或得到$temp_x$,若在$S$ 中找到与$temp_x$ 相等的结点,那么这两个结点可以互相交换。

代码如下:

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
#include <cstdio>
#include <vector>
#include <map>
#define X first
#define Y second
#define N 100005
using namespace std;
int n,a[N],p;
long long ans;
vector<int>e[N],b[2];
map<int,int>mp[2];
int dfs(int u,int d){
int deep=d;
b[d&1].push_back(a[u]);
mp[d&1][a[u]]++;
for(int i=0;i<(int)e[u].size();++i)
deep=max(deep,dfs(e[u][i],d+1));
return deep;
}
int main(void){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=2;i<=n;++i){
scanf("%d",&p);
e[p].push_back(i);
}
int d=dfs(1,0);
int res=0;
for(int i=0;i<(int)b[d&1].size();++i)
res^=b[d&1][i];
if(res==0){
int tot=b[d&1].size();
ans+=(long long)tot*(tot-1)/2;
tot=b[!(d&1)].size();
ans+=(long long)tot*(tot-1)/2;
}
for(map<int,int>::iterator it=mp[!(d&1)].begin();it!=mp[!(d&1)].end();++it){
int temp=res^it->X;
ans+=(long long)(it->Y)*mp[d&1][temp];
}
printf("%I64d\n",ans);
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×