T1. Coin
As soon as I saw this question, my first reaction was that the more money each pile, the greater the variance.
Therefore, let's assume that there are \ (x \) coins in each pile, and the corresponding variance is \ (f(x) \), so we can divide this \ (x \), \ (O(n) \) to calculate the variance, and find out the two \ (f \) values on both sides of \ (k \), and look at the one that is closer. The complexity is \ (O(nlogn) \).
After looking at the data range, it is found that it can not be exceeded, so we can only write out the formula to see if there are any excellent properties:
We were surprised to find that \ (f(x)=f(1) \times x^2 \)
Then the complexity of finding variance becomes \ (O(1) \), complexity \ (O(n) \), of course, you can also divide it directly. The complexity is the same, and you can pass this question.
code:
#include<bits/stdc++.h>
#define N 10001001
using namespace std;
typedef double db;
typedef long long ll; //In ten years, OI is empty, and we can't see our ancestors in 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; //Calculate variance with sum
if(fabs(sum)<1e-9) //First case
{
puts("No answer!");
exit(0);
}
ll x=floor(sqrt(k/sum)),y=ceil(sqrt(k/sum)); //Here, X and Y represent a and B in the train of thought
if(!x) //The second case
{
printf("%lld\n",y);
return 0;
}
if(fabs(x*x*1.0*sum-k)<=fabs(y*y*1.0*sum-k)) //The third case
printf("%lld\n",x);
else
printf("%lld\n",y);
return 0;
}
T2. Brush questions
First of all, we find that each time we either do a problem, the ability value decreases or the ability value increases. The only elements we care about are the number of problems we do now \ (x \) and the current ability value \ (w \), which can be described as a binary \ ((x,w) \).
Then there is an obvious dp. Let \ (f[x][w] \) indicate whether the current \ (x \) question has been done, and the capability value is \ (w \). The answer to \ (x \) is that the maximum \ (Q \) satisfies \ (f[x][q]=1 \), the number of states \ (O(mV) \), the transition \ (O(n) \), and the complexity
\(O(mnV)\).
However, we find that when \ (m \) is large enough and reaches the \ (O(n) \) level, the value of \ (f \) is fixed. The points \ (x \) are odd and even. We can discuss the complexity \ (O(n^2V) \).
We find that the transferred \ (O(n) \) cannot be removed, so we start from the state. The state of \ (0 / 1 \) is very wasteful at first sight, and we find a property that when \ (t \) reaches the point of \ (x \), the moment of \ (t+2 \) can also be reached.
This inspires us to split the state into odd time arrival points and even time arrival points. In this way, when we reach the point \ (t \) at \ (t \) for the first time, all \ (t+2i \) can be reached, so we only care about the time of the first arrival point \ (t \).
So we built this picture, ran the shortest circuit, and answered the query online.
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. Guess number
First, what is your strategy? How many points did you get?
Then let's sensibly infer a better strategy. Let's set our current interval length as \ (n \) and the asked interval as \ ([l,r] \), then how will the interactive library answer you?
Since the final answer \ (q \) and the specified number \ (u \) are adaptive, the interactive library will try to make the interval you can determine next as long as possible. Then the interval we can determine next is the longer one of \ ([l,n] \) and \ ([1,r] \), so the interval we ask should be closer to the middle as possible.
Next, we need to determine the interval length \ (len \). According to the perceptual understanding of the cost function \ (\ frac{1}{len} \), if it is too long, it will not be optimal, because every time the length is reduced by 2, the next determined interval length will be reduced by 1, and if the length is large, the cost will almost remain the same. This is, you are confused. How much is the optimal length?
Let \ (f[i] \) represent the cost of determining the final number when the current interval length that can be determined is \ (I \). If it is transferred, we enumerate the length \ (len \) to calculate the middle interval \ ([l,r] \), and the transfer is as follows: \ (f[i]=min {max (f[r-1],f[i-l])+\frac{1}{len} \).
This is a \ (O(n^2) \) dp. If you want to optimize, let's make a table and have a look.
Let \ (g[i] \) represent the interval length selected in the first step. We are surprised to find that there is little difference between \ (g[i] \) and \ (g[i-1] \) in a section, and then increase suddenly.
With this idea, we type all the tables below 1e5 and find that only 25 numbers have suddenly increased more than 50, so we record these numbers. For other \ (g[i] \), just take \ (len\in [g[i − 1] - 5,g[i − 1] + 50] \) and complexity \ (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. Flip sequence
This is a problem of following the vine and feeling the melon. As long as you think patiently, you will be able to do it.
An obvious strategy is to take \ (x=1 \), that is, the positions of two adjacent numbers can be exchanged, and the sequence can be sorted like bubble sorting. The number of times is \ (O (reverse order to number) \).
Let's consider this process. For example, we first find 1, constantly exchange 1 to the first position, then find 2, and constantly exchange 2 to the second position This enlightens us whether there can be a method with fewer operations to exchange \ (i \) to the \ (i \) position without changing the position of the previous \ (i − 1 \).
This process is very simple. Assuming that the number we are operating now is \ (i \) and the position is \ (LOC \), we will continue to turn \ (LOC \) to \ (loc-x \), then to \ (i+x \), and finally back to \ (i \).
However, there is a problem with this operation, that is, the sequence of the last \ (\ frac{3}{2} x \) cannot be restored. What should we do? We need to find another operation so that this operation can exchange the positions of two adjacent numbers without changing other values, so we can use the bubble sorting above.
Unfortunately, I still don't know whether this operation is feasible, but I have found a way to exchange numbers with a distance of 2. Suppose we want to exchange \ (a_i \) and \ (a_{i+2} \), we can do the following four operations:
- \(rev(i+2-x,i+2)\)
- \(rev(i+4-x,i+2)\)
- \(rev(i+3-x,i+1)\)
- \(rev(i+2-x,i)\)
In this way, if we use another method to make the parity of the following numbers and subscripts the same, the problem is finished.
We define the semi coincidence of a position as whether the parity of this position is the same as that of the number in the current position, then the problem is equivalent to making the semi coincidence of all subsequent positions 1.
So what operations do we have related to this semi fit? Like changing the semi fit of a position?
Lucky, we can do the following to change the semi fit of two adjacent positions \ (i \) and \ (i+1 \):
- \(rev(i+1−x,i+1)\)
- \(rev(i+3−x,i+1)\)
Since the given is an arrangement, the number of positions that do not meet the semi fit must be even, so we first move the positions that meet the semi fit to the front, then change the latter semi fit to 1, and finally make a bubble sorting on the odd and even positions for the whole sequence. This problem is solved.
Let's analyze how much of this \ (x \) is appropriate:
- First move the numbers \ (1\to n − \ frac{3}{2} x \) to the front, and the number is about \ (\ frac{n^2}{2x} \).
- Secondly, move the position satisfying the half fit degree to the first half of the rear \ (\ frac{3}{2} x \) position for about \ (\ frac{9x^2}{4} \).
- Then, correct the following semi fit degrees, and the number is about \ (x \).
- Finally, the whole sequence is bubble sorted. Only the following \ (\ frac{3}{2} x \) positions are affected, so the number of times is about \ (\ frac{9x^2}{4} \).
Finally, calculate the mean inequality. When \ (x=\sqrt[3]{\frac{n^2}{18} \), it is the best, and the number is about 19000. However, since we calculated the worst case before, we can't reach this upper bound in the actual test, so we can pass this problem.
# 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. Cyclic section
This is a computational geometry problem.
Firstly, the vector \ (x \) must be subtracted from some two vectors, so we violently enumerate this \ (x \) to check, complexity \ (O(n^3) \).
Then we find a way to quickly find \ (x \), first find a convex hull for the point set, and then make a rotating cartridge. If \ (\ geq 4 \) points pass at a certain time, there must be parallel lines. We can find \ (z \) and \ (x \) by selecting the parallel line with fewer points.
Then we need to find all the starting points. Just look at whether there is a point at the current point minus the vector \ (x \). This can be maintained with a map, or after sorting all points, it can be divided into two parts, with complexity \ (O(n logn) \).
Here are some details:
- How to find \ (z \) and \ (x \) on a line? First, since there are no three starting points collinear, the number of starting points can only be 1 or 2. check them respectively.
- If all points are collinear, special judgment is required.
# 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;
}