摘要:$P \neq NP$

10132020机房赛

T1

题目分析

把图划分为两部分,一部分是团,一部分是独立集,求方案数.

于是很好分析出来要求图中的最大团,因为最大团中的点不可能出现在独立集中.

可这问题不是个典型的NP吗…

于是正解是暴力划分…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=1010;
lxl T,n,m,InCnt,OutCnt,ans;
lxl edge[big][big],in[big],out[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
void dfs(lxl x)
{
if(x==n+1){ans+=InCnt&&OutCnt;return;}
for(R int i(1);i<=OutCnt;++i)if(edge[out[i]][x])goto nout;
{
out[++OutCnt]=x;
dfs(x+1);
--OutCnt;
}
nout:;
for(R int i(1);i<=InCnt;++i)if(!edge[in[i]][x])goto nin;
{
in[++InCnt]=x;
dfs(x+1);
--InCnt;
}
nin:;
return;
}
int main(void)
{
T=read();
while(T--)
{
ans=0;
memset(edge,false,sizeof edge);
n=read(),m=read();
for(R int i(1);i<=m;++i)
{
lxl u=read(),v=read();
edge[u][v]=edge[v][u]=true;
}
dfs(1);
printf("%lld\n",ans);
}
return 0;
}

T2

题目分析

顺序枚举前缀的变化,发现每变化一个位置上的值,会对它前面位置的后缀和产生影响.

同时后缀的变化是要变到可能的最小值,而$B$为正,所以一定是找到最大的后缀和,然后变化这一段,因为可以不变,在结尾添加一个$0$.

然后线段树维护后缀和,每次区间修改,区间求最值即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=1000010;
lxl n,NodeCnt,root,ans,sum,am,bm;
lxl c[2][big<<2],max[big<<2],a[big],suf[big],tag[big<<2];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void PushDown(lxl t)
{
if(!tag[t])return;
max[c[0][t]]+=tag[t],max[c[1][t]]+=tag[t];
tag[c[0][t]]+=tag[t],tag[c[1][t]]+=tag[t];
tag[t]=0;
}
inline void PushUp(lxl t)
{
if(max[c[0][t]]>max[c[1][t]])max[t]=max[c[0][t]];
else max[t]=max[c[1][t]];
}
void build(lxl &t,lxl l,lxl r)
{
t=++NodeCnt;
if(l==r){max[t]=suf[l];return;}
lxl mid((l+r)>>1);
build(c[0][t],l,mid),build(c[1][t],mid+1,r);
PushUp(t);
}
void modify(lxl t,lxl l,lxl r,lxl x,lxl y,lxl k)
{
if(x<=l&&y>=r){tag[t]+=k,max[t]+=k;return;}
PushDown(t);
lxl mid((l+r)>>1);
if(x<=mid)modify(c[0][t],l,mid,x,y,k);
if(y>mid)modify(c[1][t],mid+1,r,x,y,k);
PushUp(t);
}
lxl query(lxl t,lxl l,lxl r,lxl x,lxl y)
{
if(x<=l&&y>=r)return max[t];
PushDown(t);
lxl mid((l+r)>>1),ma(-INF);
if(x<=mid)ma=std::max(ma,query(c[0][t],l,mid,x,y));
if(y>mid)ma=std::max(ma,query(c[1][t],mid+1,r,x,y));
return ma;
}
int main(void)
{
n=read(),am=read(),bm=read();
for(R int i(1);i<=n;++i)a[i]=read(),sum+=a[i];
a[++n]=0;
for(R int i(n);i;--i)suf[i]=suf[i+1]+a[i];
build(root,1,n);
lxl origin=query(root,1,n,1,n);
ans=sum-origin+(origin*-bm);
for(R int i(1);i<n;++i)
{
sum=sum-a[i]+(a[i]*-am);
modify(root,1,n,1,i,(a[i]*-am)-a[i]);
origin=query(root,1,n,1,n);
ans=std::max(ans,sum-origin+(origin*-bm));
}
printf("%lld\n",ans);
return 0;
}

T3

题目分析

考虑把题目中的贡献转化为边权,做最小生成树.

只要保证联通即可,所以最优解一定是一颗树.

贡献1是很好处理的,可以直接赋,贡献2要考虑一个顺序的问题.

对于边$(x,y)$,它们一定会产生$( u_x - t_x ) \times t_y \times f_x + ( u_y - t_y ) \times t_x \times f_y$的贡献,如果是$x$后加人,贡献会增加$( u_x - t_x ) \times ( u_y - t_y ) \times f_x$的贡献,$y$后加人同理.

然后是每个点加人会有之前已经有的人产生的贡献,这个可以处理完生成树之后直接算.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl small=51,big=3010;
lxl n,ans,ECnt,c;
lxl fa[small],t[small],u[small],f[small];
struct _Edge
{
lxl u,v,w;
inline bool operator <(const _Edge &another)const{return w<another.w;}
}e[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
lxl find(lxl x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline lxl calc(lxl x,lxl y)
{
lxl XFirst,YFirst,num1,num2;
YFirst=(u[x]-t[x])*(u[y]-t[y])*f[x];
XFirst=(u[x]-t[x])*(u[y]-t[y])*f[y];
num1=(u[x]-t[x])*t[y]*f[x];
num2=(u[y]-t[y])*t[x]*f[y];
return std::min(YFirst,XFirst)+num1+num2;
}
inline void kruskal()
{
lxl x,y;
std::sort(e+1,e+1+ECnt);
for(R int i(1);i<=ECnt;++i){x=find(e[i].u),y=find(e[i].v);if(x!=y)fa[x]=y,ans+=e[i].w;}
for(R int i(1);i<=n;++i)ans+=(u[i]-t[i])*(t[i]+u[i]-1)*f[i]/2;
}
int main(void)
{
n=read();
for(R int i(1);i<=n;++i)fa[i]=i,t[i]=read();
for(R int i(1);i<=n;++i)u[i]=read();
for(R int i(1);i<=n;++i)f[i]=read();
for(R int i(1);i<=n;++i)
{
char str[small];
scanf("%s",str+1);
for(R int j(i+1);j<=n;++j)
if(str[j]=='Y')
{
ans+=calc(i,j);
lxl x=find(i),y=find(j);
if(x!=y)fa[x]=y;
}
else e[++ECnt]=(_Edge){i,j,calc(i,j)};
}
c=read();
for(R int i(1);i<=ECnt;++i)e[i].w+=(t[e[i].u]+t[e[i].v])*c;
kruskal();
printf("%lld\n",ans);
return 0;
}

总结

这次的确是先开T1了,不过求最大团是个典型的np问题不知道怎么做,于是想了个又假又难写的缩点后大力分类讨论模拟,写了200多行,浪费了一个多小时时间来调试,最后写了个二分最大团大小然后搜索剪枝的暴力,正解其实就是搜索但是写得不是很好只拿了20.

问题就在于经常想出假做法还不能快速地hack掉自己,浪费掉一次写代码和调试的时间,应该在写之前就造一些数据来手推,而不是写完了再出数据hack,有时候hack掉的不是代码中的小错误而是整个解法.

开考2个小时的时候写的T2,很快发现在后缀情况下存在区间加和区间最值的模型,打了个线段树,稍微调试了一下就过了大样例.

不过只拿了90分,原因是处理不选择前缀时,我是在循环前进行了一次询问,后来在调试时发现得到询问值之后更新答案的方式有问题,就只在循环里改了,循环前的一次询问忘了改,修改代码的时候还是得注意点.

做T3时时间剩一个小时左右,觉得可以先做一棵最小生成树然后搜索出操作序列,最优性的问题剪枝也非常好剪,或者直接模拟退火出操作序列,考虑$n$很小效率上应该差距不大.

但是其实先做最小生成树是假的因为前面的连边对后来的操作序列有影响,不过数据水得可以这都没卡,场上有模拟退火出操作序列拿70的.

最后几分钟发现在剪枝的时候有一句代码写错了,用编辑器回溯代码时不小心回溯过头了没发现过来,回溯到了另外一个打错的版本,于是爆零了,在优化代码时记得把之前的存一份.

比赛总结