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)又非常有限，因此显然是求个循环节搞。
需要注意几点：
1 1. k的大小太小，比循环节开始的第一个位置还小
2 2. K是LL类型，各种和k有关的变量也要记得是LL类型
3 3. 为了寻找循环节第一次出现的位置，将循环节第二次的开始存了进去，但是在算一个循环节的分数以及其他的时候，记得不要把这个多余的一次算进去。
4
5
6
7
8/* ***********************************************
9Author :111qqz
10Created Time :2017年09月24日 星期日 14时26分54秒
11File Name :C.cpp
12************************************************ */
13
14#include <cstdio>
15#include <cstring>
16#include <iostream>
17#include <algorithm>
18#include <vector>
19#include <queue>
20#include <set>
21#include <map>
22#include <string>
23#include <cmath>
24#include <cstdlib>
25#include <ctime>
26#define PB push_back
27#define fst first
28#define sec second
29#define lson l,m,rt<<1
30#define rson m+1,r,rt<<1|1
31#define ms(a,x) memset(a,x,sizeof(a))
32typedef long long LL;
33#define pi pair < int ,int >
34#define MP make_pair
35
36using namespace std;
37const double eps = 1E-8;
38const int dx4[4]={1,0,0,-1};
39const int dy4[4]={0,-1,1,0};
40const int inf = 0x3f3f3f3f;
41LL k;
42int x,y;
43int a[5][5],b[5][5];
44map< pair<int,int>,bool >mp;
45vector < pair<int,int> >seq; //记录游戏序列，肯定不会很长。
46int nx( int x,int y)
47{
48 return a[x][y];
49}
50int ny ( int x,int y)
51{
52 return b[x][y];
53}
54LL s_ali( int x,int y)
55{
56
57 if (x==2&&y==1) return 1;
58 if (x==3&&y==2) return 1;
59 if (x==1&&y==3) return 1;
60 return 0;
61}
62LL s_bob( int x,int y)
63{
64 if (y==2&&x==1) return 1;
65 if (y==3&&x==2) return 1;
66 if (y==1&&x==3) return 1;
67 return 0;
68}
69void print( pair<LL,LL>score)
70{
71
72 printf("ali:%lld bob:%lld\n ",score.fst,score.sec);
73}
1/* 几种可能错误:
2 * k的大小不足以出现循环节
3 * 比分序列的时候为了找循环节开始的位置存了最后一个元素进去（第一次循环的开始），但是后面算的时候要去除
4 * k的大小是LL,记得各种地方的LL
5 */
6pair<LL,LL> solve(int x,int y)
7{
1 pair< LL,LL >ret;
2 ret.fst=ret.sec=0;
3 seq.clear();
4 mp.clear();
5 seq.PB(MP(x,y));
6 mp[MP(x,y)]=true;
7 while (1)
8 {
9 int xx = nx(x,y);
10 int yy = ny(x,y);
11 seq.PB(MP(xx,yy));
12 if (mp[MP(xx,yy)])
13 {
14 break;
15 }
16 mp[MP(xx,yy)] = true;
17 x = xx;
18 y = yy;
19 }
20
21
22 int siz = seq.size();
23 // for ( int i = 0 ; i < siz ; i++) printf("(%d %d)\n",seq[i].fst,seq[i].sec);
24 pair<int,int>tar = seq[siz-1];
25 int st,en;
26 st = -1;
27 en = siz-1;
28 for ( int i = 0 ; i < siz ; i++)
29 {
30 pair<int,int> u = seq[i];
31 if (u.fst==tar.fst&&u.sec==tar.sec)
32 {
33 st = i;
34 break;
35 }
36 }
37 //printf("st:%d\n",st);
38 seq.pop_back();
39 siz = seq.size();
40 LL ali_sum,bob_sum;
41 ali_sum=bob_sum=0LL;
42 //有一种可能是k比循环节的开始要小。
43 if (k<st) //没有循环节
44 {
45 for ( int i = 0 ; i < k ; i++)
46 {
47 int x = seq[i].fst;
48 int y = seq[i].sec;
49 ret.fst += s_ali(x,y);
50 ret.sec += s_bob(x,y);
51 }
52// print(ret);
53 return ret;
54 }
55
56 for ( int i = 0 ; i < st ; i++)
57 {
58 int x = seq[i].fst;
59 int y = seq[i].sec;
60 ali_sum+=s_ali(x,y);
61 bob_sum+=s_bob(x,y);
62 }
63 k-=st; //剩下的是循环节部分.
64 LL circle_len = siz-st;
65 //printf("cir_len:%lld\n",circle_len);
66 LL circle_ali=0;
67 LL circle_bob=0; //一个循环节中的得分.
68 for ( int i = st ; i < siz ; i++)
69 {
70 int x = seq[i].fst;
71 int y = seq[i].sec;
72 circle_ali+=1LL*s_ali(x,y);
73 circle_bob+=1LL*s_bob(x,y);
74 }
75 LL num = k/circle_len;
76 LL mod = k%circle_len;
77 //printf("num:%lld mod:%lld\n",num,mod);
78 ret.fst = 1LL*ali_sum;
79 ret.sec = 1LL* bob_sum;
80 //print(ret);
81 ret.fst += 1LL*num*circle_ali;
82 ret.sec += 1LL*num*circle_bob;
83 // print(ret);
84 for ( int i = st ; i< st+mod ; i++)
85 {
86 int x = seq[i].fst;
87 int y = seq[i].sec;
88 ret.fst += 1LL*s_ali(x,y);
89 ret.sec += 1LL*s_bob(x,y);
90 }
91
92 return ret;
93
94
95}
96
97int main()
98{
99 #ifndef ONLINE_JUDGE
100 freopen("./in.txt","r",stdin);
101 #endif
102 cin>>k>>x>>y;
103 for ( int i = 1 ; i <= 3 ; i++)
104 for ( int j = 1 ; j <= 3 ; j++)
105 scanf("%d",&a[i][j]);
106 for ( int i = 1 ; i <= 3 ; i++)
107 for ( int j = 1 ; j <= 3 ; j++)
108 scanf("%d",&b[i][j]);
109 pair<LL,LL> ans = solve(x,y);
110 printf("%lld %lld\n",ans.fst,ans.sec);
111
112
113
114 #ifndef ONLINE_JUDGE
115 fclose(stdin);
116 #endif
117 return 0;
118}
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}