acm7-7总结

acm

7-7acm总结：

7-1月一号开始我勉强开始我的补题生活。

概率与期望(kuangbin)

这是我之前未刷完的一个专题。

B.是一个掷骰子的题。离散型概率分布。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define p printf
using namespace std;

int main(){
    int k,n;
    scanf("%d",&k);
    for(int i = 1; i <= k; i++){
        scanf("%d",&n);
        int gold[120];
        double gai[120]={0};
        gai[0]=1;
        for(int j = 0; j < n; j++){
            scanf("%d",&gold[j]);
        }
        //double ans = gold[0];
        for(int p = 0; p < n-1; p++){
            for(int q=p+1; q<=p+6 && q < n; q++){
                gai[q]+=gai[p]*1.0/min(6,n-p-1);
            }
        }
        double ans=0;
        for(int j = 0; j < n; j++){
            ans += gai[j]*gold[j];
        }
        p("Case %d: %.12lf\n",i,ans);
    }
    return 0;
}

C. 一个数除以他的因数直至1所需的步数。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

double a[111111]={0};

void init(){
    for(int i = 2; i < 100010; i++){
        double num = 0;
        double ans = 0;
        int ad = (int)sqrt (i);
        for(int j = 1; j <= (int)sqrt(i);j++){
            if(i%j!=0)continue;
            num++;
            ans+=a[j];
            if(j==i/j)continue;
            num++;
            ans+=a[i/j];
        }
        ans += num;
        a[i]=ans/(1.0*num-1);
    }
}

int main(){
    init();
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        int input;scanf("%d",&input);
        printf("Case %d: %.8lf\n",i+1,a[input]);
    }return 0;
}

D.概率dp，求不大于某个概率的最大的盗窃的钱

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
#include<cstdio>
#include<iostream>
using namespace std;
double f[10010],p[110];
int m[110];
int n,sum;
double lim;

int main(){
    int k,t=0;
    scanf("%d",&k);
    while(t++<k){
        scanf("%lf%d",&lim,&n);
        lim = 1 - lim;
        sum = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d%lf",&m[i],&p[i]);
            p[i] = 1 - p[i];
            sum+=m[i];
        }
        for(int i = 1; i <= sum; ++i)
            f[i] = 0;
        f[0]=1;
        int top = 0;
        for(int i = 1; i <= n; i++){
            for(int j = top; j >= 0; j--){
                f[j + m[i]] = max(f[j + m[i]], f[j] * p[i]);
                if(f[j+m[i]] > lim)
                    top = max(top, j + m[i]);
            }
        }
        printf("Case %d: %d\n", t, top);
    }
}

E.考虑反面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<iostream>
using namespace std;

int main(){
    double days;
    int k,t=0;
    scanf("%d",&k);
    while(t++<k){
        scanf("%lf",&days);
        double ans = (days-1)/days;
        int i = 2;
        while(ans>0.5){
            ans *= (days-i++)/days;
        }
        printf("Case %d: %d\n",t, --i);
    }
}

F.是一个蛇的，还没做出来。

G.看一下答案，找一下规律$ \sum_{i=1}^{n} \frac{n}{i} $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<iostream>

using namespace std;

int main(){
    int k,t=0;
    scanf("%d",&k);
    while(t++<k){
        int a;
        scanf("%d",&a);
        double sum=0;
        for(int i = 1; i <= a; i++){
            sum += a*1.0/i;
        }
        printf("Case %d: %.12lf\n",t,sum);
    }
    return 0;
}

H 老虎与鹿，鹿肯定被吃掉了，老师必须是奇数而且要在你之前自相残杀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int main(){
    int k,t=0;
    scanf("%d",&k);
    while(k>t++){
        int a,b;
        double ans = 0;
        scanf("%d %d",&a,&b);
        if(a%2==0){
            ans = 1.0/(a+1);
        }
        printf("Case %d: %.12lf\n",t,ans);
    }
    return 0;
}

I 要用滚动数组算状态量的概率(有点像数位dp？)。

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
#include<cstdio>
#include<iostream>

double dp[2][5010][2];

using namespace std;
int m1,m2;
int main(){
    int t=0,k;
    scanf("%d",&k);
    while(t++<k){
        int n,s;
        scanf("%d%d",&n,&s);
        m1 = s - 2*n;
        m2 = n - m1;
        //第n个位置无论是谁都是0
        dp[n%2][m1][0]=dp[n%2][m1][1]=0;
        for(int i = n-1; i>=0; i--){
            for(int j = min(m1,i); j >= 0 && i-j<=m2; j--){
                //yes;
                double p1 = (m1-j)*1.0/(n-i);
                //no
                double p2 = 1-p1;
                if(j+1<=m1){
                    //末尾是yes
                    dp[i%2][j][0] = dp[(i+1)%2][j+1][0]*p1 + (dp[(i+1)%2][j][1]+1)*p2;
                    dp[i%2][j][1] = (dp[(i+1)%2][j+1][0]+1)*p1 + (dp[(i+1)%2][j][1])*p2;
                }else{
                    //没有yes了
                    dp[i%2][j][0] = (dp[(i+1)%2][j][1]+1)*p2;
                    dp[i%2][j][1] = (dp[(i+1)%2][j][1])*p2;
                }
            }
        }
        //m1==j时p2==1;
        printf("Case %d: %.12lf\n",t,dp[0][0][0]);
    }
    return 0;
}

J。让矩形中的点全部反色，问要需要几次才能全部打开。

考虑每一维的可能性，二项分布，考虑反面。

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
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
//不同侧概率
double P(int pos, int len){
    return 1.0-((1.0*(pos-1)*(pos-1) + 1.0*(len-pos)*(len-pos)) / (len*len));
}



int main(){
    int t=0,k;
    scanf("%d",&k);
    while(t++<k){
        int x,y,z,k;
        scanf("%d%d%d%d",&x,&y,&z,&k);
        double ans = 0;
        //考虑每一维 该点被覆盖的概率
        for(int i = 1; i <= x; i++){
            for(int j = 1; j <= y; j++){
                for(int q = 1; q <= z; q++){
                    double p = P(i,x)*P(j,y)*P(q,z);
                    //f(n)=f(n-1)*(1-p)+g(n-1)*p,然后g(n)=1-f(n)得到：f(n)=f(n-1)*(1-2p)+p，最后得到f(n)=(1-(1-2p)^n)/2。
                    ans += 0.5 - 0.5*pow(1-2*p, k);
                }
            }
        }
        printf("Case %d: %.12lf\n",t,ans);
    }
    return 0;
}

K题，逃犯跑一道题。可以发现E(x) = ($\frac{5 + \sum_{i∈能去的点}E(i)}{cnt+1}$)

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<iostream>
#include<cstring>
#define maxn 16
#define eps 1e-9
#define CLR(mp,value) memset(mp,value,sizeof mp)
using namespace std;

double mp[maxn][maxn];
double dp[maxn][1<<maxn];
bool vis[maxn][1<<maxn];
int n,m;
//dp[u][st] = sigma(dp[i][st|(1<<i)]) && (!st&(1<<i))
int dfs(int st, int u){
    //走完了
    if(st == (1<<n)-1){
        dp[u][st]=0;
        return 1;
    }
    if(vis[u][st])return dp[u][st]>eps;
    int cnt = 0;
    dp[u][st]=5;
    vis[u][st]=1;
    for(int i = 0; i < n; i++){
        //可以走的话
        if(mp[u][i] && (!(st&(1<<i))) && dfs((st|1<<i),i)){
            int st0 = st|(1<<i);
            cnt++;
            dp[u][st]+=dp[i][st|(1<<i)]+mp[u][i];
        }
    }
    if(cnt){
        dp[u][st]/=cnt;
        return 1;
    }
    dp[u][st] = 0;
    return 0;
}

