Codeforces eductional round 29
10个月没写题了，菜啊。进行一点恢复性训练好了。
A: 给一个数，可以在填写若干（或者0）个前缀0，问能否变成回文数。
思路是直接删掉后面可能的出现的0再判断回文数就好。
/* ***********************************************
Author :111qqz
Created Time :2017年09月24日 星期日 13时51分06秒
File Name :A.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6bool check( int x)
7{
8 vector<int>val;
9 while (x)
10 {
11 int tmp = x;
12 val.push_back(tmp);
13 x/=10;
14 }
15 int siz = val.size();
16 if (siz==1) return true;
17 for ( int i = 0 ; i < siz/2 ; i++)
18 {
19 if (val[i]!=val[siz-1-i]) return false;
20 }
21 return true;
22}
23int main()
24{
25 #ifndef ONLINE_JUDGE
26 //freopen("./in.txt","r",stdin);
27 #endif
28 int x;
29 cin>>x;
30 while(x==0)
31 {
32 x/=10;
33 }
34 if (check(x)) puts("YES");
35 else puts("NO");
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}
B: 2*n个人，每个人的重量为w[i],要分成n-1组，每组2个人，以及2个单独的人。单独的人的不稳定性为0,每组的不稳定是该组的2个人的重量的差的绝对值。总的不稳定为所有组的不稳定性之和。问可能的最小不稳定性是多少。
思路：由于n才50,100个人，暴力枚举单独的人，复杂度O(n_n_nlg(n)),很稳。 注意n给的是组数，所以数组最大值应该为100而不是50.
/* ***********************************************
Author :111qqz
Created Time :2017年09月24日 星期日 13时57分04秒
File Name :B.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=107;
7int n;
8int w[N];
9bool single[N];
10void print( vector<int> x)
11{
12 int siz = x.size();
13 for ( int i = 0 ; i < siz ; i++) printf("%d ",x[i]);
14 printf("\n");
15}
16int main()
17{
18 #ifndef ONLINE_JUDGE
19 freopen("./in.txt","r",stdin);
20 #endif
21 cin>>n;
22 n*=2;
23 ms(single,false);
24 int ret = inf;
25 int sum = 0;
26 for ( int i = 1 ; i <= n ; i++) scanf("%d",&w[i]);
27 for ( int i = 1 ; i <= n ; i++)
28 {
29 single[i] = true;
30 for ( int j = i+1 ; j<= n ;j++)
31 {
32 single[j] = true;
33 vector<int>team;
34 for ( int k = 1 ; k <= n ; k++)
35 if (!single[k]) team.push_back(w[k]);
36 sort(team.begin(),team.end());
37// print(team);
38 //cout<<"team_size:"<<team.size()<<endl;
39 int siz = team.size();
40 sum = 0;
41 for ( int i = 0 ; i < siz ; i+=2)
42 {
43 sum = sum + abs(team[i]-team[i+1]);
44 }
45 ret = min(ret,sum);
46 single[j]=false;
47 }
48 single[i]=false;
49 }
50 printf("%d\n",ret);
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}
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. k的大小太小，比循环节开始的第一个位置还小
2. K是LL类型，各种和k有关的变量也要记得是LL类型
3. 为了寻找循环节第一次出现的位置，将循环节第二次的开始存了进去，但是在算一个循环节的分数以及其他的时候，记得不要把这个多余的一次算进去。
/* ***********************************************
Author :111qqz
Created Time :2017年09月24日 星期日 14时26分54秒
File Name :C.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6LL k;
7int x,y;
8int a[5][5],b[5][5];
9map< pair<int,int>,bool >mp;
10vector < pair<int,int> >seq; //记录游戏序列，肯定不会很长。
11int nx( int x,int y)
12{
13 return a[x][y];
14}
15int ny ( int x,int y)
16{
17 return b[x][y];
18}
19LL s_ali( int x,int y)
20{
1 if (x==2&&y==1) return 1;
2 if (x==3&&y==2) return 1;
3 if (x==1&&y==3) return 1;
4 return 0;
5}
6LL s_bob( int x,int y)
7{
8 if (y==2&&x==1) return 1;
9 if (y==3&&x==2) return 1;
10 if (y==1&&x==3) return 1;
11 return 0;
12}
13void print( pair<LL,LL>score)
14{
printf("ali:%lld bob:%lld\n ",score.fst,score.sec);
}
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 }
1 int siz = seq.size();
2 // for ( int i = 0 ; i < siz ; i++) printf("(%d %d)\n",seq[i].fst,seq[i].sec);
3 pair<int,int>tar = seq[siz-1];
4 int st,en;
5 st = -1;
6 en = siz-1;
7 for ( int i = 0 ; i < siz ; i++)
8 {
9 pair<int,int> u = seq[i];
10 if (u.fst==tar.fst&&u.sec==tar.sec)
11 {
12 st = i;
13 break;
14 }
15 }
16 //printf("st:%d\n",st);
17 seq.pop_back();
18 siz = seq.size();
19 LL ali_sum,bob_sum;
20 ali_sum=bob_sum=0LL;
21 //有一种可能是k比循环节的开始要小。
22 if (k<st) //没有循环节
23 {
24 for ( int i = 0 ; i < k ; i++)
25 {
26 int x = seq[i].fst;
27 int y = seq[i].sec;
28 ret.fst += s_ali(x,y);
29 ret.sec += s_bob(x,y);
30 }
31// print(ret);
32 return ret;
33 }
1 for ( int i = 0 ; i < st ; i++)
2 {
3 int x = seq[i].fst;
4 int y = seq[i].sec;
5 ali_sum+=s_ali(x,y);
6 bob_sum+=s_bob(x,y);
7 }
8 k-=st; //剩下的是循环节部分.
9 LL circle_len = siz-st;
10 //printf("cir_len:%lld\n",circle_len);
11 LL circle_ali=0;
12 LL circle_bob=0; //一个循环节中的得分.
13 for ( int i = st ; i < siz ; i++)
14 {
15 int x = seq[i].fst;
16 int y = seq[i].sec;
17 circle_ali+=1LL*s_ali(x,y);
18 circle_bob+=1LL*s_bob(x,y);
19 }
20 LL num = k/circle_len;
21 LL mod = k%circle_len;
22 //printf("num:%lld mod:%lld\n",num,mod);
23 ret.fst = 1LL*ali_sum;
24 ret.sec = 1LL* bob_sum;
25 //print(ret);
26 ret.fst += 1LL*num*circle_ali;
27 ret.sec += 1LL*num*circle_bob;
28 // print(ret);
29 for ( int i = st ; i< st+mod ; i++)
30 {
31 int x = seq[i].fst;
32 int y = seq[i].sec;
33 ret.fst += 1LL*s_ali(x,y);
34 ret.sec += 1LL*s_bob(x,y);
35 }
return ret;
}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("./in.txt","r",stdin);
5 #endif
6 cin>>k>>x>>y;
7 for ( int i = 1 ; i <= 3 ; i++)
8 for ( int j = 1 ; j <= 3 ; j++)
9 scanf("%d",&a[i][j]);
10 for ( int i = 1 ; i <= 3 ; i++)
11 for ( int j = 1 ; j <= 3 ; j++)
12 scanf("%d",&b[i][j]);
13 pair<LL,LL> ans = solve(x,y);
14 printf("%lld %lld\n",ans.fst,ans.sec);
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}
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(注意边界）
/* ***********************************************
Author :111qqz
Created Time :2017年09月25日 星期一 05时19分52秒
File Name :D.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E5+7;
7int n,q,m;
8int a[N];
9int b[105];
10struct Node
11{
12 int opt,x,y;
13}qu[N];
14/* 思路：
15 * 对于所有操作进行完，b[i]位置上的数是多少，
16 * 因为所有的数只是位置改变，大小没有改变
17 * 我们想要还原，到最后的b[i]位置，应该对应的是初始序列中的哪个位置。
18 * 如果当前位置是pos,那么在进行上一个反转操作之前的位置就是(L+R)-pos,
19 * 进行上一个移位操作的位置就是pos-1(注意边界）
20 */
21int main()
22{
23 #ifndef ONLINE_JUDGE
24 freopen("./in.txt","r",stdin);
25 #endif
26 cin>>n>>q>>m;
27 for ( int i = 1; i <= n ; i++) scanf("%d",&a[i]);
28 for ( int i = 1 ; i <= q ; i++) scanf("%d%d%d",&qu[i].opt,&qu[i].x,&qu[i].y);
29 for ( int i = 1 ; i <= m ; i++) scanf("%d",&b[i]);
1 for ( int i = q ; i >= 1 ; i--)
2 {
3 int opt = qu[i].opt;
4 int L = qu[i].x;
5 int R = qu[i].y;
6 if (opt==1)
7 {
8 for ( int j = 1 ; j <= m ; j++)
9 {
10 if (b[j]>=L&&b[j]<=R)
11 {
12 if (b[j]-1>=L)
13 b[j] = b[j]-1;
14 else b[j] = R;
15 }
16 }
17 }
18 else
19 {
20 for ( int j = 1 ; j <= m ;j++)
21 {
22 if (b[j]>=L&&b[j]<=R)
23 {
24 b[j] = R+L-b[j];
25 }
26 }
27 }
28 }
29 for ( int i = 1 ; i <= m ; i++)
30 printf("%d ",a[b[i]]);
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}