5241

ljh_lxy
bobo34
yxc的小迷妹
violet_garden

Judy_wfy
yxc
AcMerrr
MBH
Scimelan
77777777777

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.

### 输入

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

#### 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


## 解法

#### 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的数

#### 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。

#### 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


## 算法

#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;
}


## 算法

#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;
}


## Manancher算法（动态规划）

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);

}