4311. 最小值【签到】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
int n,m;
double ans=1e9,a,b;
int main(void)
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a>>b,ans=min(ans,a/b);
    printf("%.6lf\n",m*ans);
	return 0;
}

4312. 出现次数【前缀和 / KMP】

在这里插入图片描述
用的KMP获得位置，然后保存排序。
每次询问暴力查找，但过了r的时候break
比赛的时候想的前缀和，但是那个边界处理没想明白。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5*2+10;
int n,m,k,s[N];
char a[N],b[N];//让其下标从1开始
int ne[N];//ne[i]表示前i个字符的最长的相等的前后缀
vector<pair<int,int>>ve;
void init()
{
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&a[i]!=a[j+1]) j=ne[j];
        if(a[i]==a[j+1]) j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=m;i++)
    {
        while(j&&b[i]!=a[j+1]) j=ne[j];
        if(b[i]==a[j+1]) j++;
        if(j==n)//求a在b出现的所有的位置
        {
            ve.push_back({i-n+1,i});
            j=ne[j];
        }
    }
}
int main(void)
{
    cin>>m>>n>>k;
    cin>>b+1>>a+1;
    init();
    sort(ve.begin(),ve.end());
    while(k--)
    {
        int l,r; scanf("%d%d",&l,&r);
        int cnt=0;
        for(int i=0;i<ve.size();i++)
        {
            int x=ve[i].first,y=ve[i].second;
            if(l<=x&&y<=r) cnt++;
            if(y>r) break;
        }
        printf("%d\n",cnt);
    }
	return 0;
}

前缀和做法：我们将子串的开头作为标识。
故求 [l,r] 内的子串个数等于s[r-b.size()+1]-s[l-1]

#include<bits/stdc++.h>
using namespace std;
const int N=1e5*2+10;
int n,m,k,s[N];
string a,b;
int main(void)
{
    cin>>m>>n>>k;
    cin>>a>>b;
    a="0"+a;
    for(int i=1;i<a.size();i++)
    {
        s[i]=s[i-1];
        if(a.substr(i,b.size())==b) s[i]++;
    }
    while(k--)
    {
        int l,r; scanf("%d%d",&l,&r);
        r=r-b.size()+1;
        if(r<l) cout<<0<<endl;
        else cout<<s[r]-s[l-1]<<endl;
    }
	return 0;
}

4313. 满二叉树等长路径【递归 / 贪心】

在这里插入图片描述

//递归加贪心，因为是路径和，只要父节点增加，
//对应的子节点都会增加，所以只要把每个子节点搞成相同的即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int w[N],n,ans;
int dfs(int u)//子树到u的距离
{
    if(u>=pow(2,n+1)) return 0;
    int l=dfs(u*2)+w[u*2];
    int r=dfs(u*2+1)+w[u*2+1];
    ans+=abs(l-r);//俩子树弄成相同的值的花费
    return max(l,r);
}
int main(void)
{
    cin>>n;
    for(int i=2;i<pow(2,n+1);i++) cin>>w[i];
    dfs(1);
    cout<<ans;
    return 0;
}