计蒜客信息学4月提高组模拟赛

计蒜客信息学4月提高组模拟赛

A 男左女右

分类讨论,考思维清晰、细节明确

核心思想就是分n的奇偶性和当前先手奇偶性仔细讨论

1
2
3
4
5
6
7
8
9
10
11
12
int T=qread();
while(T--)
{
scanf("%s",str+1);int ln=strlen(str+1),op=qread();
if(ln==1 and str[1]-'0'==2)
{
printf("%d\n",op);
continue;
}
if((str[ln]-'0')%2==0 and op==0) printf("%d\n",op^1);
else printf("%d\n",op);
}

B 漫天飞刺

考虑如何把 $O(n^3logINF^2)$ 的log去掉,很自然地想到先把当前最大子矩阵求出来

然后修改那个位置就枚举,通过预处理(稍微改一改最大子矩阵的求法)求出这种方案的 $max( 不包括此点的mx,包括此点的mx-old+new) )$

时间复杂度为 $O(n^3)$

C 旋转茶杯 bzoj3579破冰派对

题意:给出一个无向图,求子图满足【选的点是团,没选的点是独立集】;问最大权值的子图或问合法子图方案数

这种乱搞题的核心:要么搞出一种复杂度正确的方法,要么证明没有这种情况

如果我们能求出任意一个方案,那么其他的方案一定是:

  1. 从团中删除一个点
  2. 向团中加入一个点
  3. 从团中删除一个点再加入一个点

考虑如何求出一个合法解,直接建 $n^2$ 的边去2-sat似乎没有优化空间

将所有点按照度数从大到小排序,按顺序加入点,如果某次发现x无法加入到团中,那么就停下

此时如果和后面有边相连,那就没有合法解(假设x往前连a个往后b个,这b个点都要加入团中内部一定也是团,则 $b\leq 后面 \leq a+b$即往前的度数<=a,同样gg)无论如何都可以退出了,因为既然现在有合法解,那么b=0,全部往前都不够后面的自然也不够了

然后关于这个合法方案还有一个遗留问题,就可能独立集里面有非法边,然后为此前面某个团中的点x自愿退出来让后面的t加入;这种情况实际上是不存在的,还是分析一下度数,原本团a,x的连边为a+b,则团新大小为a+b,而后面这个能加入的点至少为 $a+b+1$

得到合法方案后(一定是一段in+一段out),按照上面说的考虑调整,核心就是尽量让复杂度和m相关

第二种情况在本做法中显然是没有的,第一种直接枚举,第二种想不到可看代码,很好懂

复杂度下界为 $O(n+m)$

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
//#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(int &x,const ll y) {x=(x>y?x:y);}
void chmin(int &x,const ll y) {x=(x<y?x:y);}
const ll MOD=998244353;
void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll inv(ll x){return qpower(x,MOD-2);}
const int MAX_N=1e5+10;
int cas,n;
int a[MAX_N],deg[MAX_N];vc<int> to[MAX_N];
int q[MAX_N];bool cmp(int x,int y){return deg[x]>deg[y];}
bool in[MAX_N];
bool getone()
{
int pp=0;
for(int i=1;i<=n;i++)
{
int cnt=0,x=q[i];
for(int t=0;t<(int)to[x].size();t++) cnt+=in[to[x][t]];
if(cnt==pp) in[x]=1,pp++;
else if(deg[x]-cnt>0) return 0;
}
for(int x=1;x<=n;x++) if(!in[x])
for(int t=0;t<(int)to[x].size();t++) if(!in[to[x][t]]) return 0;
return 1;
}
vc<int> A;
bool on[MAX_N*5];int pos[MAX_N],king[MAX_N];
void solve()
{
int sum=0;for(int i=1;i<=n;i++) if(in[i]) A.PB(i),pos[i]=A.size()-1,sum+=a[i];
int m=A.size();
int ans=(m>0 and m<n);cas=1;//bzoj
// int ans=cas&1?1:sum;
for(int x=1;x<=n;x++) if(in[x])
{
//从团中删除一个点
bool ok=1;
for(int tt=0;tt<(int)to[x].size();tt++)
{
int y=to[x][tt];
if(!in[y]) {ok=0;break;}
}
if(ok)
{
if(cas&1)
{
if(m>1)//bzoj
ans++;
}
else chmax(ans,sum-a[x]);
}
}
//从团中删除一个点再加入一个点
for(int t=0;t<m;t++)
{
int x=A[t],yy,cnt=0;
for(int i=0;i<(int)to[x].size();i++)
{
int y=to[x][i];if(in[y]) continue;
cnt++;yy=y;
}
if(cnt==0) king[x]=-666; else king[x]=yy;
}
for(int y=1;y<=n;y++) if(!in[y])
{
int cnt=0;for(int t=0;t<(int)to[y].size();t++) cnt+=in[to[y][t]];
if(cnt==m-1)
{
for(int i=0;i<m;i++) on[i]=0;
for(int t=0;t<(int)to[y].size();t++) on[pos[to[y][t]]]=1;
for(int i=0;i<m;i++) if(!on[i])
{
int x=A[i];if(king[x]!=y and king[x]!=-666) continue;
if(cas&1)
{
if(m>0 and m<n)//bzoj
ans++;
}
else chmax(ans,sum-a[x]+a[y]);
}
}
}
write2(ans);
}
int ct[MAX_N];
void main()
{
int T=qread();
while(T--)
{
cas=1;n=qread();int m=qread();
memset(in,0,sizeof in);
memset(king,0,sizeof king);
memset(deg,0,sizeof deg);A.clear();
for(int i=1;i<=n;i++) to[i].clear();
while(m--)
{
int x=qread(),y=qread();
deg[x]++;deg[y]++;
to[x].PB(y);to[y].PB(x);
}
// cas=qread(),n=qread();
// for(int i=1;i<=n;i++) a[i]=qread();
// for(int x=1;x<=n;x++)
// {
// int cnt=qread();deg[x]+=cnt;
// while(cnt--)
// {
// int y=qread();deg[y]++;
// to[x].PB(y);to[y].PB(x);
// }
// }
memset(ct,0,sizeof ct);
for(int i=1;i<=n;i++) ct[deg[i]]++;
for(int i=1;i<MAX_N;i++) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--) q[n-(ct[deg[i]]--)+1]=i;
if(getone()) solve();
else write2(0);
}
}
};
signed main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/21f3.html
转载请注明出处,谢谢!