11.10正睿做题笔记

T1

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

代码：

#include
#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 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 inline T Max(T a,T b){return atemplate inline T Min(T a,T b){return aint 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
#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 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] // 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
#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 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 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
#define N 200010
#define M 500010
#define int long long
using namespace std;
template 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 }
}ques[M];
int t,n,m,a[N],Ans[M];
Rode b[N];int tail;
vector 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().swap(v[i]);
tail=0;
}
inline void Solve(){
for(int i=1;i<=n;i++){
UpdateB(i);
for(int j=0;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;
}