int main(){
    int t=0,k;
    scanf("%d",&k);
    while(t++<k){
        CLR(mp,0);
        CLR(dp,0);
        CLR(vis,0);
        scanf("%d%d",&n,&m);
        int u,v,w;
        for(int i = 0; i < m; i++){
            scanf("%d%d%d",&u,&v,&w);
            mp[u][v]=mp[v][u]=w;
        }
        dfs(1,0);
        printf("Case %d: %.12lf\n",t,dp[0][1]);
    }

    return 0;
}

L 二项分布E(x)=np 在乘一个人数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
#include<iostream>

using namespace std;
int main(){
    int t=0,k;
    scanf("%d",&k);
    while(t++<k){
        int n,m,turn;
        double p;
        scanf("%d%d%d%lf",&n,&m,&turn,&p);
        printf("Case %d: %.12lf\n",t,n*turn*p);
    }

    return 0;
}

M 感觉像是一道图论题目

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<utility>
#include<queue>
#define CLR(a,v) memset(a, v, sizeof a)

using namespace std;
int n,m,s,K;

double mp[110][110];
void floyd(){
    for(int i = 0; i < n; i++){
        mp[i][i] = 1.0;
    }
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                mp[i][j] = max(mp[i][j], mp[i][k]*mp[k][j]);
            }
        }
    }
}

int main(){
    int t=0,k;
    scanf("%d",&k);
    while(t++<k){
        scanf("%d%d%d%d",&n,&m,&s,&K);
        CLR(mp,0);
        int u,v;
        double w;
        while(m--){
            scanf("%d%d%lf",&u,&v,&w);
            mp[u][v] = mp[v][u] = w/100.0;
        }
        floyd();
        double ans = 1.0/mp[0][n-1]*2*K*s;
        printf("Case %d: %.7lf\n",t,ans);
    }
    return 0;
}

N，算每根棍子的期望，1的话就直接出来了，2的话就几何分布,且每根棍子只有第一次是对结果有贡献的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<iostream>
using namespace std;
double biao[5050];//几何分布的期望1/p
int main(){
    int t=0,k;
    for(int i = 1; i < 5010; i++)
        biao[i]=biao[i-1]+1.0/i;
    scanf("%d",&k);
    while(t++<k){
        int n;scanf("%d",&n);
        double ans = 0;
        int x,y;
        for(int i = 0; i < n; i++){
            scanf("%d%d",&x,&y);
            if(y==1)
                ans+=x;
            else
                ans+=x*biao[n];
        }
        printf("Case %d: %.12lf\n",t,ans);
    }
    return 0;
}

op没做。。。直接看的Q：q 的话要解期望的方程。

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
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

int main(){
    int t=0,k;
    scanf("%d",&k);
    while(t++<k){
        double k1,k2;
        double p;
        scanf("%lf%lf%lf",&p,&k1,&k2);
        if(p<1e-9){
            printf("Case %d: %lf\n",t,k1);
            continue;
        }else if(p>1-(1e-9)){
            printf("Case %d: %lf\n",t,k2);
            continue;
        }
        double q = 1-p;
        double needp = 1 - pow(p,k2-1);
        double needq = 1 - pow(q,k1-1);
        double e1 = (needq/p+1/q)/(1/needp-needq);
        double e2 = needq*e1+needq/p;
        double ans = p*e1+q*e2+1;
        printf("Case %d: %.12lf\n",t,ans);
    }
    return 0;
}

矩阵

感觉矩阵的核心也是在找地推关系式，然后就借助矩阵快速幂求出。

a. 存在循环节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<iostream>
const int mod = 1e9+7;
using namespace std;

int main(){
    int x,y,n;scanf("%d%d%d",&x,&y,&n);
    n%=6;
    if(n==0)n=6;
    int ans;
    int z = y-x;
    if(n%3==1) ans = x;
    else if(n%3==2) ans = y;
    else ans = z;
    if(n>3)ans = -1*ans;
    while(ans<0)ans+= mod;
    printf("%d",ans%mod);
    return 0;
}

b.cpp纯粹构造矩阵。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#define mod 10000007
#define ll long long
using namespace std;

int n,m;

