分类存档：默认分类

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1115
【算法分析】
先假设n为偶数，然后对于任意偶数i<=n，都满足a[i]=a[i-1]。
那么显然先手只能取奇数位置a[j]的石头。然后后手必然可以取同样数量的a[j+1]。那么最后必然是后手的取完石头。所以先手必败。

对于n为偶数时的一般情况，依然是连续的每两个分组。
我们可以将这个模型分成两部分，一部分是a[i-1]=a[i]的，另一部分是a[i]-a[i-1]。（i为偶数）
然后一部分用前面那个解决，后者，将两堆合成一个整体看，就变成一般的NIM游戏了！
于是利用SG函数那个xor定理就可以解决了。。
【CODE】
#include int Tc,n,i,ans,a[1005];
int main(){
scanf("%d",&Tc);
for (;Tc;Tc–){
scanf("%d",&n);
for (i=0;i if (n%2) ans=a[0]; else ans=0;
for (i=n-1;i>0;i-=2) ans^=(a[i]-a[i-1]);
if (ans) puts("TAK");
else puts("NIE");
}
}

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1013
【题目大意】
求高维球心坐标。
【算法分析】
首先距离公式容易推知，然后点到球心距离必然都相等，于是联立n条等式，高斯消元即可。
另外：
我爬山法好像陷进局部最优解里去了，我爬山用的是方差作估价函数，直接WA。
估计最后一名的800+MS的神牛就是爬山过的。求爬山正确的估价函数。
【其它】高斯消元1Y。
【CODE】
#include #include #include #include #define sqr(x) ((x)*(x))
const int N=15;
int n;
double a[N][N],c[N][N];

void Swap(int x,int y){
double tmp;
for (int i=0;i<=n;i++){
tmp=c[x][i];
c[x][i]=c[y][i];
c[y][i]=tmp;
}
}

void guass(){
int i,j,k;
for (i=1;i<=n;i++){
for (k=i,j=i;j<=n;j++)
if (fabs(c[j][i-1])>fabs(c[k][i-1])) k=j;
Swap(i,k);
for (j=i+1;j<=n;j++)
for (k=n;k>=i-1;k–)
c[j][k]-=c[i][k]*c[j][i-1]/c[i][i-1];
}
}

void solve(){
double ans[N];
memset(ans,0,sizeof(ans));
ans[n]=1;
for (int i=n;i>=1;i–){
double Sum=0;
for (int j=i;j<=n;j++)
Sum-=ans[j]*c[i][j];
ans[i-1]=Sum/c[i][i-1];
}
for (int i=0;i if (i) printf(" ");
printf("%.3lf",ans[i]);
}
printf("n");
}

int main(){
scanf("%d",&n);
for (int i=0;i<=n;i++)
for (int j=0;j scanf("%lf",&a[i][j]);
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++){
for (int j=0;j c[i][j]=2*(a[i][j]-a[i-1][j]);
c[i][n]+=sqr(a[i-1][j])-sqr(a[i][j]);
}
}
guass();
solve();
}