秉承ACM团队合作的思想懒，这篇blog只有部分题解，剩余的请前往星感大神Star_Feel的blog食用（表示男神汉克斯更懒不屑于写我们分别代写了下...）
C. Cloud Computing
扫描线搞一搞区间（主席树也OK啊，只是空间玄学，主席树理论空间nlogn实际上开小那么10倍8倍没什么锅啊zzzz），对于权值建立权值线段树，然后记录每个权值出现的次数以及区间权值和，然后在线段树上二分求答案即。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=,M=;
struct node {
int lc,rc;ll c; ll sum;
} t[M]; int rt[N],cnt;
void add(int &u,int l,int r,int c,int p,int pp) {
if(u==) u=++cnt; t[u].c+=c; t[u].sum+=ll(c)*ll(pp);
if(l==r) return ; int mid=(l+r)/;
if(p<=mid) add(t[u].lc,l,mid,c,p,pp);
else add(t[u].rc,mid+,r,c,p,pp);
}
void Merge(int &u1,int u2) {
if(u1==) { u1=u2; return ; } if(u2==) return ;
t[u1].c+=t[u2].c; t[u1].sum+=t[u2].sum;
Merge(t[u1].lc,t[u2].lc); Merge(t[u1].rc,t[u2].rc);
}
int n,K,ys[];
ll find(int u,int l,int r,int k) {
if(t[u].c<=k) return t[u].sum;
if(l==r) return ll(k)*ll(ys[l]);
int mid=(l+r)/;
if(t[t[u].lc].c>=k) return find(t[u].lc,l,mid,k);
else return t[t[u].lc].sum+find(t[u].rc,mid+,r,k-t[t[u].lc].c);
}
int L[],R[],C[],P[],s[];
struct ls {
int x,id;
} A[];
bool cmp(ls n1,ls n2) { return n1.x<n2.x; }
int main() {
scanf("%d%d",&n,&K);
int m; scanf("%d",&m);
cnt=; memset(rt,,sizeof(rt));
int t=;
for(int i=;i<=m;i++) {
int l,r,c,p; scanf("%d%d%d%d",&L[i],&R[i],&C[i],&P[i]);
A[++t]=(ls){P[i],i};
}
sort(A+,A++t,cmp); int tot=;
for(int i=;i<=t;i++) {
if(A[i].x!=A[i-].x) tot++;
s[A[i].id]=tot; ys[tot]=A[i].x;
}
for(int i=;i<=m;i++) {
add(rt[L[i]],,tot,C[i],s[i],P[i]);
add(rt[R[i]+],,tot,-C[i],s[i],P[i]);
}
for(int i=;i<=n;i++) Merge(rt[i],rt[i-]);
ll ans=;
for(int i=;i<=n;i++) ans+=find(rt[i],,tot,K);
printf("%lld\n",ans);
return ;
}
C. Cloud Computing(主席树by_hanks_o)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL read()
{
LL x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(''<=ch&&ch<=''){x=x*+ch-'';ch=getchar();}
return x;
}
struct node
{
int l,r,lc,rc;LL c,s;
}tr[];int trlen;
void bt(int l,int r)
{
int now=++trlen;
tr[now].l=l;tr[now].r=r;
tr[now].lc=tr[now].rc=-;
tr[now].c=;tr[now].s=;
if(l<r)
{
int mid=(l+r)/;
tr[now].lc=trlen+;bt(l,mid);
tr[now].rc=trlen+;bt(mid+,r);
}
}
void change(int now,LL p,LL c)
{
if(tr[now].l==tr[now].r)
{
tr[now].c+=c;
tr[now].s=(LL)tr[now].l*tr[now].c;
return ;
} int mid=(tr[now].l+tr[now].r)/;
int lc=tr[now].lc,rc=tr[now].rc; if(p<=mid)change(lc,p,c);
else change(rc,p,c); tr[now].c=tr[lc].c+tr[rc].c;
tr[now].s=tr[lc].s+tr[rc].s;
}
LL findans(int now,LL k)
{
if(tr[now].c<=k)return tr[now].s;
if(tr[now].l==tr[now].r)return k*tr[now].l; int mid=(tr[now].l+tr[now].r)/;
int lc=tr[now].lc,rc=tr[now].rc; if(tr[lc].c>=k)return findans(lc,k);
else return tr[lc].s+findans(rc,k-tr[lc].c);
} struct line
{
int id;LL c,p;
line(){}
line(int ID,LL C,LL P){id=ID;c=C;p=P;}
}li[];int len;
bool cmp(line l1,line l2){return l1.id<l2.id;}
int main()
{
int n,k,m,l,r;LL c,p;
n=read(),k=read(),m=read();
for(int i=;i<=m;i++)
{
l=read(),r=read(),c=read(),p=read();
li[++len]=line(l,c,p);
li[++len]=line(r+,-c,p);
} LL ans=;int tp=;
sort(li+,li+len+,cmp);
trlen=;bt(,);
for(int i=;i<=n;i++)
{
while(tp<=len&&li[tp].id==i)change(,li[tp].p,li[tp].c),tp++;
ans+=findans(,k);
}
printf("%lld\n",ans);
return ;
}
C. Cloud Computing(扫描线)
D. Garbage Disposal
强行贪心，>K的直接就扔了，然后剩下的留到后面扔（直接并到后一天的垃圾里面），但是要判断一下今天剩下的还有没有包含前一天的，有的话只能加一个袋子
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=;
int a[N];
typedef long long ll;
int main() {
int n,k; scanf("%d%d",&n,&k);
ll ans=;
for(int i=;i<=n;i++) scanf("%d",&a[i]);
int last=;
for(int i=;i<n;i++) {
ans+=a[i]/k;
int now=a[i]%k;
if(a[i]-last>=now) { last=now; a[i+]+=last; }
else { last=; ans++; }
}
ans+=a[n]/k; if(a[n]%k!=) ans++; printf("%lld\n",ans);
return ;
}
D. Garbage Disposal(by_hanks_o)
G. Monsters and Potions
这就是一个O(n^4)的硬模拟，枚举集合点，不断重复枚举每个英雄，O(n)判断是否可达以及修改点权
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std; int p[],h[],dd[],d[];bool v[];
int aslen,as[];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)scanf("%d%d",&p[i],&h[i]);
for(int i=;i<=n;i++)scanf("%d",&dd[i]); for(int pos=;pos<=n;pos++)
{
bool bk=true;aslen=;
memset(v,false,sizeof(v));
memcpy(d,dd,sizeof(d));
while(bk==true)
{
bk=false;
for(int i=;i<=m;i++)
{
if(v[i]==true)continue;
if(p[i]>=pos)
{
bool flag=true;
int k=h[i];
for(int j=p[i];j>=pos;j--)
{
k+=d[j];
if(k<){flag=false;break;}
}
if(flag==true)
{
as[++aslen]=i;v[i]=true;bk=true;
for(int j=pos;j<=p[i];j++)d[j]=;
}
}
else
{
bool flag=true;
int k=h[i];
for(int j=p[i];j<=pos;j++)
{
k+=d[j];
if(k<){flag=false;break;}
}
if(flag==true)
{
as[++aslen]=i;v[i]=true;bk=true;
for(int j=p[i];j<=pos;j++)d[j]=;
}
}
}
}
if(aslen==m)
{
printf("%d\n",pos);
for(int i=;i<aslen;i++)printf("%d ",as[i]);
printf("%d\n",as[aslen]);
return ;
}
}
printf("-1\n");
return ;
}
G. Monsters and Potions
I. Privatization of Roads in Berland
这题搞了我一天。。%得头皮发麻（主要是没有官方题解啊qwq而且眼瞎没看到discuss有人发了）
首先，两条相同公司的边肯定是放在一起的，这样才能尽可能的让一个点周围的公司较少
（此处作出贡献对的是这个点只被1个公司的边连向的个数）
这样的话，对于每一条边，会对1个点作出贡献。
考虑对于du[i]<=k的点，它最多接受du[i]的贡献
对于k<du[i]<=2*k的点，我们最多让用k条边每个公司都出现一次，然后多出来的du[i]-k条边和前面的边匹配，那么单独的边的条数就是2*k-du[i]
du[i]>2*k必然无解
网络流一手，st连向边流量为1，边连向它连接的两点流量为1，表示它只能对其中一个点作出贡献，另一个点一定可以找到一条和它同个公司的边。点流向ed流量为最多接受的贡献，通过残余网络，需要判断一下每条边是否都用上了
对于输出方案，通过残余网络我们可以知道每条边选了哪个点，考虑到对于这个点我这条边上的公司是单独的，那另一边就是成对的，就让这条边到另一边去匹配
通过discuss我又了解到一种做法，对于k<du[i]<=2*k的点，我们必须找到至少(k-du[i])*2条边两两属于同一个公司，也就是相当于多重匹配问题？
同样是网络流，st连向边流量为1，边连向它连接的两点流量为1，表示它也是只能用于其中一个点的两两配对，点流向ed流量为(k-du[i])*2
这样的话，你还需要判断是否满流
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(''<=ch&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void write(int d)
{
if(d<){putchar('-');d=-d;}
if(d>=)write(d/);
putchar(d%+'');
} int n,m,K;
struct node
{
int x,y,c,next;
}a[];int len,last[];
void ins(int x,int y,int c)
{
len++;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len; len++;
a[len].x=y;a[len].y=x;a[len].c=;
a[len].next=last[y];last[y]=len;
}
int st,ed,h[],list[];
bool bt_h()
{
int head=,tail=;list[]=st;
memset(h,,sizeof(h));h[st]=;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(a[k].c>&&h[y]==)
{
h[y]=h[x]+;
list[tail++]=y;
}
}
head++;
}
if(h[ed]==)return false;
return true;
}
int findflow(int x,int f)
{
if(x==ed)return f;
int s=;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(a[k].c>&&h[y]==h[x]+&&s<f)
{
int t=findflow(y,min(a[k].c,f-s));
s+=t;a[k].c-=t;a[k^].c+=t;
}
}
if(s==)h[x]=;
return s;
} //-------------------------------------------dicnic------------------------------------ int u[],v[],du[];
bool check()
{
int c=;
for(int i=,k=;i<=m;i++,k+=)c+=a[k].c;
return c==m;
}
vector<int>vec[];
int as[];
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int T;
T=read();
while(T--)
{
n=read(),m=read(),K=read();
len=;memset(last,,sizeof(last));
st=n+m+,ed=n+m+;
memset(du,,sizeof(du));
for(int i=;i<=m;i++)
{
u[i]=read(),v[i]=read();
ins(st,i+n,);
du[u[i]]++,du[v[i]]++;
}
for(int i=;i<=m;i++)
ins(i+n,u[i],),ins(i+n,v[i],);
bool flag=false;
for(int i=;i<=n;i++)
{
if(du[i]<=K)ins(i,ed,du[i]);
else if(du[i]<=*K)ins(i,ed,*K-du[i]);
else
{
for(int i=;i<m;i++)putchar(''),putchar(' ');
putchar(''),puts("");
flag=true;break;
}
}
if(flag==true)continue; /*printf("\n");
for(int i=2;i<=len;i+=2)printf("%d %d %d\n",a[i].x,a[i].y,a[i].c);*/
int ans=;
while(bt_h())
{
ans+=findflow(st,(<<));
/*printf("\n");
for(int i=2;i<=len;i+=2)printf("%d %d %d\n",a[i].x,a[i].y,a[i].c);
printf("%d\n",ans);*/
}
if(!check())
{
for(int i=;i<m;i++)putchar(''),putchar(' ');
putchar(''),puts("");
continue;
} for(int i=;i<=n;i++)vec[i].clear();
for(int i=,k=+*m+;i<=m;i++,k+=)
{
if(a[k].c==)vec[u[i]].push_back(i);
else vec[v[i]].push_back(i);
}
int cnt=;
for(int i=;i<=n;i++)
for(int j=;j<vec[i].size();j++)
{
if(j%==)cnt++;
as[vec[i][j]]=cnt;
}
for(int i=;i<m;i++)write(as[i]),putchar(' ');
write(as[m]);puts("");
}
return ;
}
I. Privatization of Roads in Berland
J. Streets and Avenues in Berhattan
考虑一个性质，对于最后不方便度的贡献只会来自于1种字母，否则我们可以通过两个不同字母的行列交换满足这一条件
枚举这一个字母，因为其他的字母都可以全部放满了，对行进行背包，f[k]表示行有k个已经被命名是否可行
假如k可行，剩下的行就有n-k个，因为我们是i这个字母不放，剩下都可以放列，所以剩余列数就是m-(K-c[i]-k)
求剩余行和列乘积的最小值即可
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std; char ss[];
int c[];
bool f[];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m,K;
scanf("%d%d%d",&n,&m,&K);
scanf("%s",ss+);
memset(c,,sizeof(c));
for(int i=;i<=K;i++)c[ss[i]-'A'+]++; int ans=(<<);
for(int i=;i<=;i++)
{
memset(f,false,sizeof(f));f[]=true;
for(int j=;j<=;j++)
{
if(i==j||c[j]==)continue;
for(int k=n;k>=c[j];k--)f[k]|=f[k-c[j]];
} for(int k=;k<=n;k++)
if(f[k]==true)
{
int h=max(,n-k),l=max(,m-(K-c[i]-k));
if(h+l<=c[i])ans=min(ans,h*l);
}
}
printf("%d\n",ans);
}
return ;
}
J. Streets and Avenues in Berhattan
L. Odd Federalization
一道挺神的题，假如是考场做就只能暴力猜结论了？？
结论是一个图拆分成r个诱导子图并且满足每个点的度数都为偶数，r<=2
r=1明显直接做
r=2对于每个点都有0或1两种取值，若一个点度数为偶数，那么要满足条件的话所有它连向的点的权值异或和应该等于0
若为奇数，则所有它连向的点的权值异或和再异或当前点的点权应该等于1
高斯消元解异或方程可踩此题
那么为什么呢，反证它一手
考虑对于高斯消元无解的情况，是出现0=1
右边是1证明产生选出来的这些柿子的点，有奇数个度数为奇数的点
左边是0证明所有参与了运算的点的系数都是偶数，那么也包括上面那奇数个度数为奇数的点，而剩下的点的度数都应该为偶数
用这个算出来，这些点组成的图的度数就是奇数了（偶*偶+奇*奇=奇数），然而对于无向图度数一定是偶数QWQ
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<bitset>
using namespace std; int n,m,du[];
bool check()
{
for(int i=;i<=n;i++)
if(du[i]%==)return false; printf("1\n");
for(int i=;i<n;i++)printf("1 ");
printf("1\n");
return true;
}
bitset<>s[];
void gauss()
{
int x=;
for(int j=;j<=n;j++)
{
for(int i=x;i<=n;i++)
if(s[i][j]==){swap(s[i],s[x]);break;}
if(s[x][j]==)continue; for(int i=;i<=n;i++)
{
if(i==x)continue;
if(s[i][j]==)s[i]^=s[x];
}
x++;
}
}
int as[];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)s[i].reset();
memset(du,,sizeof(du));
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
du[x]++,du[y]++;
s[x][y]=,s[y][x]=;
}
if(check())continue; for(int i=;i<=n;i++)
if(du[i]%==)s[i][i]=,s[i][n+]=;
gauss();
x=;
for(int j=;j<=n;j++)
{
if(s[x][j]==){as[j]=;continue;}
as[j]=s[x][n+]+;x++;
} printf("2\n");
for(int i=;i<n;i++)printf("%d ",as[i]);
printf("%d\n",as[n]);
}
return ;
}
L. Odd Federalization