Chengrui's Blog

0%

发表于 分类于 ， 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
#include<cstdio>
int a[9][9];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        for(int i=0;i<9;i+=2)
            for(int j=0;j<=i;j+=2)
                scanf("%d",&a[i][j]);
        for(int i=8;i>0;i-=2)
            for(int j=1;j<i;j+=2)
                a[i][j]=(a[i-2][j-1]-a[i][j-1]-a[i][j+1])/2;
        for(int i=1;i<9;i+=2)
            for(int j=0;j<=i;++j)
                a[i][j]=a[i+1][j]+a[i+1][j+1];
        for(int i=0;i<9;++i){
            for(int j=0;j<=i;++j){
                if(j) printf(" ");
                printf("%d",a[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

求所给的数能用多少种连续素数的和表示。

类似于求最大连续和优化的方法。使用前缀和减少运算。然后输入范围是2到10000，貌似可以打表交。

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
#include<cstdio>
const int maxn=10010;
int isp[1250],pre_p,sum[1250];
bool np[maxn]={true,true};
void prepare(){
    for(int i=2;i<maxn;++i){
        if(!np[i])
            isp[pre_p++]=i;
        for(int j=0;j<pre_p&&i*isp[j]<maxn;++j){
            np[i*isp[j]]=true;
            if(!(i%isp[j])) break;
        }
    }
    for(int i=1;i<=pre_p;++i)
        sum[i]=sum[i-1]+isp[i-1];
    return;
}
int main(){
    prepare();
    int n;
    while(~scanf("%d",&n)&&n){
        int cnt=0;
        for(int i=0;i<pre_p;++i){
            if(isp[i]>n) break;
            for(int j=i+1;j<=pre_p;++j)
                if(n==sum[j]-sum[i]) ++cnt;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出两个1e12以内的数，求有多少不是素数，但是一个素数的n次方（n>1）数。

一开始用set存了所有的数，之后用set.find()循环求得两个迭代器，再用distance求个数，但是因为所求的数的间隔较大，循环会超时……虽然超时了， 但是学了求迭代器距离的方法，收获也挺大。

后来改为如下做法，首先打素数表，然后分别求比所给的两个数小的数的个数，求两者差。

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
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000010;
LL isp[78500],pre_p;
bool np[maxn]={true,true};
void prime(){
    for(int i=2;i<maxn;++i){
        if(!np[i])
            isp[pre_p++]=i;
        for(int j=0;j<pre_p&&i*isp[j]<maxn;++j){
            np[i*isp[j]]=true;
            if(!(i%isp[j])) break;
        }
    }
    return;
}
LL solve(LL n){
    LL cnt=0;
    for(int i=0;i<pre_p;++i){
        LL cur=isp[i]*isp[i];
        while(cur<n) cur*=isp[i],++cnt;
    }
    return cnt;
}
int main(){
    prime();
    int t;
    scanf("%d",&t);
    while(t--){
        LL l,r;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",solve(r+1)-solve(l));
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

特别抽象的一道题，给出数据总量n，数组p的元素大小sp，数组q元素大小sq，求使Qofs'(i)=(Pofs(i)+Pofs(i)<<A)>>B成立的A、B 的值，和q数组占用的空间k。

一开始没看懂题目，翻译之后感觉不知从何下手。直到看到了 code4101 的博文：http://blog.csdn.net/code4101/article/details/38540759

只需要从枚举32以内的A、B并判断是否合法即可，最终保留最小的k和使k最小的a、b。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
typedef long long LL;
int main(){
    LL n,sp,sq;
    while(~scanf("%lld%lld%lld",&n,&sp,&sq)){
        LL best=(LL)1<<62,a,b,aa=0,bb=0;
        for(a=0;a<32;++a)
            for(b=0;b<32;++b){
                LL cur=(((n-1)*sp+((n-1)*sp<<a))>>b)+sq;
                if(cur>=n*sq&&cur<best) best=cur,aa=a,bb=b;
            }
        printf("%lld %lld %lld\n",best,aa,bb);
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出数据块，判断能否恢复数据且是否合法。

好久前跳过去的一道题，找了个英语大神翻译之后总算看懂了……读懂题之后其实并不难，就是简单的数据处理。

一开始没注意到样例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
52
53
54
55
56
57
58
59
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=6500;
int d,s,b,n;
char data[7][maxn];
bool parity;
bool read(){
    scanf("%d%d%d\n",&d,&s,&b);
    if(!d) return false;
    memset(data,0,sizeof(data));
    parity=getchar()=='O',n=s*b;
    for(int i=0;i<d;++i)
        scanf("%s",data[i]);
    return true;
}
bool solve(){
    for(int i;i<n;++i){
        bool k=false;
        int broke=-1;
        for(int j=0;j<d;++j){
            char& c=data[j][i];
            if(c=='1') k=!k;
            if(c=='x'){
                if(broke!=-1) return false;
                else broke=j;
            }
        }
        if(broke==-1&&k!=parity) return false;//校验不合法。
        if(broke!=-1) data[broke][i]=k==parity?'0':'1';//修复。
    }
    return true;
}
void print_ans(bool v){
    if(!v) {printf("invalid.\n");return;}
    printf("valid, contents are: ");
    int num=0,cnt=0;
    for(int i=0;i<b;++i){
        int pos=i*s;
        for(int j=0;j<d;++j){
            if(i%d==j) continue;//校验块跳过。
            for(int k=0;k<s;++k){
                num<<=1,num+=data[j][pos+k]=='1',++cnt;
                if((cnt%=4)==0) printf("%X",num),num=0;
            }
        }
    }
    if(cnt) printf("%X",num<<(4-cnt));//补0。
    printf("\n");
    return;
}
int main(){
    int t=0;
    while(read()){
        printf("Disk set %d is ",++t);
            print_ans(solve());
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出一个1到n的排列，给出操作顺序，使升序排列能变为所给排列。

书上的表述又出错了，导致WA了一次。倒着从所给排列变回升序排列，然后倒着打印解。当前两个已经是升序，就把最后一个拿到前面，否则交换之后再拿。

感觉只要不是求最少步解的题，都可以用构造法转化成类似方法求解。

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<algorithm>
#include<vector>
using namespace std;
int n;
vector<int> a,ans;
int main(){
    while(~scanf("%d",&n)&&n){
        a.clear(),ans.clear();
        for(int i=0;i<n;++i){
            int k;
            scanf("%d",&k);
            a.push_back(k);
        }
        while(1){
            if(a[0]==1){
                bool ok=true;
                for(int i=0;i<n;++i)
                    if(a[i]!=i+1){ok=false;break;}
                if(ok) break;
            }
            if(a[0]<a[1]||(a[1]==1&&a[0]==n)){//注意有特例。
                ans.push_back(2);
                a.insert(a.begin(),a[n-1]);
                a.erase(a.end()-1);
            }
            else{
                ans.push_back(1);
                swap(a[0],a[1]);
            }
        }
        for(int i=(int)ans.size()-1;i>=0;--i)
            printf("%d",ans[i]);
        printf("\n");
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出一个1到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
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=10010;
int n,a[maxn],pos[maxn];
struct range{
    int l,r;
    range(int l=0,int r=0):l(l),r(r){}
    void print(){
        printf("%d %d\n",l+1,r+1);
        return;
    }
};
vector<range> ans;
void Swap(int sta,int len){
    for(int i=0;i<len;++i)
        swap(a[sta+i],a[sta+len+i]),swap(pos[a[sta+i]-1],pos[a[sta+len+i]-1]);
    ans.push_back(range(sta,sta+len*2-1));
    return;
}
void solve(){
    ans.clear();
    for(int i=0;i<n;++i){
        if(pos[i]==i) continue;
        while(pos[i]-i>(n-i)/2)//调整i到能够一次调好的位置。
            Swap(pos[i]*2-n,n-pos[i]);
        Swap(i,pos[i]-i);
    }
    return;
}
void print_ans(){
    printf("%d\n",(int)ans.size());
    for(int i=0;i<ans.size();++i)
        ans[i].print();
    return;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;++i)
            scanf("%d",&a[i]),pos[a[i]-1]=i;
        solve();
        print_ans();
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出一个n个数字的串，去掉d个数字使得串的数值最大。

用贪心法解决，当前一个的数字小于后一个数字时，前一个即被去掉，当去掉个数足够时，读入剩下的字符即可。如果去掉的数目不够，剩下的数字则不存入。

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<vector>
using namespace std;
vector<char> s;
int main(){
    int n,d;
    while(~scanf("%d%d",&n,&d)&&n){
        int len=n-d;
        s.clear(),getchar();
        for(int i=0;i<n;++i){
            char c=getchar();
            if(s.size()>0){
                int p=(int)s.size()-1;//从最后一个字符开始判断是否去除。
                while(d&&c>s[p]&&p>=0){
                    s.erase(s.begin()+p--);
                    --d;
                }
            }
            if(s.size()!=len) s.push_back(c);//字符数目未满，继续存入。
            else --d;
        }
        for(int i=0;i<s.size();++i) putchar(s[i]);
        printf("\n");
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出四个数组a、b、c、d，每个取一个数字，求有多少种取法使得和值为0。

枚举a、b中的和，查找c、d中的和的相反数有没有与a、b的和相等的。O(n^2*logn)的算法，如书上所说的，使用multiset和count超时了，改用 数组之后Ac。

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 maxn=4010;
int a[4][maxn],sum[maxn*maxn];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,p=0,cnt=0;
        scanf("%d",&n);
        memset(sum,0,sizeof(sum));
        for(int i=0;i<n;++i)
            for(int j=0;j<4;++j)
                scanf("%d",&a[j][i]);
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                sum[p++]=a[0][i]+a[1][j];
        sort(sum,sum+p);
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                cnt+=upper_bound(sum,sum+p,-a[2][i]-a[3][j])-lower_bound(sum,sum+p,-a[2][i]-a[3][j]);
        printf("%d\n",cnt);
        if(t) printf("\n");
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出两个01?串，求通过多少次变换可以让第一个与第二个相同。可进行的变换有把0变成1，把?变成0或1，交换两个字符。

使用交换把两串相同的交换没有意义，所以仅对两串有差异的地方进行统计。0可以任意变成1，而0只能通过交换或?产生，所以对第一个串中需要由1变为0的处理就成了关 键。首先是用效率最高的交换，然后使用?，如果交换和使用?都无法满足，那么就不能相同。处理完需要由1变为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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=210;
char s[maxn],s0[maxn];
int solve(int n){
    int sum,_0_1,_1_0,_1_q,_0_q,cnt;
    sum=_1_0=_0_1=_1_q=_0_q=cnt=0;
    for(int i=0;i<n;++i){
        if(s0[i]=='1'&&s[i]=='?') ++sum,++_1_q;
        if(s0[i]=='0'&&s[i]=='?') ++sum,++_0_q;
        if(s0[i]=='1'&&s[i]=='0') ++sum,++_1_0;
        if(s0[i]=='0'&&s[i]=='1') ++sum,++_0_1;
    }
    int t=min(_1_0,_0_1);//交换。
    cnt+=t,_0_1-=t,sum-=2*t;
    t=min(_1_q,_0_1);//使用?替换后交换。
    cnt+=2*t,_0_1-=t,sum-=2*t;
    if(_0_1) return -1;
    return cnt+sum;
}
int main(){
    int t,tt=0;
    scanf("%d",&t);
    while(t--){
        scanf("%s%s",s,s0);
        printf("Case %d: %d\n",++tt,solve((int)strlen(s0)));
    }
    return 0;
}

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