最近状态差到爆炸.

\(AT\)连掉两把分，啥时候能上黄啊。

\(A\)

考虑直接动归。

把\(O(n^2)\)的动归后缀和优化成\(O(n)\)

A

#include<iostream>
#include<cstdio>
#define ll long long
#define N 100005
#define mod 1000000007

ll a[N],f[N],g[N],sf[N],sg[N];
ll n,ans,sum;

int main(){
    scanf("%lld",&n);
    for(int i = 1;i <= n;++i)
    scanf("%lld",&a[i]),sum = (sum + a[i]) % mod;
    //f:i为-时从i到n有多少种合法方案，g:这些合法方案的权数。
    f[n] = 1,g[n] = (-2 * a[n] + mod) % mod;
    f[n + 1] = 1;
    sf[n] = 2,sf[n + 1] = 1,sg[n] = g[n];
    for(int i = n - 1;i >= 2;--i){
        f[i] = sf[i + 2];
        g[i] = (f[i] * (-2 * a[i] + mod) % mod + sg[i + 2]) % mod;
        sf[i] = (sf[i + 1] + f[i]) % mod;
        sg[i] = (sg[i + 1] + g[i]) % mod;
    }
//    for(int i = n;i >= 2;--i)
//    std::cout<<f[i]<<" "<<g[i]<<std::endl;
    for(int i = n;i >= 2;--i)
    ans = (ans + sum * f[i] % mod + g[i]) % mod;
    ans = (ans + sum) % mod;
    std::cout<<ans<<std::endl;
} 

\(B\)

听说B是一个结论题，正解来看呢，应该是把\(n\)个可取值都试一遍，但是我写的模拟退火。

B

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cmath>
#define ll long long
#define N 100005

struct P{int x,y,w;}p[N];

ll n;

double ansx,ansy;

inline  double find(double x){
    double ans = 0;
    for(int i = 1;i <= n;++i)
    ans += (p[i].x + x - std::min((double)p[i].x,(double)(2 * x))) / (1.0 * n);
    return ans;
}

int main(){
//    freopen("q.in","r",stdin);
//    freopen("q.out","w",stdout);
    srand(273352);
    scanf("%lld",&n);
    for(int i = 1;i <= n;++i){
        scanf("%d",&p[i].x);
        ansx += p[i].x; }
    ansx = (ansx) / (1.0 * n);
    ansy = 0x7f7f7f7f;
    double eps = 1e-15;
    double T = 200;//初始温度
    while(T > eps && ((double)(clock())/CLOCKS_PER_SEC)<1.9){//终止态
//        std::cout<<T<<" "<<(rand() * 2 - RAND_MAX) * T<<std::endl;
        double nowx = ansx + ((rand() * 2 - RAND_MAX + 1) * T);//在值域[ansx - t,ansx + t];中挑选一个随机数
        long double z = find(nowx) - find(ansx);
        if(z < 0)
        ansx = nowx,ansy = std::min(ansy,find(nowx));
        else
        if(exp(-z / T) * RAND_MAX > rand())//随机接受
        ansx = nowx;
        T *= 0.997;//降温速率
//        std::cout<<ansx<<std::endl;
    }
    printf("%.12lf\n",ansy);
} 

\(C\)

考虑每一个数在\(fib\)数系下都有唯一分解。

做完了。

C

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long

ll f[200],to[200],ti[200];
ll ans[200];

ll n;
ll k;

//0 1
//1 1
//1 2
//1 3
//4 3
//4 7

int main(){
    scanf("%lld",&n);
    ll q = n;
    ll len = 1;
    f[0] = 1,f[1] = 1;
    while(f[len] <= n + 1){
        f[++len] = f[len - 1] + f[len - 2];
    }
    for(int i = len;i >= 1;--i)
    if(n >= f[i])
    to[++to[0]] = i,n -= f[i];
    std::sort(to + 1,to + to[0] + 1);
    for(int i = 1;i <= to[0];++i)
    ti[i] = to[to[0]] - to[i];
    std::sort(ti + 1,ti + to[0] + 1);
    ll s = to[to[0]];
    ll x = 0,y = 0;
    ll now = 1;
    for(int i = 0;i <= s;++i){
        if(i == ti[now]){
            if(i & 1)
            ans[++k] = 1,x += 1;
            else
            ans[++k] = 2,y += 1;
            ++now;
        }
        if(i & 1)
        ans[++k] = 4,y += x;
        else
        ans[++k] = 3,x += y;
    }
    std::cout<<k<<std::endl;
    if(x == q){
        for(int i = 1;i <= k;++i)
        std::cout<<ans[i]<<std::endl;
    }
    else{
        for(int i = 1;i <= k;++i){
            if(ans[i] <= 2)
            std::cout<<3 - ans[i]<<std::endl;
            else
            std::cout<<7 - ans[i]<<std::endl;
        }
    }
} 

