D
题意：给定一个 \(n\times m\) 的字符矩形，重复执行以下操作直到删除字符数为0：
- 对于每一行，若有且仅有一种字符存在，且个数大于1，将这些字符标记
- 对于每一列，若有且仅有一种字符存在，且个数大于1，将这些字符标记
- 删除所有标记的字符
求最后还能剩下多少字符。
注意到每一行每一列最多被删一次，我们可以用队列模拟这个操作，每次更新时间复杂度是 \(O(n+m)\)，并将被删数标记。
时间复杂度 \(O((n+m)^2)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 505050
char a[5050][5050];
int h[5050][300],r[5050][300],vis[5050][5050],s[N][2],n,m,sur[N][2];
struct node{
int id,opt;
};
queue<node>q;
signed main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
h[i][a[i][j]-'a']++,r[j][a[i][j]-'a']++;
s[i][0]++,s[j][1]++;
}
}
for(int i=1;i<=n;i++)for(int j=0;j<26;j++)sur[i][0]+=(h[i][j]>0);
for(int i=1;i<=m;i++)for(int j=0;j<26;j++)sur[i][1]+=(r[i][j]>0);
for(int i=1;i<=n;i++)if(sur[i][0]==1&&s[i][0]!=1){
q.push((node){i,0});
}
for(int i=1;i<=m;i++)if(sur[i][1]==1&&s[i][1]!=1){
q.push((node){i,1});
}
while(!q.empty()){
node u=q.front();q.pop();
if(u.opt==0){
for(int i=1;i<=m;i++){
if(vis[u.id][i]==0){
vis[u.id][i]=1;r[i][a[u.id][i]-'a']--;s[i][1]--;
if(r[i][a[u.id][i]-'a']==0){
sur[i][1]--;if(sur[i][1]==1&&s[i][1]!=1)q.push((node){i,1});
}
}
}
}
else {
for(int i=1;i<=n;i++){
if(!vis[i][u.id]){
vis[i][u.id]=1;h[i][a[i][u.id]-'a']--;s[i][0]--;
if(h[i][a[i][u.id]-'a']==0){
sur[i][0]--;
if(sur[i][0]==1&&s[i][0]!=1)q.push((node){i,0});
}
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans+=(vis[i][j]==0);
}
}
cout<<ans<<"\n";
}
E
题意：给定若干本书，在读第 \(i\) 本书之前，需要读 \(p_i\) 本书，分别是 \(c_{i,1}\sim c_{i,p_i}\)
求一个读书顺序，使得读的书最少且满足读了这些书之后就可以读第一本书。数据保证有解。
首先，我们建立两张有向图，第一张图的边形如 \((i,j)\)，意为读第 \(i\) 本书必须要读第 \(j\) 本书。第二张图是第一张图的反图。
然后我们在第一张图从点1开始跑，标记到达的所有点，这些书是必读书，其他书没有任何关系。
接下来这个顺序，便可以在第二张图里只对被标记的点进行Topsort即可。
F
赛上一直以为是优先队列模拟，最后3min意识到是DP，却是没了时间。
题意：给定 \(n\) 个平面上的点 \((x_i,y_i)\)，你需要从1号节点按顺序走到 \(n\) 号节点，从点 \(i\) 走到点 \(i+1\) 的代价为二者的欧几里得距离。
现在你可以选择跳过其中一部分点，不可以跳过点1和点 \(n\)，假设你跳过了 \(c\) 个点，就需要付出 \(2^{c-1}\) 的额外代价（\(c=0\) 时候需要付出0代价）
求你最终需要付出的代价最小值。你的答案不可以和标准答案误差超过 \(10^{-5}\)
范围：\(2\le n\le 10^4,0\le x_i,y_i\le 10^4\)，不存在两个重合的点。
首先估计答案上界，不跳过点，其代价最多为 \(n\sqrt {2\times 10^8}\le 10^8\sqrt 2< 2^{30}\)
所以说，\(c\) 是不可能超过 \(29\) 的。这时候可以考虑直接枚举 \(c\) 计算答案。
怎么算？最优化问题，可以选择跳过，问题可划分可拼凑，明显的动态规划。
设 \(f_{i,j}\) 为前 \(i\) 个点里跳过 \(j\) 个点，在第 \(i\) 个点落脚所付出的最小代价。
显然有 \(f_{i,j}=\min_{j\ge (i-k-1)}f_{k,j-(i-k-1)}+dis(k,i)\)
然后枚举答案，\(\min f_{n,i}+2^{i-1}\)。复杂度 \(O(nc^2)\)
当附加代价单一可以通过某参数单独计算时，可先不考虑附加代价，最后处理即可。
signed main(){
cin>>n;
db ans=1e18;
for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
f[1][0]=0;
for(int j=0;j<=30ll;j++){
for(int i=2;i<=n;i++){
f[i][j]=1e18;
for(int k=1;k<i;++k)if(i-k-1<=j)f[i][j]=min(f[i][j],f[k][j-(i-k-1)]+dis(i,k));
}
}
for(int c=0;c<=30;++c){
db res;
if(c==0)res=0;
else res=(1<<(c-1));db mn=1e18;
for(int i=0;i<=min(n,c);i++)mn=min(mn,f[n][i]);
res+=mn;
ans=min(ans,res);
}
printf("%.15f",ans);
}
G
题意：给定 \(N,A,B,C,X\)，求满足以下条件的 \((i,j,k)\) 个数：
\[Ai+Bj+Ck=X,1\le i,j,k\le N \]\(1\le N\le 10^6,1\le A,B,C\le 10^9,1\le X\le 3\times 10^{15}\)
在这个问题中，注意到下界是1，不方便处理，可令 \(X'=X-A-B-C,N'=N-1\),将下界化为0
首先，注意到 \(N\) 比较小，可以进行枚举 \(i\)，那么式子就化为 \(Bx+Cy=X'\)，其中 \(X'=X-Ai\)。
设 \(d=\gcd(B,C)\)，若 \(d\) 不整除 \(X'\)，则直接 continue。
我们设 \(b=\frac{B}{d},c=\frac{C}{d}\)，另用exgcd求一组特解 \(Bx_0+Cy_0=d\)，并将 \(x_0\) 化为最小非负整数解。(防爆long long)
然后，我们对于 \(Bx+Cy=X'\)，先令 \(x_1=x_0·\frac{X'}{d}\bmod c\)(有细节，需提前模)，同时求出另一个对应的 \(y_1\)。
此时注意到合法的系数必定是在一段区间之内，设端点为 \(l,r\)。
注意以下简称系数是指周期数，也即解的个数。
此时必定有 \(x_1\) 是最小解了，那么它的系数的 \(l\) 应该由 \(y_1\) 来限制，也即 \(l=\lceil\frac{(y_1-N)}{b}\rceil\)。
这是要找出令 \(y'_1\le N\) 的最小系数。当然有可能 \(y_1\le N\)，此时应当令 \(l=0\)
综上，\(l=\max(0,\lceil\frac{(y_1-N)}{b}\rceil)\)
然后考虑求最大解。有两种情况：
- 一是由 \(y\) 来决定，它取最小值时，\(x\) 取得最大系数，是 \(\lfloor\frac{y_1}{b}\rfloor\)(之所以下取整是要留一个最小非负解)。
- 二是由 \(x\) 来决定，它最大可以取到 \(\lfloor\frac{N-x_1}{c}\rfloor\)。
所以 \(r=\min(\lfloor\frac{N-x_1}{c}\rfloor,\lfloor\frac{y_1}{b}\rfloor)\)
当然，若 \(x_1>N\)，亦或者 \(y_1<0\)，这都是非法的，直接令 \(r=-1\) 即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int get(int a,int b,int c,int &x,int &y){//ax+by=c
int d=exgcd(a,b,x,y);x*=c/d,y*=c/d;
return d;
}
int N,A,B,C,X;
signed main(){
ios::sync_with_stdio(false);
cin>>N>>A>>B>>C>>X;
N--,X-=A+B+C;
if(X<0){
puts("0");return 0;
}
int x0,y0;
int d=exgcd(B,C,x0,y0),b=B/d,c=C/d,ans=0;//k0=b,k1=c
x0%=c;y0=(d-B*x0)/C;
for(int i=0;i<=N;i++){
int x=X-i*A;
if(x%d!=0)continue;
if(x<0)break;
int l,r,x1=x/d%c*x0,y1;x1=(x1%c+c)%c,y1=(x-x1*B)/C;
l=max(0ll,(y1-N+b-1ll)/b);
if(x1>N||y1<0)r=-1ll;
else r=min((N-x1)/c,y1/b);
if(l<=r)ans+=r-l+1;
}
cout<<ans;
}