A Rudolf and the Ticket
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int n,m,t,a[N],b[N],k,ans;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>t;
while(t--){
ans=0;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
for(int i=n;i>=1;i--){
if(a[i]>k)continue;
for(int j=m;j>=1;j--){
if(b[j]>k)continue;
if(a[i]+b[j]<=k){ans++;}
}
}
cout<<ans<<endl;
}
return 0;
}
暴力枚举
B Rudolf and 121
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int t,n,a[N],pos;
void solve(){
cin>>n;
pos=0;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n-2;i++){
a[i+1]-=2*a[i];
a[i+2]-=a[i];
if(a[i+1]<0||a[i+2]<0)pos=1;
}
if(a[n]>0||a[n-1]>0)pos=1;
if(pos)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>t;
while(t--)solve();
return 0;
}
由题意,可以遍历一次数组,进行操作。
如果修改途中有元素减到0以下或遍历结束后元素不全为0,则输出NO
C Rudolf and the Ugly String
t = int(input())
for i in range(t):
n = int(input())
s = input()
ans = s.count("map") + s.count("pie") - s.count("mapie")
print(ans)
Python...基础count操作
不想写stl...
D Rudolf and the Ball Game
#include<bits/stdc++.h>
using namespace std;
int t,n,m,x,r;
char c;
void solve(){
cin>>n>>m>>x;
vector<int>dp(n);
x--;
dp[x]=1;
for(int i=1;i<=m;i++){
cin>>r>>c;
vector<int>tmp(n);
for(int j=0;j<n;j++){
if(dp[j]){
if(c!='1')tmp[(j+r)%n]=1;
if(c!='0')tmp[(j+n-r)%n]=1;
}
}
dp=tmp;
}
int ans=count(dp.begin(),dp.end(),1);
cout<<ans<<endl;
for(int i=0;i<n;i++)
if(dp[i])cout<<i+1<<' ';
cout<<endl;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>t;
while(t--)solve();
return 0;
}
模拟。
E Rudolf and k Bridges
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
int t,n,m,k,d;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>t;
while(t--){
cin>>n>>m>>k>>d;
vector<ll>r(n);
for(int i=0;i<n;i++){
vector<int>c(m);
for(int j=0;j<m;j++){
cin>>c[j];
c[j]++;
}
vector<ll>dp(m,inf);
dp[0]=1;
deque<int>q;
for(int j=1;j<m;j++){
while(!q.empty()&&dp[j-1]<dp[q.back()])q.pop_back();
q.push_back(j-1);
if(j-q.front()>d+1)q.pop_front();
dp[j]=c[j]+dp[q.front()];
}
r[i]=dp[m-1];
}
ll ans=inf;
for(int i=0;i+k<=n;i++){
ll sum=0;
for(int j=0;j<k;j++){
sum+=r[i+j];
}
ans=min(ans,sum);
}
cout<<ans<<endl;
}
return 0;
}
F Rudolf and Imbalance
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e7+10;
void solve(){
int n,m,k;
cin>>n>>m>>k;
vector<ll>a(n);
for(int i=0;i<n;i++)cin>>a[i];
vector<ll>d(m),f(k);
for(int i=0;i<m;i++)cin>>d[i];
for(int i=0;i<k;i++)cin>>f[i];
sort(d.begin(),d.end());
sort(f.begin(),f.end());
ll gap1=0;
for(int i=1;i<n;i++){
gap1=max(gap1,a[i]-a[i-1]);
}
ll ans=gap1;
for(int i=1;i<n;i++){
if(a[i]-a[i-1]==gap1){
ll gap2=0;
for(int j=1;j<n;j++){
if(j!=i)
gap2=max(gap2,a[j]-a[j-1]);
}
ll res=gap1;
ll sum=a[i]+a[i-1];
for(int x=m-1,y=0;x>=0;x--){
while(y<k && 2*(d[x]+f[y])<sum){
y++;
}
if(y<k)res=min(res,2*(d[x]+f[y])-sum);
if(y>0)res=min(res,sum-2*(d[x]+f[y-1]));//查询中值左边最接近的数
}
res=max(gap2,(a[i]-a[i-1]+res)/2);
ans=min(ans,res);
break;
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin>>t;
//int t=1;
while(t--)solve();
return 0;
}