struct Matrix{
    ll m[15][15];
    Matrix(){
        memset(m,0,sizeof m);
    }
};
Matrix mul(Matrix a, Matrix b){
    Matrix c;
    for(int i = 1; i <= n+2; i++){
        for(int k = 1; k <= n+2; k++)
        if(a.m[i][k]){
            for(int j = 1; j <= n+2; j++)
            if(b.m[k][j]){
                c.m[i][j] = (c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
            }
        }
    }
    return c;
}

Matrix powmul(Matrix a, int k){
    Matrix b;
    for(int i = 1; i <= n+2; i++){
        b.m[i][i] = 1;
    }
    while(k){
        if(k&1)b = mul(b,a);
        a = mul(a,a);
        k>>=1;
    }
    return b;
}


int main(){
    while(~scanf("%d%d",&n,&m)){
        Matrix a,b;
        a.m[1][1] = 23;
        for(int i = 2; i <= n+1; i++){
            scanf("%lld",&a.m[i][1]);
            a.m[i][1]%=mod;
        }
        a.m[n+2][1] = 3;
        for(int i = 1; i <= n+1; i++){
            b.m[i][1] = 10;
        }
        for(int i = 1; i <= n+2; i++){
            b.m[i][n+2] = 1;
        }
        for(int i = 2; i <= n+1; i++){
            for(int j = 2; j <= i; j++){
                b.m[i][j] = 1;
            }
        }
        b = powmul(b, m);
        a = mul(b,a);
        printf("%lld\n",a.m[n+1][1]);
    }
    return 0;
}

c. 构造矩阵

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
#include <cstdio>
#include<iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<vector>
#define ll long long
ll na,m;
int n = 1;
struct Matrix{
    ll m[15][15];
    Matrix(){
        memset(m,0,sizeof m);
    }
};
Matrix mul(Matrix a, Matrix b){
    Matrix c;
    for(int i = 1; i <= n+2; i++){
        for(int k = 1; k <= n+2; k++)
        if(a.m[i][k]){
            for(int j = 1; j <= n+2; j++)
            if(b.m[k][j]){
                c.m[i][j] = (c.m[i][j]+a.m[i][k]*b.m[k][j])%m;
            }
        }
    }
    return c;
}

Matrix powmul(Matrix a, int k){
    Matrix b;
    for(int i = 1; i <= n+2; i++){
        b.m[i][i] = 1;
    }
    while(k){
        if(k&1)b = mul(b,a);
        a = mul(a,a);
        k>>=1;
    }
    return b;
}


int main(){
    while(~scanf("%d%d",&na,&m)){
        Matrix a,b,c;
        a.m[1][1]=a.m[2][2]=4;
        a.m[1][3]=a.m[3][3]=1;
        a.m[2][3]=2;
        b.m[1][1]=b.m[3][1]=1;
        b.m[2][1]=0;
        a = powmul(a,na/2);
        a = mul(a,b);
        if(na==1){a.m[1][1]=1;}
        printf("%lld\n",a.m[na%2==1?1:2][1]%m);
    }
}

e题关键在于如果直接计算会超内存。可以先计算中间的，首尾最后计算。中间的都是6x6不会超内存。

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll int
//C^(n*n)=（A*B)^(n*n)=A*(B*A)^(n*n-1)*B
using namespace std;
int mod = 6;
struct Matrix{
    int m[10][10];
    Matrix(){
        memset(m,0,sizeof m);
    }
};

int n,k;

Matrix mul(Matrix a, Matrix b){
    Matrix c;
    for(int i = 1; i <= k; i++){
        for(int k1 = 1; k1 <= k; k1++)
        if(a.m[i][k1]){
            for(int j = 1; j <= k; j++)
            if(b.m[k1][j]){
                c.m[i][j] = (c.m[i][j]+a.m[i][k1]*b.m[k1][j])%mod;
            }
        }
    }
    return c;
}

Matrix powmul(Matrix a, int m){
    Matrix b;
    for(int i = 1; i <= k; i++){
        b.m[i][i] = 1;
    }
    while(m){
        if(m&1)b = mul(b,a);
        a = mul(a,a);
    //cout << " 1 " <<endl;
        m>>=1;
    }
    return b;
}
int A[1005][11],B[11][1005],ans[1005][1005],tmp[11][1005];
int main(){
    while(~scanf("%d%d",&n,&k)){
        if(n*k==0)break;
        memset(A,0,sizeof A);
        memset(B,0,sizeof B);
        memset(ans,0,sizeof ans);
        memset(tmp,0,sizeof tmp);
        int temp;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++){
                scanf("%d",&temp);
                A[i][j] = temp;
            }
        }
        for(int i = 1; i <= k; i++){
            for(int j = 1; j <= n; j++){
                scanf("%d",&temp);
                B[i][j] = temp;
            }
        }
        Matrix c;
        for(int i = 1; i <= k; i++){
            for(int k1 = 1; k1 <= n; k1++)
            if(B[i][k1]){
                for(int j = 1; j <= k; j++)
                if(A[k1][j]){
                    c.m[i][j] = (c.m[i][j]+B[i][k1]*A[k1][j])%mod;
                }
            }
        }

        c = powmul(c,n*n-1);

        for(int i = 1; i <= k; i++){
            for(int k1 = 1; k1 <= k; k1++)
            if(c.m[i][k1]){
                for(int j = 1; j <= n; j++)
                if(B[k1][j]){
                    tmp[i][j] = (tmp[i][j]+c.m[i][k1]*B[k1][j])%mod;
                }
            }
        }

        for(int i = 1; i <= n; i++){
            for(int k1 = 1; k1 <= k; k1++)
            if(A[i][k1]){
                for(int j = 1; j <= n; j++)
                if(tmp[k1][j]){
                    ans[i][j] = (ans[i][j]+A[i][k1]*tmp[k1][j])%mod;
                }
            }
        }

        temp = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                temp+=ans[i][j];
                //printf("%2d ",ans[i][j]);
            }
            //printf("\n");
        }
        printf("%d\n",temp);
    }
}

中间UVA的没有做。M： Xn+Yn$\sqrt{b}$ 构造。题给条件没有完全使用， $(a-1)^2 < b < a^2$→$(a-\sqrt{b})^n<1 → S_n = 2*X_n $

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
ll a,b,n,m;
struct Matrix{
    ll m[3][3];
    Matrix(){
        memset(m, 0, sizeof m);
    }
};

Matrix mul(Matrix a, Matrix b){
    Matrix c;
    for(int i = 1; i <= 2; i++){
        for(int k = 1; k <= 2; k++)
        if(a.m[i][k]){
            for(int j = 1; j <= 2; j++)
            if(b.m[k][j]){
                c.m[i][j] = (c.m[i][j]+a.m[i][k]*b.m[k][j])%m;
            }
        }
    }
    return c;
}


Matrix powmul(Matrix a, int k){
    Matrix b;
    for(int i = 1; i <= 2; i++){
        b.m[i][i] = 1;
    }
    while(k){
        if(k&1)b = mul(b,a);
        a = mul(a,a);
        k>>=1;
    }
    return b;
}

int main(){
    while(~scanf("%lld%lld%lld%lld",&a,&b,&n,&m)){
        Matrix base,ans;
        base.m[1][1] = base.m[2][2] = a;
        base.m[1][2] = b;
        base.m[2][1] = 1;
        ans.m[1][1]=1;
        base = powmul(base, n);
        ans = mul(base,ans);
        ll ansss = 2*ans.m[1][1];
        printf("%lld\n",ansss%m);
    }
}

N 这里的N太大，只需要降N就行了，构造矩阵。锲而不舍的构造，不停的化解
$$
u(n+1,k)=\sum\limits_{i=0}^{k}C_k^i u(n,i)+\sum\limits_{i=0}^{k}C_k^{i}v(n,i)”
$$

$$
fn^k=f[n]\sum\limits_{i=0}^{k} C_k^i n^i=\sum\limits_{i=0}^{k}C_k^if[n]n^i”
$$

$$
v(n+1,k)=\sum\limits_{i=0}^{k}C_k^i u(n,i)”
$$

$$
\begin{pmatrix}S(n+1,k)\u(n+1,0)\u(n+1,1)\\vdots \u(n+1,k)\v(n+1,0)\v(n+1,1)\\vdots \v(n+1,k) \end{pmatrix}=\begin{pmatrix}1 & C_k^0 & C_k^1 &\cdots& C_k^k & C_k^0 & C_k^1 &\cdots& C_k^k\0 & 1 & 0 &\cdots& 0 & 1 & 0 &\cdots& 0\0 & C_1^0 & C_1^1 &\cdots& 0 & C_1^0 & C_1^1 &\cdots& 0\\vdots\0 & C_k^0 & C_k^1 &\cdots& C_k^k & C_k^0 & C_k^1 &\cdots& C_k^k\0 & 1 & 0 &\cdots& 0 & 0 & 0 &\cdots& 0\0 & C_1^0 & C_1^1 &\cdots& 0 & 0 & 0 &\cdots& 0\\vdots\0 & C_k^0 & C_k^1 &\cdots& C_k^k & 0 & 0 &\cdots& 0\\end{pmatrix} \begin{pmatrix}S(n,k)\u(n,0)\u(n,1)\\vdots \u(n,k)\v(n,0)\v(n,1)\\vdots \v(n,k) \end{pmatrix}
$$

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
78
79
80
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll unsigned long long
using namespace std;
int m = 1000000007;
ll C[50][50];
ll n,k;

struct Matrix{
    ll m[100][100];
    Matrix(){
        memset(m,0,sizeof m);
    }
};
Matrix mul(Matrix a, Matrix b){
    Matrix c;
    for(int i = 1; i <= 2*k+3; i++){
        for(int k1 = 1; k1 <= k*2+3; k1++)
        if(a.m[i][k1]){
            for(int j = 1; j <= k*2+3; j++)
            if(b.m[k1][j]){
                c.m[i][j] = (c.m[i][j]+a.m[i][k1]*b.m[k1][j])%m;
            }
        }
    }
    return c;
}

Matrix powmul(Matrix a, ll k1){
    Matrix b;
    for(int i = 1; i <= k*2+3; i++){
        b.m[i][i] = 1;
    }
    while(k1){
        if(k1&1)b = mul(b,a);
        a = mul(a,a);
        k1>>=1;
    }
    return b;
}

