Preface
这场其实是上周六 VP 的，但因为后面连着好几天组队训练就一直没补题，拖到今天才补
这场VP 的时候写了 A~E，F 感觉会了但是急着吃饭就跑了，今天写了下 F 发现贼好写写完就过了，亏麻了
A. Sliding
签到，手玩下式子即可
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int t,n,m,r,c;
signed main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%lld%lld%lld%lld",&n,&m,&r,&c);
printf("%lld\n",(n-r)*m+(m-c)+(n-r)*(m-1));
}
return 0;
}
B. Everyone Loves Tres
看一眼好怪啊不会做，想了会无果索性直接打表找到规律
当 \(n\) 为偶数时答案形如 \(3333\dots33366\)；当 \(n\) 为奇数时答案形如 \(3333\dots36366\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int LIM=18;
vector <int> vec[25];
int t,n;
inline void DFS(CI now=0,CI sum=0)
{
if (now>LIM) return;
if (sum!=0&&sum%66==0) vec[now].push_back(sum);
DFS(now+1,sum*10+3); DFS(now+1,sum*10+6);
}
signed main()
{
// DFS(); for (RI i=1;i<=LIM;++i)
// if (!vec[i].empty()) printf("%lld\n",*min_element(vec[i].begin(),vec[i].end()));
for (scanf("%lld",&t);t;--t)
{
scanf("%lld",&n);
if (n==1||n==3) { puts("-1"); continue; }
if (n%2==0)
{
for (RI i=1;i<=n-2;++i) putchar('3');
puts("66");
} else
{
for (RI i=1;i<=n-5;++i) putchar('3');
puts("36366");
}
}
return 0;
}
C. Alya and Permutation
很神秘的构造啊，先考虑 \(n\) 为偶数的情形，令 \(k\) 为 \(n\) 二进制下的最高位
不难发现 \(2^{k+1}-1\) 是答案是上界，下面给出一种方法构造出这个上界
先将 \(1,2,3,4,7,8,2^k-1,2^k\) 放在序列最后，然后前面的奇数位置放剩下的偶数，偶数位置放剩下的奇数即可
不难发现此时前面一波操作后会得到一个 \(1\)，然后进入上面的序列后最终就会得到 \(2^{k+1}-1\)
当 \(n\) 为奇数时显然 \(n\) 就是答案的上界，因此把 \(1\sim n-1\) 用上述方法构造后，把 \(n\) 放在末尾即可
注意这个做法当且仅当 \(n=5\) 时需要特判一下
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
int t,n;
signed main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n); vector <int> ans;
auto solve=[&](CI n)
{
vector <int> vec;
auto check=[&](CI x)
{
return (x&(-x))==x;
};
for (RI i=n;i>=1;--i)
{
if (check(i)||check(i+1)) continue;
vec.push_back(i);
}
for (RI i=1;i<=n;++i)
if (check(i)||check(i+1)) vec.push_back(i);
return vec;
};
if (n==5) ans={2,1,3,4,5};
else if (n%2==0) ans=solve(n);
else ans=solve(n-1),ans.push_back(n);
int ret=0; for (RI i=0;i<ans.size();++i)
if (i&1) ret|=ans[i]; else ret&=ans[i];
printf("%d\n",ret);
for (auto x:ans) printf("%d ",x); putchar('\n');
}
return 0;
}
D. Yet Another Real Number Problem
先考虑一个无视数的规模时的做法，这个就很经典
拿一个递减的单调栈维护所有还可以往后操作的数，每次考虑如果把栈顶数中的 \(2\) 都换给当前数是否更优，是则弹栈
但直接做数的规模会变得不可控，因此很容易想到把每个数是 \(2\) 的多少次幂以及剩余部分开个结构体存起来
手玩一下比较的式子会发现可以推出十分简单的表达式，然后这题就做完了
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=1e9+7;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
inline void dec(int& x,CI y)
{
if ((x-=y)<0) x+=mod;
}
struct ifo
{
int val,p;
inline ifo(CI VAL=0,CI P=0)
{
val=VAL; p=P;
}
inline int rval(void)
{
return 1LL*val*quick_pow(2,p)%mod;
}
friend inline bool operator < (const ifo& A,const ifo& B)
{
if (B.p>=30) return 1;
return 1LL*A.val<1LL*B.val*(1LL<<B.p);
}
}stk[N]; int t,n;
signed main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n); int top=0,ans=0;
for (RI i=1;i<=n;++i)
{
ifo cur; scanf("%d",&cur.val);
while (cur.val%2==0) ++cur.p,cur.val/=2;
while (top&&stk[top]<cur)
{
dec(ans,stk[top].rval());
cur.p+=stk[top].p; stk[top].p=0;
inc(ans,stk[top--].rval());
}
stk[++top]=cur; inc(ans,cur.rval());
printf("%d%c",ans," \n"[i==n]);
}
}
return 0;
}
E. Monster
考虑令 \(f(i,j)\) 表示进行 \(i\) 次一操作，\(j\) 次二操作最多能打多少血，显然存在最优策略
即先进行 \(k\) 次一操作，\(1\) 次二操作的循环，一直到一操作用完，然后把剩下的二操作用完
则很容易推出 \(s=\min(\lfloor\frac{i}{k}\rfloor,j),f(i,j)=k\times \frac{s\times (s+1)}{2}+i\times (j-s)\)
观察这个式子会发现 \(f(i,j)\ge \frac{i\times j}{2}\)，在 \(j=\lfloor\frac{i}{k}\rfloor\) 取等号，因此我们可以推出 \(\min(i,j)\le \sqrt {2z}\)
直接枚举其中的一个然后二分另一个即可，单组数据复杂度 \(O(\sqrt z\log z)\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int LIM=2e4;
int t,x,y,z,k;
signed main()
{
for (scanf("%lld",&t);t;--t)
{
scanf("%lld%lld%lld%lld",&x,&y,&z,&k);
auto calc=[&](CI mxd,CI num)
{
int tmp=min(num,mxd/k);
return (tmp+1)*tmp/2LL*k+mxd*(num-tmp);
};
int ans=1e18;
for (RI i=1;i<=LIM;++i)
{
int l=1,r=z,mid,ret=-1;
while (l<=r) if (calc(i,mid=l+r>>1)>=z) ret=mid,r=mid-1; else l=mid+1;
if (ret!=-1) ans=min(ans,i*x+ret*y);
}
for (RI i=1;i<=LIM;++i)
{
int l=1,r=z,mid,ret=-1;
while (l<=r) if (calc(mid=l+r>>1,i)>=z) ret=mid,r=mid-1; else l=mid+1;
if (ret!=-1) ans=min(ans,ret*x+i*y);
}
printf("%lld\n",ans);
}
return 0;
}
F. Tree Operations
考虑当总操作次数固定时该怎么做，显然此时可以求出每个点操作的次数 \(c_i\)
不妨 DP 求解，令 \(f_i\) 表示处理完点 \(i\) 的子树后还需要上面进行多少次操作，首先有 \(f_u=a_u+\sum_{u\to v} f_v\)，然后分情况讨论：
- \(c_i\le f_i\)，此时直接令 \(f_i=f_i-c_i\) 即可，剩余的操作由祖先节点补上；
- \(c_i>f_i\)，此时多出的 \(c_i-f_i\) 次操作可以在一个点上重复加减消耗，因此 \(f_i=(c_i-f_i)\bmod 2\)；
但直接枚举操作次数也不现实，而直接对总操作次数二分也没有单调性
不过我们可以注意到，若 \(m\) 是一个合法的解，则 \(m+2n\) 也一定合法，因为我们至少可以通过在每个点处都加减抵消来达到相同的结果
因此这题直接枚举总操作次数对 \(2n\) 取模的结果，剩下的部分就有二分性了，总复杂度 \(O(n^2\log n)\)
#include<cstdio>
#include<iostream>
#include<vector>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=2005;
int t,n,rt,a[N],f[N]; vector <int> v[N];
inline void DP(CI now,CI lim,CI fa=0)
{
int cnt=lim/n+(now<=lim%n); f[now]=a[now];
for (auto to:v[now]) if (to!=fa) DP(to,lim,now),f[now]+=f[to];
if (f[now]>=cnt) f[now]-=cnt; else f[now]=(cnt-f[now])%2;
}
signed main()
{
for (scanf("%lld",&t);t;--t)
{
scanf("%lld%lld",&n,&rt);
for (RI i=1;i<=n;++i) scanf("%lld",&a[i]),v[i].clear();
for (RI i=1;i<n;++i)
{
int x,y; scanf("%lld%lld",&x,&y);
v[x].push_back(y); v[y].push_back(x);
}
int ans=1e18;
for (RI m=0;m<2LL*n;++m)
{
int l=0,r=2e9,mid,ret=-1;
while (l<=r)
{
mid=l+r>>1; DP(rt,2LL*n*mid+m);
if (f[rt]==0) ret=mid,r=mid-1; else l=mid+1;
}
if (ret!=-1) ans=min(ans,2LL*n*ret+m);
}
printf("%lld\n",ans);
}
return 0;
}
Postscript
最近比赛压力增大，而且也有几门课要期中考/期末考，同时某人的炉石瘾也越来越大了
但不管怎么说还是不能懈怠了训练啊
标签：CI,27,const,int,Global,Codeforces,include,RI,define From： https://www.cnblogs.com/cjjsb/p/18533864