T1. 硬币
一看到这题，我第一反应就是每堆钱越多，方差就越大。
所以不妨设每堆硬币有 \(x\) 个，对应的方差为 \(f(x)\)，于是我们就可以二分这个 \(x\)，\(O(n)\) 算一下方差，求出 \(k\) 两边的两个 \(f\) 值，看一看那个更接近就好了，复杂度 \(O(nlogn)\)。
看了一下数据范围发现并不能过，那我们就只能把式子写出来看看有没有什么优秀的性质：
\[\bar{a}=\frac{x\sum_{i=1}^n a_i}{n},a^2=\frac{\sum_{i=1}^n (xa_i-\bar{a})^2}{n}=\frac{\sum_{i=1}^n x^2a_i^2+\sum_{i=1}^n \bar{a}^2 -2\sum_{i=1}^n xa_i\bar{a}}{n} \]我们惊奇地发现，\(f(x)=f(1) \times x^2\)
那么我们求方差的复杂度就变成 \(O(1)\) 的了，复杂度 \(O(n)\)，当然你也可以直接除一下即可，复杂度是一样的，可以通过本题。
code:
#include<bits/stdc++.h>
#define N 10001001
using namespace std;
typedef double db;
typedef long long ll; //十年 OI 一场空，不开 long long 见祖宗
inline void read(ll &ret)
{
scanf("%lld",&ret);
return;
}
ll n,k;
ll a[N];
signed main()
{
// freopen("coin024.in", "r", stdin);
// freopen("coin024.out", "w", stdout);
read(n);
read(k);
db now=0.0;
for(int i=1;i<=n;i++)
read(a[i]),now+=1.0*a[i];
now/=n;
db sum=0.0;
for(int i=1;i<=n;i++)
sum+=(now-1.0*a[i])*(now-1.0*a[i]);
sum/=n; //用 sum 计算方差
if(fabs(sum)<1e-9) //第一种情况
{
puts("No answer!");
exit(0);
}
ll x=floor(sqrt(k/sum)),y=ceil(sqrt(k/sum)); //此处用 x,y 代表思路中的 a,b
if(!x) //第二种情况
{
printf("%lld\n",y);
return 0;
}
if(fabs(x*x*1.0*sum-k)<=fabs(y*y*1.0*sum-k)) //第三种情况
printf("%lld\n",x);
else
printf("%lld\n",y);
return 0;
}
T2.刷题
首先，我们发现每个时刻要么做一道题，能力值减少，要么能力值增加，我们关心的元素只有现在做的题目数量 \(x\) 和当前的能力值 \(w\)，可以被描述为一个二元组 \((x,w)\)。
那么就有了一个很显然的 dp，设 \(f[x][w]\) 表示当前做了 \(x\) 道题，能力值为 \(w\) 这个状态是否可达，\(x\) 的答案就是最大的 \(q\) 满足 \(f[x][q]=1\)，状态数 \(O(mV)\)，转移 \(O(n)\)，复杂度
\(O(mnV)\)。
但我们发现，当 \(m\) 足够大，取到 \(O(n)\) 级别的时候，\(f\) 的取值就固定了，分 \(x\) 是奇数和偶数讨论即可，复杂度 \(O(n^2V)\)。
我们发现转移的 \(O(n)\) 是无法去掉的，于是我们从状态下手，这个 \(0/1\) 的状态一看就很浪费，而且我们发现一个性质，当 \(t\) 这个时刻到达 \(x\) 这个点时，\(t+2\) 这个时刻也能到达。
这启发我们把状态拆点，拆成奇数时刻到达点和偶数时刻到达点，这样的话我们第一次在 \(t\) 时刻到达点 \(t\) 时，所有 \(t+2i\) 时刻都能到达，所以我们现在只关心第一次到达点 \(t\) 的时间了。
于是我们把这张图建出来跑个最短路，在线回答询问即可。
code:
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#define pi pair<int,int>
using namespace std;
void in(int &x){
x=0;int f=1;
char c=getchar();
while((c>'9'||c<'0')&&c!='-')c=getchar();
if(c=='-')f=-1,c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
x*=f;
}
void inn(long long &x){
x=0;int f=1;
char c=getchar();
while((c>'9'||c<'0')&&c!='-')c=getchar();
if(c=='-')f=-1,c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
x*=f;
}
void out(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)out(x/10);
putchar(x%10+'0');
}
int n,m,k,t,p,x,z,v[4005];
struct node{
int v,next,w;
}edge[16000005];
int num,head[5005];
int a[5005][2],ans[8005];
bool vis[5005][2];
void add(int u,int v,int w){
edge[++num].next=head[u];
edge[num].v=v;
edge[num].w=w;
head[u]=num;
}
queue<int>q;
void spfa(int s){
memset(a,0x3f,sizeof a);
memset(vis,0,sizeof vis);
a[s][0]=0;
queue<pi>q;
q.push(make_pair(s,1));
while(!q.empty()){
int k=q.front().first;
int l=q.front().second;
q.pop();
vis[k][l]=0;
for(int i=head[k];i;i=edge[i].next){
int v=edge[i].v;
if(a[v][0]>1+a[k][1]){
a[v][0]=1+a[k][1];
if(!vis[v][0]){
vis[v][0]=1;
q.push(make_pair(v,l^1));
}
}
if(a[v][1]>1+a[k][0]){
a[v][1]=1+a[k][0];
if(!vis[v][1]){
vis[v][1]=1;
q.push(make_pair(v,l^1));
}
}
}
}
}
signed main(){
in(n);in(t);
for(int i=1;i<=n;i++){
in(x);
if(v[x])continue;
v[x]=1;
for(int j=0;j<4000;j++){
if(j>=x)add(j,j-x,1);
else add(j,j+x,1);
}
}
spfa(0);
for(int i=1;i<=8000;i++){
for(int j=3999;j>=0;j--){
if(a[j][i%2]<=i){
ans[i]=j;
break;
}
}
}
while(t--){
long long y;
inn(y);
if(y>=8000){
if(y%2)y=7999;
else y=8000;
}
out(ans[y]);
putchar('\n');
fflush(stdout);
}
}
T3.猜数
首先，你的策略是什么？获得了多少分呢？
然后我们来感性地推测出一个比较优的策略，设我们当前区间长度为 \(n\)，询问的区间为 \([l,r]\)，那么交互库会怎么回答你呢？
由于最后的答案 \(q\) 和指定的数 \(u\) 都是自适应的，所以交互库会尽量让你接下来能确定的区间尽量长，那么接下来我们能确定的区间就是 \([l,n]\) 和 \([1,r]\) 中更长的一个，所以我们询问的区间要越靠中间越好。
接下来我们要确定区间长度 \(len\)，根据代价函数 \(\frac{1}{len}\)，这个东西感性理解的话如果太长了肯定不优，因为长度每减少 2，接下来确定的区间长度就能减少 1，并且长度大了的话代价几乎不变了，这是，你陷入了迷茫，长度到底是多少才最优呢？
可设 \(f[i]\) 表示当前能确定的区间长度为 \(i\) 时，确定最终的数的代价，转移的话，我们枚举长度 \(len\)，算出中间那个区间 \([l,r]\)，转移如下：\(f[i]=min{max(f[r-1],f[i-l])+\frac{1}{len}}\)。
这是一个 \(O(n^2)\) 的 dp，要优化的话我们打出表来看看。
设 \(g[i]\) 表示长度为 \(i\) 的区间第一步选取的区间长度，我们惊奇地发现，在一段区间里 \(g[i]\) 和 \(g[i-1]\) 相差不大，然后突然增加。
有了这个思路，我们把 1e5 以下的表都打出来，发现突然增加的力度超过 50 的数只有 25 个，于是我们把这些数记录下来，其他 \(g[i]\) 只要取 \(len\in [g[i−1]−5,g[i−1]+50]\) 即可，复杂度 \(O(50n)\)。
code:
# include <stdio.h>
# include <algorithm>
# define lim 100000
# define lowbit(x) (x&(-x))
# define clr() fflush(stdout)
# define ldb long double
ldb f[100010];
int g[100010];
int che[100010];
ldb c[100010];
void init()
{
che[431]=1;
che[612]=1;
che[868]=1;
che[1233]=1;
che[1748]=1;
che[2480]=1;
che[2573]=1;
che[3512]=1;
che[4961]=1;
che[7004]=1;
che[9526]=1;
che[9895]=1;
che[11545]=1;
che[13969]=1;
che[16129]=1;
che[19774]=1;
che[22408]=1;
che[27985]=1;
che[30882]=1;
che[35084]=1;
che[39596]=1;
che[42055]=1;
che[50338]=1;
che[56028]=1;
che[56236]=1;
che[72630]=1;
che[77920]=1;
che[79207]=1;
}
void add(int pos)
{
int i,j;
c[pos]=c[pos-1]+f[pos];
return;
}
ldb qj(int x,int y)
{
return c[y]-c[x-1];
}
int read()
{
int now=0;
char c=getchar();
while(c<'0' || c>'9')
c=getchar();
while(c>='0' && c<='9')
{
now=(now<<1)+(now<<3)+(c&15);
c=getchar();
}
return now;
}
ldb gtans(int x,int y)
{
ldb anss=0;
int cu=y;
if(x&1)
{
if(y==1)
return f[x/2];
x++;
y--;
}
return f[x/2+(y+1)/2-1];
}
int main()
{
int i,j,n,m,l,r;
init();
n=read();
f[1]=0;
g[1]=1;
add(1);
for(i=2;i<=n;i++)
{
int y=std::max(g[i-1]-1,1);
int li=std::min(i,i/2+2);
if(!che[i])
li=std::min(li,g[i-1]+40);
for(j=std::max(g[i-1]-1,(i&1))+2;j<=li;j+=2)
{
if(gtans(i,j)+(1.0/(ldb)j)<gtans(i,y)+(1.0/(ldb)y))
y=j;
}
j=y;
f[i]=gtans(i,j)+(1.0/(ldb)j);
g[i]=j;
add(i);
}
l=1;
r=n;
while(l<r)
{
int u,v;
v=(l+r)/2+(g[r-l+1])/2;
u=v-g[r-l+1]+1;
printf("? %d %d\n",u,v);
clr();
scanf("%d%d",&u,&v);
if(v==0)
l=u+1;
if(v==1)
{
l=u;
r=u;
}
if(v==2)
r=u-1;
}
printf("! %d\n",l);
clr();
return 0;
}
T4.翻转序列
这是一道顺藤摸瓜的题，只要耐心思考，就一定能做出来。
一个显然的策略是取 \(x=1\)，即可以交换相邻两个数的位置，就可以像冒泡排序一样给序列排序，次数是 \(O(逆序对个数)\) 的。
我们来考虑这个过程，比如我们先找到 1 ，把 1 不断交换到第一个位置，再找到 2 ，把 2 不断交换到第二个位置...... 这就启发我们，能不能有操作次数更少的方法，使得把 \(i\) 交换到第 \(i\) 个位置且不改变前 \(i−1\) 个数的位置。
这个过程是很简单的，假设我们现在操作的数字是 \(i\) ，位置为 \(loc\)，那我们就不断把 \(loc\) 转到 \(loc-x\)，然后再转到 \(i+x\)，最后转回 \(i\)。
但是这样操作有一个问题，就是最后 \(\frac{3}{2} x\) 的序列没法复原，这下怎么办呢，我们需要找到另外的操作，使得这个操作能在不改变其他值的情况下交换相邻两个数的位置，这样就可以用上面冒泡排序来做了。
但遗憾的是，我仍未知道这种操作是否可行，但我找到了交换距离为 2 的数的方法。假设我们要交换 \(a_i\) 和 \(a_{i+2}\)，那么我们可以进行如下四次操作：
- \(rev(i+2-x,i+2)\)
- \(rev(i+4-x,i+2)\)
- \(rev(i+3-x,i+1)\)
- \(rev(i+2-x,i)\)
这样如果我们再通过一种方法，使得后面的数和下标的奇偶性相同，这题就做完了。
我们定义一个位置的半契合性为这个位置的奇偶性是否与当前位置上数的奇偶性相同，那么问题等价为我们使得后面所有位置的半契合性为 1 即可。
那么我们有什么跟这个半契合性相关的操作呢？比如改变某个位置的半契合性之类的？
Luckily，我们可以进行如下操作，来改变相邻两个位置 \(i\) 和 \(i+1\) 的半契合性：
- \(rev(i+1−x,i+1)\)
- \(rev(i+3−x,i+1)\)
由于给定的是一个排列，所以不满足半契合性的位置个数一定是偶数，所以我们先把满足半契合性的位置移动到前面，再把后面的半契合性全改成 1，最后再对整个序列做一次奇偶位置上的冒泡排序，这题就解决了。
那么我们来分析一下这个 \(x\) 取多少合适：
- 首先把 \(1\to n− \frac{3}{2} x\) 这些数移到前面，次数约为 \(\frac{n^2}{2x}\)。
- 其次把满足半契合度的位置移到后 \(\frac{3}{2} x\) 个位置的前半部分，次数约为 \(\frac{9x^2}{4}\)。
- 接着把后面的半契合度都改对，次数约为 \(x\)。
- 最后整个序列冒泡排序，受影响的只有后面 \(\frac{3}{2} x\) 个位置，所以次数约为 \(\frac{9x^2}{4}\)。
最后均值不等式算一下，当 \(x=\sqrt[3]{\frac{n^2}{18}}\) 时最优，次数大概为 19000，但是由于我们之前算的都是最坏情况，实际测试中远达不到这个上界，可以通过此题。
# include <stdio.h>
# include <math.h>
# include <algorithm>
int rem[25010][2],totr,xx;
int a[10010],p[10010],n,totn;
int same(int x,int y)
{
if((x&1)==(y&1))
return 1;
return 0;
}
void reverse(int x,int y)
{
int i,j;
totr++;
rem[totr][0]=x;
rem[totr][1]=y;
for(i=x;i<=y;i++)
{
j=y+x-i;
if(i<j)
{
std::swap(p[a[i]],p[a[j]]);
std::swap(a[i],a[j]);
}
}
return;
}
void gett(int y)
{
int i,j;
while(p[y]>y)
{
int x=p[y];
if(x-xx>=y)
{
reverse(x-xx,x);
continue;
}
if(same(x,y+xx))
{
reverse(y,y+xx);
continue;
}
else
{
j=(x-y)/2;
reverse(x-j,y+xx+j);
continue;
}
}
return;
}
void swapp(int y)
{
while(p[y]>y)
{
int x=p[y];
reverse(x-xx-1,x-1);
reverse(x-xx,x);
reverse(x-xx-1,x-1);
reverse(x-xx-1,x-3);
}
return;
}
void changee(int y)
{
y++;
if(y+xx<=n)
{
reverse(y,y+xx);
y+=xx+1;
}
if((n-y+1)>(xx+1-(n-y+1)))
{
reverse(n-xx,n);
y=n-(xx+1-(n-y+1))+1;
}
y--;
while(y!=n)
{
y+=2;
reverse(y-xx,y);
reverse(y-xx+2,y);
}
return;
}
void bl(int x)
{
while(p[x]!=x)
{
int y=p[x];
reverse(y-1,y);
}
return;
}
int done()
{
int i,j;
if(totn>n)
return 0;
if(same(totn,a[totn]))
return 1;
for(i=totn+1;i<=n;i++)
{
if(same(totn,a[i]) && same(totn,i))
{
int y=a[i];
while(p[y]>totn)
{
int x=p[y];
reverse(x-xx-1,x-1);
reverse(x-xx,x);
reverse(x-xx-1,x-1);
reverse(x-xx-1,x-3);
}
return 1;
}
}
return 0;
}
int main()
{
int i,j,m;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
p[a[i]]=i;
}
if(n<=20)
{
for(i=1;i<=n;i++)
bl(i);
printf("3\n%d\n",totr);
for(i=1;i<=totr;i++)
printf("%d %d\n",rem[i][0],rem[i][1]);
return 0;
}
xx=(int)pow(n*n/10,1.0/3);
if(!(xx&1))
xx++;
printf("%d\n",xx);
for(i=1;i<=n-xx-xx/2-1;i++)
gett(i);
totn=n-xx-xx/2;
while(1)
{
if(!done())
break;
totn++;
}
changee(totn-1);
for(i=1;i<=n;i++)
swapp(i);
printf("%d\n",totr);
for(i=1;i<=totr;i++)
printf("%d %d\n",rem[i][0],rem[i][1]);
return 0;
}
T5.循环节
这是一道计算几何题。
首先 \(x\) 这个向量一定是由某两个向量减出来的，所以我们就暴力枚举这个 \(x\) 去 check，复杂度 \(O(n^3)\)。
接着我们想办法快速求 \(x\)，首先对点集求一个凸包，接着做一个旋转卡壳，如果某个时刻经过了 \(\geq 4\) 个点，那么必存在连线平行。我们就选点数少的那一条平行线，可以求出 \(z\) 和 \(x\)。
然后我们就需要找出所有起点，只要看看当前这个点减去向量 \(x\) 之后的位置上有没有点即可。这个可以拿一个 map 维护，或者把所有点排序之后二分，复杂度 \(O(n logn)\)。
这里有几个细节：
- 如何在一条线上求出 \(z\) 和 \(x\)？首先由于没有三个起点共线，那么起点的个数只能为 1 或 2，分别 check 一下即可。
- 如果所有点共线，需要特判。
# include <stdio.h>
# include <map>
# include <algorithm>
# define int long long
using std::map;
struct vect
{
int x,y;
vect(int _x=0,int _y=0)
{
x=_x;
y=_y;
}
int operator * (const vect w)
{
return this->x*w.y-this->y*w.x;
}
bool operator != (const vect w)
{
return (this->x!=w.x || this->y!=w.y);
}
vect operator + (const vect w) const
{
return vect(this->x+w.x,this->y+w.y);
}
vect operator - (const vect w) const
{
return vect(this->x-w.x,this->y-w.y);
}
bool operator < (const vect &w) const
{
return (x<w.x || x==w.x && y<w.y);
}
}a[100010],b[100010];
int cmp(vect x,vect y)
{
return (x.x<y.x || x.x==y.x && x.y<y.y);
}
int ts[100010],tots,tx[100010],totx;
int totz,z[100010];
map< vect,int >mp;
signed main()
{
int i,j,n,m,x,y,laci;
int ss,xx;
int tos=0,tox=0;
vect js=0,jx=0;
vect djl,cjl;
vect las;
scanf("%lld",&n);
for(i=1;i<=n;i++)
{
scanf("%lld%lld",&x,&y);
a[i].x=x;
a[i].y=y;
b[i]=a[i];
}
std::sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i++)
{
if(!tots)
{
tots++;
ts[tots]=i;
continue;
}
while(tots>1)
{
if((a[ts[tots]]-a[ts[tots-1]])*(a[i]-a[ts[tots-1]])>0)
tots--;
else
break;
}
tots++;
ts[tots]=i;
}
for(i=n;i>=1;i--)
{
if(!totx)
{
totx++;
tx[totx]=i;
continue;
}
while(totx>1)
{
if((a[tx[totx]]-a[tx[totx-1]])*(a[i]-a[tx[totx-1]])>0)
totx--;
else
break;
}
totx++;
tx[totx]=i;
}
if(n==1)
{
printf("1\n1\n0 0\n0");
return 0;
}
if(tots==n && totx==n)
{
int ff=0;
djl=a[2]-a[1];
for(i=3;i<=n;i++)
{
if(a[i]-a[i-1]!=djl)
{
ff=1;
cjl=a[i]-a[1];
j=i;
break;
}
}
if(!ff)
{
for(i=1;i<=n;i++)
mp[a[i]]=1;
for(i=1;i<=n;i++)
{
if(!mp[b[i]-djl])
{
j=i;
break;
}
}
printf("1\n%lld\n%lld %lld\n%lld",j,djl.x,djl.y,n-1);
return 0;
}
for(i=1;i<=n;i++)
mp[a[i]]=1;
int tot1=0,tot2=0;
for(i=1;i<=n;i++)
{
if(mp[a[i]+djl])
tot1++;
if(mp[a[i]+cjl])
tot2++;
}
printf("2\n");
if(tot1>=tot2)
{
for(i=1;i<=n;i++)
{
if(!mp[b[i]-djl])
printf("%lld ",i);
}
printf("\n%lld %lld\n%lld",djl.x,djl.y,(n-2)/2);
return 0;
}
else
{
for(i=1;i<=n;i++)
{
if(!mp[b[i]-cjl])
printf("%lld ",i);
}
printf("\n%lld %lld\n%lld",cjl.x,cjl.y,(n-2)/2);
return 0;
}
}
for(i=1;i<=n;i++)
mp[a[i]]=i;
vect u,v;
ss=1;
xx=1;
int ff=0;
while(ss<tots && xx<totx)
{
u=a[ts[ss+1]]-a[ts[ss]];
v=a[tx[xx]]-a[tx[xx+1]];
if(u*v==0)
{
ff=1;
break;
}
if(u*v<0)
ss++;
else
xx++;
}
if(!ff)
{
printf("%lld\n",n);
for(i=1;i<=n;i++)
printf("%lld ",i);
printf("\n0 0\n0");
return 0;
}
tos=1;
tox=1;
js=a[ts[ss+1]]-a[ts[ss]];
jx=a[tx[xx+1]]-a[tx[xx]];
ss++;
xx++;
// printf("!%lld %lld\n",a[ss-1].x,a[ss-1].y);
for(i=ss;i<tots;i++)
{
if((a[ts[i+1]]-a[ts[i]])*(a[ts[i]]-a[ts[i-1]]))
break;
tos++;
}
for(i=xx;i<totx;i++)
{
if((a[tx[i+1]]-a[tx[i]])*(a[tx[i]]-a[tx[i-1]]))
break;
tox++;
}
if(tos>=tox)
{
laci=tox;
las=jx;
}
else
{
laci=tos;
las=js;
}
for(i=1;i<=n;i++)
{
if(!mp[a[i]-las])
{
totz++;
z[totz]=i;
}
}
if(2*totz==n && totz>=3 && !((a[z[2]]-a[z[1]])*(a[z[3]]-a[z[2]])))
{
las=a[z[2]]-a[z[1]];
laci=totz-1;
totz=0;
for(i=1;i<=n;i++)
{
if(!mp[b[i]-las])
{
totz++;
z[totz]=i;
}
}
}
else
{
totz=0;
for(i=1;i<=n;i++)
{
if(!mp[b[i]-las])
{
totz++;
z[totz]=i;
}
}
}
printf("%lld\n",totz);
for(i=1;i<=totz;i++)
printf("%lld ",z[i]);
printf("\n%lld %lld\n%lld",las.x,las.y,laci);
return 0;
}