F.Niyaz and Small Degrees
挺sb的一题，为什么比赛时只过了4个呢
考虑当(x)固定的时候怎么做。显然可以树形DP：设(f_{u,i=0/1})表示只考虑(u)子树中的所有点和边，删边使得点(u)的度数(leq x-i)且除(u)以外的点度数都(leq x)的最小代价。转移时将(u)的所有儿子(v)一起考虑，先假设所有(u,v)之间的边都删掉，把(f_{u,i})加上(sum f_{v,0}+w_{u,v})，再考虑把一些边加回来。我们可以认为将(u,v)之间的边加回来的代价为(f_{v,1}-f_{v,0}-w_{u,v})，将所有儿子的代价排序，贪心地取前(k)小的边加回来就可以了。有一种特殊情况是代价为负的儿子个数(>k)，这种情况下显然取且仅取所有代价为负的儿子。
现在我们要对所有(xin[0,n-1])计算答案。可以发现，对于一个固定的(x)，所有度数(<=x)的点一定是合法的。所以我们可以把边分为三类：两个端点的度数都(>x)的边（称为实边），恰好一个端点的度数(>x)的边（称为虚边），两个端点的度数都(leq x)的边。
显然第三类边对答案没有影响。对于所有实边，如果我们只保留原树中的这些边，那么会形成若干个连通块。我们可以考虑对于每一个 存在度数(>x)的点 的连通块做一遍上述DP。这个DP的不同之处在于，每个点会连出若干条虚边，我们可能会删除一些虚边。这也很好做，只要DP到一个点时枚举它在实树上删掉了多少条与儿子的连边，就可以计算出至少要删除多少条与它相连的虚边，用数据结构维护与每个点相连的所有虚边，求前(k)小即可。
显然复杂度是(O(sum deg*log n)=O(nlog n))的。
具体实现的时候，肯定不能用(treap)求前(k)小。（你想写我也是资瓷的）。考虑从小到大枚举(x)，随着(x)的递增，(k)是递减的，所以可以用(multiset)维护前(k)小。对于一个固定的(x)，在DP前先枚举一遍所有度数(>x)的点，将这个点的(multiset)删到(size()<=k)。DP到一个点时，暴力将所有它与实树上的儿子之间的边加入(multiset)并动态维护前(k)小，DP完后撤销这些边即可。还有一个细节，如果每次DP时都暴力for每条边并判断它是否是实边，复杂度会退化为(O(n^2))，所以应该当发现一条边不再是实边后就删除这条边。
暂时是全CF最短代码
#include<bits/stdc++.h>
using namespace std;
const int N=250010;
typedef long long ll;
int gi() {
int x=0,o=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') o=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*o;
}
int to[N<<1],ww[N<<1],nxt[N<<1],tot=1,deg[N],h[N];
void adde(int u,int v,int w) {
to[++tot]=v,ww[tot]=w,nxt[tot]=h[u],h[u]=tot;
to[++tot]=u,ww[tot]=w,nxt[tot]=h[v],h[v]=tot;
++deg[u],++deg[v];
}
int n,fa[N],x,fw[N],son[N];
ll f[N][2],sum[N];
multiset<ll> s[N];
vector<int> Q[N],P[N];
void dfs(int u) {
for(int i=h[u];i;i=nxt[i]) {
int v=to[i];
if(v!=fa[u]) ++son[u],fa[v]=u,fw[v]=ww[i],dfs(v);
}
}
void dp(int u) {
f[u][0]=f[u][1]=0;
ll w,pre=sum[u];
vector<ll> ins,del;
for(int i=h[u],pre=-1;i;pre=i,i=nxt[i]) {
int v=to[i];
if(v!=fa[u]&°[v]>x) dp(v),f[u][0]+=f[v][1],f[u][1]+=f[v][1],s[u].insert(w=f[v][0]+ww[i]-f[v][1]),ins.push_back(w),sum[u]+=w;
else if(pre==-1) h[u]=nxt[i];
else nxt[pre]=nxt[i];
}
for(int i=1;~i;i--) {
int k=son[u]-x+i;
while(s[u].size()>k) sum[u]-=max(0ll,w=*s[u].rbegin()),s[u].erase(s[u].find(w)),del.push_back(w);
f[u][i]+=sum[u];
}
for(auto w:del) s[u].insert(w);
for(auto w:ins) s[u].erase(s[u].find(w));
sum[u]=pre;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=gi();
for(int i=1,u,v,w;i<n;i++) u=gi(),v=gi(),w=gi(),adde(u,v,w);
dfs(1);
for(int i=2;i<=n;i++) Q[min(deg[i],deg[fa[i]])].push_back(i);
for(int i=1;i<=n;i++)
for(int j=0;j<deg[i];j++) P[j].push_back(i);
for(x=0;x<n;x++) {
ll w;
for(auto u:Q[x]) s[fa[u]].insert(fw[u]),sum[fa[u]]+=fw[u];
for(auto u:P[x]) while(s[u].size()>son[u]-x+1) sum[u]-=max(0ll,w=*s[u].rbegin()),s[u].erase(s[u].find(w));
ll ans=0;
for(auto u:P[x]) if(deg[fa[u]]<=x) dp(u),ans+=min(f[u][1],f[u][0]+fw[u]);
printf("%lld ",ans);
}
return 0;
}
G.Get Ready for the Battle
答案有一个显然的下界(lceilfrac{sum{hp}}{n}
ceil)。既然是构造题就考虑怎样达到这个下界。
考虑依次将每个敌人打到恰好0hp。设(sum)表示(hp)的前缀和，则我们发现，打到第(i)个敌人时，在若干轮后，它会剩下(sum_imod n) hp。所以我们相当于要求，需要存在一个士兵的前缀使得这个前缀的攻击力之和为(sum_imod n)，这样我们就可以在下一轮中用这一个前缀攻击(i)，剩余士兵攻击后面的敌人，来满足恰好将这个敌人打到0hp。可以想到一种构造方式：设(a)为所有(sum_imod n)排序后的数组，(a_0=0,a_m=n)，则(ans_i=a_i-a_{i-1})。
这样可能会有一个问题，如果某一轮有多个敌人被打死，就可能存在一些敌人使得最后攻击它的士兵不是一段前缀。不过可以发现上面的构造方式一定能处理这种情况。
至于输出攻击方案，实现时为了方便，可以维护两个指针(i,j)，(i)指向当前正在考虑的敌人，(j)指向当前正在考虑的士兵，每次令(j=jmod m+1)即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int gi() {
int x=0,o=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') o=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*o;
}
int n,m,h[N],a[N],ans[N],tot=0;
int main() {
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=gi(),m=gi();
for(int i=1,s=0;i<=m;i++) s+=(h[i]=gi()),a[i]=s%n;
a[m]=n,sort(a+1,a+m+1);
for(int i=m;i;i--) a[i]-=a[i-1];
for(int i=1,j=1;i<=m;i++) while(h[i]>0) ans[++tot]=i,h[i]-=a[j],j=j%m+1;
while(tot%m) ans[++tot]=1;
printf("%d
",tot/m);
for(int i=1;i<=m;i++) printf("%d%c",a[i],"
"[i==m]);
for(int i=1;i<=tot;i++) printf("%d%c",ans[i],"
"[i%m==0]);
return 0;
}
H.Triple
更了，真香
这里记录一种可以解决(m(m>3))元组问题的方法吧。
暴力显然是对于每个元组做一次(fwt)求出点值表示，乘起来后(ifwt)还原。
设(a_{i,j})表示第(i)个元组的第(j)位，(x_i)为题目给你的第(i)个系数。
显然，每一个元组(fwt)后得到的数组最多包含(2^m)种不同的值，即(b_1x_1+b_2x_2+...+b_mx_m)，(b_iin{-1,1})。如果我们能对于(2^k)位中的每一位(p)，(2^m)种值中的每一种值(q)，求出有多少个元组满足(fwt)后第(p)位的值为(q)，那么就可以快速计算答案了。
有一个结论：((-1)^{popcount((iigoplus j)&k)}=(-1)^{popcount(i&k)}(-1)^{popcount(j&k)})。证明很简单，因为((iigoplus j))只有当某一位(i,j)都为(1)时才可能对(popcount)有影响，显然影响是偶数。
考虑枚举(m)个位置的一个子集，设这个子集为(s_1,s_2,...,s_t)。设数组(G)一开始都为(0)，对于每一个元组(i)，我们令(G_{a_{i,s_1}igoplus a_{i,s_2}igoplusdotsigoplus a_{i,s_k}}+1)。对(G)数组(fwt)，设(fwt)后得到的(G)数组为(G')。
考虑(2^k)位中的每一位(p)。设(b_{i,j})为第(i)个元组(fwt)后的数组的第(p)位中(x_j)的系数，即第(i)个元组(fwt)后第(p)位为(b_{i,1}x_1+b_{i,2}x_2+dots+b_{i,m}x_m)。根据(fwt)的原理，我们有((-1)^{popcount(a_{i,1}&p)}=b_{i,1},dots,(-1)^{popcount(a_{i,m}&p)}=b_{i,m})，即我们可以算出((-1)^{popcount((a_{i,s_1}igoplus a_{i,s_2}igoplus dots a_{i,s_m})&p)})的值。也就是说，我们知道(2^m)条信息，每一条信息形如 (fwt)后第(p)位为某个值的元组 在(G')数组中对第(p)位的贡献为多少。这样就能对第(p)位列出(2^m)个方程。如果这些方程线性无关，我们就可以解方程，就能知道对于(2^m)种值中的每一种值(q)，有多少个元组满足(fwt)后第(p)位的值为(q)。
可以证明这些方程是线性无关的。
证明：
将(b)中的正看作(0)，负看作(1)。设(A)为方程的系数矩阵，那么(A_{i,j}=(-1)^{popcount(i&j)})。证明方程线性无关，相当于证明(det(A) eq 0)。
考虑归纳证明。当(m=0)时显然成立。当(m>0)时，设(S)为(A)的前(2^{m-1})行，(2^{m-1})列形成的子矩阵，显然(A=left(egin{array}{cccc} S & S \ S & -S end{array} ight))。手动解这个行列式可以发现(det(A)=-2det(S)^2)，显然不为(0)。
考虑怎样快速解这样一个方程组。可以将它消成(left(egin{array}{cccc} S & 0 \ 0 & -2S end{array} ight))的形式，这样就只要递归解两个大小为(2^{m-1})的方程组即可。这样复杂度是(O(2^m*m))的。
总复杂度(O(2^{m+k}*(m+k)+n*2^m))。代码懒得写了。