新普金娱乐网址


克回的无非是那时候的记忆,我们惟有深入的想念

数学SQL Server语言 函数以及SQL编程

数学bzoj 2326 矩阵乘法

  • 九月 23, 2018
  • 数学
  • 没有评论

Input

*第一行: N

*第2..N+1行: 第i行里有 T_i 和 P_i.

[HNOI2011]数学作业

Time Limit: 10 Sec  Memory
Limit: 128 MB
Submit: 2415  Solved: 1413
[Submit][Status][Discuss]

Sample Input

5
1 2
5 9
3 8
4 10
1 3

输入解释:

Bessy 考了5门试, 分数分别吗1/2, 5/9, 3/8, 4/10, 1/3.

Description

数学 1.jpg).jpg)

 

思路:令f[n]表示Concatenate(1,n)。那么有:

f[i]=f[i-1]*10+(i-1)+1   1<=i<=9

f[i]=f[i-1]*100+(i-1)+1  10<=i<=99

……

为此可用矩阵加速:

数学 2

但,这个矩阵是分段的。

 

分段矩阵乘法即可。

 

 1 #include<cstring>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdio>
 6 
 7 #define ll long long
 8 using namespace std;
 9 
10 ll n,m;
11 ll a[4][4],b[4][4];
12 
13 ll mul(ll a,ll b)
14 {
15     ll ans=0;
16     while(b)
17     {
18         if (b%2==1) ans=(ans+a)%m;
19         a=(a<<1)%m;
20         b>>=1;
21     }
22     return ans;
23 }
24 void mmul(ll a[4][4],ll b[4][4],ll c[4][4])
25 {
26     ll t[4][4];
27     for (int i=1;i<=3;i++)
28         for (int j=1;j<=3;j++)
29         {
30             t[i][j]=0;
31             for (int k=1;k<=3;k++)
32                 t[i][j]=(t[i][j]+mul(a[i][k],b[k][j]))%m;
33         }
34     for (int i=1;i<=3;i++)
35         for (int j=1;j<=3;j++)
36             c[i][j]=t[i][j];
37 }
38 void cal(ll t,ll x)
39 {
40     memset(b,0,sizeof(b));
41     b[1][1]=t,b[2][1]=b[2][2]=b[3][1]=b[3][2]=b[3][3]=1;
42     ll y=x-t/10+1;
43     while(y)
44     {
45         if (y&1) mmul(a,b,a);
46         mmul(b,b,b);
47         y>>=1;
48     }
49 }
50 int main()
51 {
52     scanf("%lld%lld",&n,&m);
53     for (int i=1;i<=3;i++)
54         a[i][i]=1;
55     ll t=10;
56     while(n>=t)
57     {
58         cal(t,t-1);
59         t*=10;
60     }
61     cal(t,n);
62     printf("%lld",a[3][1]);    
63 }

 

Description

Bessy 正在上并且分还不错. 她考了N (一个数量被1 <= N <= 50,000,
其余数据 1 <= N <= 50,00) 次试,每次试验得分为T_i, 满分为P_i(0
<= T_i <= P_i < 40,000; 0 < P_i).
在盘算总分时,她底老师先拿拿分数(P_i/T_i)最高的D个试卷去丢,然后用那余P_i
的和除因其余T_i的及当Bessy的分数.
Bessy精通数学,所以高速发现这并不曾想象中那么好.
Bessy想告知她底民办教师有附和以下条件的D:
如果让一组(D个)分数去丢,她的分数回比老师竟出来的又高. Bessy
很诧异地窥见其未曾少蹩脚试得分百分点是平的.

Sample Output

2
1
2

 

题解:

枚举剩下的分个数kk,设高的kk个分数和底积极分子分母分别吗UU和DD。

那么在甄选了之中间找到A=min(Dt[x]−Up[x])A=min(Dt[x]−Up[x]),没选的内部找到B=max(Dt[x]−Up[x])B=max(Dt[x]−Up[x])。

若是A<BA<B,则可以再次甚。

于A,BA,B的精打细算,可以用决策单调性分治求解。

时间复杂度O(nlogn)O(nlog⁡n)。

充分可以之数学思量。

 1 #include<cstring>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdio>
 6 
 7 #define ll long long
 8 #define ls tr[p].l
 9 #define rs tr[p].r
10 #define N 100007
11 using namespace std;
12 const ll inf=2000000000000010;
13 inline ll read()
14 {
15     ll x=0,f=1;char ch=getchar();
16     while(ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
17     while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 
21 int n,ans,q[N];
22 ll f[N],g[N];
23 struct Node
24 {
25     int t,p;
26 }a[N],b[N];
27 
28 inline bool cmp(Node a,Node b)
29 {
30     return a.t*b.p>b.t*a.p;
31 }
32 void getf(int l,int r,int dl,int dr)
33 {
34     int m=(l+r)>>1,dm;
35     f[m]=inf;
36     for(int i=dl;i<=m&&i<=dr;i++)
37     {
38         ll t=1LL*a[i].t*b[m].p-1LL*a[i].p*b[m].t;
39         if(t<f[m])f[m]=t,dm=i;
40       }
41     if(l<m)getf(l,m-1,dl,dm);
42     if(r>m)getf(m+1,r,dm,dr);
43 }
44 void getg(int l,int r,int dl,int dr)
45 {
46     int m=(l+r)>>1,dm;
47     g[m]=-inf;
48       for(int i=dr;i>m&&i>=dl;i--)
49     {    
50         ll t=1LL*a[i].t*b[m].p-1LL*a[i].p*b[m].t;
51         if(t>g[m])g[m]=t,dm=i;
52       }
53       if(l<m)getg(l,m-1,dl,dm);
54       if(r>m)getg(m+1,r,dm,dr);
55 }
56 int main()
57 {
58     scanf("%d",&n);
59       for(int i=1;i<=n;i++)
60         scanf("%d%d",&a[i].t,&a[i].p);
61       sort(a+1,a+n+1,cmp);
62       for(int i=1;i<=n;i++)
63           b[i].t=b[i-1].t+a[i].t,b[i].p=b[i-1].p+a[i].p;
64       getf(1,n-1,1,n),getg(1,n-1,1,n);
65       for(int i=1;i<n;i++)
66           if(f[i]<g[i]) q[++ans]=n-i;
67     printf("%d\n",ans);
68     for(int i=ans;i;i--)
69         printf("%d\n",q[i]);
70 }

 

[Usaco2007 Jan]Cow School牛学校

Time Limit: 5 Sec  Memory
Limit: 64 MB
Submit: 175  Solved: 83
[Submit][Status][Discuss]

Output

* 第一执: K, 符合条件的D的个数.

*第2..K+1行: 按递增顺序,每行一个符合条件的D.

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图