[破碎的状态] CF Gym 100960D
题意:
特别特别特别鸣谢Jimmy.Carlson.Wang的翻译
直接带他翻译贴上来了...
本题为交互题。
你现在有一个使用N维坐标系的飞船。
飞船用N个选择器去表示他的速度，对于每个选择器有1~M的M个档位。第i个数表示第i个选择器。当飞船到达第j个档位时，整个飞船的速度会加<K(i,j) · Xi>这个向量。这里Kij是一个整数，表示一个第i个选择器第j个档位的“传输系数”。因此，一个飞船的总速度S是sigma(1,n)<K(i,gi)·Xi>，gi表示选择的第i个选择器的档位。
为了让飞船正常运行，必须满足以下几个条件：
1、对于任意一个速度S，存在一个系数组ci可以使得S=sigma(1.n)<ci·Xi>（ci可以等于K(i,j)，也可以不等于）
2、K(i,j)恒小于K(i,t)，当且仅当j<t。
3、对于每一个选择器，一定有一个档位的传输系数是0。
现在这个飞船正在高速运行着，你需要计算出每一个选择器的一个合适的档位，使得总速度S=0.
你现在可以做的就是询问不超过120次。询问的方法是先打一个问号，然后空一格，接着输出N个1~M的数字，表示第i个选择器调整到第j个档位。
每次询问后你的程序需要读取N个整数，表示总速度S的每一个系数。
当你已经确定一个合适的档位时，可以输出一个A，然后空一格，接着输出N个1~M的数字，表示当S=0时每一个选择器的档位，然后立刻跳出程序。
如果你的程序读入到的第一个数字是987654321，表示你炸了，你必须立刻退出程序。
你现在有一个使用N维坐标系的飞船。
飞船用N个选择器去表示他的速度，对于每个选择器有1~M的M个档位。第i个数表示第i个选择器。当飞船到达第j个档位时，整个飞船的速度会加<K(i,j) · Xi>这个向量。这里Kij是一个整数，表示一个第i个选择器第j个档位的“传输系数”。因此，一个飞船的总速度S是sigma(1,n)<K(i,gi)·Xi>，gi表示选择的第i个选择器的档位。
为了让飞船正常运行，必须满足以下几个条件：
1、对于任意一个速度S，存在一个系数组ci可以使得S=sigma(1.n)<ci·Xi>（ci可以等于K(i,j)，也可以不等于）
2、K(i,j)恒小于K(i,t)，当且仅当j<t。
3、对于每一个选择器，一定有一个档位的传输系数是0。
现在这个飞船正在高速运行着，你需要计算出每一个选择器的一个合适的档位，使得总速度S=0.
你现在可以做的就是询问不超过120次。询问的方法是先打一个问号，然后空一格，接着输出N个1~M的数字，表示第i个选择器调整到第j个档位。
每次询问后你的程序需要读取N个整数，表示总速度S的每一个系数。
当你已经确定一个合适的档位时，可以输出一个A，然后空一格，接着输出N个1~M的数字，表示当S=0时每一个选择器的档位，然后立刻跳出程序。
如果你的程序读入到的第一个数字是987654321，表示你炸了，你必须立刻退出程序。
这个题的算法是高斯消元+二分答案
前面先询问101次,把每个单位元,也就是这里面的X数组给骗出来(当然如果X数组的gcd不为1我们可以带它除以gcd不影响就对了)
然后再询问后高斯消元,求出每个的K(i,now[i])
根据这个值是否为0,进行二分,求出这个值到底在哪
复杂度:前N+1次O(N),后18次二分答案每次O(n^3)
n<=100所以不会TLE
高斯消元用int是个极端错误的选择,以后再也不瞎搞了....
ifdef-endif是用来本地测试的......
代码:
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int gcd(int x,int y)
{
if (y==0) return x; else return gcd(y,x%y);
}
int n,m;
const double eps=1e-7;
struct vectors
{
double a[105];
inline double operator [] (const int &x)
{
return a[x];
}
void get_gcd()
{
int i;
int k=0;
for (i=0;i<n;i++)
{
k=gcd(k,(int)(fabs(a[i])+eps));
}
if (k==0) return; //Impossible?
k=abs(k);
for (i=0;i<n;i++)
{
a[i]/=k;
}
}
void operator -= (const vectors &b)
{
int i;
for (i=0;i<=n;i++)
{
a[i]-=b.a[i];
}
}
friend vectors operator * (vectors a,double b)
{
int i;
for (i=0;i<=n;i++)
{
a.a[i]*=b;
}
return a;
}
};
vectors base;
vectors v[105];
vectors tempv[105];
int now[105];
int l[105],r[105];
int sol[105];
void guess()
{
int i;
for (i=0;i<n;i++)
{
int j;
for (j=0;j<n;j++)
{
tempv[i].a[j]=v[j][i];
}
tempv[i].a[n]=now[i];
}
for (i=0;i<n;i++)
{
int j;
int tmp=i;
for (j=i;j<n;j++)
{
if (tempv[j][i]!=0)
{
if (fabs(tempv[j][i])>fabs(tempv[tmp][i]))
{
tmp=j;
}
}
}
swap(tempv[tmp],tempv[i]);
for (j=i+1;j<n;j++)
{
tempv[j]-=tempv[i]*(tempv[j][i]/tempv[i][i]);
}
}
for (i=n-1;i>=0;i--)
{
double t=(tempv[i][n]/tempv[i][i]);
if (t>0) t+=eps; else t-=eps;
sol[i]=(int)t;
int j;
for (j=0;j<i;j++)
{
tempv[j].a[n]-=tempv[j][i]*tempv[i][n]/tempv[i][i];
}
}
}
#ifdef absi2011
int val[105];
int read(int x)
{
return val[x];
}
int k[15][15];
int a[15][15];
int sum[15];
void init()
{
int i,j;
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
cin>>a[i][j];
}
}
for (i=0;i<n;i++)
{
for (j=0;j<m;j++)
{
cin>>k[i][j];
}
}
}
void test()
{
int i;
for (i=0;i<n;i++)
{
sum[i]=0;
}
int j;
for (j=0;j<n;j++)
{
int x;
x=(l[j]+r[j])/2;
x--;
for (i=0;i<n;i++)
{
sum[i]+=a[j][i]*k[j][x];
}
}
for (j=0;j<n;j++)
{
val[j]=sum[j];
}
}
#endif
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
#endif
scanf("%d%d",&n,&m);
if (m==1)
{
int i;
printf("A ");
for (i=0;i<n-1;i++)
{
printf("1 ");
}
printf("1\n");
fflush(stdout);
return 0;
}
#ifdef absi2011
init();
#endif
printf("?");
int i;
for (i=0;i<n;i++)
{
#ifdef absi2011
l[i]=1;
r[i]=1;
#else
printf(" 1");
#endif
}
#ifdef absi2011
test();
#endif
printf("\n");
fflush(stdout);
for (i=0;i<n;i++)
{
#ifdef absi2011
base.a[i]=read(i);
#else
scanf("%d",&now[i]);
base.a[i]=now[i];
#endif
}
for (i=0;i<n;i++)
{
int j;
printf("?");
for (j=0;j<n;j++)
{
#ifdef absi2011
l[j]=1;
r[j]=1;
if (i==j) r[j]=3;
#else
if (i==j) printf(" 2"); else printf(" 1");
#endif
}
printf("\n");
#ifdef absi2011
test();
#endif
fflush(stdout);
for (j=0;j<n;j++)
{
#ifdef absi2011
v[i].a[j]=read(j);
#else
scanf("%d",&now[i]);
v[i].a[j]=now[i];
#endif
}
v[i]-=base;
v[i].get_gcd();
}
for (i=0;i<n;i++)
{
l[i]=1;
r[i]=m;
}
for (i=0;i<18;i++)
{
int j;
printf("?");
for (j=0;j<n;j++)
{
printf(" %d",(l[j]+r[j])/2);
}
printf("\n");
fflush(stdout);
#ifdef absi2011
test();
#endif
for (j=0;j<n;j++)
{
#ifdef absi2011
now[j]=read(j);
#else
scanf("%d",&now[j]);
#endif
}
//now-=base;
guess();
for (j=0;j<n;j++)
{
if (sol[j]<0)
{
l[j]=(l[j]+r[j])/2+1;
}
else if (sol[j]==0)
{
l[j]=(l[j]+r[j])/2;
r[j]=l[j];
}
else
{
r[j]=(l[j]+r[j])/2-1;
}
}
}
printf("A");
for (i=0;i<n;i++)
{
printf(" %d",l[i]);
}
printf("\n");
return 0;
}
评论 (0)