显然如果有多棵树,则一定会存在无法到达的点。否则直接暴力 b f s bfs bfs求每个点到其余点的距离, a n s ans ans取 m a x max max即可
#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
struct DSU{
vector<int> data;
void init(int n){data.assign(n,-1);}
bool unionSet(int x,int y){
x=root(x);
y=root(y);
if(x!=y){
if(data[y] < data[x]) swap(x,y);
data[x]+=data[y];
data[y]=x;
}
return x != y;
}
bool same(int x,int y) {return root(x)==root(y);}
int root(int x) {return data[x] < 0 ? x : data[x]=root(data[x]);}
int Size(int x) {return -data[root(x)];}
};
int n,m,dep[N];
bool st[N];
vector<int> g[N];
int bfs(int u){
mst(dep,-1);
mst(st,false);
queue<int> q;
dep[u]=0;
q.push(u);
while(q.size()){
int t=q.front();
st[t]=true;
q.pop();
rep(i,0,sz(g[t])){
int v=g[t][i];
if(st[v]) continue;
if(dep[v]==-1){
dep[v]=dep[t]+1;
q.push(v);
}
}
}
int res=0;
rep(i,1,n+1) res=max(res,dep[i]);
return res;
}
void solve(){
DSU d;
cin>>n>>m;
d.init(n+1);
rep(i,0,m){
int a,b;
cin>>a>>b;
g[a].PB(b);
g[b].PB(a);
d.unionSet(a,b);
}
if(d.Size(1)!=n) cout<<"=["<<endl;
else{
int ans=0;
rep(i,1,n+1){
ans=max(ans,bfs(i));
}
cout<<"=] "<<ans<<endl;
}
}
int main(){
IOS;
//freopen("window.in", "r", stdin);
//freopen("window.out", "w", stdout);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
最长公共子序列裸题,套模板即可
#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=2*1e3+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
int f[N][N];
char a[N],b[N];
void solve(){
cin>>a+1>>b+1;
int len1=strlen(a+1),len2=strlen(b+1);
rep(i,1,len1+1){
rep(j,1,len2+1){
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
}
cout<<f[len1][len2]<<endl;
}
int main(){
//IOS;
//freopen("window.in", "r", stdin);
//freopen("window.out", "w", stdout);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
将每个人的技能值排个序,从前到后 d f s dfs dfs即可。(这道题数据挺弱的,有的假算法都可以过)
#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=30;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
ll a[N];
int n,x,d,ans;
void dfs(int now,ll mn,ll sum){
if(sum>=x) ans++;
rep(i,now+1,n){
if(a[i]-mn<=d) dfs(i,mn,sum+a[i]);
}
}
void solve(){
cin>>n>>x>>d;
rep(i,0,n) cin>>a[i];
sort(a,a+n);
rep(i,0,n){
dfs(i,a[i],a[i]);
}
cout<<ans<<endl;
}
int main(){
IOS;
//freopen("window.in", "r", stdin);
//freopen("window.out", "w", stdout);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
排序后将第一个与最后一个结合,第二个与倒数第二个结合,以此类推。然后取最大值和最小值相减。
#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
int a[N];
void solve(){
int n;
cin>>n;
rep(i,0,n*2) cin>>a[i];
sort(a,a+n*2);
vector<int> v;
rep(i,0,n){
v.PB(a[i]+a[n*2-i-1]);
}
sort(all(v));
cout<<v[sz(v)-1]-v[0]<<endl;
}
int main(){
//IOS;
//freopen("window.in", "r", stdin);
//freopen("window.out", "w", stdout);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
思路很简单,就是使用 m a p map map统计每个字符串出现的次数,如果多次出现,则存进 a n s ans ans数组。做这道题时先是因为未知错误一直在第一个样例wa,后来一直超时,最后输出时使用puts才A掉。
#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=8*1e6+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
int n;
char s[N];
unordered_map<string,int> cnt;
string ans[N];
void solve(){
cin>>n;
int idx=0;
rep(i,0,n){
cin>>s;
if(!cnt[s]) cnt[s]++;
else{
if(strlen(s)>=4){
ans[idx++]=s;
}
}
}
if(n==1){
cout<<"SAFO"<<endl;
return;
}
if(!idx){
cout<<"SAFO"<<endl;
return;
}
cout<<idx<<endl;
rep(i,0,idx){
puts(ans[i].c_str());
}
}
int main(){
IOS;
//freopen("window.in", "r", stdin);
//freopen("window.out", "w", stdout);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
并查集裸题,套模板即可
#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=30;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
struct DSU{
vector<int> data;
void init(int n){data.assign(n,-1);}
bool unionSet(int x,int y){
x=root(x);
y=root(y);
if(x!=y){
if(data[y] < data[x]) swap(x,y);
data[x]+=data[y];
data[y]=x;
}
return x != y;
}
bool same(int x,int y) {return root(x)==root(y);}
int root(int x) {return data[x] < 0 ? x : data[x]=root(data[x]);}
int Size(int x) {return -data[root(x)];}
};
void solve(){
DSU d;
map<string,int> s;
int n,m;
cin>>n>>m;
d.init(n+1);
int idx=1;
rep(i,0,n){
string str;
cin>>str;
s[str]=idx++;
}
rep(i,0,m){
int op;
string s1,s2;
cin>>op>>s1>>s2;
int a=s[s1],b=s[s2];
if(op==1) d.unionSet(a,b);
else{
if(d.same(a,b)) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
}
}
int main(){
//IOS;
//freopen("window.in", "r", stdin);
//freopen("window.out", "w", stdout);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
线段树裸题,分别维护最大值最小值和 s u m sum sum即可
#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
int w[N];
struct Node{
int l,r,mn,mx,sum;
}node[N * 4];
struct SegTree{
void push_up(int ind){
node[ind].mn=min(node[lson].mn,node[rson].mn);
node[ind].mx=max(node[lson].mx,node[rson].mx);
node[ind].sum=node[lson].sum+node[rson].sum;
}
void push_down(int ind){
}
void build(int l,int r,int ind){
node[ind].l=l;
node[ind].r=r;
if(l==r){
node[ind].mn=w[l];
node[ind].mx=w[l];
node[ind].sum=w[l];
}else{
int mid=l+r>>1;
build(l,mid,lson);
build(mid+1,r,rson);
push_up(ind);
}
}
void update(int l,int r,int ind,int val){
if(l>node[ind].r || r<node[ind].l) return;
if(l<=node[ind].l && r>=node[ind].r){
node[ind].mn=val;
node[ind].mx=val;
node[ind].sum=val;
}else{
push_down(ind);
update(l,r,lson,val);
update(l,r,rson,val);
push_up(ind);
}
}
void query_sum(int l,int r,int ind,int &ans){
if(l>node[ind].r || r<node[ind].l) return;
if(l<=node[ind].l && node[ind].r<=r){
ans+=node[ind].sum;
}else{
push_down(ind);
query_sum(l,r,lson,ans);
query_sum(l,r,rson,ans);
push_up(ind);
}
}
void query_max(int l,int r,int ind,int &ans){
if(l>node[ind].r || r<node[ind].l) return;
if(l<=node[ind].l && node[ind].r<=r){
ans=max(ans,node[ind].mx);
}else{
push_down(ind);
query_max(l,r,lson,ans);
query_max(l,r,rson,ans);
push_up(ind);
}
}
void query_min(int l,int r,int ind,int &ans){
if(l>node[ind].r || r<node[ind].l) return;
if(l<=node[ind].l && node[ind].r<=r){
ans=min(ans,node[ind].mn);
}else{
push_down(ind);
query_min(l,r,lson,ans);
query_min(l,r,rson,ans);
push_up(ind);
}
}
};
void solve(){
int n,q;
cin>>n>>q;
SegTree seg;
rep(i,1,n+1) cin>>w[i];
seg.build(1,n,1);
while(q--){
int op,x,y;
cin>>op>>x>>y;
if(op==1){
int sum=0,mn=INF,mx=0;
seg.query_sum(x,y,1,sum);
seg.query_max(x,y,1,mx);
seg.query_min(x,y,1,mn);
cout<<sum-mn-mx<<endl;
}else{
seg.update(x,x,1,y);
}
}
}
int main(){
//IOS;
//freopen("window.in", "r", stdin);
//freopen("window.out", "w", stdout);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
要我们解一个同余方程,发现答案可以取 0 0 0,而任何数的 0 0 0次幂都是1,所以输出 0 0 0即可。(样例的这个 − 1 -1 −1没有看懂是什么意思)
#include<bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll oone=1;
void solve(){
int n,m;
scanf("%d%d",&n,&m);
cout<<0<<endl;
}
int main(){
//IOS;
//freopen("window.in", "r", stdin);
//freopen("window.out", "w", stdout);
int t;cin>>t;
while(t--)
solve();
return 0;
}