游记：https://www.cnblogs.com/gmh77/p/12005426.html

D1D2没来

D3T1

D4T1

题解：

线性基，由于b不会重所以先选b大的

如果b相同a相反那么就随便选顺序考虑 正选 都不选/同时选 负选 三种情况，高斯消元判断

也许吧反正我直接丢就过了

线性基可以用bitset优化

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define abs(x) ((x)>0?(x):-(x))
#define max(a,b) (a>b?a:b)
using namespace std;

struct type{
    long long s;
    int id;
} A[71];
int a[71];
int b[71];
long long s[71];
bitset<71> c[200001];
bitset<71> C[200001];
bool bz[71];
bitset<71> f[71];
bitset<71> S;
int n,m,i,j,k,l;
long long ans;
char ch;

bool cmp(type a,type b)
{
    return a.s>b.s;
}

long long qpower(long long a,int b)
{
    long long ans=1;
    
    while (b)
    {
        if (b&1)
        ans=ans*a;
        
        a=a*a;
        b>>=1;
    }
    
    return ans;
}

void dg(int t,long long sum)
{
    int i;
    
    if (t>n)
    {
        ans=max(ans,sum);
        return;
    }
    
    dg(t+1,sum);
    
    fo(i,1,m)
    if (c[t][i])
    {
        if (!bz[i])
        sum+=s[i];
        else
        sum-=s[i];
        
        bz[i]=!bz[i];
    }
    dg(t+1,sum);
    
    fo(i,1,m)
    if (c[t][i])
    bz[i]=!bz[i];
}

int main()
{
//  freopen("a.in","r",stdin);
    
    scanf("%d%d",&n,&m);
    fo(i,1,n)
    {
        fo(j,1,m)
        {
            ch=getchar();
            while (ch!='0' && ch!='1')
            ch=getchar();
            
            c[i][j]=ch=='1';
        }
    }
    fo(i,1,m)
    {
        scanf("%d%d",&a[i],&b[i]);
        s[i]=a[i]*qpower(3,b[i]);
        
        A[i]={abs(s[i]),i};
    }
    
    sort(A+1,A+m+1,cmp);
    
    fo(j,1,m)
    {
        fo(i,1,n)
        C[i][j]=c[i][A[j].id];
    }
    
    if (n<=20)
    {
        dg(1,0);
        printf("%lld\n",ans);
    }
    else
    {
        fo(i,1,n)
        {
            S=C[i];
            
            fo(j,1,m)
            if (S[j])
            {
                if (!bz[j])
                {
                    bz[j]=1;
                    f[j]=S;
                    break;
                }
                else
                S^=f[j];
            }
        }
        
        S=0;
        fo(i,1,m)
        if (bz[i] && (!S[i] && a[A[i].id]==1 || S[i] && a[A[i].id]==-1))
        S^=f[i];
        
        fo(i,1,m)
        if (S[i])
        ans+=s[A[i].id];
        
        printf("%lld\n",ans);
    }
}

D4T2

不会

D4T3

题解：

构造题，考虑点分治

每次考虑经过分治中心的路径，使得经过这个点的路径满足条件

一次分治会把一棵树分成两棵树，让从一棵树到另一棵树的路径合法

把同一层的分治中心拉出来，对于从一个中心出发往一棵树的边的边权设为+wi，往另一棵树的设为-wi，暴力跑即可

可以发现这样会使得两棵树之间的路径满足，并且其他的路径不会超过最大值（|全加 or 全减|>=|有加有减|）

对于划分子树，可以使一棵子树的大小尽量接近1/3原树大小，这样可以满足m<=16的限制

具体的实现，每次把一棵子树加到原子树中，若新子树大小<1/3原树则直接加（因为不会跳过2/3），否则就把该树单独作为一棵子树向下分治

对于边权的赋值，如果u-->v的权为+w，则v-->u的边权为-w

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;

int p[17];
int a[2002][3];
int ls[1001];
int size[1001];
bool bz[2002];
int Ans[1001][17];
int b[17][2002];
int c[17][1001];
int C[17];
int a2[17][1001];
int b2[17][1001];
int A[17];
int B[17];
int n,i,j,k,l,len,x,y,z,mn,mn2,ans,num,TOT,tot2;

bool cmp(int x,int y)
{
    return size[a[x][0]]<size[a[y][0]];
}

