6.14 YZBOI模拟赛solution
\(6.14\ YZBOI\)模拟赛\(solution\)
本来不想写题解来着。。。毕竟是自己找的题还是写一写吧
上午为了整活，就把赛制改成\(IOI\)赛制了，于是乎拯救了大家的\(70pts\)代码。
三道巨水的题。。。\(bz\)迅速就\(AK\)了。。。
\(T1\ Delta\)
比较直观的想，肯定是找一个少的的完全图划分了，又发现平方具有传递性，就变成维护联通块了
#include
#define int long long
#define MAXN 5005
using namespace std;
int n,a[MAXN],fa[MAXN],ans[MAXN];
bool vis[MAXN];
int Find(int x)
{
if(fa[x]==x) return x;
return fa[x]=Find(fa[x]);
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
fa[i]=i;
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(a[i]*a[j]>0)
{
if((int)sqrt(a[i]*a[j])*(int)sqrt(a[i]*a[j])!=a[i]*a[j]) continue;
int fi=Find(i);
int fj=Find(j);
if(fi==fj) continue;
fa[fi]=fj;
}
}
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
int num=0;
for(int j=i;j<=n;j++)
{
if(a[j]!=0&&vis[Find(j)]==false)
{
vis[Find(j)]=true;
num++;
}
if(num==0) ans[num+1]++;
else ans[num]++;
}
}
for(int i=1;i<=n;i++)
{
cout< \(T2 Add\)
线性规划会吧，模拟会吧，单纯形法会吧，转对偶会吧，那么这就是一道水题了
#include
using namespace std;
#define MAXN 100005
const double eps=1e-9;
const int INF=1000000000;
double a[1005][MAXN],b[MAXN],v,c[MAXN];
int m,n;
void solve(int l,int e)
{
b[l]/=a[l][e];
for(int i=1;i<=n;++i) if(i!=e) a[l][i]/=a[l][e];
a[l][e]=1/a[l][e];
for(int i=1;i<=m;++i)
{
if(i!=l&&abs(a[i][e])>eps)
{
b[i]-=b[l]*a[i][e];
for(int j=1;j<=n;++j)
{
if(j!=e) a[i][j]-=a[l][j]*a[i][e];
}
a[i][e]=-a[i][e]*a[l][e];
}
}
v+=c[e]*b[l];
for(int i=1;i<=n;++i)
{
if(i!=e) c[i]-=c[e]*a[l][i];
}
c[e]=-c[e]*a[l][e];
}
void simplex()
{
int l,e;
while(true)
{
for(e=1;e<=n;++e)
{
if(c[e]>eps) break;
}
if(e>n) break;
double t=INF;
for(int i=1;i<=m;++i)
{
if(a[i][e]>eps&&b[i]/a[i][e]>m>>n;
for(int i=1;i<=m;++i) scanf("%lf",&b[i]);
for(int i=1,l,r;i<=n;++i)
{
scanf("%d%d",&l,&r);
for(int j=l;j<=r;++j) ++a[j][i];
scanf("%lf",&c[i]);
}
simplex();
printf("%.0lf\n",v);
return 0;
}
\(T3\ Times\)
我记得这道题是我省选前一天为了帮忙\(debug\)写的
考虑最优解必然是在最小生成树上的，然后考虑从大往小删除边，我们需要保证删边之后每个联通块至少有一个守卫，那么大概就是我们对每个守卫匹配一个边去割掉，而且不存在交叉，那么就可以很直观的用费用流来表示
#include
#define MIN 0xcfcfcfcfcfcfcfcf
#define INF 2147483647
#define int long long
#define MAXN 1000005
using namespace std;
struct node
{
int u,v,w;
}lu[MAXN];
int head[MAXN],cost[MAXN],val[MAXN],nxt[MAXN],to[MAXN],tot=1;
int dis[MAXN],fa[MAXN],Sum,s,t,n,m,k;
bool vis[MAXN],in[MAXN];
vector >rd[MAXN];
int Find(int x)
{
if(fa[x]==x) return x;
return fa[x]=Find(fa[x]);
}
int R(int x)
{
return x+n+n;
}
int ru(int x)
{
return x;
}
int chu(int x)
{
return x+n;
}
void add(int u,int v,int w,int cts)
{
tot++; to[tot]=v; val[tot]=w; cost[tot]=cts; nxt[tot]=head[u]; head[u]=tot;
swap(u,v),w=0,cts*=-1;
tot++; to[tot]=v; val[tot]=w; cost[tot]=cts; nxt[tot]=head[u]; head[u]=tot;
}
bool bfs(int s,int t)
{
memset(dis,0xcf,sizeof(dis));
queueq;
dis[s]=0;
in[s]=true;
q.push(s);
while(q.size())
{
int now=q.front();
q.pop();
in[now]=false;
for(int i=head[now];i;i=nxt[i])
{
int y=to[i];
if(val[i]&&dis[y]=INF)
{
cout<<-1;
return 0;
}
cout<