atcoder ARC092F
给定一张 \(n\) 个点 \(m\) 条边的有向图，判断每一条边反向后是否改变图中强连通分量的数量。
数据范围： \(n\le1000 \ \ \ \ m\le200000\)
先跑一遍tarjan，然后问题转化为判断每个直接相连的两点在不经过其连边的情况下是否互通。
对每个点dfs维护前缀和后缀能否回到该点，若都不能则不能，反之则能
因为每条边都要遍历
所以在图上的dfs复杂度是边数 $ m $
$ O(n*m) $ 可以通过本题。
cf472D
给定图上所有点对距离，判断是否存在合法生成树
\(n\le2000\)
注意到若存在则必定为最小生成树，kruscal建图，$ n^{2} $ dfs判定，结束
#include<bits/stdc++.h>
using namespace std;
int n,tot,cnt;
int fa[4001000];
struct node{
int u,v,w;
}b[4001000];
int dis[3000][3000];
bool cmp(node a,node b){
return a.w<b.w;
}
int find(int a){
if(fa[a]==a) return a;
return fa[a]=find(fa[a]);
}
struct nodde{
int v,w;
};
bool flag=0;
vector<nodde>e[3000];
void dfs(int u,int fa,int s,int diss){
if(diss!=dis[s][u]) flag=1;
for(auto ed:e[u]){
int v=ed.v,w=ed.w;
if(v==fa) continue;
dfs(v,u,s,diss+w);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int u;
scanf("%d",&u);
dis[i][j]=u;
b[++tot].u=i;
b[tot].v=j;
b[tot].w=u;
if(i!=j&&u==0) flag=1;
}
}
for(int i=1;i<=n;i++) fa[i]=i;
sort(b+1,b+1+n*n,cmp);
for(int i=1;i<=n*n;i++){
int u=b[i].u,v=b[i].v;
if(find(u)!=find(v)){
e[u].push_back({v,b[i].w});
e[v].push_back({u,b[i].w});
cnt++;
fa[find(u)]=find(v);
if(cnt==n-1) break;
}
}
for(int i=1;i<=n;i++) dfs(i,0,i,0);
if(flag) cout<<"NO";
else cout<<"YES";
return 0;
}
简单移动
给两个长度相等的字符串 \(A,B\) 每次可以在中任选一个字符并移到串的开头。求将 \(A\) 变成
\(B\) 的最小操作次数。
等价于最长后缀和。
姨外孙女婿舅妈的妹夫
你有面值分别为$ 1\ 5\ 10\ 50 $的纸币，每种都有无穷多张。
给定 \(n\) 求使用 \(n\) 张纸币能够得到多少种不同的面值和。
表哥发现11之后n每加一ans加49
输入一个输出一个先想打表好吧