void init(){
    C[0][0] = 1;
    for(int i = 0; i < 49; i++){
        C[i+1][0]=1;
        for(int j = 1; j <= i; j++){
            C[i+1][j]=C[i][j]+C[i][j-1];
        }
        C[i+1][i+1] = 1;
    }
}

int main(){
    init();
    while(~scanf("%lld%lld",&n,&k)){
        Matrix base,r;
        base.m[1][1]=1;
        for(int i = 2; i <= 2*k+3; i++){
            if(i>k+2){
                base.m[1][i]=C[k][i-k-3];
            }else{
                base.m[1][i] = C[k][i-2];
            }
        }
        for(int i = 0; i <= k; i++){
            for(int j = 0; j <= i; j++){
                base.m[i+2][j+2]=C[i][j];
                base.m[i+3+k][j+2]=C[i][j];
                base.m[i+2][j+k+3]=C[i][j];
            }
        }
        for(int i = 1; i <= 2*k+3; i++){
            r.m[i][1]=1;
        }
        base = powmul(base, n-1);
        r = mul(base,r);
        printf("%lld\n",r.m[1][1]%m);
    }
}

R 这里根据地推关系式可以得出最后的结果只跟a,b的斐波那契额次方有关。

但是矩阵模的时候需要注意使用欧拉定理。$a^{n} \%c == a^{(n\%phi(c) + phi(c))}\%c$

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
ll mod = 1000000007;
ll m;
using namespace std;
ll n,k,a,b;
struct Matrix{
    ll m[3][3];
    Matrix(){
        memset(m,0,sizeof m);
    }
};

ll phi(ll n){
    ll res = n;
    for(int i = 2; i<=sqrt(n)+1; i++){
        if(n%i==0){
            res = res -res/i;
            while(n%i==0)n/=i;
        }
    }
    if(n>1)
        res=res-res/n;
    return res;
}

ll quickmode(ll a, ll b, ll c){
    ll res = 1;
    while(b){
        if(b&1)res=res*a%c;
        a=a*a%c;
        b>>=1;
    }
    return res;
}

Matrix mul(Matrix a, Matrix b){
    Matrix c;
    for(int i = 1; i <= 2; i++){
        for(int k1 = 1; k1 <= 2; k1++)
        if(a.m[i][k1]){
            for(int j = 1; j <= 2; j++)
            if(b.m[k1][j]){
                c.m[i][j] = (c.m[i][j]+a.m[i][k1]*b.m[k1][j])%m;
            }
        }
    }
    return c;
}

Matrix powmul(Matrix a, ll k1){
    Matrix b;
    for(int i = 1; i <= 2; i++){
        b.m[i][i] = 1;
    }
    while(k1){
        if(k1&1)b = mul(b,a);
        a = mul(a,a);
        k1>>=1;
    }
    return b;
}

ll power(ll a, ll k1){
    ll ans = 1;
    while(k1){
        if(k1&1)ans=ans*a%m;
        a=a*a%m;
        k1>>=1;
    }
    return ans;
}

int main(){
    while(~scanf("%lld%lld%lld",&a,&b,&n)){
        //if(a*b==0){printf("0\n");continue;}
        m = phi(mod);
        Matrix base,r;
        base.m[1][1]=base.m[1][2]=base.m[2][1]=1;
        r.m[2][1] = 1;
        base = powmul(base, n);
        r = mul(base, r);
        ll e1 = r.m[1][1] +m;
        ll e2 = r.m[2][1] +m;
        m = mod;
        //printf("%lld %lld\n",e1,e2);
        ll ans = power(a, e2)*power(b, e1);
        //printf("%lld %lld\n",power(a, e2),power(b ,e1));
        printf("%lld\n",ans%m);
    }
    return 0;
}

S 构造矩阵就行了。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
ll m = 1000000007;
ll n,a0,ax,ay,b0,bx,by;
using namespace std;
struct Matrix{
    ll m[6][6];
    Matrix(){
        memset(m, 0, sizeof m);
    }
};

Matrix mul(Matrix a, Matrix b){
    Matrix c;
    for(int i = 1; i <= 5; i++){
        for(int k = 1; k <= 5; k++)
        if(a.m[i][k]){
            for(int j = 1; j <= 5; j++)
            if(b.m[k][j]){
                c.m[i][j] = (c.m[i][j]+a.m[i][k]*b.m[k][j])%m;
            }
        }
    }
    return c;
}


Matrix powmul(Matrix a, ll k){
    Matrix b;
    for(int i = 1; i <= 5; i++){
        b.m[i][i] = 1;
    }
    while(k){
        if(k&1)b = mul(b,a);
        a = mul(a,a);
        k>>=1;
    }
    return b;
}
int main(){
    while(~scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&a0,&ax,&ay,&b0,&bx,&by)){
        Matrix base,r;
        base.m[1][1] = base.m[1][2] = 1;
        base.m[2][2] = ax*bx%m;
        base.m[2][3] = ax*by%m;
        base.m[2][4] = ay*bx%m;
        base.m[2][5] = ay*by%m;
        base.m[3][3] = ax%m;
        base.m[3][5] = ay%m;
        base.m[4][4] = bx%m;
        base.m[4][5] = by%m;
        base.m[5][5] = 1;
        r.m[1][1] = 0;
        r.m[2][1] = a0*b0%m;
        r.m[3][1] = a0%m;
        r.m[4][1] = b0%m;
        r.m[5][1] = 1;
        base = powmul(base, n);
        r = mul(base, r);
        printf("%lld\n",r.m[1][1]%m);
    }
    return 0;
}

计算几何

A—B应该是同类型，B排序一下就可以了。

B：

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

struct Point{
    int x,y;
};

struct Line{
    Point a,b;
    int v;
}line[5005];

int cnt[5005];

//叉积判断
int Multi(Point p0, Point p1, Point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

void BSearch(Point a, int n){
    int l,r, mid;

    l = 0;r = n - 1;
    while(l < r){
        mid = (l+r)>>1;
        if(Multi(a,line[mid].a, line[mid].b)>0) l = mid+1;
        else r = mid;
    }
    if(Multi(a, line[l].a, line[l].b) < 0)cnt[l]++;
    else cnt[l+1]++;
}

bool cmp(Line a, Line b){
    return a.v<b.v;
}

int ans[1001];

int main(){
    int n, m, x1, x2, y1, y2;
    Point a;
    int t1,t2;
    while(~scanf("%d",&n) && n){
        scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
        for(int i = 0; i < n; i++){
            scanf("%d%d", &t1, &t2);
            line[i].a.x = t1;
            line[i].a.y = y1;
            line[i].b.x = t2;
            line[i].b.y = y2;
            line[i].v = t1+t2;
        }
        sort(line, line+n, cmp);
        memset(cnt, 0, sizeof cnt);
        memset(ans, 0, sizeof ans);
        for(int i = 0; i < m; i++){
            scanf("%d%d",&a.x,&a.y);
            BSearch(a,n);
        }
        printf("Box\n");
        for(int i = 0; i <= n; i++){
            ans[cnt[i]]++;
        }
        for(int i = 1; i <= 1000; i++){
            if(ans[i])printf("%d: %d\n",i,ans[i]);
        }
    }
    return 0;
}

C: 其实就是任意两点能不能和其他直线都相交。

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
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
/*
方法：原命题等价为存在一条直线穿过所有的线段
（易知过公共点且垂直于所求直线的直线符合条件，设为直线a），
该命题又等价于从所有线段中任选两端点形成的直线存在可以穿过所有的线段的直线
（可将a平移至一条线段端点，然后绕这点旋转，使a过另一条线段端点）
*/
using namespace std;

const int N = 1e2+5;
const double eps = 1e-8;

struct Point{
    double x,y;
    Point(){};
    Point(double a, double b){
        x=a,y=b;
    }
}p[N*2];

struct Segment{
    Point a,b;
    Segment(){}
    Segment(Point x, Point y){
        a=x,b=y;
    }
}seg[N];

int n;

double Multi(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y-p0.y);
}

