Chengrui's Blog

0%

发表于 分类于 ， ， Disqus：

先手的人优先选取与总和对三求余的数相同的数字，然后每次取数只能取3的倍数。

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<iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int n,t=0;
    cin>>n;
    while(n--){
        string s;
        cin>>s;
        int cnt=0,sum=0,b=0,c=0;
        for(int i=0;i<s.size();i++){
            sum+=s[i]-'0';
            if(s[i]%3==1) b++;
            else if(s[i]%3==2) c++;
            else cnt++;
        }
        cout<<"Case "<<++t<<": ";
        if(sum%3==1) if(b) cnt++;
        if(sum%3==2) if(c) cnt++;
        if(cnt%2) cout<<"S";
        else cout<<"T";
        cout<<endl;
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

求完全平方数的数目，打表解决快点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
bool a[100010];
int main(){
    ios::sync_with_stdio(false);
    for(int i=1;i<317;i++)
        a[i*i]=true;
    int m,n;
    while(cin>>m>>n){
        if(!m&&!n) break;
        int cnt=0;
        for(int i=m;i<=n;i++)
            if(a[i]) cnt++;
        cout<<cnt<<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
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
bool cmp(string s1,string s2){
    return s1+s2>s2+s1;
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n&&n){
        vector<string>a;
        for(string s;n--&&cin>>s;a.push_back(s));
        sort(a.begin(),a.end(),cmp);
        string s;
        for(int i=0;i<a.size();s+=a[i++]);
        cout<<s<<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
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
struct sp{
    double o,r,l1,l2;
    bool operator <(const sp &a)const{
        if(l1==a.l1) return l2<a.l2;
        else return l1<a.l1;
    }
};
int main(){
    int n,l;
    double w;
    while(cin>>n>>l>>w){
        w/=2;
        vector<sp> a;
        sp t;
        while(n--){
            cin>>t.o>>t.r;
            if(t.r>w){
                double k=sqrt(t.r*t.r-w*w);
                t.l1=t.o-k;
                t.l2=t.o+k;
                if(t.l1<0) t.l1=0;
                if(t.l2>l) t.l2=l;
                a.push_back(t);
            }
        }
        sort(a.begin(),a.end());
        bool flag=false;
        int cnt=0,last=0;
        double now=0,maxn=0;
        while(now<l){
            for(int i=last;i<a.size();i++){
                if(a[i].l1<=now){
                    maxn=max(maxn,a[i].l2);
                    last++;
                    flag=true;
                }
                else break;
            }
            if(flag) flag=false;
            else{
                cnt=-1;
                break;
            }
            now=maxn;
            cnt++;
        }
        cout<<cnt<<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
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
bool cmp(int a, int b){
    return abs(a)<abs(b);
}
int main(){
    ios::sync_with_stdio(false);
    int n,t;
    cin>>t;
    while(t--){
        cin>>n;
        vector<int> a,b;
        int k;
        while(n--){
            cin>>k;
            a.push_back(k);
        }
        sort(a.begin(),a.end(),cmp);
        bool flag=false;
        if(a[0]>0) flag=true;
        int cnt=1;
        for(int i=1;i<a.size();i++)
            if((flag&&a[i]<0)||(!flag&&a[i]>0)){
                flag=!flag;
                cnt++;
            }
        cout<<cnt<<endl;
    }
    return 0;
}

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

发表于 分类于 ， ， Disqus：

这么水的道题，居然WA了一次，看样例最后是-1，就用n==-1，做break的判断了，万万没想到，居然最后是个负数就break。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int n=0,a[20]={1},t=0;
    for(int i=1;i<20;i++) a[i]=a[i-1]<<1;
    while(cin>>n){
        if(n<0) break;
        int i;
        for(i=19;i>=0;i--) if(n>=a[i]) break;
        cout<<"Case "<<++t<<": ";
        cout<<(n==a[i]?i:i+1)<<endl;
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

在一个平面上从原点出发，走n步，第i步走的距离为i，每一步都必须转向90度。有k个障碍物，不能穿过。给出步数和障碍物位置，问有多少种可行路径。

输入有负数，但仍然可以使用数组，将g[maxn][maxn]作为原点。(x,y)用g[maxn+x][maxn+y]表示。

进行DFS，注意是否有障碍物，当剩下的步数走不回原点时，回溯。

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxm=25,maxn=250;
const char s[]="ensw";
const int go[2][4]={{1,0,0,-1},{0,1,-1,0}};
int n,cnt,sum[maxm];
bool g[maxn*2][maxn*2],vis[maxn*2][maxn*2];
char s0[maxm];
void read(){
    int k;
    cin>>n>>k;
    while(k--){
        int x,y;
        cin>>x>>y;
        if(abs(x)>=maxn||abs(y)>=maxn) continue;
        g[maxn+x][maxn+y]=true;//g[maxn+x][maxn+y]表示(x,y)。
    }
    return;
}
bool cdt(int x1,int y1,int x2,int y2){//判断是否经过障碍物。
    if(x1==x2){
        int x=x1+maxn,maxy=maxn+max(y1,y2);
        for(int y=maxn+min(y1,y2);y<=maxy;y++){
            if(g[x][y]) return true;
        }
    }
    if(y1==y2){
        int y=y1+maxn,maxx=maxn+max(x1,x2);
        for(int x=maxn+min(x1,x2);x<=maxx;x++){
            if(g[x][y]) return true;
        }
    }
    return false;
}
void dfs(int cur,int last_x,int last_y,int last_dir){
    int dist=abs(last_x)+abs(last_y);
    if(dist>sum[n]-sum[cur]) return;//剩下步数回不到原点，回溯。
    if(cur==n){
        if(dist) return;
        cout<<s0<<endl;
        cnt++;
        return;
    }
    for(int i=0;i<4;i++){
        if(i==last_dir||i==3-last_dir) continue;
        int cur_x=last_x+go[0][i]*(cur+1),cur_y=last_y+go[1][i]*(cur+1);
        if(cdt(last_x,last_y,cur_x,cur_y)) continue;
        if(!vis[maxn+cur_x][maxn+cur_y]){
            s0[cur]=s[i];
            vis[maxn+cur_x][maxn+cur_y]=true;
            dfs(cur+1,cur_x,cur_y,i);
            vis[maxn+cur_x][maxn+cur_y]=false;
            s0[cur]=0;
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    for(int i=1;i<maxm;i++) sum[i]=sum[i-1]+i;
    while(t--){
        cnt=0;
        memset(vis,0,sizeof(vis));
        memset(s0,0,sizeof(s0));
        memset(g,0,sizeof(g));
        read();
        if((n>14&&n<17)||(n>6&&n<9))//n不为这些值时，没有解。
        dfs(0,0,0,-1);
        cout<<"Found "<<cnt<<" golygon(s)."<<endl<<endl;
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

输入n个结点的无向图和一个结点k，按照字典需输出用结点1到k的所有路径。

首先从k开始dfs将所有与之连通的结点标记，若1位被标记则无解。

然后从结点1开始dfs，只对和k连通的结点进行。找到之后输出。

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
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=25;
int a[maxn],des,cnt;
bool g[maxn][maxn],vis[maxn];
void dfs(int v){//判断哪些连通。
    vis[v]=true;
    for(int u=1;u<maxn;u++)
        if(g[u][v]&&!vis[u]) dfs(u);
    return;
}
void search(int cur){
    if(a[cur]==des){
        cnt++;
        for(int i=0;i<=cur;i++){
            if(i) cout<<" ";
            cout<<a[i];
        }
        cout<<endl;
        return;
    }
    for(int i=1;i<maxn;i++){
        if(g[a[cur]][i]&&vis[i]){//只对连通的进行dfs。
            a[cur+1]=i;
            vis[i]=false;
            search(cur+1);
            vis[i]=true;
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    int t=0;
    while(cin>>des){
        cout<<"CASE "<<++t<<":"<<endl;
        memset(a,0,sizeof(a));
        memset(g,0,sizeof(g));
        memset(vis,0,sizeof(vis));
        int u,v;
        while(cin>>u>>v){
            if(!u&&!v) break;
            g[u][v]=g[v][u]=true;
        }
        cnt=0;
        a[0]=1;
        vis[1]=false;
        dfs(des);
        if(!vis[1]) goto END;//无法到达，输出0。
        search(0);
    END:
        cout<<"There are "<<cnt<<" routes from the firestation to streetcorner "<<des<<"."<<endl;
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

输出由前L个字母组成的第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
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=85;
int n,l,cnt,S[maxn];
int dfs(int cur){
    if(cnt++==n){//打印解。
        for(int i=0;i<cur;i++){
            if(i&&i%4==0&&i%64!=0) cout<<" ";
            if(i&&i%64==0) cout<<endl;
            cout<<(char)('A'+S[i]);
        }
        cout<<endl;
        cout<<cur<<endl;
        return 0;
    }
    for(int i=0;i<l;i++){
        S[cur]=i;
        bool ok=true;
        for(int j=1;j*2<=cur+1;j++){
            bool equal=true;
            for(int k=0;k<j;k++)
                if(S[cur-k]!=S[cur-k-j]){
                    equal=false;
                    break;
                }
            if(equal){//相同，不是困难串。
                ok=false;
                break;
            }
        }
        if(ok) if(!dfs(cur+1)) return 0;
    }
    return 1;
}
int main(){
    while(cin>>n>>l){
        if(!n&&!l) break;
        cnt=0;
        memset(S,0,sizeof(S));
        dfs(0);
    }
    return 0;
}

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