Codeforces eductional round 29

10个月没写题了，菜啊。进行一点恢复性训练好了。

A: 给一个数，可以在填写若干（或者0）个前缀0，问能否变成回文数。

思路是直接删掉后面可能的出现的0再判断回文数就好。

代码实现

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年09月24日 星期日 13时51分06秒
 4File Name :A.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34bool check( int x)
35{
36    vector<int>val;
37    while (x)
38    {
39    int tmp = x;
40    val.push_back(tmp);
41    x/=10;
42    }
43    int siz = val.size();
44    if (siz==1) return true;
45    for ( int i = 0 ; i < siz/2 ; i++)
46    {
47    if (val[i]!=val[siz-1-i]) return false;
48    }
49    return true;
50}
51int main()
52{
53    #ifndef  ONLINE_JUDGE
54    //freopen("./in.txt","r",stdin);
55  #endif
56    int x;
57    cin>>x;
58    while(x==0)
59    {
60        x/=10;
61    }
62    if (check(x)) puts("YES");
63    else puts("NO");
64
65
66  #ifndef ONLINE_JUDGE
67  fclose(stdin);
68  #endif
69    return 0;
70}

B: 2*n个人，每个人的重量为w[i]，要分成n-1组，每组2个人，以及2个单独的人。单独的人的不稳定性为0，每组的不稳定是该组的2个人的重量的差的绝对值。总的不稳定为所有组的不稳定性之和。问可能的最小不稳定性是多少。

思路：由于n才50,100个人，暴力枚举单独的人，复杂度O(n_n_nlg(n))，很稳。注意n给的是组数，所以数组最大值应该为100而不是50.

代码实现

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年09月24日 星期日 13时57分04秒
 4File Name :B.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=107;
35int n;
36int w[N];
37bool single[N];
38void print( vector<int> x)
39{
40    int siz = x.size();
41    for ( int i = 0 ; i < siz ; i++) printf("%d ",x[i]);
42    printf("\n");
43}
44int main()
45{
46    #ifndef  ONLINE_JUDGE
47    freopen("./in.txt","r",stdin);
48  #endif
49    cin>>n;
50    n*=2;
51    ms(single,false);
52    int ret = inf;
53    int sum = 0;
54    for ( int  i = 1 ; i <= n ; i++) scanf("%d",&w[i]);
55    for ( int i = 1 ; i <= n  ; i++)
56    {
57        single[i] = true;
58        for ( int j = i+1 ; j<= n ;j++)
59        {
60        single[j] = true;
61        vector<int>team;
62        for ( int k = 1 ; k <= n ; k++)
63            if (!single[k]) team.push_back(w[k]);
64        sort(team.begin(),team.end());
65//      print(team);
66        //cout<<"team_size:"<<team.size()<<endl;
67        int siz = team.size();
68        sum =  0;
69        for ( int i = 0 ; i < siz ; i+=2)
70        {
71            sum = sum + abs(team[i]-team[i+1]);
72        }
73        ret = min(ret,sum);
74        single[j]=false;
75        }
76        single[i]=false;
77    }
78    printf("%d\n",ret);
79
80
81  #ifndef ONLINE_JUDGE
82  fclose(stdin);
83  #endif
84    return 0;
85}

C: Ali和Bob两个机器人进行一个类似“石头剪子布”的游戏，每次2个机器人同时出{1,2,3}中的一个。 2 beats 1, 3 beats 2 , 1 beats 3. 赢的得1分，输的得0分。数字一样2人都不得分。2个机器人当前回合的策略（也就是出哪个数字）只取决于上一回合2个机器人出的数字。并且规则完全已知，会用2张3*3的表的形式给出。现在要进行k场游戏，问最后的分数是多少。

思路：由于k比较大，所有可能的分数序列(x,y)又非常有限，因此显然是求个循环节搞。

需要注意几点：

代码实现

