ベ断桥烟雨ミ_53

264

sacave

......_519
ermu99

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
struct Edge
{
int id,w;
};
vector<Edge> h[N];
int dist[N];
void dfs(int u,int father,int distance)
{
dist[u]=distance;
for(int i=0;i<h[u].size();i++)
if(h[u][i].id!=father)
dfs(h[u][i].id,u,distance+h[u][i].w);
}
int main(){
int n;
cin>>n;
int t=n-1;
while(t--)
{
int a,b,c;
cin>>a>>b>>c;
h[a].push_back({b,c});
h[b].push_back({a,c});
}
dfs(1,-1,0);
int u=1;
for(int i=1;i<=n;i++)
if(dist[i]>dist[u])
u=i;

dfs(u,-1,0);
for(int i=1;i<=n;i++)
if(dist[i]>dist[u])
u=i;

int s=dist[u];
cout<<((long long)21+s)*s/2;
return 0;
}



#include <bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
bool st[N][N];
int n;
typedef pair<int,int> PII;
#define x first
#define y second
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int  bfs(int x,int y)
{
int total=0,bound=0;
queue<PII> q;
q.push({x,y});
while(q.size())
{
PII t=q.front();
q.pop();
total++;
st[t.x][t.y]=true;
bool has_hy=false;
for(int i=0;i<4;i++)
{
int a=t.x+dx[i],b=t.y+dy[i];
if(a<1||b<1||a>n||b>n)continue;
if(st[a][b])continue;
if(g[a][b]=='.'){
has_hy=true;
continue;
}
if(g[a][b]=='#')
{
q.push({a,b});
st[a][b]=true;
}
}
if(has_hy==true)bound++;
}
if(total==bound)return 1;
else return 0;
}
int main(){

cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>g[i][j];

int cnt=0;//被淹岛屿的数量
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{

if(g[i][j]=='#'&&!st[i][j])
{

cnt+=bfs(i,j);
}
}
cout<<cnt<<endl;;
return 0;
}


#include <bits/stdc++.h>
using namespace std;
const int N=110;
struct Point
{
int x,y,z;
};
int dx[6] = {1, 0, -1, 0, 0, 0};
int dy[6] = {0, 1, 0, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, -1, 1};
int L,R,C;
char g[N][N][N];
int dist[N][N][N];
void bfs(Point start,Point end)
{
queue<Point> q;

q.push({start.x,start.y,start.z});
dist[start.x][start.y][start.z]=0;
while(q.size())
{
Point t=q.front();
q.pop();
for(int i=0;i<6;i++)
{
int x=t.x+dx[i],y=t.y+dy[i],z=t.z+dz[i];
if(x<1||y<1||z<1||x>L||y>R||z>C)continue;
if(g[x][y][z]=='#')continue;
if(dist[x][y][z]!=-1)continue;

q.push({x,y,z});
//g[x][y][z]='#';
dist[x][y][z]=dist[t.x][t.y][t.z]+1;
}
}
}
int main(){
while(cin>>L>>R>>C,L&&R&&C)
{
memset(dist, -1, sizeof(dist));
Point start,end;
for(int i=1;i<=L;i++)
for(int j=1;j<=R;j++)
for(int k=1;k<=C;k++)
{
cin>>g[i][j][k];
if(g[i][j][k]=='S')
start.x=i,start.y=j,start.z=k;
else if(g[i][j][k]=='E')
end.x=i,end.y=j,end.z=k;

}
bfs(start,end);
int distance=dist[end.x][end.y][end.z];
if(distance==-1)cout<<"Trapped!"<<endl;
else printf("Escaped in %d minute(s).\n",distance);
}
return 0;
}


#include <bits/stdc++.h>
using namespace std;
int a[100010];

int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];

int maxv=0;
int sd=1;
for(int d=1,i=1;i<=n;i*=2,d++)//d为深度，或层数，i为每层开始的起点
{
long long  s=0;
for(int j=i;j<i+i&&j<=n;j++)
s+=a[j];
if(maxv<s)
{
maxv=s;
sd=d;
}
}
cout<<sd;
return 0;
}


