计蒜客NOIP2018模拟1

https://www.jisuanke.com/contest/1152

T1:最失败的一道题，其实就是道水题，好几种写法，一种都没想出来。

题意转化后就是：每个数可以选a[i]和a[i]-k，最后求使1,2,3,...,T都存在的最大的T+1和最多能让多少个数小于等于T。

为什么第一问可以转化成求有多少个数小于等于T呢？首先不大于k的怪物可以直接杀死，然后大于k的怪物显然当且仅当血量小于等于T时才可能被用第二种操作杀死，所以当T最大一定是第二问最优的情况。所以第二问做完后直接扫一边就是第一问的答案。

考虑第二问怎么求：

方法一：二分答案。二分T判断可行性即可，没有任何坑点。$O(n\log n)$

方法二：直接循环。c[]记录每个数有多少个。从1枚举，若 c[i]>0 则 c[i]-- 否则 c[i+k]--，某个数小于0了就终止循环。$O(n)$

方法三：若a[i]>k则连无向边<a[i],a[i]-k>否则连自环<a[i],a[i]>。考虑这个图的每个连通块，如果边数等于点数-1（也就是一棵树），则必然有一个数取不到（显然这个数要选最大的那个），否则块内所有数都能取到。并查集维护连通块即可。$O(n\alpha(n))$

方法四：继续方法三的思想，每个块dfs一遍就可以求出块内的点数和边数了。$O(n)$

前两种简直是无脑方法我竟然都没想到，后面两种应该是一个常用套路，以后发现数的范围也是$O(n)$级别的话就要从数的角度考虑了（比如说建图或生成函数做FFT）

方法一：

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=l; i<=r; i++)

 using namespace std;

 const int N=;

 int n,k,a[N],ans;

 bool b[N];

 int jud(int mid){

     rep(i,,mid+) b[i]=;

     rep(i,,n){

         if (a[i]<=k) { b[a[i]]=; continue; }

         if (a[i]>mid) { b[a[i]-k]=; continue; }

         if (!b[a[i]-k]) b[a[i]-k]=; else b[a[i]]=;

     }

     rep(i,,mid) if (!b[i]) return ;

     return ;

 }

 int main(){

     freopen("A.in","r",stdin);

     freopen("A.out","w",stdout);

     scanf("%d%d",&n,&k);

     rep(i,,n) scanf("%d",&a[i]);

     sort(a+,a+n+);

     if (!jud()){

         int s=;

         for (; s<n && a[s+]<=k; s++);

         printf("%d %d\n",s,);

         return ;

     }

     int L=,R=a[n]; ans=;

     while (L<=R){

         int mid=(L+R)>>;

         if (jud(mid)) ans=mid,L=mid+; else R=mid-;

     }

     int s=;

     for (; s<n && (a[s+]<=k || a[s+]-k<=ans); s++);

     printf("%d %d\n",s,min(n,ans+));

     return ;

 }

方法二：

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=l; i<=r; i++)

 using namespace std;

 const int N=;

 int n,k,ans,a[N],c[N];

 int main(){

     freopen("A.in","r",stdin);

     freopen("A.out","w",stdout);

     scanf("%d%d",&n,&k); int s=;

     rep(i,,n) scanf("%d",&a[i]),c[a[i]]++;

     while (){

         if (c[s]) c[s]--;

         else if (c[s+k]) c[s+k]--;

             else break;

         s++;

     }

     rep(i,,n) if (a[i]<=k || a[i]-k<=s-) ans++;

     printf("%d %d\n",ans,min(n,s));

     return ;

 }

