【190727】计蒜客 North America Qualifier 2018

2019-07-30

目录

B题

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<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
int lcm(int a,int b)
{
    int res = a*b/gcd(a,b);
    return res;
}
int main()
{

    int p,q,s;
    scanf(" %d %d %d",&p,&q,&s);
    if(lcm(p,q)<=s)
        printf("yes\n");
    else
        printf("no\n");
    return 0;
}

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
void solveE(string ss)
{
    string res="";
    char last=' ',cur=' ';
    int cnt = 1;
    for(int i=0;i<ss.length();i++)
    {
        cur = ss[i];
        if(last==' ')
        {
            res += cur;
            last = cur;
            continue;
        }
        else if(last==cur)
        {
            cnt++;
            continue;

        }
        else //last !=cur
        {

            res+=char(cnt+48);
            cnt = 1;
            res+=cur;
            last = cur;
        }
    }
    res+=char(cnt+48);
    cout<<res<<endl;
}
void solveD(string ss)
{
    string res="";
    char last=' ',cur=' ';
    int cnt;
    for(int i=0;i<ss.length();i++)
    {
        cur = ss[i];
        if(last==' ')
        {
            res += cur;
            last = cur;
        }
        else if(isdigit(cur))
        {
            cnt = int(cur-49);//因为已经算了一个了
            while(cnt--)
                res+=last;
            continue;
        }
        else
        {
            res += cur;
            last = cur;
            continue;
        }
    }
    cout<<res<<endl;

}
int main()
{
    char flag;//E or D
    string ss;
    cin>>flag>>ss;
    if(flag=='E')
    {
        solveE(ss);
    }
    else if(flag=='D')
    {
        solveD(ss);
    }
    return 0;
}

A题

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<bits/stdc++.h>
using namespace std;
const int maxn = 100+20;
int ans[maxn][10][10];
int n;
bool  check(int a,int b,int rowa,int rowb,int num)//要检测其他的数据能否让其他的行先赢,哪怕是同时赢也可以字典序最小
{
    set<int> temp;
    for(int j=1;j<=5;j++)
    {
        if(ans[a][rowa][j]!=num)
            temp.insert(ans[a][rowa][j]);
        if(ans[b][rowb][j]!=num)
            temp.insert(ans[b][rowb][j]);
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=5;i++)
        {
            bool flag = true;
            for(int j=1;j<=5;j++)
            {
                if(temp.count(ans[k][i][j]))
                {
                    continue;
                }
                else
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
                return false;//no tie
            else
                continue;
        }
    return true;
}
int main()
{
    cin>>n;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=5;i++)
            for(int j=1;j<=5;j++)
                cin>>ans[k][i][j];
    for(int a=1;a<=n;a++)
        for(int b=a+1;b<=n;b++)
        {
            int num;
            for(int i=1;i<=5;i++)
                for(int j=1;j<=5;j++)
                {
                    num = ans[a][i][j];
                    for(int row=1;row<=5;row++)
                        for(int col=1;col<=5;col++)
                            if(ans[b][row][col]==num)
                            {
                                if(check(a,b,i,row,num))
                                {
                                    cout<<a<<" "<<b<<endl;
                                    return 0;
                                }
                            }
                }

        }
    cout<<"no ties"<<endl;
    return 0;
}

