计蒜客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(nlog 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(nalpha(n))$
方法四：继续方法三的思想，每个块dfs一遍就可以求出块内的点数和边数了。$O(n)$
前两种简直是无脑方法我竟然都没想到，后面两种应该是一个常用套路，以后发现数的范围也是$O(n)$级别的话就要从数的角度考虑了（比如说建图或生成函数做FFT）
方法一：
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=l; i<=r; i++) 4 using namespace std; 5 6 const int N=100100; 7 int n,k,a[N],ans; 8 bool b[N]; 9 10 int jud(int mid){ 11 rep(i,1,mid+1) b[i]=0; 12 rep(i,1,n){ 13 if (a[i]<=k) { b[a[i]]=1; continue; } 14 if (a[i]>mid) { b[a[i]-k]=1; continue; } 15 if (!b[a[i]-k]) b[a[i]-k]=1; else b[a[i]]=1; 16 } 17 rep(i,1,mid) if (!b[i]) return 0; 18 return 1; 19 } 20 21 int main(){ 22 freopen("A.in","r",stdin); 23 freopen("A.out","w",stdout); 24 scanf("%d%d",&n,&k); 25 rep(i,1,n) scanf("%d",&a[i]); 26 sort(a+1,a+n+1); 27 if (!jud(1)){ 28 int s=0; 29 for (; s<n && a[s+1]<=k; s++); 30 printf("%d %d ",s,1); 31 return 0; 32 } 33 int L=1,R=a[n]; ans=0; 34 while (L<=R){ 35 int mid=(L+R)>>1; 36 if (jud(mid)) ans=mid,L=mid+1; else R=mid-1; 37 } 38 int s=0; 39 for (; s<n && (a[s+1]<=k || a[s+1]-k<=ans); s++); 40 printf("%d %d ",s,min(n,ans+1)); 41 return 0; 42 }
方法二：
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=l; i<=r; i++) 4 using namespace std; 5 6 const int N=100100; 7 int n,k,ans,a[N],c[N]; 8 9 int main(){ 10 freopen("A.in","r",stdin); 11 freopen("A.out","w",stdout); 12 scanf("%d%d",&n,&k); int s=1; 13 rep(i,1,n) scanf("%d",&a[i]),c[a[i]]++; 14 while (1){ 15 if (c[s]) c[s]--; 16 else if (c[s+k]) c[s+k]--; 17 else break; 18 s++; 19 } 20 rep(i,1,n) if (a[i]<=k || a[i]-k<=s-1) ans++; 21 printf("%d %d ",ans,min(n,s)); 22 return 0; 23 }
方法四：
1 #include<cstdio> 2 #include<vector> 3 #include<algorithm> 4 #define rep(i,l,r) for (int i=l; i<=r; i++) 5 #define For(i,x) for (int i=h[x],k; i; i=nxt[i]) 6 using namespace std; 7 8 const int N=200100; 9 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]; 10 vector<int>V[N]; 11 12 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } 13 14 void dfs(int x,int fa,int co){ 15 V[co].push_back(x); bel[x]=co; vis[x]=1; pv[co]++; 16 For(i,x) if ((k=to[i])!=fa && k!=x && !vis[k]) dfs(k,x,co); 17 } 18 19 int main(){ 20 freopen("A.in","r",stdin); 21 freopen("A.out","w",stdout); 22 scanf("%d%d",&n,&k); int s=1; 23 rep(i,1,n) scanf("%d",&a[i]),mx=max(mx,a[i]); 24 rep(i,1,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]); 25 rep(i,1,mx) if (!vis[i]) tot++,dfs(i,0,tot); 26 rep(i,1,tot) sort(V[i].begin(),V[i].end()); 27 for (int i=1; i<=cnt; i+=2) pe[bel[to[i]]]++; 28 rep(i,1,tot) if (pe[i]<pv[i]) b[V[i][V[i].size()-1]]=1; 29 for (; !b[s]; s++); 30 rep(i,1,n) if (a[i]<=k || a[i]-k<=s-1) ans++; 31 printf("%d %d ",ans,min(min(mx+1,n),s)); 32 return 0; 33 }
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=1000100,p=100003,p1=1000003; int n,m,u,v,cnt,tot,d[N],id[N],to[N<<1],nxt[N<<1],h[N],hash1[p1+100],hash2[p1+100],S[210][210]; 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+1)%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+1)%p1); if (!hash1[i]) return 0; 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<=200){ rep(i,1,m) scanf("%d%d",&u,&v),S[u][v]=1,S[v][u]=1; rep(i,1,n-2) rep(j,i+1,n-1) if (S[i][j]) rep(k,j+1,n) if (S[j][k] && S[i][k]) { printf("%d %d %d ",i,j,k); return 0; } } rep(i,1,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,1,n) if (d[i]>=si) id[++tot]=i; rep(i,1,tot-2) rep(j,i+1,tot-1) rep(k,j+1,tot) if (find(id[i],id[j]) && find(id[j],id[k]) && find(id[i],id[k])){ printf("%d %d %d ",id[i],id[j],id[k]); return 0; } rep(i,1,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 ",x,y,z); return 0; } } return 0; }
方法二(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=100010; int n,m,u,v,U[N],V[N]; bitset<4010>a[4010]; int main(){ freopen("B.in","r",stdin); freopen("B.out","w",stdout); scanf("%d%d",&n,&m); rep(i,1,m) scanf("%d%d",&u,&v),a[u].set(v),a[v].set(u),U[i]=u,V[i]=v; if (n<=4000){ rep(i,1,m){ bitset<4010>C=a[U[i]]&a[V[i]]; if (C.none()) continue; int s1=U[i],s2=V[i]; rep(j,1,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 ",s1,s2,s3); return 0; } } } return 0; }
满分：
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 typedef long long ll; 5 using namespace std; 6 7 const int N=100100,M=4200100; 8 int n,m,tot,a[5000][200],h[M],x[M],y[M],h1[M],nxt1[M],fa[N],nxt[N],used[N],que[N]; 9 10 int add(int a, int b){ 11 x[++tot] = a; y[tot] = b; h[tot] = nxt[a]; nxt[a] = tot; 12 int h = (a * 30000 + b) % 999983; nxt1[tot] = h1[h]; h1[h] = tot; 13 return 0; 14 } 15 16 int findh(int a, int b){ 17 int h = (a * 30000 + b) % 999983; 18 int i = h1[h]; 19 while (i != 0) { 20 if ((a == x[i]) && (b == y[i])) return 1; 21 else i=nxt1[i]; 22 } 23 return 0; 24 } 25 26 void fin(int i, int j, int k){ 27 if (j > k) swap(j,k); 28 if (i > j) swap(i,j); 29 if (j > k) swap(j,k); 30 printf("%d %d %d ", i, j, k); 31 } 32 33 int alg1(){ 34 for (int i = 1; i <= m; i++) { 35 for (int j = 0; j <= n / 30; j++) 36 if ((a[x[2 * i - 1]][j] & a[y[2 * i - 1]][j]) != 0) { 37 int s = a[x[2 * i - 1]][j] & a[y[2 * i - 1]][j]; 38 int k = 0; 39 while (s > 0) s = s / 2,k++; 40 fin(x[2 * i - 1], y[2 * i - 1], j * 30 + k - 1); 41 return 0; 42 } 43 } 44 return 0; 45 } 46 47 int alg2(){ 48 int round = 0; 49 while (1 != 0) { 50 round++; int p = 1,q = 0; 51 for (int i = 1; i <= n; i++) { 52 if (used[i] != round) que[++q] = i,fa[i] = i; 53 while (p <= q) { 54 int ptr = nxt[que[p]]; 55 while (ptr != 0) { 56 if (used[y[ptr]] != round) { 57 que[++q] = y[ptr]; 58 used[y[ptr]] = round; 59 fa[y[ptr]] = que[p]; 60 } 61 ptr = h[ptr]; 62 } 63 p++; 64 } 65 } 66 for (int i = 1; i <= tot; i++) 67 if ((x[i] != fa[x[i]]) && (y[i] != fa[x[i]]) && (findh(y[i], fa[x[i]]) == 1)) { 68 fin(x[i], fa[x[i]], y[i]); return 0; 69 } 70 } 71 return 0; 72 } 73 74 int main(){ 75 freopen("B.in","r",stdin); 76 freopen("B.out","w",stdout); 77 scanf("%d%d", &n, &m); tot = 0; 78 for (int i = 1; i <= m; i++) { 79 int p, q; 80 scanf("%d%d", &p, &q); 81 add(p, q); add(q, p); 82 if (n <= 5000) { 83 int c = q / 30,d = q % 30; 84 a[p][c] += (1 << d); 85 c=p/30,d=p%30; 86 a[q][c] += (1<<d); 87 } 88 } 89 if (n <= 5000) alg1(); else alg2(); 90 return 0; 91 }
T3：考虑只有第一种概率模型的情况，从角的角度考虑。设同色三角形个数为$a$，异色为$b$，同色角个数x，异色$y$。则有$x=3a+b，y=2b$，解得$a=frac{2x-y}{6}$