2022杭电多校第4场
contest传送门
战况
这次队友的发挥直接起飞，我依旧是算是爆零了((
这次还是没有出现字符串题目。
补题
07-Climb Stairs
题意
有点像最近网上多次出现的智障广告小游戏
主人公，有一个战斗力，初始时在第 $0$ 层，每一次最多可以向上跳 $k$ 层，或者向下跳一层。每一层都有一个怪兽，有战斗力 $a_i$ 。主人公每次只能达到怪物的战斗力小于等于他的战斗力的所在的层，每到达一层，他都能抢夺怪物的战斗力，加到自己的战斗力上。
每一层最多只能访问一次。
问他能否把所有的怪物都消灭。
思路
根据主人公的运动方式限制，可以得出他只能按照类似于这种运动方式进行运动。
于是我们可以直接使用贪心思想进行模拟即可，记录当前的战斗力，当前的位置，要去的位置。
直接进行模拟
代码
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
| #include<bits/stdc++.h>
#define Inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=100005;
int n,k;
LL now,a[MAXX];
inline void solve(){
scanf("%d%lld%d",&n,&now,&k);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
int l=0,las=0;
LL need=0LL,sum=0LL;
bool can=false;
for(int i=1;i<=n;++i){
if(las+k<i) break;
if(a[i]>=need)
need=a[i]-now;
else{
need=max(need-a[i],a[i]-now);
}
sum+=a[i];
if(a[i]<=now&&need<=0){
if(i==n) can=true;
now+=sum;
las=l+1;
l=i;
need=sum=0LL;
}
}
if(can) printf("YES\n");
else printf("NO\n");
}
signed main(){
int t;scanf("%d",&t);
while(t--)
solve();
return 0;
}
|
11-Link is as bear
题意
给出一个长度为 $n$ 的 $long long$ 类型的数组，有一种操作，选个 $l,r\ (1 \leq l \leq r \leq n)$ ，使里面所有的 $a[i]=xor(l,r)$ ，里面的 $xor(l,r)$ 指的是里面所有元素异或起来的值。
可以进行无数次操作，最后要求使得所有的数都相等且尽可能大，问这个最大的值等于多少。
题目保证初始数组中最少有两个数相等。
思路
可以证明，这道题中，从这 $n$ 个数里面任取一些数异或起来的方案，都是可以构造出对应的方案来做到的。
然后，这道题就转化为了在 $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<bits/stdc++.h>
#define Inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=100005;
LL d[70];
inline void init(){
for(int i=0;i<=62;++i)
d[i]=0LL;
}
inline void add(LL jj){
for(int i=62;i>=0;--i){
if(jj&(1LL<<i)){
if(!d[i]){
d[i]=jj;
break;
}
jj^=d[i];
}
}
}
inline LL getmax(){
LL ret=0LL;
for(int i=62;i>=0;--i)
ret=max(ret,ret^d[i]);
return ret;
}
int n;
LL a[MAXX];
inline void solve(){
init();
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
add(a[i]);
}
printf("%lld\n",getmax());
}
signed main(){
int t;scanf("%d",&t);
while(t--)
solve();
return 0;
}
|
01-Link with Bracket Sequence II
题意
类似于上次的合法括号序列方案。
有长度为 $n$ 的序列，这次里面有 $m$ 种括号(其实时整数表示括号)，分别用一个正数和一个负数来表示左括号和对应的右括号。同样丢失了若干位置的数字，这里是知道丢失的位置的下标，输入时，输入 $0$ 表示这个位置的数字丢失了。
问有多少种合法的括号序列方案可以补全。
思路
考虑区间dp， $f[i][j]$ 表示 $a[i]$ 和 $a[j]$ 匹配时子序列 $[i,j]$ 的合法序列方案数， $g[i][j]$ 表示子序列 $[i,j]$ 中所有合法序列方案数。
- 枚举 $i,j$ 位置上内容，如果能够形成匹配的括号对，则 $f[i][j]=k*g[i+1][j-1]$ ，其中 $k$ 为使得 $a[i]$ 和 $a[j]$ 相匹配的方案数
- $g[i][j]=g[i][k-1]+f[k][j]$ ，其中 $k$ 为枚举 $[i,j]$ 中的值。
最后答案取 $g[1][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
52
| #include<bits/stdc++.h>
#define Inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=505;
const LL mod=1000000007;
int n,m,a[MAXX];
LL f[MAXX][MAXX],g[MAXX][MAXX];
inline void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
if(n%2){
printf("0\n");
return;
}
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for(int i=0;i<=n;++i)
g[i+1][i]=1LL;
for(int len=2;len<=n;len+=2){
for(int l=1;l+len-1<=n;++l){
int r=l+len-1;
LL jj=0LL;
if(a[l]>=0&&a[r]<=0){
if(a[l]==0&&a[r]==0)
jj=(LL)m;
else if(a[l]==0||a[r]==0)
jj=1LL;
else if(a[l]+a[r]==0)
jj=1LL;
}
f[l][r]=g[l+1][r-1]*jj%mod;
for(int k=l;k<=r;++k)
g[l][r]=(g[l][r]+g[l][k-1]*f[k][r]%mod)%mod;
}
}
printf("%lld\n",g[1][n]);
}
signed main(){
int t;scanf("%d",&t);
while(t--)
solve();
return 0;
}
|
