PAT Advanced Level

  1. 具有充分的英文阅读理解能力；
  2. 理解并掌握基础数据结构，包括：线性表、树、图；
  3. 理解并熟练编程实现经典高级算法，包括哈希映射、并查集、最短路径、拓扑排序、关键路径、贪心、深度优先搜索、广度优先搜索、回溯剪枝等；
  4. 具备较强的问题抽象和建模能力，能实现对复杂实际问题的模拟求解。

1、排序：快速排序，直接插入排序，希尔排序，分治排序，堆排序。

2、图论：拓扑排序(好像没考过)、最短路径、深度搜索、广度搜索。

3、树：树的遍历、完全二叉树、AVL,CBT,BST。

4、其他：并查集，模拟，哈希(二次探测一次，简单hash多次)、背包(一次)，lcs（一次），最大子和（一次）,set(一次)，1057（分块搜索）

一些东西

整行读入字符串

string str;
getline(cin,str);//读入string

char str2[1024];
cin.getline(str2,1024);//读入char数组

string::erase

erase(pos,n)：

删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符。

erase(position)：

删除position处的一个字符(position是个string类型的迭代器)。

erase(first,last)：

删除从first到last之间的字符（first和last都是迭代器）。

记模板

最大公约数

gcd(a,b)=gcd(b,a mod b)​

int gcd(int a,int b)
{
    if(a<b){int temp;temp=a;a=b;b=temp;}	//使a>=b
    if(b==0)return a;
    return gcd(b,a%b);
}

最短路

floyd

for(k=1;k<=n;k++)    
for(i=1;i<=n;i++)    
for(j=1;j<=n;j++)    
dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);

Dijkstra

struct edge
{
    int to,cost;
};
vector<edge>v[1010];
typedef pair<int,int>p;
bool vis[1010];
int dis[1010];
int n;
void dijkstra()
{
    fill(dis+1,dis+n+1,INF);
    dis[1]=0;
    priority_queue<p,vector<p>,greater<p> >q;
    q.push(p(0,1));
    while(!q.empty())
    {
        p temp=q.top();
        q.pop();
        int w=temp.first;int id=temp.second;
        if(vid[id])continue;
        vis[id]=true;
        for(int i=0;i<v[id].size();i++)
        {
            edge &e=v[id][i];
            if(w+e.cost<dis[e.to])
            {
                dis[e.to]=w+e.cost;
                q.push(p(dis[e.to],e.to));
            }
        }
    }
}

数位dp

int a[20];
long long dp[20][state];
long long dfs(int pos,/*state变量*/,bool lead,bool limit)
{
    if(pos==-1) return 1;
    if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
    int up=limit?a[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++)
    {
        if() ...
        else if()...
        ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos])
    }
    if(!limit && !lead) dp[pos][state]=ans;
    return ans;
}
long long solve(long long x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,/*一系列状态 */,true,true);
}
int main()
{
    long long le,ri;
    while(~scanf("%lld%lld",&le,&ri))
    {
        printf("%lld\n",solve(ri)-solve(le-1));
    }
}

树状数组

（下标都从1开始）

区间查询 单点修改

int n;
int d[500010];
int lowbit(int x)
{
    return x&(-x);
}
int query(int x)//查询前缀和
{
    int res=0;
    while(x)
    {
        res+=d[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int v)//单点修改
{
    while(x<=n)
    {
        d[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
    int m,x,y,ope;
    scanf("%d%d",&n,&m);
    memset(d,0,sizeof(d));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        add(i,x);
    }
    while(m--)
    {
        scanf("%d%d%d",&ope,&x,&y);
        if(ope==1)add(x,y);
        else if(ope==2)printf("%d\n",query(y)-query(x-1));
    }
    return 0;
}

单点查询 区间修改

int n;
int c[500010];//差分数组
int lowbit(int x)
{
    return x&(-x);
}
int query(int x)//单点查询
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int v)//区间修改
{
    while(x<=n)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
    int m,x,y,k,ope,ls;
    scanf("%d%d",&n,&m);
    memset(c,0,sizeof(c));
    ls=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        add(i,x-ls);
        ls=x;
    }
    while(m--)
    {
        scanf("%d",&ope);
        if(ope==1)
        {
            scanf("%d%d%d",&x,&y,&k);
            add(x,k);
            add(y+1,-k);
        }
        else if(ope==2)
        {
            scanf("%d",&x);
            printf("%d\n",query(x));
        }
    }
    return 0;
}

二分

求满足条件的最大值

int l=1,r=maxn,ans=0;
while(l<=r)
{
    int mid=(l+r)>>1;
    if(judge(mid))ans=mid,l=mid+1;
    else r=mid-1;
}

求满足条件的最小值

int l=1,r=maxn,ans=0;
while(l<=r)
{
    int mid=(l+r)>>1;
    if(judge(mid))ans=mid,r=mid-1;
    else l=mid+1;
}

并查集

int par[1010],high[1010];
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        par[i]=i;
        high[i]=0;
    }
}
int find(int x)
{
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(high[x]<high[y])par[x]=y;   //启发式合并
    else
    {
        par[y]=x;
        if(high[x]==high[y])high[x]++;
    }
}
bool same(int x,int y)
{
    return find(x)==find(y);
}

优先队列的优先级设置

struct fruit
{
    string name;
    double price;
}f1,f2,f3; //定义三个结构体变量
struct cmp
{
    bool operator()(fruit f1, fruit f2) //重载括号
    {
        return f1.price<f2.price; //等同于less
    }
};

调用：priority_queue<fruit,vector<fruit>,cmp>q;

AVL的插入

