A. Rudolf and the Ticket
题意：
有两个数组\(b_n\)和\(c_m\),两个数组中分别取一个数相加是否小于k，有几种方法使\(b_f\)+\(c_s\)<=k
思路：
暴力枚举所有方案，时间复杂度O(nm)
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n,m,k;
cin>>n>>m>>k;
int b[n+1],c[m+1];
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=m;i++){
cin>>c[i];
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(b[i]+c[j]<=k){
ans++;
}
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
B. Rudolf and 121
题意：
有一个数组\(a_n\)，有一种操作，可以选择一个下标i，操作：\(a_{i-1}\)-=1,\(a_i\)-=2,\(a_{i+1}\)-=1。可以进行任意次操作，是否可以使数组全为0
思路：
贪心，从前往后操作使\(a_{i-1}\)=0，若\(a_i\)小于0则不行
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=2;i<n;i++){
int t=a[i-1];
if(t<0){
cout<<"NO"<<endl;
return ;
}
a[i]-=2*t;
a[i+1]-=t;
}
if(a[n-1]==0&&a[n]==0){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
C. Rudolf and the Ugly String
题意：
删除任意字符使字符串中不含map和pie
思路：
若字符串中含有map或pie，删除字符p来同时应对mapie的特殊情况
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n;
cin>>n;
string s;
cin>>s;
int ans=0;
vector<int > mp(n+1,0);
string t1="map";
string t2="pie";
for(int i=0;i<n-2;i++){
if(mp[i]==1){
continue;
}
if(s.substr(i,3)==t1){
ans++;
mp[i+2]=1;
}else if(s.substr(i,3)==t2){
ans++;
mp[i]=1;
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
D. Rudolf and the Ball Game
题意：
给一个环，环上有n个玩家，球一开始在玩家x手上，每次抛出可以选择顺时针抛出，可以逆时针抛出，也有可能不知道往哪边抛出，求结束时球可能在哪几个玩家手上
思路：
模拟即可，每次抛出时记录球一开始可能在谁手上，可能会传到谁手上,注意去重
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n,m,x;
cin>>n>>m>>x;
int r;
string c;
queue<int > Q;
Q.push(x);
for(int i=1;i<=m;i++){
cin>>r>>c;
queue <int > cnt;
map<int ,int > mp;
if(c[0]=='?'){
while(!Q.empty()){
int t=Q.front();
Q.pop();
if(mp[(t+r-1)%n+1]==0){
cnt.push((t+r-1)%n+1);
mp[(t+r-1)%n+1]=1;
}
if(mp[(t-r+n-1)%n+1]==0){
cnt.push((t-r+n-1)%n+1);
mp[(t-r+n-1)%n+1]=1;
}
}
}else if(c[0]=='0'){
while(!Q.empty()){
int t=Q.front();
Q.pop();
if(mp[(t+r-1)%n+1]==0){
cnt.push((t+r-1)%n+1);
mp[(t+r-1)%n+1]=1;
}
}
}else if(c[0]=='1'){
while(!Q.empty()){
int t=Q.front();
Q.pop();
if(mp[(t-r+n-1)%n+1]==0){
cnt.push((t-r+n-1)%n+1);
mp[(t-r+n-1)%n+1]=1;
}
}
}
Q=cnt;
}
vector<int > ans;
while(!Q.empty()){
ans.push_back(Q.front());
Q.pop();
}
sort(ans.begin(),ans.end());
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
E. Rudolf and k Bridges
题意：
有一个河流，要造k座连续的桥，桥墩的代价为\(a_{i,j}\)+1，桥墩间的距离不能超过d，求造桥的最小代价
思路：
计算在第i行造桥的最小代价，dp即可，状态转移方程为\(dp_j\)=\(dp_{k}\)+\(a_{i,j}\)+1,k为[j-k-1,j-1],这里枚举k的话会超时，所以这里要维护单调队列来直接得到k的值（单调队列不会的话我有时间再写一篇博客），这样求出每行的最小代价。最后选择连续的k行桥，这里前缀和然后枚举就好
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const long long INF = 0x3f3f3f3f3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n,m,k,d;
cin>>n>>m>>k>>d;
ll a[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
vector<ll > ans;
for(int i=1;i<=n;i++){
vector<ll > dp(m+1,0);
deque<int> Q; // 存储的是编号
while(!Q.empty()){
Q.pop_back();
}
dp[1]=a[i][1]+1;
Q.push_back(1);
for(int j=2;j<=m;j++){
if (!Q.empty() && j - Q.front() > d+1) // 毕业
Q.pop_front();
dp[j]=dp[Q.front()]+a[i][j]+1;
while (!Q.empty() && dp[Q.back()] > dp[j]) // 比新生弱的当场退役（求区间最小值把这里改成>即可）
Q.pop_back();
Q.push_back(j); // 新生入队
}
ans.push_back(dp[m]);
}
ll pre[n+1];
pre[0]=ans[0];
for(int i=1;i<n;i++){
pre[i]=pre[i-1]+ans[i];
}
ll cnt=INF;
cnt=pre[k-1];
for(int i=k;i<n;i++){
cnt=min(cnt,pre[i]-pre[i-k]);
}
cout<<cnt<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
F. Rudolf and Imbalance
题意：
有一个数组a，它是升序的，它的平衡性为最大的\(a_i\)-\(a_{i-1}\)，有两个数组d、f，可以从两个数组中分别选择一个数相加，将\(d_i\)+\(f_j\)插入到数组a的对应位置中，使平衡性降低，这个操作最多一次。求最小的平衡性
思路：
先找出数组中使平衡性最大的两个数，需要找到\(d_i\)+\(f_j\)插入到这两个数之间，使平衡性降低，如果暴力枚举数组d和f的所有情况，时间复杂度将达到1e10，3秒肯定超时，所以这里要进行优化，先将数组d和f排序，枚举数组d，然后对数组f进行二分，使\(d_i\)+\(f_j\)接近那两个数的中间值，最后将最接近中间值的\(d_i\)+\(f_j\)加入到数组a中，再计算一遍平衡性
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n,m,k;
cin>>n>>m>>k;
ll a[n+1],b[m+1],f[k+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
}
for(int i=1;i<=k;i++){
cin>>f[i];
}
ll mx=0;
int mx_l=0,mx_r=0;
int count=0;
for(int i=2;i<=n;i++){
if(a[i]-a[i-1]>mx){
count=1;
mx=a[i]-a[i-1];
mx_l=i-1;
mx_r=i;
}else if(a[i]-a[i-1]==mx){
count++;
}
}
if(count>1){
cout<<mx<<endl;
return ;
}
sort(b+1,b+1+m);
sort(f+1,f+1+k);
ll ans=0;
for(int i=1;i<=m;i++){
//zuocebianjie
int left = 1;
int right = k+1; // 注意
ll target=(a[mx_l]+a[mx_r])/2;
while (left < right) { // 注意
int mid = (left + right) / 2;
if (b[i]+f[mid] == target) {
right = mid;
} else if (b[i]+f[mid] < target) {
left = mid + 1;
} else if (b[i]+f[mid] > target) {
right = mid; // 注意
}
}
int res=left;
if(res>=1&&res<=k){
int t=b[i]+f[res];
if(t>=a[mx_l]&&t<=a[mx_r]){
if(max(t-a[mx_l],a[mx_r]-t)<max(ans-a[mx_l],a[mx_r]-ans)||ans==0){
ans=t;
}
}
}
//youce
left=1;
right=k+1;
target=(a[mx_l]+a[mx_r]+1)/2;
while (left < right) {
int mid = (left + right) / 2;
if (b[i]+f[mid] == target) {
left = mid + 1; // 注意
} else if (b[i]+f[mid] < target) {
left = mid + 1;
} else if (b[i]+f[mid] > target) {
right = mid;
}
}
res=left-1;
if(res>=1&&res<=k){
int t=b[i]+f[res];
if(t>=a[mx_l]&&t<=a[mx_r]){
if(max(t-a[mx_l],a[mx_r]-t)<max(ans-a[mx_l],a[mx_r]-ans)||ans==0){
ans=t;
}
}
}
}
if(ans==0){
cout<<mx<<endl;
}else{
a[0]=ans;
sort(a,a+1+n);
ll cnt=0;
for(int i=1;i<=n;i++){
cnt=max(cnt,a[i]-a[i-1]);
}
cout<<cnt<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}