k的大小太小，比循环节开始的第一个位置还小
K是LL类型，各种和k有关的变量也要记得是LL类型
为了寻找循环节第一次出现的位置，将循环节第二次的开始存了进去，但是在算一个循环节的分数以及其他的时候，记得不要把这个多余的一次算进去。

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2017年09月24日 星期日 14时26分54秒
  4File Name :C.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define PB push_back
 20#define fst first
 21#define sec second
 22#define lson l,m,rt<<1
 23#define rson m+1,r,rt<<1|1
 24#define ms(a,x) memset(a,x,sizeof(a))
 25typedef long long LL;
 26#define pi pair < int ,int >
 27#define MP make_pair
 28
 29using namespace std;
 30const double eps = 1E-8;
 31const int dx4[4]={1,0,0,-1};
 32const int dy4[4]={0,-1,1,0};
 33const int inf = 0x3f3f3f3f;
 34LL k;
 35int x,y;
 36int a[5][5],b[5][5];
 37map< pair<int,int>,bool >mp;
 38vector < pair<int,int> >seq; //记录游戏序列，肯定不会很长。
 39int nx( int x,int y)
 40{
 41    return a[x][y];
 42}
 43int ny ( int x,int y)
 44{
 45    return b[x][y];
 46}
 47LL s_ali( int x,int y)
 48{
 49
 50    if (x==2&&y==1) return 1;
 51    if (x==3&&y==2) return 1;
 52    if (x==1&&y==3) return 1;
 53    return 0;
 54}
 55LL s_bob( int x,int y)
 56{
 57    if (y==2&&x==1) return 1;
 58    if (y==3&&x==2) return 1;
 59    if (y==1&&x==3) return 1;
 60    return 0;
 61}
 62void print( pair<LL,LL>score)
 63{
 64
 65    printf("ali:%lld bob:%lld\n ",score.fst,score.sec);
 66}
 67
 68/* 几种可能错误:
 69 * k的大小不足以出现循环节
 70 * 比分序列的时候为了找循环节开始的位置存了最后一个元素进去（第一次循环的开始），但是后面算的时候要去除
 71 * k的大小是LL,记得各种地方的LL
 72 */
 73pair<LL,LL> solve(int x,int y)
 74{
 75
 76    pair< LL,LL >ret;
 77    ret.fst=ret.sec=0;
 78    seq.clear();
 79    mp.clear();
 80    seq.PB(MP(x,y));
 81    mp[MP(x,y)]=true;
 82    while (1)
 83    {
 84    int xx = nx(x,y);
 85    int yy = ny(x,y);
 86    seq.PB(MP(xx,yy));
 87    if (mp[MP(xx,yy)])
 88    {
 89        break;
 90    }
 91    mp[MP(xx,yy)] = true;
 92    x = xx;
 93    y = yy;
 94    }
 95
 96
 97    int siz = seq.size();
 98 //   for ( int i = 0 ; i < siz ; i++) printf("(%d %d)\n",seq[i].fst,seq[i].sec);
 99    pair<int,int>tar = seq[siz-1];
100    int st,en;
101    st = -1;
102    en = siz-1;
103    for ( int i = 0 ; i < siz ; i++)
104    {
105    pair<int,int> u = seq[i];
106    if (u.fst==tar.fst&&u.sec==tar.sec)
107    {
108        st = i;
109        break;
110    }
111    }
112    //printf("st:%d\n",st);
113    seq.pop_back();
114    siz = seq.size();
115    LL ali_sum,bob_sum;
116    ali_sum=bob_sum=0LL;
117    //有一种可能是k比循环节的开始要小。
118    if (k<st) //没有循环节
119    {
120    for ( int i = 0 ; i < k ; i++)
121    {
122        int x = seq[i].fst;
123        int y = seq[i].sec;
124        ret.fst += s_ali(x,y);
125        ret.sec += s_bob(x,y);
126    }
127//  print(ret);
128    return ret;
129    }
130
131    for ( int i = 0 ; i < st ; i++)
132    {
133    int x = seq[i].fst;
134    int y = seq[i].sec;
135    ali_sum+=s_ali(x,y);
136    bob_sum+=s_bob(x,y);
137    }
138    k-=st; //剩下的是循环节部分.
139    LL circle_len = siz-st;
140    //printf("cir_len:%lld\n",circle_len);
141    LL circle_ali=0;
142    LL circle_bob=0; //一个循环节中的得分.
143    for ( int i = st ; i < siz ; i++)
144    {
145    int x = seq[i].fst;
146    int y = seq[i].sec;
147    circle_ali+=1LL*s_ali(x,y);
148    circle_bob+=1LL*s_bob(x,y);
149    }
150    LL num = k/circle_len;
151    LL mod = k%circle_len;
152    //printf("num:%lld  mod:%lld\n",num,mod);
153    ret.fst = 1LL*ali_sum;
154    ret.sec = 1LL* bob_sum;
155    //print(ret);
156    ret.fst += 1LL*num*circle_ali;
157    ret.sec += 1LL*num*circle_bob;
158   // print(ret);
159    for ( int i = st ; i< st+mod ; i++)
160    {
161    int x = seq[i].fst;
162    int y = seq[i].sec;
163    ret.fst += 1LL*s_ali(x,y);
164    ret.sec += 1LL*s_bob(x,y);
165    }
166
167    return ret;
168
169
170}
171
172int main()
173{
174    #ifndef  ONLINE_JUDGE
175    freopen("./in.txt","r",stdin);
176  #endif
177    cin>>k>>x>>y;
178    for ( int i = 1 ; i <= 3 ; i++)
179        for ( int j = 1 ; j <= 3 ; j++)
180        scanf("%d",&a[i][j]);
181    for ( int i = 1 ; i <= 3 ; i++)
182        for ( int j = 1 ; j <= 3 ; j++)
183        scanf("%d",&b[i][j]);
184    pair<LL,LL> ans = solve(x,y);
185    printf("%lld %lld\n",ans.fst,ans.sec);
186
187
188
189  #ifndef ONLINE_JUDGE
190  fclose(stdin);
191  #endif
192    return 0;
193}

