Contest : ACdream区域赛指导赛之专题赛系列(1)の数学专场
题意：n(<=10^18)的数转化成2进制。翻转后(去掉前导零)输出十进制
思路：water
/*
* this code is made by shiyuan
* Problem: 1095
* Verdict: Accepted
* Submission Date: 2014-05-24 19:06:37
* Time: 0 MS
* Memory: 1676 KB
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
int main(){
int t; scanf("%d",&t);
while(t--){
LL n; scanf("%lld",&n);
string s="";
while(n){
if(n&1) s+="1";
else s+="0";
n/=2;
}
LL ans=0,tmp=1;
int i=s.size()-1;
while(s[i]!='1' && i>=0) i--;
for(;i>=0;i--){
if(s[i]=='1'){
ans+=tmp;
}
tmp*=2;
}
printf("%lld\n",ans);
}
return 0;
}
题意：n(<=1000)仅仅地鼠出现的坐标、被击中的概率以及时间已知，还有锤子的移动速度，求期望的最大值
思路：依据时间排序，用dp[i]表示前i仅仅地鼠被击中的期望，dp[i]=max(dp[i],dp[j]+p[i]) 当且仅当第i仅仅地鼠和第j仅仅地鼠可达(锤子移动的时间够)
/*
* this code is made by shiyuan
* Problem: 1092
* Verdict: Accepted
* Submission Date: 2014-05-24 23:54:42
* Time: 372 MS
* Memory: 1724 KB
*/
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
struct node{
int x,y,t;
double p;
}P[1010];
double dp[1010];
void init(){
for(int i=0;i<1010;i++) dp[i]=0;
}
bool cmp(node a,node b){
return a.t<b.t;
}
double sq(double x){
return x*x;
}
double dis(node a,node b){
return sqrt(sq(a.x-b.x+0.0)+sq(a.y-b.y+0.0));
}
int main(){
int t; scanf("%d",&t);
while(t--){
int n; LL v; scanf("%d%lld",&n,&v);
init();
for(int i=0;i<n;i++){
scanf("%d%d%d%lf",&P[i].x,&P[i].y,&P[i].t,&P[i].p);
}
sort(P,P+n,cmp);
for(int i=0;i<n;i++){
dp[i]=P[i].p;
for(int j=0;j<i;j++){
if(v*(P[i].t-P[j].t)-dis(P[i],P[j])>=0){
dp[i]=max(dp[i],dp[j]+P[i].p);
}
}
}
double ans=0;
for(int i=0;i<n;i++) ans=max(ans,dp[i]);
printf("%.6lf\n",ans);
}
return 0;
}
tag: polya计数
tag: 莫比乌斯反演
英文题，看了头大。不想做
E.女神的正多面体
题意：分别给出正四面体、正六面体和正十二面体中4、8、6个点。相邻的点可达，告诉起点和终点，问k步内能到达终点的方案数
思路：三种不同的方法构造不同矩阵，多加一行纪录k步以内的全部方案
个人见解：曾经做过一个类似的题，思路几乎相同，可是当时那个题我的理解是已经到达终点了就不该继续往前了。好比1-3-2-3（起点1，终点3）个人觉得应该是属于不合法的方案，所以假设依照这样理解的话，我们在考虑构造矩阵的话，由终点引出的下若干个点的值应该置为0 （当然这题的正讲解的不是这样）
/*
* this code is made by shiyuan
* Problem: 1093
* Verdict: Accepted
* Submission Date: 2014-05-24 19:57:19
* Time: 28 MS
* Memory: 1676 KB
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const LL mod=1000000007;
struct Matrix{
LL m[10][10];
}E,D;
int n,st,ed;
LL K;
Matrix Multi(Matrix A,Matrix B){
Matrix ans;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ans.m[i][j]=0;
for(int k=1;k<=n;k++){
ans.m[i][j]=(ans.m[i][j]+A.m[i][k]*B.m[k][j])%mod;
}
}
}
return ans;
}
void init(){
memset(D.m,0,sizeof(D.m));
memset(E.m,0,sizeof(E.m));
for(int i=1;i<=9;i++)
E.m[i][i]=1;
}
Matrix Pow(Matrix A,LL k){
Matrix ans=E;
while(k){
if(k&1) k--,ans=Multi(ans,A);
else k/=2,A=Multi(A,A);
}
return ans;
}
int main(){
int T; scanf("%d",&T);
while(T--){
scanf("%d%lld%d%d",&n,&K,&st,&ed);
init();
Matrix ans;
memset(ans.m,0,sizeof(ans.m));
if(n==4){
memset(D.m,0,sizeof(D.m));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) D.m[i][j]=0;
else D.m[i][j]=1;
}
}
}
else if(n==6){
n=8;
memset(D.m,0,sizeof(D.m));
D.m[1][2]=D.m[1][4]=D.m[1][5]=1;
D.m[2][1]=D.m[2][3]=D.m[2][6]=1;
D.m[3][2]=D.m[3][4]=D.m[3][7]=1;
D.m[4][1]=D.m[4][3]=D.m[4][8]=1;
D.m[5][1]=D.m[5][6]=D.m[5][8]=1;
D.m[6][2]=D.m[6][5]=D.m[6][7]=1;
D.m[7][3]=D.m[7][6]=D.m[7][8]=1;
D.m[8][4]=D.m[8][5]=D.m[8][7]=1;
}
else{
n=6;
memset(D.m,0,sizeof(D.m));
D.m[1][2]=D.m[1][3]=D.m[1][4]=D.m[1][5]=1;
D.m[2][1]=D.m[2][3]=D.m[2][5]=D.m[2][6]=1;
D.m[3][1]=D.m[3][2]=D.m[3][4]=D.m[3][6]=1;
D.m[4][1]=D.m[4][3]=D.m[4][5]=D.m[4][6]=1;
D.m[5][1]=D.m[5][2]=D.m[5][4]=D.m[5][6]=1;
D.m[6][2]=D.m[6][3]=D.m[6][4]=D.m[6][5]=1;
}
ans.m[st][1]=1;
n++;
for(int i=1;i<n;i++)
D.m[n][i]=D.m[ed][i];
D.m[n][n]=1;
ans=Multi(Pow(D,K),ans);
printf("%lld\n",ans.m[n][1]);
}
return 0;
}
题意：已知一个正n边形上的三个点，求n的最小值以及正n边行中心坐标
思路：依据三个点求三角形的外心。然后遍历n，求得一个n使得三个角都是180/n的倍数
卡精度，输出坐标的时候处理好-0.0001这样的数据
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
#define pi acos(-1.0)
#define eps 1e-6
struct point{
double x,y;
point(double xx=0,double yy=0){
x=xx,y=yy;
}
point operator-(point b)
{
return point(x-b.x,y-b.y);
}
double operator*(point b)
{
return x*b.x+y*b.y;
}
};
struct line{point a,b;};
double sq(double x){
return x*x;
}
double dist(point p1,point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
point intersection(line u,line v){
point ret=u.a;
double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))
/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
ret.x+=(u.b.x-u.a.x)*t;
ret.y+=(u.b.y-u.a.y)*t;
return ret;
}
point circumcenter(point a,point b,point c){
line u,v;
u.a.x=(a.x+b.x)/2;
u.a.y=(a.y+b.y)/2;
u.b.x=u.a.x-a.y+b.y;
u.b.y=u.a.y+a.x-b.x;
v.a.x=(a.x+c.x)/2;
v.a.y=(a.y+c.y)/2;
v.b.x=v.a.x-a.y+c.y;
v.b.y=v.a.y+a.x-c.x;
return intersection(u,v);
}
double angle(point a,point b,point c){
point d,e;
d=b-a,e=c-a;
return acos(d*e/(sqrt(sq(d.x)+sq(d.y))*sqrt(sq(e.x)+sq(e.y))));
}
bool is_ok(double n,int i){
double cnt=i*n/pi;
return fabs(cnt-round(cnt))<eps;
}
int main(){
int T; scanf("%d",&T);
while(T--){
point p[3];
for(int i=0;i<3;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
point o=circumcenter(p[0],p[1],p[2]);
double x=angle(p[0],p[1],p[2]);
double y=angle(p[1],p[2],p[0]);
double z=angle(p[2],p[0],p[1]);
int i=3;
for(;i<=100000;i++){
if(is_ok(x,i) && is_ok(y,i) && is_ok(z,i)) break;
}
printf("%.4lf %.4lf %d\n",o.x+eps,o.y+eps,i);
}
return 0;
}