头像

一条代码




离线:2天前


最近来访(109)
用户头像
ljh_lxy
用户头像
bobo34
用户头像
yxc的小迷妹
用户头像
violet_garden
用户头像
济带阿孙
用户头像
Judy_wfy
用户头像
yxc
用户头像
AcMerrr
用户头像
MBH
用户头像
Scimelan
用户头像
77777777777
用户头像
嘎_3
用户头像
MAX_1109
用户头像
糕小芝
用户头像
垫底抽風
用户头像
wr1sw
用户头像
I+III
用户头像
lihua777
用户头像
windac
用户头像
馨意


题目描述

Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well.

According to Wikipedia, opinion leadership is leadership by an active media user who interprets the meaning of media messages or content for lower-end media users. Typically opinion leaders are held in high esteem by those who accept their opinions.

To be more specific, let’s define an opinion leader index OLI to be Nin/Nout, where Nin is the number of one’s followers and Nout is the number of users that one follows on Weibo. Then for any given threshold T, we call those users whose OLI is at least T the opinion leaders.

Some of the opinion leaders may follow each other. An opinion leader who has the most number of other opinion leaders following him/her is defined to be the leader of the opinion leaders. Your job is to find those leaders of the opinion leaders.

输入

Each input file contains one test case. For each case, the first line contains 2 positive integers: N(≤1e4), the number of users; and T(≤100), the threshold for OLI. Hence it is assumed that all the users are numbered from 1 to N, and those users whose OLI is at least T is the opinion leaders.

Then N lines follow, each in the format:

M[i] user_list[i]

where M[i] (≤100) is the total number of people that user[i] follows and is always positive; and user_list[i] is a list of the indices of the M[i] users that are followed by user[i]. It is guaranteed that no one can follow oneself, and all the indices in a user_list[i] are distinct. All the numbers are separated by a space.

输出

Print in one line all the leaders of the opinion leaders, in ascending order of their indices.

It is guranteed that there is at least one ouput. All the numbers must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

样例

10 3
3 9 3 8
2 1 3
2 9 7
3 2 7 5
3 6 3 7
2 7 3
1 2
2 3 9
1 10
1 3
7 9

解法

OLI: Nout/Nin
Opinion Leaders:OLI超过T的人
主要是找出被最多Opinion Leaders关注的Opinion Leaders

记录所有的Opinion Leaders,然后统计关注他的人里面的Opinion Leaders数量。


C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,t,f[10010],ma;
vector<int>out[10010],in[10010],r;
int main()
{
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        while(x--)
        {
            int y;
            cin>>y;
            out[i].push_back(y);
            in[y].push_back(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(in[i].size()/out[i].size()>=t)f[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        int m=0;
        for(auto j=in[i].begin();j!=in[i].end();j++)
        {
            if(f[*j]==1)m++;
        }
        if(f[i]==1&&m>ma)
        {
            ma=m;
            r.clear();
            r.push_back(i);
        }
        else if(f[i]==1&&m==ma)
        {
            r.push_back(i);
        }
    }
    for(auto i=r.begin();i!=r.end();i++)
    {
        if(i!=r.begin())cout<<" ";
        cout<<*i;
    }
    return 0;
}



题目描述

“During the sorting, processing every element which is not yet at its final position is called a run. Which of the following cannot be the result after the second run of quicksort?” – This is a question in the Graduate Entrance Exam set. Now you are supposed to write a program to check the answers automatically.

输入

“During the sorting, processing every element which is not yet at its final position is called a run. Which of the following cannot be the result after the second run of quicksort?” – This is a question in the Graduate Entrance Exam set. Now you are supposed to write a program to check the answers automatically.
where N (3≤N≤1e5) is the number of elements, and a[i]’s (≤1e9) are distinct elements to be checked. All the numbers in a line are positive integers that are separated by spaces.

输出

For each test case, output in a line Yes if it is possible to be the second run of quicksort, or No if not.

样例

4
8
5 2 16 12 28 60 32 72
8
2 16 5 28 12 60 32 72
8
2 12 16 5 28 32 72 60
8
5 2 12 28 16 32 72 60
Yes
Yes
Yes
No

解法

每一次快排会确定当前区间某一个元素的位置
1. 如果三个以上元素位置确定
2. 两个元素位置确定并且包含第一个元素或最后一个元素中的其中一个,则为快排第二趟后的序列。


#include <bits/stdc++.h>
using namespace std;
int t,n,a[100010],b[100010],lmax[100010],rmin[100010],r;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        r=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            lmax[i]=max(lmax[i-1],a[i]);
            b[i]=a[i];
        }
        rmin[n+1]=1000000000;
        for(int i=n;i>=1;i--)
        {
            rmin[i]=min(rmin[i+1],a[i]);
        }
        sort(b+1,b+n+1);
        for(int i=1;i<=n;i++)
        {
            if(lmax[i]==a[i]&&rmin[i]==a[i]&&a[i]==b[i])r++;//左边最大是它,右边最小是它
        }
        if(r>=3||(r==2&&(a[1]==b[1]||a[n]==b[n])))printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}




