T1

T1 的正确结论在考场上写出来，然后我却不是很确定。事后想一想还是那个数据范围的问题，其实先手为了避免损失，一定会先选小的，再选大的。排序直接做就可以。但似乎并不能严谨证明。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define int long long
#define ull unsigned long long
#define N 110
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

template<typename T> inline T Max(T a,T b){return a<b?b:a;}
template<typename T> inline T Min(T a,T b){return a<b?a:b;}

int n,a[N],f[N][2],Sum;

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);for(int i=1;i<=n;i++) read(a[i]),Sum+=a[i];
    sort(a+1,a+n+1);f[n][0]=-a[n];f[n][1]=+a[n];
    // printf("f[%d][0]=%d f[%d][1]=%d\n",n,f[n][0],n,f[n][1]);
    for(int i=n-1;i>=1;i--){
        if(a[i]>=4){
            f[i][0]=Min(-a[i]+f[i+1][1],-(a[i]-4)+4+f[i+1][0]);
            f[i][1]=Max(a[i]+f[i+1][0],(a[i]-8)+f[i+1][1]);
        }
        else{
            f[i][0]=f[i+1][1]-a[i];
            f[i][1]=f[i+1][0]+a[i];
        }
        // printf("f[%d][0]=%d f[%d][1]=%d\n",i,f[i][0],i,f[i][1]);
    }
    int all=Sum-f[1][0];
    int Ans2=all/2;int Ans1=Sum-Ans2;
    printf("%lld %lld\n",Ans1,Ans2);
    return 0;
}

T2

考虑启发式合并，合并两个并查集的时候，遍历小的那一个，容易发现不卡死等同于没有奇环，于是我们遍历一下小的那一个就行。注意传递 No 标记。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define int long long
#define uint unsigned int
#define ull unsigned long long
#define N 100010
#define M 200010
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

struct edge{
    int to,next;
    inline void Init(int to_,int ne_){
        to=to_;next=ne_;
    }
}li[N<<2];
int head[N],tail;

inline void Add(int from,int to){
    li[++tail].Init(to,head[from]);
    head[from]=tail;
}

int Fa[N],Size[N],Col[N];
int n,m,a[N];
bool No[N];

inline int Find(int x){assert(x&&x<=n);return x==Fa[x]?x:Fa[x]=Find(Fa[x]);}

inline void dfs(int k,int fa){
    Col[k]=Col[fa]^1;
    for(int x=head[k];x;x=li[x].next){
        int to=li[x].to;if(to==fa) continue;dfs(to,k);
    }
}

inline void Merge(int a,int b){
    // printf("a=%lld b=%lld\n",a,b);
    int faa=Find(a),fab=Find(b);
    if(Size[faa]<Size[fab]){swap(faa,fab);swap(a,b);}
    // printf("faa=%lld fab=%lld\n",faa,fab);
    if(faa==fab){
        // printf("Now Col[%lld]=%lld Col[%lld]=%lld\n",a,Col[a],b,Col[b]);
        if(Col[a]==Col[b]) No[faa]=1;
        return;
    }
    Size[faa]+=Size[fab];Fa[fab]=faa;
    Add(a,b);Add(b,a);
    if(No[faa]||No[fab]){
        No[faa]=1;return;
    }
    dfs(b,a);
    // printf("Col:");for(int i=1;i<=n;i++) printf("%lld ",Col[i]);puts("");
    // printf("Fa:");for(int i=1;i<=n;i++) printf("%lld ",Fa[i]);puts("");
    // printf("No:");for(int i=1;i<=n;i++) printf("%lld ",No[i]);puts("");
}

inline void Init(){
    read(n);read(m);for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) Fa[i]=i;
    for(int i=1;i<=n;i++) Size[i]=1;
}

inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

inline void Solve(){
    int op;read(op);
    // printf("op=%d\n",op);
    if(op==1){
        int x,c;read(x);read(c);a[x]=c;
    }
    else if(op==2){
        int x,y;read(x);read(y);if(x==y) return;
        Merge(x,y);
    }
    else{
        int x,y,v;read(x);read(y);read(v);
        // printf("x=%d y=%d v=%d\n",x,y,v);
        // printf("here\n");
        int faa=Find(x),fab=Find(y);
        // printf("faa=%d fab=%d\n",faa,fab);
        if(faa!=fab||No[faa]||No[fab]) return(void)puts("0");
        int fenzi=a[x]*v;int fenmu=a[y];int g=gcd(a[x]*v,a[y]);
        // printf("g=%d\n",g);
        fenzi/=g;fenmu/=g;
        if((Col[x]^Col[y])==1) printf("-");
        printf("%lld/%lld\n",abs(fenzi),abs(fenmu));
    }
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    Init();
    while(m--){
        // printf("m=%d\n",m);
        Solve();
    }
    return 0;
}

T3

我们直接枚举最大的那个数是哪个因数，后面的贪心选就可以，1e9 以内因数最大的数有 1344 个因数，所以不会 T。

#include<bits/stdc++.h>
#define N 10000010
using namespace std;

int n,d[N],c,a[N],tail,ans[N];

int t;

inline void Init(){
	scanf("%d%d",&n,&c);
}

