A题
题解
以样例2为例
黄色区域为可以容纳下的书, 让我们分开来计算
因为a书不可被减少, 所以a书顶上至少能够装得下
(
n
−
m
)
b
∗
(
h
−
a
)
\frac{(n-m)}{b}*(h-a)
b(n−m)∗(h−a)
然后再考虑b书头上, 设x为减少的b书
那么b书头上能够容纳
m
−
x
b
∗
(
h
−
b
)
\frac{m-x}{b}*(h-b)
bm−x∗(h−b)
根据样例很明显a书在装了
(
n
−
m
)
b
∗
(
h
−
a
)
\frac{(n-m)}{b}*(h-a)
b(n−m)∗(h−a)本b书后可能还会存在空位, 此时可以将空位让给b书, 所以b书头上可以多计算a书剩下装不下b书的区域, 这个多出来的区域就是
n
−
(
n
−
m
)
b
∗
b
n-\frac{(n-m)}{b}*b
n−b(n−m)∗b
最后得到b头上的结果为
m
−
x
+
n
−
(
n
−
m
)
b
∗
b
b
∗
(
h
−
b
)
\frac{m-x+n-\frac{(n-m)}{b}*b}{b}*(h-b)
bm−x+n−b(n−m)∗b∗(h−b)
而这个x要怎么得到, 很明显x可以二分答案
代码
bool check(ll x)
{
ant=((m-x+n-n/b*b)/b)*(k-b);//b能容纳多少本书
return (cnt+ant)>=x;
}
void solve()
{
cin>>a>>b>>n>>m>>k;
ans=n+m;
cnt=(n/b)*(k-a);//能放cnt本b书
ll l,r;
l=0,r=m-1;
while(l<=r)
{
ll mid=l+r+1>>1;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
l=max(l-1,0);
cout<<n+m-l<<endl;
return;
}
F题
题解
签到题没什么好解释的, 感觉自己写的dfs还复杂了点
这题甚至可以直接打表, 毕竟能走的路径就那么点
代码
void dfs(ll a,ll b,ll w)
{
if(a==b)
{
ans=min(ans,w);
return;
}
f[a]=1;
if(a==1)
{
cnt=2;
if(f[cnt]==0) dfs(cnt,b,w+1);
cnt=3;
if(f[cnt]==0) dfs(cnt,b,w+1);
}else if(a==2)
{
cnt=1;
if(f[cnt]==0) dfs(cnt,b,w+1);
cnt=4;
if(f[cnt]==0) dfs(cnt,b,w+1);
}else if(a==3)
{
cnt=1;
if(f[cnt]==0) dfs(cnt,b,w+1);
cnt=4;
if(f[cnt]==0) dfs(cnt,b,w+1);
}else if(a==4)
{
cnt=2;
if(f[cnt]==0) dfs(cnt,b,w+1);
cnt=3;
if(f[cnt]==0) dfs(cnt,b,w+1);
cnt=5;
if(f[cnt]==0) dfs(cnt,b,w+1);
cnt=6;
if(f[cnt]==0) dfs(cnt,b,w+1);
}else if(a==5)
{
cnt=7;
if(f[cnt]==0) dfs(cnt,b,w+1);
cnt=4;
if(f[cnt]==0) dfs(cnt,b,w+1);
}else if(a==6)
{
cnt=7;
if(f[cnt]==0) dfs(cnt,b,w+1);
cnt=4;
if(f[cnt]==0) dfs(cnt,b,w+1);
}else
{
cnt=5;
if(f[cnt]==0) dfs(cnt,b,w+1);
cnt=6;
if(f[cnt]==0) dfs(cnt,b,w+1);
}
f[a]=0;
}
void solve()
{
ll x,y,a,b,ans1,ans2;
cin>>a>>b>>x>>y;
ans=INF;
ans1=ans2=0;
dfs(a,x,0);
ans1+=ans;
ans=INF;
dfs(b,y,0);
ans1+=ans;
ans=INF;
dfs(a,y,0);
ans2+=ans;
ans=INF;
dfs(b,x,0);
ans2+=ans;
cout<<min(ans1,ans2)<<endl;
return;
}
H题
题解
这不括号配对吗, 几年没见怎么变省赛题了
遇到(不输出, 遇到-直接输出当前下标, 遇到)先输出当前下标然后输出上一个(的下标
感觉比括号配对还简单
代码
void solve()
{
cin>>n;
cin>>str;
stack<ll>s;
str=" "+str;
rep(i,1,n)
{
if(str[i]=='-') cout<<i<<' ';
else if(str[i]==')')
{
cout<<i<<' ';
cout<<s.top()<<' ';
s.pop();
}
else if(str[i]=='(') s.push(i);
}
return;
}
I题
题解
一开始还想了会, 看到数据范围直接爆搜
就是爆搜板子, 比搜有多少种排列还简单
代码
void dfs(ll x)
{
if(x==n)
{
ans++;
return;
}
ll it=n-x;
rep(i,1,it)
dfs(x+i);
}
void solve()
{
cin>>n;
dfs(0);
cout<<ans<<endl;
return;
}
L. Let’s Swap
这题把我折磨麻了, 不是t14就是t15的
题解
官方提解说 字符串哈希能写, kmp能写
然后我就用了find函数, 一直t改成kmp才过了, 麻了
两种操作, 连续使用一种操作就会使得字符串变过去又变回来, 所以只能交替使用两种操作
交替使用两种操作会发现实质上前面l1个字符串移动到了最后面 (默认l1比l2小)
所以只要将a字符串自加变成a+=a后在a中寻找b字符串就行了 (注意b字符串翻转后在a字符串内也算)
最后判断一下b字符串在a中移动的步数是否合法, 如果合法就yes反之no
在a中寻找字符串的操作不能用find!!!必须要用kmp算法, 不然会超时
代码
inline void getNext(int m){
int j = 0;
kmp_next[0] = 0;
for(int i=1; i<m; ++i)
{
while(j>0 && b[i]!=b[j]) j=kmp_next[j-1];
if(b[i]==b[j]) ++j;
kmp_next[i] = j;
}
}
inline int kmp(int n,int m){
int i, j = 0;
int p = -1;
getNext(m);
for(i=0; i<n; ++i){
while(j>0 && b[j]!=a[i]) j=kmp_next[j-1];
if(b[j]==a[i]) ++j;
if(j==m)
{
p = i - m + 1;
break;
}
}
return p;
}
inline void solve()
{
cin>>a>>b>>x>>y;
n=a.size();
a+=a;
ans=0;
if(x>y) swap(x,y);
if(kmp(2*n,n)==-1)
{
ans=1;
reverse(b.begin(),b.end());
}
cnt=kmp(2*n,n);
if(ans&&cnt==-1)
{
no
return;
}
if(ans) cnt=abs(cnt-x);
if(cnt%(__gcd(n,abs(y-x)))) no
else yes
return;
}