题目描述

A d-tree is a tree of degree d. A complete tree is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Given the pre-order traversal sequence of a complete d-tree, you are supposed to obtain its level-order traversal sequence. And more, for any given node, you must be able to output the bottom-up path from this node to the root.

输入

Each input file contains one test case. For each case, the first line gives two positive integers: N (≤50) and d (2≤d≤5), which are the total number of nodes in the tree, and the tree’s degree, respectively. Then in the next line, N integer keys (≤100) are given as the pre-order traversal sequence of the tree. Finally K (≤N) and K positions are given, where each position is the index of a key in the level-order traversal sequence, starting from 0.

All the numbers in a line are separated by a space.

输出

For each case, first print in one line the level-order traversal sequence of the complete d-tree. Then for each given position, print in a line the bottom-up path from this node to the root.

All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.

样例

9 3
91 71 2 34 10 15 55 18 7
3
5 7 3
91 71 15 7 2 34 10 55 18
34 71 91
55 15 91
7 91

解法

树的遍历:先序遍历,第一个数是根节点,第二个数是子树。
层序遍历
如何找到子节点: 从0开始!x为根,度为d,子节点序号k就等于x * d + i (i = 1,2,3……d)


C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,d,le[55],pre[55],p=0,k;
void dfs(int x)
{
    if(x>=n)return;
    le[x]=pre[p++];
    for(int i=1;i<=d;i++)
    {
        dfs(x*d+i);
    }
}
int main()
{
    cin>>n>>d;
    for(int i=0;i<n;i++)cin>>pre[i];
    dfs(0);
    for(int i=0;i<n;i++)cout<<le[i]<<(i<n-1?" ":"\n");
    cin>>k;
    while(k--)
    {
        int x;
        cin>>x;
        while(x)
        {
            cout<<le[x]<<" ";
            x=(x-1)/d;
        }
        cout<<le[0]<<endl;
    }
    return 0;
} 



题目描述

Least Recently Used (LRU) cache scheme is to remove the least recently used frame (the one hasn’t been used for the longest amount of time) when the cache is full and a new page is referenced which is not there in cache.

Your job is to implement this LRU cache scheme.

输入

Each input file contains one test case. For each case, the first line gives 2 positive integers N (≤1e4) and M (≤1e5) which are the size of the cache and the number of referenced page ID’s. Then M referenced page ID’s are given in the next line. A page ID is a number in the range [1,2e4]. All the numbers in a line are separated by a space.

输出

For each test case, output in a line the page ID’s in the order of their being removed from the cache. All the numbers in a line must be separated by 1 space, and there must be no extra space at the beginning or the end of the line.

It is guaranteed that at least one page will be removed.

样例

4 11
1 2 3 1 4 5 2 1 5 6 3
2 3 4 2

解法

队列,先进先出
1. 先进来的优先级最低,最先被输出,num若不为1则优先级提高
2. 要被移入的答案中的,是最靠前的num为1的数

头结点不一定是要被移走的,只有当头结点num为1的时候才要被移走


C++ 代码