#include <bits/stdc++.h>
using namespace std;
const int N=25;
typedef pair<int,int> PII;
#define x first
#define y second
char a[N][N];
int w,h;
int bfs(int sx,int sy)
{
int cnt=0;
queue<PII> q;
q.push({sx,sy});
a[sx][sy]='#';
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
while(q.size())
{
PII t=q.front();
q.pop();
cnt++;
for(int i=0;i<4;i++)
{
int x=t.x+dx[i],y=t.y+dy[i];
//if(x<1||x>h||y<1||y>w||a[x][y]=='#')continue;
if(a[x][y]=='.')
{
q.push({x,y});
a[x][y]='#';
}
}
}
return cnt;
}
int main(){

while(cin>>w>>h,w&&h)
{
int startx,starty;
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
{
cin>>a[i][j];
if(a[i][j]=='@')
{
startx=i,starty=j;
}
}
cout<<bfs(startx,starty)<<endl;
}
return 0;
}


#include <bits/stdc++.h>
using namespace std;
int w,h;
char g[25][25];
int dfs(int x,int y)
{
int cnt=1;
g[x][y]='#';
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a>=1&&a<=h&&b>=1&&b<=w&&g[a][b]=='.')
{
cnt+=dfs(a,b);
}
}
return cnt;
}
int main(){
while(cin>>w>>h,w||h)
{
int sx,sy;
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
{
cin>>g[i][j];
if(g[i][j]=='@')
sx=i,sy=j;
}
cout<<dfs(sx,sy)<<endl;
}
return 0;
}


#include <bits/stdc++.h>
using namespace std;
int a[10010];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int count=0;
for(int i=1;i<=n;i++)
{
if(a[i]!=i)
{
for(int j=i+1;j<=n;j++)
{
if(i==a[j])
{
count++;
swap(a[i],a[j]);
}
}
}
}
//for(int i=1;i<=n;i++)cout<<a[i];
cout<<count;
return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=210;

char a[N][N];
int dist[N][N];
void bfs(PII start)
{
queue<PII> q;
q.push(start);
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
while(!q.empty())
{
PII u=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=u.x+dx[i],y=u.y+dy[i];
if(a[x][y]=='#')continue;
if(a[x][y]=='.')
{

dist[x][y]=dist[u.x][u.y]+1;
a[x][y]='#';
q.push({x,y});
}
if(a[x][y]=='E')
{
cout<<dist[u.x][u.y]+1<<endl;
return;
}
}
}
cout<<"oop!"<<endl;
}
int main(){
int t;
cin>>t;
while(t--)
{
memset(a,'#',sizeof a);
memset(dist,0,sizeof dist);
int r,c;
cin>>r>>c;
PII start;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
cin>>a[i][j];
if(a[i][j]=='S')
start.x=i,start.y=j;
}
bfs(start);
}
return 0;
}


#include <bits/stdc++.h>
#define ts first
#define id second
using namespace std;
const int N=100010;
bool st[N];
int cnt[N];
pair<int,int> tz[N];

int main(){
int n,d,k;
cin>>n>>d>>k;
for(int i=0;i<n;i++)
{
scanf("%d%d",&tz[i].ts,&tz[i].id);
}
sort(tz,tz+n);
for(int i=0,j=0;i<n;i++)
{
int id=tz[i].id;
cnt[id]++;
while(tz[i].ts-tz[j].ts>=d){
cnt[tz[j].id]--;
j++;
}
if(cnt[id]>=k)st[id]=true;
}
for(int i=0;i<=N;i++)
if(st[i])cout<<i<<endl;
return 0;
}


#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int w[N];
struct Node{
int l,r;
int maxv;
}tr[N*4];
void build(int u,int l,int r)
{
if(l==r)tr[u]={l,r,w[r]};
else {
tr[u]={l,r};
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);
}
}
int query(int u,int l,int r)
{
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].maxv;
int mid=(tr[u].l+tr[u].r)>>1;
int maxv=INT_MIN;
if(mid>=l)maxv=query(u<<1,l,r);
if(mid+1<=r)maxv=max(maxv,query(u<<1|1,l,r));
return maxv;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
build(1,1,n);
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",query(1,x,y));
}
return 0;
}


#include <bits/stdc++.h>
using namespace std;
const int N=32010;
int tr[N],lever[N];
int lowbit(int x)
{
return x & -x;
}
{
for(int i=x;i<=N;i+=lowbit(i))tr[i]+=v;
}
int query(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i))res+=tr[i];
return res;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
x++;
lever[query(x)]++;