void New(int x,int y,int z)
{
    ++len;
    a[len][0]=y;
    a[len][1]=ls[x];
    a[len][2]=z;
    ls[x]=len;
}

void dfs1(int Fa,int t)
{
    int i;
    size[t]=1;
    
    for (i=ls[t]; i; i=a[i][1])
    if (a[i][0]!=Fa && !bz[i])
    {
        dfs1(t,a[i][0]);
        size[t]+=size[a[i][0]];
    }
}

void dfs2(int Fa,int t,int Size)
{
    int i,mx=Size;
    
    for (i=ls[t]; i; i=a[i][1])
    if (a[i][0]!=Fa && !bz[i])
    {
        dfs2(t,a[i][0],Size+(size[t]-size[a[i][0]]));
        mx=max(mx,size[a[i][0]]);
    }
    
    if (mx<mn)
    mn=mx,mn2=t;
}

void dfs3(int T,int Fa,int t,int s)
{
    int i;
    
    for (i=ls[t]; i; i=a[i][1])
    if (a[i][0]!=Fa && !bz[i])
    {
        b[T][i]=a[i][2]*s;
        b[T][i^1]=-a[i][2]*s;
        
        dfs3(T,t,a[i][0],s);
    }
}

void dfs4(int Fa,int t,int sum)
{
    int i;
    
    Ans[t][l]=sum;
    
    for (i=ls[t]; i; i=a[i][1])
    if (a[i][0]!=Fa)
    dfs4(t,a[i][0],sum+b[l][i]);
}

void work(int T,int t)
{
    int i,Tot=0,Sz,sum=0,sz1,sz2;
    
    ans=max(ans,T);
    
    dfs1(0,t);
    mn=2133333333;
    dfs2(0,t,0);
    
    t=mn2;
    Sz=size[t]/3;
    
    C[T]=0;
    for (i=ls[t]; i; i=a[i][1])
    if (!bz[i])
    c[T][++C[T]]=i;
    
    if (!C[T]) return;
    
    sort(c[T]+1,c[T]+C[T]+1,cmp);
    
    if (size[c[T][C[T]]]>=Sz)
    {
        A[T]=C[T]-1;B[T]=1;
        fo(i,1,C[T]-1)
        a2[T][i]=c[T][i];
        b2[T][1]=c[T][C[T]];
    }
    else
    {
        A[T]=B[T]=0;
        fo(i,1,C[T])
        {
            sum+=size[a[c[T][i]][0]];
            a2[T][++A[T]]=c[T][i];
            
            if (sum>=Sz)
            break;
        }
        fo(i,i+1,C[T])
        b2[T][++B[T]]=c[T][i];
    }
    
//  ---
    
    dfs1(0,t);
    if (A[T] && B[T])
    {
        sz1=size[a[a2[T][A[T]]][0]];
        sz2=size[a[b2[T][B[T]]][0]];
        
        fo(i,1,B[T]) bz[b2[T][i]]=bz[b2[T][i]^1]=1;
        dfs3(T,0,t,-1);
        if (A[T]>1 || sz1>1)
        work(T+1,t);
        fo(i,1,B[T]) bz[b2[T][i]]=bz[b2[T][i]^1]=0;
        
        fo(i,1,A[T]) bz[a2[T][i]]=bz[a2[T][i]^1]=1;
        dfs3(T,0,t,1);
        if (B[T]>1 || sz2>1)
        work(T+1,t);
        fo(i,1,A[T]) bz[a2[T][i]]=bz[a2[T][i]^1]=0;
    }
}

int main()
{
//  freopen("c.in","r",stdin);
//  freopen("c.out","w",stdout);
    
    p[0]=1;
    fo(i,1,16)
    p[i]=p[i-1]*2;
    
    scanf("%d",&n);
    len=1;
    fo(i,2,n)
    {
        scanf("%d%d%d",&x,&y,&z);
        
        New(x,y,z);
        New(y,x,z);
    }
    
    work(1,1);
    
    fo(l,1,ans)
    dfs4(0,1,0);
    
    printf("%d\n",ans);
    fo(i,1,n)
    {
        fo(j,1,ans)
        printf("%d ",Ans[i][j]);
        printf("\n");
    }
}

2019学军集训题解

原文：https://www.cnblogs.com/gmh77/p/12051260.html