#include <bits/stdc++.h>
using namespace std;
int v[20010],num[20010],c,n,m;
queue<int>q;
vector<int>r;
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x;
        scanf("%d",&x);
        if(c<n)
        {   //若输入的是队列中有的数,入队,此时队列中有多个与该数相同的数,但不改变cache的大小。
            q.push(x);
            if(num[x]==0)
            {   
                c++;
            }
            num[x]++;
        }
        else
        {
            if(num[x]==0)
            {   //处理num大于1的数,它们优先级最高,不可能被移走,将他们除去,但此时队列中仍有该数
                while(num[q.front()]!=1)
                {
                    num[q.front()]--;
                    q.pop();
                }
                //此时的头节点才是真正要被移走的点
                num[q.front()]--;
                r.push_back(q.front());
                q.pop();
            }
            //将输入的节点入队
            q.push(x);
            num[x]++;
        }
    }
    for(auto i=r.begin();i!=r.end();i++)
    {
        if(i!=r.begin())printf(" ");
        printf("%d",*i);
    }
    return 0;
} 



题目描述

The above question is commonly seen in a final exam of the course Data Structures. That is, given a graph G, you are supposed to tell if a sequence of vertices can be possibly obtained from any depth first search (DFS) on G.

Now it is your job to write a program which can give the answers automatically.

Note: it is required that each vertex must be visited once even if the graph is not connected. In the graph given by the sample input, if we start from vertex 4, then vertex 1 cannot be reached during this DFS, yet it can be the first vertex visited in the next DFS. Hence the 5th query 4 3 2 5 1 is possible.

输入

Each input file contains one test case. For each case, the first line contains 3 positive integers: N (≤1e3), M (≤1e4), and K (≤100), which are the number of vertices, the number of edges, and the number of queries, respectively. Then M lines follow, each gives an edge in the format:

输出

For each query, print in a line yes if the given sequence does correspond to a DFS sequence, or no if not.

样例

5 7 6
1 2
1 3
1 5
2 5
3 2
4 3
5 4
1 5 4 3 2
1 3 2 5 4
1 2 5 4 3
1 2 3 4 5
4 3 2 5 1
5 4 3 2 5
yes
yes
yes
no
yes
no

解法

DFS序列:经历dfs遍历的序列,必须遍历到最底层

合法性:从起点出发能够到达最底层,且不能有重复点!

  1. 能够按照检查序列遍历到达最底层,则必定为DFS序列,输出yes
  2. 按照序列无法遍历完的,若到达最底层,则检查未遍历完的点,合法则yes,否则输出no;若不能到达最底层,输出no。

总得来说,就是存在一个不能到达最底层的起点或者存在重复点就要输出no

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,m,k,a[1010][1010],vis[1010],flag=1;
vector<int>vec[1010];
queue<int>q;
set<int>s;
void dfs(int x)
{
    if(flag==0||q.empty())return;
    vis[x]=1;
    while(!q.empty())
    {
        if(a[x][q.front()]==1)
        {
            int y=q.front();
            q.pop();
            dfs(y);
        }
        else
        {
            for(int i=0;i<vec[x].size();i++)
            { //未到达最底层
                if(vis[vec[x][i]]==0)
                {
                    flag=0;
                    return;
                }
            }
            return;
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        a[x][y]=1;
        vec[x].push_back(y);
    }
    while(k--)
    {
        memset(vis,0,sizeof vis);
        flag=1;
        while(!q.empty())q.pop();
        s.clear();
        for(int i=0;i<n;i++)
        {
            int x;
            cin>>x;
            q.push(x);
            s.insert(x);
        }
        while(!q.empty())
        {   //可能存在未遍历完,但合法的点
            int y=q.front();
            q.pop();
            dfs(y);
        }       
        if(flag==0||s.size()!=n)cout<<"no"<<endl;
        else cout<<"yes"<<endl;
    }
    return 0;
} 



题目描述

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
    Both the left and right subtrees must also be binary search trees.
  • A binary tree with positive keys can be represented by an array, which stores the keys in level-order as in a complete tree, with all the NULL nodes represented by −1. For example, the following tree is stored in an array as { 40, 25, 60, -1, 30, -1, 80, -1, -1, 27 }.

输入

Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N integer keys (in the range (0, 100000)) are given in the next line. All the numbers in a line are separated by a space.

输出

For each test case, first print in a line YES if the sequence does correspond to a BST, or NO if not. Then print in the next line the inorder traversal sequence of that tree. It is guaranteed that the tree is non-empty.

All the numbers in a line must be separated by a space, and there must be no extra space at the beginning or the end of the line.

样例

10
40 25 60 -1 30 -1 80 -1 -1 27
YES
25 27 30 40 60 80

解题

二叉查找树的中序遍历是升序的

C++ 代码

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n,tree[1005],flag=1;
vector<int> v;
void inorder(int temp)
{
    if(temp>n) return;
    inorder(2*temp);//左子树
    if(tree[temp]!=-1)
        v.emplace_back(tree[temp]);
    inorder(2*temp+1);//右子树
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>tree[i];

    inorder(1);

    for(int i=1;i<v.size();i++)
        if(v[i]<v[i-1])
            flag=0;

    if(flag==1)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    cout<<v[0];
    for(int i=1;i<v.size();i++)
        cout<<" "<<v[i];
    return 0;
}




The task is simple: find the first K largest numbers from a given sequence of N integers, and output them in descending order.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers N and K (≤5). Then N integer keys

Output Specification:

For each test case, print in descending order the Kth largest numbers.

All the numbers in a line must be separated by a space, and there must be no extra space at the beginning or the end of the line.

Sample Input 1:

10 4
40 25 60 -15 30 -21 80 -1 -5 27

Sample Output 1:

80 60 40 30

Sample Input 2:

4 5
23 -17 99 1

Sample Output 2:

99 23 1 -17

算法

小端优先队列
优先队列:每次让优先级最高的先出队列
小根堆 :priority_queue<int,vector<int>,greater<int>> q;


#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int a[10];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,k,t;
    cin>>n>>k;
    if(k>n) k=n;
    if(n<=5)
    {
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        reverse(a,a+n);
        cout<<a[0];
        for(int i=1;i<k;i++)
            cout<<" "<<a[i];
    }
    else
    {
        priority_queue<int,vector<int>,greater<int>> q;
        for(int i=0;i<5;i++)
        {
            cin>>t;
            q.push(t);
        }
        for(int i=5;i<n;i++)
        {
            cin>>t;
            q.push(t);
            q.pop();
        }
        for(int i=4;i>=0;i--)
        {
            a[i]=q.top();
            q.pop();
        }
        cout<<a[0];
        for(int i=1;i<k;i++)
            cout<<" "<<a[i];
    }
    return 0;
}



