因为没A/改几道题，就一起写了
题目在LOJ上都能找到
2019.2.28
100+20+12
前两个小时一直在睡觉+想题也没思路，我太菜了
T1 洗衣服
分开处理出洗衣服和烘干的时间，然后一边正着排序一边倒着排序，依次匹配(小的配大的)
正确性......不会证，意会
#pragma GCC optimize(2)
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,m1,m2,a[N],b[N];
long long fin[N],edp[N],ans;
struct c
{
long long st,rt;
long long Endt()
{
return st+rt;
}
};
bool operator < (c x,c y)
{
return x.Endt()>y.Endt();
}
priority_queue<c> hp1,hp2;
int main()
{
scanf("%d%d%d",&n,&m1,&m2);
for(int i=;i<=m1;i++)
scanf("%d",&a[i]),hp1.push((c){,a[i]});
for(int i=;i<=m2;i++)
scanf("%d",&b[i]),hp2.push((c){,b[i]});
for(int i=;i<=n;i++)
{
c f=hp1.top(); hp1.pop();
fin[i]=f.st=f.Endt(); hp1.push(f);
}
// for(int i=1;i<=n;i++) printf("%d ",fin[i]);
for(int i=n;i;i--)
{
c f=hp2.top(); hp2.pop();
long long ed=fin[i]+f.Endt();
if(ed>ans) ans=ed; f.st=f.Endt();
hp2.push(f);
}
printf("%lld",ans);
return ;
}
T2 编码
已经忘掉有2-sat这个东西了，想起来好歹还能写个$n^2$暴力=。=
$n^2$暴力就是枚举每对串之间的关系，优化的话我们就插出一棵Trie，边走边判断：从根到叶子的每一条链上都只能有一个填1的‘？’，记录前后缀来优化
(说的简单，你又没写
T3 猜数列
题 解 人
2019.3.1
咕计得分：100+20+10
实际得分：100+20+10
睡了一个半小时，花了半个小时切了T1，咸鱼了一个半小时没想出来T2,T3，然后跑了
T1 远行
LCT+并查集维护联通块直径，由直径性质可知每次答案一定有直径的一个端点
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int rev[N],stk[N],aset[N],pts[N][];
int fth[N],son[N][],len[N];
int n,m,t1,t2,t3,top,typ,ans;
void Read(int &x)
{
x=; char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
}
int Finda(int x)
{
return x==aset[x]?x:aset[x]=Finda(aset[x]);
}
void Pushup(int nde)
{
len[nde]=len[son[nde][]]+len[son[nde][]]+;
}
void Release(int nde)
{
if(rev[nde])
{
int &lson=son[nde][],&rson=son[nde][];
rev[lson]^=,rev[rson]^=,rev[nde]^=;
swap(lson,rson);
}
}
bool Nottop(int nde)
{
int fa=fth[nde];
return son[fa][]==nde||son[fa][]==nde;
}
void Rotate(int nde)
{
int fa=fth[nde],gr=fth[fa],isl=nde==son[fa][];
if(Nottop(fa)) son[gr][fa==son[gr][]]=nde;
fth[nde]=gr,fth[fa]=nde,fth[son[nde][isl]]=fa;
son[fa][isl^]=son[nde][isl],son[nde][isl]=fa;
Pushup(fa),Pushup(nde);
}
void Splay(int nde)
{
stk[top=]=nde;
for(int i=nde;Nottop(i);i=fth[i])
stk[++top]=fth[i];
while(top) Release(stk[top--]);
while(Nottop(nde))
{
int fa=fth[nde],gr=fth[fa];
if(Nottop(fa))
Rotate(((son[fa][]==nde)==(son[gr][]==fa))?fa:nde);
Rotate(nde);
}
Pushup(nde);
}
void Access(int nde)
{
int lst=,mem=nde;
while(nde)
{
Splay(nde),son[nde][]=lst;
Pushup(nde),lst=nde,nde=fth[nde];
}
Splay(mem);
}
void Turnroot(int nde)
{
Access(nde),rev[nde]^=;
}
int Getroot(int nde)
{
Access(nde);
while(son[nde][])
nde=son[nde][];
Splay(nde);
return nde;
}
void Split(int x,int y)
{
Turnroot(x),Access(y);
}
int Query(int x,int y)
{
Split(x,y);
return len[y];
}
void Link(int x,int y)
{
Split(x,y);
if(Getroot(y)!=x) fth[x]=y;
}
pair<int,int> Longest(int x)
{
int f=Finda(x),l1=Query(x,pts[f][]),l2=Query(x,pts[f][]);
// printf("%d belong to %d,two points are %d and %d\n",x,f,pts[f][0],pts[f][1]);
if(l1>l2) return make_pair(l1-,pts[f][]);
else return make_pair(l2-,pts[f][]);
}
void Road(int x,int y)
{
int fx=Finda(x),fy=Finda(y);
int ori=Query(pts[fy][],pts[fy][])-;
int add=Query(pts[fx][],pts[fx][])-;//printf("two parts's di are %d and %d\n",ori,add);
pair<int,int> p1=Longest(x),p2=Longest(y); //printf("Di of %d is %d\n",x,p1);printf("Di of %d is %d\n",y,p2);
if(p1.first+p2.first+>ori)
pts[fy][]=p1.second,pts[fy][]=p2.second,ori=p1.first+p2.first+;
//if(fy==3) printf("%d===%d\n",p1.second,p2.second);
Link(x,y),aset[fx]=fy;
if(add>ori)
{
pts[fy][]=pts[fx][];
pts[fy][]=pts[fx][],ori=add;
}
// printf("Link %d with %d,noww they belong to %d,two points are %d and %d\n",x,y,fy,pts[fy][0],pts[fy][1]);
}
int main()
{//freopen("hike2.in","r",stdin);
//freopen("myans.txt","w",stdout);
Read(typ),Read(n),Read(m);
for(int i=;i<=n;i++)
len[i]=,aset[i]=pts[i][]=pts[i][]=i;
while(m--)
{
Read(t1);
if(t1==)
{
Read(t2),Read(t3);
if(typ) t2^=ans,t3^=ans; Road(t2,t3);
}
else
{
Read(t2); if(typ) t2^=ans;
printf("%d\n",ans=Longest(t2).first);
}
}
return ;
}
T2 珠宝
决策单调性优化DP，是没写过的东西呢
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=,M=;
ll tr1[N],tr2[N],tmp[N],tep[N],sum[N];
int n,m,t1,t2,sz,mx; vector<int> ve[M];
bool cmp(ll a,ll b)
{
return a>b;
}
void Solve(ll *lst,ll *cur,int l,int r,int nl,int nr)
{
if(l>r) return;
if(nl==nr)
for(int i=l;i<=r;i++)
cur[i]=lst[nl]+sum[i-nl];
else
{
if(l==r)
{
cur[l]=; int lp=max(nl,l-sz),rp=min(nr,l);
for(int i=lp;i<=rp;i++)
cur[l]=max(cur[l],lst[i]+sum[l-i]);
}
else
{
int mid=(l+r)/; cur[mid]=;
int pt=-,lp=max(nl,mid-sz),rp=min(nr,mid);
for(int i=lp;i<=rp;i++)
{
ll val=lst[i]+sum[mid-i];
if(val>=cur[mid])
cur[mid]=val,pt=i;
}
Solve(lst,cur,l,mid-,nl,pt);
Solve(lst,cur,mid+,r,pt,nr);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d%d",&t1,&t2);
ve[t1].push_back(t2),mx=max(mx,t1);
}
mx=min(mx,m); ll *dp=tr1,*pd=tr2;
for(int i=;i<=mx;i++)
if(!ve[i].empty())
{
sz=ve[i].size();
sort(ve[i].begin(),ve[i].end(),cmp);
for(int j=;j<=sz;j++)
sum[j]=sum[j-]+ve[i][j-];
for(int j=,p;j<i;j++)
{
p=; for(int k=j;k<=m;k+=i) tmp[++p]=dp[k];
Solve(tmp,tep,,p,,p);
p=; for(int k=j;k<=m;k+=i) pd[k]=tep[++p];
}
for(int j=;j<i;j++) pd[j]=dp[j]; swap(dp,pd);
}
for(int i=;i<=m;i++)
dp[i]=max(dp[i-],dp[i]),printf("%lld ",dp[i]);
return ;
}
T3 矩阵
线性代数那一套.jpg
ywy讲的太神仙了，没听懂。。。
tbl讲的好多了，但是不想写了