联训题单 / CSP 集训杂题纪要
总览
| 题单 | 进度 | 备注 |
|---|---|---|
| 数据结构1 | 4/24 | 数据结构可爱捏 >_< |
| 搜索 模拟 | All Clear/10 | 搜索可爱捏 >_< |
| 数学1 | 0/11 | 数学不可爱捏 (`Д´) |
数据结构 1
STEP
读假题了，读成下面这样了：
给定 01 序列，每次单点修改，查询最长的字符相同的连续段长度
这不是一眼线段树经典板子题，分别维护左右区间信息以及合并处的信息，然后尝试在中间合并来更新答案
十五分钟光速打完拉下样例来发现不对，然后才发现自己读假题了
随后发现这俩题难道不是一个做法吗，只不过你要找的是 01010 这样的而不是 11111 这样的，所以你只有在不同的时候才能合并左右区间
所以改了个符号就过了
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,q;
namespace stree{
struct tree{
int l,r;
int maxsize;
int slize,srize;
bool lch,rch;
}t[800001];
#define tol (id*2)
#define tor (id*2+1)
#define mid(l,r) mid=((l)+(r))/2
void pushup(int id){
t[id].maxsize=
max({t[tol].maxsize,t[tor].maxsize,
t[tol].slize,t[tor].slize,
t[tol].srize,t[tor].srize,});
if(t[tol].rch!=t[tor].lch){
t[id].maxsize=max(t[id].maxsize,t[tol].srize+t[tor].slize);
}
if(t[tol].slize==t[tol].r-t[tol].l+1 and t[tol].rch!=t[tor].lch){
t[id].slize=t[tol].slize+t[tor].slize;
}
else{
t[id].slize=t[tol].slize;
}
if(t[tor].srize==t[tor].r-t[tor].l+1 and t[tol].rch!=t[tor].lch){
t[id].srize=t[tol].srize+t[tor].srize;
}
else{
t[id].srize=t[tor].srize;
}
t[id].lch=t[tol].lch;
t[id].rch=t[tor].rch;
}
void build(int id,int l,int r){
t[id].l=l;t[id].r=r;
if(l==r){
t[id].maxsize=t[id].slize=t[id].srize=1;
t[id].lch=t[id].rch=0;
return;
}
int mid(l,r);
build(tol,l,mid);
build(tor,mid+1,r);
pushup(id);
}
void change(int id,int p){
if(t[id].l==t[id].r){
int res=t[id].lch^1;
t[id].lch=t[id].rch=res;
return;
}
if(p<=t[tol].r) change(tol,p);
else change(tor,p);
pushup(id);
}
inline int ask(){
return t[1].maxsize;
}
}
int main(){
scanf("%d %d",&n,&q);
stree::build(1,1,n);
while(q--){
int x;
scanf("%d",&x);
stree::change(1,x);
printf("%d\n",stree::ask());
}
}
三元上升子序列
设 \(f2_i\) 表示以 \(i\) 结束的二元上升子序列个数，\(f3_i\) 表示以 \(i\) 结束的三元上升子序列个数，则不难有转移方程
\[f2_i=\sum_{\{j|j\lt i,a_j\lt a_i\}}1
\]
\[f3_i=\sum_{\{j|j\lt i,a_j\lt a_i\}}f2_j
\]
对于内层的处理直接开一个值域线段树，从前到后在对应值域处插入答案，查询直接插 \(1\) 到当前值前缀和即可
因为有俩方程所以开了两颗线段树
要注意判当 \(a_i=1\) 时 \(a_i-1=0\) 的问题，我懒得判了直接全部都加一了，整体平移答案不变
不开 long long 见祖宗
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[30001];
int f2[30001],f3[30001];
int ans=0;
struct stree{
struct tree{
int l,r;
int sum;
}t[400001];
#define tol (id*2)
#define tor (id*2+1)
#define mid(l,r) mid=((l)+(r))/2
void build(int id,int l,int r){
t[id].l=l;t[id].r=r;
if(l==r){
return;
}
int mid(l,r);
build(tol,l,mid);
build(tor,mid+1,r);
}
void change(int id,int p,int val){
if(t[id].l==t[id].r){
t[id].sum+=val;
return;
}
if(t[tol].r>=p) change(tol,p,val);
else change(tor,p,val);
t[id].sum=t[tol].sum+t[tor].sum;
}
int ask(int id,int l,int r){
if(l<=t[id].l and t[id].r<=r){
return t[id].sum;
}
if(r<=t[tol].r){
return ask(tol,l,r);
}
else if(l>=t[tor].l){
return ask(tor,l,r);
}
int mid(t[id].l,t[id].r);
return ask(tol,l,mid)+ask(tor,mid+1,r);
}
};
stree x,y;
signed main(){
scanf("%d",&n);
x.build(1,1,100004);
y.build(1,1,100004);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);a[i]++;
}
for(int i=1;i<=n;++i){
ans+=y.ask(1,1,a[i]-1);
x.change(1,a[i],1);
y.change(1,a[i],x.ask(1,1,a[i]-1));
}
cout<<ans;
}
线段树分裂
你们有什么头绪吗
线段树分裂也能用类似 FHQ 的思路去解
只是有点难调
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
namespace stree{
struct tree{
int tol,tor;
int val;
}t[4000001];
int tot;
inline int newnode(){
tot++;
return tot;
}
#define mid(l,r) mid=((l)+(r))/2
void change(int&id,int l,int r,int pos,int val){
if(!id) id=newnode();
t[id].val+=val;
if(l==r){
return;
}
int mid(l,r);
if(pos<=mid) change(t[id].tol,l,mid,pos,val);
else change(t[id].tor,mid+1,r,pos,val);
}
int ask(int id,int l,int r,int L,int R){
if(R<l or r<L) return 0;
if(L<=l and r<=R){
return t[id].val;
}
int mid(l,r);
return ask(t[id].tol,l,mid,L,R)+ask(t[id].tor,mid+1,r,L,R);
}
int kth(int id,int l,int r,int k){
if(l==r) return l;
int mid(l,r);
if(t[t[id].tol].val>=k) return kth(t[id].tol,l,mid,k);
return kth(t[id].tor,mid+1,r,k-t[t[id].tol].val);
}
int merge(int x,int y){
if(x==0) return y;
if(y==0) return x;
t[x].val+=t[y].val;
t[x].tol=merge(t[x].tol,t[y].tol);
t[x].tor=merge(t[x].tor,t[y].tor);
return x;
}
void split(int x,int &y,int k){
if(x==0) return;
y=newnode();
int now=t[t[x].tol].val;
if(k>now) split(t[x].tor,t[y].tor,k-now);
else swap(t[x].tor,t[y].tor);
if(k<now) split(t[x].tol,t[y].tol,k);
t[y].val=t[x].val-k;
t[x].val=k;
return;
}
}
int root[200001];
int seq=1;
signed main(){
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;++i){
int x;scanf("%lld",&x);
stree::change(root[1],1,n,i,x);
}
while(m--){
int op;scanf("%lld",&op);int x,y,z;
if(op==0){
scanf("%lld %lld %lld",&x,&y,&z);
int k1=stree::ask(root[x],1,n,1,z);
int k2=stree::ask(root[x],1,n,y,z);
int tmp=0;
stree::split(root[x],root[++seq],k1-k2);
stree::split(root[seq],tmp,k2);
root[x]=stree::merge(root[x],tmp);
}
if(op==1){
scanf("%lld %lld",&x,&y);
root[x]=stree::merge(root[x],root[y]);
}
if(op==2){
scanf("%lld %lld %lld",&x,&y,&z);
stree::change(root[x],1,n,z,y);
}
if(op==3){
scanf("%lld %lld %lld",&x,&y,&z);
printf("%lld\n",stree::ask(root[x],1,n,y,z));
}
if(op==4){
scanf("%lld %lld",&x,&y);
if(stree::t[root[x]].val<y){
printf("-1\n");
continue;
}
printf("%lld\n",stree::kth(root[x],1,n,y));
}
}
}
搜索 模拟
小木棍
这题的搜索方法很关键啊
- 如果你枚举所有的短木棍放到哪个长木棍里，那么你大概率会 T 掉
- 如果你枚举所有的长木棍被哪些短木棍拼成，那么你大概率会被卡常
事实上应该搜所有的长木棍被哪些长度的短木棍拼成
这样你只需要对值域开桶就好了，会少很多搜索次数
剪枝
- 从大到小排序，防止后面的值过大导致不合法情况太多
- 如果当前长木棍完全没填或者没填的正好等于当前剩余值，那么直接退，后面一定没有合法解
因为你用这个如果正好能卡上剩下的部分，这是一个非常优的解，如果这个都实现不了，反而要用比它小的木棍来凑，那么给后面剩下的木棍一定更少，显然还是不合法的
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n;
int tot;
int maxn,minn=0x3f3f3f3f;
int a[101],cnt[101];
bool dfs(int res,int eachsum,int _tot,int sum,int lastchoose){
if(res>_tot) return true;
if(sum==eachsum){
return dfs(res+1,eachsum,_tot,0,maxn);
}
for(int i=min(eachsum-sum,lastchoose);i>=minn;i--){
if(cnt[i]){
cnt[i]--;
if(dfs(res,eachsum,_tot,sum+i,i)) return true;
cnt[i]++;
if(sum==0 or sum+i==eachsum){
return false;
}
}
}
return false;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
cnt[a[i]]++;
tot+=a[i];
maxn=max(maxn,a[i]);
minn=min(minn,a[i]);
}
for(int i=maxn;i<=tot/2;i++){
if(tot%i==0){
if(dfs(1,i,tot/i,0,maxn)){
cout<<i;
return 0;
}
}
}
cout<<tot;
}
Pushing Boxes
这个题的要求比较特殊，是在保证最小推箱子次数前提下的移动步数最小
所以我们对广搜开一个优先队列，然后以推箱子次数为第一关键字排序，这样可以保证第一次遇到的答案符合要求
然后在广搜里要注意顺序，优先走路，再考虑周围是否有箱子以及推箱子
- 走路的时候要注意目的地是否有箱子
- 方案输出直接采用拼接字符串的方式，字符串直接扔进优先队列里就行了
由于 POJ 实在是太史了，所以你需要尽量减少不必要的入队次数，即入队的时候判掉 vis，否则就会 TLE，但是入队的时候判掉 vis 是假的
Hack:
6 9
T......##
#..##...#
#.###....
#.####...
.......BS
#..####..
0 0
Except Output:
WWWWWWswNNNNenW
去找 huge 换了 UVA 的源，这样能稍微解决一点，否则就只能 Astar 了
点击查看代码
#include<iostream>
#include<queue>
#include<cstring>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
namespace hdk{
int n,m;
int mp[21][21];
// -1 stand for rock
// 0 stand for space
// 1 stand for box
// 2 stand for me
// 3 stand for target
inline int __getchar(){
char ch=getchar();
while(ch!='#' and ch!='.' and ch!='T' and ch!='B' and ch!='S') ch=getchar();
if(ch=='#') return -1;
if(ch=='.') return 0;
if(ch=='B') return 1;
if(ch=='S') return 2;
return 3;
}
struct node{
int x,y;
inline bool operator ==(const node &A){
return x==A.x and y==A.y;
}
inline bool operator !=(const node &A){
return !(x==A.x and y==A.y);
}
inline node(){}
inline node(int _x,int _y){
x=_x;y=_y;
}
};
node b,s,t;
struct nnode{
int move_times,push_times;
node box,me;
string method;
inline bool operator <(const nnode &A)const{
if(push_times==A.push_times) return move_times>A.move_times;
return push_times>A.push_times;
}
inline nnode(int x,int y,int bx,int by,int mx,int my,string met){
move_times=x;
push_times=y;
box=node(bx,by);
me=node(mx,my);
method=met;
}
};
inline bool ill(int x,int y){
if(x<1 or x>n) return false;
if(y<1 or y>m) return false;
return true;
}
inline bool between(int x1,int y1,int x2,int y2){
if(x1==x2) return abs(y1-y2)==1;
if(y1==y2) return abs(x1-x2)==1;
return false;
}
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
char box_info[5]={' ','E','W','S','N'};
char mov_info[5]={' ','e','w','s','n'};
bool vis[21][21][21][21];
inline nnode bfs(nnode start){
priority_queue<nnode>q;
q.push(start);
vis[start.box.x][start.box.y][start.me.x][start.me.y]=true;
while(!q.empty()){
nnode u=q.top();q.pop();
if(u.box==t) return u;
for(int i=1;i<=4;++i){
if(ill(u.me.x+dx[i],u.me.y+dy[i])){
if(node(u.me.x+dx[i],u.me.y+dy[i])!=u.box){
if(mp[u.me.x+dx[i]][u.me.y+dy[i]]!=-1){
if(!vis[u.box.x][u.box.y][u.me.x+dx[i]][u.me.y+dy[i]]){
vis[u.box.x][u.box.y][u.me.x+dx[i]][u.me.y+dy[i]]=true;
q.push(nnode(u.move_times+1,u.push_times,u.box.x,u.box.y,u.me.x+dx[i],u.me.y+dy[i],u.method+mov_info[i]));
}
}
}
}
}
if(between(u.box.x,u.box.y,u.me.x,u.me.y)){
for(int i=1;i<=4;++i){
if(node(u.me.x+dx[i],u.me.y+dy[i])==u.box){
if(ill(u.me.x+dx[i]*2,u.me.y+dy[i]*2)){
if(mp[u.me.x+dx[i]*2][u.me.y+dy[i]*2]!=-1){
if(!vis[u.me.x+dx[i]*2][u.me.y+dy[i]*2][u.box.x][u.box.y]){
vis[u.me.x+dx[i]*2][u.me.y+dy[i]*2][u.box.x][u.box.y]=true;
q.push(nnode(u.move_times,u.push_times+1,u.me.x+dx[i]*2,u.me.y+dy[i]*2,u.box.x,u.box.y,u.method+box_info[i]));
}
}
}
}
}
}
}
return nnode(-1,-1,0,0,0,0,"Impossible.");
}
inline void main(){
int cnt=0;
while(1){
cnt++;
cin>>n>>m;
if(n==0 and m==0) break;
memset(vis,0,sizeof vis);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
mp[i][j]=__getchar();
if(mp[i][j]==1) b=node(i,j);
if(mp[i][j]==2) s=node(i,j);
if(mp[i][j]==3) t=node(i,j);
if(mp[i][j]!=-1) mp[i][j]=0;
}
}
cout<<"Maze #"<<cnt<<'\n';
cout<<bfs(nnode(0,0,b.x,b.y,s.x,s.y,"")).method<<"\n\n";
}
}
}
int main(){
hdk::main();
}
斗地主 加强版
甚好
首先如果不动脑子地打暴力会得到这么一坨东西
#include<bits/stdc++.h>
using namespace std;
int t,n;
struct node{
int x,y;
};
node a[24];
struct cthin{
template<typename T>
cthin& operator >>(T&x){
cin>>x;
return *this;
}
cthin& operator >>(node&x){
cin>>x.x>>x.y;
return *this;
}
}cthin;
struct cthout{
template<typename T>
cthout& operator <<(const T x){
cout<<x;
return *this;
}
}manbaout;
int ans=0;
int cnt[16];
#define dw cnt[14]
#define xw cnt[15]
inline int mod(int x){
while(x>13) x-=13;
return x;
}
void dfs(int tot,int pcnt){
// cout<<"dfs "<<tot<<" "<<pcnt<<endl;
if(pcnt==n){
ans=min(ans,tot);
return;
}
if(tot>=ans) return;
for(int k=5;k<=12;++k){
for(int i=1;i<=13;++i){
bool flag=true;
for(int j=i;j<=i+k-1;++j){
if(j==2 or cnt[mod(j)]<1){
flag=false;
break;
}
}
if(flag){
for(int j=i;j<=i+k-1;++j){
cnt[mod(j)]--;
}
dfs(tot+1,pcnt+k);
for(int j=i;j<=i+k-1;++j){
cnt[mod(j)]++;
}
}
}
}
for(int k=3;k<=12;++k){
for(int i=1;i<=13;++i){
bool flag=true;
for(int j=i;j<=i+k-1;++j){
if(j==2 or cnt[mod(j)]<2){
flag=false;
break;
}
}
if(flag){
for(int j=i;j<=i+k-1;++j){
cnt[mod(j)]-=2;
}
dfs(tot+1,pcnt+k*2);
for(int j=i;j<=i+k-1;++j){
cnt[mod(j)]+=2;
}
}
}
}
for(int k=2;k<=12;++k){
for(int i=1;i<=13;++i){
bool flag=true;
for(int j=i;j<=i+k-1;++j){
if(j==2 or cnt[mod(j)]<3){
flag=false;
break;
}
}
if(flag){
for(int j=i;j<=i+k-1;++j){
cnt[mod(j)]-=3;
}
dfs(tot+1,pcnt+k*3);
for(int j=i;j<=i+k-1;++j){
cnt[mod(j)]+=3;
}
}
}
}
for(int i=1;i<=15;++i){
if(cnt[i]>=4){
cnt[i]-=4;
for(int j=1;j<=15;++j){
if(cnt[j]>=1){
cnt[j]--;
for(int k=1;k<=15;++k){
if(cnt[k]>=1){
cnt[k]--;
dfs(tot+1,pcnt+6);
cnt[k]++;
}
}
cnt[j]++;
}
}
for(int j=1;j<=15;++j){
if(cnt[j]>=2){
cnt[j]-=2;
for(int k=1;k<=15;++k){
if(cnt[k]>=2){
cnt[k]-=2;
dfs(tot+1,pcnt+8);
cnt[k]+=2;
}
}
cnt[j]+=2;
}
}
cnt[i]+=4;
}
}
bool vis[16]={};
for(int k=4;k>=1;--k){
for(int i=1;i<=15;++i){
if((!vis[i]) and cnt[i]>=k){
cnt[i]-=k;
vis[i]=true;
dfs(tot+1,pcnt+k);
cnt[i]+=k;
}
}
}
for(int i=1;i<=15;++i){
if(cnt[i]>=3){
cnt[i]-=3;
for(int j=1;j<=15;++j){
if(cnt[j]>=1){
cnt[j]--;
dfs(tot+1,pcnt+4);
cnt[j]++;
}
}
cnt[i]+=3;
}
}
for(int i=1;i<=15;++i){
if(cnt[i]>=3){
cnt[i]-=3;
for(int j=1;j<=15;++j){
if(cnt[j]>=2){
cnt[j]-=2;
dfs(tot+1,pcnt+5);
cnt[j]+=2;
}
}
cnt[i]+=3;
}
}
if(xw){
xw=0;
dfs(tot+1,pcnt+1);
xw=1;
}
if(dw){
dw=0;
dfs(tot+1,pcnt+1);
dw=1;
}
if(xw and dw){
xw=0;dw=0;
dfs(tot+1,pcnt+2);
xw=1;dw=1;
}
}
signed main(){
ios::sync_with_stdio(false);
cthin>>t>>n;
while(t--){
memset(cnt,0,sizeof cnt);
ans=0x7fffffff;
for(int i=1;i<=n;++i){
cthin>>a[i];
if(a[i].x!=0){
cnt[a[i].x]++;
}
else{
if(a[i].y==1) xw=1;
else dw=1;
}
}
dfs(0,0);
cout<<ans<<'\n';
}
}
依照题意模拟即可，打不出来建议退役
然后考虑怎么优化，发现这玩意根本优化不动
实际上需要换一种思路，去枚举出哪种牌而不是一次次判断能出什么牌，我们按编号从小到大依次打出该编号的牌，能打就打，打完了再考虑怎么打完后面的牌（不是说这个牌打不完就不能打后面的，而是优先进行能打完当前牌的操作），这样能省去很多不必要的状态
但是你这么打又出问题了，被 hack 掉了
44666655
你会发现，如果你以编号递增顺序优先出牌，那么你就会出成对子+对子+炸弹的形式，然而正解是四带二对
为了避免这种情况，所以考虑把四带二对拆成两种情况：
- 4+2+2
- 2+4+2
其他的能拆分的操作同理，最后一共拆出来的情况如下
- 4+1+1
- 4+2+2
- 4
- 三顺子
- 3+1
- 3+2
- 3
- 双顺子
- 2+4+2
- 2+3
- 2
- 顺子
- 1+3
- 1
- 火箭
然后加一点剪枝
- 如果当前状态答案已经劣于当前最优解了，直接返回
- 优先搜出牌数量大的，即按照
4->3->2->1的顺序搜
比较方便的一个技巧是，把 A,2 挪到整副牌最后（大小王之前），这样做顺子的时候方便一点
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int t,n;
struct node{
int x,y;
};
node a[24];
struct cthin{
template<typename T>
cthin& operator >>(T&x){
cin>>x;
return *this;
}
cthin& operator >>(node&x){
cin>>x.x>>x.y;
return *this;
}
}cthin;
struct cthout{
template<typename T>
cthout& operator <<(const T x){
cout<<x;
return *this;
}
}manbaout;
int ans=0;
int cnt[16];
#define dw cnt[14]
#define xw cnt[15]
inline int mp(int x){
if(x==1) return 12;
if(x==2) return 13;
return x-2;
}
inline int mod(int x){
while(x>13) x-=13;
return x;
}
void dfs(int now,int tot,int pcnt){
if(tot>ans) return; //剪枝
if(pcnt==n){
ans=min(ans,tot);
return;
}
if(now>15) return;
if(cnt[now]==0) dfs(now+1,tot,pcnt);
if(dw and xw){
dw--;xw--;
dfs(now,tot+1,pcnt+2);
dw++;xw++;
}
if(cnt[now]>=4){
cnt[now]-=4;
for(int i=1;i<=13;++i){ //4 + 1 + 1
if(cnt[i]>=1){
cnt[i]--;
for(int j=i;j<=15;++j){
if(cnt[j]>=1){
cnt[j]--;
dfs(now,tot+1,pcnt+6);
cnt[j]++;
}
}
cnt[i]++;
}
}
for(int i=1;i<=13;++i){ //4 + 2 + 2
if(cnt[i]>=2){
cnt[i]-=2;
for(int j=i;j<=13;++j){
if(cnt[j]>=2){
cnt[j]-=2;
dfs(now,tot+1,pcnt+8);
cnt[j]+=2;
}
}
cnt[i]+=2;
}
}
dfs(now,tot+1,pcnt+4); //4
cnt[now]+=4;
}
if(cnt[now]>=3){
cnt[now]-=3;
for(int i=now+1;i<=12;++i){ //3 顺子
if(cnt[i]<3) break;
if(i-now+1>=2){
for(int j=now+1;j<=i;++j) cnt[j]-=3;
dfs(now,tot+1,pcnt+(i-now+1)*3);
for(int j=now+1;j<=i;++j) cnt[j]+=3;
}
}
for(int i=1;i<=15;++i){ //3 + 1
if(i==now) continue;
if(cnt[i]>=1){
cnt[i]--;
dfs(now,tot+1,pcnt+4);
cnt[i]++;
}
}
for(int i=1;i<=15;++i){ //3 + 1
if(i==now) continue;
if(cnt[i]>=2){
cnt[i]-=2;
dfs(now,tot+1,pcnt+5);
cnt[i]+=2;
}
}
dfs(now,tot+1,pcnt+3); //3
cnt[now]+=3;
}
if(cnt[now]>=2){
cnt[now]-=2;
for(int i=now+1;i<=12;++i){ //2 顺子
if(cnt[i]<2) break;
if(i-now+1>=3){
for(int j=now+1;j<=i;++j) cnt[j]-=2;
dfs(now,tot+1,pcnt+(i-now+1)*2);
for(int j=now+1;j<=i;++j) cnt[j]+=2;
}
}
for(int i=1;i<=13;++i){ //2 + 4 + 2
if(cnt[i]>=4 and i!=now){
cnt[i]-=4;
for(int j=1;j<=13;++j){
if(cnt[j]>=2 and j!=i){
cnt[j]-=2;
dfs(now,tot+1,pcnt+8);
cnt[j]+=2;
}
}
cnt[i]+=4;
}
}
for(int i=1;i<=13;++i){ //2 + 3
if(cnt[i]>=3 and i!=now){
cnt[i]-=3;
dfs(now,tot+1,pcnt+5);
cnt[i]+=3;
}
}
dfs(now,tot+1,pcnt+2);
cnt[now]+=2;
}
if(cnt[now]>=1){
cnt[now]-=1;
for(int i=now+1;i<=12;++i){ //顺子
if(cnt[i]<1) break;
if(i-now+1>=5){
for(int j=now+1;j<=i;++j) cnt[j]--;
dfs(now,tot+1,pcnt+(i-now+1));
for(int j=now+1;j<=i;++j) cnt[j]++;
}
}
for(int i=1;i<=13;++i){ //1 + 4 + 1
if(cnt[i]>=4 and i!=now){
cnt[i]-=4;
for(int j=1;j<=15;++j){
if(cnt[j]>=1 and j!=i){
cnt[j]--;
dfs(now,tot+1,pcnt+6);
cnt[j]++;
}
}
cnt[i]+=4;
}
}
for(int i=1;i<=13;++i){ //1 + 3
if(cnt[i]>=3 and i!=now){
cnt[i]-=3;
dfs(now,tot+1,pcnt+4);
cnt[i]+=3;
}
}
dfs(now,tot+1,pcnt+1);
cnt[now]++;
}
}
signed main(){
ios::sync_with_stdio(false);
cthin>>t>>n;
while(t--){
memset(cnt,0,sizeof cnt);
ans=0x7fffffff;
for(int i=1;i<=n;++i){
cthin>>a[i];
if(a[i].x!=0){
cnt[mp(a[i].x)]++;
}
else{
if(a[i].y==1) xw=1;
else dw=1;
}
}
dfs(1,0,0);
cout<<ans<<'\n';
}
}
Expression
收回说这道题很好的评价
首先我们只考虑当前枚举到的第 \(i\) 位（假设第 \(i\) 位之前都已经满足要求了，此时高位的决策是不会影响第 \(i\) 位的），设 \(a\) 的第 \(i\) 位为 \(a_i\)，\(b,c\) 同理，并且从低位进上来的数为 \(j\)，容易发现，当 \(a_i+b_i+j=c_i\) 的时候，这一位我们就不需要考虑了，直接去做下一位就行了
对于搜索的结束情况，就是 \(c\) 的更高位已经没有东西了，这个时候你只需要把当前 \(a,b\) 还没处理的高位丢到 \(c\) 的高位上就结束了
那么怎么处理不合法的情况
这个时候你可以考虑在第 \(i\) 位插入一个数字，随便 \(a,b,c\) 哪个数都行，只要能让它变成 \(a_i+b_i+j=c_i\) 的情况即可（这里实际上写的时候应该是在模 \(10\) 意义下，并且注意处理进位），然后你就可以将其转化为上面那种情况然后继续处理下一位了
思路不难，但是写起来很恶心，涉及到往某一位插入，最高位插入，还要统计最终答案的三个数字，建议是全都传到 dfs 里，对于插入的问题可以通过向 dfs 里传一个当前位数来解决
不评价了，难写的要死，只能说不愧是紫搜
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,c;
int ans=0x7fffffff;
int aans[4];
int base10[64];
void dfs(int a,int b,int c,int jw,int na,int nb,int nc,int nowans,int deep){
// cout<<"dfs "<<a<<" "<<b<<" "<<c<<" "<<jw<<" "<<na<<" "<<nb<<" "<<nc<<" "<<nowans<<" "<<deep<<endl;
if(nowans>ans) return;
if(a==0 and b==0 and c==0 and jw==0){
if(nowans<ans){
ans=nowans;
aans[0]=na;
aans[1]=nb;
aans[2]=nc;
}
return;
}
if(c==0){
int tmp=(a+b+jw);
int res=0;
while(tmp){
res++;
tmp/=10;
}
dfs(0,0,0,0,na+a*base10[deep],nb+b*base10[deep],nc+base10[deep]*(a+b+jw),nowans+res,deep+1);
return;
}
if((a+b+jw)%10==c%10){
dfs(a/10,b/10,c/10,(a%10+b%10+jw)/10,na+(a%10)*base10[deep],nb+(b%10)*base10[deep],nc+(c%10)*base10[deep],nowans,deep+1);
}
dfs(a*10+(c%10-b%10-jw+10)%10,b,c,jw,na,nb,nc,nowans+1,deep);
dfs(a,b*10+(c%10-a%10-jw+10)%10,c,jw,na,nb,nc,nowans+1,deep);
dfs(a,b,c*10+(a%10+b%10+jw)%10,jw,na,nb,nc,nowans+1,deep);
}
signed main(){
base10[0]=1;
for(int i=1;i<=18;++i) base10[i]=base10[i-1]*10;
scanf("%lld+%lld=%lld",&a,&b,&c);
dfs(a,b,c,0,0,0,0,0,0);
printf("%lld+%lld=%lld",aans[0],aans[1],aans[2]);
}
Distinct Paths
一眼：\(N,M\le 1000\)，我打暴搜，真的假的？
两眼：DP 套 DFS 吗
三眼：草，诈骗题
注意到路径上的颜色最多只有 \(n+m-1\) 个，如果你 \(k\) 连这个都达不到那就没有合法方案
所以你就可以搜了，因为这个题求的是集合，所以你可以直接搜坐标
因为只能向右/向下走，可以对 \(k\) 状压一下，求出 \((x-1,y),(x,y-1)\) 的决策颜色之和，然后枚举没选过的颜色填进去
优化
- 如果当前没填的数比要走的格子还少，无解
- 如果一个数第一次被填，则填什么都是一样的（注意这里 “第一次被填” 指的是没有在之前的决策与已经确定的数中出现过）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
int n,m,k;
int mp[101][101];
int used[101][101];
int cnt[101];
int dfs(int x,int y){
if(x==n+1){
return 1;
}
int res=0;
int now=used[x-1][y]|used[x][y-1];
if(k-__builtin_popcount(now)<((m-y)+(n-x)+1)) return res;
if(mp[x][y]==0){
int ls=-1;
for(int i=1;i<=k;++i){
if((now&(1<<i))==0){
cnt[i]++;
used[x][y]=now|(1<<i);
if(cnt[i]==1 and ls==-1) ls=dfs(y==m?x+1:x,y==m?1:y+1);
if(cnt[i]==1) res+=ls;
else res+=dfs(y==m?x+1:x,y==m?1:y+1);
res%=p;
cnt[i]--;
}
}
}
else{
if((now&(1<<mp[x][y]))==0){
used[x][y]=now|(1<<mp[x][y]);
res+=dfs(y==m?x+1:x,y==m?1:y+1);
res%=p;
}
}
return res%p;
}
signed main(){
cin>>n>>m>>k;
if(n+m-1>k){
cout<<0;
return 0;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>mp[i][j];
cnt[mp[i][j]]++;
}
}
cout<<dfs(1,1)%p<<endl;
}
Rotation Puzzle
挺板的一道题
折半搜索可以将 \(2^{2k}\) 的复杂度降到 \(2^{k+1}\log\)，前提是知道最终状态
从起始状态开始搜一半状态，最后开始搜一半状态，然后从中间合并答案，找合并点用哈希就行了
这题我也不知道卡不卡哈希，我的单进制哈希被卡了，但是双进制单模哈希没被卡
最难的部分应该是旋转怎么写
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int mp[101][101];
int mp2[101][101];
inline void rotate(int x,int y){
for(int i=x;i<=x+n-2;++i){
for(int j=y;j<=y+m-2;++j){
int nx=x+n-2-i+x,ny=y+m-2-j+y;
if(i<nx or (i==nx and j<ny)){
swap(mp[i][j],mp[nx][ny]);
}
}
}
}
inline void rotate2(int x,int y){
for(int i=x;i<=x+n-2;++i){
for(int j=y;j<=y+m-2;++j){
int nx=x+n-2-i+x,ny=y+m-2-j+y;
if(i<nx or (i==nx and j<ny)){
swap(mp2[i][j],mp2[nx][ny]);
}
}
}
}
int ans=0x7fffffff;
unsigned long long __hash(){
unsigned long long ans=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
ans=ans*(n+m+1)+mp[i][j];
}
}
return ans;
}
unsigned long long __hash2(){
unsigned long long ans=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
ans=ans*(n+m+1)+mp2[i][j];
}
}
return ans;
}
unsigned long long __0hash(){
unsigned long long ans=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
ans=ans*233+mp[i][j];
}
}
return ans;
}
unsigned long long __0hash2(){
unsigned long long ans=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
ans=ans*233+mp2[i][j];
}
}
return ans;
}
map<pair<unsigned long long,unsigned long long>,int>hast;
void dfs(int tot){
if(tot>10) return;
int tmp=__hash(),tmp2=__0hash();
if(!hast.count({tmp,tmp2})) hast[{tmp,tmp2}]=tot;
else hast[{tmp,tmp2}]=min(hast[{tmp,tmp2}],tot);
rotate(1,1);
dfs(tot+1); //1
rotate(1,1);
rotate(1,2);
dfs(tot+1); //2
rotate(1,2);
rotate(2,1);
dfs(tot+1); //3
rotate(2,1);
rotate(2,2);
dfs(tot+1); //4
rotate(2,2);
}
void dfs2(int tot){
if(tot>10) return;
int tmp=__hash2(),tmp2=__0hash2();
if(hast.count({tmp,tmp2})){
ans=min(ans,hast[{tmp,tmp2}]+tot);
}
rotate2(1,1);
dfs2(tot+1); //1
rotate2(1,1);
rotate2(1,2);
dfs2(tot+1); //2
rotate2(1,2);
rotate2(2,1);
dfs2(tot+1); //3
rotate2(2,1);
rotate2(2,2);
dfs2(tot+1); //4
rotate2(2,2);
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>mp[i][j];
mp2[i][j]=(i-1)*m+j;
}
}
dfs(0);
dfs2(0);
cout<<(ans>20?-1:ans);
}
Anya and Cubes
还是板子题大佬
不是，你放这么多折半板子干啥
这个题甚至比上一个简单
你对 \(n\) 取一个中点，分别对前一半和后一半搜就行了
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,s;
int a[30];
int fact(int x){
__int128 res=1;
for(int i=x;i>=1;--i){
res*=i;
if(res>s) return -1;
}
return res;
}
int mid;
map<pair<int,long long>,int>mp;
map<long long,bool>vis;
void dfs1(int now,int factcnt,int sum){
if(now>mid){
mp[{factcnt,sum}]++;
vis[sum]=true;
return;
}
dfs1(now+1,factcnt,sum);
dfs1(now+1,factcnt,sum+a[now]);
int tmp=fact(a[now]);
if(tmp!=-1) dfs1(now+1,factcnt+1,sum+tmp);
}
long long ans=0;
void dfs2(int now,int factcnt,int sum){
if(now<=mid){
if(vis.count(sum)){
for(int l=0;l+factcnt<=k;++l){
ans+=mp[{l,sum}];
}
}
return;
}
dfs2(now-1,factcnt,sum);
dfs2(now-1,factcnt,sum-a[now]);
int tmp=fact(a[now]);
if(tmp!=-1) dfs2(now-1,factcnt+1,sum-tmp);
}
signed main(){
cin>>n>>k>>s;
for(int i=1;i<=n;++i) cin>>a[i];
mid=n/2;
dfs1(1,0,0);
dfs2(n,0,s);
cout<<ans;
}
卖瓜
怎么还是折半板子
没啥可说的
这个题和前两个题的区别是要加剪枝，否则可能会 TLE
所以 cc_hash_table 和 gp_hash_table 区别在哪
点击查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
int n,m;
int mid;
int ans=114514,cnt;
int a[32];
long long b[32];
cc_hash_table<int,int>mp;
void dfs1(int now,int pcnt,int sum){
if(sum>m) return;
if(sum+b[now]<m) return;
if(sum==m){
mp[sum]=pcnt;
return;
}
if(now==mid+1){
if(mp[sum]) mp[sum]=min(mp[sum],pcnt+1);
else mp[sum]=pcnt+1;
return;
}
dfs1(now+1,pcnt,sum+a[now]);
dfs1(now+1,pcnt+1,sum+a[now]/2);
dfs1(now+1,pcnt,sum);
}
void dfs2(int now,int pcnt,int sum){
if(sum>m or pcnt>ans) return;
if(sum==m){
ans=min(ans,mp[sum]+pcnt);
return;
}
if(now==n+1){
if(mp[m-sum]) ans=min(ans,pcnt+mp[m-sum]-1);
return;
}
dfs2(now+1,pcnt,sum+a[now]);
dfs2(now+1,pcnt+1,sum+a[now]/2);
dfs2(now+1,pcnt,sum);
}
int main(){
cin>>n>>m;
mid=min(n/2+1,n-2);
m*=2;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]*=2;
}
sort(a+1,a+1+n);
for(int i=n;i>=1;i--){
b[i]=b[i+1]+a[i];
}
dfs1(1,0,0);
dfs2(mid+1,0,0);
if(ans==114514) cout<<-1;
else cout<<ans;
}