题目描述

给你一个由小写拉丁字母组成的字符串 ss。我们定义 ss 的一个子串的存在值为这个子串在 ss 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 ss,求所有回文子串中的最大存在值。

输入格式

一行,一个由小写拉丁字母(a~z)组成的非空字符串 ss。

输出格式

输出一个整数,表示所有回文子串中的最大存在值。

算法

回文数(回文自动机)

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5+8;
typedef long long ll;

char S[N<<1],a[N];
int cnt[N];
ll ans;

struct node{
    int len,fail,son[26],siz;
    void init(int _len){
        memset(son,0,sizeof(son));
        fail = 0;
        len = _len;
    }
}tree[N];

ll num,last,L,R;

void init(){
    last = 0;
    ans = 0;
    num = 1;
    R = 1e5+7;
    tree[0].init(0);
    memset(S,-1,sizeof(S));
    tree[1].init(-1);
    tree[0].fail = 1;
}

int getfail(int p){
    while(S[R-tree[p].len - 1]!=S[R])  p = tree[p].fail;
    return p;
}

void Insert(int x){
    S[++R] = x;
    int cur = getfail(last);
    int now = tree[cur].son[x];
    if(!now){
        now = ++num;
        tree[now].init(tree[cur].len+2);
        tree[now].fail = tree[getfail(tree[cur].fail)].son[x];
        tree[cur].son[x] = now;
    }
    cnt[last=now]++;
}

ll Max(ll a,ll b){
    if(a>b) return a;
    else return b;
}

int main(){
    gets(a);
    int len = strlen(a);
    init();
    for(int i = 0 ; i < len ; i ++){
        Insert(a[i]-'a');
    }
    for(int i=num;i>=0;--i)
        cnt[tree[i].fail]+=cnt[i],ans=Max(ans,(ll)cnt[i]*(ll)tree[i].len);
    printf("%lld\n",ans);
}


分享 回文树

题目描述

维护字符串,可以执行以下操作(初始为空串)
1:前端插入一个字符
2:后端插入一个字符
3:查询不同本质回文串个数
4:查询所有回文串个数

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 3e5 + 8;
int s[N];

struct node{
    int len,fail,son[26],siz;
    void init(int _len){
        memset(son,0,sizeof(son));
        fail = siz = 0;
        len = _len;
    }
}tree[N];
ll num,last[2],ans,L,R;

