Day1
一双木棋
由于$n,m\le 10$，可以考虑状态压缩
又因为某个点能放的前提是左边和上边都有棋子
所以表示轮廓线
$0$表示横边界，$1$表示竖边界
那么$3\times 3$棋盘（其他一样）初始状态就是$000111$，边界条件是$111000$
这样就可以每次根据轮廓线走，有拐角的时候就可以放棋子
设$w$表示轮廓线，从$0\rightarrow n+m-2$用$i$枚举每一位，w»i&1如果是$1$就是竖边界，$0$就是横边界
w»i&3如果$=1$说明没有拐角，即不可以放棋子
所以可以用$f$数组表示这个状态轮廓线到最后能获得最大的分数
把$A$走看出加分，$B$走看成减分
代码
# include<iostream>
# include<cstring>
# include<cstdio>
using namespace std;
int n,m;
int a[11][11],b[11][11];
int f[(((1<<10)-1)<<10)+1];
int read()
{
int x=0,f=1;
char ch=getchar();
for(;!isdigit(ch);f=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*f;
}
int dfs(int w,bool fl)
{
if(f[w]>-1e7) return f[w];
f[w]=fl?-1e8:1e8;
int xx=n,yy=0;
for(int i=0;i<n+m-1;++i)
{
if(w>>i&1) --xx;
else ++yy;
if((w>>i&3)!=1) continue;
if(fl) f[w]=max(f[w],dfs(w^(3<<i),fl^1)+a[xx+1][yy+1]);
else f[w]=min(f[w],dfs(w^(3<<i),fl^1)-b[xx+1][yy+1]);
}
return f[w];
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
a[i][j]=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
b[i][j]=read();
memset(f,128,sizeof(f));
f[((1<<n)-1)<<m]=0;
printf("%d",dfs((1<<n)-1,1));
return 0;
}
IIIDX
这道题$60$分还是很好拿的（那我也没拿到）……
可以发现编号之间的关系是一棵树
然后就可以贪心了
后序遍历这棵树，把从小到大排序的难度依次填入……然后就有$60$分
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cstdlib>
# include<algorithm>
using namespace std;
const int MAX=5e5+1;
struct p{
int x,y;
}c[MAX];
int n,num,cnt;
double m;
int a[MAX],h[MAX],ans[MAX];
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num;
}
int read()
{
int x=0,f=1;
char ch=getchar();
for(;!isdigit(ch);f=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*f;
}
void dfs(int x)
{
for(int i=h[x];i;i=c[i].x)
dfs(c[i].y);
ans[x]=a[cnt++];
}
int main()
{
n=read(),scanf("%lf",&m);
a[0]=-1e8;
for(int i=1;i<=n;++i)
a[i]=read();
sort(a,a+n+1,greater<int>());
for(int i=n;i>=1;--i)
add(i/m,i);
dfs(0);
for(int i=1;i<=n;++i)
printf("%d ",ans[i]);
return 0;
}
满分做法：
上面那种做法难度有相同的时候是错的
考虑用线段树维护排序后这个点向左最多能选多少个点
查询时二分搞一搞就行了
值得注意的是，搞这个点的时候，区间得加上ta父节点的$size-1$（但只用加一次）
但这样并没有什么卯月，还是$60$，因为重复的问题没有解决
可以用一个数组记录这个点向右有多少连续相同的跟这个点难度相同的数（注意是排序后）
然后每次询问出一个答案后就可以看ta向右最远能到达哪个点，并将那个点作为答案，这个点标记为选过的，以后向右延伸时应选这个点$-1$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cstdlib>
# include<algorithm>
# define mid (l+r>>1)
# define tl (k<<1)
# define tr (k<<1|1)
using namespace std;
const int MAX=5e5+1;
struct p{
int x,lazy;
}s[MAX<<2];
int n;
double m;
int siz[MAX],fa[MAX],d[MAX],a[MAX],ans[MAX];
int read()
{
int x=0,f=1;
char ch=getchar();
for(;!isdigit(ch);f=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*f;
}
void down(int k)
{
if(!s[k].lazy) return;
int f=s[k].lazy;
s[k].lazy=0;
s[tl].lazy+=f,s[tr].lazy+=f;
s[tl].x+=f,s[tr].x+=f;
}
void pus(int k)
{
s[k].x=min(s[tl].x,s[tr].x);
}
void build(int l,int r,int k)
{
if(l==r)
{
s[k].x=l;
return;
}
build(l,mid,tl);
build(mid+1,r,tr);
pus(k);
}
void change(int l,int r,int k,int L,int R,int dis)
{
if(l==L&&r==R)
{
s[k].x+=dis,s[k].lazy+=dis;
return;
}
down(k);
if(R<=mid) change(l,mid,tl,L,R,dis);
else if(L>mid) change(mid+1,r,tr,L,R,dis);
else
{
change(l,mid,tl,L,mid,dis);
change(mid+1,r,tr,mid+1,R,dis);
}
pus(k);
}
int ask(int l,int r,int k,int x)
{
if(l==r)
{
if(s[k].x>=x) return l;
else return l+1;
}
down(k);
if(s[tr].x>=x) return ask(l,mid,tl,x);
return ask(mid+1,r,tr,x);
}
int main()
{
n=read(),scanf("%lf",&m);
for(int i=1;i<=n;++i)
a[i]=read();
sort(a+1,a+1+n,greater<int>());
for(int i=1;i<=n;++i)
fa[i]=i/m,siz[i]=1;
for(int i=n;i>=1;--i)
{
siz[fa[i]]+=siz[i];
if(a[i]==a[i+1]) d[i]=d[i+1]+1;
}
build(1,n,1);
for(int i=1;i<=n;++i)
{
if(fa[i]&&fa[i]!=fa[i-1]) change(1,n,1,ans[fa[i]],n,siz[fa[i]]-1);
int tt=ask(1,n,1,siz[i]);
tt+=d[tt],++d[tt],tt-=d[tt]-1,ans[i]=tt;
change(1,n,1,tt,n,-siz[i]);
}
for(int i=1;i<=n;++i)
printf("%d ",a[ans[i]]);
return 0;
}
秘密袭击
不会
所以我们考虑暴力的方法
考虑树形$dp$，$f_{i,k}$表示点$i$作为第$k$大的点的方案数
然后就枚举每个点向下跑
状态转移方程挺好推的……就这样
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# define LL long long
using namespace std;
const int MAX=2e3+1,mod=64123;
int n,k,w;
vector<int> c[MAX];
int d[MAX];
LL f[MAX][MAX];
int read()
{
int x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void dfs(int x,int fa,int s)
{
if(d[x]>d[s]||(d[x]==d[s]&&s>x))
for(int i=0;i<k;++i)
f[x][i+1]=f[fa][i],f[x][i+1]%=mod;
else for(int i=1;i<=k;++i)
f[x][i]=f[fa][i],f[x][i]%=mod;
for(int i=0;i<c[x].size();++i)
if(c[x][i]!=fa) dfs(c[x][i],x,s);
for(int i=1;i<=k;++i)
f[fa][i]+=f[x][i],f[fa][i]%=mod;
}
int main()
{
n=read(),k=read(),w=read();
for(int i=1;i<=n;++i)
d[i]=read();
for(int i=1;i<n;++i)
{
int x=read(),y=read();
c[x].push_back(y),c[y].push_back(x);
}
LL ans=0;
for(int i=1;i<=n;++i)
{
int sum=0;
for(int j=1;j<=n;++j)
if(d[i]<d[j]||(d[i]==d[j]&&j<i)) ++sum;
if(sum<k-1) continue;
memset(f,0,sizeof(f));
f[i][1]=1;
for(int j=0;j<c[i].size();++j)
dfs(c[i][j],i,i);
ans+=(1ll*f[i][k]*d[i])%mod;
ans%=mod;
}
printf("%lld",ans);
return 0;
}
Day2
劈配
按编号遍历每个人，再按志愿从小到大遍历志愿，动态加边并判断加上后最大流是否$=1$
是就退出，不是就拆下加上的边并向下遍历
这是第一问，第二问一看就可以二分答案
每次二分调换一下再判断就行了
这里有个优化：因为二分每次都重建边很麻烦，可以存$0\rightarrow n-1$最优情况下的图，然后二分判断就可以直接在前一个图上面加边
考试的时候想了一个贪心网络流，感觉能得$60+$，结果脑抽加了一句这个志愿没出现过就输出$i$，然后只有$10$分QAQ
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<queue>
# include<vector>
using namespace std;
const int MAX=201,MAXN=602,inf=1e8;
struct p{
int y,dis,fl;
};
vector<p> c[MAX<<3],cc[MAX<<3][MAX<<3];
int T,C,n,m,t;
int s[MAX],d[MAXN],b[MAX],ans[MAX];
int gh[MAX][MAX];
int a[MAX][MAX][MAX];
int read()
{
int x=0,f=1;
char ch=getchar();
for(;!isdigit(ch);f=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*f;
}
void add(int x,int y,int dis)
{
c[x].push_back((p){y,dis,c[y].size()});
c[y].push_back((p){x,0,c[x].size()-1});
}
void cut(int x)
{
c[x].pop_back();
}
bool bfs()
{
queue<int> qu;
qu.push(0);
memset(d,0,sizeof(d));
d[0]=1;
while(!qu.empty())
{
int tt=qu.front();
qu.pop();
for(int i=0;i<c[tt].size();++i)
if(!d[c[tt][i].y]&&c[tt][i].dis)
{
d[c[tt][i].y]=d[tt]+1;
qu.push(c[tt][i].y);
}
}
return d[t];
}
int dfs(int x,int dix)
{
if(x==t||!dix) return dix;
int sum=0;
for(int i=0;i<c[x].size();++i)
{
int y=c[x][i].y,fl=c[x][i].fl;
if(d[y]==d[x]+1&&c[x][i].dis)
{
int dis=dfs(y,min(dix,c[x][i].dis));
if(dis)
{
sum+=dis;
dix-=dis;
c[x][i].dis-=dis;
c[y][fl].dis+=dis;
if(!dix) break;
}
}
}
if(!sum) d[x]=-1;
return sum;
}
int dinic()
{
int tot=0;
while(bfs()) tot+=dfs(0,inf);
return tot;
}
void work()
{
for(int i=1;i<=n;++i)
{
bool fl=0;
for(int j=1;j<c[i].size();++j)
if(c[c[i][j].y][c[i][j].fl].dis)
{
fl=1;
printf("%d ",(ans[i]=gh[i][c[i][j].y-n]));
break;
}
if(!fl) printf("%d ",m+1);
}
printf("\n");
}
bool Work(int mid)
{
for(int i=1;i<c[mid].size();++i)
if(c[mid][i].dis)
if(gh[mid][c[mid][i].y-n]<=s[mid]) return 1;
else return 0;
}
bool look(int mid)
{
for(int i=0;i<=2*n+m;++i)
c[i]=cc[mid-1][i];
c[t]=cc[mid-1][t];
for(int j=1;j<=s[mid];++j)
if(a[mid][j][0])
{
for(int l=1;l<=a[mid][j][0];++l)
add(mid,a[mid][j][l]+n,1);
int tot=dinic();
if(tot==1) return 1;
for(int l=1;l<=a[mid][j][0];++l)
cut(a[mid][j][l]+n),cut(mid);
}
return 0;
}
void Copy(int x)
{
for(int i=0;i<=2*n+m;++i)
cc[x][i]=c[i];
cc[x][t]=c[t];
}
int main()
{
T=read(),C=read();
while(T--)
{
n=read(),m=read();
t=n*2+m+1;
memset(ans,1,sizeof(ans));
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
memset(cc,0,sizeof(cc));
for(int i=1;i<=m;++i)
add(i+n,i+n+m,(b[i]=read())),add(i+n+m,t,inf);
for(int i=1;i<=n;++i)
add(0,i,1);
Copy(0);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
a[i][(gh[i][j]=read())][++a[i][gh[i][j]][0]]=j;
for(int j=1;j<=m;++j)
if(a[i][j][0])
{
for(int l=1;l<=a[i][j][0];++l)
add(i,a[i][j][l]+n,1);
int tot=dinic();
if(tot==1) break;
for(int l=1;l<=a[i][j][0];++l)
cut(a[i][j][l]+n),cut(i);
}
Copy(i);
}
for(int i=1;i<=n;++i)
s[i]=read();
work();
for(int i=1;i<=n;++i)
{
if(ans[i]<=s[i]) printf("0 ");
else
{
int l=1,r=i-1,Ans=-1;
while(l<=r)
{
int mid=(l+r>>1);
swap(a[i],a[i-mid]);
swap(s[i],s[i-mid]);
if(look(i-mid)) Ans=mid,r=mid-1;
else l=mid+1;
swap(a[i],a[i-mid]);
swap(s[i],s[i-mid]);
}
if(Ans!=-1) printf("%d ",Ans);
else printf("%d ",i);
}
}
printf("\n");
}
return 0;
}
下两道题都没看懂告辞
