D – Circumferences(简单计算几何)
Problem
二维平面上给定两个点/(s,t/)和若干个圆，问是否可以从/(s/)只经过圆边到达/(t/)
/(1/le N/le 3000/)
Solve
把每个圆之间的相交或相切关系转换成两个圆可达，于是就变成了一个图论问题，给定起点和终点，问是否可以从起点到终点，一次/(bfs/)就可以实现。
但其实判断连通性也可以用并查集，这样更快。
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3005;
struct Point{
int x,y;
};
struct Circle{
Point c;
int r;
}cir[N];
bool vis[N][N],st[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
Point s,t;
cin>>s.x>>s.y>>t.x>>t.y;
for(int i=1;i<=n;i++){
cin>>cir[i].c.x>>cir[i].c.y>>cir[i].r;
}
int ss=0,tt=0;
auto get_dist=[&](Point a,Point b)->ll{
return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
};
for(int i=1;i<=n;i++){
if(get_dist(s,cir[i].c)==1LL*cir[i].r*cir[i].r){
ss=i;
}
if(get_dist(t,cir[i].c)==1LL*cir[i].r*cir[i].r){
tt=i;
}
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
ll d=get_dist(cir[i].c,cir[j].c);
ll L=1LL*(cir[i].r-cir[j].r)*(cir[i].r-cir[j].r);
ll R=1LL*(cir[i].r+cir[j].r)*(cir[i].r+cir[j].r);
if(L<=d&&d<=R){
vis[i][j]=vis[j][i]=1;
//f[find(i)]=find(j); 并查集
}
}
if(!ss||!tt) cout<<"No/n";
else{
/*
if(find(ss)!=find(tt)) cout<<"No/n";
else cout<<"Yes/n";s
*/
queue<int>q;
q.push(ss);
while(q.size()){
int u=q.front();
q.pop();
if(st[u]) continue;
st[u]=1;
if(u==tt){
cout<<"Yes/n";
return 0;
}
for(int v=1;v<=n;v++){
if(vis[u][v]&&!st[v]){
q.push(v);
}
}
}
cout<<"No/n";
}
return 0;
}
E – LCM on Whiteboard(简单数论、STL 去重)
Problem
给定/(n/)个数，每个数按照质因子分解的形式给出，对于/(1/le i/le n/)，若把第/(i/)个数变成/(1/)，可以得到一个这些数的最小公倍数。问可以得到多少个不同的最小公倍数
Solve
显然一开始的最小公倍数就是每个质因子最大幂次的乘积，现在只需要考虑把一个数变成/(1/)后是否对质因子的最大幂次产生影响即可。
感觉不好想到的就是用 STL 去重了，其实只要满足偏序关系的都是可以去重的，一开始数论部分很好考虑，考虑去重的情况考虑了很久。
Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<vector<pair<int,int>>>fac(n+1);
map<int,vector<int>>v;
for(int i=1;i<=n;i++){
int m;
cin>>m;
for(int j=1;j<=m;j++){
int p,x;
cin>>p>>x;
fac[i].emplace_back(p,x);
v[p].emplace_back(x);
}
}
for(auto &[p,q]:v) sort(q.begin(), q.end());
vector<vector<pair<int,int>>>ans;
for(int i=1;i<=n;i++){
vector<pair<int,int>>t;//这里存储的是需要除的因子的幂次，不直接求
for(auto [p,x]:fac[i]){
//如果i这个因p的幂次等于最大的幂次，说明变为1就会改变,
if(x==v[p].back()){
//看次大的是否还是最大幂次，如果是，则没有影响，否则就要除以最大幂次并乘上次大幂次
int d=(v[p].size()==1)?0:v[p][int(v[p].size())-2];
if(d!=x) t.emplace_back(p,d-x);
}
}
sort(t.begin(), t.end());
ans.push_back(t);
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()),ans.end());
cout<<ans.size()<<'/n';
}
F – Select Edges(树形 DP、带悔)
problem
给定一个/(N/)个点的树，每条树边有一个边权，现在要求每个点/(i/)的度数小于等于/(d_i/)，问保留哪些边可以使得保留下的边的边权和最大。
Solve
考虑树形/(dp/)：/(dp[u][0]/)表示不选择连向父亲的边，/(dp[u][1]/)表示选择连向父亲的边
一开始我们先记录/(u/)的儿子/(v/)都不选父边的贡献和/(s/)。然后我们记录每一个/(dp[v][1]+w-dp[v][0]/)，这一步是让我们有反悔的余地，这一步其实很好想到。
把所有/(dp[v][1]+w-dp[v][0]/)按照从大到小排序，然后开始转移：
令/(dp[u][0]=dp[u][1]=s/)，其实/(/sum_{v/in Son_u}dp[v][0]/)，然后我们开始反悔操作，加入一个/(dp[v][1]+w-dp[v][0]/)相当于撤销之前不选的操作从而选上这条边
对于/(dp[u][0]/)，把前/(d[u]/)大的累计进入答案，如果遇到小于/(0/)的，当做/(0/)加入答案。
对于/(dp[u][1]/)，把前/(d[u]-1/)大的累计进入答案，如果遇到小于/(0/)的，当做/(0/)加入答案。
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>d(n+1);
for(int i=1;i<=n;i++) cin>>d[i];
vector<vector<pair<int,int>>>e(n+1);
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
e[u].emplace_back(v,w);
e[v].emplace_back(u,w);
}
vector<vector<ll>>dp(n+1,vector<ll>(2));
//dp[u][0]:不选连向父亲的边
//dp[u][1]:选连向父亲的边
const int inf=1e9;
auto dfs=[&](auto self,int u,int fa)->void{
ll s=0;
vector<ll>ww;
for(auto [v,w]:e[u]){
if(v==fa) continue;
self(self,v,u);
s+=dp[v][0];
//类似于带悔贪心的思想，假设u的连向儿子的边都没有选，通过这种差值替换每一条边的选择方案。
//这里取好和0取max,是因为如果是负数，可能不会选，而题目要求的是选的边数小于等于d[u]
ww.push_back(max(dp[v][1]+w-dp[v][0],0LL));
}
sort(ww.begin(), ww.end());;
reverse(ww.begin(), ww.end());
dp[u][0]=s;
//在所有连向儿子的边中选择最大的d[u]条替换，由于选择的是d[u]条，所以向dp[u][0]转移
for(int i=0;i<min(int(ww.size()),d[u]);i++) dp[u][0]+=ww[i];
if(d[u]==0) dp[u][1]=-inf;
else{
dp[u][1]=s;
//选择d[u]-1条，向dp[u][1]转移，代表要选连向u父亲的边
for(int i=0;i<min(int(ww.size()),d[u]-1);i++) dp[u][1]+=ww[i];
}
};
dfs(dfs,1,1);
cout<<dp[1][0]<<'/n';
}
G – Grid Card Game(最小割、网格模型)
Problem
给定一个/(n/times m/)的网格，每个格子上有一个数字/(a_{i,j}/)，现在可以选择若干列和若干行，贡献就是这些列和行中的元素的并集的和。但如果某一行和某一列的交点的数字是负数，那么贡献就要减去/(10^{100}/)，问可以得到的最大贡献是多少。
Solve
网格模型，把行和列分别当做点
显然，如果某一行和某一列的和小于/(0/)一定不会选
假设目前选择了一行/(i/)和一列/(j/)，由于我们已经分别统计过他们的和的贡献，因此还需要减去他们交点的数字，不然会重复计数
于是可以构建这样一个网络流模型：
- 源点/(S/)向每个和大于/(0/)的行连边
- 每个和大于/(0/)的列向汇点/(T/)连边
- 对于一行/(i/)和一列/(j/)，如果/(a_{i,j}/lt 0/)，那么/(i/)向/(j/)连边权为/(/infty/)的边，否则连边权为/(a_{i,j}/)的边权。
- 最后就是所有非负数行列和之和-最小割
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=205,M=N+N*N;
const ll INF=1LL<<60;
int n,m,S,T,cnt;
int head[N],d[N],cur[N];
struct edges
{
int v,nxt;
ll f;
}e[M*2];
void add(int u,int v,ll f)
{
e[cnt].v=v,e[cnt].nxt=head[u],e[cnt].f=f,head[u]=cnt++;
e[cnt].v=u,e[cnt].nxt=head[v],e[cnt].f=0,head[v]=cnt++;
}
bool bfs()
{
memset(d,-1,sizeof d);
queue<int>q;
q.push(S);
d[S]=0,cur[S]=head[S];
while(q.size())
{
int u=q.front();
q.pop();
for(int i=head[u];~i;i=e[i].nxt)
{
int v=e[i].v;
ll f=e[i].f;
if(d[v]==-1&&f)
{
d[v]=d[u]+1;
cur[v]=head[v];
if(v==T) return true;
q.push(v);
}
}
}
return false;
}
ll find(int u,ll limit)
{
if(u==T) return limit;
ll flow=0;
for(int i=cur[u];~i&&flow<limit;i=e[i].nxt)
{
cur[u]=i;
int v=e[i].v;
ll f=e[i].f;
if(d[v]==d[u]+1&&f)
{
ll t=find(v,min(f,limit-flow));
if(!t) d[v]=-1;
e[i].f-=t,e[i^1].f+=t,flow+=t;
}
}
return flow;
}
ll dinic()
{
ll ans=0,flow;
while(bfs()) while(flow=find(S,INF)) ans+=flow;
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
memset(head,-1,sizeof head);
cin>>n>>m;
S=0,T=n+m+1;
vector<vector<ll>>a(n+1,vector<ll>(m+1));
vector<ll>x(n+1),y(m+1);
ll sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
x[i]+=a[i][j];
y[j]+=a[i][j];
if(a[i][j]<0) add(i,n+j,INF);
else add(i,n+j,a[i][j]);
}
for(int i=1;i<=n;i++) if(x[i]>0)add(S,i,x[i]),sum+=x[i];
for(int i=1;i<=m;i++) if(y[i]>0)add(n+i,T,y[i]),sum+=y[i];
ll flow=dinic();
cout<<sum-flow<<'/n';
return 0;
}
Ex – Yet Another Path Counting(根号分治的思想)
Problem
给定一个/(n/times n/)的网格，每个网格上有一个数字/(1/le a_{i,j}/le n^2/)。每次在网格上可以向下或向右走，问起点和终点数字相同的路径数量
/(1/le N/le 400/)
Solve
暴力做法 1：
枚举每个数字，枚举它的所有出现过的网格，然后把这些网格两两组合，每次计算用组合数直接计算/(O(1)/)的复杂度。但如果全部格子都是一样的数字，那么/(n^2/)个格子两两组合就是/(n^4/)，时间复杂度显然不行。
暴力做法 2：
用/(dp/)的做法，每次枚举一种颜色，然后用/(dp/)做法/(O(n^2)/)求出，但如果有/(n^2/)种颜色，那么时间复杂度就是/(O(n^4)/)的，所以也不行。
考虑在这两种做法中做一个平衡，类似于根号分治的思想/(O(/sqrt{n^2}n^2)=O(n^3)/)
枚举每一个数字，如果这个数字的个数小于等于/(n/)，那么就用暴力做法 1，否则用暴力做法 2.
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
int power(int x,int y){
int res=1;
while(y){
if(y&1) res=1LL*res*x%mod;
x=1LL*x*x%mod;
y>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>fac(2*n+1),infac(2*n+1);
fac[0]=1;
for(int i=1;i<=2*n;i++) fac[i]=1LL*fac[i-1]*i%mod;
infac[2*n]=power(fac[2*n],mod-2);
for(int i=2*n;i>=1;i--) infac[i-1]=1LL*infac[i]*i%mod;
vector<vector<int>>a(n+1,vector<int>(n+1));
vector<vector<pair<int,int>>>c(n*n+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>a[i][j];
c[a[i][j]].emplace_back(i,j);
}
auto binom=[&](int n,int m)->int{
if(n<m||m<0) return 0;
return 1LL*fac[n]*infac[m]%mod*infac[n-m]%mod;
};
ll ans=0;
for(int k=1;k<=n*n;k++){
if(c[k].size()<=n){
for(int i=0;i<c[k].size();i++)
for(int j=i;j<c[k].size();j++){
auto p=c[k][i],q=c[k][j];
if(p.second>q.second) continue;
int x=q.first-p.first+q.second-p.second;
int y=q.first-p.first;
ans=(ans+binom(x,y))%mod;
}
}else{
vector<vector<int>>dp(n+1,vector<int>(n+1));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(a[i][j]==k) dp[i][j]=1;
dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
if(a[i][j]==k) ans=(ans+dp[i][j])%mod;
}
}
}
if(ans<0) ans=(ans+mod)%mod;
cout<<ans<<'/n';
}
原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/273399.html