double dis(Point a, Point b){
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

bool slove(Segment x){
    for(int i = 0; i < n; i++){
        if(Multi(seg[i].a, x.a, x.b) * Multi(seg[i].b, x.a, x.b) > eps)
        return false;
    }
    return true;
}

int main(){
    int t;scanf("%d",&t);
    double x1,y1,x2,y2;
    while(t--){
        scanf("%d",&n);
        for(int i = 0; i < n; i++){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            p[2*i]=Point(x1,y1);p[2*i+1]=Point(x2,y2);
            seg[i]=Segment(p[2*i],p[2*i+1]);
        }
        bool flag = 0;
        if(n==1)flag = 1;
        for(int i = 0; i < 2*n; i++){
            for(int j = 0; j < i; j++){
                if(dis(p[i],p[j])>=eps && slove(Segment(p[i],p[j])))
                flag = true;
            }
            if(flag)break;
        }
        if(flag)puts("Yes!");
        else puts("No!");
    }
    return 0;
}

D：自己写的findPoint()的模板，事实证明是存在问题的，无法找出一个点和一个线段的焦点。很尴尬

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
78
79
80
81
82
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>

using namespace std;

const double eps = 1e-8;
const int N = 2;
struct Point{
    double x,y;
    Point(){};
    Point(double a, double b){
        x=a,y=b;
    }
}p[N*2];

struct Segment{
    Point a,b;
    Segment(){}
    Segment(Point x, Point y){
        a=x,b=y;
    }
}seg[N];

int n;

double Multi(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y-p0.y);
}

double dis(Point a, Point b){
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
int slove(Segment s1, Segment s2){
    if(max(fabs(Multi(s1.a, s2.a, s2.b)), fabs(Multi(s1.b, s2.a, s2.b)))<=eps)
        return 0;
    if(abs((s1.a.x-s1.b.x)*(s2.a.y-s2.b.y) - (s1.a.y-s1.b.y)*(s2.a.x-s2.b.x))<=eps)
        return 1;
    return 2;
}

void findPoint(Segment s1, Segment s2){
    double x1,y1,x2,y2,x3,y3,x4,y4;
    x1 = s1.a.x; y1 = s1.a.y;
    x2 = s1.b.x; y2 = s1.b.y;
    x3 = s2.a.x; y3 = s2.a.y;
    x4 = s2.b.x; y4 = s2.b.y;
    double ansx,ansy;
    if(x1==x2){
        ansx = x1;
        ansy = (y4-y3)*(ansx - x3)/(x4-x3) +y3;
    }else if(x3==x4){
        ansx = x3;
        ansy = (y2-y1)*(ansx - x1)/(x2-x1) +y1;
    }else{
        ansx = ( (y3-y1) + x1*(y2-y1)/(x2-x1) - x3*(y4-y3)/(x4-x3)  )/( (y2-y1)/(x2 - x1) -(y4-y3)/(x4-x3)  );
        ansy = (y2-y1)*(ansx - x1)/(x2-x1) +y1;
    }
    printf(" %.2lf %.2lf\n",ansx,ansy);
}

char output[][10]={"LINE","NONE","POINT"};
int main(){
    int t;scanf("%d",&t);
    puts("INTERSECTING LINES OUTPUT");
    double x1,y1;
    while(t--){
        for(int i = 0; i < 4; i++){
            scanf("%lf%lf",&x1,&y1);
            p[i] = Point(x1,y1);
        }
        seg[0] = Segment(p[0],p[1]);
        seg[1] = Segment(p[2],p[3]);
        int ans = slove(seg[0],seg[1]);
        printf("%s",output[ans]);
        if(ans == 2)findPoint(seg[0],seg[1]);
        else puts("");
    }
    puts("END OF OUTPUT");
    return 0;
}

Ｅ题还没写

Ｆ：是找出没有被压住的棍子,正序判的话，数据刚好很水就过了．

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;


const double eps = 1e-10;
const int N = 1e5+1000;
struct Point{
    double x,y;
    Point(){};
    Point(double a, double b){
        x=a,y=b;
    }
}p[N*2];

struct Segment{
    Point a,b;
    Segment(){};
    Segment(Point x, Point y){
        a=x,b=y;
    }
}seg[N];

int n;

double Multi(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y-p0.y);
}

bool intersect(Segment s1, Segment s2){
    if(Multi(s1.a, s2.a, s2.b)*Multi(s1.b, s2.a, s2.b) >= -eps)return false;
    if(Multi(s2.a, s1.a, s1.b)*Multi(s2.b, s1.a, s1.b) >= -eps)return false;
    return true;
}

bool vis[N];

int main(){
    while(~scanf("%d",&n) && n){
        memset(vis, 0, sizeof vis);
        double x1,x2,y1,y2;
        for(int i = 0; i < n; i++){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            p[2*i] = Point(x1,y1);
            p[2*i+1] = Point(x2,y2);
            seg[i] = Segment(p[2*i], p[2*i+1]);
        }
        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n; j++){
                if(intersect(seg[i],seg[j])){
                    vis[i] = 1;
                    break;
                }
            }
        }
        printf("Top sticks:");
        for(int i = 0; i < n-1; i++)
        if(!vis[i])printf(" %d,",i+1);
        printf(" %d.\n",n);
    }
    return 0;
}

Ｇ：只要找每个焦点和宝藏连线与其他直线相交的点的个数的最小值．坑在于这里只需要处理规范相交的，也就是说在同一直线或者交于端点是不算的．

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
78
79
80
81
82
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const double eps = 1e-8;
const int N = 1e5+1000;
struct Point{
    double x,y;
    Point(){};
    Point(double a, double b){
        x=a,y=b;
    }
}p[N*2];

struct Segment{
    Point a,b;
    Segment(){};
    Segment(Point x, Point y){
        a=x,b=y;
    }
}seg[N];

int n;

double Multi(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y-p0.y);
}


int dblcmp(double m){
    if(fabs(m) <eps)return 0;
    return m > 0?1:-1;
}

bool intersect_ex(Segment s1, Segment s2){
    //处理规范相交
    if(Multi(s1.a, s2.a, s2.b)*Multi(s1.b, s2.a, s2.b) < -eps
    && Multi(s2.a, s1.a, s1.b)*Multi(s2.b, s1.a, s1.b) < -eps
    )return true;
    return false;
}


bool intersect(Segment s1, Segment s2){
//处理非规范相交
    if(dblcmp(max(s1.a.x, s1.b.x) - min(s2.a.x, s2.b.x) > 0)
    && dblcmp(max(s2.a.x, s2.b.x) - min(s1.a.x, s1.b.x) > 0)
    && dblcmp(max(s1.a.y, s1.b.y) - min(s2.a.y, s2.b.y) > 0)
    && dblcmp(max(s2.a.y, s2.b.y) - min(s1.a.y, s1.b.y) > 0)
    && dblcmp(Multi(s1.a, s2.a, s2.b)* Multi(s1.b, s2.a, s2.b) < 0)
    && dblcmp(Multi(s2.a, s1.a, s1.b)* Multi(s2.b, s1.a, s1.b) <= 0)
    )return true;
    return false;
}



