今日看点
$\texttt{集训training 结束end 大家everyone 变硬hard}$
$\texttt{集训training 结束end 大家everyone 原神genshin}$
$\texttt{“T2 std怎么超时了，抓一个小朋友来当标程”}$
$\texttt{“T3 90分是怎么做到的”}$
$\texttt{“T3 输出-1？”}$
$\texttt{《睡一觉起来网好了》}$
$\texttt{《两个机房共用十兆带宽》}$
$\texttt{《2v5 优势在我》}$
$\texttt{《牛腩煲但是没吃牛肉》}$
A
根据每个数位有没有给他压成 [0,2^{10}) 的二进制数，第 i 位代表有没有 i。
然后一个数要算有相交的可以算没有相交的。
然后开个高位前缀和就可以了。
#include
#define CKE if(CHECK)
#define FRE if(FIL)
#define int long long
#define MX 1000005
using namespace std;
const int CHECK=0,FIL=1;int read();
int n,a,p[MX],w[1024];
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("training.in","r",stdin);
FRE freopen("training.out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
a=read();
while(a){
p[i]|=(1<<(a%10));
a/=10;
}w[p[i]]++;
}
for(int i=0;i<10;i++){
for(int j=0;j<1024;j++){
if(j&(1<<i)){
w[j]+=w[j^(1<<i)];
}
}
}
a=n*(n-1);
for(int i=1;i<=n;i++){
a-=w[1023^p[i]];}
printf("%lld\n",a/2);
return 0;
}
int read(){
int Ca=0;char Cr=' ';int Cf=1;
while(Cr'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}
B
std 你怎么超时了哈哈哈哈哈哈
人话：选子图，最大化最小度数。
一个状态想让答案变大肯定要删除度数最小的点。
线段树，支持单点修改，全局最小值，查找最小位置。
#include
#define CKE if(CHECK)
#define FRE if(FIL)
#define MX 100005
using namespace std;
const int CHECK=0,FIL=1;int read();
int n,m,res,d[MX],hs[MX];
vector v[MX];
class SegmentTree{
public:
int tr[MX*4];
void set(int t,int w){tr[t]=w;}
void Set(int t,int l,int r,int L,int w){
if(l>=r){set(t,w);return;}
int mid=(l+r)>>1;
if(L<=mid) Set(t<<1,l,mid,L,w);
else Set(t<<1|1,mid+1,r,L,w);
tr[t]=min(tr[t<<1],tr[t<=r) return l;
int mid=(l+r)>>1;
if(tr[t<<1]<tr[t<<1|1]) return Find(t<<1,l,mid);
else return Find(t<<1|1,mid+1,r);
}
}A;
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("end.in","r",stdin);
FRE freopen("end.out","w",stdout);
n=read();m=read();
while(m--){
int a=read();int b=read();
v[a].push_back(b);d[b]++;
v[b].push_back(a);d[a]++;
}
for(int i=1;i<=n;i++) A.Set(1,1,n,i,d[i]);
res=A.tr[1];
for(int i=1;i<n;i++){
int t=A.Find(1,1,n);hs[t]=1;
//cout<<t<<' ';
A.Set(1,1,n,t,1919810);
for(auto j:v[t]){
if(!hs[j]){
A.Set(1,1,n,j,--d[j]);}}
res=max(res,A.tr[1]);
//cout<<A.tr[1]<<'\n';
}printf("%d\n",res);
return 0;
}
int read(){
int Ca=0;char Cr=' ';int Cf=1;
while(Cr'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}
C
lxl：“90 分是怎么做到的”
lxl：“输出 -1？”
我是双 \log 爆草大神。
容易知道一定有一种编号方案使得任何时刻任意连通块编号连续。
所以操作一开并查集，操作二区间加。
操作三答案是 a现在的权值 减去 a合并前的权值。
那么怎么知道合并前的权值呢？
整！体！二！分！
不知道为啥有一个点输出-1，和 0 取 \max 就过了。
超绝 130 行代码。
#include
#define CKE if(CHECK)
#define FRE if(FIL)
#define MX 300005
#define GP pair
#define MP make_pair
using namespace std;
const int CHECK=0,FIL=1;int read();
int n,fd[MX],nw[MX];
unordered_map mp[MX];
int l[MX],r[MX],f[MX],res[MX];
int find(int i){return f[i]=(f[i]==i)?i:find(f[i]);}
//fa on tree
//f on bcj
int q,que[MX][3];
int RES[MX],X[MX],Y[MX],hcnt;
GP quer[MX];
vector v[MX];
class Tree{public:
int o[MX];
void add(int a,int b){while(a<=n){o[a]+=b;a+=(a&-a);}}
int sum(int a){int b=0;while(a){b+=o[a];a-=(a&-a);}return b;}
}A;
void dfs(int t){
fd[t]=1;
sort(v[t].begin(),v[t].end());
for(auto I:v[t]){
dfs(I.second);
}nw[t]=++hcnt;
}
void merge(int a,int b){
a=find(a),b=find(b);
l[a]=min(l[a],l[b]);
r[a]=max(r[a],r[b]);
f[b]=a;
}
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("everyone.in","r",stdin);
FRE freopen("everyone.out","w",stdout);
n=read();q=read();
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=q;i++){
int a=0,b=0;
que[i][0]=read();
a=que[i][1]=read();
if(que[i][0]!=2){
b=que[i][2]=read();}
if(que[i][0]==1){
a=find(a);b=find(b);
if(a==b) continue;
//swap(a,b);
v[b].push_back(MP(-i,a));
f[a]=b;
//cout<<a<<' '<<b<<'\n';
}
}
//return 0;
//编号
for(int i=1;i<=n;i++){
if(!fd[i]) dfs(find(i));
}hcnt=0;
//return 0;
//
for(int i=1;i<=n;i++){
l[i]=r[i]=nw[i];
f[i]=i;
//cout<<i<"<<nw[i]<<'\n';
}
for(int i=1;i<=q;i++){
int op=que[i][0];
int a=que[i][1];
int b=que[i][2];
if(op==1){
merge(a,b);
mp[a][b]++;
mp[b][a]++;
}else if(op==2){
a=find(a);
//cout<<l[a]<<' '<<r[a]<<'\n';
A.add(l[a],1);
A.add(r[a]+1,-1);
}else{
if(find(a)!=find(b)){continue;}
res[i]=A.sum(nw[a])+mp[a][b];
hcnt++,X[i]=1,Y[i]=i,RES[i]=0;
//cout<<i<<" init "<<res[i]<>1,i);
}
if(!hcnt) break;
sort(quer+1,quer+1+hcnt);
int pl=1;
for(int i=1;i<=n;i++){
l[i]=r[i]=nw[i];
f[i]=i;A.o[i]=0;
}
for(int i=1;i<=q;i++){
int op=que[i][0];
int a=que[i][1];
int b=que[i][2];
if(op==1){
merge(a,b);
}else if(op==2){
a=find(a);
A.add(l[a],1);
A.add(r[a]+1,-1);
}
while(pl<=hcnt && quer[pl].first<=i){
int T=quer[pl].first;
int id=quer[pl++].second;
a=que[id][1],b=que[id][2];
if(find(a)==find(b)){
Y[id]=T-1;//cout<<id<<" tryWA "<<Y[id]<<'\n';
}else{
X[id]=T+1;//cout<<id<<" tryAC "<<X[id]<='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}
D
赛时没想出来，大悲。
把 m+q 个区间按左端点排序，从右往左扫。
扫到查询区间的时候计算答案。
这样的好处是选取的线段不会从左侧超出去。
$f_i$ 表示包含位置 $i$ 的区间的最小右端点（没有则为 $\infin$）。
那么扫到一个区间的时候可以合并的充要条件是 \forall i\in[l,r]，f_i\leq r。
所以维护 f，支持区间取最小值和区间求最大值，是容易的。
#include
#define CKE if(CHECK)
#define FRE if(FIL)
#define MX 500005
#define MT make_tuple
#define GT tuple
using namespace std;
const int CHECK=0,FIL=1;int read();
int n,m,q,x,y,k,res[MX];GT ww[MX*2];
class SegmentTree{public:
int tr[MX*4],lz[MX*4];
void set(int t,int w){
tr[t]=min(tr[t],w);
if(!lz[t]) lz[t]=w;
else lz[t]=min(lz[t],w);
}
void pd(int t){
if(!lz[t]) return;
set(t<<1,lz[t]);
set(t<=r) return;
int mid=(l+r)>>1;
build(t<<1,l,mid);
build(t<<1|1,mid+1,r);
}
void Set(int t,int l,int r,int L,int R,int w){
if(L<=l && r>1;pd(t);
if(L<=mid) Set(t<mid) Set(t<<1|1,mid+1,r,L,R,w);
tr[t]=max(tr[t<<1],tr[t<<1|1]);
}
int Max(int t,int l,int r,int L,int R){
if(L<=l && r>1,ans=0;pd(t);
if(L<=mid) ans=max(ans,Max(t<mid) ans=max(ans,Max(t<<1|1,mid+1,r,L,R));
return ans;
}
}A;
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("hard.in","r",stdin);
FRE freopen("hard.out","w",stdout);
n=read();m=read();q=read();
A.build(1,1,n);
for(int i=1;i<=m;i++){
x=read();y=read();
ww[++k]=MT(x,0,y);
}
for(int i=1;i=1;i--){
x=get(ww[i]),y=get(ww[i]);
int id=-get(ww[i]);
//cout<<x<<' '<<y<<' '<<id<<'\n';
if(id){
res[id]=(A.Max(1,1,n,x,y)<=y);
}else{
A.Set(1,1,n,x,y,y);
}
}
for(int i=1;i<=q;i++) printf(res[i]?"YES\n":"NO\n");
return 0;
}
int read(){
int Ca=0;char Cr=' ';int Cf=1;
while(Cr'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}