A.[USACO2.3] 零的数列 Zero Sum
link
正解
这道题就是DFS为主，搜索每个数中间符号的情况。
在check中计算表达式的值，若为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
|
#include<bits/stdc++.h>
using namespace std;
int n;
bool check(string s)
{
char p='+';
int sum=0,tmp=0;
for(int i=0;i<s.size();i++)
{
if(s[i]==' ')continue;
else if(s[i]>='0'&&s[i]<='9')tmp=tmp*10+s[i]-'0';
else if(s[i]=='+')
{
if(p=='+')sum+=tmp;
else sum-=tmp;
tmp=0;
p='+';
}
else
{
if(p=='+')sum+=tmp;
else sum-=tmp;
tmp=0;
p='-';
}
}
if(p=='+')sum+=tmp;
else sum-=tmp;
return (sum==0);
}
void dfs(int k,string s)
{
if(k==n)
{
if(check(s))puts(s.c_str());
return ;
}
int sp=2*k-1;
dfs(k+1,s);
s[sp]='+';
dfs(k+1,s);
s[sp]='-';
dfs(k+1,s);
}
int main()
{
cin>>n;
string s="";
for(int i=1;i<=n;i++)
{
s+=to_string(i);
if(i!=n)s+=' ';
}
dfs(1,s);
return 0;
}
|
乱解
以上这些只是正解的手法。
根据我们敏锐的视觉，我们可以发现$3 \leq n \leq 9$（🤯）
根据
打表出省一
的理念，我们可以进行打表啊！
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
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
switch(n)
{
case 3:cout<<"1+2-3";break;
case 4:cout<<"1-2-3+4";break;
case 5:cout<<"1 2-3-4-5";break;
case 6:cout<<"1 2+3-4-5-6";break;
case 7:
cout<<"1+2-3+4-5-6+7\n";
cout<<"1+2-3-4+5+6-7\n";
cout<<"1-2 3+4+5+6+7\n";
cout<<"1-2 3-4 5+6 7\n";
cout<<"1-2+3+4-5+6-7\n";
cout<<"1-2-3-4-5+6+7\n";
break;
case 8:
{
cout<<"1 2-3 4-5 6+7 8\n";
cout<<"1+2 3-4 5+6+7+8\n";
cout<<"1+2+3+4-5-6-7+8\n";
cout<<"1+2+3-4+5-6+7-8\n";
cout<<"1+2-3+4+5+6-7-8\n";
cout<<"1+2-3-4-5-6+7+8\n";
cout<<"1-2 3-4+5+6+7+8\n";
cout<<"1-2+3-4-5+6-7+8\n";
cout<<"1-2-3+4+5-6-7+8\n";
cout<<"1-2-3+4-5+6+7-8\n";
break;
}
case 9:
cout<<"1 2+3 4-5 6-7+8+9\n";
cout<<"1 2+3+4-5-6-7+8-9\n";
cout<<"1 2+3-4 5+6+7+8+9\n";
cout<<"1 2+3-4+5-6+7-8-9\n";
cout<<"1 2-3+4+5 6-7 8+9\n";
cout<<"1 2-3+4+5+6-7-8-9\n";
cout<<"1 2-3-4-5+6-7-8+9\n";
cout<<"1 2-3-4-5-6+7+8-9\n";
cout<<"1+2-3 4-5 6+7 8+9\n";
cout<<"1-2 3-4-5 6-7+8 9\n";
cout<<"1-2-3 4+5+6+7+8+9\n";
break;
}
}
|
（模拟赛上因为这个忘记加换行被肘飞了）
B. [FJCPC 2025] 割点
link
简单来说，这道题就是三个条件，让我们构造一个图，让它满足下面的条件：
- 节点$1$必须是割点，$n$号节点不是割点。
- 对于中间的节点（$2$到$n-1$），给定一个$01$串指定这个节点是不是割点（第$i$个字符是$1$代表第$i$号节点是割点，反之不是）
- 图的度数序列需要满足从$1$到$n$为非升序。
（说白了，我白说了，我不会做……）
代码就等我思考114514以后再放吧
C.「C.E.L.U-01」族谱树
link
求lca的方法有倍增和tarjan，因为tarjan的时间复杂度够，而倍增肯定会tle
我们在dfs时就统计答案，这样就可以$O(n)$（？）处理出每个深度的答案
1
2
3
4
5
6
7
8
| void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
for(int i=head[u];i;i=nxt[i])
dfs(v[i],u),f[v[i]]=u;
if(ans[dep[u]]==0)ans[dep[u]]=u;
else ans[dep[u]]=find(ans[dep[u]]);
}
|
后面两行就是求当前深度的lca
ans[dep[u]]==0是判断这个深度是不是还没有记录答案，那就是当前节点$u$了
否则就是find(ans[dep[u]])
注意要用上快读，不要偷懒用vector，这题卡时间的！
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
|
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5000010;
int head[MAXN],nxt[MAXN],v[MAXN];
int f[MAXN],ans[MAXN],dep[MAXN];
bool vis[MAXN];
int n,q;
int read()
{
register int x=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int find(register int i)
{
if(f[i]==i)return i;
return f[i]=find(f[i]);
}
void dfs(register int u,register int fa)
{
dep[u]=dep[fa]+1;
for(int i=head[u];i;i=nxt[i])
dfs(v[i],u),f[v[i]]=u;
if(ans[dep[u]]==0)ans[dep[u]]=u;
else ans[dep[u]]=find(ans[dep[u]]);
}
int main()
{
n=read(),q=read();
for(register int i=1;i<=n;i++)
{
f[i]=i;
int u=read();
v[i]=i,nxt[i]=head[u],head[u]=i;
}
dfs(1,0);
while(q--)printf("%d\n",ans[read()]);
return 0;
}
|
（其实中间的register没啥用处，应该是可以删掉的）
D.[HEOI2016/TJOI2016] 树
link
通过记录时间倒着来推
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
| #include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
struct option
{
bool type;
int id,ans;
}opt[MAXN];
vector <int> g[MAXN];
int color[MAXN],f[MAXN],ff[MAXN];
void dfs(int u,int fa)
{
if(color[u])f[u]=u;
else f[u]=fa;
ff[u]=fa;
for(auto v:g[u])
if(v!=fa)dfs(v,u);
}
int find(int i)
{
if(f[i]==i)return i;
return f[i]=find(f[i]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
color[1]=1;
for(int i=1;i<=m;i++)
{
char op;
cin>>op>>opt[i].id;
opt[i].type=(op=='C');
if(op=='C')color[opt[i].id]++;
}
dfs(1,0);
ff[1]=1;
for(int i=m;i>=1;i--)
if(opt[i].type)
{
color[opt[i].id]--;
if(!color[opt[i].id])f[opt[i].id]=ff[opt[i].id];
}
else opt[i].ans=find(opt[i].id);
for(int i=1;i<=m;i++)
if(!opt[i].type)
cout<<opt[i].ans<<'\n';
return 0;
}
|