int ans[100];

int main(){
    scanf("%d",&n);
    double x1,y1,x2,y2;
    for(int i = 0; i < n; i++){
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
        p[i*2] = Point(x1,y1);
        p[i*2+1] = Point(x2,y2);
        seg[i] = Segment(p[2*i], p[i*2+1]);
    }
    if(n>0)scanf("%lf%lf",&x1,&y1);
    int minx = ~0u>>1;
    for(int i = 0; i < 2*n; i++){
        for(int j = 0; j < n; j++){
            if(intersect_ex(seg[j], Segment(Point(x1,y1), p[i])))
            ans[i]++;
            //printf("(%lf,%lf):%d\n",p[i].x,p[i].y,ans[i]);
        }
        minx = min(minx,ans[i]);
    }
    if(n==0)minx = 0;
    printf("Number of doors = %d\n",minx+1);
    return 0;
}

Ｈ：处理非规范相交(有点相交就行)．注意，直线一点在矩形里面也算．

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
78
79
80
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

const double eps = 1e-10;
const int N = 1000;
struct Point{
    double x,y;
    Point(){};
    Point(double a, double b){
        x=a,y=b;
    }
}p[N*2];

struct Segment{
    Point a,b;
    Segment(){};
    Segment(Point x, Point y){
        a=x,b=y;
    }
}seg[N];

int n;

double Multi(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y-p0.y);
}

int dblcmp(double m){
    if(fabs(m) <eps)return 0;
    return m > 0?1:-1;
}


bool intersect(Segment s1, Segment s2){
//处理非规范相交
    if(dblcmp(max(s1.a.x, s1.b.x) - min(s2.a.x, s2.b.x) >= 0)
    && dblcmp(max(s2.a.x, s2.b.x) - min(s1.a.x, s1.b.x) >= 0)
    && dblcmp(max(s1.a.y, s1.b.y) - min(s2.a.y, s2.b.y) >= 0)
    && dblcmp(max(s2.a.y, s2.b.y) - min(s1.a.y, s1.b.y) >= 0)
    && dblcmp(Multi(s1.a, s2.a, s2.b)* Multi(s1.b, s2.a, s2.b) <= 0)
    && dblcmp(Multi(s2.a, s1.a, s1.b)* Multi(s2.b, s1.a, s1.b) <= 0)
    )return true;
    return false;
}

bool inRect(Point a, Point x, Point y){
    if(max(x.x, y.x) >= a.x && a.x >= min(x.x, y.x)
     &&max(x.y, y.y) >= a.y && a.y >= min(x.y, y.y)
    )return true;
    return false;
}

int main(){
    scanf("%d",&n);
    double x1,y1,x2,y2,x3,y3,x4,y4;
    while(n--){
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
        p[0]=Point(x1,y1);p[1]=Point(x2,y2);
        p[2]=Point(x3,y3);p[3]=Point(x4,y3);
        p[4]=Point(x4,y4);p[5]=Point(x3,y4);
        seg[0]=Segment(p[0],p[1]);
        seg[1]=Segment(p[2],p[3]);
        seg[2]=Segment(p[3],p[4]);
        seg[3]=Segment(p[4],p[5]);
        seg[4]=Segment(p[5],p[2]);
        bool flag = 0;
        for(int i = 1; i < 5; i++){
            if(intersect(seg[0],seg[i])){
                flag=1;break;
            }
        }
        if(inRect(p[0],p[2],p[4]) || inRect(p[1],p[2],p[4]))
            flag = true;
        if(flag)puts("T");
        else puts("F");
    }
    return 0;
}

Ｉ：这题是寻找一个凸包．我用了两个方法，卷包裹法和极坐标的，极坐标的写起来简单一些．

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

const double eps = 1e-8;
const int N = 60;
struct Point{
    double x,y;
    int id;
    Point(){};
    Point(double a, double b, int i){
        x=a,y=b,id=i;
    }
}p[N*2];

struct Segment{
    Point a,b;
    Segment(){};
    Segment(Point x, Point y){
        a=x,b=y;
    }
}seg[N];

int n;

double dis(Point a, Point b){
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double Multi(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y);
}

double dMulti(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.x - p0.x)+(p1.y - p0.y)*(p2.y - p0.y);
}

double ang(Point p0, Point p1, Point p2){
    return acos(dMulti(p0, p1, p2)/dis(p0, p1)/dis(p0, p2));
}

bool inRect(Point a, Point x, Point y){
    if(max(x.x, y.x) >= a.x && a.x >= min(x.x, y.x)
     &&max(x.y, y.y) >= a.y && a.y >= min(x.y, y.y)
    )return true;
    return false;
}

int dblcmp(double m){
    if(fabs(m) <eps)return 0;
    return m > 0?1:-1;
}

bool intersect_ex(Segment s1, Segment s2){
    //处理规范相交
    if(Multi(s1.a, s2.a, s2.b)*Multi(s1.b, s2.a, s2.b) < -eps
    && Multi(s2.a, s1.a, s1.b)*Multi(s2.b, s1.a, s1.b) < -eps
    )return true;
    return false;
}


bool intersect(Segment s1, Segment s2){
//处理非规范相交
    if(dblcmp(max(s1.a.x, s1.b.x) - min(s2.a.x, s2.b.x) > 0)
    && dblcmp(max(s2.a.x, s2.b.x) - min(s1.a.x, s1.b.x) > 0)
    && dblcmp(max(s1.a.y, s1.b.y) - min(s2.a.y, s2.b.y) > 0)
    && dblcmp(max(s2.a.y, s2.b.y) - min(s1.a.y, s1.b.y) > 0)
    && dblcmp(Multi(s1.a, s2.a, s2.b)* Multi(s1.b, s2.a, s2.b) < 0)
    && dblcmp(Multi(s2.a, s1.a, s1.b)* Multi(s2.b, s1.a, s1.b) <= 0)
    )return true;
    return false;
}

bool vis[N*2];

void JuanBaoGuo(int st){
    memset(vis ,0 ,sizeof vis);
    vis[st]=1;
    Point now = p[st];
    Point pre = Point(0,p[st].y,-1);

    printf("%d %d", n, now.id);
    int cont = 1;
    while(cont<n){
        //printf("\n");
        double minx = -1;
        int v=0;
        for(int i = 0; i < n; i++){
            if(vis[i])continue;
            double temp = ang(now, pre, p[i]);
            
            if(temp >= minx && Multi(p[i], pre, now) > -eps){
                minx =temp;
                v = i;
            }
        }
        printf(" %d",p[v].id);
        cont++;
        pre = now;
        now = p[v];
        vis[v] = 1;
    }
    puts("");
}
//找最小的点
bool cmp(Point a, Point b){
    if(a.y==b.y)return a.x<b.x;
    return a.y<b.y;
}
Point o;//变换的中点
bool cmpx(Point a, Point b){
    int x1 = a.x - o.x;
    int y1 = a.y - o.y;
    int x2 = b.x - o.x;
    int y2 = b.y - o.y;
    if(x1*y2 - x2*y1>0)return 1;
    if(x1*y2 == x2*y1 && x1*x1 + y1*y1 < x2*x2 + y2*y2)return 1;
    return 0;
}

