【Educational Codeforces Round 53 (Rated for Div. 2)】
程序员文章站
2024-03-06 21:52:26
...
前言
O(∩_∩)O
无惧掉分
题目
A. Diverse Substring
题意
做法
坑点
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 1e5+10;
char str[maxn];
int sum[30];
int main()
{
int len;
scanf("%d%s",&len,str);
for(int i=1;i<len;i++)
{
if(str[i]!=str[i-1])
{
printf("YES\n");
cout<<str[i-1]<<str[i]<<endl;
return 0;
}
}
printf("NO\n");
return 0;
}
B. Vasya and Books
题意
做法
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 2e5+10;
int a[maxn],b[maxn];
int mp[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
mp[a[i]]=i;
}
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
int maxx=0;
for(int i=1;i<=n;i++)
{
int tmp=mp[b[i]];
printf("%d ",max(0,tmp-maxx));
maxx=max(maxx,tmp);
}
return 0;
}
C. Vasya and Robot
题意
做法
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define dbg(x) cout<<#x<<" = "<<x<<endl
const int maxn = 2e5+10;
char s[maxn];
int x,y;
int n,sum[maxn][4];//U D L R
map<char,int> mp;
int n1,n2,n3,n4;
bool check(int mid)
{
int sum1=0,sum2=0,sum3=0,sum4=0;
for(int i=1;i<=n-mid+1;i++)
{
sum1=sum[i-1][0]+sum[n][0]-sum[i+mid-1][0];
sum2=sum[i-1][1]+sum[n][1]-sum[i+mid-1][1];
sum3=sum[i-1][2]+sum[n][2]-sum[i+mid-1][2];
sum4=sum[i-1][3]+sum[n][3]-sum[i+mid-1][3];
int xx=0,yy=0;
n1=0,n2=0,n3=0,n4=0;
xx+=(sum4-sum3);
yy+=(sum1-sum2);
if(xx>=x) n3=xx-x;
else n4=x-xx;
if(yy>=y) n2=yy-y;
else n1=y-yy;
if(n1+n2+n3+n4<=mid&&(mid-n1-n2-n3-n4)%2==0) return true;
}
return false;
}
int main()
{
mp['U']=0;
mp['D']=1;
mp['L']=2;
mp['R']=3;
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;i++)
{
sum[i][0]=sum[i-1][0];
sum[i][1]=sum[i-1][1];
sum[i][2]=sum[i-1][2];
sum[i][3]=sum[i-1][3];
sum[i][mp[s[i]]]++;
}
scanf("%d%d",&x,&y);
int l=0,r=n,mid;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)) r=mid-1;
else l=mid+1;
}
if(l==n+1) printf("-1\n");
else printf("%d\n",l);
return 0;
}
D. Berland Fair
题意
做法
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
ll a[maxn];
int main()
{
int n;
ll T;
scanf("%d%lld",&n,&T);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
ll ans=0;
while(T)
{
ll sum=0;
ll cnt=0;
for(int i=1;i<=n;i++)
{
if(a[i]<=T)
{
cnt++;
sum+=a[i];
}
}
if(cnt==0) break;
if(T<sum)
{
for(int i=1;i<=n;i++)
{
if(T>=a[i])
{
ans++;
T-=a[i];
}
}
}
else
{
ans+=1LL*cnt*(T/sum);
T=T%sum;
}
}
printf("%lld\n",ans);
return 0;
}
E. Segment Sum
题意
做法
坑点
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const ll Mod = 998244353ll;
typedef pair<ll,ll> pll;
#define Se second
#define Fi first
ll l,r,k;
ll pow_[20];
int cal(ll x)
{
int ans=0;
while(x)
{
if(x&1) ans++;
x/=2;
}
return ans;
}
pll dp[20][1<<12][2];
ll a[20];
pll dfs(ll len,ll state,bool limit,bool lead)
{
if(len==0) return pll(1,0);//遍历结束,无需算对答案的贡献,但是要像正常数位dp一样统计满足条件的个数
if(!limit&&dp[len][state][lead].Se) return dp[len][state][lead];//注意带前导0的数位dp套路
pll ans=pll(0,0);
int up=limit?a[len]:9;
for(int i=0;i<=up;i++)
{
ll temp=state|((lead||i)<<i);
//若当前有前导0而且当前数位为0,则状态不更新
if(cal(temp)>k) continue;
//不满足答案的状态要去掉
pll tmp=dfs(len-1,temp,limit&&i==a[len],lead||i);
ans.Fi=(ans.Fi+tmp.Fi)%Mod;
ans.Se=(ans.Se+tmp.Se+(1LL*i*pow_[len-1]%Mod*tmp.Fi)%Mod)%Mod;
//当前数位对答案的贡献为当前数位所代表的值为i*pow[len-1]
//当前数位为i的数字个数为tmp.Fi
//总贡献为:i*pow_[len-1]%Mod*tmp.Fi
}
return dp[len][state][lead]=ans;
}
ll solve(ll x)
{
for(int i=0;i<20;i++)
{
for(int j=0;j<(1<<12);j++)
{
for(int l=0;l<2;l++)
{
dp[i][j][l].Fi=0;
dp[i][j][l].Se=0;
}
}
}
memset(a,0,sizeof(a));
int len=0;
while(x)
{
a[++len]=x%10;
x/=10;
}
return dfs(len,0,true,0).Se%Mod;
}
int main()
{
pow_[0]=1;
for(int i=1;i<20;i++) pow_[i]=pow_[i-1]*10%Mod;//每一位的贡献预处理
scanf("%lld%lld%lld",&l,&r,&k);
printf("%lld\n",(solve(r)-solve(l-1)+Mod)%Mod);
return 0;
}
推荐阅读
-
【Educational Codeforces Round 53 (Rated for Div. 2)】
-
Educational Codeforces Round 42 (Rated for Div. 2) E. Byteland, Berland and Disputed Cities
-
Educational Codeforces Round 53 (Rated for Div. 2)
-
Educational Codeforces Round 53 (Rated for Div. 2)D(模拟)
-
Educational Codeforces Round 53 (Rated for Div. 2) D - Berland Fair
-
Educational Codeforces Round 53 (Rated for Div. 2)
-
Educational Codeforces Round 53 (Rated for Div. 2)D. Berland Fair
-
【 Educational Codeforces Round 53 (Rated for Div. 2) D. Berland Fair】思维题
-
Codeforces Round #561 (Div. 2) C. A Tale of Two Lands
-
Codeforces Round #459 (Div. 2) C. The Monster(枚举+思维)