AtCoder Regular Contest 122 A~D题解

本场链接:Tokio Marine & Nichido Fire Insurance Programming Contest 2021（AtCoder Regular Contest 122)

A - Many Formulae

容易想到按当前做到哪一个数作为划分依据进行dp,进一步可以发现放置的符号也是有关的:

• 状态:\(f[i][j]\)表示做完前\(i\)个元素,\(i\)元素之前的符号是\(j = 0\)时+反之为-.
• 入口:\(f[1][0] = 1\)
• 转移:可以发现填充符号的时候可能会有多个符合这个局面的和存在,额外记录一个状态表示个数:\(c[i][j]\)同\(f[i][j]\),则\(f[i][0] = (f[i - 1][0] + f[i - 1][1])*c[i][0],f[i][1] = f[i - 1][0] * c[i][1]\).\(c[i][0] = c[i - 1][0] + c[i - 1][1],c[i][1] = c[i - 1][0]\).
• 出口:\(f[n][0] + f[n][1]\).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
#define int ll
const int N = 1e5+7,MOD = 1e9+7;
int a[N],f[N][2],c[N][2];

signed main()
{
    int n;scanf("%lld",&n);
    forn(i,1,n) scanf("%lld",&a[i]);
    f[1][0] = a[1];
    c[2][0] = 1;c[2][1] = 1;
    forn(i,3,n) c[i][0] = (c[i - 1][0] + c[i - 1][1]) % MOD,c[i][1] = c[i - 1][0];
    forn(i,2,n)
    {
        f[i][0] = (1ll * f[i - 1][0] + f[i - 1][1] + 1ll * c[i][0] * a[i] % MOD) % MOD;
        f[i][1] = ((f[i - 1][0] - 1ll * c[i][1] * a[i] % MOD) % MOD + MOD) % MOD;
    }
    printf("%lld\n",((f[n][0] + f[n][1]) % MOD + MOD) % MOD);
    return 0;
}   

B - Insurance

因为表达式和\(min(a_i,2x)\)有关,考虑按段枚举\(x\)的取值:\([0,a_1/2],[a_1/2,a_2/2]...\),将答案表达出来再根据单调性求值即可.特别的,当\(x\in[a_n/2,+\infin]\)这个区间的时候取\(x=a_n/2\)最小,可以作为初值.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)

const int N = 1e5+7;
int a[N];
ll sum[N];

int main()
{
    int n;scanf("%d",&n);
    forn(i,1,n) scanf("%d",&a[i]);
    sort(a + 1,a + n + 1);
    forn(i,1,n) sum[i] = sum[i - 1] + a[i];
    double res = a[n] / 2.0;
    forn(i,0,n - 1)
    {
        double x;
        if(2 * i <= n)  x = a[i + 1] / 2.0;
        else x = a[i] / 2.0;
        res = min(res,(sum[n] - sum[i]) * 1.0 / n + (2 * i - n) * x / n);
    }

    printf("%.18lf\n",res);
    return 0;
}   

C - Calculator

这种构造题肯定有某种很特别的构造方式,(1)(2)操作都非常平常,然后可以非常神棍的这样发现:\(x=1,y=0\)如果交替执行\(3,4,3,4....\),\(x,y\)一定各是某个斐波那契数:考虑把\(n\)表达成某些\(fib(x)\)的和.假设一开始整个操作序列仅限于\(3,4,3,4...\),如果在一开始给一个\(x=1\)的操作的话,那么由于超过86步之后就会超过\(10^{18}\)所以这样交替操作的步数不会超过\(86\)左右.进一步的,可以发现如果在第\(i\)步插入(1)/(2)操作,就会让\(x\)的结果增加\(fib(k-i)\),其中\(k\)是交替的操作总步数.因为偶数步结束的时候是由\(y\)增加\(x\),所以在偶数步插入(1)操作;反过来插入(2)操作.

