本场链接: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
",((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]...),将答案表达出来再根据单调性求值即可.特别的,当(xin[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
",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
",res);
forr(i,1,t)
{
if(n >= f[i]) n -= f[i],printf("%d
",(i&1) + 1);
printf("%d
",((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
",dfs(1,n,0,30));
return 0;
}