2021-3-29 【PTA】

if (a.ave_area != b.ave_area) return a.ave_area > b.ave_area;

return a.id < b.id;

}

int pre[maxn];

int find(int x) {

return x == pre[x] ? x : pre[x] = find(pre[x]);

}

int union0(int x, int y) {

int fx = find(x), fy = find(y);

if (fx != fy) {

pre[fx] = fy;

return 1;

}

return 0;

}

int main() {

for (int i = 0; i < maxn; i++) pre[i] = i;

set<int> v;

map<int, node> nodes;

int n;

cin >> n;

while (n--) {

int id, p1, p2, k, houses;

double area;

cin >> id >> p1 >> p2 >> k;

v.insert(id);

if (p1 != -1) {

v.insert(p1);

union0(p1, id);

}

if (p2 != -1) {

v.insert(p2);

union0(p2, id);

}

while (k--) {

int id1;

cin >> id1;

v.insert(id1);

union0(id1, id);

}

cin >> houses >> area;

nodes[id] = node{id, houses, area};

}

set<int> sset;

map<int, vector<int> > mmap;

for (auto it = v.begin(); it != v.end(); it++) {

int fa = find(*it);

mmap[fa].push_back(*it);

sset.insert(fa);

}

cout << sset.size() << endl;

vector<family> families;

for (auto it = sset.begin(); it != sset.end(); it++) {

int fa = find(*it), sz = mmap[fa].size();

double hs = 0, area = 0;

for (int i = 0; i < sz; i++) {

hs += nodes[mmap[fa][i]].houses;

area += nodes[mmap[fa][i]].area;

}

families.push_back(family{mmap[fa][0], sz, hs / sz, area / sz});

}

sort(families.begin(), families.end(), cmp);

for (int i = 0; i < families.size(); i++) {

printf("%04d %d %.3lf %.3lf", families[i].id, families[i].members, families[i].ave_houses, families[i].ave_area);

if (i < families.size() - 1) puts("");

}

return 0;

}

#include<bits/stdc++.h>

using namespace std;

string s;

int main()

{

getline(cin,s);

int ans=-1;

for(int i=0;i<s.size();i++)

{

for(int j=s.size()-1;j>=i;j--)

{

int l=i,r=j;

while(s[l]==s[r] && l<=r)

{

l++;

r--;

}

if(l>r)

{

ans=max(ans,j-i+1);

}

}

}

cout<<ans;

return 0;

}

#include<bits/stdc++.h>

using namespace std;

#define ll long long

string s;

char p[5000];

int len[5000];

void init()

{

p[0]='@';

int l=s.length();

for(int i=1;i<=l*2;i+=2)

{

p[i]='#';p[i+1]=s[i/2];

}

p[l*2+1]='#';

p[l*2+2]='!';

}

int main()

{

ios::sync_with_stdio(false);

getline(cin,s);

init();

int po=0,mx=0,maxn=0,l;//po 最长子串的中心点，mx 最长子串的右端点

l=strlen(p);

for(int i=1;i<=l;i++)

{

if(i<mx) len[i]=min(len[2*po-i],mx-i);

else len[i]=1;

while(p[i-len[i]]==p[i+len[i]]) //中心扩展

len[i]++;

if(i+len[i]>mx)//更新

{

mx=i+len[i];po=i;

}

maxn=max(maxn,len[i]);

}

cout<<maxn-1;//子串长度为 len[i]-1

return 0;

}

#include<bit 《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 s/stdc++.h>

using namespace std;

struct T{

int id;//存储 id

int money;//钱数

int sumHb;//红包个数

};

auto cmp=[](T &e1,T &e2){//用来排序的规则

return tie(e2.money,e2.sumHb,e1.id)<tie(e1.money,e1.sumHb,e2.id);

};

int main(){

int N;

cin>>N;

map<int,int>val;

map<int,int>hb;

vector<int>flag;

for(int i=1;i<=N;i++){

int num,sum=0;

cin>>num;

for(int j=1;j<=num;j++){

int id,mon;

cin>>id>>mon;

if(count(flag.begin(),flag.end(),id)==0){//用来判断 id 有没有重复抢红包

sum+=mon;//用来统计编号 i 发放的红包总额

val[id]+=mon;//抢到红包的人 增加其金钱总额

hb[id]++;//存放编号 i 发放的红包个数

flag.push_back(id);

}

}

val[i]-=sum;//从编号 i 已有的金钱数减去发放红包的钱数

flag.clear();//清空容器

}

vector<T>ss;//存放编号 id 收入金额 红包个数

for(auto item : val){

ss.push_back({item.first,item.second,hb[item.first]});

}

sort(ss.begin(),ss.end(),cmp);//排序

for(int i=0;i<ss.size();i++){

printf("%d %.2f",ss[i].id,(ss[i].money*1.0)/100);

if(i+1!=ss.size())

cout<<endl;

}

return 0;

}

#include<cstdio>//C++头文件的标准写法;

#include<iostream>

using namespace std;

#include<algorithm>//包含了 sort 函数;

struct node

{

int id;//人的编号;

int num;//人抢到红包的个数;

int value;//抢到红包的金额;

}person[10000];

bool f(struct node a,struct node b)

