模拟赛
总是忘记保存怎么办
难得挂分。
T1 AND and SUM
签到题，如果两数按位与结果为 \(a\)，那么它们的二进制重复为 \(1\) 的位一定就是 \(a\) 的二进制为 \(1\) 的位置，
所以它们相加的值至少是 \(2a\)。并且不够的差值只能在 \(a\) 二进制为零的位置补（否则会有进位），所以判 \((s-2a)\&a\) 是否为零。
赛时判了很多东西。。。
code
#include<bits/stdc++.h>
using namespace std;
#define LL __int128
int T;
LL a,s;
inline LL read()
{
LL res=0; char x=getchar();
while(x<'0'||x>'9') x=getchar();
while(x>='0'&&x<='9') res=(res<<1)+(res<<3)+(x^48),x=getchar();
return res;
}
int main()
{
freopen("and.in","r",stdin);
freopen("and.out","w",stdout);
scanf("%d",&T);
while(T--)
{
a=read(),s=read();
if(a==0) printf("Yes\n");
else if(s==0) printf("No\n");
else if((a<<1)>s) printf("No\n");
else if((a<<1)==s) printf("Yes\n");
else
{
if((s-(a<<1))&a) printf("No\n");
else printf("Yes\n");
}
}
return 0;
}
T2 Maximum Composition
前两天刚见过的题，幸好赛时想出来了，虽然唐氏挂分。
先考虑如果确定选 \(f_1，f_2\)，那么什么顺序是最优的。
-
先选 \(f_1\)：\(a_2(a_1x+b_1)+b_2=a_1a_2x+a_2b_1+b_2\)。
-
先选 \(f_2\)：\(a_1(a_2x+b_2)+b_1=a_1a_2x+a_1b_2+b_1\)
所以如果 \((a_1-1)b_2<(a_2-1)b_1\)，那么先选 \(f_1\) 更优。
所以我们按上述标准排序，那么得到的就是在有序的数列上选 \(k\) 个函数使结果最大。那么可以直接 DP。
注意初始化！！！
code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5+5;
int n,k;
LL f[N][11];
struct A
{
int a,b;
bool operator < (const A &x) const
{
return 1.0*(a-1)/b<1.0*(x.a-1)/x.b;
}
} s[N];
int main()
{
freopen("func.in","r",stdin);
freopen("func.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d%d",&s[i].a,&s[i].b);
sort(s+1,s+1+n); f[0][0]=1;//！！！！！！！！！！！！！！
for(int i=1;i<=n;i++)
{
f[i][0]=1;
for(int j=1;j<=min(k,i);j++)
{
f[i][j]=max(f[i-1][j-1]*s[i].a+s[i].b,f[i-1][j]);
}
}
printf("%lld",f[n][k]);
return 0;
}
T3 kangaroo
怎么想到这是预设型 DP 啊！
预设型 DP，也叫插入法 DP（这个更合适）。
我们先转化题意，将每次跳跃的点的编号组成一个序列。那么这个序列一定是波浪形的。
也就是一大一小交替放的序列的个数。考虑插入法 DP。也就是考虑填数所形成的连续段。
我们按点的编号从小到大填，这样有一个显然性质是后填的数一定比先填的大！（够显然吧）。
那么如果得到结论：填的数只能单独成段或者连接另外两个连通块。
否则一定会出现一段单调的区间，这是非法的。
所以设计状态为 \(f_{i,j}\) 表示填前 \(i\) 个数形成 \(j\) 个连续段的方案数。
转移比较简单，注意特判终点和起点，它们必须在序列两端。
还有线性 \(O(n)\) 做法，如果有机会？？？ CEOI2016 Kangaroo 线性做法
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+5,mod = 1e9+7;
int n,s,t;
int f[2][N];
int main()
{
// freopen("kang.in","r",stdin);
// freopen("kang.out","w",stdout);
scanf("%d%d%d",&n,&s,&t);
f[1][1]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(i==s||i==t) f[i&1][j]=(1ll*f[(i-1)&1][j-1]+f[(i-1)&1][j])%mod;
else
{
f[i&1][j]=(1ll*f[(i-1)&1][j+1]*j+1ll*f[(i-1)&1][j-1]*(j-(i>s)-(i>t)))%mod;
}
}
}
printf("%d\n",f[n&1][1]);
return 0;
}
T4 The Classic Problem
一眼高精度。
\(2^{1e5}\) 显然不能用常规方法做。但是 dij 求最短路是肯定的，所以我们考虑如果想实现 dij 需要维护哪些操作。
我们正常的 \(dij\) 需要维护的操作：加法和比较大小。
加法每次只会在二进制的某一位加一。如果加的这一位恰好为 \(1\)，那么考虑进位，找出向后连续的最长的 \(1\)。如果为 \(0\)，那直接加即可。
比较大小则先比较高位，不同再比较低位。
并且我们应该要能记录每一个出现的数。
上述操作都可以用主席树实现，用主席树维护 \(1e5\) 的二进制位。
由于比较的操作需要判断区间是否相等，所以考虑直接用 hash 维护，这样的话加的时候注意对齐。
单点加区间推平直接搞，查找连续的 \(1\) 线段树上二分即可，其他的正常 dij。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5,H = 1e9+3579,B = 233,mod = 1e9+7,V = 2e5+5;
int n,m,s,t;
int head[N],tot,p[N],p2[N],num,rt[N];
struct E {int u,v,w;} e[N<<1];
inline void add(int u,int v,int w) {e[++tot]={head[u],v,w}; head[u]=tot;}
inline void init() {p[0]=p2[0]=1; for(int i=1;i<N;i++) p[i]=1ll*p[i-1]*B%H,p2[i]=p2[i-1]*2ll%mod;}
namespace SEG
{
struct T {int l,r,sum,hs,len;} tr[N<<7];
inline void pushup(int k)
{
tr[k].len=tr[tr[k].l].len+tr[tr[k].r].len;
tr[k].sum=tr[tr[k].l].sum+tr[tr[k].r].sum;
tr[k].hs=(1ll*tr[tr[k].l].hs*p[tr[tr[k].r].len]%H+tr[tr[k].r].hs)%H;
}
inline void bui(int &k,int l,int r,int v)
{
k=++num;
if(l==r) return (tr[k].len=1,tr[k].hs=tr[k].sum=v),void(0);
int mid=l+r>>1;
bui(tr[k].l,l,mid,v); bui(tr[k].r,mid+1,r,v);
pushup(k);
}
inline void mdf(int &k,int pre,int l,int r,int p,int v)
{
k=++num; tr[k]=tr[pre];
if(l==r) return (tr[k].sum=tr[k].hs=v),void(0);
int mid=l+r>>1;
if(p<=mid) mdf(tr[k].l,tr[pre].l,l,mid,p,v);
else mdf(tr[k].r,tr[pre].r,mid+1,r,p,v);
pushup(k);
}
void assign(int &k,int pre,int co,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return k=co,void(0);
k=++num; tr[k]=tr[pre];
int mid=l+r>>1;
if(L<=mid) assign(tr[k].l,tr[pre].l,tr[co].l,l,mid,L,R);
if(R>mid) assign(tr[k].r,tr[pre].r,tr[co].r,mid+1,r,L,R);
pushup(k);
}
int cmp(int x,int y,int l,int r)
{
if(l==r) return tr[x].hs-tr[y].hs;
int mid=l+r>>1;
if(tr[tr[x].r].hs!=tr[tr[y].r].hs) return cmp(tr[x].r,tr[y].r,mid+1,r);
return cmp(tr[x].l,tr[y].l,l,mid);
}
int afind(int k,int l,int r)
{
if(tr[k].sum==tr[k].len) return r;
if(l==r) return -1;
int mid=l+r>>1;
int x=afind(tr[k].l,l,mid);
if(x==mid) return max(x,afind(tr[k].r,mid+1,r));
return x;
}
int find(int k,int l,int r,int p)
{
if(p<=l) return afind(k,l,r);
int mid=l+r>>1;
if(p<=mid)
{
int x=find(tr[k].l,l,mid,p);
if(x==mid) return max(x,find(tr[k].r,mid+1,r,p));
return x;
}
return find(tr[k].r,mid+1,r,p);
}
}; using namespace SEG;
inline int ad(int k,int p)
{
int x=find(k,0,V,p),r=0,res=0;
if(x<0) x=p-1,r=k;
else assign(r,k,rt[0],0,V,p,x);
mdf(res,r,0,V,x+1,1);
return res;
}
int d[N];
bool vs[N];
inline void dj(int s)
{
struct node
{
int u,id;
bool operator < (const node &x) const
{
return cmp(id,x.id,0,V)>0;
}
};
priority_queue<node> q; bui(rt[0],0,V,0); bui(rt[n+1],0,V,1);
for(int i=1;i<=n;i++) rt[i]=rt[n+1];
rt[s]=rt[0]; q.push({s,rt[s]}); d[s]=0;
while(!q.empty())
{
int u=q.top().u,id=q.top().id; q.pop();
if(vs[u]) continue; vs[u]=1;
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v;
int now=ad(id,e[i].w);
if(!vs[v]&&cmp(now,rt[v],0,V)<0)
{
d[v]=(d[u]+p2[e[i].w])%mod; q.push({v,rt[v]=now});
}
}
}
}
int main()
{
freopen("hellagur.in","r",stdin);
freopen("hellagur.out","w",stdout);
scanf("%d%d",&n,&m); init();
for(int i=1;i<=m;i++)
{
int x,y,z; scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
scanf("%d%d",&s,&t);
dj(s);
printf("%d\n",vs[t]?d[t]:-1);
return 0;
}