具体来说,首先找一个最大的\(t\),满足\(f(t) \leq n\).一开始的操作序列是交替执行\(3,4...\)一共\(t\)个.之后从大到小枚举是否可以插入\(fib(i)\),如果可以就直接放入并更新操作,如此构造即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)

const int N = 105;
ll f[N];

int main()
{
    ll n;scanf("%lld",&n);
    f[0] = 1;f[1] = 1;
    int t = 1;
    while(f[t - 1] + f[t] <= n) ++t,f[t] = f[t - 1] + f[t - 2];
    ll cur = n,res = t;
    forr(i,1,t) if(cur >= f[i])   cur -= f[i],++res;
    printf("%d\n",res);
    forr(i,1,t)
    {
        if(n >= f[i])   n -= f[i],printf("%d\n",(i&1) + 1);
        printf("%d\n",((i - 1) & 1) + 3);
    }
    return 0;
}   

D - XOR Game

考虑最终的答案每一位的取值:要让这个值比较小是比较顺的想法.

从高到低考虑每一位:如果\(2n\)个元素在这一位取\(1\)和取\(0\)的个数都是偶数,那么显然无论先手选择哪个元素,后手都可以镜像操作使这一位变成\(0\),为了保证之后不在这一位产生\(1\),将所有这一位是\(0\)的元素划分成一组,其他另成一组,往下递归继续做;如果是奇数,那么必须要从\(1\)和\(0\)两组元素中取一对出来,剩下的所有元素这一位产生的结果都会是\(0\),而且往后不可能有一个结果比取出来的一对数的结果更大,所以一旦出现了这样取一对出来的情况,他就是序列后缀能产生的最大值,因为不可能再有一对元素在这一位产生\(1\).所以取两个集合中异或值最小的一对元素即是这个后缀的答案.

如此可以先对整个\(\{a\}\)排序,这样就可以快速找到某位取\(1\)的分界线.之后执行一个dfs框架,每次划分组往下递归,找到不同的就求出答案返回.

对于两个集合各取一个元素求异或最小值的子问题是Trie基本操作,难度和本题差距过大就不展开了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)

const int N = 4e5+7,M = 32;
int tr[N * M][2],cnt[N * M],a[N],idx,n;

void insert(int x,int v)
{
    int p = 0;
    forr(i,0,30)
    {
        int k = x >> i & 1;
        if(!tr[p][k])   tr[p][k] = ++idx;
        cnt[tr[p][k]] += v;
        p = tr[p][k];
    }
}

int query(int x)
{
    int p = 0,res = 0;
    forr(i,0,30)
    {
        int k = x >> i & 1;
        if(tr[p][k] && cnt[tr[p][k]])   
        {
            p = tr[p][k];
            if(k)   res |= 1 << i;
        }
        else
        {
            p = tr[p][k ^ 1];
            if(k ^ 1)   res |= 1 << i;
        }
    }
    return res ^ x;
}

int dfs(int L,int R,int v,int dep)
{
    if(dep < 0 || L > R)   return 0;
    int p = lower_bound(a + 1,a + n + 1,v | (1 << dep)) - a;
    if((p - L) % 2 == 0)    return max(dfs(L,p - 1,v,dep - 1),dfs(p,R,v | (1 << dep),dep - 1));
    int res = 2e9;
    forn(i,0,idx)   tr[i][0] = tr[i][1] = 0;idx = 0;
    forn(i,L,p - 1) insert(a[i],1);
    forn(i,p,R) res = min(res,query(a[i]));
    return res;
}

int main()
{
    scanf("%d",&n);n *= 2;
    forn(i,1,n) scanf("%d",&a[i]);
    sort(a + 1,a + n + 1);
    printf("%d\n",dfs(1,n,0,30));
    return 0;
}   

AtCoder Regular Contest 122 A~D题解

原文：https://www.cnblogs.com/HotPants/p/14881114.html