少有的补完一整场题，记录一下。
A. Rudolf and the Ticket
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int a[N],b[N];
void solve(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i]+b[j]<=k) ans++;
}
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}B. Rudolf and 121
显然，第一个只能是有对第二个操作来变为0.当第一个变为0后，可以把第二个看成继续。简单模拟一下，最后判断是否全为0即可。
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],b[N];
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++) a[i]=0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[i]+=x;
if(i<n-1&&a[i]>=0){
a[i+1]-=2*a[i];
a[i+2]-=a[i];a[i]=0;
}
}
bool fl=1;
//cout<<'\n';
for(int i=1;i<=n;i++){
//cout<<a[i]<<' ';
if(a[i]) fl=0;
}
if(fl) cout<<"YES\n";
else cout<<"NO\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}C. Rudolf and the Ugly String
显然的，注意到mapie时只算一个即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char c[N];
void solve(){
int n;
char ch;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
cin>>c[i];
if(c[i]=='p'){
if(i>2){
if(c[i-2]=='m'&&c[i-1]=='a'){
ans++;
c[i]=' ';
continue;
}
}
}
else if(c[i]=='e'){
if(i>2){
if(c[i-2]=='p'&&c[i-1]=='i'){
ans++;
}
}
}
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}D. Rudolf and the Ball Game
注意到$n \leq 1000 , m \leq 1000$，所以我们可以直接使用$O(nm)$的dp。
即我们关注每一回合都有哪些个位置的玩家有可能接到球。
转移时从上一回合转移即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
bool dp[N][N];
int n;
int change(int x,int k){
int res=(x+k+n)%n;
if(!res) res=n;
return res;
}
void solve(){
int m,x;
cin>>n>>m>>x;
for(int i=0;i<=m;i++) for(int j=1;j<=n;j++) dp[i][j]=0;
dp[0][x]=1;
for(int i=1;i<=m;i++){
int d;
char op;
cin>>d>>op;
if(op=='0'){
for(int j=1;j<=n;j++){
if(dp[i-1][j]) dp[i][change(j,d)]=1;
}
}
else if(op=='1'){
for(int j=1;j<=n;j++){
if(dp[i-1][j]) dp[i][change(j,-d)]=1;
}
}
else{
for(int j=1;j<=n;j++){
if(dp[i-1][j]) dp[i][change(j,d)]=1,dp[i][change(j,-d)]=1;
}
}
}
int ans=0;
queue<int> q;
for(int i=1;i<=n;i++) if(dp[m][i]) ans++,q.push(i);
cout<<ans<<'\n';
while(q.size()){
cout<<q.front()<<' ';;
q.pop();
}
cout<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}E. Rudolf and k Bridges
单调队列优化dp板子题（可以去搜索烽火传递）。
唯一一点题目要注意的是要选的是最小的连续的k行，而不是最小的k行。（因为我WA了一发）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,k,d;
int a[N];
int dp[N];
int ress[N];
void solve(){
cin>>n>>m>>k>>d;
vector<int> ve;
int minn=0;
int ans=1e18;
for(int i=1;i<=n;i++){
deque<pair<int,int> > q;
for(int j=1;j<=m;j++){
cin>>a[j];
if(q.size()&&j-q.front().second>d+1) q.pop_front();
if(q.size()) dp[j]=q.front().first+a[j]+1;
else dp[j]=1;
while(q.size()&&dp[j]<=q.back().first) q.pop_back();
q.push_back({dp[j],j});
}
ress[i]=dp[m];
minn+=ress[i];
if(i>=k){
minn-=ress[i-k];
ans=min(ans,minn);
}
//cout<<ress[i]<<' ';
ve.push_back(dp[m]);
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}F. Rudolf and Imbalance
首先呢，模拟一下，显然，答案要么是差分后最大的值，要么就是max(次大值，将最大的值拆开后的两个数中的最大值)。
然后呢对于$d$中确定的一个$d_{i}$，显然，答案的值关于选择的$f_{i}$的大小呈现一个单峰函数的图像。
所以可以使用三分或者双指针的方法。在这里由于我搞不清楚双指针要怎么维护，所以直接套了个三分。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,k,idx;
int a[N],b[N],c[N];
int check(int x){
return max(abs(x-a[idx]),abs(x-a[idx+1]));
}
void solve(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
//if(i>2) ;
}
for(int i=1;i<=m;i++) cin>>b[i];
for(int i=1;i<=k;i++) cin>>c[i];
sort(b+1,b+1+m);
//cout<<b[1]<<'\n';
sort(c+1,c+1+k);
int maxn1=0,maxn2=0;
for(int i=2;i<=n;i++){
if(a[i]-a[i-1]>maxn1){
maxn2=maxn1;
maxn1=a[i]-a[i-1];
idx=i-1;
}
else{
if(a[i]-a[i-1]>=maxn2){
maxn2=a[i]-a[i-1];
}
}
}
if(maxn2==maxn1){
cout<<maxn2<<'\n';
return;
}
int minn=maxn1;
for(int i=1;i<=m;i++){
int l=1,r=k;
while(r-l>=10){
int mid1=l+(r-l)/3;
int mid2=r-(r-l)/3;
if(check(b[i]+c[mid1])>check(b[i]+c[mid2])){
l=mid1;
}
else{
r=mid2;
}
}
int maxn=1e18;
for(int j=l;j<=r;j++){
//cout<<i<<' '<<j<<' '<<check(b[i]+c[j])<<'\n';
maxn=min(maxn,check(b[i]+c[j]));
}
minn=min(minn,maxn);
}
cout<<max(minn,maxn2)<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}G. Rudolf and Subway
一个点对于某些点的距离为0，到某些点的距离为1。
有一种做法是可以将在同一个颜色路径上的点全部与一个虚拟节点相连。对于边权到虚拟节点为1，虚拟节点到原来的点为0。（为1表示走这条路线，之后再走相同颜色的路线时价值为0）
还有一种做法是对于一个点，把该点正在走的路径作为一个状态记录下来。由于状态数不多，所以不会爆内存。（其实我是看的jiangly的写法）
然后还有一点就是由于边的边权都是1或者0.所以可以使用双端队列优化bfs的方法来优化。
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
struct node{
int d,x,c;
};
void solve(){
cin>>n>>m;
vector<map<int,vector<int> > > ne(n+1);
for(int i=1;i<=m;i++){
int u,v,c;
cin>>u>>v>>c;
ne[u][c].push_back(v);
ne[v][c].push_back(u);
}
int ss,tt;
cin>>ss>>tt;
map<pair<int,int>,int> d;
deque<node> q;
q.push_back({0,ss,0});
while(q.size()){
auto [dd,x,c]=q.front();
q.pop_front();
if(d.count({x,c})) continue;
d[{x,c}]=dd;
if(c){
q.push_front((node){dd,x,0});
for(auto v:ne[x][c]){
q.push_front((node){dd,v,c});
}
}
else{
for(auto [c,_]:ne[x]){
q.push_back((node){dd+1,x,c});
}
}
}
cout<<d[{tt,0}]<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}