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}$