void polar(){
    sort(p, p+n, cmp);
    for(int i = 0; i < n - 1; i++){
        o = p[i];
        sort(p+i,p+n,cmpx);
    }
    printf("%d",n);
    for(int i = 0; i < n; i++){
        printf("% d",p[i].id);
    }
    puts("");
}

int main(){
    int m;scanf("%d",&m);
    while(m--){
        scanf("%d",&n);
        int x1,y1,id;
        Point minx = Point(-1,1<<28,-1);
        for(int i = 0; i < n; i++){
            scanf("%d%d%d",&id,&x1,&y1);
            p[i] = Point(x1, y1, id);
            if(p[i].y < minx.y)minx = p[i];
        }
        //卷包裹法：
        //JuanBaoGuo(minx.id-1);
        //极坐标：
        polar();

    }
    return 0;
}

Ｊ：一道数学题把，主要需要注意每添加一个方块都需要和前面所有的判断一下然后找到最大的左端．

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
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
int n;
struct Square{
    int len,l,r;
}sq[55];
int main(){
    while(~scanf("%d",&n) && n){
        memset(sq, 0, sizeof sq);
        int temp = 0;
        for(int i = 0; i < n; i++){
            scanf("%d",&temp);
            sq[i].len = temp;
            sq[i].l=0;
            for(int j = 0; j < i; j++){
                int t1;
                if(sq[i].len <= sq[j].len )t1 = sq[j].l + sq[j].len + sq[i].len;
                else t1 = sq[j].l + 3*sq[j].len - sq[i].len;
                if(t1 > sq[i].l)sq[i].l = t1;
            }
            sq[i].r = sq[i].l+2*sq[i].len;
        }
        //update l,r;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(sq[j].len < sq[i].len && sq[j].r > sq[i].l)
                    sq[j].r = sq[i].l;
                else if(sq[j].len > sq[i].len && sq[j].r > sq[i].l)
                    sq[i].l = sq[j].r;
            }
        }
        for(int i = 0; i < n; i++){
            if(sq[i].l<sq[i].r)printf("%d ",i+1);
        }
        puts("");
    }
    return 0;
}

K: 一道比较猥琐的题目，需要注意上面一个板子如果盖住了下面的一个板子的特殊情况．我写的模板不能处理点与点相交或者点与线段相交．可能是我选取的方法不是很好．

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

const double eps = 1e-8;
const int N = 60;
struct Point{
    double x,y;
    Point(){};
    Point(double a, double b){
        x=a,y=b;
    }
}p[N*2];

struct Segment{
    Point a,b;
    Segment(){};
    Segment(Point x, Point y){
        a=x,b=y;
    }
}seg[N];

int n;

double dis(Point a, Point b){
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double Multi(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y);
}

double dMulti(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.x - p0.x)+(p1.y - p0.y)*(p2.y - p0.y);
}

double ang(Point p0, Point p1, Point p2){
    return acos(dMulti(p0, p1, p2)/dis(p0, p1)/dis(p0, p2));
}

bool inRect(Point a, Point x, Point y){
    if(max(x.x, y.x) >= a.x && a.x >= min(x.x, y.x)
     &&max(x.y, y.y) >= a.y && a.y >= min(x.y, y.y)
    )return true;
    return false;
}

int dblcmp(double m){
    if(fabs(m) <eps)return 0;
    return m > 0?1:-1;
}

bool intersect_ex(Segment s1, Segment s2){
    //处理规范相交
    if(Multi(s1.a, s2.a, s2.b)*Multi(s1.b, s2.a, s2.b) < -eps
    && Multi(s2.a, s1.a, s1.b)*Multi(s2.b, s1.a, s1.b) < -eps
    )return true;
    return false;
}


bool intersect(Segment s1, Segment s2){
//处理非规范相交
    if(dblcmp(max(s1.a.x, s1.b.x) - min(s2.a.x, s2.b.x) >= 0)
    && dblcmp(max(s2.a.x, s2.b.x) - min(s1.a.x, s1.b.x) >= 0)
    && dblcmp(max(s1.a.y, s1.b.y) - min(s2.a.y, s2.b.y) >= 0)
    && dblcmp(max(s2.a.y, s2.b.y) - min(s1.a.y, s1.b.y) >= 0)
    && dblcmp(Multi(s1.a, s2.a, s2.b)* Multi(s1.b, s2.a, s2.b) <= 0)
    && dblcmp(Multi(s2.a, s1.a, s1.b)* Multi(s2.b, s1.a, s1.b) <= 0)
    )return true;
    return false;
}

Point findPoint(Segment s1, Segment s2){
    double x1,y1,x2,y2,x3,y3,x4,y4;
    x1 = s1.a.x; y1 = s1.a.y;
    x2 = s1.b.x; y2 = s1.b.y;
    x3 = s2.a.x; y3 = s2.a.y;
    x4 = s2.b.x; y4 = s2.b.y;
    double ansx,ansy;
    if(dblcmp(x1-x2)==0){
        if(dblcmp(x3-x4)==0){
            if(dblcmp(y3-y4)==0)return Point(x1,y3);
            else if(dblcmp(y1-y2)==0)return Point(x1,y1);
        }
        ansx = x1;
        ansy = (y4-y3)*(ansx - x3)/(x4-x3) +y3;
    }else if(dblcmp(x3-x4)==0){
        ansx = x3;
        ansy = (y2-y1)*(ansx - x1)/(x2-x1) +y1;
    }else{
        ansx = ( (y3-y1) + x1*(y2-y1)/(x2-x1) - x3*(y4-y3)/(x4-x3)  )/( (y2-y1)/(x2 - x1) -(y4-y3)/(x4-x3)  );
        ansy = (y2-y1)*(ansx - x1)/(x2-x1) +y1;
    }
    return Point(ansx, ansy);
}

double getK(Point a, Point b){
    return (b.y-a.y)/(b.x-a.x);
}

int main(){
    int n;
    scanf("%d",&n);
    double x1,y1,x2,y2,x3,y3,x4,y4;
    while(n--){
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
        p[0] = Point(x1,y1);p[1] = Point(x2,y2);
        p[2] = Point(x3,y3);p[3] = Point(x4,y4);
        seg[0] = Segment(p[0],p[1]);
        seg[1] = Segment(p[2],p[3]);
        if(!intersect(seg[0],seg[1])){printf("0.00\n");continue;}
        Point cross = findPoint(seg[0],seg[1]);
        Point l,r;
        //cout << cross.x << " " << cross.y << endl;
        if(p[0].y > cross.y){l = p[0];}
        else if(p[1].y > cross.y){l = p[1];}
        else{printf("0.00\n");continue;}
        if(p[2].y > cross.y)r = p[2];
        else if(p[3].y > cross.y)r = p[3];
        else{printf("0.00\n");continue;}
        double ans=1;
        if(l.x != cross.x && r.x != cross.x){
            if( (l.x >= r.x && r.x > cross.x ) && (getK(cross, l)>=getK(cross, r) ))
            ans = 0;
            if( (r.x >= l.x && l.x > cross.x ) && (getK(cross, r)>=getK(cross, l) ))
            ans = 0;
            if( (l.x <= r.x && r.x < cross.x ) && (getK(cross, l)<=getK(cross, r) ))
            ans = 0;
            if( (r.x <= l.x && l.x < cross.x ) && (getK(cross, r)<=getK(cross, l) ))
            ans = 0;
        }
        if(ans){
            if(l.y > r.y){
                l = findPoint(Segment(Point(x1,r.y), Point(x2,r.y)), seg[0]);
           // cout << l.x << l.y << ":" << r.x << r.y << endl;
            }else if(l.y < r.y){
                r = findPoint(Segment(Point(x3,l.y), Point(x4,l.y)), seg[1]);
            }
            ans = fabs(Multi(cross,l,r));
        }
        printf("%.2lf\n",ans/2);
    }
    return 0;
}