struct node
{
    int val;
    int high;
    node *left,*right;
    node(int x)
    {
        val=x;high=0;
        left=right=NULL;
    }
};
int gethigh(node *temp)
{
    if(temp==NULL)return -1;
    return temp->high;
}
node* SingleRotateLL(node *root)
{
    node *temp;
    temp=root->left;
    root->left=temp->right;
    temp->right=root;
    root->high=max(gethigh(root->left),gethigh(root->right))+1;     //更新高度
    temp->high=max(gethigh(temp->left),gethigh(temp->right))+1;     
    return temp;
}
node *SingleRotateRR(node *root)
{
    node *temp;
    temp=root->right;
    root->right=temp->left;
    temp->left=root;
    root->high=max(gethigh(root->left),gethigh(root->right))+1; //更新高度
    temp->high=max(gethigh(temp->left),gethigh(temp->right))+1;
    return temp;
}
node *DoubleRotateLR(node *root)
{
    root->left=SingleRotateRR(root->left);
    return SingleRotateLL(root);
}
node *DoubleRotateRL(node *root)
{
    root->right=SingleRotateLL(root->right);
    return SingleRotateRR(root);
}
node* Insert(node *root,int x)
{
    if(root==NULL){return new node(x);}
    if(x<root->val)
    {
        root->left=Insert(root->left,x);
        if(abs(gethigh(root->left)-gethigh(root->right))>1)
        {
            if(x<root->left->val)
                root=SingleRotateLL(root);
            else
                root=DoubleRotateLR(root);
        }
    }
    else
    {
        root->right=Insert(root->right,x);
        if (abs(gethigh(root->left)-gethigh(root->right))>1)
        {
            if(x>root->right->val)
                root=SingleRotateRR(root);
            else
                root=DoubleRotateRL(root);
        }
    }
    root->high=max(gethigh(root->left),gethigh(root->right))+1; //更新高度
    return root;
}
int main()
{
    int n,x;
    scanf("%d",&n);
    node *root=NULL;
    while(n--)
    {
        scanf("%d",&x);
        root=Insert(root,x);
    }
    printf("%d\n",root->val);
    return 0;
}

题解

Nowcoder

1017

求栈的中位数，包括push和pop操作。

对于求中位数，二分+树状数组。

1038

求1～N十进制表示中1的个数。

数位dp。

$dp[i][j]​$：长度为i已有j个1的数字中1的个数。

int dfs(int pos,int num,bool limit)
{
    if(pos==-1)return num;
    if(!limit&&dp[pos][num]!=-1)return dp[pos][num];
    int up=limit?a[pos]:9;
    int ans=0;
    for(int i=0;i<=up;i++)
        ans+=dfs(pos-1,i==1?num+1:num,limit&&i==up);
    if(!limit)dp[pos][num]=ans;
    return ans;
}

1049

给你一些数字的片段，希望拼接之后能拼出的最小的数字。

样例输入：5 32 321 3214 0229 87，样例输出：22932132143287。

假设有两个相邻的数字片段a,b。然后我们就要想，把a和b交换能不能使整个序列变小呢？这个问题的其实等价于b+a 是否小于a+b，也就是说对于这样一个序列，如果某两个相邻的元素之间发生交换可以使得整个序列的值变小，就应该交换。

注意00000的情况即可。

bool cmp(string x,string y)
{
    if(x+y<y+x)return true;
    return false;
}

PTA

1045

有一组喜欢的数字序列，要从另一组数字里面选出最长的子序列，使得喜欢的数字序列包含在子序列中（不需要每一个都被包含）。

可以把喜欢的数字序列从小到大编号，然后在数字里选出子序列就相当于最长非递减子序列。

1091

如果dfs要考虑深度，避免递归深度过大爆栈。

这题。所以用bfs。

1103

给出N，K，P，使得。输出的方案首先最大然后字典序最大。

dfs。注意写法。

dfs里面不要用循环写，因为要字典序最大，肯定是从最大的数开始枚举。

dfs(int id,int now, int cnt, int sum, int path[])
转移：
	if(now+a[id]<=n)
    {
        path[cnt + 1] = id;
        dfs(id,now + a[id], cnt + 1, sum + id, path);
    }
    if(id-1>=1)
        dfs(id-1,now,cnt,sum,path);
调用：dfs(a[0],0, 0, 0, pp);

1123

判断是不是完全二叉树。当某个节点的儿子有为空的以后，出现子节点不为空的则说明不是完全二叉树，否则是。

1135

给出一个二叉查找树的前序遍历序列，判断该树是不是红黑树。

已知红黑树满足以下性质：

（1）每个结点要么是红的要么是黑的。

（2）根结点是黑的。

（3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。

（4）如果一个结点是红的，那么它的两个儿子都是黑的。

（5）对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

这道题debug了好久…一直有几个点过不去，然后看题解发现是自己不清楚红黑树的定义。它的叶子并不是我之前所想的叶子。

如图是一棵红黑树：

此图忽略了叶子和根部的父结点。同时，上文中我们所说的 “叶结点” 或”NULL结点”，如上图所示，它不包含数据而只充当树在此结束的指示，这些节点在绘图中经常被省略。

然后改一下写的代码就可以过了。

1139

A想要联系B需要这样的步骤：A先找一个同性朋友C，再让C找一个与B同性且同时是C和B的D，由D联系B。现给出一些关系，给出A和B，输出可能的联系的方案，即输出C和D。编号都用四位数表示。

本来想的是DFS，这样会超时，其实已经规定了深度为4，所以只要枚举A的同性朋友C和B的同性朋友D，判断C和D是否是朋友即可。因为这里N最大为300，所以根据复杂度知道可行。

这里还有一些坑，比如男女用+-来表示，如果直接用int来接收的话，如果出现-0000就没法判断到底是+还是-了。还有输出的时候应该要%04d（注意！！！）。

题解

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！

tips Previous
I/O调度 Next