同济校赛&牛客小白月赛
两串糖果
以vij 代表区间i-j的乘积和，revij代表反转之后的区间乘积和
dpi代表1到i的区间最优结果，考虑状态转移，该状态可以由前面区间[1,j] 加上[j+1,i]这一区间的不反转或反转的最大值。因此有状态转移方程dp[i]=max(dp[i], dp[j]+max(v[j+1] [i], rev[j+1] [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
| #include <bits/stdc++.h>
#ifdef DEBUG
#define debug(x) cerr<<__LINE__<<"行 [" << #x << "] = "<<x<< endl;
#endif
using namespace std;
typedef long long ll;
const int N=5e3+10;
int n,a[N],b[N],v[N][N],rev[N][N],dp[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for (int i=1; i<=n; i++) {
cin>>a[i];
}
for (int i=1; i<=n; i++) {
cin>>b[i];
}
for (int i=n; i>=1; i--) {
for (int j=i; j<=n; j++) {
if (j==i) {
v[i][j]=a[i]*b[i];
rev[i][j]=a[i]*b[i];
}
else {
v[i][j]=v[i+1][j-1]+a[i]*b[i]+a[j]*b[j];
rev[i][j]=rev[i+1][j-1]+a[i]*b[j]+a[j]*b[i];
}
}
}
for (int i=1; i<=n; i++) {
for (int j=0; j<i; j++) {
dp[i]=max(dp[i], dp[j]+max(v[j+1][i], rev[j+1][i]));
}
}
cout<<dp[n];
return 0;
}
|
生日
首先考虑所有的状态数，每个人都有两个可供选择的日子去过生日，因此总方案为2^n^。
考虑第 i 天过生日的情况，第 i 天可能会有三个人过生日，即编号为（i，2i，2i +1）的三人，但三人不一定全部存在。所以分类讨论
当只有一个人存在，第i天没人和他一天过生日，贡献为0
当只有两个人存在时，第i天的贡献为他们两人的异或值乘上2^n-2^（因为两个人状态已确定）
当三人都存在时，有四种组合方案，第i天的贡献为四种方案的异或值相加乘上2^n-3^（因为三个人状态已确定）
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>
#ifdef DEBUG
#define debug(x) cerr<<__LINE__<<"行 [" << #x << "] = "<<x<< endl;
#endif
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,a[N],p2[N],mod=1e9+7;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
p2[0]=1;
ll sum=0;
for (int i=1; i<=n; i++) {
cin>>a[i];
p2[i]=p2[i-1]*2%mod;
}
for (int i=1; i<=n;i++) {
ll cur=0;
if (i*2<=n) {
cur+=a[i]^a[i*2];
}
if (i*2+1<=n) {
cur+=a[i]^a[i*2+1];
cur+=a[i]^a[i*2+1]^a[i*2];
cur+=a[i*2]^a[i*2+1];
sum=(sum+cur*p2[n-3])%mod;
}
else {
sum=(sum+cur*p2[n-2])%mod;
}
}
cout<<sum;
return 0;
}
|
工艺品
分类讨论
当 a<c 时，鸡尾酒一人一直做即可，答案为$$\lfloor n/a \rfloor$$
半成品的数量取决于做的慢的那一个人的速度
当(a>=c)$$\land$$ (b>=c)时，鸡尾酒最多能加工的半成品为$$\lfloor n-c/b \rfloor$$ 个
当(a>=c)$$\land$$ (b<c)时，鸡尾酒最多能加工的半成品为$$\lfloor n-b/c \rfloor $$个
当a>=c时，最后答案要加上$$\lfloor (n-half*c)/a \rfloor $$个（半成品最后集中加工最优，为加工成品留出最大的时间）
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>
#ifdef DEBUG
#define debug(x) cerr<<__LINE__<<"行 [" << #x << "] = "<<x<< endl;
#endif
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,a,b,c;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>a>>b>>c;
if (a<c) {
cout<<n/a;
}
else {
int half=0;
if (b<=c) {
half=(n-b)/c;
}
else half=(n-c)/b;
cout<<half+(n-half*c)/a;
}
return 0;
}
|
