https://codeforces.com/gym/104090
C. No Bug No Game
题解
显然，部分被放入的物品只有一个。我们可以枚举物品 i 和它被放入的体积。然后枚举它前面的物品一共占用的体积 j，就能得到后面的物品一共占用的体积 k−i−j。对前缀和后缀分别做一遍背包就可以了。
G. Subgraph Isomorphism
题解
当 m=n−1 时，显然答案为 YES。当 m>n 时，答案一定为 NO。当 n=m 时，考虑环上的所有点。当且仅当每个点的子树同构或只有两种子树交替出现时，答案为 YES。判定子树同构可以用树哈希实现。
代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull mask(chrono::steady_clock::now().time_since_epoch().count());
ull shift(ull x)
{
x^=mask;
x^=x<<13;
x^=x>>7;
x^=x<<17;
x^=mask;
return x;
}
const int N=1e5+5;
int st,f[N],deg[N];
bool vis[N];
ull hsh[N];
vector<int> g[N];
void dfs(int u,int fa)
{
hsh[u]=1;
for(auto v:g[u])
{
if(v==fa||!vis[v]) continue;
dfs(v,u);
hsh[u]+=shift(hsh[v]);
}
}
void dfs0(int u,int fa)
{
dfs(u,0);
f[u]=fa;
for(auto v:g[u])
if(v!=fa&&v!=st&&!vis[v]) dfs0(v,u);
}
void solve()
{
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++) g[i].clear(),vis[i]=0,deg[i]=0;
for(int i=1;i<=m;i++)
{
int u,v;cin>>u>>v;
deg[u]++,deg[v]++;
g[u].push_back(v),g[v].push_back(u);
}
if(m==n-1)
{
cout<<"YES"<<'\n';
return;
}
if(m>n)
{
cout<<"NO"<<'\n';
return;
}
queue<int> q;
for(int i=1;i<=n;i++)
if(deg[i]==1) vis[i]=1,q.push(i);
while(!q.empty())
{
int u=q.front();q.pop();
for(auto v:g[u])
{
deg[v]--;
if(deg[v]==1) vis[v]=1,q.push(v);
}
}
for(int i=1;i<=n;i++)
if(!vis[i])
{
for(auto j:g[i])
{
if(!vis[j])
{
st=i;
dfs0(i,j);
if(hsh[i]==hsh[j])
{
bool ok=1;
for(int k=j;k!=i;k=f[k])
if(hsh[k]!=hsh[i]) ok=0;
cout<<(ok?"YES":"NO")<<'\n';
}
else
{
bool ok=1;
for(int k=j;k!=i;k=f[k])
{
if(hsh[k]==hsh[f[k]]) ok=0;
if(hsh[k]!=hsh[i]&&hsh[k]!=hsh[j]) ok=0;
}
cout<<(ok?"YES":"NO")<<'\n';
}
return;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
while(t--)
{
solve();
}
return 0;
}
|
I. Guess Cycle Length
题解
由于每次只能得到 pi，所以必须得到一个数两次才能确定 n。一个想法是先走 n 次 1 步，然后走 n 次 n 步，类似于大步小步算法。但这样步数太多了。考虑先用一些询问的返回值来确定 n 的范围。假设 k 次询问得到最大的值为 mx，那么 n 的范围一定在 [mx,mx+d] 之间，这时我们先走小步，然后走一次步长为 mx ，然后再走大步，这样就容易走到之前的小步内了。唯一可能的风险是 n>mx+d，不过当取 k=3000，d=3000×3000 时，正确率已经非常高了。
代码
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
| #include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rd(int l,int r) {return rnd()%(r-l+1)+l;}
map<int,int> mp;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int x,n0=1;
for(int i=1;i<=3000;i++)
{
cout<<"walk "<<rd(1,1e9)<<endl;
cin>>x;
n0=max(n0,x);
}
mp[x]=0;
for(int i=1;i<3000;i++)
{
cout<<"walk "<<1<<endl;
cin>>x;
if(mp.find(x)!=mp.end())
{
cout<<"guess "<<i<<endl;
return 0;
}
mp[x]=i;
}
cout<<"walk "<<n0<<endl;
cin>>x;
int cnt=2999+n0;
while(1)
{
if(mp.find(x)!=mp.end())
{
cout<<"guess "<<cnt-mp[x]<<endl;
return 0;
}
cnt+=3000;
cout<<"walk "<<3000<<endl;
cin>>x;
}
return 0;
}
|
M. Please Save Pigeland
题解
对于每个点，记它与所有关键点的距离之和为 disi，与所有关键点距离的 gcd 为 gcdi，那么答案就是 mingcdidisi。考虑在换根的过程中维护：每次换根时，到子树内的关键点距离减少 w，到子树外的关键点距离增加 w，可以求出 dfs 序后区间加。维护 gcd 时考虑 gcd(a1,a2,⋯,am)=gcd(a1,a2−a1,⋯,am−am−1)，所以进行差分，每次修改的点就是 O(1) 级别的了。