void init(){
    last[0] = last[1] = 0;
    ans = 0; num = 1;
    L = 1e5 + 8, R = 1e5 + 7;
    tree[0].init(0);
    memset(s,-1,sizeof(s));
    tree[1].init(-1);
    tree[0].fail = 1;
}


int getfail(int p,int d){    //后缀链跳跃。复杂度可以看成O(1)
    if(d)                    //新字符在尾部
        while(s[R-tree[p].len-1] != s[R])
            p = tree[p].fail;
    else                     //新字符在头部
        while(s[L+tree[p].len+1] != s[L])
            p = tree[p].fail;
    return p;                //返回结点p
}

void Insert(int x,int d){    //往回文树上插入新结点,这个结点表示一个新回文串
    if(d) s[++R] = x;        //新字符x插到S的尾部
    else  s[--L] = x;        //新字符x插到S的头部
    int father = getfail(last[d],d);    //插到一个后缀的子结点上
    int now = tree[father].son[x];
    if(!now){                 //字典树上还没有这个字符,新建一个
       now = ++num;
       tree[now].init(tree[father].len+2);
       tree[now].fail = tree[getfail(tree[father].fail,d)].son[x];
       tree[now].siz = tree[tree[now].fail].siz+1;
       tree[father].son[x] = now;
    }
    last[d] = now;
    if(R-L+1 == tree[now].len)   last[d^1]=now;
    ans += tree[now].siz;

}

int main(){
    int op,n;
    while(scanf("%d",&n)!=EOF){
        init();
        while(n--){
            char c; scanf("%d",&op);
             if(op==1) scanf(" %c",&c), Insert(c-'a',0);
            if(op==2) scanf(" %c",&c), Insert(c-'a',1);
            if(op==3) printf("%lld\n",num-1);
            if(op==4) printf("%lld\n",ans);
        }
    }
    return 0;
}



题目描述

给出一个只由小写英文字符 a,b,c,d,…… 组成的字符串 S ,求 S 中最长回文串的长度。
字符串长度为 n。

输入格式

一行小写英文字符a,b,c,d,……组成的字符串 S。

Manancher算法(动态规划)

用法:最长回文字符串
利用回文的镜像也是回文,i和j镜像对称,那么P[i] = P[j]
关键:如何快速计算P?
P就是从该点的最大的回文串的半径。

S: $ # a # b # b # a # &

P[i]: 1 1 2 1 2 5 2 1 2 1 1

  1. 假设已经找到P[0]~p[i-1]
  2. R是最大右端点,C是该回文字符串的中心点
  3. 计算P[i]
    若i>=R:令P[i]=1,然后只能暴力中心扩展求P[i]
    若i<R:
    (1)j被C的回文串包含,P[i] = P[j] = P[2C-i],再用中心拓展法求P[i].
    (2)j不被C所包含, P[i] = w = R - i = C + P[c] - i,再用中心拓展法求P[i].

#include<bits/stdc++.h>

using namespace std;
const int N = 11000010;
char s[N] , t[N<<1];
int P[N<<1] ,n;

void manacher(){
    int R = 0, C ;
    n = strlen(t);
    for(int i = 1 ; i < n ; i ++){

        if(i < R) P[i] = min(P[(C<<1)-i] , P[C]+C-i);
        else P[i] = 1;
        //中心拓展法求P[i]
        while(t[i+P[i]] == t[i-P[i]]) P[i] ++;
        //P[i]是已求得的回文串,那么此时最大的右端点就是P[i]+i
        if(P[i] + i > R){
            R = P[i] + i;
            C = i;
        }
    }
}

int main(){
    gets(s);
    int len = strlen(s);
    for(int j = 0, i = 0 ; j < len ; j ++){
        if(j == 0){ 
            t[i ++] = '$';
            t[i ++] = '#';
            t[i ++] = s[j];
            t[i ++] = '#';
            }
        else if(j == len - 1){
            t[i ++] = s[j];
            t[i ++] = '#';
            t[i ++] = '&';
        }
        else{
            t[i ++] = s[j];
            t[i ++] = '#';
        }
    }

    manacher();
    int ans = 1;
    for(int i = 0 ; i < n ; i ++) ans = max(ans,P[i]);
    printf("%d",ans-1);

}