absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] Codeforces 66C 解题报告
[破碎的状态] ICPC-Camp Day 8 H Random Walk

[破碎的状态] CF Gym 100960D

absi2011 posted @ Apr 23, 2016 10:50:26 PM in 刷题记录 with tags 二分 小高考 高斯消元 CF Gym 交互题 瞎搞 , 541 阅读

题意:

特别特别特别鸣谢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,表示你炸了,你必须立刻退出程序。

这个题的算法是高斯消元+二分答案

 

前面先询问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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter