Chengrui's Blog

0%

发表于 分类于 ， Disqus：

中学物理知识推推公式就能出来，没什么好说的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<cmath>
using namespace std;
const double g=9.81;
int main(){
    double k,l,s,m;
    while(~scanf("%lf%lf%lf%lf",&k,&l,&s,&m)&&(k||l||s||m)){
        double dtl=(m*g+sqrt(m*m*g*g+2.0*k*l*m*g))/k;
        if(s>l+dtl) puts("Stuck in the air.");
        else{
            double v=2.0*g*s;
            if(s>l) v-=k*(s-l)*(s-l)/m;
            if(v<=100.0) puts("James Bond survives.");
            else puts("Killed by the impact.");
        }
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出一些01串，含星号的串表示包含两个串，星号位置分别为0和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
59
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2100;
int n,m;
char s[15];
int a[maxn];
bool _set[maxn],g[maxn][maxn];
int from[maxn];
bool vis[maxn];
bool match(int x){
    for(int i=0;i<maxn;++i)
        if(g[x][i]&&!vis[i]){
            vis[i]=true;
            if(from[i]==-1||match(from[i])){
                from[i]=x;
                return true;
            }
        }
    return false;
}
int hungary(){
    int tot=0;
    memset(from,-1,sizeof from);
    for(int i=0;i<maxn;++i){
        memset(vis,0,sizeof vis);
        tot+=match(i);
    }
    return tot;
}
int main(){
    while(~scanf("%d%d",&n,&m)&&(n||m)){
        memset(g,0,sizeof g);
        memset(_set,0,sizeof _set);
        for(int i=0;i<m;++i){
            scanf("%s",s);
            int pos=-1,tmp=0;
            for(int j=0;j<n;++j)
                if(s[j]=='1') tmp|=1<<j;
                else if(s[j]=='*') pos=j;
            _set[tmp]=true;
            if(pos!=-1){
                tmp|=1<<pos;
                _set[tmp]=true;
            }
        }
        m=0;
        for(int i=0;i<maxn;++i)
            if(_set[i]){
                ++m;
                for(int j=0;j<n;++j){
                    int tmp=i^(1<<j);
                    if(_set[tmp]) g[i][tmp]=true;
                }
            }
        printf("%d\n",m-hungary()/2);
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

给出两个序列，第一个序列中的数不重复，求两个序列的LCS。
以为第一个序列的数不同，所以可以保存数在第一个序列中出现的顺序，然后删除第二个序列中不再第一个序列中的数，将剩下的数换成在第一个序列中出现的位置，对处理好的 序列求LIS。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=62510;
int s[maxn],num[maxn],d[maxn];
int main(){
    int t,tt=0;scanf("%d",&t);
    while(t--){
        int n,p,q;
        scanf("%d%d%d",&n,&p,&q);
        memset(num,0,sizeof num);
        for(int i=1;i<=p+1;++i){
            int x;scanf("%d",&x);
            num[x]=i;
        }
        n=0;
        for(int i=0;i<=q;++i){
            int x;scanf("%d",&x);
            if(num[x]) s[n++]=num[x];
        }
        fill(d,d+n,inf);
        for(int i=0;i<n;++i) *lower_bound(d,d+n,s[i])=s[i];
        printf("Case %d: %d\n",++tt,int(lower_bound(d,d+n,inf)-d));
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

给出一个序列，求连续子序列和大于s的最短子序列长度。
尺取法，最开始子序列只有第一个数，当不满足条件时，移动终点延长子序列；当序列和满足条件时，移动起点缩短子序列，遍历数组复杂度 O ( 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>
#include<algorithm>
using namespace std;
const int maxn=100010;
int a[maxn];
int main(){
    int n,s;
    while(~scanf("%d%d",&n,&s)){
        for(int i=0;i<n;++i) scanf("%d",&a[i]);
        int res=n+1;
        int l=0,r=0,sum=0;
        for(;;){
            while(r<n&&sum<s) sum+=a[r++];
            if(sum<s) break;
            res=min(res,r-l);
            sum-=a[l++];
        }
        if(res>n) res=0;
        printf("%d\n",res);
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

现在输入一个整数 k ，每次取前 n 位，反复平方，一直下去，输出能得到的最大数。每次取前 n 位所以一定会出现循环，使用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
#include<cstdio>
#include<algorithm>
typedef long long LL;
using namespace std;
int buf[100];
int Next(int n,int k){
    if(!k) return 0;
    LL k2=LL(k)*k;
    int l=0;
    while(k2>0){
        buf[l++]=k2%10;
        k2/=10;
    }
    n=min(n,l);
    int ans=0;
    for(int i=0;i<n;++i)
        ans=ans*10+buf[--l];
    return ans;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int n,k;scanf("%d%d",&n,&k);
        int ans=k,k1=k,k2=k;
        do{
            k1=Next(n,k1);
            k2=Next(n,k2);ans=max(ans,k2);
            k2=Next(n,k2);ans=max(ans,k2);
        }while(k1!=k2);
        printf("%d\n",ans);
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

向正方形中填字母，每个字母不能和邻近的字母相同，输出字典序最小的解。直接从第一个开始构造，从A到Z枚举生成。

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>
const int maxn=15;
char g[maxn][maxn];
int main(){
    int t,tt=0;scanf("%d",&t);
    while(t--){
        int n;scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%s",g[i]+1);
        printf("Case %d:\n",++tt);
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j)
                if(g[i][j]=='.')
                    for(int ch='A';ch<='Z';++ch){
                        if(ch==g[i-1][j]) continue;
                        if(ch==g[i][j-1]) continue;
                        if(ch==g[i+1][j]) continue;
                        if(ch==g[i][j+1]) continue;
                        g[i][j]=ch;
                        break;
                    }
            printf("%s\n",g[i]+1);
        }
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

给出n、m，有n个蛋糕，m+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
#include<cstdio>
#include<cmath>
using namespace std;
const double EPS=1e-6;
const double PI=acos(-1);
const int maxn=10010;
int n,f;
double a[maxn];
inline double c(double r){
    return PI*r*r;
}
bool ok(double x){
    int sum=0;
    for(int i=0;i<n;++i){
        sum+=floor(a[i]/x);
    }
    return sum>=f+1;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){scanf("%d%d",&n,&f);
        double sum=0;
        for(int i=0;i<n;++i){
            scanf("%lf",&a[i]);
            a[i]=c(a[i]);
            sum+=a[i];
        }
        double l=0,r=sum,m=(l+r)/2;
        while(r-l>EPS){
            if(ok(m)) l=m;
            else r=m;
            m=(l+r)/2;
        }
        printf("%.4f\n",m);
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

求所给点的凸包每个顶点向外延伸半径为 l 的圆后所得图形的周长。
凸包周长模板题，求得凸包周长后加上以 l 为半径的圆的周长就是墙的长度。

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<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
struct point{
    double x,y;
}a[maxn],b[maxn];
bool mult(point p0,point p1,point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)>=(p2.x-p0.x)*(p1.y-p0.y);
}
bool operator<(const point &p1,const point &p2){
    return p1.y<p2.y||(p1.y==p2.y&&p1.x<p2.x);
}
int graham(point pnt[],int n,point res[]){
    int i,len,top=1;
    sort(pnt,pnt+n);
    if(n==0) return 0;
    res[0]=pnt[0];
    if(n==1) return 1;
    res[1]=pnt[1];
    if(n==2) return 2;
    res[2]=pnt[2];
    for(i=2;i<n;i++){
        while(top&&mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top]=pnt[i];
    }
    len=top;res[++top]=pnt[n-2];
    for(i=n-3;i>=0;i--){
        while(top!=len&&mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top]=pnt[i];
    }
    return top;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int n,l;scanf("%d%d",&n,&l);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
        int k=graham(a,n,b);
        double ans=0;
        for(int i=0;i<k-1;++i)
            ans+=sqrt((b[i].x-b[i+1].x)*(b[i].x-b[i+1].x)+(b[i].y-b[i+1].y)*(b[i].y-b[i+1].y));
        if(k>2) ans+=sqrt((b[k-1].x-b[0].x)*(b[k-1].x-b[0].x)+(b[k-1].y-b[0].y)*(b[k-1].y-b[0].y));
        ans+=2*acos(-1)*l;
        printf("%.0lf\n",ans);
        if(t) printf("\n");
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

输入 n 、 m ，求最大 k 使 ( m k ) % n = 0 。首先筛选出所有素数，然后求出所有 n ，唯一分解的结果。对于 m 进行分解，对于每一个在 m 中的素数 p [ i ] 的指数 e [ i ] ， k = m i n ( e [ i ] ) 。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10010;
int p[maxn],pnum,en[maxn][1250],em[maxn];
bool np[maxn]={1,1};
void init(){
    for(int i=2;i<maxn;++i)
        if(!np[i]){
            p[pnum++]=i;
            for(int j=i*i;j<maxn;j+=i)
                np[j]=true;
        }
    for(int i=2;i<maxn;++i){
        int k=i;
        for(int j=0;j<pnum;++j){
            while(k%p[j]==0) k/=p[j],++en[i][j];
            en[i][j]+=en[i-1][j];
        }
    }
    return;
}
int main(){
    init();
    int t,tt=0;scanf("%d",&t);
    while(t--){
        memset(em,0,sizeof em);
        int m,n;scanf("%d%d",&m,&n);
        int ans=0x3f3f3f3f;
        for(int i=0;i<pnum;++i){
            while(m%p[i]==0) m/=p[i],++em[i];
            if(em[i]) ans=min(en[n][i]/em[i],ans);
        }
        printf("Case %d:\n",++tt);
        if(ans) printf("%d\n",ans);
        else puts("Impossible to divide");
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

求一个数n拆成k个数的方法个数。
利用隔板法求得

a n s = ( n + k − 1 k − 1 )

利用 c [ i ] [ j ] = ( c [ i − 1 ] [ j ] + c [ i − 1 ] [ j − 1 ] ) % m o d 递推预处理组合数，然后读入 n 、 k 输出答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
const int maxn=210;
const int mod=1000000;
int c[maxn][maxn];
int main(){
    for(int i=0;i<maxn;++i) c[i][0]=1;
    for(int i=1;i<maxn;++i)
        for(int j=1;j<=i;++j)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    int n,k;
    while(~scanf("%d%d",&n,&k)&&(n||k))
        printf("%d\n",c[n+k-1][k-1]);
    return 0;
}

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