G题

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
//维护RR之间的逆序区间，逆序输出
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+20;
int n;
char ss[maxn];
int maxx = 1,num=1;//R自己本来算一个
inline void out(int x) {
    if(x>9) out(x/10);
    putchar(x%10+'0');
}
int main()
{
    scanf("%d",&n);
    scanf("%s",ss);

    for(int i=0;i<n;i++)
    {
        if(ss[i]=='R')
        {
            for(int k=1;k<=num;k++)
            {
                out(maxx-k+1);
                putchar('\n');
            }
            maxx++;
            num=1;//维护从上一次的最左边的L然后到这一次的R的数量
        }
        else
        {
            num++;
            maxx++;
        }
        if(i==n-2)//总共就这么多个
        {
            for(int k=1;k<=num;k++)
            {
                out(maxx-k+1);
                putchar('\n');
            }
        }
    }
    return 0;
}

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
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
//对于每一行我需要知道每一个数据被填入的位置
//遍历每一行
//对于每一列我需要知道这一列中已经出现了哪些值,还可以填入什么
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100+10;
bool visc[maxn][maxn];//表示第j列k是否出现过
bool visr[maxn];//当前行是否出现过
bool vis[maxn];//匹配，表示当前数据是否在当前列被匹配过
int res[maxn][maxn];
int pos[maxn];//每一行出现的位置,用于调整
int n,k;
//首先要检查一遍
bool dfs(int row,int col)//匹配每一行
{
    for(int ans = 1;ans<=n;ans++)
    {
        if(!vis[ans]&&!visc[col][ans])
        {
            vis[ans] = true;//匹配数,并不是行数据，而是预备数据
            if(!visr[ans]||dfs(row,pos[ans]))
               {
                   res[row][col] = ans;
                   pos[ans] = col;
                   visr[ans] =true;
                   return true;
               }
        }

    }
    return false;

}
void solve()
{
    for(int row = k+1;row<=n;row++)
    {
        memset(pos,-1,sizeof(pos));
        memset(visr,false,sizeof(visr));
        for(int col = 1;col<=n;col++)
        {
            memset(vis,false,sizeof(vis));//关键就是这里，在这一次匹配的时候记录已经尝试过的方案
            dfs(row,col);
        }
        for(int col=1;col<=n;col++)
        {
            visc[col][res[row][col]] = true;//第col列这个数是否出现过
        }
    }
    for(int i = 1;i<=n;i++)
       {
           for(int j=1;j<=n;j++)
            {
                if(j!=n)
                printf("%d ",res[i][j]);
                else
                printf("%d\n",res[i][j]);
            }
       }
}
int main()
{

    memset(visc,false,sizeof(visc));
    scanf("%d%d",&n,&k);
    int flag =  false;//确定是否有解
    for(int i=1;i<=k;i++)
    {
        memset(pos,-1,sizeof(pos));
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&res[i][j]);
            if(visc[j][res[i][j]]==true)
                flag = true;
            else
                visc[j][res[i][j]] = true;
            if(pos[res[i][j]]!=-1)
                flag = true;
            else
                pos[res[i][j]] = j;
        }
    }
    if(flag == true)
    {
        printf("no\n");
    }
    else
    {
        printf("yes\n");
        solve();
    }
    return 0;
}

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
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
//每次行动之前都清空数组然后，只要能计算下一次的位置就好了,注意会有新的车子出来
//每一次移动前都把下一次的障碍区设置好了，然后看是否会撞到，无非就是更新障碍区
//每次维护每一行最左边的那一个的位置就好了
//只要超过了间隔就更新这一行最左边的那个，最上面是从左往右
//从右往左更新最右边的那个
//点灯的时候记住边界
//说白了就是起始点变化的等差数列
#include<bits/stdc++.h>
using namespace std;//第一行从左往右
const int maxl = 10+10;
const int maxw = 20+10;
 int l,w;//行数，列数
 struct point
{
    int x,y;
};

struct Lane
{

    int start_point;
    int interval;
    int speed;
}lane[maxl];
bool g[maxl][maxw];
int pos[maxl];//每条跑道最边上的那个车子在哪
void gen_map()//从上到下更新map
{
    for(int i=0;i<l;i++)
    {
        int start_point , speed , interval;
        start_point = pos[i];
        speed = lane[i].speed;
        interval= lane[i].interval;
        int cur_point,last_point;
        int cnt ;//用来遍历和计时
        if(i%2==0)//偶数从左到右,反向点灯
        {

            start_point += speed;//得到当前位置
            while(start_point>=interval)//维护最小值,
            {
                pos[i] = start_point - interval;
                start_point = pos[i];
//                cout<<i<<"p\t"<<pos[i]<<endl;
            }
            pos[i] = start_point;
//            cout<<i<<"p\t"<<pos[i]<<endl;
            last_point = cur_point = start_point;
            while(last_point-speed < w )
            {
//                cout<<i<<"l\t"<<last_point<<endl;
                cnt = speed;
                if(!(cur_point>=0&&cur_point<w))//防止speed为0的情况
                {
                }
                else
                    g[i][cur_point] = true;
                while(cnt)
                {
                    if(!(cur_point>=0&&cur_point<w))
                        {
                            --cur_point;
                            --cnt;
                            continue;
                        }
                    g[i][cur_point] = true;
                    --cur_point;
                    --cnt;
                }
                last_point+=interval;
                cur_point=last_point;
            }
        }
        else
        {
            start_point-=speed;
            while(w-start_point-1>=interval)//出现新的车子了
            {
                pos[i] = start_point+interval;
                start_point = pos[i];
//                cout<<i<<"\t"<<pos[i]<<endl;
            }
            pos[i] = start_point;//维护最小值
//            cout<<i<<"\t"<<pos[i]<<endl;
            last_point = cur_point = start_point;
            while(last_point+speed>=0)
            {
                if(!(cur_point>=0&&cur_point<w))//防止speed为0的情况
                {
                }
                else
                    g[i][cur_point] = true;

                cnt = speed;
                while(cnt)
                {
                    if(!(cur_point>=0&&cur_point<w))
                    {
                        --cnt;
                        ++cur_point;
                        continue;
                    }
                    g[i][cur_point] = true;
                    ++cur_point;
                    --cnt;
                }
                last_point-=interval;
                cur_point =last_point;
            }
        }
    }

}
point get_cur_pos(char dir,point last_pos)
{
    point cur_pos;
    if(dir == 'U')
    {
        cur_pos.x = last_pos.x+1 ;
        cur_pos.y = last_pos.y ;
    }
    else if(dir == 'D')
    {
        cur_pos.x =last_pos.x-1 ;
        cur_pos.y = last_pos.y;
    }
    else if(dir == 'L')
    {
        cur_pos.x =last_pos.x ;
        cur_pos.y = last_pos.y-1;
    }
    else if(dir == 'R')
    {
        cur_pos.x =last_pos.x ;
        cur_pos.y = last_pos.y+1;
    }
    return cur_pos;

}

