突如其来的崩溃
考试经过
T1基本没有思路，大部分时间在想网络流，然而不会建图，转而投身T2，似乎哈希模拟有很多分，直接开打，T3认为比较可做然而没有什么想法，T4拿到了几乎白给的\(20pts\)之后就不会了，最后一个小时在T1获得重大进展，建出了基环树，写了一个奇怪的dp就交了
10+20+0+0=30 大跌眼镜
T1假了不说，T2暴力模拟是贪心选的，大部分人都挂了，T3没写，甚至尤其无法理解T4为何爆零
文件没问题，仔细看dp，看，看，看
是我活该了
T1.ZYB和售货机
一个显然的贪心是每个物品找到他的最优来源，然后如果能赚钱就把它取到只剩一件
剩下的会存在一些限制，形象表示出来，每个\(i\)向\(f_i\)连边，最终是一个内向基环树森林
每个节点最多只有一个出边，考虑每个树，他在环上一定有一条边不能选
对于每个节点处理出他的最优和次优来源，然后扫描一下这个环，选择一个不选他代价最小的便把他删掉
具体实现是先dfs一边划分联通块，每个联通块内dfs找环，处理每个点的最优来源和次优来源，如果环上一个点最优来源不在环上，直接删去无影响，如果全在，选一个差值最小的删去，然后减掉差值，我的实现貌似比别人复杂emmm
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=100050;
int f[N],c[N],d[N],a[N];
int mi[N],ms[N];bool v[N];
vector <int> s[N];int num;
struct node{
int from,to,next;
}b[2*N];
int head[N],mm=1;
inline void add(int x,int y)
{
b[mm].from=x;b[mm].to=y;
b[mm].next=head[x];head[x]=mm++;
}
inline void dfs(int x,int p)
{
v[x]=1;s[p].push_back(x);
for(int i=head[x];i;i=b[i].next)
{
int y=b[i].to;
if(v[y])continue;
dfs(y,p);
}
}
signed main()
{
freopen("goods.in","r",stdin);
freopen("goods.out","w",stdout);
int n;cin>>n;
for(int i=1;i<=n;i++)mi[i]=ms[i]=1e9;
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld%lld",&f[i],&c[i],&d[i],&a[i]);
mi[i]=min(mi[i],d[i]);ms[i]=min(ms[i],d[i]);
if(c[i]<=mi[f[i]])ms[f[i]]=mi[f[i]],mi[f[i]]=c[i];
else if(c[i]<ms[f[i]])ms[f[i]]=c[i];
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(mi[i]>=d[i])continue;
ans+=(d[i]-mi[i])*a[i];
if(c[i]<d[f[i]])add(i,f[i]),add(f[i],i);
}
for(int i=1;i<=n;i++)if(!v[i])dfs(i,++num);
memset(v,0,sizeof(v));mm=1;
memset(b,0,sizeof(b));memset(head,0,sizeof(head));
for(int i=1;i<=n;i++)if(c[i]<d[f[i]])add(i,f[i]);
for(int i=1;i<=num;i++)
{
if(s[i].size()==1)continue;
int x=s[i][0];bool flag=0;
while(!v[x])
{
v[x]=1;int ii=head[x];
if(!ii){flag=1;break;}
x=b[ii].to;
}
if(flag)continue;int mip=1e9,xx=x;
while(1)
{
int y=f[x];
if(c[x]==mi[y])mip=min(mip,ms[y]-mi[y]),flag=1;
x=y;if(x==xx)break;
}
if(flag)ans-=mip;
}
cout<<ans;
return 0;
}
T2.ZYB玩字符串
考场做法是暴力找匹配，每次删掉从前往后第一个串，但会被hack，比如ababaa
正解是枚举模式串\(p\)之后dp来判断，设\(f_{i，j}\)表示区间\(i,j\)是否能合法，如果长度为\(len\)的倍数就代表能否消光，否则合法条件是消完之后剩下的一定是\(p\)的前缀，考虑最后一个字符属于哪个部分
这里的prefix就代表p，不太难理解
这样复杂度上线是\(n^4\)，需要一些剪枝：
1.枚举\(p\)的时候先枚举长度，如果当前长度有合法串就不用继续了
2.用hash+stl记忆化一下，判断过的不用再判断，适用与大量相同字符的情况
3.len必须是总长度的因数，满足的len不会很多
于是就跑得飞快
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=205;
char s[N];bool f[N][N];
char ans[N];int ss=201,n;
ull p[N],ha[N];
unordered_set <ull> st;
inline void clear()
{
memset(s,0,sizeof(s));memset(f,0,sizeof(f));
memset(ans,0,sizeof(ans));
memset(ha,0,sizeof(ha));st.clear();
for(int i=1;i<=201;i++)ans[i]='z';ss=201;
}
inline bool check(int l,int r)
{
memset(f,0,sizeof(f));int ll=r-l+1;
for(int i=1;i<=n;i++)if(s[i]==s[l])f[i][i]=1;
for(int len=2;len<=n;len++)
for(int i=1;i<=n-len+1;i++)
{
int j=i+len-1;
f[i][j]|=f[i][j-1]&(s[l+(j-i)%ll]==s[j]);
for(int k=1;k<=j/ll;k++)
f[i][j]|=f[i][j-k*ll]&f[j-k*ll+1][j];
}
/**/
if(f[1][n])return 1;
return 0;
}
inline void update(int l,int r)
{
int len=r-l+1;
if(len>ss)return;
if(len<ss)
{
memset(ans,0,sizeof(ans));
for(int i=1;i<=len;i++)ans[i]=s[l+i-1];
ss=len;return;
}
else
{
for(int i=1;i<=len;i++)
{
if(ans[i]<s[l+i-1])return;
if(ans[i]>s[l+i-1])
{
memset(ans,0,sizeof(ans));
for(int j=1;j<=len;j++)ans[j]=s[l+j-1];
ss=len;return;
}
}
}
}
inline ull get(int l,int r){return ha[r]-ha[l-1]*p[r-l+1];}
signed main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
int t;cin>>t;
p[0]=1;for(int i=1;i<=200;i++)p[i]=p[i-1]*131;
while(t--)
{
clear();scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)ha[i]=ha[i-1]*131+(s[i]-'a'+1);
for(int l=1;l<=n;l++)
{
if(n%l)continue;
bool flag=0;
for(int i=1;i<=n-l+1;i++)
{
ull h=get(i,i+l-1);
if(st.find(h)!=st.end())continue;
if(check(i,i+l-1))
{
update(i,i+l-1);
flag=1;
}
st.insert(h);
}
if(flag)break;
}
printf("%s\n",ans+1);
}
return 0;
}
复习了区间dp，用dp来检验的思想还是要深入
T3.午餐
一道比较玄学的题
首先吃饭的关系显然可以转化成无向图，每条边有\(l,r\)两个权值
先算出数组\(h\)表示每个人最早什么时候以后学会，对于始终不会的就是正无穷
俩人吃饭，其实保证了在一个人没学会之前学会的人不能和他吃饭，严格来讲是多源最长路
满足限制的时候每个人越早学会越好，处理完之后再来一遍带限制最短路，处理出每个人学会的最早时间\(d\)
这里就是一个魔改dij，从当前的点x往外更新的时候要注意这么几个问题：
1.x还没学会就吃饭了，即r[i]<x，相当与没用，跳过
2.这饭不吃不要紧，一旦吃了饭y就会提前学会了，r[i]<=h[y]，也不合法
然后就用\(\max(d_x,l_i,h_y+1)\)来更新y，别的基本一样
首先判断是否有解，如果h[1]!=-1或有必然掌握的人没掌握(没更新上\(d\))，就无解
最后对于每条边判断吃饭时间：
如果俩人有一个掌握时间超过了\(r\)，那么啥时候吃都无所谓，取\(l\)就行
否则要按着晚学会的来，取\(\max(l_i,d_x,d_y)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=200050;
struct node{
int from,to,next,l,r,id,ans;
}a[2*N];
int head[N],mm=1;
inline void add(int x,int y,int l,int r,int id)
{
a[mm].from=x;a[mm].to=y;a[mm].l=l;a[mm].r=r;
a[mm].id=id;a[mm].next=head[x];head[x]=mm++;
}
inline void die(){puts("Impossible");exit(0);}
int n,m,h[N],d[N],p[N],ans[N];bool v[N];
priority_queue <pair<int,int> > q;
inline void dij()
{
h[1]=-1;
for(int i=1;i<=n;i++)if(h[i]==1e12)q.push(make_pair(h[i],i));
while(q.size())
{
int x=q.top().second,w=q.top().first;q.pop();
if(v[x])continue;
for(int i=head[x];i;i=a[i].next)
{
int y=a[i].to;if(a[i].r>w)continue;
if(a[i].l>h[y])h[y]=a[i].l,q.push(make_pair(h[y],y));
}
v[x]=1;
}
}
inline void dijj()
{
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
d[1]=h[1]+1;q.push(make_pair(0,1));
while(q.size())
{
int x=q.top().second,w=-q.top().first;q.pop();
if(v[x])continue;
for(int i=head[x];i;i=a[i].next)
{
int y=a[i].to;
if(a[i].r<d[x]||a[i].r<=h[y])continue;
if(max(max(d[x],a[i].l),h[y]+1)<d[y])
d[y]=max(max(d[x],a[i].l),h[y]+1),q.push(make_pair(-d[y],y));
}
v[x]=1;
}
}
signed main()
{
freopen("lunch.out","w",stdout);
freopen("lunch.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,l,r;scanf("%lld%lld%lld%lld",&x,&y,&l,&r);
add(x,y,l,r,i);add(y,x,l,r,i);
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&p[i]);
if(p[i]==-1)h[i]=1e12;
}
dij();memset(v,0,sizeof(v));
if(h[1]!=-1)die();dijj();
for(int i=1;i<=n;i++)if(p[i]==1&&d[i]>1e12)die();
for(int i=1;i<mm;i+=2)
{
int id=a[i].id,x=a[i].from,y=a[i].to;
if(max(d[x],d[y])>a[i].r)ans[id]=a[i].l;
else ans[id]=max(a[i].l,max(d[x],d[y]));
}
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}
T4.计数
见此
考试总结
低级错误一定要避免，考虑问题要仔细，一定要想正确性
时间还是要正确分配的，得分硬道理