A - A Healthy Breakfast
高桥日常出境。
头一次知道 getchar() 的返回值是 int。
点击查看代码
#include<cstdio>
using namespace std;
int main()
{
char s[3]={getchar(),getchar(),getchar()};
if(s[0]=='R'&&s[1]=='M') puts("Yes");
else if(s[0]=='R'&&s[2]=='M') puts("Yes");
else if(s[1]=='R'&&s[2]=='M') puts("Yes");
else puts("No");
return 0;
}
B - Vertical Reading
题目可以转化成从 \(c\) 开始，每次跳 \(w\) 个字符。
所以直接枚举 \(c\) 和 \(w\) + 暴力判断。
点击查看代码
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
int n,m;
char s[N],t[N];
int main()
{
scanf("%s%s",s+1,t+1);
n=strlen(s+1),m=strlen(t+1);
for(int w=1;w<n;w++)
for(int c=1;c<=w;c++)
{
bool flag=true;
int p=1;
for(int i=c;i<=n;i+=w,p++)
{
if(s[i]!=t[p])
{
flag=false;
break;
}
}
p--;
if(flag && p==m)
{
printf("Yes\n");
return 0;
}
}
printf("No\n");
return 0;
}
C - Move It
贪心，在每个盒子里多出的物品中选最轻的拿走。
点击查看代码
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,a[N],w[N];
vector<int> box[N];
bool cmp(int x,int y){return w[x]<w[y];}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
box[a[i]].push_back(i);
}
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
long long ans=0;
for(int i=1;i<=n;i++)
{
sort(box[i].begin(),box[i].end(),cmp);
for(int j=0;j<(int)box[i].size()-1;j++)
ans+=w[box[i][j]];
}
printf("%lld\n",ans);
return 0;
}
D - Ghost Ants
同向蚂蚁永远不互相穿过，所以只用考虑不同向的蚂蚁；又因为正向蚂蚁和逆向蚂蚁互相穿过只算一对，所以只用考虑每只正向蚂蚁会穿过多少逆向蚂蚁。
很明显，会和在 \(a_i\) 处的正向蚂蚁互相穿过的逆向蚂蚁的起始坐标应当在区间 \([a_i,a_i+2t]\) 内，所以将逆向蚂蚁排序以后二分（可以用 lower_bound 和 `upper_bound）找在这个区间内最左和最右的蚂蚁编号，其间蚂蚁的数量就可以累计到答案里。
点击查看代码
#include<cstdio>
#include<bitset>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n,aidx,bidx;
long long t,a[N],b[N];
char str[N];
bitset<N> type;
int main()
{
scanf("%d%lld%s",&n,&t,str+1);
for(int i=1;i<=n;i++)
type[i]=str[i]-'0';
for(int i=1;i<=n;i++)
{
long long x; scanf("%lld",&x);
if(type[i]) a[++aidx]=x;
else b[++bidx]=x;
}
sort(b+1,b+bidx+1);
long long ans=0;
for(int i=1;i<=aidx;i++)
{
int l=lower_bound(b+1,b+bidx+1,a[i])-b;
int r=upper_bound(b+1,b+bidx+1,a[i]+(t<<1))-b-1;
ans+=(r-l+1);
}
printf("%lld\n",ans);
return 0;
}
E - Random Swaps of Balls
之前从来没有接触过这方面的题目（DP 概率），所以第一眼就放弃然后去做后面的题了。
算法是从这篇题解里学习的，这里就不多赘述了。
#include<cstdio>
#define LL long long
using namespace std;
const int K=1e5+5,P=998244353;
LL n,k,f[K];
LL quick_pow(LL x,LL y)
{
LL res=1;
while(y)
{
if(y&1) res=res*x%P;
x=x*x%P;
y>>=1;
}
return res;
}
LL inv(LL x){return quick_pow(x,P-2);}
int main()
{
scanf("%lld%lld",&n,&k);
LL leave=(((n-1)*inv(n*n%P))<<1)%P;
LL back=(inv(n*n%P)<<1)%P;
f[0]=1;
for(int i=1;i<=k;i++)
{
f[i]=(1-leave)*f[i-1]+back*(1-f[i-1]);
f[i]=(f[i]%P+P)%P;
}
LL ans = f[k] + (1-f[k])*inv(n-1)%P * (2+n)%P*(n-1)%P*inv(2)%P;
printf("%lld\n",(ans%P+P)%P);
return 0;
}
G - Suitable Edit for LIS
第一眼感觉很可做的样子，最后居然独立切出来了（虽然不是场切）。
不过我这个方法细节特别多，而且似乎是个假做法（对拍了 \(3000+\) 组数据后发现了 Hack 数据，不过这个做法也可以说 \(99.99\%\) 正确吧，至少题目数据没有能 Hack 掉我）。
简而言之就是在原本树状数组求 LIS 的基础上各种判断是否能新插入一个数进去，而且在序列长度相同情况下的选择优先级也需要很仔细。
因为不一定正确就不写解析了。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=2e5+5;
int n,a[N],f[N];
bool added[N];
unordered_map<int,int> c;
inline int lowbit(int x){return x&-x;}
bool cmp_greater(int x,int y) //x>y
{
if(f[x]!=f[y]) return f[x]>f[y];
if(added[x]!=added[y]) return added[x]<added[y];
if(a[x]!=a[y]) return a[x]<a[y]; //这一行和下一行可能交换与否都有可能出最优解
if(x!=y) return x<y;
return false;
}
int maxp(int x,int y)
{
return cmp_greater(x,y)?x:y;
}
void update(int x,int y)
{
for(x++;x<=1e9;x+=lowbit(x))
c[x]=maxp(c[x],y);
return;
}
int query(int x)
{
int res=0;
for(x++;x;x-=lowbit(x))
res=maxp(res,c[x]);
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int ans=0;
a[0]=-0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
int pos=query(a[i]-1);
if(pos!=i-1 && a[pos]!=a[i]-1 && !added[pos])
{
printf("added in %d\n",i);
added[i]=true;
f[i]=f[pos]+2;
update(a[i],i);
}
else
{
added[i]=added[pos];
f[i]=f[pos]+1;
update(a[i],i);
}
printf("f[%d]=%d(from %d)\n",i,f[i],pos);
if(i!=n && !added[i]) ans=max(ans,f[i]+1);
else ans=max(ans,f[i]);
}
printf("%d\n",ans);
return 0;
}