1
13
2016
3

Diary of OI

Jan.13th

注:黑粗体为超链接
今天突发奇想想把CF的Contest从第一场一场场做过去
然后发现1C又是计算几何 简直hopeless
然而竟然刚了2个小时就刚出来了 真开心(其实看了题解)
反正这题就是先转一转 然后多边形的中心点求出来
然后算一算几边形就好啦
下面这坨就是坐标旋转公式(顺时针)
$X'=Xcos(\alpha)+Ysin(\alpha)$
$Y'=Ycos(\alpha)-Xsin(\alpha)$
为什么呢?→_→
 C++ Code By WTRC
1
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
1
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,25if (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
1
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==1return;
    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);
        
}

 

Category: Diary | Tags: codeforces | Read Count: 450
Avatar_small
qiancl 说:
Jan 13, 2016 11:23:59 AM

人群中的费老板怎么变蓝了呢

繁星 说:
Jan 13, 2016 12:56:00 PM

人群中的费老板怎么变蓝了呢

Avatar_small
WasteRice 说:
Jan 13, 2016 06:08:44 PM

@qiancl:
@繁星:
因为突然觉得绿的不好看


登录 *


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

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com