方法四：

 #include<cstdio>

 #include<vector>

 #include<algorithm>

 #define rep(i,l,r) for (int i=l; i<=r; i++)

 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])

 using namespace std;

 const int N=;

 int n,k,ans,mx,cnt,tot,b[N],vis[N],bel[N],a[N],pe[N],pv[N],to[N],nxt[N],h[N];

 vector<int>V[N];

 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }

 void dfs(int x,int fa,int co){

     V[co].push_back(x); bel[x]=co; vis[x]=; pv[co]++;

     For(i,x) if ((k=to[i])!=fa && k!=x && !vis[k]) dfs(k,x,co);

 }

 int main(){

     freopen("A.in","r",stdin);

     freopen("A.out","w",stdout);

     scanf("%d%d",&n,&k); int s=;

     rep(i,,n) scanf("%d",&a[i]),mx=max(mx,a[i]);

     rep(i,,n) if (a[i]>k) add(a[i],a[i]-k),add(a[i]-k,a[i]); else add(a[i],a[i]),add(a[i],a[i]);

     rep(i,,mx) if (!vis[i]) tot++,dfs(i,,tot);

     rep(i,,tot) sort(V[i].begin(),V[i].end());

     for (int i=; i<=cnt; i+=) pe[bel[to[i]]]++;

     rep(i,,tot) if (pe[i]<pv[i]) b[V[i][V[i].size()-]]=;

     for (; !b[s]; s++);

     rep(i,,n) if (a[i]<=k || a[i]-k<=s-) ans++;

     printf("%d %d\n",ans,min(min(mx+,n),s));

     return ;

 }

T2：

首先参考[JSOI2017]原力，这是一个套路，但是只有80分。

考虑一种做法：先求出图的一棵生成树。假设三角形有至少一条边在树上，那么枚举一条非树边<u,v>，直接看fa[u]是否和v相邻即可。如果没有满足条件的边则说明这棵树上没有边在三角形上，删去所有树边。重复以上操作即可，复杂度$O(\frac{m^2}{n})$。

这个做法当n在4000左右时显然会很大，但这个时候直接bitset搞一下就可以了，复杂度$O(mn/64)$。

综合以上两种方法即可拿到满分。

80分：

#include<map>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define rep(i,l,r) for (int i=l; i<=r; i++)

typedef long long ll;

using namespace std;

const int N=,p=,p1=;

int n,m,u,v,cnt,tot,d[N],id[N],to[N<<],nxt[N<<],h[N],hash1[p1+],hash2[p1+],S[][];

void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }

void Hash(int u,int v){ int i=(u*p+v)%p1; for (; hash1[i]; i=(i+)%p1); if (!hash1[i]) hash1[i]=u,hash2[i]=v; }

int find(int u,int v){

    int i=(u*p+v)%p1;

    for (; hash1[i] && (hash1[i]!=u || hash2[i]!=v); i=(i+)%p1);

    if (!hash1[i]) return ; else return i;

}

int main(){

    freopen("B.in","r",stdin);

    freopen("B.out","w",stdout);

    scanf("%d%d",&n,&m); int si=(int)sqrt(n);

    if (n<=){

        rep(i,,m) scanf("%d%d",&u,&v),S[u][v]=,S[v][u]=;

        rep(i,,n-) rep(j,i+,n-) if (S[i][j]) rep(k,j+,n) if (S[j][k] && S[i][k])

            { printf("%d %d %d\n",i,j,k); return ; }

    }

    rep(i,,m) scanf("%d%d",&u,&v),add(u,v),add(v,u),d[u]++,d[v]++,Hash(min(u,v),max(u,v));

    rep(i,,n) if (d[i]>=si) id[++tot]=i;

    rep(i,,tot-) rep(j,i+,tot-) rep(k,j+,tot)

        if (find(id[i],id[j]) && find(id[j],id[k]) && find(id[i],id[k])){

            printf("%d %d %d\n",id[i],id[j],id[k]); return ;

        }

    rep(i,,n) if (d[i]<si){

        for (int j=h[i]; j; j=nxt[j])

            for (int k=nxt[j]; k; k=nxt[k]) if (find(to[j],to[k]) || find(to[k],to[j])){

                int x=i,y=to[j],z=to[k];

                if (x>y) swap(x,y);

                if (y>z) swap(y,z);

                if (x>y) swap(x,y);

                printf("%d %d %d\n",x,y,z); return ;

            }

    }

    return ;

}

方法二(bitset)：

#include<cstdio>

#include<bitset>

