day18
程序员文章站
2022-08-02 10:38:36
今天的题好难啊！！！！80/300； T1第一眼像个树形DP，推了大约30min无果，改写暴力还写挂了！！！！0/100 正解：贪心，每次选最小的花费，向上更新看是否合法； #include #include #include #include
今天的题好难啊！！！！80/300；
t1第一眼像个树形dp，推了大约30min无果，改写暴力还写挂了！！！！0/100
正解：贪心，每次选最小的花费，向上更新看是否合法；
#include<iostream>
#include<cstdio>
#include<vector>
#include<cctype>
#include<algorithm>
using namespace std;
struct node{
int e,fa;
}a[1010];
int fa[1010],w[1010];
int n,ans,total;
bool v;
inline int cmp(node x,node y){return x.e<y.e;}
inline int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
inline void check(int x,int i)
{
if(i==0)return;
if(w[i]>=x)
{
check(x,fa[i]);
}
else
{
v=0;
return;
}
}
inline void updata(int x,int i)
{
if(i==0)return;
w[i]-=x;
updata(x,fa[i]);
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
fa[i]=read();a[i].e=read();w[i]=read();
a[i].fa=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
v=1;
check(a[i].e,a[i].fa);
if(v){total++;updata(a[i].e,a[i].fa);}
}
cout<<total<<endl;
return 0;
}
t2发现答案只在右端点，写了一个o（n/2+n2/2）的算法，拿了60分（吸一口氧可拿80）60/100
正解，把 l 和 r 丢到一个数组中排序，处理一个 sa 记录全部 l 的和，sp 记录现在在几个区间中，
遇到一个 l 端点 sa--,sp++;遇到一个 r 端点 先判断是否要更新答案，然后 sp--;复杂度极低；
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
long long l,r;
}c[210000];
int n,l[110000],r[110000];
inline long long maxx(long long x,long long y){return x>y?x:y;}
inline int cmp(node x,node y)
{
return x.l<y.l;
}
inline int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int main()
{
n=read();long long sa=0,sp=0,ans1,ans=-1;
for(int i=1;i<=n;i++)
{
l[i]=read();r[i]=read();
sa+=l[i];
c[i].l=l[i];c[i+n].r=1;
c[i+n].l=r[i];
}
sort(c+1,c+1+2*n,cmp);
for(int i=1;i<=2*n;i++)
{
if(c[i].r)
{
if(ans<sa+sp*c[i].l){
ans1=c[i].l;ans=sa+sp*c[i].l;
}
sp--;
}
if(!c[i].r)
{
sa-=c[i].l;sp++;
}
}
cout<<ans1<<" "<<ans<<endl;
return 0;
}
t3写了一个暴力匹配结果炸了？？？20/100
把a串以*分割成几个子串，b串*2处理循环，在kmp搞一下，记录以某个字符为起点能匹配完a的某个子串的最近位置。
然后再扫一遍就行了。
#include<bits/stdc++.h>
using namespace std;
char a[200],b[210000],c[110][110];
int n,m,ans,next[101][101],first[51][200001],last[200001],v,gs[101];
int main()
{
scanf("%s%s",a+1,b+1);
n=strlen(a+1);m=strlen(b+1);
for(int i=1;i<=n;i++)
{
while(a[i]=='*')
i++;
gs[0]++;
while(a[i]!='*'&&i<=n)
{
c[gs[0]][++gs[gs[0]]]=a[i];
i++;
}
}
if(gs[0]==1&&n!=m)
{
cout<<'0'<<endl;
return 0;
}
for(int i=1;i<m;i++)
b[i+m]=b[i];
for(int i=1;i<=gs[0];i++)
{
int k=0;
for(int j=2;j<=gs[i];j++)
{
while(c[i][j]!=c[i][k+1]&&k)k=next[i][k];
if(c[i][j]==c[i][k+1])k++;
next[i][j]=k;
}
}
for(int i=1;i<=gs[0];i++)
{
int k=0;
for(int j=1;j<=2*m;j++)
{
while(k&&c[i][k+1]!=b[j])k=next[i][k];
if(c[i][k+1]==b[j])k++;
if(i==gs[0])last[j]=k;
if(k==gs[i]){
int l=j-k+1;
while(l&&!first[i][l])
{
first[i][l]=j;
l--;
}
k=next[i][k];
}
}
}
for(int i=1;i<=m;i++)
{
int r=i+m-1,l=i-1,g=1;
if(a[1]!='*'&&i+gs[g]-1!=first[g][i])continue;
while(l<=r&&g<=gs[0])
{
l++;
l=first[g][l];
if(!l)break;
g++;
}
if(a[n]!='*')
{
if(g!=gs[0]+1||l>r)continue;
ans+=(last[r]==gs[gs[0]]);
}
else if(g==gs[0]+1&&l<=r)ans++;
}
cout<<ans<<endl;
return 0;
}
完。