Jan.13th
注：黑粗体为超链接
今天突发奇想想把CF的Contest从第一场一场场做过去
然后发现1C又是计算几何 简直hopeless
然而竟然刚了2个小时就刚出来了 真开心（其实看了题解）
反正这题就是先转一转 然后多边形的中心点求出来
然后算一算几边形就好啦
下面这坨就是坐标旋转公式（顺时针）
$X'=Xcos(\alpha)+Ysin(\alpha)$
$Y'=Ycos(\alpha)-Xsin(\alpha)$
为什么呢？→_→
C++ Code By WTRC
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long #define eps 1e-6 #define abs(a) ((a)>0?(a):(-(a))) using namespace std; const double pi=acos(-1); struct Point{ double x,y; }a,b,c,cet; void Rotate(Point&a,double ang){ double x=a.x,y=a.y; a.x=x*cos(ang)+y*sin(ang); a.y=y*cos(ang)-x*sin(ang); } double sqr(double a){return a*a;} void CalcCenter(){ double k1=-1.0*(a.x-b.x)/(a.y-b.y); double b1=(a.y+b.y)/2-(a.x+b.x)/2*k1; double k2=-1.0*(a.x-c.x)/(a.y-c.y); double b2=(a.y+c.y)/2-(a.x+c.x)/2*k2; cet.x=(b1-b2)/(k2-k1); cet.y=k1*cet.x+b1; } int main(){ scanf("%lf%lf",&a.x,&a.y); scanf("%lf%lf",&b.x,&b.y); scanf("%lf%lf",&c.x,&c.y); while (abs(a.y-b.y)<eps||abs(a.y-c.y)<eps||abs(b.y-c.y)<eps){ double al=rand()*1.0; Rotate(a,al);Rotate(b,al);Rotate(c,al); } CalcCenter(); double aga=atan2(a.y-cet.y,a.x-cet.x); double agb=atan2(b.y-cet.y,b.x-cet.x); double agc=atan2(c.y-cet.y,c.x-cet.x); int n=2; while (n<100){ n++; double Ang=2*pi/n; if (fabs(floor((agb-agc)/Ang+0.5)*Ang+agc-agb)>=eps) continue; if (fabs(floor((aga-agb)/Ang+0.5)*Ang+agb-aga)>=eps) continue; if (fabs(floor((aga-agc)/Ang+0.5)*Ang+agc-aga)>=eps) continue; break; } double R=sqrt(sqr(cet.x-a.x)+sqr(cet.y-a.y)); double s=sin(pi/n)*cos(pi/n)*sqr(R)*n; printf("%.10lf\n",s); } |
下午干了什么呢？去上了英语课和语文课，然后剩下的时间都在看傅里叶变换，然而只是大概知道是什么东西，到欧拉公式那块之后就看不懂了……决定先学微积分，FFT以后再说。我这算不算颓了一下午
- Dirak:一下午都没学会傅里叶变换你是搞笑的吗
只能说是一道和字符串有关的模拟题
本来想用哈希或者MAP的
想了想不用Trie怎么增加实力呢
然后代码长度就爆炸了
C++ Code By WTRC
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } struct Trie{ Trie *next[26]; vector<int>val,time; int Size; Trie(){ Rep(i,0,25) next[i]=NULL; val.clear();time.clear(); Size=0; } }*Root; int Max=-1<<30,AST=1<<30,n; string Ans; char s[40]; void Build(Trie *now,int S,int T){ int len=strlen(s); Rep(i,0,len-1){ int to=s[i]-'a'; if (now->next[to]==NULL) now->next[to]=new Trie; now=now->next[to]; } if (now->Size) now->val.push_back(now->val[now->Size-1]+S); else now->val.push_back(S); now->time.push_back(T); now->Size++; } void FindMax(Trie *now){ if (now->Size){ int FNV=now->val[now->Size-1]; if (FNV>Max) Max=FNV; } Rep(i,0,25) if (now->next[i]!=NULL) FindMax(now->next[i]); } void FindAns(Trie *now,string ans){ if (now->Size&&now->val[now->Size-1]==Max) Rep(i,0,now->Size-1) if (now->val[i]>=Max&&now->time[i]<AST){ AST=now->time[i]; Ans=ans; break; } char ss[2]; Rep(i,0,25){ ss[0]='a'+i;ss[1]=0; if (now->next[i]!=NULL) FindAns(now->next[i],ans+ss); } } int main(){ Root=new Trie; n=IN(); Rep(i,1,n){ scanf("%s",s); int sc=IN(); Build(Root,sc,i); } FindMax(Root); FindAns(Root,""); puts(Ans.c_str()); } |
一眼DP 然而想了想并不知道怎么DP
后来发现2和5可以分开做，输出更小的那个就行了
为什么呢？因为你另外一个肯定不会比这个小对吧，那答案就是这个
然后就是0的情况要特判一下
C++ Code By WTRC
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } bool hvz=0; int poxz,n; int a[1005][1005][2]; int dp[1005][1005][2]; void DP(int ct){ dp[1][1][ct]=a[1][1][ct]; Rep(i,2,n){ dp[1][i][ct]=dp[1][i-1][ct]+a[1][i][ct]; dp[i][1][ct]=dp[i-1][1][ct]+a[i][1][ct]; } Rep(i,2,n) Rep(j,2,n) dp[i][j][ct]=min(dp[i-1][j][ct],dp[i][j-1][ct])+a[i][j][ct]; } void Print(int x,int y,int ct){ if (x==n&&y==n) printf("%d\n",dp[x][y][ct]); if (x==1&&y==1) return; if (x==1){ Print(x,y-1,ct); putchar('R'); } else if (y==1){ Print(x-1,y,ct); putchar('D'); } else{ if (dp[x][y-1][ct]+a[x][y][ct]==dp[x][y][ct]){ Print(x,y-1,ct); putchar('R'); } else{ Print(x-1,y,ct); putchar('D'); } } } int main(){ n=IN(); Rep(i,1,n) Rep(j,1,n){ int x=IN(); if (x==0){hvz=1;x=10;poxz=i;} while (x%2==0) a[i][j][0]++,x/=2; while (x%5==0) a[i][j][1]++,x/=5; } DP(0);DP(1); if (hvz){ if (dp[n][n][0]==0) Print(n,n,0); else if (dp[n][n][1]==0) Print(n,n,1); else{ puts("1"); Rep(i,2,poxz) putchar('D'); Rep(i,2,n) putchar('R'); Rep(i,poxz+1,n) putchar('D'); } } else if (dp[n][n][0]<dp[n][n][1]) Print(n,n,0); else Print(n,n,1); } |
Jan 13, 2016 11:23:59 AM
人群中的费老板怎么变蓝了呢
Jan 13, 2016 12:56:00 PM
人群中的费老板怎么变蓝了呢
Jan 13, 2016 06:08:44 PM
@qiancl:
@繁星:
因为突然觉得绿的不好看