因为这次难得不在十点半(或是更晚)，大家都在打，然后我又双叒叕垫底了=。=
自己对时间的分配，做题的方法和心态还是太蒻了，写的时候经常写一半推倒重来。还有也许不是自己写不出来，而是在开始写之前就觉得自己写不出来
多打CF
A.Sea Battle
讨论.jpg
也有式子的解法，我没想
B.Draw
讨论失败.jpg
(写题顺序：ADFC，没有B)
讨论个**，转化成线段求交，答案就是$\sum max(0,min(x,y)-max(lstx,lsty)+(lstx!=lsty))$，记得加上一开始的1
C.Birthday
赛场降智->枚举两边$n^2$+排序后中间轮着放检查$n$->$n^3$睿智算法
正确答案->不知为啥还要枚举，排序以后直接轮着放->$n\log n$
D.Gourmet choice
并查集+拓扑排序
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=;
int num[N],aset[N],que[N],bel[N];
int p[N],noww[M],goal[M],deg[N];
int n,m,f,b,t1,t2,cnt,tot,ff;
char rd[][];
int Finda(int x)
{
return x==aset[x]?x:aset[x]=Finda(aset[x]);
}
void Link(int f,int t)
{
noww[++cnt]=p[f],deg[t]++;
goal[cnt]=t,p[f]=cnt;
}
int main ()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n+m;i++) aset[i]=i;
for(int i=;i<=n;i++)
{
scanf("%s",rd[i]+);
for(int j=;j<=m;j++)
if(rd[i][j]=='=')
aset[Finda(i)]=Finda(j+n);
}
for(int i=;i<=n+m;i++) bel[i]=Finda(i);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(rd[i][j]=='<') Link(bel[i],bel[j+n]);
if(rd[i][j]=='>') Link(bel[j+n],bel[i]);
}
for(int i=;i<=n+m;i++)
if(!deg[i]) que[++b]=i,num[i]=;
while(f<=b)
{
int tn=que[f++];
for(int i=p[tn];i;i=noww[i])
if(!(--deg[goal[i]]))
que[++b]=goal[i],num[goal[i]]=num[tn]+;
}
for(int i=;i<=n+m;i++) if(deg[i]) printf("No"),exit(); puts("Yes");
for(int i=;i<=n;i++) printf("%d ",num[bel[i]]); puts("");
for(int i=n+;i<=n+m;i++) printf("%d ",num[bel[i]]);
return ;
}
E.String Multiplication
请讨论.jpg
答案只和最大子段，前缀连续和后缀连续有关，枚举哪个字符作为答案之后再统计就比较简单了
但是仍然有很多细节=。=
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=;
string str[N]; long long ans;
int main()
{
int n; cin>>n;
for(int i=;i<=n;i++)
cin>>str[i];
for(int i='a';i<='z';i++)
{
long long maxi=;
for(int j=;j<=n;j++)
{
int len=str[j].size();
long long lst=,tmp=,pre=,suf=;
for(int k=;k<len;k++)
(str[j][k]==i)?lst=max(lst,++tmp):tmp=;
if(lst||maxi)
{
for(int k=;k<len;k++)
if(str[j][k]==i) pre++;
else break;
for(int k=len-;~k;k--)
if(str[j][k]==i) suf++;
else break;
if(lst==len) maxi=(maxi+)*lst+maxi;
else maxi=maxi?max(lst,pre+suf+):lst;
}
}
ans=max(ans,maxi);
}
printf("%lld",ans);
return ;
}
F.Asya And Kittens
并查集维护小猫之间的连通性，同时维护每只小猫的下一只小猫和当前小猫链里最后一只小猫是谁。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,st,t1,t2,cnt;
int aset[N],nxt[N],endp[N];
int Finda(int x)
{
return x==aset[x]?x:aset[x]=Finda(aset[x]);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) aset[i]=endp[i]=nxt[i]=i;
for(int i=;i<n;i++)
{
scanf("%d%d",&t1,&t2);
int t3=Finda(t1),t4=Finda(t2);
aset[t3]=t4,nxt[endp[t4]]=t3,endp[t4]=endp[t3];
}
for(int i=;i<=n;i++)
if(Finda(i)==i) {st=i; break;}
while(nxt[st]!=st)
printf("%d ",st),st=nxt[st];
printf("%d",st);
return ;
}
G.Most Dangerous Shark
单调栈优化DP，代码咕咕了