后面的工作量比较大，已放弃．

期间使用的模板的整理

  • 矩阵
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
int mod = 6;
struct Matrix{
    int m[10][10];
    Matrix(){
        memset(m,0,sizeof m);
    }
};

int n,k;

Matrix mul(Matrix a, Matrix b){
    Matrix c;
    for(int i = 1; i <= k; i++){
        for(int k1 = 1; k1 <= k; k1++)
        if(a.m[i][k1]){
            for(int j = 1; j <= k; j++)
            if(b.m[k1][j]){
                c.m[i][j] = (c.m[i][j]+a.m[i][k1]*b.m[k1][j])%mod;
            }
        }
    }
    return c;
}

Matrix powmul(Matrix a, int m){
    Matrix b;
    for(int i = 1; i <= k; i++){
        b.m[i][i] = 1;
    }
    while(m){
        if(m&1)b = mul(b,a);
        a = mul(a,a);
    //cout << " 1 " <<endl;
        m>>=1;
    }
    return b;
}
  • 欧拉函数
1
2
3
4
5
6
7
8
9
10
11
12
ll phi(ll n){
    ll res = n;
    for(int i = 2; i<=sqrt(n)+1; i++){
        if(n%i==0){
            res = res -res/i;
            while(n%i==0)n/=i;
        }
    }
    if(n>1)
        res=res-res/n;
    return res;
}
  • 计算几何
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
const double eps = 1e-8;
const int N = 60;
struct Point{
    double x,y;
    Point(){};
    Point(double a, double b){
        x=a,y=b;
    }
}p[N*2];

struct Segment{
    Point a,b;
    Segment(){};
    Segment(Point x, Point y){
        a=x,b=y;
    }
}seg[N];

int n;
//距离
double dis(Point a, Point b){
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
//叉积判断点在线段两端．跟eps或者-eps比较会有不同的结果，注意．
double Multi(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y);
}
//点积
double dMulti(Point p0, Point p1, Point p2){
    return (p1.x - p0.x)*(p2.x - p0.x)+(p1.y - p0.y)*(p2.y - p0.y);
}
//算角度，利用点积算的acos角度，也就是说方向是需要额外判断的
double ang(Point p0, Point p1, Point p2){
    return acos(dMulti(p0, p1, p2)/dis(p0, p1)/dis(p0, p2));
}
//点在矩形里面．
bool inRect(Point a, Point x, Point y){
    if(max(x.x, y.x) >= a.x && a.x >= min(x.x, y.x)
     &&max(x.y, y.y) >= a.y && a.y >= min(x.y, y.y)
    )return true;
    return false;
}
//处理近似０和eps的关系的
int dblcmp(double m){
    if(fabs(m) <eps)return 0;
    return m > 0?1:-1;
}
//修改eps前面的符号有不同效果．
bool intersect_ex(Segment s1, Segment s2){
    //处理规范相交
    if(Multi(s1.a, s2.a, s2.b)*Multi(s1.b, s2.a, s2.b) < -eps
    && Multi(s2.a, s1.a, s1.b)*Multi(s2.b, s1.a, s1.b) < -eps
    )return true;
    return false;
}


bool intersect(Segment s1, Segment s2){
//处理非规范相交
    if(dblcmp(max(s1.a.x, s1.b.x) - min(s2.a.x, s2.b.x) >= 0)
    && dblcmp(max(s2.a.x, s2.b.x) - min(s1.a.x, s1.b.x) >= 0)
    && dblcmp(max(s1.a.y, s1.b.y) - min(s2.a.y, s2.b.y) >= 0)
    && dblcmp(max(s2.a.y, s2.b.y) - min(s1.a.y, s1.b.y) >= 0)
    && dblcmp(Multi(s1.a, s2.a, s2.b)* Multi(s1.b, s2.a, s2.b) <= 0)
    && dblcmp(Multi(s2.a, s1.a, s1.b)* Multi(s2.b, s1.a, s1.b) <= 0)
    )return true;
    return false;
}
//斜率
double getK(Point a, Point b){
    return (b.y-a.y)/(b.x-a.x);
}
//找线段的相交的点(必须是线段,且必须是相交的)．
void findPoint(Segment s1, Segment s2){
    double x1,y1,x2,y2,x3,y3,x4,y4;
    x1 = s1.a.x; y1 = s1.a.y;
    x2 = s1.b.x; y2 = s1.b.y;
    x3 = s2.a.x; y3 = s2.a.y;
    x4 = s2.b.x; y4 = s2.b.y;
    double ansx,ansy;
    if(x1==x2){
        ansx = x1;
        ansy = (y4-y3)*(ansx - x3)/(x4-x3) +y3;
    }else if(x3==x4){
        ansx = x3;
        ansy = (y2-y1)*(ansx - x1)/(x2-x1) +y1;
    }else{
        ansx = ( (y3-y1) + x1*(y2-y1)/(x2-x1) - x3*(y4-y3)/(x4-x3)  )/( (y2-y1)/(x2 - x1) -(y4-y3)/(x4-x3)  );
        ansy = (y2-y1)*(ansx - x1)/(x2-x1) +y1;
    }
    printf(" %.2lf %.2lf\n",ansx,ansy);
}

//加强版．．．．
Point findPoint(Segment s1, Segment s2){
    double x1,y1,x2,y2,x3,y3,x4,y4;
    x1 = s1.a.x; y1 = s1.a.y;
    x2 = s1.b.x; y2 = s1.b.y;
    x3 = s2.a.x; y3 = s2.a.y;
    x4 = s2.b.x; y4 = s2.b.y;
    double ansx,ansy;
    if(dblcmp(x1-x2)==0){
        if(dblcmp(x3-x4)==0){
            if(dblcmp(y3-y4)==0)return Point(x1,y3);
            else if(dblcmp(y1-y2)==0)return Point(x1,y1);
        }
        ansx = x1;
        ansy = (y4-y3)*(ansx - x3)/(x4-x3) +y3;
    }else if(dblcmp(x3-x4)==0){
        ansx = x3;
        ansy = (y2-y1)*(ansx - x1)/(x2-x1) +y1;
    }else{
        ansx = ( (y3-y1) + x1*(y2-y1)/(x2-x1) - x3*(y4-y3)/(x4-x3)  )/( (y2-y1)/(x2 - x1) -(y4-y3)/(x4-x3)  );
        ansy = (y2-y1)*(ansx - x1)/(x2-x1) +y1;
    }
    return Point(ansx, ansy);
}

期间刷的其他无专题性水题另外给出。

本文标题:acm7-7总结

文章作者:呼哧

发布时间:2017-07-07, 18:40:42

最后更新:2018-08-04, 02:45:44

原始链接:http://hu-chi.github.io/2017/07/07/acm/7-7acm整理笔记/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 7-7acm总结：
    1. 1.1. 概率与期望(kuangbin)
    2. 1.2. 矩阵
    3. 1.3. 计算几何
    4. 1.4. 期间使用的模板的整理
|