題目連結（洛谷）
T1 比賽
T2 消毒
T3 旅行
代碼在本文末尾
比賽
- 主要考察：代碼實作
- 算法：記憶化搜尋+狀态壓縮
- 突破口：狀壓記憶化優化搜尋
- 正确思路：發現 n≤10 n ≤ 10 ，複雜度玄學，鎖定搜尋
一開始看到這題覺得比較像高斯消元之類的 可能被Day2洗腦了吧 但發現複雜度如果是 O(n3) O ( n 3 ) ，那資料就太松了
看到這題的 n≤10 n ≤ 10 就會往搜尋的方面想，但發現普通的搜尋會T，加上優化
發現現有的優化中（蒟蒻總共就隻會那麼幾種優化）記憶化在這題中優化效果比較明顯，那就用上記憶化，同時數組下表用一個29進制數表示，用map儲存即可
消毒
- 主要考察：思維靈活性
- 算法：dfs+二分圖比對
- 突破口：從二維平面入手
- 正确思路：考慮兩維的情況，發現第三維可以枚舉
這題是在三維長方體解決問題，根據以往的經驗，省選題從簡單情況入手深入
先考慮二維的情況：給定一個 n∗m n ∗ m 的矩形，給定一些要處理的點，每次可以標明一塊 a∗b a ∗ b 的矩形并處理内部節點，費用為 min(a,b) m i n ( a , b ) ，問最少花費多少可以将所有給定點處理
這個子問題是二分圖比對中經典的最小點覆寫模型
解釋一下：首先确定一點，每次隻取一長條（ 1∗a 1 ∗ a ）可以達到最優，因為如果是取一個 a∗b(a<b) a ∗ b ( a < b ) 的矩形，等價于處理 a a 條(1∗b)(1∗b)的矩形
然後問題等價于每次可以選取一列或一行，若 (x,y) ( x , y ) 處有需處理的點，則将 x x 向yy連線，最後求最小點覆寫即可，至此二維下的問題得以解決
但這種方法我不知道怎麼放到直接放到三維中去，因為蒟蒻并不會三分圖下的最小點覆寫
瞟一眼資料，發現資料 a·b·c≤5000 a · b · c ≤ 5000 ，這意味着 min(a,b,c)≤5000‾‾‾‾‾√3≈17 m i n ( a , b , c ) ≤ 5000 3 ≈ 17 ，則第三維可以使用枚舉的方法，枚舉這一層是使用1的代價直接削掉還是與其它層一起處理，對于與其它層一起處理可以将這些層的點縮到一個平面内（因為可以設定每次處理的寬為1，高為長方體的高）
旅行
- 主要考察：思維能力
- 算法：推導結論+優先隊列模拟
- 突破口：從特殊情況下入手
- 正确思路：考慮答案為零的情況，進而猜出結論
這題真心不會，以為是一個Dp加上一個什麼玄學優化之類的，看了幾篇題解問了dalao才勉強弄明白的
簡述一下dalao的解法：
将數列轉化成僅包含 ±1 ± 1 的數列，求字尾和（因為這樣可以快速判斷一段序列中的零一個數差）
将字尾和畫成一條函數圖像，感受一下：
考慮序列和為零的情況，發現如果旅途中有至少 m m 個點使得切分出來的數列為零則答案為零（顯然），否則為一（因為可以在函數圖像中上下距離為的一條水準線與函數的交界處取得，以将答案限制在1
考慮序列和為rr的情況，找到第一個字尾和等于零的位置，這個位置後面的部分就是上面的情況，最大值為1或0，不影響前面的答案，接下來隻取第一個元素到第一個字尾和為零的位置，很容易發現答案就是 ⌈rm⌉ ⌈ r m ⌉
至于字典序，則使用優先隊列模拟求解
代碼部分
比賽
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register
#define cl(x) memset(x,0,sizeof(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?(x):(-(x)))
template <typename _Tp> inline _Tp read(_Tp&x){
rg char c11=getchar(),ob=;x=;
while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),ob=;
while(isdigit(c11))x=x*+c11-'0',c11=getchar();if(ob)x=-x;return x;
}
const int N=;const ll p=;
ll a[N],b[N];
ll n,m,ans,top();
map <ll,ll> f[N];
ll calc(ll,ll,ll);
ll dfs(ll);
int main(){
read(n);
for(rg int i=;i<=n;++i)read(a[i]);
sort(a+,a+n+);
printf("%lld\n",dfs());
return ;
}
ll calc(ll x,ll y,ll now){
if(x>n)return y?:dfs(now+);
if(*(n-x+)<y)return ;
ll cnt=;
if(y>=)cnt=(cnt+calc(x+,y-,now))%p;
if(y&&a[x]){
--a[x];
cnt=(cnt+calc(x+,y-,now))%p;
++a[x];
}
if(a[x]>=){
a[x]-=;
cnt=(cnt+calc(x+,y,now))%p;
a[x]+=;
}
return cnt;
}
ll dfs(ll x){
if(x==n)return a[n]==;
top=;
for(rg int i=x;i<=n;++i)b[++top]=a[i];
sort(b+,b+top+);
ll tmp=;
for(rg int i=;i<=top;++i)tmp=tmp*+b[i];
if(f[x].find(tmp)!=f[x].end())return f[x][tmp];
else return f[x][tmp]=calc(x+,a[x],x);
}
消毒
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rg register
#define min(x,y) ((x)<(y)?(x):(y))
template <typename _Tp> inline _Tp read(_Tp&x){
rg char c11=getchar(),ob=;x=;
while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),ob=;
while(isdigit(c11))x=x*+c11-'0',c11=getchar();if(ob)x=-x;return x;
}
const int N=;
struct Edge{int v,nxt;}e[N];
int head[N],pos[][N],fr[N],bo[N],Floor[N];
int a,b,c,mi,Ans,m_,_;
inline void add(int u,int v){e[++_].v=v,e[_].nxt=head[u],head[u]=_;}
inline char find(int x){
for(rg int i=head[x];i;i=e[i].nxt)
if(!bo[e[i].v]){
bo[e[i].v]=;
if(!fr[e[i].v]||find(fr[e[i].v])){
fr[e[i].v]=x;
return ;
}
}
return ;
}
void work(int x){
for(rg int i=;i<=b;++i)head[i]=;
for(rg int i=;i<=c;++i)fr[i]=;
_=;
int ans=;
for(rg int i=;i<a;++i)
if(x&(<<i))Floor[i+]=,++ans;
else Floor[i+]=;
for(rg int i=;i<=m_;++i)
if(Floor[pos[][i]])
add(pos[][i],pos[][i]);
for(rg int i=;i<=b;++i){
for(rg int j=;j<=c;++j)bo[j]=;
ans+=find(i);
}
Ans=min(Ans,ans);
return ;
}
int main(){
int T,x;read(T);
while(T--){
m_=,Ans=;
read(a),read(b),read(c);
mi=min(a,min(b,c));
for(rg int i=;i<=a;++i)
for(rg int j=;j<=b;++j)
for(rg int k=;k<=c;++k)
if(read(x))
pos[][++m_]=i,pos[][m_]=j,pos[][m_]=k;
if(mi==b)swap(a,b),swap(pos[],pos[]);
if(mi==c)swap(a,c),swap(pos[],pos[]);
for(rg int i=;i<(<<a);++i)
work(i);
printf("%d\n",Ans);
}
return ;
}
旅行
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register
#define cl(x) memset(x,0,sizeof(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?(x):(-(x)))
#define Min(x,y) ((a[(x)])<(a[(y)])?(x):(y))
template <typename _Tp> inline _Tp read(_Tp&x){
rg char c11=getchar(),ob=;x=;
while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),ob=;
while(isdigit(c11))x=x*+c11-'0',c11=getchar();if(ob)x=-x;return x;
}
const int N=;
int n,m,opt[N],cnt[N],a[N],__();
struct node{int l,r,x;}t[N<<];
struct Queue{
int be,en,len;
inline int newnode(int l,int r,int x){t[++__].x=x,t[__].l=l,t[__].r=r;return __;}
inline void push_back(int x){
if(!len)be=en=newnode(,,x);
else t[en].r=newnode(en,,x),en=t[en].r;
++len;
}
inline bool empty(){return !len;}
inline int front(){return t[be].x;}
inline int back(){return t[en].x;}
inline void pop_back(){en=t[en].l;--len;}
inline void pop_front(){be=t[be].r;--len;}
inline void push(int x){
while(!empty()&&a[back()]>a[x])pop_back();
push_back(x);
}
}Qu[N<<],*qu=Qu+N,Q[N<<],*q=Q+N;
int main(){
read(n);read(m);
for(rg int i=;i<=n;++i)
read(a[i]),opt[i]=read(opt[i])?:-;
for(rg int i=n-;i;--i)opt[i]+=opt[i+];
for(rg int i=n;i;--i)
cnt[i]=cnt[i+]+(!opt[i]);
int r;
if(opt[]) r=(abs(opt[])-)/m+;
else r=cnt[]<m;
cnt[n+]=-;
if(!r)
for(rg int i=,j=;i<m;++i){
for(;cnt[j+]>=m-i;++j)
if(!opt[j+])q[].push(j);
printf("%d ",a[q[].front()]);
q[].pop_front();
}
else {
a[n+]=n+;int las();
for(rg int i=;i<=n;++i)
qu[opt[i]].push_back(i-);
for(rg int i=;i<m;++i){
int ans=n+;
for(rg int j=opt[las+]-r;j<=opt[las+]+r;++j){
if((int)(ceil((double)(abs(j))/(m-i)))>r)continue;
for(;!qu[j].empty()&&n-qu[j].front()>=m-i;qu[j].pop_front())
if(qu[j].front()>las)q[j].push(qu[j].front());
for(;!q[j].empty()&&q[j].front()<=las;q[j].pop_front());
if(!q[j].empty())
ans=Min(ans,q[j].front());
}
las=ans;
printf("%d ",a[ans]);
}
}
printf("%d\n",a[n]);
}