模拟赛 #13
总结
T1，T2
考场上很快就写出来了，没有什么大问题。
T3
考场上想到了绝大部分正解，但是最后有一个小性质没有想到，所以没有拿到分。
题解
T1
贪心即可。如果说当前这个杆子能往左放倒，就往左放倒，不能放倒就往右放倒，如果都不能就立着。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
pair<int,int> a[maxn];
signed main()
{freopen("put.in","r",stdin); freopen("put.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,r=-1,ans=1;cin>>n;for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;sort(a+1,a+1+n);r=a[1].first;for(int i=2;i<n;i++){if(a[i].first-a[i].second>r) r=a[i].first,ans++;else if(a[i].first+a[i].second<a[i+1].first) r=a[i].first+a[i].second,ans++;else r=a[i].first;}cout<<ans+1;return 0;
}
T2
考虑贪心，我们每一次让最小的和最小的匹配，然后依次往上。最后到最大的和最大的匹配。不难证明，这样一定是最优的。
由于题目让我们每次要删掉一个 \(b\) 中的值。那么我们可以发现删掉这个 \(b\) 的值，它的前面是不会被影响的，而在他之后的则会变成 \(b_{i+1}\) 和 \(a_i\) 配对。
对这两者分别做一个前缀最大值和后缀最大值即可。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
int a[maxn],suf[maxn],pre[maxn],ans[maxn];
pair<int,int> b[maxn];
signed main()
{freopen("match.in","r",stdin);freopen("match.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n;cin>>n;for(int i=1;i<=n+1;i++) cin>>b[i].first,b[i].second=i;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);sort(b+1,b+2+n);for(int i=1;i<=n;i++) pre[i]=max({pre[i-1],0ll,b[i].first-a[i]});for(int i=n;i>=1;i--) suf[i]=max({suf[i+1],0ll,b[i+1].first-a[i]});for(int i=1;i<=n+1;i++) ans[b[i].second]=max(pre[i-1],suf[i]);for(int i=1;i<=n+1;i++) cout<<ans[i]<<' ';return 0;
}
T3
这个题目我们可以发觉，求因数是不好求的，我们可以考虑求倍数。
这样我们就可以去整数分块。
那么此时我们对 \(\lfloor \frac{n}{i} \rfloor\) 区分块。
那么对于这样子的分块，已知左端点，我们有一个求右端点的公式。即：
求出每一个块之后我们就知道长度。现在的问题就是如何快速的求出异或和。
这里有一个很有意思的性质。\(2k\bigoplus (2k+1)=1\) ，根据这个性质，我们可以对长度及左右单点特殊判断即可。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
signed main()
{freopen("div.in","r",stdin);freopen("div.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,ans=0;cin>>n;for(int l=1,r=0;l<=n;l=r+1){int x=n/l;r=n/x;if(x&1){int len=r-l+1;if(len&1){if(l&1) ans^=l^(len/2&1);else ans^=r^(len/2&1);}else{if(l&1) ans^=l^r^(len/2-1&1);else ans^=(len/2&1);}}}cout<<ans;return 0;
}
模拟赛 #14
总结
T1,T2,T3
考场上很快就想出了做法，并且达到了正解，没有什么问题。
T4
考场上想到了一大步纷纷跑的做法下来，发觉郑姐就是这么做，但是还是有一些部分没法做。有一个非常巧妙的做法
题解
T1
记录每一个数值的总共的出现次数。
那么如果说我们不去重的话，我们的总贡献值和为：\(C_m^2 \times n\)
如果说去重的话，那么任意两个同时出现，以其中一个数值就会使得贡献减一。所以我们只需要对每一个贡献值求出来。任取两个的方案数，然后再给总贡献值减去就可以了。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
int cnt[maxn],a[maxn],st[maxn],ed[maxn];
signed main()
{freopen("array.in","r",stdin);freopen("array.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i],ed[a[i]]=1,st[a[i]]=0;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;cnt[a[x]]+=i-st[a[x]];st[y]=i;ed[a[x]]=0;a[x]=y;ed[a[x]]=1;}for(int i=0;i<=n+m;i++) if(ed[i]) cnt[i]+=m-st[i]+1;int ans=(m+1)*m*n;for(int i=0;i<=n+m;i++){if(cnt[i]<=1) continue;ans-=cnt[i]*(cnt[i]-1)/2;}cout<<ans<<endl;return 0;
}
T2
考虑DP由于每一行他的次数最多修改 \(m\) 次，不然改了跟没改是一个道理，所以说我们现在就可以设出 \(f_{i,j}\) 和 \(g_{i,j,k}\)。
分别表示走到 \((i,j)\) 的最小步数以及走到 \((i,j)\) 这个位置，他当前这一行旋转 \(k\) 次的最小步数。
那么转移方程如下。
其中 \(K\) 就是题目给的 \(K\)。那么最后答案就是。\(f_{n,m-1}\)
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=200+5;
int f[maxn][maxn],g[maxn][maxn][maxn],a[maxn][maxn];
signed main()
{freopen("escape.in","r",stdin);freopen("escape.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++) for(int j=0;j<m;j++) cin>>a[i][j];memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));f[0][0]=0;for(int i=1;i<=n;i++)for(int j=0;j<m;j++)for(int l=0;l<=m;l++){g[i][j][l]=min(g[i][j-1][l],f[i-1][j]+k*l)+a[i][(j+l)%m];f[i][j]=min(f[i][j],g[i][j][l]);}cout<<f[n][m-1];return 0;
}
T3
我对于每一个加属性节点，我们考虑在它之前的战斗节点应该怎么分配，因为我们会发现他们我无论加哪个。总的属性点数是一样的，所以说我们就可以去枚举。找出最优的解法即可。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+1;
int a[maxn],b[maxn],dp[maxn];
signed main()
{freopen("game.in","r",stdin);freopen("game.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,m,cnt=0;cin>>n>>m;for(int i=1;i<=n;i++){int x;cin>>x;if(x>0) a[x]++;if(x<0) b[-x]++;if(x==0||i==n){for(int i=1;i<=cnt;i++) a[i]+=a[i-1],b[i]+=b[i-1];for(int i=0;i<=cnt;i++) dp[i]=dp[i]+a[i]+b[cnt-i];cnt++;for(int i=cnt;i>=0;i--) dp[i]=max(dp[i],dp[i-1]);memset(a,0,sizeof(a));memset(b,0,sizeof(b));}}int ans=0;for(int i=1;i<=m;i++) ans=max(ans,dp[i]);cout<<ans;return 0;
}
T4
不难发觉一个性质，如果说我不能在前两个回合内分出胜负，那么他们这辈子都不可能分出胜负了。
那么只考虑在前两个回合内，Bob胜出的方案为：
- \(q\) 在叶子上
- 如果 \(q\) 朝 \(p\) 的方向移动一个之后，\(q\) 接下来一定是一个和叶子相邻的节点。
对于第一种情况，我们设叶子结点数为 \(c\)，那么。方案数就为 \(c\times (n-c)\)。
而对于第2种情况，我们可以统计那些。不和叶子节点相邻的节点的总个数。
那么对于每一个跟叶子节点相邻的点我们选一个点当 \(q\) 节点另外一边我们选一个 \(p\) 节点，即：\(ans=\sum x\times d_i-1\)
其中 \(d_i\) 代表的就是当前这个点连接的度数。除连接叶子节点。
两者相加即为答案。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
vector<int> g[maxn];
int d[maxn];
signed main()
{freopen("caterpillar.in","r",stdin);freopen("caterpillar.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,ans=0,c1=0,c2=0;cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}for(int i=1;i<=n;i++) if(g[i].size()==1) c1++;ans+=c1*(n-c1);for(int i=1;i<=n;i++)if(g[i].size()>1){for(auto to:g[i]) if(g[to].size()>1) d[i]++;if(d[i]==g[i].size()) c2++;}for(int i=1;i<=n;i++) if(d[i]>1&&d[i]!=g[i].size()) ans+=c2*(d[i]-1);cout<<ans;return 0;
}