Chengrui's Blog

0%

发表于 分类于 ， Disqus：

在一个棋盘上移动骰子，求最少次数使骰子移动一圈回到原点。移动有限制，顶面数字与目标格数字相同或目标格为-1时才可以移动。

输入棋盘和骰子的初始位置和初始状态（用顶面和正面表示）。

感觉与UVa816特别相似。因为有骰子朝向问题，所以还要注意顶面和正面的数字，所以要用四维数组vis记录当前状态是否出现过。

思路出来了代码实现就很简单了，从起点开始BFS，vis数组在判断是否出现的同时还要记录经过的步数，用state数组记录上一步的状态。

当再次遇到起点坐标时，打印解。

骰子的旋转移动事先打表。

PS：开始的时候CE了，cmath里有y0、y1的定义。std里有node关键字。

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<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=12;
const int ro1[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//骰子的移动打表。
const int ro2[7][7]={
    {0,0,0,0,0,0,0},
    {0,0,4,2,5,3,0},
    {0,3,0,6,1,0,4},
    {0,5,1,0,0,6,2},
    {0,2,6,0,0,1,5},
    {0,4,0,1,6,0,3},
    {0,0,3,5,2,4,0}
};
char s[25];
int r,c,x_sta,y_sta,u,f,g[maxn][maxn];
int vis[maxn][maxn][7][7];
struct Node{
    int x,y,u,f;
    Node(int x=0,int y=0,int u=0,int f=0):x(x),y(y),u(u),f(f){}
};
Node state[maxn][maxn][7][7];
bool read(){
    if(scanf("%s",s)==EOF||!strcmp(s,"END")) return false;
    memset(g,0,sizeof(g));
    scanf("%d%d%d%d%d%d",&r,&c,&x_sta,&y_sta,&u,&f);
    for(int i=1;i<=r;++i)
        for(int j=1;j<=c;++j)
            scanf("%d",&g[i][j]);
    return true;
}
Node rotate(Node pre,int dis){
    Node cur=pre;
    cur.x+=ro1[dis][0],cur.y+=ro1[dis][1];
    if(dis==0){cur.f=7-cur.f;swap(cur.u,cur.f);}
    if(dis==1){cur.u=7-cur.u;swap(cur.u,cur.f);}
    if(dis==2){cur.u=ro2[cur.u][cur.f];}
    if(dis==3){cur.u=7-ro2[cur.u][cur.f];}
    return cur;
}
bool match(Node cur,int i){
    if(g[cur.x+ro1[i][0]][cur.y+ro1[i][1]]==-1) return true;
    if(g[cur.x+ro1[i][0]][cur.y+ro1[i][1]]==cur.u) return true;
    return false;
}
bool in(Node cur,int i){
    return cur.x+ro1[i][0]>0&&cur.x+ro1[i][0]<=r&&cur.y+ro1[i][1]>0&&cur.y+ro1[i][1]<=c;
}
void print_ans(Node a){
    stack<Node> Nodes;//倒着找到的解，所以要压入栈，然后倒着输出。
    Nodes.push(Node(x_sta,y_sta,u,f));
    while(1){
        Nodes.push(a);
        if(!vis[a.x][a.y][a.u][a.f]) break;
        a=state[a.x][a.y][a.u][a.f];
    }
    int cnt=0;
    while(1){
        if(cnt%9==0) printf("\n  ");
        printf("(%d,%d)",Nodes.top().x,Nodes.top().y);
        Nodes.pop();
        if(!Nodes.empty()) printf(",");//格式控制。
        else{
            printf("\n");
            break;
        }
        cnt++;
    }
    return;
}
void solve(){
    printf("%s",s);
    memset(vis,-1,sizeof(vis));
    memset(state,0,sizeof(state));
    queue<Node> q;
    Node sta(x_sta,y_sta,u,f);
    vis[x_sta][y_sta][u][f]=0;
    q.push(sta);
    while(!q.empty()){
        Node a=q.front();
        q.pop();
        for(int i=0;i<4;++i){
            if(!match(a,i)||!in(a,i)) continue;
            Node b=rotate(a,i);
            if(b.x==x_sta&&b.y==y_sta){//找到就打印解。
                print_ans(a);
                return;
            }
            if(vis[b.x][b.y][b.u][b.f]<0){
                vis[b.x][b.y][b.u][b.f]=vis[a.x][a.y][a.u][a.f]+1;//记录步数。
                state[b.x][b.y][b.u][b.f]=a;//记录上一步的位置和骰子状态。
                q.push(b);
            }
        }
    }
    printf("\n  No Solution Possible\n");
    return;
}
int main(){
    while(read()){
        solve();
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出六种象形文字。然后给出十六进制的数表，求对应数表的01图所含有的字母，获得字母按字典序打印。

书上给了很巧妙的思路：每个字母中白色块的数目不同，依此判断字母是什么。

先把数表转化为二进制。然后进行一次Floodfill把所有的象形文字独立出来。要注意先加一圈“空气”使得无关的0连通。

然后对每个独立的象形文字进行Floodfill，求有几个白色连通块。查找出对应的字母。该字母数量+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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int maxn=210;
const int a[6]={1,5,3,2,4,0};//打表储存字母和字典序的顺序。
const char b[7]="WAKJSD";
int h,w,cnt[6],ct;
bool vis[maxn][maxn],g[maxn][maxn];
map<char,int> hex;
void pre(){//预处理十六进制转化数组。
    for(int i=0;i<10;++i) hex['0'+i]=i;
    for(int i=0;i<6;++i) hex['a'+i]=10+i;
    return;
}
bool read(){
    scanf("%d%d",&h,&w);
    if(!h&&!w) return false;
    memset(g,0,sizeof(g));
    for(int i=1;i<=h;++i){
        getchar();
        int pos=1;
        for(int j=1;j<=w;++j){
            int c=hex[getchar()];//读入的同时进行处理。
            for(int k=3;k>=0;--k)
                g[i][pos++]=c&(1<<k);
        }
    }
    w*=4;
    return true;
}
bool in(int x,int y){
    return x>=0&&x<=h+1&&y>=0&&y<=w+1;
}
void dfs(int x,int y,bool k){//Floodfill。
    if(!in(x,y)||vis[x][y]) return;
    if(!k&&g[x][y]) return;
    if(k&&!g[x][y]){
        ++ct;
        dfs(x,y,0);
        return;
    }
    vis[x][y]=true;
    dfs(x,y+1,k);
    dfs(x+1,y,k);
    dfs(x,y-1,k);
    dfs(x-1,y,k);
    return;
}
void solve(){
    memset(cnt,0,sizeof(cnt));
    memset(vis,0,sizeof(vis));
    dfs(0,0,0);
    for(int i=0;i<=h;++i){
        for(int j=0;j<=w;++j){
            if(g[i][j]&&!vis[i][j]){
                ct=0;
                dfs(i,j,1);
                ++cnt[ct];
            }
        }
    }
    for(int i=0;i<6;i++)
        while(cnt[a[i]]--) putchar(b[a[i]]);
    printf("\n");
    return;
}
int main(){
    pre();
    int t=0;
    while(read()){
        printf("Case %d: ",++t);
        solve();
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

多米诺骨牌每骨牌上有两个数，给出7*8的数表，问如何用骨牌布满，输出所有可能解。

一共只有28个骨牌，一开始就感觉是暴力的问题。

首先预处理骨牌，因为每个骨牌都可以用唯一的数对表示，所以用二维数组g来储存对应骨牌的编号。

然后从左上角开始进行枚举，vis储存状态。当存在骨牌冲突时回溯，当右下角也铺上骨牌时输出当前解。

PS：貌似lay和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
78
79
80
81
82
83
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10;
int lo[maxn][maxn],vis[maxn][maxn],g[maxn][maxn],cnt;
bool used[30];
void prepare(){//处理骨牌。
    for(int i=1,j=0,k=0;i<=28;++i,++k){
        if(k>6) ++j,k=j;
        g[j][k]=g[k][j]=i;
    }
    return;
}
bool read(){
    for(int i=0;i<7;++i)
        for(int j=0;j<8;++j)
            if(scanf("%d",&lo[i][j])==EOF) return false;
    return true;
}
void dfs(int);
void lay(int x,int y,bool right,int cur){//铺骨牌，变量right控制向下铺还是向右铺。
    int x1=x,y1=y;
    if(right) ++y1;
    else ++x1;
    int a=lo[x][y],b=lo[x1][y1];
    if(g[a][b]&&!used[g[a][b]]){
        used[g[a][b]]=true;
        vis[x][y]=vis[x1][y1]=g[a][b];
        dfs(cur+1);//<span style="font-family: Arial, Helvetica, sans-serif;">两个函数互相递归调用。</span>
        used[g[a][b]]=false;
        vis[x][y]=vis[x1][y1]=-1;
    }
    return;
}
void dfs(int cur){
    if(cur==28){//铺满打印解。
        for(int i=0;i<7;++i){
            for(int j=0;j<8;++j)
                printf("%4d",vis[i][j]);
            printf("\n");
        }
        printf("\n");
        ++cnt;
        return;
    }
    int x=7,y=8;
    for(int i=0;i<7;++i){
        bool flag=true;
        for(int j=0;j<8;++j)
            if(vis[i][j]==-1){
                flag=false;
                x=i,y=j;
                break;
            }
        if(!flag) break;
    }
    if(y+1<8&&vis[x][y+1]==-1) lay(x,y,true,cur);//两个函数互相递归调用。
    if(x+1<7&&vis[x+1][y]==-1) lay(x,y,false,cur);
    return;
}
int solve(){
    cnt=0;
    memset(vis,-1,sizeof(vis));
    memset(used,0,sizeof(used));
    dfs(0);
    return cnt;
}
int main(){
    int t=0;
    prepare();
    while(read()){
        if(t) printf("\n\n\n");
        printf("Layout #%d:\n\n",++t);
        for(int i=0;i<7;++i){
            for(int j=0;j<8;++j)
                printf("%4d",lo[i][j]);
            printf("\n");
        }
        printf("\nMaps resulting from layout #%d are:\n\n",t);
        printf("There are %d solution(s) for layout #%d.\n",solve(),t);
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出环的数量n，之后再给出环的连接状态，问最少打开几个环再重新连接就能使所有环连成一个链条。

环的数量很少，用二进制枚举子集，然后逐个判断是否可以连成一条链，如果连成，用解开的数目维护最小值。

判断能否连成一条链，首先要使解开后的链条没有三个连在一起的结点，然后链条不能形成环。

判断形成环时，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
#include<cstdio>
#include<cstring>
const int INF=1<<30;
const int maxn=20;
int n,best;
bool g[maxn][maxn],vis[maxn];
bool read(){
    if(scanf("%d",&n)==EOF||!n) return false;
    memset(g,0,sizeof(g));
    int u,v;
    while(~scanf("%d%d",&u,&v)&&!(u==-1&&v==-1))
        g[u-1][v-1]=g[v-1][u-1]=true;
    return true;
}
bool node(int s){//判断是否形成结点。
    for(int i=0;i<n;++i){
        if(s&(1<<i)) continue;
        int num=0;
        for(int j=0;j<n;++j)
            if(!(s&(1<<j))&&g[i][j]) ++num;
        if(num>2) return false;
    }
    return true;
}
bool dfs(int s,int cur,int pre)
{
    vis[cur]=true;
    bool ok=true;
    for(int i=0;i<n;++i){
        if(!(s&(1<<i))&&g[cur][i]){
            if(!vis[i]){
                if(!dfs(s,i,cur))
                    ok=false;
            }
            else if(i!=pre) return false;//已经来过，但不是上一个，形成环。
        }
    }
    if(!ok) return false;
    return true;
}
bool ring(int s,int num){//判断有无环。
    int cnt=0;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;++i){
        if(s&(1<<i)) continue;
        if(vis[i]) continue;
        ++cnt;
        if(!dfs(s,i,-1)) return false;
    }
    if(cnt>num+1) return false;
    return true;
}
int solve(){
    int best=INF,s=1<<n;//二进制枚举子集，0表示不解开，1表示解开。
    for(int i=0;i<s;++i){
        int cur=0;
        for(int j=0;j<n;++j)
            if(i&(1<<j)) ++cur;
        if(cur>=best) continue;//统计解开的个数，若大于之前最大值，则continue。
        if(node(i)&&ring(i,cur))
            best=best>cur?cur:best;
    }
    return best;
}
int main(){
    int t=0;
    while(read())
        printf("Set %d: Minimum links to open is %d\n",++t,solve());
    return 0;
}

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

发表于 分类于 ， Disqus：

给出结点和结点之间的连接，求带宽最小的排列。带宽就是在排列中每一个点到其他点最大距离的最大值。

数据量很小，可以枚举全排列，使用algorithm中的next_permutation函数。

对于每个排列求带宽比较，有一个点的带宽大于当前最小值，就剪掉。

这道题不用函数，手动构造能剪更多枝，可以更加省时，但代码可能会长点。

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
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
using namespace std;
const int maxn=30;
int a[maxn],b[maxn],n,best,k[10]={1};
bool g[maxn][maxn],vis[maxn];
bool read(){
    char c=0,d=0;
    best=1<<30,n=0;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(g,0,sizeof(g));
    memset(vis,0,sizeof(vis));
    while(d!='\n'){
        c=getchar();
        if(c=='#') return false;
        if(!vis[c-'A']) ++n,vis[c-'A']=true;
        getchar();
        while(isupper(d=getchar())){
            if(!vis[d-'A']) ++n,vis[d-'A']=true;
            g[c-'A'][d-'A']=true;
            g[d-'A'][c-'A']=true;
        }
    }
    return true;
}
int get_bw(){
    int bw=0;
    for(int i=0;i<n;++i){
        if(!vis[a[i]]) continue;
        for(int j=0;j<n;++j){
            if(!vis[a[j]]) continue;
            if(g[a[i]][a[j]])
                bw=max(abs(i-j),bw);
            if(bw>best) return bw;//有大于当前最小值的就回溯。
        }
    }
    return bw;
}
void solve(){
    int sum=k[n];
    for(int i=0,j=0;i<n;++i){
        while(!vis[j]) ++j;
        a[i]=j++;
    }
    for(int i=0;i<sum;++i){
        int t=get_bw();
        if(best>t){
            for(int j=0;j<n;++j)
                b[j]=a[j];
            best=t;
        }
        next_permutation(a,a+n);//枚举全排列。
    }
    return;
}
int main(){
    for(int i=1;i<10;++i) k[i]=i*k[i-1];
    while(read()){
        solve();
        for(int i=0;i<n;++i)
            printf("%c ",b[i]+'A');
        printf("-> %d\n",best);
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

ACM对抗赛决赛题，在比赛时没出，后来找学长给讲了，利用相同值一起加减少运算次数，就过了。

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;
long long H(long long n){
    long long res=0,cur,last=n;
    for(long long i=1;i<=n;i++){
        cur=n/i;
        res+=cur;
        if(cur<last){
            res+=(n/cur-i)*cur;
            i=n/cur;
            last=cur;
        }
    }
    return res;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        cout<<H(n)<<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<string>
#include<vector>
#include<sstream>
using namespace std;
vector<int> a,b;
bool cmp(int x,int y){
    return x>y;
}
void reverse(int n){
    for(int i=0;i<(n+1)/2;++i) swap(a[i],a[n-1-i]);
    return;
}
bool read(){
    string s;
    a.clear(),b.clear();
    getline(cin,s);
    stringstream ss(s);
    int k,first=1;
    while(ss>>k){
        if(first) first=0;
        else cout<<" ";
        cout<<k;
        a.push_back(k);
    }
    if(!a.size()) return false;
    cout<<endl;
    b=a;
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    while(read()){
        int n=(int)a.size();
        sort(b.begin(),b.end(),cmp);
        for(int i=0;i<n;++i){
            int j=0;
            for(j=0;j<n;++j)
                if(a[j]==b[i]) break;
            if(j==n-1-i) continue;
            else if(j){
                cout<<n-j<<" "<<i+1<<" ";
                reverse(j+1);
                reverse(n-i);
            }
            else{
                cout<<i+1<<" ";
                reverse(n-i);
            }
        }
        cout<<"0"<<endl;
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

求给出的数最近的两个素数的差，若给的数是素数，输出0。

在青岛理工大学邀请赛时，做过这道题，当时打表打在循环内了，超时了。这个问题一定要注意。

再说这个求素数，之前OJ作业上做到过筛选求素数的题，后来百度过高速求素数的方法，XA2的Xcode 5亿素数5秒左右，具体代码如下。

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
#include<iostream>
using namespace std;
const unsigned maxn=1300010;
int p[maxn],n;
bool np[maxn]={true,true};
int main(){
    ios::sync_with_stdio(false);
    for(int i=2;i<maxn;i++){
        if(!np[i])
            p[n++]=i;
        for(int j=0;j<n&&i*p[j]<maxn;j++){
            np[i*p[j]]=1;
            if(!(i%p[j])) break;
        }
    }
    while(cin>>n&&n){
        if(!np[n]){
            cout<<"0"<<endl;
            continue;
        }
        int i=n,j=n;
        while(np[i]) i--;
        while(np[j]) j++;
        cout<<j-i<<endl;
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出由"/"、""、"."组成的矩形，求围出的多边形的面积。

之前在青岛理工大学邀请赛做过，对于"/"和""每个都是0.5，对于"."只有在多边形内部的为1。

用q来标记是否在多边形内部，在读入的同时完成统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
int m,n;
int main(){
    while(scanf("%d%d",&m,&n)!=EOF){
        int sum=0;
        getchar();
        for(int i=0;i<m;++i){
            bool q=false;
            for(int j=0;j<n;++j){
                char c=getchar();
                if(c=='/'||c=='\\') ++sum,q=!q;
                if(c=='.'&&q) sum+=2;
            }
            getchar();
        }
        printf("%d\n",sum/2);
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

输入字母的莫尔斯编码、字典，之后输入编码过的单词，要求输出对应的单词。

使用map保存莫尔斯编码，读入字典后，将每个单词的编码保存在vector中并排序。然后对于每个输入莫尔斯编码串，与字典比对进行输出。

紫书书上第四章的题，学过STL之后做更加简单。

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
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
using namespace std;
string s;
map<char,string> decode;
struct m_word{
    string s,s0;
    m_word(string s="",string s0=""):s(s),s0(s0){}
    bool operator < (const m_word &x) const {
        return s0.length()==x.s0.length()?s0<x.s0:s0.length()<x.s0.length();
    }
};
vector<m_word> dict;
string code(){//编码输入单词。
    string s0;
    for(int i=0;i<s.length();++i){
        s0+=decode[s[i]];
    }
    return s0;
}
int main(){
    ios::sync_with_stdio(false);
    while(1){//构造map。
        char c;
        cin>>c;
        if(c=='*') break;
        cin>>s;
        cin.get();
        decode[c]=s;
    }
    while(1){//构造字典。
        cin>>s;
        if(s=="*") break;
        dict.push_back(m_word(s,code()));
    }
    sort(dict.begin(),dict.end());
    while(1){
        cin>>s;
        if(s=="*") break;
        int t=0,cnt;
        while(1){//对比直至找到对应单词。
            cnt=0;
            for(int i=0;i<dict.size();++i){
                if(dict[i].s0==s.substr(0,s.size()-t)){
                    if(!cnt) cout<<dict[i].s;
                    cnt++;
                }
                else if(dict[i].s0.substr(0,dict[i].s0.size()-t)==s){
                    if(!cnt) cout<<dict[i].s;
                    cnt++;
                }
            }
            if(cnt) break;
            ++t;
        }
        if(t) cout<<"?";
        else if(cnt!=1&&!t) cout<<"!";
        cout<<endl;
    }
    return 0;
}

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