Chengrui's Blog

0%

发表于 分类于 ， Disqus：

模拟网页搜索，直接遍历查找会超时，需要使用映射或指针一类的简化查找。
直接用STL写的，原本准备超时之后再用指针重写，没想到2.595s过了，就懒得改了。

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
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<vector>
#include<set>
#include<map>
using namespace std;
struct inc{
    set<int> doc,line[110];
};
map<string,inc> dict;
vector<string> a[110];
void pre(string s,int a,int l){
    for(int i=0;i<s.length();++i)
        if(isalpha(s[i])) s[i]=tolower(s[i]);
        else s[i]=' ';
    stringstream ss(s);
    while(ss>>s){
        if(!dict.count(s)) dict[s]=inc();
        dict[s].doc.insert(a);
        dict[s].line[a].insert(l);
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    //freopen("in_1.txt","w",stdout);
    int n,m,cnt;
    cin>>n;cin.get();
    for(int i=0;i<n;++i){
        cnt=0;
        string s;
        while(getline(cin,s),s!="**********"){
            pre(s,i,cnt++);
            a[i].push_back(s);
        }
    }
    cin>>m;cin.get();
    for(int i=0;i<m;++i){
        bool flag=true;
        string s;
        getline(cin,s);
        if(s.find(" AND ")!=s.npos){
            stringstream ss(s);
            string s1,s2;
            ss>>s1>>s2>>s2;
            for(int i=0;i<n;++i){
                if(dict[s1].doc.count(i)&&dict[s2].doc.count(i)){
                    if(flag) flag=false;
                    else cout<<"----------\n";
                    set<int> k;
                    for(set<int>::iterator it=dict[s1].line[i].begin();it!=dict[s1].line[i].end();++it)
                        k.insert(*it);
                    for(set<int>::iterator it=dict[s2].line[i].begin();it!=dict[s2].line[i].end();++it)
                        k.insert(*it);
                    for(set<int>::iterator it=k.begin();it!=k.end();++it)
                        cout<<a[i][*it]<<endl;
                }
            }
        }
        else if(s.find(" OR ")!=s.npos){
            stringstream ss(s);
            string s1,s2;
            ss>>s1>>s2>>s2;
            for(int i=0;i<n;++i){
                if(dict[s1].doc.count(i)||dict[s2].doc.count(i)){
                    if(flag) flag=false;
                    else cout<<"----------\n";
                    set<int> k;
                    for(set<int>::iterator it=dict[s1].line[i].begin();it!=dict[s1].line[i].end();++it)
                        k.insert(*it);
                    for(set<int>::iterator it=dict[s2].line[i].begin();it!=dict[s2].line[i].end();++it)
                        k.insert(*it);
                    for(set<int>::iterator it=k.begin();it!=k.end();++it)
                        cout<<a[i][*it]<<endl;
                }
            }
        }
        else if(s.find("NOT ")!=s.npos){
            string s0=s.substr(4);
            for(int i=0;i<n;++i){
                if(!dict[s0].doc.count(i)){
                    if(flag) flag=false;
                    else cout<<"----------\n";
                    for(int j=0;j<a[i].size();++j)
                        cout<<a[i][j]<<endl;
                }
            }
        }
        else{
            for(int i=0;i<n;++i){
                if(dict[s].doc.count(i)){
                    if(flag) flag=false;
                    else cout<<"----------\n";
                    for(set<int>::iterator it=dict[s].line[i].begin();it!=dict[s].line[i].end();++it)
                        cout<<a[i][*it]<<endl;
                }
            }
        }
        if(flag) cout<<"Sorry, I found nothing.\n";
        cout<<"==========\n";
    }
    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
27
28
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1010;
int a[maxn],b[maxn];
int main(){
    int n;
    while(cin>>n,n){
        for(int i=0;i<n;++i) cin>>a[i];
        for(int i=0;i<n;++i) cin>>b[i];
        sort(a,a+n),sort(b,b+n);
        int sta1=0,sta2=0,ed1=n-1,ed2=n-1,win=0,lose=0;
        while(sta1<=ed1&&sta2<=ed2){
            if(a[sta1]<b[sta2]) ++sta1,--ed2,++lose;
            else if(a[sta1]>b[sta2]) ++sta1,++sta2,++win;
            else{
                if(a[ed1]>b[ed2]) --ed1,--ed2,++win;
                else if(a[ed1]<b[ed2]) ++sta1,--ed2,++lose;
                else{
                    if(a[sta1]<b[ed2]) ++lose;
                    ++sta1,--ed2;
                }
            }
        }
        cout<<(win-lose)*200<<endl;
    }
    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
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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=70;
int n,k[10]={1};
char g[maxn][maxn];
vector<int> a;
int solve_g(int l,int r,int u,int d,int cur,int p){
    bool w=true,b=true;
    for(int i=u;i<=d;++i){
        if(!w&&!b) break;
        for(int j=l;j<=r;++j){
            if(g[i][j]=='1') w=false;
            else b=false;
        }
    }
    if(w||b) return b?cur:-1;
    int h=l+(r-l+1)/2,v=u+(d-u+1)/2,t;
    if((t=solve_g(l,h-1,u,v-1,cur+1*k[p],p+1))!=-1) a.push_back(t);
    if((t=solve_g(h,r,u,v-1,cur+2*k[p],p+1))!=-1) a.push_back(t);
    if((t=solve_g(l,h-1,v,d,cur+3*k[p],p+1))!=-1) a.push_back(t);
    if((t=solve_g(h,r,v,d,cur+4*k[p],p+1))!=-1) a.push_back(t);
    return -1;
}
void solve_a(int b){
    int l=0,r=n-1,u=0,d=n-1;
    while(b){
        int h=l+(r-l+1)/2,v=u+(d-u+1)/2;
        switch(b%5){
            case 1:r=h-1,d=v-1;break;
            case 2:l=h,d=v-1;break;
            case 3:r=h-1,u=v;break;
            case 4:l=h,u=v;break;
        }
        b/=5;
    }
    for(int i=u;i<=d;++i)
        for(int j=l;j<=r;++j)
            g[i][j]='*';
    return;
}
int main(){
    for(int i=1;i<10;++i) k[i]=k[i-1]*5;
    int t=0;
    while(scanf("%d",&n),n){
        if(t) printf("\n");
        printf("Image %d\n",++t);
        a.clear();
        memset(g,0,sizeof(g));
        if(n>0){
            getchar();
            for(int i=0;i<n;++i) fgets(g[i],maxn-1,stdin);
            int k;
            if((k=solve_g(0,n-1,0,n-1,0,0))!=-1) a.push_back(k);
            sort(a.begin(),a.end());
            for(int i=0;i<a.size();){
                printf("%d",a[i++]);
                if(i%12==0||i==(int)a.size()) printf("\n");
                else printf(" ");
            }
            printf("Total number of black nodes = %d\n",(int)a.size());
        }
        else{
            n=-n;
            while(1){
                int k;
                scanf("%d",&k);
                if(k<0) break;
                solve_a(k);
            }
            for(int i=0;i<n;++i){
                for(int j=0;j<n;++j)
                    if(!g[i][j]) g[i][j]='.';
                puts(g[i]);
            }
        }
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

模拟Petri网变迁，读懂题之后其实不难。
建一个petri结构体，ip、op是参与变迁的place的编号。用数组记录每个参与变迁的place的tokens改变量。剩下的就好办了，题目说明了只会有唯一 解，所以只需要循环执行可以进行的变迁就好了。

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
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=105;
int p,t,np[maxn],lim;
struct petri{
    int ip,op,i[maxn],o[maxn],in[maxn],out[maxn];
} pet[maxn];
int main(){
    int tt=0;
    while(scanf("%d",&p),p){
        memset(pet,0,sizeof(pet));
        for(int i=1;i<=p;++i) scanf("%d",&np[i]);
        scanf("%d",&t);
        for(int i=1;i<=t;++i){
            int k;
            while(scanf("%d",&k),k){
                if(k<0) ++pet[i].in[-k];
                else ++pet[i].out[k];
            }
            for(int j=1;j<=p;++j){
                if(pet[i].in[j]) pet[i].i[++pet[i].ip]=j;
                if(pet[i].out[j]) pet[i].o[++pet[i].op]=j;
            }
        }
        scanf("%d",&lim);
        int cnt=0;
        for(int i=1;i<=t;++i){
            bool flag=true;
            petri &k=pet[i];
            for(int j=1;j<=k.ip;++j)
                if(np[k.i[j]]<k.in[k.i[j]]){flag=false;break;}
            if(!flag) continue;
            for(int j=1;j<=k.ip;++j) np[k.i[j]]-=k.in[k.i[j]];
            for(int j=1;j<=k.op;++j) np[k.o[j]]+=k.out[k.o[j]];
            i=0;
            if(++cnt>=lim) break;
        }
        if(cnt>=lim) printf("Case %d: still live after %d transitions\n",++tt,lim);
        else printf("Case %d: dead after %d transitions\n",++tt,cnt);
        printf("Places with tokens:");
        for(int i=1;i<=p;++i) if(np[i]) printf(" %d (%d)",i,np[i]);
        printf("\n\n");
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

分配PGA奖金的问题，题目不难，但是细节比较坑。
要注意数据的读入，排名带T的条件，奖金精度的控制等很多细节。

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
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=145;
int n,pos;
double sum,pri[maxn];
struct player{
    char name[25];
    double prize;
    bool amateur,t;
    int sc[4],pre,tot,dq,rk;
} p[maxn];
bool cmp1(const player &a,const player &b){
    if(a.dq>-3&&b.dq>-3) return a.pre<b.pre;
    return a.dq>b.dq;
}
bool cmp2(const player &a,const player &b){
    if(a.dq!=b.dq) return a.dq>b.dq;
    if(a.tot!=b.tot) return a.tot<b.tot;
    return strcmp(a.name,b.name)<0;
}
void init(){
    memset(p,0,sizeof(p));
    scanf("%lf",&sum);
    for(int i=0;i<70;++i){
        scanf("%lf",&pri[i]);
        pri[i]=pri[i]/100.0*sum;
    }
    scanf("%d\n",&n);
    char s[40];
    for(int i=0;i<n;++i){
        fgets(p[i].name,20,stdin);
        if(strchr(p[i].name,'*')) p[i].amateur=true;
        for(int j=0;j<4;++j){
            if(!scanf("%d",&p[i].sc[j])){p[i].dq=j-4;break;}
            if(j<2) p[i].pre+=p[i].sc[j];
            p[i].tot+=p[i].sc[j];
        }
        fgets(s,40,stdin);
    }
    return;
}
void solve(){
    sort(p,p+n,cmp1);
    pos=0;
    while(pos<min(n,70)&&p[pos].dq>-3) ++pos;
    while(p[pos].dq>-3&&p[pos].pre==p[pos-1].pre) ++pos;
    sort(p,p+pos,cmp2);
    int k=0,rk=0,prk=0;
    while(k<pos){
        if(p[k].dq) break;
        int sta=k,prerk=rk+1,cnt=0;
        bool x=false;
        double sum=0;
        while(!p[sta].dq&&p[k].tot==p[sta].tot){
            if(!p[sta].amateur) sum+=pri[prk+cnt++],x=true;
            ++rk,++sta;
        }
        sum/=cnt;
        for(int i=k;i<=sta;++i){
            p[i].rk=prerk;
            if(prk>69) p[i].amateur=true,p[i].t=false;
            if(!p[i].amateur) p[i].prize=sum,p[i].t=cnt>1;
        }
        k=sta-1,k++;
        prk+=cnt;
    }
}
void print_ans(){
    printf("Player Name          Place     RD1  RD2  RD3  RD4  TOTAL     Money Won\n");
    printf("-----------------------------------------------------------------------\n");
    for(int i=0;i<pos;++i){
        printf("%-21s",p[i].name);
        if(p[i].dq) printf("          ");
        else{
            char t[5];
            sprintf(t,"%d%c",p[i].rk,p[i].t?'T':' ');
            printf("%-10s",t);
        }
        for(int j=-4;j<p[i].dq;++j) printf("%-5d",p[i].sc[4+j]);
        for(int j=p[i].dq;j<0;++j) printf("     ");
        if(p[i].dq) printf("%s","DQ");
        else if(!p[i].amateur) printf("%-10d",p[i].tot);
        else printf("%d",p[i].tot);
        if(p[i].dq||p[i].amateur){printf("\n");continue;}
        printf("$%9.2lf\n",p[i].prize);
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        init();
        solve();
        print_ans();
        if(t) printf("\n");
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出n个点，求有多少组边(a,b)满足|a − b| ≡ 1 mod n。
设P[n]为边的个数，P[3]=4，P[4]=7。此后每项都是前两项的和。因为到10000项数很大，所以要用大整数，Java大整数比C++方便就用了。
原公式：
** P[2n]=1+2n/1!+2n(2n-3)/2!+……+2n(n-1)!/n! **

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.math.*;
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        BigInteger a[]=new BigInteger[10010];
        a[3]=new BigInteger("4"),a[4]=new BigInteger("7");
        for(int i=5;i<10010;++i)
          a[i]=a[i-1].add(a[i-2]);
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()){
            int n=cin.nextInt();
            System.out.println(a[n]);
        }
    }
}

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

发表于 分类于 ， Disqus：

给出一个偶数n（2≤n≤100000）。表示一共有2n个汉堡，其中牛肉汉堡和奶酪汉堡各有n个。有2n个人每个人吃之前投硬币，正面吃牛肉汉堡，反面吃奶酪汉堡。 问最后两个人吃到相同汉堡的概率。
设P[n]为有2n个汉堡时最后两个人吃到不同汉堡的概率。
有：
** P[n]=1/(2(2n-2))C(2n-2,n-1)
直接计算会超时，于是要求递推公式：
P[n+1]/P[n]=(C(2n,n)/(2^n))((2(2n-2))/C(2n-2,n-1))=(2n-1)/(2n) **
把P[1]初始化为1之后用公式计算所有值保存，查找输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
const int maxn=50005;
double a[maxn]={1,1};
int main(){
    for(int i=2;i<maxn;++i)
        a[i]=a[i-1]*(2*i-3)/(2*i-2);
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        printf("%.4lf\n",1-a[n/2]);
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

有a头牛，b辆车，a+b个门，开始任选一个，然后排除掉c个有牛的门，求换门之后获得车的概率。书上解释很详细了。

1
2
3
4
5
6
7
#include<cstdio>
int main(){
    double a,b,c;
    while(~scanf("%lf%lf%lf",&a,&b,&c))
        printf("%.5lf\n",(a*b+b*(b-1))/((a+b)*(a+b-c-1)));
    return 0;
}

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

发表于 分类于 ， Disqus：

给出一个长度为n的01串表示子弹序列，打一枪空的，求下一枪的策略。

书上给出了思路，统计串中00和0的个数a和b，然后求概率a/b和b/n的大小。前者大是SHOOT，后者大是ROTATE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<string>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    string s;
    while(cin>>s){
        int a=0,b=0;
        for(int i=0;i<s.length();++i)
            if(s[i]=='0'){
                ++a;
                if(s[(i+1)%s.length()]=='0') ++b;
            }
        a*=a,b*=s.length();
        if(a==b) cout<<"EQUAL"<<endl;
        else cout<<(a>b?"ROTATE":"SHOOT")<<endl;
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出一个数n，求n个结点的树有多少种结构满足每个结点的子结点数相同。

n结点树，除去根结点，有n-1个结点，根结点的每棵子树需要完全相同，所以根结点的子树个数k，满足(n-1)%k==0。然后就可以递推打表了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
const int maxn=1010,mod=1000000007;
int a[maxn]={0,1},t,n;
void pre(){
    for(int i=1;i<maxn;++i)
        for(int j=1;j<i;++j){
            if((i-1)%j) continue;
            a[i]+=a[j];
            a[i]%=mod;
        }
    return;
}
int main(){
    pre();
    while(cin>>n)
        cout<<"Case "<<++t<<": "<<a[n]<<endl;
    return 0;
}

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