#include<algorithm>

#define rep(i,l,r) for (int i=l; i<=r; i++)

using namespace std;

const int N=;

int n,m,u,v,U[N],V[N];

bitset<>a[];

int main(){

    freopen("B.in","r",stdin);

    freopen("B.out","w",stdout);

    scanf("%d%d",&n,&m);

    rep(i,,m) scanf("%d%d",&u,&v),a[u].set(v),a[v].set(u),U[i]=u,V[i]=v;

    if (n<=){

        rep(i,,m){

            bitset<>C=a[U[i]]&a[V[i]];

            if (C.none()) continue;

            int s1=U[i],s2=V[i];

            rep(j,,n) if (C[j]){

                int s3=j;

                if (s1>s2) swap(s1,s2);

                if (s2>s3) swap(s2,s3);

                if (s1>s2) swap(s1,s2);

                printf("%d %d %d\n",s1,s2,s3);

                return ;

            }

        }

    }

    return ;

}

满分：

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

 const int N=,M=;

 int n,m,tot,a[][],h[M],x[M],y[M],h1[M],nxt1[M],fa[N],nxt[N],used[N],que[N];

 int add(int a, int b){

     x[++tot] = a; y[tot] = b; h[tot] = nxt[a]; nxt[a] = tot;

     int h = (a *  + b) % ; nxt1[tot] = h1[h]; h1[h] = tot;

     return ;

 }

 int findh(int a, int b){

     int h = (a *  + b) % ;

     int i = h1[h];

     while (i != ) {

         if ((a == x[i]) && (b == y[i]))  return ;

         else  i=nxt1[i];

     }

     return ;

 }

 void fin(int i, int j, int k){

     if (j > k) swap(j,k);

     if (i > j) swap(i,j);

     if (j > k) swap(j,k);

     printf("%d %d %d\n", i, j, k);

 }

 int alg1(){

     for (int i = ; i <= m; i++) {

         for (int j = ; j <= n / ; j++)

             if ((a[x[ * i - ]][j] & a[y[ * i - ]][j]) != ) {

                 int s = a[x[ * i - ]][j] & a[y[ * i - ]][j];

                 int k = ;

                 while (s > ) s = s / ,k++;

                 fin(x[ * i - ], y[ * i - ], j *  + k - );

                 return ;

             }

     }

     return ;

 }

 int alg2(){

     int round = ;

     while ( != ) {

         round++; int p = ,q = ;

         for (int i = ; i <= n; i++) {

             if (used[i] != round) que[++q] = i,fa[i] = i;

             while (p <= q) {

                 int ptr = nxt[que[p]];

                 while (ptr != ) {

                     if (used[y[ptr]] != round) {

                         que[++q] = y[ptr];

                         used[y[ptr]] = round;

                         fa[y[ptr]] = que[p];

                     }

                     ptr = h[ptr];

                 }

                 p++;

             }

         }

         for (int i = ; i <= tot; i++)

             if ((x[i] != fa[x[i]]) && (y[i] != fa[x[i]]) && (findh(y[i], fa[x[i]]) == )) {

                 fin(x[i], fa[x[i]], y[i]); return ;

             }

     }

     return ;

 }

 int main(){

     freopen("B.in","r",stdin);

     freopen("B.out","w",stdout);

     scanf("%d%d", &n, &m); tot = ;

     for (int i = ; i <= m; i++) {

         int p, q;

         scanf("%d%d", &p, &q);

         add(p, q); add(q, p);

         if (n <= ) {

             int c = q / ,d = q % ;

             a[p][c] += ( << d);

             c=p/,d=p%;

             a[q][c] += (<<d);

         }

     }

     if (n <= )  alg1(); else  alg2();

     return ;

 }

T3：考虑只有第一种概率模型的情况，从角的角度考虑。设同色三角形个数为$a$，异色为$b$，同色角个数x，异色$y$。则有$x=3a+b，y=2b$，解得$a=\frac{2x-y}{6}$

巴特西

计蒜客NOIP2018模拟1

最新文章

热门文章