Chengrui's Blog

0%

发表于 分类于 ， Disqus：

给出能相互到达的网页，输出在给出的网页中相互到达需要点击几次，首先离散化，然后用Floyd求少点击次数，枚举求平均点击次数。

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<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=110;
const int inf=0x3f3f3f3f;
int d[maxn][maxn];
map<int,int> id;
int main(){
    int n,u,v,t=0;
    while(~scanf("%d%d",&u,&v)&&(u||v)){
        memset(d,0x3f,sizeof d);
        id.clear();
        n=0;
        if(!id.count(u)) id[u]=++n;
        if(!id.count(v)) id[v]=++n;
        d[id[u]][id[v]]=1;
        while(~scanf("%d%d",&u,&v)&&(u||v)){
            if(!id.count(u)) id[u]=++n;
            if(!id.count(v)) id[v]=++n;
            d[id[u]][id[v]]=1;
        }
        for(int k=1;k<=n;++k)
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j)
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        int sum=0;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(i!=j&&d[i][j]!=inf) sum+=d[i][j];
        printf("Case %d: average length between pages = %.3lf clicks\n",++t,double(sum)/(n*(n-1)));
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出一个 s ，然后给出 n 组邮票，问那一组可以凑出最大连续邮资。
对每一组邮票，求出当邮资为i时需要邮票数的最小值 d [ i ] ，边界为 d [ 0 ] = 0 、 d [ i ] > s 时break。类似于背包问题的求法，具体方法见代码。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int d[maxn],ans[20],num[20],a[20][20];
int main(){
    int s;
    while(~scanf("%d",&s)&&s){
        int n;scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&num[i]);
            for(int j=1;j<=num[i];++j) scanf("%d",&a[i][j]);
            memset(d,0x3f,sizeof(d));
            d[0]=0;
            for(int j=1;j<maxn;++j){
                for(int k=1;k<=num[i]&&j-a[i][k]>=0;++k)
                    d[j]=min(d[j],d[j-a[i][k]]+1);
                if(d[j]>s){ans[i]=j-1;break;}
            }
        }
        int best=-1,pos=0;
        for(int i=1;i<=n;++i){
            if(ans[i]>best) best=ans[i],pos=i;
            else if(ans[i]==best){
                if(num[i]<num[pos]) pos=i;
                else if(num[i]==num[pos]){
                    bool ok=false;
                    for(int j=num[i];j>0;--j)
                        if(a[i][j]!=a[pos][j]){
                            ok=a[i][j]<a[pos][j];
                            break;
                        }
                    if(ok) pos=i;
                }
            }
        }
        printf("max coverage =%4d :",ans[pos]);
        for(int i=1;i<=num[pos];i++)
            printf("%3d",a[pos][i]);
        printf("\n");
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出 n 个相同的气球， k 层楼，问最少几次试验可以知道气球最高从多少层扔下不会爆。
用 d [ i ] [ j ] 表示用 i 个球，实验 j 次所能确定的最高楼层数，对于每一次试验分爆和不爆两种情况讨论：
1、爆了，转移到 d [ i − 1 ] [ j − 1 ] + 1 ，用掉了1个球和一次试验机会。
2、没爆，将当前测试层数的上一层当做第1层继续进行试验，转移到 d [ i ] [ j − 1 ] 。
得出转移方程 d [ i ] [ j ] = d [ i − 1 ] [ j − 1 ] + 1 + d [ i ] [ j − 1 ] 。
好久之前做的题了，具体思路见紫书。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
ULL d[110][65],k,n;
int main(){
     for(int i=1;i<110;++i)
        for(int j=1;j<65;++j)
            d[i][j]=d[i-1][j-1]+1+d[i][j-1];
     while(~scanf("%llu%llu",&k,&n)&&k){
        int ans = 0;
        for(int i=64;i>=0;--i)
            if(d[k][i]<n){
                ans=i+1;
                break;
            }
        if(ans<=63) printf("%d\n",ans);
        else puts("More than 63 trials needed.");
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出一个计算机网络，选取其中给一部分作为服务器，问最少选择几个服务器。
一共有三种状态：
1、 d [ u ] [ 0 ] ：u是服务器，每个子结点可以是也可以不是。
2、 d [ u ] [ 1 ] ：u不是服务器，但u的父亲是，u的子结点都不是服务器。
3、 d [ u ] [ 2 ] ：u和u的父亲都不是服务器，u的子结点恰有一个是服务器。
三种状态的转移：
d [ u ] [ 0 ] = ∑ m i n ( d [ v ] [ 0 ] , d [ v ] [ 1 ] ) + 1 。
d [ u ] [ 1 ] = ∑ d [ v ] [ 2 ] 。
d [ u ] [ 2 ] = m i n ( d [ u ] [ 1 ] − d [ v ] [ 2] + d [ v ] [ 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
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=10010;
vector<int> g[maxn];
int d[maxn][3];
int vis[maxn];
int dp(int u){
    vis[u]=1;
    d[u][0]=1,d[u][1]=0,d[u][2]=maxn;
    queue<int> q;
    for(int i=0;i<g[u].size();++i)
        if(!vis[g[u][i]]){
            dp(g[u][i]);
            q.push(g[u][i]);
            d[u][0]+=min(d[g[u][i]][0],d[g[u][i]][1]);
            d[u][1]+=d[g[u][i]][2];
        }
    while(!q.empty()){
        d[u][2]=min(d[u][2],d[u][1]-d[q.front()][2]+d[q.front()][0]);
        q.pop();
    }
    return 0;
}

int main(){
    int n;
    while(~scanf("%d",&n)&&n!=-1){
        if(!n) continue;
        for(int i=1;i<=n;++i) g[i].clear();
        memset(vis,0,sizeof(vis));
        for(int i=1;i<n;++i){
            int u,v;scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dp(1);
        printf("%d\n",min(d[1][0],d[1][2]));
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出两个点和多个正方形，求两点与原点连线和正方形围成的最大面积。
当正方形对角线共线且与两边构成等腰三角形是面积最大。联立方程求出三角形底边两点坐标，然后利用向量叉乘求出面积。

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        double ax,ay,bx,by;
        scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
        double l=0,ans=0;
        for(int i=0;i<n;++i){
            double a;
            scanf("%lf",&a);
            l+=a;
            ans-=a*a/2;
        }
        double k1=ay/ax,k2=by/bx;
        if(k1>k2) swap(k1,k2);
        ax=(k1+1)*l/(k2-k1),ay=k1*ax;
        bx=(k2+1)*l/(k2-k1),by=k2*bx;
        ans+=(ax*by-ay*bx)/2;
        printf("%.3lf\n",ans);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

枚举50000以内的数，对数，利用快速幂求值验证。

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
#include<cstdio>
#include<cmath>
using namespace std;
int fexp(int a,int b){
    int cur=1,t=a;
    while(b){
        if(b&1) cur*=t;
        t*=t;
        b>>=1;
    }
    return cur;
}
int find(int n){
    for(int i=2;i<50000;++i){
        int k=(log10(fabs(n))/log10(i)+0.01);
        if(fexp(i,k)==n) return k;
        if(fexp(-i,k)==n) return k;
    }
    return 1;
}
int main(){
    int n;
    while(~scanf("%d",&n)&&n)
        printf("%d\n",find(n));
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

求给出的范围内有多少对互素的整数答案为 2 ∗ f ( n ) + 1 , f ( n ) = ∑ n 2 p h i ( n ) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
using namespace std;
const int maxn=50010;
int f[maxn],n;
void phi_table(int n,int* phi){
    for(int i=2;i<=n;++i) phi[i]=0;
    phi[1]=1;
    for(int i=2;i<=n;++i)
        if(!phi[i])
            for(int j=i;j<=n;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
    return;
}
int main(){
    phi_table(maxn-1,f);
    for(int i=3;i<maxn;++i)
        f[i]+=f[i-1];
    while(~scanf("%d",&n)&&n)
        printf("%d\n",n==1?1:f[n]*2+1);
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

对m进行分解，然后从 ( n − 1 0 ) 计算到 ( n − 1 n − 1 ) ，对每个数能否被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
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=100010;
int p[110],e[110],pnum;
int ans[maxn],pos;
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        pnum=pos=0;
        int k=sqrt(m);
        for(int i=2;i<=k;++i){
            if(m%i==0){
                p[pnum]=i,e[pnum]=0;
                while(m%i==0) m/=i,++e[pnum];
                ++pnum;
            }
            if(m==1) break;
        }
        if(m>1){
            p[pnum]=m;
            e[pnum]=1;
            ++pnum;
        }
        int cnt=pnum;
        for(int i=1;i<n;++i){
            int a=n-i,b=i;
            for(int j=0;j<pnum;++j){
                while(a%p[j]==0){
                    a/=p[j];
                    --e[j];
                    if(e[j]==0) --cnt;
                }
                while(b%p[j]==0){
                    b/=p[j];
                    ++e[j];
                    if(e[j]==1) ++cnt;
                }
            }
            if(cnt==0) ans[pos++]=i+1;
        }
        printf("%d\n",pos);
        if(pos==0) printf("\n");
        for(int i=0;i<pos;++i)
            printf("%d%c",ans[i],i==pos-1?'\n':' ');
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

输入一个数 n ， ( 1 ≤ n ≤ 30000000 ) ，输出有多少对整数满足 1 ≤ a ≤ b ≤ n , g c d ( a , b ) = a ⨁ b 。
设 c = a ⨁ b ，则 a ⨁ c = b 。找规律可得，当满足条件时， c = a − b 。
因此，枚举 c 、 a ，对每一对验证 c = a ⨁ b 即可。时间复杂度 O ( n l o g n ) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
using namespace std;
const int maxn=30000010;
int a[maxn];
void init(){
    int k=maxn/2;
    for(int i=1;i<k;++i)
        for(int j=i+i;j<maxn;j+=i)
            if(i==(j^(j-i))) ++a[j];
    for(int i=1;i<maxn;++i)
        a[i]+=a[i-1];
    return;
}
int main(){
    init();
    int t,tt=0;scanf("%d",&t);
    while(t--){
        int n;scanf("%d",&n);
        printf("Case %d: %d\n",++tt,a[n]);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

首先筛选出2到 ( 2 3 1 − 1 ) ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ √ 的素数，然后对每个输入的数进行分解。最后若只有一个素因子，则得出的和要加1。输入为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
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
#include<cstdio>
#include<cstring>
#include<cmath>
typedef long long LL;
using namespace std;
const int maxn=46350;
bool np[maxn];
int p[4800],prime;
int e[4800];
void init(){
    for(int i=2;i<maxn;++i){
        if(!np[i]) p[prime++]=i;
        for(int j=0;j<prime&&i*p[j]<maxn;++j){
            np[i*p[j]]=true;
            if(!(i%p[j])) break;
        }
    }
    return;
}
LL fexp(int a,int b){
    LL cur=1,tmp=a;
    while(b){
        if(b&1) cur=cur*tmp;
        tmp=tmp*tmp;
        b>>=1;
    }
    return cur;
}
int main(){
    init();
    int t=0;
    LL n;
    while(~scanf("%lld",&n)&&n){
        if(n==1){
            printf("Case %d: 2\n",++t);
            continue;
        }
        memset(e,0,sizeof(e));
        int cnt=0;
        LL ans=0;
        for(int i=0;i<prime;++i){
            while(n%p[i]==0) n/=p[i],++e[i];
            if(e[i]>0) ++cnt,ans+=fexp(p[i],e[i]);
            if(n==1) break;
        }
        if(n!=1) ++cnt,ans+=n;
        if(cnt==1) ++ans;
        printf("Case %d: %lld\n",++t,ans);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **