23考研寄咯……
23年机考比22年，21年简单，整体趋势在逐年下降。T1, T2 都比较简单，T3难度过大，区分度不足。
- T1: 签到
- T2: 队列 + 优先队列
- T3: ？
传送门
T1 公司
签到题，懒得放题意了。
可能爆int，注意需要使用long long。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include <cstdio>
#define MAXN 100010
int a[MAXN],v[MAXN];
long long u[MAXN];
int main()
{
int n,m,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",a+i);
while(m--) scanf("%d%d",&x,&y),u[x]+=a[y],++v[x];
int ans=0;
for(int i=1;i<=n;++i) if(v[i]&&u[i]>1ll*a[i]*v[i]) ++ans;
printf("%d\n",ans);
}
|
T2 任务调度
维护一个队列，队列内每个元素有序号（按插入顺序严格递增）和权值，支持以下操作：
1 x：队尾插入权值为$x$的元素，序号自增。
2 x y：在序号为$y$的元素的正前方插入权值为$x$的元素，序号自增。
3：弹出队头（队列内序号最小元素），输出序号。
4：弹出队列内权值最大元素，输出序号。
使用链表直接维护队列。维护一个指针数组，下标为元素序号，指向对应元素。操作1直接维护队列及数组；操作2通过数组查询位置并插入；操作3直接维护队列及数组。难点在操作4。
使用一个优先队列维护（可能）在队列内的元素。维护一个status数组记录序号对应元素是否在队列中。每次操作1,2将元素放入优先队列中并标记入队，每次操作3,4更改status数组标记出队。每次操作4前，只要堆顶已出队便重复弹出，直到找到第一个在队中的元素，即可确定待弹出元素。每个元素只会进堆出堆一次，故算法时间复杂度正确。
时间复杂度$O(N \log N)$。解题用时40min。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 500010
struct Node
{
int idx, val;
Node *pre, *nxt;
};
int n,m;
int cnt,tot;
int status[MAXN];
Node *head,*tail,*p[MAXN];
priority_queue<pair<int,int> >q;
void insertBack(int x)
{
++tot;
if(cnt>=m)
{
printf("ERR\n");
return;
}
printf("%d\n",tot);
status[tot]=1;
q.push(make_pair(x,tot));
p[tot]=new Node();
p[tot]->idx=tot;
p[tot]->val=x;
++cnt;
if(cnt==1)
{
head=tail=p[tot];
p[tot]->nxt=p[tot]->pre=NULL;
}
else
{
tail->nxt=p[tot];
p[tot]->pre=tail;
p[tot]->nxt=NULL;
tail=p[tot];
}
}
void insertBefore(int x,int y)
{
++tot;
if(cnt>=m||status[y]!=1)
{
printf("ERR\n");
return;
}
printf("%d\n",tot);
status[tot]=1;
q.push(make_pair(x,tot));
p[tot]=new Node();
p[tot]->idx=tot;
p[tot]->val=x;
++cnt;
p[y]->pre->nxt=p[tot];
p[tot]->pre=p[y]->pre;
p[tot]->nxt=p[y];
p[y]->pre=p[tot];
if(head==p[y]) head=p[tot];
}
void popFirst()
{
if(!cnt)
{
printf("ERR\n");
return;
}
printf("%d\n",head->idx);
status[head->idx]=2;
head=head->nxt;
head->pre=NULL;
--cnt;
}
void popMax()
{
if(!cnt)
{
printf("ERR\n");
return;
}
while(!q.empty()&&status[q.top().second]!=1) q.pop();
int tmp=q.top().second;
q.pop();
status[tmp]=2;
printf("%d\n",tmp);
Node *tmpp=p[tmp];
if(tmpp->pre) tmpp->pre->nxt=tmpp->nxt;
else head=head->nxt;
if(tmpp->nxt) tmpp->nxt->pre=tmpp->pre;
else tail=tail->pre;
--cnt;
}
int main()
{
scanf("%d%d",&n,&m);
int mode,x,y;
while(n--)
{
scanf("%d",&mode);
if(mode==1)
{
scanf("%d",&x);
insertBack(x);
}
else if(mode==2)
{
scanf("%d%d",&x,&y);
insertBefore(x,y);
}
else if(mode==3) popFirst();
else if(mode==4) popMax();
}
}
|
T3 集合
8分嗯搜很好写，再往上就不会了（悲