{

if(a.value!=b.value)//如果金额没有并列,则按照总金额从达到小的顺序递减输出;

{

return a.value>b.value;

}

else if(a.num != b.num)//金额有并列，则按照抢到红包的个数递减输出;

{

return a.num>b.num;

}

else if(a.id != b.id)//如果金额和抢到红包的个数都有并列,则按照人的编号递增输出;

{

return a.id<b.id;

}

}

int main()

{

int n,k,p,i,j,sum=0,n1;//k 指的是抢到红包的个数,n 指的是抢红包人的编号,p 指的是抢到红包的金额;

cin>>n;

for(i=1;i<=n;i++)

{

person[i].id = i;//编号是 i 的人对应的 id 值是 i;

cin>>k;

sum=0;

for(j=1;j<=k;j++)

{

cin>>n1>>p;

// person[n1].id = n1;易错点，因为你不知道每个人都抢了红包,当有的人没有抢，那么对应的 id 值就变成了 0;

person[n1].value = person[n1].value + p;//记录抢到红包的金额;

person[n1].num ++;//记录抢到红包的个数;

sum = sum + p;//记录第 i 个人发红包的总金额;

}

person[i].value = person[i].value - sum;//更新编号为 i 的人剩余的总金额;

}

//因为人的编号 n 是正整数,故需要将 person 加 1;

//person+n+1 包含的范围是 person+n，不包括那个 1;

//[person+1,person+n+1)---->[1,n]

sort(person+1,person+n+1,f);//自动调用 f()函数,包含在头文件 ----> #include<algorithm>

for(i=1;i<=n;i++)

{

//抢到红包的进金额是按照分这个单位来计算的,故需要在输出是转换成元;

printf("%d %.2lf\n",person[i].id,person[i].value*1.0/100);

}

}

#include<iostream>

using namespace std;

int relative[101][101];

int fa[101];

int find(int x) {

return fa[x] == x ? x : find(fa[x]);

}

void unin(int x, int y) {

int a = find(x), b = find(y);

fa[b] = a;

return;

}

int main() {

for (int i = 0; i < 101; i++) {

fa[i] = i;

}

int N, M, K;

cin >> N >> M >> K;

for (int i = 0; i < M; i++) {

int x, y, edge;

cin >> x >> y >> edge;

if (edge == 1)

unin(x, y);

else {

relative[x][y] = -1;

relative[y][x] = -1;

}

}

for (int i = 0; i < K; i++) {

int x, y;

cin >> x >> y;

if (find(x) == find(y) && relative[x][y] != -1)

cout << "No problem"<<endl;

else if (find(x) != find(y) && relative[x][y] != -1)

cout << "OK"<<endl;

else if (find(x) == find(y) && relative[x][y] == -1)

cout << "OK but..."<<endl;

else

cout << "No way"<<endl;

}

return 0;

}

#include<iostream>

#include<queue>

#include<vector>

using namespace std;

int pre[35];

int in[35];

typedef struct node* bintree;

queue<bintree> q;

struct node{

bintree left;

bintree right;

int data;

};

bintree huanyuan(int prel,int prer,int inl,int inr)

{

if(prel>prer)return NULL;

bintree bt=new node;

bt->data=pre[prel];

int k;

for(int i=inl;i<=inr;i++)

{

if(in[i]==pre[prel])

{

k=i;

break;

}

}

bt->right=huanyuan(prel+1,prel+k-inl,inl,k-1);

bt->left=huanyuan(prel+k-inl+1,prer,k+1,inr);

return bt;

}

void layeror(bintree bt,vector<int> &vec)

{

if(bt==NULL)return;

q.push(bt);

while(!q.empty())

{

vec.push_back(q.front()->data);

bintree t=q.front();

q.pop();

if(t->left)q.push(t->left);

if(t->right)q.push(t->right);

}

}

int main()

{

int n;

cin>>n;

for(int i=0;i<n;i++)

{

cin>>in[i];

}

for(int i=0;i<n;i++)

{

cin>>pre[i];

}

bintree bt=huanyuan(0,n-1,0,n-1);

vector<int> vec;

layeror(bt,vec);

for(int i=0;i<vec.size();i++)

{

cout<<vec[i];

if(i!=vec.size()-1)

cout<<' ';

}

}

#include<bits/stdc++.h>

using namespace std;

int n,cnt;

vector<int>in,pre,level(1000000,-1);

void levelorder(int root,int start,int end,int index)

{

if(start>end) return ;

int i=start;

while(i<end&&pre[root]!=in[i]) i++;

level[index]=pre[root];

levelorder(root+1,start,i-1,2*index+2);

levelorder(root+1+i-start,i+1,end,2*index+1);

}

int main()

{

cin>>n;

in.resize(n); pre.resize(n);

for(int i=0;i<n;i++) cin>>in[i];

for(int i=0;i<n;i++) cin>>pre[i];

levelorder(0,0,n-1,0);

for(int i=0;i<1000000;i++)

{

if(level[i]==-1) continue;

cnt++;

if(i) cout<<" ";

cout<<level[i];

if(cnt==n) break;

}

}

#include <bits/stdc++.h>

using namespace std;

int cnt;

int a[1005];

void build(int x) //建堆操作

{

int t=cnt;//cnt 是全局变量，所以 t 并不是每次都是 0

a[cnt]=x; //将值加入堆的底部

cnt++;