B - Journey Planning
思路:
找规律
当时想了很久想了个O(n^2)的dp,然后想如何优化,其实这些数减去他们下标的差值是一样的。
Ci+1-Ci=Bi+1-Bi
Ci+2-Ci+1=Bi+2-Bi+1
Ci+1-Bi+1=Ci-Bi构造同一个数组存放即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <map>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll maxn = 1e6 + 5;
const int N = 2e5;
int b[maxn];
ll s[maxn];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>b[i];
s[b[i]-i+N]+=b[i];
}
cout<<*max_element(s,s+maxn);
return 0;
}
C - Remove Adjacent
思路:
做题的时候没读清题意,每次只能删比较大的数,所以很简单,暴力模拟,从最大的数开始删,即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <map>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll maxn = 1e6 + 5;
char ch[105];
vector<char>s;
int main(){
int n;
cin>>n>>ch;
for(int i=0;i<n;i++){
s.push_back(ch[i]);
}
for(int i='z';i>='a';i--){
for(int j=0;j<s.size();j++){
if(s[j]!=i) continue;
if(s[j]==s[j-1]+1 || s[j]==s[j+1]+1){
s.erase(s.begin()+j);
j=max(-1,j-2);
}
}
}
cout<<n-s.size();
return 0;
}