D：有n(2e5)个数的序列，q(2E5)个区间操作，操作有2种类型，一种是将区间[L,R]循环右移一位。另一种是将区间[L,R]中的数整体反转。最后m（100）个询问，每个询问问b[j] (j属于1..m,b[j]属于1..n)位置上的数是多少。

思路：观察发现m比较小，可以暴力。对于所有操作进行完，b[i]位置上的数是多少，因为所有的数只是位置改变，大小没有改变.我们想要还原，到最后的b[i]位置，应该对应的是初始序列中的哪个位置。如果当前位置是pos，那么在进行上一个反转操作之前的位置就是(L+R)-pos, 进行上一个移位操作的位置就是pos-1(注意边界）

代码实现

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年09月25日 星期一 05时19分52秒
 4File Name :D.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=2E5+7;
35int n,q,m;
36int a[N];
37int b[105];
38struct Node
39{
40    int opt,x,y;
41}qu[N];
42/* 思路：
43 * 对于所有操作进行完，b[i]位置上的数是多少，
44 * 因为所有的数只是位置改变，大小没有改变
45 * 我们想要还原，到最后的b[i]位置，应该对应的是初始序列中的哪个位置。
46 * 如果当前位置是pos,那么在进行上一个反转操作之前的位置就是(L+R)-pos,
47 * 进行上一个移位操作的位置就是pos-1(注意边界）
48 */
49int main()
50{
51    #ifndef  ONLINE_JUDGE
52    freopen("./in.txt","r",stdin);
53  #endif
54    cin>>n>>q>>m;
55    for ( int i = 1;  i <= n ; i++) scanf("%d",&a[i]);
56    for ( int i = 1 ; i <= q ; i++) scanf("%d%d%d",&qu[i].opt,&qu[i].x,&qu[i].y);
57    for ( int i = 1 ; i <= m ; i++) scanf("%d",&b[i]);
58
59
60    for ( int i = q ; i >= 1 ; i--)
61    {
62        int opt = qu[i].opt;
63        int L = qu[i].x;
64        int R = qu[i].y;
65        if (opt==1)
66        {
67        for ( int j = 1 ; j <= m ; j++)
68        {
69            if (b[j]>=L&&b[j]<=R)
70            {
71            if (b[j]-1>=L)
72            b[j] = b[j]-1;
73            else b[j] = R;
74            }
75        }
76        }
77        else
78        {
79        for ( int j = 1 ; j <= m  ;j++)
80        {
81            if (b[j]>=L&&b[j]<=R)
82            {
83            b[j] = R+L-b[j];
84            }
85        }
86        }
87    }
88        for ( int i = 1 ; i <= m ; i++)
89        printf("%d ",a[b[i]]);
90
91
92  #ifndef ONLINE_JUDGE
93  fclose(stdin);
94  #endif
95    return 0;
96}

相关文章