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)\) 个数：
\(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;
}
- Beginner Atcoder Contest 315beginner atcoder contest 315 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310