2019 Wannafly Camp day7

自闭感受

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

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

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

上题解

E - 线性探查法

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

#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。（可以更优，直接枚举人）

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