美团CodeM复赛题解
配对游戏
思路
设f[i][j]表示前i个人中，还有j个向右看的人可以消除，这种状态的期望消除数量， g[i][j]为到达这种状态的概率。
考虑第i + 1的朝向，如果是向右，那么f[i + 1][j + 1] ← f[i][j]/2，
g[i + 1][j + 1] ← g[i][j]/2，如果是向左，那么
f[i + 1][j − 1] ← f[i][j]/2 + g[i][j]，g[i + 1][j − 1] ← g[i][j]/2。(注意 j = 0的情况)
代码
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int n,i,j,k;
double f[2005][2005],g[2005][2005],ans;
int main()
{
scanf("%d",&n);
g[0][0]=1;
for(i=0;i<n;++i)
for(j=0;j<=i;++j)
{
f[i+1][j+1]+=f[i][j]/2;g[i+1][j+1]+=g[i][j]/2;
if(j)f[i+1][j-1]+=f[i][j]/2+g[i][j],g[i+1][j-1]+=g[i][j]/2;
else f[i+1][j]+=f[i][j]/2,g[i+1][j]+=g[i][j]/2;
}
ans=n;
for(i=0;i<=n;++i)ans-=f[n][i];
printf("%.3lf\n",ans);
}
城市网络
思路
考虑离线处理，可以对每个询问，建出一个新点，作为叶子挂在起点下面。
然后建一棵新树，对于每个点，求出它的祖先中，第一个比它权值大的，作为它在新树中 的父亲。
考虑在新树上处理询问，可以倍增找出需要跳多少点。
代码
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int n,q,i,j,k,u,v,l,r,ans;
int a[200005],id[200005];
int tid[200005],t[200005][20],cnt;
int tfa[200005],fa[200005],deep[200005],aim[200005];
int son[200005],Next[400005],ed[400005],tot;
bool vis[200005];
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
inline bool cmp(const int &x,const int &y){return a[x]<a[y];}
void dfs(int x)
{
vis[x]=true;tid[++cnt]=x;
for(int i=son[x];i;i=Next[i])
if(!vis[ed[i]])
{
tfa[ed[i]]=x;
deep[ed[i]]=deep[x]+1;
dfs(ed[i]);
}
}
int main()
{
scanf("%d%d",&n,&q);
for(i=1;i<=n;++i)scanf("%d",&a[i]);
for(i=1;i<n;++i)
{
scanf("%d%d",&u,&v);
++tot;Next[tot]=son[u];son[u]=tot;ed[tot]=v;
++tot;Next[tot]=son[v];son[v]=tot;ed[tot]=u;
}
deep[1]=1;dfs(1);
for(i=1;i<=q;++i)tid[++cnt]=n+i;
for(i=1;i<=n+q;++i)fa[i]=id[i]=i;
for(i=1;i<=q;++i)scanf("%d%d%d",&tfa[n+i],&aim[n+i],&a[n+i]),deep[n+i]=deep[tfa[n+i]]+1;
sort(id+1,id+n+q+1,cmp);
for(l=1;l<=n+q;l=r+1)
{
for(r=l;r<n+q&&a[id[r+1]]==a[id[l]];++r);
for(i=l;i<=r;++i)u=id[i],fa[u]=tfa[u];
for(i=l;i<=r;++i)u=id[i],t[u][0]=get(u);
}
for(i=1;i<=n+q;++i)
{
u=tid[i];
for(j=0;t[u][j];++j)
t[u][j+1]=t[t[u][j]][j];
}
for(i=n+1;i<=n+q;++i)
{
ans=0;u=i;
for(j=18;j>=0;--j)
if(deep[t[u][j]]>=deep[aim[i]])
u=t[u][j],ans+=1<<j;
printf("%d\n",ans);
}
}
神秘代码
思路
N 个点N 条边的图一定是环套外向树。考虑将环上的所有方程都取出来(设共有x 个)，那 么这些方程构成了一个x个方程x个变量且首尾相接的方程组。考虑每次用第一个方程去 消，消去相同的一部分，消完后将会得到一个仅关于第一个变量的方程。由于题目保证解 唯一，所以最后的方程是ax ≡ b (mod p)的形式，通过求a的逆元就可以求得第一个变 量的值。
求得一个值后，通过bfs递推就可以得到剩余每个位置的xi 了。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>
#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define N 300005
#define M 200005
#define seed 23333
using namespace std;
int i,j,m,n,p,k,vis[N],deg[N],Q[N],cy[N],x,y,fa[N],A[N];
long long a,b,c;
struct Node{
long long a,b,c;
};
Node fx[N],E[N];
vector<pair<int,Node> >v[N];
void Find_Cycle()
{
for (i=1;i<=n;++i) if (deg[i]==1) Q[++Q[0]]=i,vis[i]=1;
int l;
for (l=1;l<=Q[0];++l)
{
int p=Q[l];
for (i=0;i<(int)v[p].size();++i)
{
int k=v[p][i].fi; --deg[k];
if (!vis[k]) fa[p]=k,E[p]=v[p][i].se;
if (deg[k]==1)
{
Q[++Q[0]]=k;
vis[k]=1;
}
}
}
for (i=1;i<=n;++i) if (!vis[i]) break;
for (;!vis[i];)
{
cy[++cy[0]]=i;
vis[i]=1;
for (j=0;j<(int)v[i].size();++j)
{
int k=v[i][j].fi;
if (!vis[k])
{
fx[cy[0]]=v[i][j].se;
i=k;
break;
}
}
}
}
int power(int x,int y)
{
int sum=1;
for (;y;y>>=1)
{
if (y&1) sum=1ll*sum*x%p;
x=1ll*x*x%p;
}
return sum;
}
int main()
{
scanf("%d%d",&n,&p);
for (i=1;i<=n;++i)
{
scanf("%d%d%lld%lld%lld",&x,&y,&a,&b,&c);
v[x].pb(mk(y,(Node){a,b,c}));
v[y].pb(mk(x,(Node){b,a,c}));
deg[x]++; deg[y]++;
}
Find_Cycle();
Node now=fx[1];
k=cy[cy[0]];
for (i=0;i<(int)v[k].size();++i)
{
int p=v[k][i].fi;
if (p==cy[1]) fx[cy[0]]=v[k][i].se;
}
for (i=2;i<=cy[0];++i)
{
now.a=(now.a*fx[i].a%p+p)%p;
now.c=((now.c*fx[i].a-fx[i].c*now.b)%p+p)%p;
now.b=((p-fx[i].b)*now.b%p+p)%p;
}
(now.a+=now.b)%=p;
if (now.a==0) puts("cao"); else A[cy[1]]=1ll*now.c*power(now.a,p-2)%p;
for (i=2;i<=cy[0];++i) A[cy[i]]=1ll*(fx[i-1].c-1ll*A[cy[i-1]]*fx[i-1].a%p+p)*power(fx[i-1].b,p-2)%p;
for (i=Q[0];i;--i)
{
int k=Q[i];
A[k]=1ll*(E[k].c-1ll*A[fa[k]]*E[k].b%p+p)*power(E[k].a,p-2)%p;
}
for (i=1;i<=n;++i) printf("%d\n",A[i]);
}
排列
思路
代码
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <vector>
#include <bitset>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
const int N=100005,Mod=1e9+7;
int n,x[N],y[N],f[N],Num[N],s[N],inc[N],ans[N];
void Add(int x,int k)
{
while(x<=n)
s[x]=(s[x]+k)%Mod,x+=x&-x;
}
int Sum(int x)
{
int ss=0;
while(x)
ss=(ss+s[x])%Mod,x-=x&-x;
return ss;
}
int main()
{
scanf("%d",&n);
for(int i=1,a,b;i<=n;i++)
scanf("%d%d",&a,&b),x[i]=a,y[a]=b;
for(int i=n;i>=1;i--)
Num[i]=n-i-Sum(y[i]),Add(y[i],1);
inc[0]=inc[1]=1;
int fac=1;
for(int i=2;i<=n;i++)
inc[i]=(Mod-(Mod/i)*(LL)inc[Mod%i]%Mod)%Mod,fac=fac*(LL)(i-1)%Mod;
memset(s,0,sizeof s);
int count=0;
for(int i=1;i<=n;i++)
{
f[i]=(LL)(Sum(y[i])+1)*inc[Num[i]]%Mod;
Add(y[i],f[i]);
if(Num[i]==0)ans[i]=f[i]*(LL)fac%Mod,count++;
else ans[i]=0;
}
for(int i=1;i<=n;++i)printf("%d\n",ans[x[i]]);
// cout<<count<<endl;
return 0;
}
Pairsum
思路
本题是一道趣味的构造题，构造方法不唯一，下面是作者的方法。
选取一个最大的素数p使得2p^2<=n，然后构造数列a[i] = 2ip+(i^2 mod p)，其中i=1,2,…p。如果a[i] = a[j]，那么有2ip=2jp从而i=j. 根据素数定理，p距离n不会太远，所以数列长度p大约是(n/2)^(1/2)，远大于n^(1/2)/2。但是一些较小的n会出现问题，所以进行特判解决。
下面证明数列a的pairwise sum是distinct的。如果a[i]+a[j] = a[k]+a[l]，那么考虑除以p的结果和余数，分别有2i+2j=2k+2l以及i^2+j^2==k^2+l^2 (mod p)。于是i–k =l–j且i^2-k^2 == l^2-j^2 (mod p)。显然i-k非0且mod p非0，于是得到i+k==l+j (mod p). 显然也有i-k==l-j (mod p)，于是i==l (mod p)，k==j (mod p)，结合i,j,k,l属于{1, 2, …, p}，于是有i=l，k=j。
另外，也可能有一些基于分治或者搜索的其他搜索，期待能看到一些有趣的解法。
随机方法构造的数列长度大约在n^(1/3)左右。
当我思考这个问题的时候并不知道这是一个被研究的组合问题，叫做Sidon set. 这个问题已经在2010年基本解决。实际上很多年前Paul Erdos和Pal Turan曾经证明对于n，答案最多是n^(1/2) + O(n^(1/4))。Singer有一个x^(1/2) (1-o(1))的构造。，细节可以看wikipedia。
代码
#include <iostream>
#include <cassert>
#include <stdio.h>
using namespace std;
bool isprime(int n) {
if (n == 2) return true;
for (int i = 2; i * i <= n; ++ i)
if (n % i == 0) return false;
return true;
}
void solve(int n) {
if (n <= 4) { cout << "1\n1" << endl; return; }
if (n <= 16) { cout << "2\n1 2" << endl; return; }
if (n <= 36) { cout << "3\n1 2 3" << endl; return; }
if (n <= 64) { cout << "4\n1 2 4 8" << endl; return; }
if (197 <= n && n <= 256) {cout << "8\n1 2 4 8 16 32 64 128" << endl; return; }
int p = 0;
for (int i = 2; 2 * i * i <= n; ++ i)
if (isprime(i)) p = i;
assert(4 * p * p >= n);
cout << p << endl;
for (int i = 1; i <= p; ++ i)
cout << 2 * i * p + ((i * i) % p) << " ";
cout << endl;
}
int main() {
int n;
cin >> n;
solve(n);
return 0;
}
通信
思路
http://immortalco.blog.uoj.ac/blog/2102
代码
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define REP(i, x, y) for(int i = (int)x; i <= (int)y; i ++)
#define FOR(i, x, y) for(int i = (int)x; i < (int)y; i ++)
#define PER(i, x, y) for(int i = (int)x; i >= (int)y; i --)
#define trace(x) cerr << #x << " " << x << endl;
#define dprintf(...) fprintf(stderr, __VA__ARGS__)
#define dln() fprintf(stderr, "\n")
using namespace std;
typedef long long LL;
typedef long double db;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
const int N = 800005;
const int P = 1e9 + 7;
const int inf = 1e9;
const LL Inf = 1e15;
const int S = 1000005;
char bf[S],*p1=bf,*p2=bf;
#define nc() (p1==p2&&(p2=(p1=bf)+fread(bf,1,S,stdin),p2==p1)?-1:*p1++)
inline int IN(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
inline int Pow(int x, int y, int p){
int an = 1;
for(; y; y >>= 1, x = (LL)x * x % p) if(y & 1) an = (LL)an * x % p;
return an;
}
void renew(int &x, int y){
x += y;
if(x < 0) x += P;
else if(x >= P) x -= P;
}
void setIO(string a){
#ifndef LOCAL
freopen((a + ".in").c_str(), "r", stdin);
freopen((a + ".out").c_str(), "w", stdout);
#else
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
}
template<typename T> inline void chkmin(T &a, const T &b) {if(a > b) a = b;}
template<typename T> inline void chkmax(T &a, const T &b) {if(a < b) a = b;}
typedef int ones[N];
typedef unsigned int u32;
bool st;
int n, top;
LL Lcost, Rcost;
ones X, Lx, Rx, stk;
struct Info{
LL Min;
u32 ways;
Info() = default;
Info(LL a, u32 b) : Min(a), ways(b) {}
};
Info operator +(const Info &a, const Info &b) {
return (a.Min < b.Min) ? a : ((a.Min > b.Min) ? b : Info(a.Min, a.ways + b.ways));
}
Info operator +(const Info &a, const LL &b) {
return Info(a.Min + b, a.ways);
}
Info A[16551425], B[16551425], C[16551425], D[16551425];
Info *curA = A, *curB = B, *curC = C, *curD = D;
Info dp[N];
//dp[i] = min(j < i) dp[j] + max(Ai - Ax, Bx - Bj)
//m1, x1 max = i
//m2, x2 max = j
struct segnode{
Info *m1, *m2, *x1, *x2;
int xl, xr, xmd;
void init(int l, int r){
xl = l;
xr = r;
xmd = (l + r) / 2;
m1 = curA; curA += r - l + 2;
m2 = curB; curB += r - l + 2;
x1 = curC; curC += r - l + 2;
x2 = curD; curD += r - l + 2;
REP(i, l, r) x1[i - l + 1].Min = 1LL << 60;
REP(i, l, r) x2[i - l + 1].Min = 1LL << 60;
}
void work(){
REP(i, xl, xr) m1[i - xl + 1] = dp[i];
REP(i, xl, xr) m2[i - xl + 1] = dp[i] + (-Rcost * i);
REP(i, xmd + 2 - xl + 1, xr - xl + 1) m1[i] = m1[i - 1] + m1[i], m2[i] = m2[i - 1] + m2[i];
PER(i, xmd - 1 - xl + 1, 1) m1[i] = m1[i + 1] + m1[i], m2[i] = m2[i + 1] + m2[i];
}
Info askopt1(int l, int r){
return m1[l - xl + 1] + m1[r - xl + 1];
}
Info askopt2(int l, int r){
return m2[l - xl + 1] + m2[r - xl + 1];
}
void renew(){
Info d1 = Info(1LL << 60, 0), d2 = d1;
REP(i, xl, xmd){
d1 = d1 + x1[i - xl + 1];
d2 = d2 + x2[i - xl + 1];
dp[i] = dp[i] + (d1 + (Lcost * i));
dp[i] = dp[i] + d2;
}
d1 = Info(1LL << 60, 0), d2 = d1;
PER(i, xr, xmd + 1){
d1 = d1 + x1[i - xl + 1];
d2 = d2 + x2[i - xl + 1];
dp[i] = dp[i] + (d1 + (Lcost * i));
dp[i] = dp[i] + d2;
}
}
void tag1(int l, int r, Info v){
// assert(xl <= l && l <= xmd && xmd < r && r <= xr);
l = l - xl + 1;
r = r - xl + 1;
x1[l] = x1[l] + v;
x1[r] = x1[r] + v;
}
void tag2(int l, int r, Info v){
// assert(xl <= l && l <= xmd && xmd < r && r <= xr);
l = l - xl + 1;
r = r - xl + 1;
x2[l] = x2[l] + v;
x2[r] = x2[r] + v;
}
} T[2100005];
int ID[N];
#define LEADZERO(x) (__builtin_clz(x) - 2)
#define HIGH_BIT(x) (30 - LEADZERO(x))
#define findv(l, r) ((ID[l]) >> HIGH_BIT(ID[l] ^ ID[r]))
Info ask1(int l, int r){
if(l == r) return dp[l];
int x = findv(l, r);
return T[x].askopt1(l, r);
}
Info ask2(int l, int r){
if(l == r) return dp[l] + (-Rcost * l);
int x = findv(l, r);
return T[x].askopt2(l, r);
}
void Tag1(int l, int r, Info v){
if(l == r){
dp[l] = dp[l] + (v + Lcost * l);
return;
}
int x = findv(l, r);
T[x].tag1(l, r, v);
}
void Tag2(int l, int r, Info v){
if(l == r){
dp[l] = dp[l] + v;
return;
}
int x = findv(l, r);
T[x].tag2(l, r, v);
}
int mxp[N];
void work(int x, int L, int R){
if(L == R) return;
int xl = L, xr = R, xmd = (L + R) / 2;
T[x].renew();
work(x << 1, L, xmd);
mxp[xmd + 1] = xmd + 1;
REP(i, xmd + 2, xr){
mxp[i] = mxp[i - 1];
if(X[i] > X[mxp[i]]) mxp[i] = i;
}
mxp[xmd] = xmd;
PER(i, xmd - 1, xl){
mxp[i] = mxp[i + 1];
if(X[i] > X[mxp[i]]) mxp[i] = i;
}
REP(i, xmd + 1, xr){
LL d = Lcost * (i - mxp[i]) / Rcost, pos1 = mxp[i] - d;
int Lt = max(Lx[mxp[i]] + 1, xl);
pos1 = max(pos1, (LL)Lt);
if(pos1 <= xmd) dp[i] = dp[i] + (ask1(pos1, xmd) + Lcost * (i - mxp[i]));
pos1 = min(pos1 - 1, (LL)xmd);
if(Lt <= pos1) dp[i] = dp[i] + (ask2(Lt, pos1) + Rcost * mxp[i]);
}
PER(i, xmd, xl){
int Rt = min(Rx[mxp[i]] - 1, xr);
LL pos1 = Rcost * (mxp[i] - i) / Lcost + mxp[i];
pos1 = min(pos1, (LL)Rt);
if(xmd + 1 <= pos1) Tag2(xmd + 1, pos1, dp[i] + Rcost * (mxp[i] - i));
pos1 = max(pos1 + 1, xmd + 1LL);
if(pos1 <= Rt) Tag1(pos1, Rt, dp[i] + (-Lcost * mxp[i]));
}
work(x * 2 + 1, xmd + 1, R);
T[x].work();
}
void build(int x, int L, int R){
if(L == R){
ID[L] = x << LEADZERO(x);
return;
}
int md = (L + R) >> 1;
build(x << 1, L, md);
build(x * 2 + 1, md + 1, R);
T[x].init(L, R);
}
bool en;
int main(){
//cerr << (&en - &st) / 1048576. << endl;
n = IN();
Lcost = IN();
Rcost = IN();
REP(i, 1, n) X[i] = IN();
REP(i, 1, n) dp[i] = Info(1LL << 60, 0);
dp[1] = Info(0, 1);
REP(i, 1, n) Rx[i] = n + 1;
REP(i, 1, n){
while(top && X[i] > X[stk[top]]){
Rx[stk[top]] = i;
top --;
}
if(top) Lx[i] = stk[top];
stk[++top] = i;
}
build(1, 1, n);
work(1, 1, n);
LL Ans1 = 0;
u32 Ans2 = 0;
REP(i, 1, n) Ans1 ^= dp[i].Min;
REP(i, 1, n) Ans2 ^= dp[i].ways;
cout << Ans1 << endl << Ans2 << endl;
return 0;
}#美团#