Codeforces Round 162 (Div. 2)(A - E)
Dashboard - Codeforces Round 162 (Div. 2) - Codeforces
A. Colorful Stones (Simplified Edition)（模拟）
模拟一下即可
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
string s1 , s2;
signed main(){
cin >> s1 >> s2;
s1 = '?' + s1;
s2 = '?' + s2;
int pos = 1;
int n = s2.size();
for(int i = 0 ; i < n ; i ++) {
if(s2[i] == s1[pos]) pos += 1;
}
cout << pos << "\n";
return 0;
}
B. Roadside Trees (Simplified Edition)（模拟 + 贪心）
手模一下 ， 可以发现 ， 贪心的从左往右处理就是最优的 ， 如果先处理右边的一定还要回来处理左边的 ， 往返时会产生花费的。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
int h[N] , n;
signed main(){
cin >> n;
for(int i = 1 ; i <= n ; i ++) cin >> h[i];
int now = 0 , res = 0;
for(int i = 1 ; i <= n ; i ++) {
if(i == 1) {
res += abs(now - h[i]) + 1;
now = h[i];
} else {
res += abs(now - h[i]) + 2;
now = h[i];
}
}
cout << res << "\n";
return 0;
}
//freopen("文件å.in","r",stdin);
//freopen("文件å.out","w",stdout);
C. Escape from Stones（链表）
模拟一下操作不难发现就是需要模拟链表操作 ， 数组模拟链表即可。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int start = 1e6 + 1 , ed = 1e6 + 2;
int pre[N] , nex[N] , now = 1 , n;
string s;
signed main(){
pre[1] = start;
nex[start] = 1;
nex[1] = ed;
pre[ed] = 1;
cin >> s;
n = s.size();
s = "??" + s;
for(int i = 2 ; i <= n ; i ++) {
if(s[i] == 'l') {
pre[i] = pre[now];
nex[pre[now]] = i;
pre[now] = i;
nex[i] = now;
} else {
nex[i] = nex[now];
pre[nex[now]] = i;
nex[now] = i;
pre[i] = now;
}
now = i;
}
for(int i = nex[start] ; i != ed ; i = nex[i]) {
cout << i << "\n";
}
return 0;
}
//freopen("文件å.in","r",stdin);
//freopen("文件å.out","w",stdout);
D. Good Sequences(dp + 数论)
考虑 dp ， 设计状态
d p [ i ] 为选择以 i 结尾的最大序列长度 dp[i] ~为选择以 i 结尾的最大序列长度 dp[i] 为选择以i结尾的最大序列长度
不难想出一个 O(n^2logn)的一个状态转移 ， 考虑优化 , 当前位置可以从前面的数转移过来当前仅当前面的数和当前位置的数有公因子 ， 考虑维护每个一个因子对应的最大贡献值 ， 然后每个数从因子转移即可 ， 复杂度O(nsqrt(n)) , 维护质因子可以做到O(nlogn)
复杂度 ( O ( n n ) ) 复杂度(O(n\sqrt n)) 复杂度(O(nn))
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
int n , a[N] , dp[N] , pre[N];
signed main(){
IOS
cin >> n;
for(int i = 1 ; i <= n ; i ++) cin >> a[i] , dp[i] = 1;
for(int i = 1 ; i <= n ; i ++) {
for(int j = 1 ; j * j <= a[i] ; j ++){
if(a[i] % j == 0) {
if(j > 1) dp[i] = max(dp[i] , pre[j] + 1);
dp[i] = max(dp[i] , pre[a[i] / j] + 1);
}
}
for(int j = 1 ; j * j <= a[i] ; j ++) {
if(a[i] % j == 0) {
pre[j] = max(pre[j] , dp[i]);
pre[a[i] / j] = max(pre[a[i] / j] , dp[i]);
}
}
}
int res = 0;
for(int i = 1 ; i <= n ; i ++) {
res = max(res , dp[i]);
}
cout << res << "\n";
return 0;
}
//freopen("文件å.in","r",stdin);
//freopen("文件å.out","w",stdout);
E. Choosing Balls(dp 优化)
考虑 dp ， 设计状态
d p [ i ] 为第 i 种颜色结尾序列的最大贡献 dp[i] ~为第i种颜色结尾序列的最大贡献 dp[i] 为第i种颜色结尾序列的最大贡献
考虑如何转移
对于第一种操作 即 : v[i] * a
当且仅当当前颜色非第一次出现时才可转移
对于第二种操作 即 : v[i] * b
任何时候都可以进行第二种操作 即：
dp[c[i]] = dp[c[i]] + v[i] * a;
dp[c[i]] = max(dp[j ≠ c[i]]) + v[i] * b
对于第二个转移来说显然是O(n^2)的 ， 考虑维护最大值和次大值来O(1) 的转移。
时间复杂度 O ( n q ) 时间复杂度O(nq) 时间复杂度O(nq)
一些易错点：
1. 首先对于 dp 数组的初始化 ， 一定要初始化成 -inf ， 因为一个序列前后是有影响的 ，贡献最大的那个数列的前缀有可能贡献是负数 ， 我们也要进行统计 ， 所以要初始化成负无穷。
2. 对于最大次大值的维护 ，因为最大值可能多次出现 ， 所以尽量多用编号去维护 ， 而非值去维护 ， 注意最大次大值可能相。
2. 对于最大次大值得维护 ， 要注意最大次大值颜色应该不同 ， 不能维护两个颜色相同得最大次大值 ，这样是错误的。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
int n , q , vis[N] , dp[N] , c[N] , v[N];
int a , b;
signed main(){
IOS
cin >> n >> q;
for(int i = 1 ; i <= n ; i ++) cin >> v[i];
for(int i = 1 ; i <= n ; i ++) cin >> c[i];
for(int i = 1 ; i <= q ; i ++) {
cin >> a >> b;
for(int j = 1 ; j <= n ; j ++) dp[j] = -1e18 , vis[j] = 0;
int id1 = 0 , id2 = 0 , ans = 0;
for(int j = 1 ; j <= n ; j ++) {
int now = dp[c[j]];
//操作二
if(dp[c[j]] == dp[id1]) {
now = max(now , dp[id2] + b * v[j]);
} else {
now = max(now , dp[id1] + b * v[j]);
}
//操作一
if(!vis[c[j]]) {
vis[c[j]] = 1;
} else {
now = max(now , dp[c[j]] + a * v[j]);
}
dp[c[j]] = now;
//用编号维护最大次大值
if(id1 != c[j]){
if(dp[c[j]] > dp[id1]) id2 = id1 , id1 = c[j];
else if(dp[c[j]] > dp[id2]) id2 = c[j];
}
ans = max(ans , dp[c[j]]);
}
cout << ans << "\n";
}
return 0;
}
