2020-9-5 刚考完PAT
最后半小时手机居然关机断网了！！！
题目描述可以参考2020年PAT秋原题
第一题（奶牛题）
好坑，我想的是找出单调序列，从小到大依次赋值，序列最大的点先放着，之后根据两边的值确定每个最大点处的值。最后一个点wa（-3分）
code1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int d[10005];
int main()
{
int N; cin>>N;
int a[N+3];
for(int i=1;i<=N;++i) cin>>a[i];
a[0]=-1; a[N+1]=-1;
//寻找单调序列
for(int i=1;i<N;++i)
{
//寻找单减
int f=1;
int j;
for(j=i;j<N;++j)
{
if(a[j+1]>a[j]) {
break;
}
}
if(j==N) j--;
if(j==i) f=0;//f=0 是单增
if(f==0)
{
for(j=i;j<N;++j)
{
if(a[j+1]<a[j]) break;
}
}
//cout<<j<<" "<<f<<" "<<i<<endl;
if(f)//减
{
int now=200;
for(int k=j;k>i;--k) {
d[k]=now;
if(a[k-1]!=a[k])
now+=100;
}
i=j; //i=j-1修改为i=j
}
else {
int now=200;
for(int k=i;k<j;++k) {
d[k]=now;
if(a[k+1]!=a[k])
now+=100;
}
i=j; //i=j-1修改为i=j
}
}
for(int i=1;i<=N;++i)
{
//cout<<d[i]<<" ";
if(d[i]==0 && i!=1 && i!=N)
{
d[i]=max(d[i-1],d[i+1])+100;
}
}
if(N>1)
if(d[N]==0)
if(a[N]>a[N-1]) d[N]=d[N-1]+100;
else if(a[N]==a[N-1]) d[N]=d[N-1];
if(d[1]==0)
if(a[1]>a[2]) d[1]=d[2]+100;
else d[1]=d[2];
ll ans=0;
for(int i=1;i<=N;++i)
{
ans+=d[i];
//cout<<d[i]<<" ";
}
if(N==1) cout<<"200"<<endl;
else if(N==2) {
if(a[1]!=a[2]) cout<<"500"<<endl;
else cout<<"400"<<endl;
}
else cout<<ans<<endl;
return 0;
}
第二题
区间和问题，先求前缀和，再暴力找（满分）
code2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N,M;
ll a[10005];
ll total=0;
ll sum[10005];
int main()
{
scanf("%lld%lld",&N,&M);
for(int i=1;i<=N;++i) {
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
for(int i=0;i<N;++i)
for(int j=i+1;j<=N;++j)
if(sum[j]-sum[i]<=M) total++;
printf("%lld
",total);
return 0;
}
第三题
建树(给出中序，前序)拼题A上做过类似的click（满分）
code3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
int in[25],pre[25];//中序和先序
int tree[25][3];
void build(int l,int r,int l1,int r1)
{
if(l>r) return ;
int i;
for(i=l1;i<=r1;++i)
if(in[i]==pre[l]) break;
if(i!=l1)//有左孩子
{
tree[l][1]=l+1;
build(l+1,l+i-l1,l1,i-1);
}
if(i!=r1)
{
tree[l][2]=(l+i-l1+1);
build(l+i-l1+1,r,i+1,r1);
}
}
struct node{
int index;
int ceng;
}temp;
int flag[25];//每层标记
int main()
{
cin>>N;
for(int i=1;i<=N;++i) cin>>in[i];
for(int i=1;i<=N;++i) cin>>pre[i];
build(1,N,1,N);
queue<node>Q;
temp.index=1; temp.ceng=1;
Q.push(temp);
while(!Q.empty())
{
temp=Q.front(); Q.pop();
if(flag[temp.ceng]==0) {
if(temp.ceng!=1) printf(" ");
printf("%d",pre[temp.index]);
flag[temp.ceng]=1;
}
if(tree[temp.index][1]!=0)
{
node temp1;
temp1.ceng=temp.ceng+1;
temp1.index=tree[temp.index][1];
Q.push(temp1);
}
if(tree[temp.index][2]!=0)
{
node temp1;
temp1.ceng=temp.ceng+1;
temp1.index=tree[temp.index][2];
Q.push(temp1);
}
}
return 0;
}
第四题（阅读理解题）
环+最短路，我居然不会找环，写了个垃圾算法，TLE了！！（-6分）
题意：给定一个有向图，边权为S、D，存在环则输出impossible，否则输出ok，然后对每个询问，输出一条从入度为0的点到该点的最短路径
code4
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,M;
struct node{
int v;
int S,D;
}temp;
vector<node>G1[1006];//反
int S1[1006][1006];
int D1[1006][1006];
int f[1006];//环标记
int flag=0;
int now;
void DFS1(int x,int cnt,vector<int> v)//查找环
{
if(cnt>M) return ;
if(x==now && cnt>1)//环
{
for(int i=0;i<v.size();++i) f[v[i]]=1;
//f[now]=1;
flag=1;
return ;
}
else {
for(int i=0;i<G1[x].size();++i)
{
v.push_back(G1[x][i].v);
DFS1(G1[x][i].v,cnt+1,v);
v.pop_back();
}
}
}
stack<int>ans;
int S_=INT_MAX,D_;
void DFS(int x,stack<int> st,int S_now,int D_now)
{
if(G1[x].size()==0)//选择最优解
{
if(S_now<S_) {
S_=S_now;
D_=D_now;
ans=st;
}
else if(S_now==S_ && D_now>D_)
{
D_=D_now;
ans=st;
}
return ;
}
else
{
for(int i=0;i<G1[x].size();++i)
{
int v=G1[x][i].v;
if(f[v]==0)
{
st.push(v);
DFS(v,st,S_now+S1[v][x],D_now+D1[v][x]);
st.pop();
}
}
}
}
int main()
{
scanf("%d%d",&N,&M);
for(int i=1;i<=M;++i)
{
int T1,T2,S,D;
scanf("%d%d%d%d",&T1,&T2,&S,&D);
S1[T1][T2]=S;
D1[T1][T2]=D;
temp.v=T1; temp.S=S; temp.D=D;
G1[T2].push_back(temp);
}
for(int i=0;i<N;++i)
{
if(f[i]) continue;
now=i;
vector<int> vv;
vv.push_back(i);
DFS1(i,0,vv);
}
if(flag) printf("Impossible.
");
else printf("Okay.
");
int Q;
scanf("%d",&Q);
while(Q--)
{
int t; scanf("%d",&t);
if(G1[t].size()==0) {
printf("You may take test %d directly.
",t);
continue;
}
if(f[t]) {
printf("Error.
");
continue;
}
S_=INT_MAX;
D_=0;
stack<int>st;
st.push(t);
DFS(t,st,0,0);
while(!ans.empty())
{
int p=ans.top();
ans.pop();
printf("%d",p);
if(ans.size()>0) printf("->");
}
printf("
");
}
return 0;
}