int main(){
//	freopen("my.in","r",stdin);
//	freopen("my.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		Init();int i;tail=0;
		for(i=1;i*i<c;i++){
			if(c%i) continue;
			a[++tail]=i;a[++tail]=c/i;
		}
		if(i*i==c) a[++tail]=i;
		sort(a+1,a+tail+1);bool op=0;
		for(int i=1;i<=tail;i++){
			op=0;
			d[n]=a[i];int now=c/a[i];int g=i;
			for(int j=n-1;j>=1;j--){
				if(g<tail&&a[g+1]==a[g]+1) g++;
				while((now%a[g]||a[g]>d[j+1]+1)&&g>1) g--;
				d[j]=a[g];now/=a[g];
			}
			if(now!=1) op=1;
			for(int j=1;j<=n-1;j++) if(d[j]>d[j+1]+1){op=1;break;}
			if(op) continue;
			break;
		}
		for(int i=1;i<=n;i++) printf("%d ",d[i]+i-1);puts("");
	}
	return 0;
}

T4

我们考虑固定一个右端点，然后我们维护所有的左端点，满足这些点 \(\and\) 到右端点之和互不相同，容易发现这样的数不会超过 \(log\)，所以我们直接做就可以。用一颗线段树维护某个哪些左端点与当前右端点直接的 \(\and\) 为平方数，之前的不用删掉，回答询问直接做就可以。注意优先级。

#include<bits/stdc++.h>
#define N 200010
#define M 500010
#define int long long
using namespace std;

template<typename T> inline void read(T &x){
	x=0;int f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f*=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	x*=f;
}

struct Node{
	int Sum,len,lazy;
	inline void Clear(){Sum=len=lazy=0;}
}p[N<<2];

#define ls(k) k<<1
#define rs(k) k<<1|1
struct SegmentTree{
	inline void A(int k,int x){
		p[k].Sum+=x*p[k].len;p[k].lazy+=x;
	}
	inline void PushDown(int k){
		if(p[k].lazy){A(ls(k),p[k].lazy);A(rs(k),p[k].lazy);p[k].lazy=0;}
	}
	inline void PushUp(int k){
		p[k].Sum=p[ls(k)].Sum+p[rs(k)].Sum;
		p[k].len=p[ls(k)].len+p[rs(k)].len;
	}
	inline void Build(int k,int l,int r){
		p[k].Clear();if(l==r){p[k].len=1;return;}int mid=(l+r)>>1;Build(ls(k),l,mid);Build(rs(k),mid+1,r);PushUp(k);
	}
	inline void Add(int k,int l,int r,int z,int y,int x){
		if(l==z&&r==y){A(k,x);return;}
		PushDown(k);int mid=(l+r)>>1;if(y<=mid) Add(ls(k),l,mid,z,y,x);else if(z>mid) Add(rs(k),mid+1,r,z,y,x);else{Add(ls(k),l,mid,z,mid,x);Add(rs(k),mid+1,r,mid+1,y,x);}PushUp(k);
	}
	inline int Ask(int k,int l,int r,int z,int y){
		if(l==z&&r==y) return p[k].Sum;
		PushDown(k);int mid=(l+r)>>1;if(y<=mid) return Ask(ls(k),l,mid,z,y);else if(z>mid) return Ask(rs(k),mid+1,r,z,y);else return Ask(ls(k),l,mid,z,mid)+Ask(rs(k),mid+1,r,mid+1,y);
	}
}tr;

struct Rode{
	int l,r,val;
	inline Rode(){}
	inline Rode(int l,int r,int val) : l(l),r(r),val(val){}
};

struct Ques{
	int l,r,id;
	inline Ques(){}
	inline Ques(int l,int r) : l(l),r(r) {}
	inline bool operator < (const Ques &b)const{
		return r<b.r;
	} 
}ques[M];

int t,n,m,a[N],Ans[M];
Rode b[N];int tail;
vector<int> v[N];

inline void Init(){
	read(n);read(m);tr.Build(1,1,n);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=m;i++){
		read(ques[i].l);read(ques[i].r);ques[i].id=i;
	}
	for(int i=1;i<=m;i++) v[ques[i].r].push_back(i);
}

inline bool Check(int x){
	int xx=(int)sqrt(x);return xx*xx==x;
}

inline void UpdateB(int id){
//	printf("tail=%lld\n",tail);
	b[++tail]=Rode(id,id,a[id]);
	for(int i=2;i<=tail;i++){
		if((b[i].val&a[id])==(b[i-1].val&a[id])) b[i].l=-1;
	}
	int now=0;
	for(int i=1;i<=tail;i++){
		if(b[i].l!=-1) b[++now]=b[i];
		else b[now].r=b[i].r;
	}
//	printf("now=%d\n",now);
	tail=now;
	for(int i=1;i<=tail;i++){
		b[i].val=b[i].val&a[id];
		if(Check(b[i].val)) tr.Add(1,1,n,b[i].l,b[i].r,1);
	}
}

inline void Clear(){
	for(int i=1;i<=n;i++) vector<int>().swap(v[i]);
	tail=0;
}

inline void Solve(){
	for(int i=1;i<=n;i++){
		UpdateB(i);
		for(int j=0;j<v[i].size();j++){
			int now=v[i][j];
			Ans[ques[now].id]=tr.Ask(1,1,n,ques[now].l,ques[now].r);
		}
	}
}

inline void Print(){
	for(int i=1;i<=m;i++) printf("%lld\n",Ans[i]);
}

signed main(){
//	freopen("my.in","r",stdin);
//	freopen("my.out","w",stdout);
	read(t);
//	printf("here\n");
	while(t--){
		Init();Solve();Print();Clear();
	}
	return 0;
}