【CCCC】PAT : 团体程序设计天梯赛-练习集 L3 答案
顶着满课，整整一星期，终于咕完了。（；´д｀）ゞ
知识点分类（23）：
1、搜索模拟（5）：BFS，DFS，最短路，路径打印
2、计算几何（5）：找规律，斜率计算，极角排序，三角形面积，三点共线，凸包
3、数据结构（5）：栈，并查集，二叉树，堆，线段树
4、图论模板（4）：Dijkstra，Floyd
4、零零碎碎（4）：数学（1）+物理（1）+DP（2）
Codes
L3-001
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;//RE3,4
const int maxm = 110;
int v[maxn], dp[maxm], pre[maxn][maxm];
bool cmp(int a, int b){return a>b;}
int main(){
int n, m;
cin>>n>>m;
for(int i = 1; i <= n; i++)
cin>>v[i];
sort(v+1,v+n+1,cmp);//结论：降序排序=最小字典序
for(int i = 1; i <= n; i++){
for(int j = m; j >= v[i]; j--){
if(dp[j]<=dp[j-v[i]]+v[i]){
dp[j]=dp[j-v[i]]+v[i]; //选择的代价为v[i],价值为v[i]
pre[i][j] = 1;//选择了硬币i，标记当前背包位置，记录路径
}
}
}
if(dp[m]!=m){//容量为m（面额）的背包能获得的最大价值为m。。
cout<<"No Solution"<<endl;
return 0;
}
//路径打印
int ok = 0;
for(int i=n, j=m; i>=1 && j>=0; i--){//注意顺序必须是逆序，和前面相反
if(pre[i][j]){
if(!ok){cout<<v[i];ok=1;}
else cout<<" "<<v[i];
j -= v[i];//当第i个硬币选中，剩余价值-=vi[i]；
}
}
return 0;
}
L3-002
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
stack<int>stk;
//multiset<int>se;
vector<int>order;
int main(){
//freopen("ans.cpp","r",stdin);
int T; cin>>T;
while(T--){
string s; cin>>s;
int re = 0;
if(s=="Push"){
int x; cin>>x;
stk.push(x);
order.insert(lower_bound(order.begin(), order.end(), stk.top()), stk.top());
}
if(s=="Pop"){
if(stk.size()){
cout<<stk.top()<<"\n";
order.erase(lower_bound(order.begin(), order.end(), stk.top()));
stk.pop();
}else{
re = 1;
}
}
if(s=="PeekMedian"){
if(stk.size()){
//cout<<stk.size()<<" ";
cout<<order[(stk.size()-1)/2]<<endl;
}else{
re = 1;
}
}
if(re)cout<<"Invalid\n";
}
return 0;
}
L3-003
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
vector<int>man[maxn];
bool cmp(pair<int,int> a, pair<int,int> b){return a.second>b.second;}
int fa[maxn+10];
void init(int n){for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int main(){
int n; cin>>n;
init(maxn);
for(int i = 1; i <= n; i++){
int k; scanf("%d:",&k);
int x; cin>>x;
man[i].push_back(x);
for(int j = 2; j <= k; j++){
int xx; cin>>xx;
merge(x,xx);
man[i].push_back(xx);
}
}
map<int,int>ma;
for(int i = 1; i <= n; i++){
ma[find(man[i][0])]++;
}
vector<pair<int,int> >vec(ma.begin(),ma.end());
sort(vec.begin(),vec.end(),cmp);
cout<<vec.size()<<endl;
for(int i = 0; i < vec.size()-1; i++)
cout<<vec[i].second<<" ";
cout<<vec[vec.size()-1].second;
/*
map<int,int>::reverse_iterator it = ma.rbegin();
cout<<(it->second); it++;
for( ; it != ma.rend(); it++)
cout<<" "<<(it->second);
*/
return 0;
}
L3-004
#include<bits/stdc++.h>
using namespace std;
int n, m, l, t, a[61][129][1287];
int ans = 0;
struct xyz{int x, y, z;};
int dx[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int check(int x, int y, int z){if(x<0||y<0||z<0||x>=l||y>=n||z>=m)return 0;return 1;}
void bfs(int x, int y, int z){
queue<xyz>q;
q.push(xyz{x,y,z});
a[x][y][z] = 0;
int sum = 1;
while(q.size()){
xyz k = q.front(); q.pop();
for(int i = 0; i < 6; i++){
xyz kk = k;//kk!=k,WA3,6,这TM也能过样例？！
kk.x += dx[i][0];
kk.y += dx[i][1];
kk.z += dx[i][2];
if(check(kk.x,kk.y,kk.z) && a[kk.x][kk.y][kk.z]){
a[kk.x][kk.y][kk.z] = 0;
sum++;
q.push(kk);
}
}
}
if(sum>=t)ans += sum;
}
int main(){
cin>>n>>m>>l>>t;
for(int k = 0; k < l; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin>>a[k][i][j];
for(int k = 0; k < l; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(a[k][i][j])bfs(k,i,j);
cout<<ans<<endl;
return 0;
}
L3-005
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1050;//RE6?
int n, m, k, ds;
struct lajitong{
string id;
double minds, aveds;
bool operator < (const lajitong &b){
if(minds != b.minds)return minds>b.minds;
if(aveds != b.aveds)return aveds<b.aveds;
return id < b.id;
}
};
int e[maxn][maxn], dist[maxn], vis[maxn];
void Dijkstra(int u){
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
dist[u] = 0;
for(int i = 1; i <= n+m; i++){
int v = -1, _min = (1e9);
for(int j = 1; j <= n+m; j++)
if(!vis[j] && dist[j]<_min)
{_min = dist[j]; v= j;}
if(v==-1)return ;
vis[v] = 1;
for(int j = 1; j <= n+m; j++){
if(!vis[j] && dist[j]>dist[v]+e[v][j]){//vis[jjjjjj],NotVVVVV
dist[j] = dist[v]+e[v][j];
}
}
}
}
int main(){
//input
cin>>n>>m>>k>>ds;
memset(e,0x3f,sizeof(e));
for(int i = 0; i < k; i++){
char a[10], b[10]; int c;
scanf("%s%s%d",a,b,&c);
int aa = (a[0]=='G' ? n+atoi(&a[1]) : atoi(a));
int bb = (b[0]=='G' ? n+atoi(&b[1]) : atoi(b));
e[aa][bb] = e[bb][aa] = c;
}
//对于每个垃圾桶，跑完dij后统计最短距离和平均距离
lajitong ans;
for(int i = 1; i <= m; i++){
Dijkstra(n+i);
double aveds = 0, minds = dist[1];
int flag = 1;
for(int j = 1; j <= n; j++){
aveds += dist[j];
minds = min(minds, dist[j]*1.0);
if(dist[j]>ds)flag = 0; //dist[jjjjjj],NotIIIIII
}
//更新答案
lajitong tmp = lajitong{"G"+to_string(i),minds,aveds/n};
//cout<<flag<<"\n";
if(flag && (ans.id.empty() || tmp<ans)){
ans = tmp;
}
}
if(ans.id.empty())
cout<<"No Solution"<<endl;
else
printf("%s\n%.1lf %.1lf", ans.id.c_str(), ans.minds, ans.aveds);
return 0;
}
L3-006
//超级注释版
#include<bits/stdc++.h>
using namespace std;
//1.分别存储两个图形的斜边(2个点)，顶点数，
vector<int> v[2], n;
//2.特判情况:四边形直角腰，矩形个数
vector<int>len; int flag;
//1.找到斜边
void deal(int id, vector<int>& x, vector<int>& y){
int sz = x.size(); set<int>st;
for(int i = 0; i < sz; i++){
//相邻点横纵坐标都不等：这两点构成斜边。
if(x[i]!=x[(i+1)%sz] && y[i]!=y[(i+1)%sz]){
st.insert(i); st.insert((i+1)%sz);
//如果是四边形：存储直角腰的长度
if(sz==4)len.push_back(abs(x[(i+2)%4]-x[(i+3)%4])+abs(y[(i+2)%4]-y[(i+3)%4]));
}
}
if(st.size()==0){//没有斜边，所以是矩形
//存下两条直角边
v[id].push_back(abs(x[2]-x[0]));
v[id].push_back(abs(y[2]-y[0]));
flag++; //矩形个数+1
}else{
//存储斜边(2个端点)
for(int i : st){
v[id].push_back(x[i]);
v[id].push_back(y[i]);
}
}
}
//2.情况判断
void solve(){
//最多也就三边形+五边形，超过8个点就错。
if(n[0]<=5 && n[1]<=5 && n[0]+n[1]<=8){
if(flag==2){//两个矩形
//只要矩形A(x,y)两条直接边有一条能和矩形B合上就行
int x=v[0][0],y=v[0][1],c=v[1][0],d=v[1][1];
if(x==c||x==d||y==c||y==d){cout<<"YES\n";return;}
}
if(flag==0){//没有矩形
//如果没有斜边，不成立
if(v[0].size()==4 && v[1].size()==4){
//特判直角腰
if(n[0]==4&&n[1]==4&&len[0]!=len[1]){cout<<"NO\n";return;}
//存下两条直角边(斜边分别做垂直的直角三角形)
int x=abs(v[0][2]-v[0][0]),y=abs(v[0][3]-v[0][1]); if(x>y) swap(x,y);
int c=abs(v[1][2]-v[1][0]),d=abs(v[1][3]-v[1][1]); if(c>d) swap(c,d);
//当且仅当直角边都相等，斜边相等
if(x==c&&y==d){cout<<"YES\n";return;}
}
}
//一个矩形的情况不存在
}
cout<<"NO\n";
}
int main(){
int T; cin>>T;
while(T--){
//1. 变量全部初始化
flag = 0; n.clear(); len.clear();
v[0].clear(); v[1].clear();
//2. 输入两个多边形
for(int i = 0; i < 2; i++){
int k; cin>>k; n.push_back(k);
vector<int>x(k), y(k);
for(int j = 0; j < k; j++)cin>>x[j]>>y[j];
//2.1 找到斜边
deal(i,x,y);
}
//3. 结论判断
solve();
}
return 0;
}
L3-007
//AC
#include<bits/stdc++.h>
using namespace std;
const int maxn = 550;
int n, m, s, t;
int e[2][maxn][maxn], dist[2][maxn], vis[2][maxn], pre[2][maxn], w[2][maxn];
void Dijkstra(int rk){
memset(dist[rk],0x3f,sizeof(dist[rk]));
memset(vis[rk],0,sizeof(vis[rk]));
memset(pre[rk],-1,sizeof(pre[rk]));
dist[rk][s] = 0;
for(int i = 0; i < n; i++){
int u = -1, _min = 1e9;
for(int j = 0; j < n; j++){
if(!vis[rk][j] && dist[rk][j]<_min){
_min = dist[rk][j]; u = j;
}
}
if(u==-1)return ;
vis[rk][u] = 1;
for(int j = 0; j < n; j++){
if(!vis[rk][j] && dist[rk][j]>dist[rk][u]+e[rk][u][j]){
dist[rk][j] = dist[rk][u]+e[rk][u][j];
pre[rk][j] = u;
//距离
if(rk==0){
w[rk][j] = w[rk][u]+1;//+1?!!:WA4!!
}
//时间
if(rk==1){
w[rk][j] = w[rk][u]+e[!rk][u][j];//WA2!
}
}else if(!vis[rk][j] && dist[rk][j] == dist[rk][u]+e[rk][u][j]){
//距离
if(rk==0){
if(w[rk][j] > w[rk][u]+1){
w[rk][j] = w[rk][u]+1;
pre[rk][j] = u;
}
}
//时间
if(rk==1){
if(w[rk][j] > w[rk][u]+e[!rk][u][j]){
w[rk][j] = w[rk][u]+e[!rk][u][j];
pre[rk][j] = u;
}
}
}
}
}
}
void Print(int rk, int x){
if(x==-1){
return ;
}else{
Print(rk, pre[rk][x]);
printf(" %d =>", x);
}
}
int main(){
memset(e,0x3f,sizeof(e));
cin>>n>>m;
for(int i = 1; i <= m; i++){
int a, b, on, le, ti;
cin>>a>>b>>on>>le>>ti;
if(on==1){
e[0][a][b] = le;
e[1][a][b] = ti;
}else{
e[0][a][b] = le;
e[1][a][b] = ti;
e[0][b][a] = le;
e[1][b][a] = ti;
}
}
cin>>s>>t;
Dijkstra(0);
Dijkstra(1);
int ok = 1, i = pre[0][t], j = pre[1][t];
while(i!=-1 && j!=-1){
if(pre[0][i] != pre[0][j]){ok=0;break;}
i = pre[0][i];
j = pre[1][j];
}
if(ok){
printf("Time = %d;",dist[1][t]);
printf(" Distance = %d:",dist[0][t]);
Print(1,pre[1][t]);
printf(" %d\n",t);
return 0;
}
printf("Time = %d:",dist[1][t]);
Print(1,pre[1][t]);
printf(" %d\n",t);
printf("Distance = %d:",dist[0][t]);
Print(0,pre[0][t]);
printf(" %d",t);
return 0;
}
L3-008
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
vector<int>G[maxn];
int vis[maxn];
bool cmp(int a, int b){return a>b;}
int bfs(int x){
memset(vis,0,sizeof(vis));
int u = -1, val = 1e9;
queue<pair<int,int> >q;
q.push({x,1});
vis[x] = 1;
while(q.size()){
pair<int,int> t = q.front(); q.pop();
vis[t.first] = 1;
for(int i = 0; i < G[t.first].size(); i++){
sort(G[t.first].begin(),G[t.first].end(),cmp);//编号小的先输出
if(!vis[G[t.first][i]])q.push({G[t.first][i],t.second+1});
}
if(u==-1 || t.second>val){
val = t.second;
u = t.first;
}else if(t.second==val && t.first<u){
u = t.first;
}
}
return u;
}
int main(){
int n, m, k;
cin>>n>>m>>k;
for(int i = 1; i <= m; i++){
int a, b; cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
for(int i = 1; i <= k; i++){
int x; cin>>x;
if(G[x].size()==0)cout<<0<<endl;
else cout<<bfs(x)<<endl;
}
return 0;
}
L3-009
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+10;
LL x[maxn], y[maxn];
int stk[maxn], top;
set<int>se;
bool check(int a, int b, int c){//向量ab在ac下面(kab<kac)，b是凹点
return (x[c]-x[a])*(y[b]-y[a])<=(x[b]-x[a])*(y[c]-y[a]);
}
int main(){
ios::sync_with_stdio(false);
int n; cin>>n;
for(int i = 0; i < n; i++){
cin>>x[i]>>y[i];
if(top>=1){
while(top>=2 && check(i,stk[top-1],stk[top-2]))top--;//b是凹点不要它了
if(stk[top-1])se.insert(stk[top-1]);//找到凸点了入栈
}
stk[top++] = i;
}
cout<<se.size()<<endl;
return 0;
}
L3-010
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int Tree[maxn];
void update(int root, int val){
if(!Tree[root])
Tree[root] = val;
else if(val > Tree[root])
update(root*2, val);
else
update(root*2+1,val);
}
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++){
int x; cin>>x; update(1,x);
}
int ok = 0, cnt = 0;
for(int i = 1; i < maxn; i++){
if(Tree[i]){
if(ok)cout<<" ";
else ok = 1;
cout<<Tree[i];
cnt = i;
}
}
if(cnt > n)cout<<"\nNO\n";
else cout<<"\nYES\n";
return 0;
}
L3-011
#include<bits/stdc++.h>
using namespace std;
const int maxn = 250;
map<string,int>ma;
map<int,string>mb;
int tot = 1;
int getid(string s){
if(ma.count(s))return ma[s];
else{
mb[tot] = s;
ma[s] = tot;
tot++;
return ma[s];
}
}
int n, k, s, t;
int e[maxn][maxn], w[maxn];
int dist[maxn], vis[maxn], pre[maxn], cnt[maxn], weight[maxn], cc[maxn];
void Dijkstra(int u){
memset(dist, 0x3f,sizeof(dist));
memset(pre,-1,sizeof(pre));
dist[u] = 0; cnt[u] = 0; weight[u]=w[u]; cc[u] = 1;
for(int i = 1; i <= n; i++){
int v = -1, minn = 1e9;
for(int j = 1; j <= n; j++){
if(!vis[j] && dist[j]<minn){
minn = dist[j];
v = j;
}
}
vis[v] = 1;
for(int j = 1; j <= n; j++){
if(!vis[j] && dist[j]>dist[v]+e[v][j]){
dist[j] = dist[v]+e[v][j];
cc[j] = cc[v];
cnt[j] = cnt[v]+1;
weight[j] = weight[v]+w[j];
pre[j] = v;
}else if(!vis[j] && dist[j]==dist[v]+e[v][j]){
cc[j] += cc[v];//+=
if(cnt[j]<cnt[v]+1){
cnt[j] = cnt[v]+1;
weight[j] = weight[v]+w[j];
pre[j] = v;
}else if(cnt[j]==cnt[v]+1){
if(weight[j]<weight[v]+w[j]){
weight[j] = weight[v]+w[j];
pre[j] = v;
}
}
}
}
}
}
int main(){
cin>>n>>k;
string a,b; cin>>a>>b;
s = getid(a); t = getid(b);
memset(e,0x3f,sizeof(e));
for(int i = 1; i < n; i++){
string a; int b; cin>>a>>b;
w[getid(a)] = b;
}
for(int i = 1; i <= k; i++){
string a, b; cin>>a>>b;
int aa = getid(a), bb = getid(b);
int cc; cin>>cc;
e[aa][bb] = e[bb][aa] = cc;
}
Dijkstra(s);
vector<string>vec;
int x = t;
while(x!=-1){
vec.push_back(mb[x]);
x = pre[x];
}
reverse(vec.begin(),vec.end());
for(int i = 0; i < vec.size(); i++){
if(i==vec.size()-1)cout<<vec[i]<<endl;
else cout<<vec[i]<<"->";
}
cout<<cc[t]<<" "<<dist[t]<<" "<<weight[t]<<"\n";
return 0;
}
L3-012
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
struct seg{ double x, y1, y2; }s[maxn];
bool cmp(seg a, seg b){return a.x<b.x;}
double maxk,mink,ansmaxk,ansmink,ansx,ansy;
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++)
cin>>s[i].x>>s[i].y1>>s[i].y2;//y1在上,y2在下
sort(s+1,s+n+1,cmp);
for(int i = 1; i <= n; i++){
ansmaxk = 1e9;
ansmink = -1e9;
int j;
for(j = 1; j <= n; j++){
if(j==i)continue;
if(i<j){// j在i右侧
maxk = (s[i].y2-s[j].y1)/(s[i].x-s[j].x);
mink = (s[i].y2-s[j].y2)/(s[i].x-s[j].x);
}else{ //j在i左侧
maxk = (s[i].y2-s[j].y2)/(s[i].x-s[j].x);
mink = (s[i].y2-s[j].y1)/(s[i].x-s[j].x);
}
if(ansmaxk<mink || ansmink>maxk)break;
if(maxk<ansmaxk){
ansmaxk = maxk;
ansx = s[j].x;
ansy = s[j].y1;
}
ansmink = max(ansmink, mink);
}
if(j==n+1){//存在解
//线段i上取了最低点，则另一条线段要取最高点
printf("%.0lf %.0lf %.0lf %.0lf\n",s[i].x,s[i].y2,ansx,ansy);
return 0;
}
}
return 0;
}L3-013
#include<bits/stdc++.h>
using namespace std;
int main(){
double w, p; cin>>w>>p;
double E = 1000, g = 9.8;
double s = 1, sum = 0;
while(s>1e-8){//精度
s = 2*E/(w/100*g);
sum += s;
E *= (100-p)/100;
}
printf("%0.3lf",sum);
return 0;
}
L3-014
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int minCnt, minTrans;
vector<int>path, tempath;
int line[maxn][maxn]; //维护两点之间的线路归属
int count(vector<int>a){//给出路径，计算换乘
int cnt = -1, preLine = 0;
for(int i = 1; i < a.size(); i++){
if(line[a[i-1]][a[i]] != preLine)cnt++;
preLine = line[a[i-1]][a[i]];
}
return cnt;
}
vector<int>G[maxn]; int vis[maxn];
void dfs(int u, int end, int cnt){
if(u==end){
if(cnt<minCnt || (cnt==minCnt && count(tempath)<minTrans)){
minCnt = cnt;
minTrans = count(tempath);
path = tempath;
}
return ;
}
for(int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if(!vis[v]){
vis[v] = 1;
tempath.push_back(v);
dfs(v,end,cnt+1);
vis[v] = 0;
tempath.pop_back();
}
}
}
int main(){
int n, m, k, pre, tmp, a, b;
cin>>n;
for(int i = 1; i <= n; i++){
cin>>m>>pre;
for(int j = 2; j <= m; j++){
cin>>tmp;
G[pre].push_back(tmp);
G[tmp].push_back(pre);
line[pre][tmp] = i;
line[tmp][pre] = i;
pre = tmp;
}
}
cin>>k;
for(int i = 1; i <= k; i++){
cin>>a>>b;
//memset(vis,0,sizeof(vis));
minCnt = 1e9, minTrans = 1e9;
tempath.clear(); tempath.push_back(a);
vis[a] = 1;
dfs(a,b,0);
vis[a] = 0;//memset
if(minCnt == 1e9) {
printf("Sorry, no line is available.\n");
continue;
}
cout<<minCnt<<"\n";
int preLine = 0, preTrans = a;//上次的线路，以及转乘点
for(int j = 1; j < path.size(); j++){
if(line[path[j-1]][path[j]]!=preLine){
if(preLine!=0)printf("Go by the line of company #%d from %04d to %04d.\n", preLine, preTrans, path[j-1]);
preLine = line[path[j-1]][path[j]];
preTrans = path[j-1];
}
}
printf("Go by the line of company #%d from %04d to %04d.\n", preLine, preTrans, b);
}
return 0;
}
L3-015
#include<bits/stdc++.h>
using namespace std;
const int maxn = 50;
int n, T0, ok;
int e[maxn][maxn], vis[maxn];
vector<int>q;
void dfs(int u, int k){
for(int i = 1; i <= n; i++){
int flag = 0;//剩余队伍不存在战胜第一只队伍
for(int j = 1; j <= n; j++){
if(!vis[j] && e[j][T0]){
flag = 1; break;
}
}
if(flag && !ok && !vis[i] && e[u][i]){
vis[i] = 1; q.push_back(i);
if(k==n-1 && e[i][T0]){
ok = 1;
for(int j = 0; j < q.size(); j++){
if(j!=0)cout<<" ";
cout<<q[j];
}
}else{
dfs(i,k+1);
}
vis[i] = 0; q.pop_back();
}
}
}
int main(){
cin>>n; cin.get();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
char ch; cin>>ch;
if(ch=='W')e[i][j] = 1;
if(ch=='L')e[j][i] = 1;
}
cin.get();
}
for(int i = 1; i <= n; i++){//另i为队首
vis[i] = 1; q.push_back(i);
T0 = i; dfs(i,1);
if(ok)return 0;
vis[i] = 0; q.pop_back();
}
cout<<"No Solution";
return 0;
}
L3-016
#include<bits/stdc++.h>
using namespace std;
struct node{int l=-1, r=-1, fa=-1, h;};
map<int,node>Tree;
void insert(int u, int h, int v){
if(u==-1)return ;
int uu = (v<u ? Tree[u].l : Tree[u].r);
if(uu!=-1){
insert(uu,h+1,v);
}else{
if(v<u)Tree[u].l = v;
else Tree[u].r = v;
Tree[v].fa = u;
Tree[v].h = h;
}
}
bool judge(int u, int a, int b, string lk){
if(lk=="root")return u==a;;
if(Tree.find(a)==Tree.end() || Tree.find(b)==Tree.end())return false;
if(lk=="siblings")return Tree[a].fa==Tree[b].fa;
if(lk=="parent")return Tree[a].l==b || Tree[a].r==b;
if(lk=="left")return Tree[b].l == a;
if(lk=="right")return Tree[b].r == a;
if(lk=="level")return Tree[a].h==Tree[b].h;
}
int main(){
int n, rt, t;
cin>>n>>rt; //rt是根
for(int i = 2; i <= n; i++){
cin>>t;
insert(rt,1,t);
}
int m, a=0, b=0; cin>>m;
for(int i = 1; i <= m; i++){
string s, lk; cin>>a>>s;
if(s=="and"){
cin>>b>>s>>s;
if(s=="siblings")lk = s;
else cin>>s>>s>>lk;
}else{
cin>>s>>lk;
if(lk=="parent")cin>>s>>b;
else if(lk!="root")cin>>s>>s>>b;
}
if(judge(rt,a,b,lk))cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
L3-017
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
struct seg{int x, y;}sg[maxn];
bool cmp(seg a, seg b){return a.y!=b.y?a.y<b.y:a.x<b.x;}
LL rmq[maxn<<2], tag[maxn<<2], c[maxn];
#define lch p<<1
#define rch p<<1|1
void pushdown(int p){
if(tag[p]){
tag[lch] += tag[p], tag[rch]+=tag[p];
rmq[lch] += tag[p], rmq[rch]+=tag[p];
tag[p] = 0;
}
}
void pushup(int p){
rmq[p] = min(rmq[lch], rmq[rch]);
}
void build(int p, int l, int r){
tag[p] = 0;
if(l==r){
rmq[p] = c[l];
return ;
}else{
int m = l+r>>1;
build(lch,l,m);
build(rch,m+1,r);
pushup(p);
}
}
void update(int p, int l, int r, int L, int R, int v){
if(l>R || r<L)return ;
if(L<=l && r<=R){
rmq[p] += v; tag[p] += v;
return ;
}
pushdown(p);
int mid = l+r>>1;
update(lch,l,mid,L,R,v);
update(rch,mid+1,r,L,R,v);
pushup(p);
}
LL query(int p, int l, int r, int L, int R){
if(l>R || r<L)return (1ll<<60);
if(L<=l && r<=R)return rmq[p];
pushdown(p);
LL mid = l+r>>1, ans = 1ll<<60;
ans = min(ans, query(lch,l,mid,L,R));
ans = min(ans, query(rch,mid+1,r,L,R));
return ans;
}
int main(){
int n, q;
cin>>n>>q;
for(int i = 1; i < n; i++)
cin>>c[i];
build(1,1,n-1); //1-(n-1)号城市分别对应i与i+1的边
for(int i = 1; i <= q; i++){
cin>>sg[i].x>>sg[i].y;
if(sg[i].x>sg[i].y)swap(sg[i].x,sg[i].y);
}
sort(sg+1,sg+q+1,cmp);
LL ans = 0;
for(int i = 1; i <= q; i++){
//cout<<sg[i].x+1<<" "<<sg[i].y<<" ";
LL res = query(1,1,n-1,sg[i].x+1,sg[i].y);//因为编号从0开始，所以x+1。
//cout<<res<<"\n";
ans += res;
if(res)update(1,1,n-1,sg[i].x+1,sg[i].y,-res);
}
cout<<ans<<endl;
return 0;
}
L3-018
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9+10;
const int maxn = 110;
struct point{ int x, y; double dis;};
bool operator!=(point a, point b){return a.x!=b.x||a.y!=b.y;}
bool operator==(point a, point b){return a.x==b.x&&a.y==b.y;}
int n, m;
double sc[maxn][maxn];//分数
point s, t;
void input(){
cin>>n>>m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin>>sc[i][j];
cin>>s.y>>s.x>>t.y>>t.x;
s.x++;s.y++;t.x++;t.y++;
s.dis = sc[s.x][s.y];
}
int flag;//1上半部分，0下半部分
double f[maxn][maxn]; //到i,j为止的最小值
int dir[][2]= {{0,1},{1,0},{-1,0},{0,-1},{-1,-1},{1,-1},{-1,1},{1,1}}; //上下左右+前后左右
int cross(point a,point b,point p){//三角形行列式公式,判断三点是否在一个直线上
return (b.x-a.x)*(p.y-a.y)-(p.x-a.x)*(b.y-a.y);
}
bool check(point p){//检查p是否合法（越界）
if(p.x<1||p.x>n||p.y<1||p.y>m)return false;//越界
if(flag && p!=s&&p!=t && cross(s,t,p)<=0)return false;//1:上半部分但点在下面(起点终点不算)
if(!flag && p!=s&&p!=t && cross(s,t,p)>=0)return false;//2.下半部分但点在上面
if(p.dis>=f[p.x][p.y])return false;//不是最小值
return true;
}
void bfs(){
//init
queue<point>q;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
f[i][j] = inf;
//search
if(check(s)){
f[s.x][s.y] = s.dis;
q.push(s);
}
while(q.size()){
point now = q.front(); q.pop();
point next;
for(int i = 0; i < 8; i++){
next.x=now.x+dir[i][0];
next.y=now.y+dir[i][1];
if(i<4)next.dis = f[now.x][now.y]+sc[next.x][next.y];
else next.dis=f[now.x][now.y]+sc[next.x][next.y]+(sc[next.x][next.y]+sc[now.x][now.y])*(sqrt(2)-1);
if(check(next)){
f[next.x][next.y] = next.dis;
q.push(next);
}
}
}
}
int main(){
input();
double ans = 0;
flag = 1; bfs(); ans += f[t.x][t.y];//搜上面
flag = 0; bfs(); ans += f[t.x][t.y];//搜下面
ans -= sc[s.x][s.y]+sc[t.x][t.y];//重复
printf("%.2f\n",ans);
return 0;
}L3-019
#include<bits/stdc++.h>
using namespace std;
//判断语句块类型
int judge(string dat, int i){
//WA3:当前位置是if并且不是在字符串内
if(dat.find("if", i)==i && (dat[i+2]==' '||dat[i+2]=='('))return 2;
if(dat.find("for",i)==i && (dat[i+3]==' ' ||dat[i+3]=='('))return 3;
if(dat.find("while",i)==i && (dat[i+5]==' '||dat[i+5]=='('))return 5;
if(dat.find("else",i)==i && dat[i+4]==' ')return 4;
return 0;//普通语句
}
//输出前删除多余空格, 并输出当前对应的空格
void erase_space(string dat,int &i){while(dat[i]==' ')i++;}
void print_space(int sp){for(int i=0;i<sp;i++)putchar(' ');}
int main(){
string dat; getline(cin,dat);
//处理int main() 找i和)输出
int l = dat.find('i',0), r = dat.find(')',0);
cout<<dat.substr(l,r-l+1)<<"\n{\n";
//处理其他，按照行分类
int tmp, space = 2;//语句类型,空格数
int flag, debt=0;//单句标记，层数（补全缺少的}）
for(int i = dat.find('{')+1,j=0,k; i < dat.size(); ){
erase_space(dat,i);//删除每行前的空格
if(dat[i]=='{' || dat[i]=='}'){
if(dat[i]=='{'){
print_space(space);
printf("{\n");
space += 2;
i++;
continue;
}else{
space -= 2;
print_space(space);
printf("}\n");
i++;
if(space==0)break;//main的}输完就结束了
//【重复】单句特判
erase_space(dat,i);
while(debt && judge(dat,i)!=4){
space -= 2;
print_space(space);
printf("}\n");
debt--;
}
}
}else if((tmp=judge(dat,i))){
print_space(space);
//处理for,while,if,+()或者else
if(tmp==4){
printf("else");
k = i+3;
}else{
cout<<dat.substr(i,tmp)<<" ";
i += tmp;
erase_space(dat, i);
//考虑if()中也有()条件的情况
k = i; int t = 0;
while(1){
if(dat[k]=='(')t++;
if(dat[k]==')')t--;
if(!t)break;
k++;
}
cout<<dat.substr(i,k-i+1);
}
//预处理{}的内容,考虑单句特判
int m = k+1;
erase_space(dat,m);
if(dat[m] != '{'){//单句标记
printf(" {\n");
flag = 1;
debt++;
i = m;
}else{
printf(" {\n");
flag = 0;
i = m+1;
}
space += 2;
}else{//普通语句
int ed = dat.find(';', i);
print_space(space);
cout<<dat.substr(i,ed-i+1)<<"\n";
i = ed+1;
//这是单句内的语句
if(flag && debt){
space -= 2;
print_space(space);
printf("}\n");
debt--;
//【重复】单句特判
erase_space(dat,i);
while(debt && judge(dat,i)!=4){
space -= 2;
print_space(space);
printf("}\n");
debt--;
}
}
}
}
return 0;
}
L3-020
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
LL f[maxn][5];
int main(){
string s; cin>>s; s = "0"+s;//从1开始
f[0][0] = 1;
for(int i = 1; i < s.size(); i++){
for(int j = 0; j <= 3; j++){//删0-3个
f[i][j] = f[i-1][j]+f[i-1][j-1];//第i个删还是不删
for(int k=i-1; k>=1 && (i-k)<=j; k--){//去重
if(s[k]==s[i]){//如果当前字符一样，那么前面的重复统计了
f[i][j] -= f[k-1][j-(i-k)];
break;
}
}
}
}
LL ans = 0;
for(int i = 0; i <= 3; i++)
ans += f[s.size()-1][i];
cout<<ans<<endl;
return 0;
}
L3-021
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+10;
struct point{LL x, y;}pp[maxn], tmp[maxn];
bool cmp(point a, point b){return a.x*b.y>a.y*b.x;}
int main(){
int n; cin>>n;
for(int i = 0; i < n; i++)
cin>>pp[i].x>>pp[i].y;
double ans = 1e18;
for(int i = 0; i < n; i++){
int cc = 0;
for(int j = 0; j < n; j++){
if(i==j)continue;
tmp[cc].x = pp[j].x-pp[i].x;
tmp[cc].y = pp[j].y-pp[i].y;
cc++;
}
sort(tmp,tmp+cc,cmp);
for(int j = 0; j < cc; j++)
ans=min(ans,abs(0.5*(tmp[j].x*tmp[(j+1)%cc].y-tmp[(j+1)%cc].x*tmp[j].y)));
}
printf("%.3f\n",ans);
return 0;
}
L3-022
#include<bits/stdc++.h>
using namespace std;
const int maxn = 210;
const int inf = 1e9+10;
int G[maxn][maxn];
vector<int>st[maxn]; int ed[maxn], vis[maxn];
void dfs(int u){
for(int i = 0; i < st[u].size(); i++){
int v = st[u][i];
if(!vis[v]){
vis[v] = 1;
dfs(v);
}
}
}
int main(){
//input
int n, m, k; cin>>n>>m>>k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
G[i][j] = inf;
for(int i = 1; i <= m; i++){
int a, b, dis;
cin>>a; ed[a] = 1;
while(cin>>dis>>b){
G[a][b] = min(G[a][b], dis);
G[b][a] = min(G[b][a], dis);
a = b;
if(getchar()=='\n')break;
}
ed[a] = 1;
}
//solve
for(int k = 1; k <= n; k++)//Floyd
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i!=j)G[i][j] = min(G[i][j],G[i][k]+G[k][j]);
for(int i = 1; i <= n; i++){//从点i出发
map<int,int>cost;//各种费用能到的最远距离
for(int j = 1; j <= n; j++){//遍历到每个点的费用去更新距离
if(G[i][j]==inf)continue;
cost[2+G[i][j]/k] = max(cost[2+G[i][j]/k],G[i][j]);
}
for(int j = 1; j <= n; j++){//更新点i能到达的最远点或者端点
if(G[i][j]==cost[2+G[i][j]/k] || i!=j&&ed[j]&&G[i][j]!=inf){
st[i].push_back(j);
}
}
}
int q; cin>>q;
for(int i = 1; i <= q; i++){
int x; cin>>x;
memset(vis,0,sizeof(vis));
vis[x] = 1;
dfs(x);
for(int j = 1; j <= n; j++)
if(vis[j])st[x].push_back(j);
sort(st[x].begin(), st[x].end());
st[x].erase(unique(st[x].begin(), st[x].end()), st[x].end());
for(int j = 0; j < st[x].size(); j++){
if(j!=0)cout<<" ";
cout<<st[x][j];
}
cout<<"\n";
}
return 0;
}
L3-023
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4+10;
struct node{
int op, left, right; //运算符和数值
double val; //当前节点的值
int post; //后继节点的
}a[maxn];
map<int,map<int,map<int,double>>>f;//记忆化数组
//第一个参数为结点，第二个参数决定是否求导，第三个参数是对谁求导
double calc(int nd, int key, int p){
if(f[nd][key][p])return f[nd][key][p];
int id = a[nd].op;
if(id==0)return f[nd][key][p] = (key == 0 ? a[nd].val : (nd == p ? 1 : 0));
if(id==1)return f[nd][key][p] = calc(a[nd].left, key, p) + calc(a[nd].right, key, p);
if(id==2)return f[nd][key][p]= calc(a[nd].left, key, p) - calc(a[nd].right, key, p);
if(id==3)return f[nd][key][p] = (key ? calc(a[nd].left, key, p) * calc(a[nd].right, 0, p) + calc(a[nd].left, 0, p) * calc(a[nd].right, key, p) : calc(a[nd].left, key, p) * calc(a[nd].right, key, p));
if(id==4)return f[nd][key][p]=(key ? exp(calc(a[nd].left, 0, p)) * calc(a[nd].left, key, p) : exp(calc(a[nd].left, key, p)));
if(id==5)return f[nd][key][p] = (key ? 1 / (calc(a[nd].left, 0, p)) * (calc(a[nd].left, key, p)) : log(calc(a[nd].left, key, p)));
if(id==6)return f[nd][key][p] = (key ? cos(calc(a[nd].left, 0, p)) * calc(a[nd].left, key, p) : sin(calc(a[nd].left, key, p)));
}
int main(){
int n; cin>>n;
for(int i = 0; i < n; i++){
cin>>a[i].op;
if(a[i].op==0){
cin>>a[i].val;
}else if(a[i].op<=3){
cin>>a[i].left>>a[i].right;
a[a[i].left].post = 1;
a[a[i].right].post = 1;
}else{
cin>>a[i].left;
a[a[i].left].post = 1;
}
}
int ed = 0, ok=0;
while(a[ed].post)ed++;
printf("%0.3lf\n",calc(ed,0,-1));
for(int i = 0; i < n; i++){
if(a[i].op==0){
if(ok)cout<<" ";
printf("%0.3lf",calc(ed,1,i));
ok = 1;
}
}
return 0;
}
