Top

2019 Wannafly Camp day7


自闭感受

Camp第七天,上午xls给我们来了一波意识流图论讲解,我没有包图论所以听了些前面简单的,就去补day3,div1的数论了。经过群里一群大佬的点醒,发现自己傻逼了,明明可以直接用我div2的欧拉函数写法套上两个杜教加分块就能过,还整半天直接用莫比乌斯跑TT。

下午训练赛,感觉题目有点坑,数据范围好大,就写了两道签到题EG,队友没有怼出A题,晚上听解题发现自己D题推的离答案就差一两步了,结果放弃了。难受!!!快被自己菜哭了。

以后还是要多刷题啊,题量太少了,大佬们看啥都是原题,加油。

上题解

E - 线性探查法

按照哈希的操作进行逆操作,求出每一位最小数值,利用set维护压入的最小值。

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
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e3+20;
struct Node{
ll a;
int id;
bool operator < (const Node &oth) const{
return a < oth.a;
}
};
ll b[maxn];
int main(){
int n;
set<Node>st;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld",&b[i]);
if(b[i]%n==i)st.insert({ b[i] , i });
}
for(int i=1;i<n;i++){ //逆操作求解
Node f=*st.begin();
st.erase(st.begin());
b[f.id]=0; //已经插入
printf("%lld ",f.a);
int j=f.id;
while(!b[j])j=(j+1)%n; //找出应该放入的位置
int k=b[j]%n,flag=1; //实际位置
while(k!=j){
if(b[k]){
flag=0;
}
k=(k+1)%n;
}
if(flag)st.insert({b[j],j});
}
cout<<st.begin()->a<<endl;
}

G - 抢红包机器人

枚举每个红包的第一个抢的人为机器人,去暴力正反扫两遍红包序列,找出机器人,最后取枚举得到的数的min,最后看看是否有人未参与抢红包,有的话就直接输出1。(可以更优,直接枚举人)

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
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int a[120][120];
bool b[120],mp[120];
int nn[120];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int aa;
scanf("%d",&nn[i]);
for(int j=0;j<nn[i];j++){
scanf("%d",&a[i][j]);
b[a[i][j]]=1; //标记此人参与了抢红包
}
}
int cnt1=0;
for(int i=1;i<=n;i++){
if(b[i]==0)cnt1++;
}
if(cnt1)printf("1\n");
else {
int res=0,ans=999999;
for(int i=0;i<m;i++){
memset(mp,0,sizeof(mp));
mp[a[i][0]]=1;
res=0;

for(int j=0;j<m;j++){ //正扫
for(int k=nn[j]-1;k>=0;k--){
if(mp[a[j][k]]){
for(k--;k>=0;k--){
mp[a[j][k]]=1;
}
}
}
}
for(int j=m-1;j>=0;j--){ //反扫
for(int k=nn[j]-1;k>=0;k--){
if(mp[a[j][k]]){
for(k--;k>=0;k--){
mp[a[j][k]]=1;
}
}
}
}
for(int i=1;i<=n;i++)if(mp[i])res++;
ans=min(ans,res);
}
printf("%d\n",ans);
}
return 0;
}