暴死力

T1

开场确实秒做法了,就是团+独立集

然后发现求团是个NP问题,卡了两个小时

然后发现可以转化成正则图,和暴力拍上感觉不错

然后我tm手贱我删暴力的清空了,这个也没交上去

不过正解真是大力求独立集,菊花图都能卡炸吧

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=1010;

int n,m,a[maxn],b[maxn],ca,cb,looker;
int ans=0;
int deg[maxn];
int e[maxn][maxn];

inline int check()
{
int i,j;
if(!ca||!cb) return 0;
for(i=1;i<=ca;i++)
for(j=i+1;j<=ca;j++)
{
if(!e[a[i]][a[j]]) return 0;
}
for(i=1;i<=cb;i++)
for(j=i+1;j<=cb;j++)
{
if(e[b[i]][b[j]]) return 0;
}
return 1;
}

int ck1(int x)
{
int i;
for(i=1;i<=ca;i++) if(!e[a[i]][x]) return 0;
return 1;
}

int ck2(int x)
{
int i;
for(i=1;i<=cb;i++) if(e[b[i]][x]) return 0;
return 1;
}

int css=0;

void dfs(int dep)
{
//if(css==10000) return ;
//css++;
if(dep==n+1)
{
if(!ca||!cb) return ;
ans++;
//cout<<ans<<endl;
return ;
}
if(ck2(dep))
{
b[++cb]=dep;
dfs(dep+1);
cb--;
}
if(ck1(dep))
{
a[++ca]=dep;
dfs(dep+1);
ca--;
}
}

int main()
{
//freopen("party.in","r",stdin);
ios::sync_with_stdio(false);
register int i,j;
int t;
cin>>t;
while(t--)
{
css=0;
ans=0;
memset(e,0,sizeof(e));
memset(deg,0,sizeof(deg));
cin>>n>>m;
looker=sqrt(m);
int t1,t2;
for(i=1;i<=m;i++)
{
cin>>t1>>t2;
e[t1][t2]=e[t2][t1]=1;
deg[t1]++;
deg[t2]++;
}
dfs(1);
cout<<ans<<endl;
}
return 0;
}

T2

没多少时间莽了个T2的暴力,觉得效果还不错

然后最后几分钟xjb优化,以为可以套一个四边形不等式,结果发现不行,但是改的时候j改成了1,但是过了大样例,结果炸了

不过我那个优化貌似和题解差不多?

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=1000100;

int mmx[maxn],mmn[maxn],ans=-0x3f3f3f3f3f3f3f3f;
int n,m,a[maxn];
int s[maxn];
int f[maxn],A,B;
//
//inline int getmmx(int x)
//{
// int j=0;
// int mmx=n;
// for(j=n;j>=x;j--)
// if(_sufsum[j]>_sufsum[mmx]) mmx=j;
// return mmx;
//}

signed main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n>>A>>B;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
s[i]=s[i-1]+a[i];
mmn[n]=s[n];
for(i=n-1;i>=0;i--)
mmn[i]=min(mmn[i+1],s[i]);
for(i=1;i<=n;i++)
mmx[i]=max(mmx[i-1],s[i]);
for(i=0;i<=n;i++)
{
int s1,s2;
mmx[i]=0;
if(i-1<=0) mmx[i]=0;
else mmx[i]=max(mmx[i-1],s[i-1]);
s1=(1+B)*mmn[i]-(1+A)*s[i]-B*s[n];
s2=(B*(A+1))*s[i]-(A*(B+1)*mmx[i])-B*s[n];
ans=max(min(s1,s2),ans);
}
cout<<ans<<endl;
// int mmn=1,mmx=getmmx(1);
// ans=_presum[n]>0?-_presum[n]:_presum[n];
// int delta=0;
// for(i=1;i<=n;i++)
// {
// _presum[i]=max(_presum[i-1],)
// }
// for(i=1;i<=n;i++)
// {
// //f[i]=_presum[i]*(-A);
// if(_presum[i]<_presum[mmn]) mmn=i;
// if(mmx<=i) mmx=getmmx(i+1);
// int t1=_presum[mmn-1]*(-A)+(_sufsum[i+1]*(-B)+(_presum[i]-_presum[mmn-1])*A*B);
// t1=min(t1,_presum[n]+_presum[mmn]*(-A)-_sufsum[mmx]*(-B));
// ans=max(ans,t1);
// }
return 0;
}

T3

怪毙了怎么又考图论

看到题:好不会,打暴力

然后突然想到了一个绝妙的做法,然后交了暴力

然后炸了

后来看好像是加边出了问题,基本达到了90%的题解做法(剩下些细节调了一下午)?

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=120;

int n,m,tot,f[maxn],sz[maxn];
int T[maxn],U[maxn],F[maxn],C,ans;
int vis[maxn];
int d[maxn][maxn];

struct edge{
int x,y,w;
bool operator <(const edge &tmp)
const {
return w<tmp.w;
}
}e[maxn*maxn];

int sum1(int x)
{
return (x*(x+1))/2;
}

int sum2(int x,int y)
{
return sum1(y)-sum1(x-1);
}

int getfather(int x)
{
if(f[x]==x) return x;
return f[x]=getfather(f[x]);
}

int getomega(int x,int y)
{
if(F[x]<F[y]) swap(x,y);
return F[x]*(U[x]-T[x])*T[y]+F[y]*(U[y]-T[y])*U[x];
}

int p=0;

inline void getans()
{
int i,j;
sort(e+1,e+tot+1);
for(i=1;i<=tot;i++)
{
int x,y;
x=getfather(e[i].x);
y=getfather(e[i].y);
if(x!=y)
{
d[e[i].x][e[i].y]=1;
d[e[i].y][e[i].x]=1;
ans+=e[i].w;
f[x]=y;
p++;
}
if(p==n-1) break;
}
cout<<ans<<endl;
return ;
}

signed main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n;
for(i=1;i<=n;i++) cin>>T[i];
for(i=1;i<=n;i++) cin>>U[i];
for(i=1;i<=n;i++) cin>>F[i];
for(i=1;i<=n;i++)
ans+=(T[i]+U[i]-1)*(U[i]-T[i])/2*F[i];
char tmp;
for(i=1;i<=n;i++) f[i]=i;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cin>>tmp;
if(i<j) continue;
if(tmp=='Y')
{
//e[++tot].x=i;
//e[tot].y=j;
d[i][j]=1;
d[j][i]=1;
int tx=getfather(i);
int ty=getfather(j);
f[tx]=ty;
ans+=getomega(i,j);
//e[tot].w=0;
if(tx==ty) continue;
p++;
}
else
{
e[++tot].x=i;
e[tot].y=j;
e[tot].w=T[i]+T[j];
}
}
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)
// cout<<getomega(i,j)<<endl;
cin>>C;
for(i=1;i<=tot;i++) e[i].w=e[i].w*C+getomega(e[i].x,e[i].y);
getans();
return 0;
}