最小值
思路：
暴力/模拟
Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
double n,m;
cin>>n>>m;
double ans=llinf;
for(int i=1;i<=n;i++)
{
double a,b;
cin>>a>>b;
ans=min(ans,m*a/b);
}
cout<<fixed<<setprecision(6)<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
出现次数
思路:
KMP/哈希.
KMP思路：
开一个数组,记录所有t在s中出现的起点.
并记录一个该数组的前缀.每次查询输出$s[r]-s[l-1]$即可.
时间复杂度$O(q)$
哈希思路:
每次暴力枚举区间中所有可能长度,是否哈希值相同即可
时间复杂度$O(n*q)$
Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
char s[N],t[N];
ull h1[N],p[N],h2[N];
ull get1(int l,int r)
{
return h1[r]-h1[l-1]*p[r-l+1];
}
ull get2(int l,int r)
{
return h2[r]-h2[l-1]*p[r-l+1];
}
//int p[N],ne[N];
void solve()
{
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++)cin>>s[i];
for(int i=1;i<=m;i++)cin>>t[i];
/* for(int i=2,j=0;i<=n;i++)//建立t的模板串
{
while(j&&p[i]!=p[j+1])j=ne[j];
if(p[i]==p[j+1])j++;
ne[i]=j;
}*/
p[0]=1;
for(int i=1;i<=n;i++)
{
h1[i]=h1[i-1]*P+s[i];
p[i]=p[i-1]*P ;
}
for(int i=1;i<=m;i++)h2[i]=h2[i-1]*P+t[i];
/* for(int i=1;i<=m;i++)cout<<t[i];
cout<<endl;
for(int i=2;i<=3;i++)cout<<s[i];
cout<<endl;*/
ull res=get2(1,m);
// cout<<get1(2,3)<<' '<<get2(1,2)<<endl;
/* if(get1(2,3)==res)cout<<"YES"<<endl;
else cout<<"NO"<<endl;*/
while(q--)
{
int l,r;
cin>>l>>r;
int ans=0;
// cout<<l<<' '<<r<<endl;
if(r-l+1<m)//如果长度就无法匹配
{
cout<<"0"<<endl;
continue;
}else
{
for(int i=l;i+m-1<=r;i++)
if(get1(i,i+m-1)==res)
{
ans++;
}
}
cout<<ans<<endl;
}
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
满二叉树等长路径
思路：
树形DP
由于如果能够增加上面边的权重,就可以使得后面每个点到$root$的路径权值更小.
因此需要优先增加两个节点,的父亲节点连向两子节点的边.
但是因此就需要首先确定其两个子节点的状态.
这个状态可以被表述为:
以左儿子为根的子树中所有叶点到左儿子的 最短路径
以右儿子为根的子树中所有叶点到右儿子的 最短路径
记x:$w[u>>1] + path_{left}$
记y:$w[u>>1|1] + path_{right}$
确定完这两个状态之后,只需要补充abs(x-y).二者的差值就可以使得 两个儿子,所形成子树的叶点,到两个儿子的路径最短且花费权值最少.
因为整个过程我都尽量考虑使用上面的边,从而使得整体花费的权值尽可能的小.所有答案一定是最小的
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int e[N],ne[N],h[N],idx;
int w[N];
ll ans=0;
int n;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
int x=0,y=0;
if((u<<1)<=n)x=dfs(u<<1);
if((u<<1|1)<=n)y=dfs(u<<1|1);
x+=w[u<<1],y+=w[u<<1|1];
ans+=abs(x-y);
return max(x,y);
}
void solve()
{
memset(h,-1,sizeof h);
cin>>n;
n=(1<<(n+1))-1;
for(int i=2;i<=n;i++)
{
cin>>w[i];
add(i/2,i);
}
dfs(1);
cout<<ans<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
