1.完全二叉树的权值

暴力去解就行了

#include 
using namespace std;
const int N=1e5+10;
int a[N];
long long mx=-0x3f3f3f3f;
int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int depth=0;for(int i=1,d=1;i<=n;i*=2,d++){long long sm=0;for(int j=i;jmx){depth=d;mx=sm;}}cout<

2.地牢大师

三维数组的bfs

#include 
using namespace std;
const int N=110;
struct node
{int x,y,z;
};
char g[N][N][N];
int dist[N][N][N];
int dx[]={1,-1,0,0,0,0},dy[]={0,0,1,-1,0,0},dz[]={0,0,0,0,1,-1};
int l,r,c;
int sx,sy,sz;
int ex,ey,ez;
int bfs()
{queue q;q.push({sx,sy,sz});dist[sx][sy][sz]=0;while(q.size()){node t=q.front();q.pop();for(int i=0;i<6;i++){int x=t.x+dx[i];int y=t.y+dy[i];int z=t.z+dz[i];// cout<l||y<1||y>r||z<1||z>c)continue;//printf("%d\n",dist[x][y][z]!=-1||g[x][y][z]=='#');if(dist[x][y][z]!=-1||g[x][y][z]=='#')continue;q.push({x,y,z});dist[x][y][z]=dist[t.x][t.y][t.z]+1;if(g[x][y][z]=='E')return dist[x][y][z];}}return -1;}
int main()
{while(cin>>l>>r>>c){if(l==0&&r==0&&c==0)break;memset(g,0,sizeof g);memset(dist,-1,sizeof dist);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')sx=i,sy=j,sz=k;if(g[i][j][k]=='E')ex=i,ey=j,ez=k;}int cnt=bfs();if(cnt==-1){puts("Trapped!");}else{printf("Escaped in %d minute(s).\n",cnt);}}return 0;
}

3.全球变暖

这个就是找连通块个数 找连通块个数的话就是bfs就可以做的 但是他需要找有没有任意一个#是被其他#包起来的，那么只需要找到某个点上下左右都没有 . 就行了 这样的话就找出来不会被淹没的岛，反过来就是找被淹没的岛

找到每个连通块中的元素数目和临近海边的元素数目，若二者相等，则：此连通块会被淹没

#include 
using namespace std;
typedef pair PII;
const int N=1010;
char g[N][N];
bool st[N][N];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int n;
int res;
int bfs(int x,int y)
{int a=0;int b=0;queue q;st[x][y]=true;q.push({x,y});while(q.size()){auto t=q.front();q.pop();a++;bool fl=true;for(int i=0;i<4;i++){int x1=t.first+dx[i],y1=t.second+dy[i];if(x1<0||x1>=n||y1<0||y1>=n||st[x1][y1])continue;if(g[x1][y1]=='.'){fl=false;continue;}q.push({x1,y1});st[x1][y1]=true;}if(!fl) b++;}return a==b;
}
int main()
{cin>>n;for(int i=0;i>g[i];for(int i=0;i

4.大臣的旅费

求树的直径

#include 
#include 
#include 
#include using namespace std;typedef long long LL;
const int N = 1E5 + 10, M = 2 * N;int n;
int h[M], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void dfs(int u, int father, int distance) {dist[u] = distance;for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (j != father) dfs(j, u, distance + w[i]);}
}int main() {scanf("%d", &n);memset(h, -1, sizeof h);for (int i = 0; i < n; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c);}dfs(1, -1, 0);int maxidx = 0, maxdist = 0;for (int i = 1; i <= n; i++) {if (dist[i] > maxdist) {maxdist = dist[i];maxidx = i;}}memset(dist, 0, sizeof dist);dfs(maxidx, -1, 0);maxdist = 0;for (int i = 1; i <= n; i++) {maxdist = max(dist[i], maxdist);}printf("%lld\n", (LL) maxdist * 10 + (LL) maxdist * (maxdist + 1) / 2);return 0;
}

5.股票买卖2

贪心就可以做了 在把所有上升区间都加上就是ans

#include 
using namespace std;
const int N=1e5+10;
int a[N];
int n;
int main()
{int res=0;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=2;i<=n;i++)if(a[i]-a[i-1]>0)res+=a[i]-a[i-1];cout<

6.货仓选址

很经典的题，点去取中位数的点就行了

#include 
using namespace std;
const int N=100100;
int a[N],n,i,ans,sum;
int main()
{cin>>n;for (i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);//排序int sum=a[n/2+1];//中位数for (i=1;i<=n;i++)ans=ans+abs(a[i]-sum);//统计和中位数之间的差cout<

7.糖果传递

上面那题的扩展

#include
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n;
int a[N];
ll s[N],c[N];
ll trans(int n,int a[])
{for(int i=1;i<=n;i++) s[i]=s[i-1]+(ll)a[i];//求前缀和后面用if(s[n]%n) return -1;//假如不能均分ll avg=s[n]/n;//平均数c[1]=0;//第一个是0for(int i=2;i<=n;i++) c[i]=s[i-1]-(ll)(i-1)*avg;//图片上有说sort(c+1,c+n+1);//排个序ll res=0;ll cavg;//中位数cavg=c[n/2+1];//奇数直接就是中间那个 偶数在中间前面和中间后面的区间都可以for(int i=1;i<=n;i++) res+=abs(c[i]-cavg);//答案就是每个数减去中位数return res;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);ll t=trans(n,a);//将a进行转换printf("%lld\n",t);return 0;
}