T1.合并集合
沙雕题，不会建议重修区间DP
T2.ZYB建围墙
较有趣的沙雕题
容易发现聚落一定聚在一起，外墙一定是六边形
考虑没新加一条边对答案的影响
以当前囊括的最大正六边形不断向外扩展
通过小学的平移知识（建议用WPS画图）可知每加一条边，新增的房子为：(r,r+1,r+1,r+1,r+1,r+2)
所以直接找到当前囊括的最大正六边形，扩展即可
找最大正六边形要枚举 (i) ，时间复杂度 ： (O(sqrt n))
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e3+5,INF=0x3f3f3f3f,base=131;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,a[22]={0,6,8,9,10,11,12,12,13,14,14,15,15,16,16,17,17,18,18,18,19};
int main(){
freopen("wall.in","r",stdin);
freopen("wall.out","w",stdout);
n=read();
int now=0;
if(n<=20)return cout<<a[n],0;
for(int i=0;6LL*(i+1)*i/2+1<=n;i++){
if(6LL*(i+1)*i/2+1==n)return cout<<6LL*(i+1),0;
now=i;
}
int ans=6LL*(now+1);
int p=1,maxs=6*(now+2),sum=6*(now+1)*now/2+1;
for(;ans+p<=maxs;p++){
if(p==1)sum+=now;
else if(ans+p<maxs)sum+=now+1;
else sum+=now+2;
if(sum>=n)break;
}
cout<<ans+p;
return 0;
}
T3.ZYB和售货机
考时发现怎么调基环树都调不出来，考后发现一定是内向基环树，然后还没发现暴力打挂，连树的 (10pts) ，暴搜的 (30pts) 都丢了
对于树的情况，可以从上往下按，每个点都可以按掉，所以直接找节点每个儿子的最大值
对于基环树的情况，抛去写的十分复杂的官方题解，发现环上的所有边一定有一条不会走满
对于每个环上的点，不管有没有树边，一定可以是直接删的代价，有树边就是最大环上临接边-最大树临接边，最后所有中取 (min) 即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define int long long
using namespace std;
const int maxn=2e5+5,INF=0x3f3f3f3f3f3f3f3f;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,a[maxn],f[maxn],exist[maxn],tot,head[maxn],col[maxn],vis[maxn],cir[maxn],son[maxn],sta[maxn],top;
struct Edge{
int next,to;
ll dis;
}e[maxn];
bool flag;
ll ans,c[maxn],d[maxn],g[maxn];
void Add(int x,int y,ll z){e[++tot]=(Edge){head[x],y,z};head[x]=tot;}
void DFS1(int u,int fa){
vis[u]=1;
bool last=flag;
for(int x=head[u];x;x=e[x].next){
int v=e[x].to;
if(vis[v]){flag=1;son[u]=v;continue;}
DFS1(v,u);
if(exist[v])son[u]=v;
else cir[u]=min(cir[u],c[v]);
}
if(!last&&flag)exist[u]=1;
if(!exist[u]){
if(cir[u]!=INF&&d[u]-cir[u]>0)ans+=(d[u]-cir[u])*a[u];
}else sta[++top]=u;
}
signed main(){
freopen("goods.in","r",stdin);
freopen("goods.out","w",stdout);
n=read();memset(cir,0x3f,sizeof(cir));
for(int i=1;i<=n;i++){
f[i]=read(),c[i]=read(),d[i]=read(),a[i]=read();
if(f[i]==i)cir[i]=c[i];
else Add(f[i],i,c[i]);
}
for(int i=1;i<=n;i++){
if(!vis[i]){
int rt=i;
bool nowflag=0;
while(f[rt]!=rt){
col[rt]=1;
rt=f[rt];
if(col[rt]){nowflag=1;break;}
}
flag=0;
DFS1(rt,0);
if(nowflag){
ll sum1=0,sum2=0;
int last=top,minn=INF,maxx=0;
while(top){
int u=sta[top--];
if(d[u]-min(cir[u],c[son[u]])>0)sum1+=(d[u]-min(cir[u],c[son[u]]))*a[u];
if(cir[u]!=INF)minn=min(cir[u]-c[son[u]],minn);
minn=min(d[u]-c[son[u]],minn);
}
if(minn==INF)minn=0;
if(max(sum1,sum2)-max(minn,0LL)>0)ans+=max(sum1,sum2)-max(minn,0LL);
}
}
}
cout<<ans;
return 0;
}
T4： ZYB玩字符串
(50pts)乱搞，选取中间的串删一分没多，但考场：
变量名不规范，爆零两行泪
还没写，RUA～