int main()
{
    int o,i,s;//每一行o,i,s表示第一辆车子的位置，车子之间的间隔，车子的速度
    int p;//表示青蛙开始的位置
    string ss;//表示青蛙的移动轨迹
    bool hit=false;
    cin>>l>>w;//奇数向右偶数向左
    for(int it=0;it<l;it++)
    {
        cin>>o>>i>>s;
        lane[it].interval = i;
        lane[it].start_point = o;
        lane[it].speed = s;
        if(it&1)
        {
            pos[it] = w-o-1;//偏移量

        }
        else
        {
            pos[it] = o;
        }
    }
    point frag;
    cin>>p>>ss;
    frag.x = -1;
    frag.y = p;
    for(int i=0;i<ss.length();i++)
    {
        char cur_dir = ss[i];//当前方向,更新地图
        memset(g,false,sizeof(g));
        gen_map();
        frag = get_cur_pos(cur_dir,frag);
        if(frag.x<0||frag.x>=l||frag.y<0||frag.y>=w)
            continue;
        else if(g[l-1-frag.x][frag.y])
        {
            hit = true;
            break;
        }
        else
        {
            continue;
        }
    }
    if(frag.x!=l)
        hit = true;
    if(hit)
        cout<<"squish"<<endl;
    else
        cout<<"safe"<<endl;
    return 0;
}

J题

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
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int a[5][5];
int point[2];
int d1[6][2]={-2,0,2,0,0,-2,0,2,2,2,-2,-2};
int d2[6][2]={-1,0,1,0,0,-1,0,1,1,1,-1,-1};
bool f(int x, int y)
{
    return x>=0 && x<5 && y>=0 && y<5 && x>=y;
}

int dfs(int flag)
{
    int endd=1;
    int maxx;
    if(flag==0) maxx=-INF;
    else maxx=INF;
    for(int x=0; x<5; ++x)
    {
        for(int y=0; y<=x; ++y)
        {
            if(a[x][y]) continue;
            for(int k=0; k<6; ++k)
            {
                int x1=x+d1[k][0];
                int y1=y+d1[k][1];
                int x2=x+d2[k][0];
                int y2=y+d2[k][1];
                if(f(x1,y1)&&f(x2,y2)&&a[x1][y1]&&a[x2][y2])
                {
                    endd=0;
                    int p1=a[x1][y1];
                    int p2=a[x2][y2];
                    a[x][y]=p1;
                    a[x1][y1]=0;
                    a[x2][y2]=0;
                    point[flag]+=p1*p2;
                    int t=dfs(1-flag);
                    if(flag==0) maxx=max(maxx,t);
                    else maxx=min(maxx,t);
                    a[x][y]=0;
                    a[x1][y1]=p1;
                    a[x2][y2]=p2;
                    point[flag]-=p1*p2;
                }
            }
        }
    }
    if (endd)
        return point[0]-point[1];
    else
        return maxx;
}

int main()
{
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j <= i; ++j)
            scanf("%d", &a[i][j]);
    printf("%d\n",dfs(0));
    return 0;
}
© 2019 blog - Powered by Hexo - Theme Chan