2021-3-29 【PTA】【天梯赛】【25分】_2021pta团队比赛-程序员宅基地
技术标签： PTA
每日三百行代码 第二十四天
#include<bits/stdc++.h>
using namespace std;
const int maxn = 30;
int a[maxn + 10], b[maxn + 10];
map<int, int>L, R;
int build(int la, int ra, int lb, int rb) {
if (la > ra)
return 0;
int root = a[ra];
int i;
for (i = lb; i <= rb && b[i] != root; i++) {
;}
if (i <= rb) {
R[root] = build(ra - rb + i, ra - 1, i + 1, rb);
L[root] = build(la, ra - rb + i - 1, lb, i - 1);
}
return root;
}
void bfs(int root) {
queue<int> Q;
Q.push(root);
int cnt = 0;
while (!Q.empty()) {
int tn = Q.front();
Q.pop();
printf(cnt++ == 0 ? "%d" : " %d", tn);
if (L[tn])
Q.push(L[tn]);
if (R[tn])
Q.push(R[tn]);
}
puts("");
}
int main() {
int N;
scanf("%d", &N);
for (int i = 1; i <= N; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= N; i++)
scanf("%d", &b[i]);
int root = build(1, N, 1, N);
bfs(root);
return 0;
}
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
Node* lc, * rc;
};
Node* buildTree(int* post, int* in, int n) {
if (n == 0)
return NULL;
int* mid = in;
while (*(post + n - 1) != *mid)mid++;
Node* T = new Node;
T->data = *mid;
int m = mid - in;
T->lc = buildTree(post, in, m);
T->rc = buildTree(post + m, mid + 1, n - 1 - m);
return T;
}
int main() {
queue<Node*>q;
int N, post[30], in[30], vis[30];
cin >> N;
for (int i = 0; i < N; ++i)
cin >> post[i];
for (int i = 0; i < N; ++i)
cin >> in[i];
q.push(buildTree(post, in, N));
int i = 0;
while (!q.empty()) {
cout << (i++ ? " " : "") << q.front()->data;
if (q.front()->lc)q.push(q.front()->lc);
if (q.front()->rc)q.push(q.front()->rc);
q.pop();
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct node{
int upset,squ,cnt;
node(){
cnt = 1;
upset = 0;
squ = 0;
}
}s[10005];
struct GG{
double cnt,upset,squ;
int id;
};
int pre[10005];
bool flag[10005]; //刚开始不都是false 如果有出现就true
int find(int x){
if( x == pre[x])
return x;
return pre[x] = find(pre[x]);
}
void merge(int x, int y){
int fx = find(x);
int fy = find(y);
if(fx > fy)
pre[fx] = fy;
else if(fx < fy)
pre[fy] = fx;
return;
}
bool cmp(GG a, GG b){
if(a.squ != b.squ)
return a.squ > b.squ;
else
return a.id < b.id;
}
int main(){
int n;
scanf("%d", &n);
for(int i = 1; i <= 10000; i ++)
pre[i] = i;
int me, fa, mo, cnt, child;
for(int i = 1; i <= n; i ++)
{
scanf("%d %d %d",&me,&fa,&mo);
flag[me] = true;
if(fa != -1)
{
merge(me, fa);
flag[fa] = true;
}
if(mo != -1)
{
merge(me, mo);
flag[mo] = true;
}
scanf("%d",&cnt);
for(int j = 1; j <= cnt; j ++ )
{
scanf("%d",&child);
merge(child, me);
flag[child] = true;
}
scanf("%d %d",&s[me].upset, &s[me].squ);
}
set<int>st;
for(int i = 10000; i >= 0; i--) //这边wa了第四个测试点因为0---10000 我写成1----10000
{
if(flag[i] == true)
{
int x = find(i);//找到它的祖先
st.insert(x);
if(x != i)
{
s[x].cnt += s[i].cnt;
s[x].squ += s[i].squ;
s[x].upset += s[i].upset;
}
}
}
set<int>::iterator it = st.begin();
vector<GG>vec;
while(it!=st.end())
{
GG gg;
gg.id = *it;
gg.cnt = s[*it].cnt;
gg.squ =s[*it].squ * 1.0 / s[*it].cnt * 1.0;
gg.upset = s[*it].upset * 1.0 / s[*it].cnt * 1.0;
vec.push_back(gg);
it++;
}
sort(vec.begin(),vec.end(),cmp);
printf("%d\n",vec.size());
for(int i = 0 ; i < vec.size(); i++)
printf("%04d %.0lf %.3lf %.3lf\n",vec[i].id, vec[i].cnt,vec[i].upset, vec[i].squ);
return 0;
}
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = 1e5 + 10;
struct node {
int id, houses;
double area;
};
struct family {
int id, members;
double ave_houses, ave_area;
};
bool cmp(const family &a, const family &b) {
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<bits/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++;
while(t>1&&(a[t/2]>a[t])) //大小不超过堆顶并且存在要换值的情况
{
a[t]=a[t/2]; //底部和顶部的值交换
a[t/2]=x; //底部和顶部的值交换
t=t/2; //继续向顶部迭代
}
a[t]=x; //最后将x填入顶部
}
int main()
{
int n,m,x,y;
string s;
while(cin>>n>>m)
{
cnt=1;
for(int i=0;i<n;i++)
{
cin>>x;
build(x); //加入小顶堆
}
map<int,int>mp;
for(int i=1;i<=n;i++) mp[a[i]]=i; //通过map将数值和它在堆中的位置对应起来
for(int i=0;i<m;i++)
{
cin>>x>>s;
if(s[0]=='a') //x和y是兄弟结点
{
cin>>y; cin>>s; cin>>s;
if(mp[x]/2==mp[y]/2) cout<<"T"<<endl;
else cout<<"F"<<endl;
}
else
{
cin>>s;
if(s[0]=='a') //x是y的一个子结点
{
cin>>s; cin>>s; cin>>y;
if(mp[x]/2==mp[y]) cout<<"T"<<endl;
else cout<<"F"<<endl;
}
else
{
cin>>s;
if(s[0]=='r') //x是根结点
{
if(mp[x]==1) cout<<"T"<<endl;
else cout<<"F"<<endl;
}
else //x是y的父结点
{
cin>>s>>y;
if(mp[x]==mp[y]/2) cout<<"T"<<endl;
else cout<<"F"<<endl;
}
}
}
}
}
return 0;
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
智能推荐
docker删除重装，以及极其重要的/etc/docker/key.json文件-程序员宅基地
文章浏览阅读8.9k次，点赞2次，收藏2次。先说以下我为何要删除docker的原因吧：因为我感觉Docker Hub有点慢，就配置了阿里云的镜像加速器，可是按阿里云的官方配置完后我怎么感觉它更慢了，对比昨天配置阿里的maven镜像仓库后快到起飞的速度，我认为是此次配置没有生效。多次确认新加入的/etc/docker/demon.json文件无误后又多次systemctl了未果，随即我怀疑阿里给出的以下方案中的“修改”的/etc/dock...
空间物理——概述_空间物理概论-程序员宅基地
文章浏览阅读1.9k次，点赞3次，收藏4次。文章目录空间物理的研究对象太阳风能量向地球传输的三种方式和所需要的时间太阳内部结构、太阳活动太阳内部结构太阳活动太阳风速度从太阳表面到地球轨道附近变化参考空间物理的研究对象大气层：10KM以上，分成平流层、中层、低热层、热层、逃逸层电离层：60-90KM以上，一直到1000KM左右，部分电离气体，中性成风碰撞的影响不可忽略地球磁层：完全电离的气体，1000KM以上，可忽略碰撞，有太阳风和..._空间物理概论
BQ4050学习笔记（二）-程序员宅基地
文章浏览阅读2.9k次，点赞5次，收藏25次。BQ4050学习笔记（二）永久失效：如果发⽣严重故障，该设备可以永久禁⽤电池组。永久故障检查（IFC 和 DFW 除外）可以通过设置Settings:Enabled PFA、 Settings:Enabled PF B、 Settings:Enabled PF C 和Settings:Enabled PF D 中的相应位单独启⽤或禁⽤。所有永久在设置ManufacturingStatus()[PF]之前，故障检查（IFC 和 DFW 除外）被禁⽤。当任何PFStatus()位置位时，器件进⼊ PER_bq4050
SpringCloudAlibaba-Nacos注册中心的使用_spring-cloud-alibaba 使用nacos 2.1版本-程序员宅基地
文章浏览阅读152次。第二步：填写配置文件参数，这里定义了一个名字为application-user-dev.yaml的配置，使用的是YAML格式。DataID : 非常重要，可以看做是配置的文件的名字，在程序中拉取配置文件的时候需要指定Data ID。如果不使用默认的public命名空间，那么需要指定namespace配置为要使用的命名空间的Id值。第一步：打开Nacos监控面板，进入配置列表，新增一个user服务的配置文件。进入配置列表 ，切换到新建立的命名空间，创建配置文件。修改Nacos，添加命名空间。_spring-cloud-alibaba 使用nacos 2.1版本
CVE-2023-21716 Microsoft Word远程代码执行漏洞Poc_cve-2023-21716复现-程序员宅基地
文章浏览阅读293次。受害者打开python代码生成的RTF文件，RTF解析器解析恶意代码，触发堆溢出，Microsoft Word会闪退，用户其它Word中未保存的内容会丢失。_cve-2023-21716复现
c语言程序设计让a变成A,c语言程序设计a期末模拟试题.docx-程序员宅基地
文章浏览阅读451次。文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208]文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208]C语言程序设计A期末模拟试题C语言程序设计A期末模拟试题一一、单项选择题(每小题2分，共20分)由C++目标文件连接而成的可执行文件的缺省扩展名为( )。A. cpp B. exe C. obj D. li..._c语言如何将a转换成a
随便推点
利用beef和msf实现session远程命令_msf如何切换一个session-程序员宅基地
文章浏览阅读534次。笔记beef启动 beef 的方法msfbeef工具目录 /usr/share/beef-xss配置文件 config.yaml启动 beef 的方法1.beef-xss2./usr/share/beef-xss/beef(使用前需要修改默认的用户名称和密码)Web 管理界面 http://127.0.0.1:3000/ui/panelShellcode http://127.0.0.1:3000/hook.js测试页面 http://127.0.0.1:3000/demos/butch_msf如何切换一个session
python判断丑数_丑数问题及变种小结-程序员宅基地
文章浏览阅读503次。丑数问题及变种小结声明1 判断丑数因子只包含2,3,5的数称为丑数(Ugly Number)，习惯上把1当作第一个丑数面试lintcode 517 ugly numbersegmentfault剑指offer 面试题34 丑数数组解法：参考剑指offer，将待判断目标依次连续整除2，3，5，若是最后获得1，证实该数为丑数；优化/*** 依次整除2，3，5判断(2，3，5顺序判断时间最优)* htt..._编写python来证明一个数是丑数
python自动化测试实战 —— WebDriver API的使用_python webdriver api-程序员宅基地
文章浏览阅读1.9k次，点赞30次，收藏11次。Selenium 简介： WebDriver是Selenium Tool套件中最重要的组件。Selenium 2.0之后已经将Selenium和WebDriver进行合并，作为一个更简单、简洁、有利于维护的API提供给测试人员使用。 它提供了一套标准的接口，可以用多种编程语言调用，并且和浏览器进行交互。 WebDriver可以对浏览器进行控制，包括输入URL，点击按钮，填写表单，滚动页面，甚至是执行JavaScript代码。同时，它也能够获取网页中的信息，如文本，标签，属_python webdriver api
Nodejs crypto模块公钥加密私钥解密探索_crypto.publicencrypt-程序员宅基地
文章浏览阅读1w次。１．什么是公钥加密私钥解密 简单一点来说一般加密解密都用的是同一个秘钥或者根本不用，而这里采用的是加密用一个秘钥，解密用另一个秘钥且能解密成功．这就属于不对称加密解密算法的一种了．２．公钥秘钥的生成 由于这种加密方案，公钥秘钥是成对的，所以需要一些工具生成 利用 openssl 生成公钥私钥 生成公钥： openssl genrsa -out rsa_private_key...._crypto.publicencrypt
Maven简明教程（5）---依赖关系（实例篇）_依赖关系怎么写-程序员宅基地
文章浏览阅读1.7k次。[工欲善其事，必先利其器]上文中，我们简单介绍了依赖关系的基本理论与配置方式。但是由于这个知识点在我们日后的开发过程中会经常使用到，因此，我们在本篇中通过演示实例来说明依赖关系，请各位看官一定跟着步骤，亲自尝试一番。仔细观察通过这种方式对我们程序架构造成的影响。特别的，这里以一份已经调试完成的工程为例，因此，与前文说的工程命名不一致，敬请谅解。准备工作：a.操作系统：win7 x6_依赖关系怎么写
2017多校联合第五场1006/hdu6090Rikka with Graph（思维公式）-程序员宅基地
文章浏览阅读343次。Rikka with GraphTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 592 Accepted Submission(s): 353Problem DescriptionAs we know,