\(D\)

考虑如果后手已经想好的每个数对，那么其实游戏进程没有差别。

所以这是一个假博弈。

我们考虑对每一位进行操作，如果这一位的\(0\),\(1\)的数量都是偶数，那么递归进子树操作。

否则则把左子树和右子树左右匹配，用\(01tire\)找出最小的匹配,因为再往下递归的所有对都小于这个匹配。

D

#include<iostream>
#include<cstdio>
#define ll long long

ll to[12000005][2];
ll cnt[12000005];

ll n;

ll dfncnt;

inline void insert(ll x){
    ll u = 0;
    cnt[u] ++ ;
    for(int i = 29;i >= 0;--i){
        int t = (x >> i) & 1;
        if(!to[u][t])
        to[u][t] = ++ dfncnt;
        u = to[u][t];
        cnt[u] ++ ;
    }
} 

ll ans = 0,tmp;

#define l(u) to[u][0]
#define r(u) to[u][1]

inline void find(ll p1,ll p2,ll now,ll dep){
//    std::cout<<p1<<" "<<p2<<" "<<now<<" "<<dep<<std::endl;
    if(dep == 0){
        tmp = std::min(now,tmp);
        return;
    }
    bool q = 0;
    for(int i = 0;i <= 1;++i)
    if(to[p1][i] && to[p2][i]){
        q = 1;
        find(to[p1][i],to[p2][i],now,dep - 1);
    }
    if(q)
    return;
    for(int i = 0;i <= 1;++i)
    if(to[p1][i] && to[p2][!i]){
        find(to[p1][i],to[p2][!i],now | (1 << (dep - 1)),dep - 1);
        q = true;
    }
}

inline void dfs(int u,int dep){
//    std::cout<<u<<" "<<dep<<std::endl;
    if(!to[u][1] && !to[u][0])
    return;
    if(cnt[l(u)] % 2 && cnt[r(u)]){
        tmp = (1 << 30);
        find(l(u),r(u),(1 << (dep - 1)),dep - 1);
        ans = std::max(ans,tmp);
        return ;
    }
    if(l(u))
    dfs(l(u),dep - 1);
    if(r(u))
    dfs(r(u),dep - 1);
}

int main(){
    scanf("%lld",&n);
    for(int i = 1;i <= 2 * n;++i){
        ll x;
        scanf("%lld",&x);
        insert(x);
    }
    dfs(0,30);
    std::cout<<ans<<std::endl;
} 

\(E\)

由于\(lcm(x,y) = \frac{x * y}{gcd(x,y)}\)

考虑最后一个数，那么有\(gcd(lcm(a_j),a_i) < a_i\)

即\(lcm（gcd(a_i,a_j)) < a_i\)这里是由于精度所以不能选择前一种（

然后依次从后向前选择就好了。

E

#include<iostream>
#include<cstdio>
#define ll long long
#define N 305

ll ans[N],a[N];
bool vis[N];

ll n;

inline ll g(ll a,ll b){return (b == 0) ? a : g(b,a % b);}

int main(){
    scanf("%lld",&n);
    for(int i = 1;i <= n;++i)
    scanf("%lld",&a[i]);
    for(int i = n;i >= 1;--i){
        bool q;
        for(int j = 1;j <= n;++j){
            ll lcm = 1;
            ll gcd = 1;
            if(!vis[j]){
                q = 1;
                for(int k = 1;k <= n;++k){
                    if(!vis[k] && k != j){
                        gcd = g(a[k],a[j]);
                        lcm = lcm / g(gcd,lcm) * gcd;
                        if(lcm >= a[j]){
                            q = 0;
                            break;
                        }
                    }
                }
                if(q){
                    ans[i] = a[j];
                    vis[j] = 1;
                    break;
                }
            }
        }
        if(!q){
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    for(int i = 1;i <= n;++i)
    std::cout<<ans[i]<<" ";
}