【HNOI模拟By lyp】Day2

1 toad
1.1 题目描述
　　有 n 个石子， A B 两人博弈， A 先手。 A 首先取若干个石子（至少一个，不能取完），然后B和A 再轮流取石子，每次取的石子不能超过 ax^b（ x 表示上次取的石子数， a, b 是两个正整数参数），且至少取一个，无法操作的人输。求 n 满足什么条件时先手必胜。
1.2 输入格式
　　第一行三个正整数 T, a, b ， T 表示数据组数， a, b 意义见题。
　　接下来 T 行，每行一个正整数 n 。
1.3 输出格式
　　对于每个 n ，输出 A 或 B ，表示此时 A 必胜还是 B 必胜。
1.4 样例输入
　　3 1 1
　　1

　　3
1.5 样例输出
　　B

　　A
1.6 数据范围
　　对于 10% 的数据，满足 a = 1, b = 1
　　对于 10% 的数据，满足 a = 2, b = 1
　　对于另外 10% 的数据，满足 1 ≤ n ≤ 10³
　　对于 60% 的数据，满足 1 ≤ n ≤ 10⁸
　　对于 100% 的数据，满足 1 ≤ a, b ≤ 10, 1 ≤ T ≤ 10⁵, 1 ≤ n ≤ 10¹⁸

  1 From r_64
  2 
  3 #include <vector>
  4 #include <list>
  5 #include <map>
  6 #include <set>
  7 #include <queue>
  8 #include <deque>
  9 #include <stack>
 10 #include <bitset>
 11 #include <algorithm>
 12 #include <functional>
 13 #include <numeric>
 14 #include <utility>
 15 #include <sstream>
 16 #include <iostream>
 17 #include <iomanip>
 18 #include <cstdio>
 19 #include <cmath>
 20 #include <cstdlib>
 21 #include <ctime>
 22 #include <cstring>
 23 #include <cassert>
 24 #if __cplusplus > 201103L
 25 #include <initializer_list>
 26 #include <unordered_map>
 27 #include <unordered_set>
 28 #endif
 29 
 30 using namespace std;
 31 
 32 #ifndef ONLINE_JUDGE
 33 #define DEBUG
 34 #endif
 35 
 36 #define oo 0x3F3F3F3F
 37 #ifdef DEBUG
 38 #define cvar(x) cerr << "<" << #x << ": " << x << ">"
 39 #define evar(x) cvar (x) << endl
 40 template<class T> void DISP(const char *s, T x, int n) {cerr << "[" << s << ": "; for (int i = 0; i < n; ++i) cerr << x[i] << " "; cerr << "]" << endl;}
 41 #define disp(x,n) DISP(#x " to " #n, x, n)
 42 #else
 43 #define cvar(...) ({})
 44 #define evar(...) ({})
 45 #define disp(...) ({})
 46 #endif
 47 #define car first
 48 #define cdr second
 49 #define PB push_back
 50 #define SZ(x) (int)((x).size())
 51 #define ALL(x) (x).begin(), (x).end()
 52 #define FOR(i, a, b) for (int _end_ = (b), i = (a); i <= _end_; ++i)
 53 #define ROF(i, a, b) for (int _end_ = (b), i = (a); i >= _end_; --i)
 54 
 55 typedef unsigned int uint;
 56 typedef long long int64;
 57 typedef unsigned long long uint64;
 58 typedef long double real;
 59 
 60 int64 fpm(int64 b, int64 e, int64 m) { int64 t = 1; for (; e; e >>= 1, b = b * b % m) e & 1 ? t = t * b % m : 0; return t; }
 61 template<class T> inline bool chkmin(T &a, T b) {return a > b ? a = b, true : false;}
 62 template<class T> inline bool chkmax(T &a, T b) {return a < b ? a = b, true : false;}
 63 template<class T> inline T sqr(T x) {return x * x;}
 64 template <typename T> T gcd(T x, T y) {for (T t; x; t = x, x = y % x, y = t); return y; }
 65 
 66 template<class edge> struct Graph
 67 {
 68     vector<vector<edge> > adj;
 69     Graph(int n) {adj.clear (); adj.resize (n + 5);}
 70     Graph() {adj.clear (); }
 71     void resize(int n) {adj.resize (n + 5); }
 72     void add(int s, edge e){adj[s].push_back (e);}
 73     void del(int s, edge e) {adj[s].erase (find (iter (adj[s]), e)); }
 74     vector<edge>& operator [](int t) {return adj[t];}
 75 };
 76 
 77 const int maxn = 111000;
 78 const int64 lmt = 1e18;
 79 
 80 struct segment {
 81     int64 L, R, d;
 82 };
 83 
 84 segment H[maxn];
 85 int a, b;
 86 
 87 int64 f(int64 x)
 88 {
 89     double ret = a * pow((double)x, b);
 90     if (ret > lmt) return lmt;
 91     return a * fpm(x, b, lmt);
 92 }
 93 
 94 int main(int argc, char **argv)
 95 {
 96 #ifndef ONLINE_JUDGE
 97     freopen("toad.in" , "r", stdin);
 98     freopen("toad.out", "w", stdout);
 99 #endif
100     ios_base::sync_with_stdio(false);
101 
102     int T;
103 
104     cin >> T >> a >> b;
105 
106     int j = 1, n;
107     int64 Hi = 1, Hj = 1;
108 // H[1] = (segment){1, 1, 1};
109     for (n = 0; ; ) {
110         int64 Ri = Hi + (f(Hj) - Hi) / Hj * Hj;
111         H[++n] = (segment){Hi, Ri, Hj};
112         Hi = Ri + Hj;
113         if (Hi > lmt) break;
114         for (; j <= n && Hj > H[j].R; ++j);
115         if (j <= n) Hj += H[j].d;
116         else Hj = Hi;
117     }
118     cerr << n << endl;
119 
120     for (int64 x; T--; ) {
121         cin >> x;
122         int l = 1, r = n, m;
123         for (; m = (l + r + 1) >> 1, l < r; )
124             H[m].L <= x ? (l = m) : (r = m - 1);
125 // assert(H[m].L <= x && H[m + 1].L > x);
126         bool ans = (x - H[m].L) % H[m].d == 0;
127         cout << (ans ? 'B' : 'A') << endl;
128     }
129     return 0; 
130 }

View Code

2 hasher
2.1 题目描述
　　对于 m, P ，我们定义一个串 S 的 hash 值为：
　　　　hash(S) =∑^|S|−1_i=0S_im_i mod P

　　请构造出两个不同的长为不超过 1500 的 0/1　　串，使得他们的 hash 值相同。
2.2 输入格式
　　一行两个数 m, P 。
2.3 输出格式
　　两行，每行一个串。要求这两个串长度相同。输出任意一组解即可。
2.4 样例输入
　　3 10
2.5 样例输出
　　10000
　　00001
2.6 数据范围
　　对于 20% 的数据，满足 P ≤ 10⁶
　　对于 80% 的数据，满足 P ≤ 10¹⁴
　　对于另外 20% 的数据，满足 P = 2⁶²

  1 #include <vector>
  2 #include <list>
  3 #include <map>
  4 #include <set>
  5 #include <queue>
  6 #include <deque>
  7 #include <stack>
  8 #include <bitset>
  9 #include <algorithm>
 10 #include <functional>
 11 #include <numeric>
 12 #include <utility>
 13 #include <sstream>
 14 #include <iostream>
 15 #include <iomanip>
 16 #include <cstdio>
 17 #include <cmath>
 18 #include <cstdlib>
 19 #include <ctime>
 20 #include <cstring>
 21 #include <cassert>
 22 #if __cplusplus > 201103L
 23 #include <initializer_list>
 24 #include <unordered_map>
 25 #include <unordered_set>
 26 #endif
 27 
 28 using namespace std;
 29 
 30 #ifndef ONLINE_JUDGE
 31 #define DEBUG
 32 #endif
 33 
 34 #define oo 0x3F3F3F3F
 35 #ifdef DEBUG
 36 #define cvar(x) cerr << "<" << #x << ": " << x << ">"
 37 #define evar(x) cvar (x) << endl
 38 template<class T> void DISP(const char *s, T x, int n) {cerr << "[" << s << ": "; for (int i = 0; i < n; ++i) cerr << x[i] << " "; cerr << "]" << endl;}
 39 #define disp(x,n) DISP(#x " to " #n, x, n)
 40 #else
 41 #define cvar(...) ({})
 42 #define evar(...) ({})
 43 #define disp(...) ({})
 44 #endif
 45 #define car first
 46 #define cdr second
 47 #define PB push_back
 48 #define SZ(x) (int)((x).size())
 49 #define ALL(x) (x).begin(), (x).end()
 50 #define FOR(i, a, b) for (int _end_ = (b), i = (a); i <= _end_; ++i)
 51 #define ROF(i, a, b) for (int _end_ = (b), i = (a); i >= _end_; --i)
 52 
 53 typedef unsigned int uint;
 54 typedef long long int64;
 55 typedef unsigned long long uint64;
 56 typedef long double real;
 57 
 58 int64 fpm(int64 b, int64 e, int64 m) { int64 t = 1; for (; e; e >>= 1, b = b * b % m) e & 1 ? t = t * b % m : 0; return t; }
 59 template<class T> inline bool chkmin(T &a, T b) {return a > b ? a = b, true : false;}
 60 template<class T> inline bool chkmax(T &a, T b) {return a < b ? a = b, true : false;}
 61 template<class T> inline T sqr(T x) {return x * x;}
 62 template <typename T> T gcd(T x, T y) {for (T t; x; t = x, x = y % x, y = t); return y; }
 63 
 64 template<class edge> struct Graph
 65 {
 66     vector<vector<edge> > adj;
 67     Graph(int n) {adj.clear (); adj.resize (n + 5);}
 68     Graph() {adj.clear (); }
 69     void resize(int n) {adj.resize (n + 5); }
 70     void add(int s, edge e){adj[s].push_back (e);}
 71     void del(int s, edge e) {adj[s].erase (find (iter (adj[s]), e)); }
 72     vector<edge>& operator [](int t) {return adj[t];}
 73 };
 74 
 75 const int maxn = 1600;
 76 
 77 int lnk[maxn];
 78 struct my_list {
 79     int head, tail;
 80 };
 81 
 82 my_list operator +(const my_list &a, const my_list &b)
 83 {
 84     if (a.head == -1) return b; if (b.head == -1) return a;
 85     lnk[a.tail] = b.head;
 86     return (my_list){a.head, b.tail};
 87 }
 88 
 89 struct node {
 90     int64 h;
 91     my_list x, y;
 92 };
 93 
 94 vector<node> z;
 95 int64 m, mod;
 96 
 97 node operator - (const node &a, const node &b)
 98 {
 99     node c = a;
100     c.h -= b.h;
101     return (node){a.h - b.h, a.x + b.y, a.y + b.x};
102 }
103 
104 bool operator < (const node &a, const node &b)
105 {
106     return a.h < b.h;
107 }
108 
109 int64 mul(int64 x, int64 y)
110 {
111     int64 t = 0;
112     for (; x; x >>= 1, (y <<= 1) %= mod)
113         x & 1 ? (t += y) : 0;
114     return t % mod;
115 }
116 
117 void output(int x)
118 {
119     vector<int> b(1500);
120     for (; x != -1; x = lnk[x]) b[x] = true;
121 // reverse(ALL(b));
122     for (vector <int> :: iterator wyh = b.begin(); wyh != b.end(); wyh++)
123         cout << *wyh;
124     cout << endl;
125 }
126 
127 string inv(string x)
128 {
129     string y;
130     for (int wyh = 0; wyh != x.length(); wyh++)
131         y += (char)((x[wyh]) ^ 1);
132     return y;
133 }
134 
135 int main(int argc, char **argv)
136 {
137     freopen("hasher.in" , "r", stdin);
138     freopen("hasher.out", "w", stdout);
139     ios_base::sync_with_stdio(false);
140     cin >> m >> mod;
141 
142     if ((mod & (mod - 1)) == 0) {
143         if (m & 1) {
144             string s = "0";
145             FOR (i, 1, 10)
146                 s += inv(s);
147             cout << s << endl
148                  << inv(s) << endl;
149         } else {
150             string s = "0";
151             FOR (i, 1, 100) s += '0';
152             cout << s << "1" << endl
153                  << s << "0" << endl;
154         }
155         return 0;
156     }
157 
158     memset(lnk, -1, sizeof(lnk));
159     int64 v = 1;
160     FOR (i, 0, 1500 - 1) {
161         node x;
162         x.h = v;
163         x.x = (my_list){i, i};
164         x.y = (my_list){-1, -1};
165 
166         z.push_back(x);
167         v = mul(v, m);
168     }
169     sort(ALL(z));
170 
171     bool flag = false;
172     for (; ; ) {
173 // cerr << SZ(z) << endl;
174 // assert(~SZ(z) & 1);
175         if (z[0].h == 0) {
176             flag = true;
177             break;
178         }
179         assert(SZ(z) != 1);
180         vector<node> q;
181 
182         int n = SZ(z), m = n - 2;
183         node r = z[m + 1] - z[m];
184         z.pop_back();
185         z.pop_back();
186         z.push_back(r);
187 
188         ROF (i, n - 2, 1) if (z[i] < z[i - 1]) swap(z[i], z[i - 1]);
189     }
190 
191     cerr << z[SZ(z) - 1].h << endl;
192     assert(flag);
193     output(z[0].x.head);
194     output(z[0].y.head);
195     return 0; 
196 }

View Code

3 casket

3.1 题目描述
Magic Land 上的时间过了若干世纪。
现在，人们谈论着一个传说：从前，他们的祖先来到了一个位于东方的岛屿，那里简直就是另
外一个世界。善于分析与构造的 Magic Land 上的人们总是不明白那里的人们是如何不借助精确的
实验与计算驱动和操纵魔法。偶然地，一个魔法使（ Magician）来到了 Magic Land，在临走的时候
留下了一个神奇的盒子，叫做星之器（ Casket of star）。虽然不知道这个盒子是做什么的，但是经过
了大量的实验和计算后，人们已经清楚它的一些事实：
1. 星之器之中有 N × M 个区域，可看作分成 N 行和 M 列的格子，每个区域之中有若干单位的
称为“星”的对象，这个对象的最小单位已经被确定，所以，这个数量总是整数。
2. 魔法使可以驱动星之器中位于同一行或同一列的不相邻（有公共边的区域称为相邻的）两个
区域中各 1 单位的“星”，使得它们分别向中心移动  格。
3. 每一次使用 2 中的方法驱动“星”，将会产生魔力，魔法使会得到这一部分魔力。魔力的量等
于这个两个区域之间所间隔的区域数。
这样，我们可以用 N × M 个数表来表示星之器的状态，比如 N = 2, M = 3 时：
2 0 1
5 1 4
1 2 0
5 1 4
当星之器为上图的状态时，通过操纵第一行的第 1 和 3 个区域中的“星”，变为下图所示的状
态，同时，将产生 1 单位的魔力（因为这两个区域之间恰好隔了 1 个区域）。
在经过了进一步的研究之后，人们知道了这个星之器最初的状态（ Ini）以及最终被他们得到时
的状态（ Fin）。
你希望知道，星之器最多帮助它的拥有者提供了多少的魔力。即：经过一系列上述操作由初态
（ Ini）变为终态（ Fin），至多产生多少魔力。
需要注意的是，显然操作过程中每个区域内“星”的数量不能是负的，即：如果那个区域已经
没有“星”了，当然就不能继续操作了。
3.2 输入格式
　　第一行包含两个正整数 N, M 表示星之器的大小。
　　接下来的 N 行，每行包含 M 个自然数： Inii,j ，描绘了初态（ Ini）。
　　在一个空行后的 N 行，每行包含 M 个自然数： F ini,j ，描绘了终态（ Fin）。

3.3 输出格式
　　输出一个正整数，表示至多产生的魔力。
3.4 样例输入
5 5
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 1 0 1 1
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1
2 0 0 0 1
0 0 2 0 0
0 0 0 0 0
3.5 样例输出
　　7
3.6 数据范围
　　30% 的数据中 N ≤ 2 ，如样例 2；
　　100% 的数据中 1 ≤ N, M ≤ 200, Ini_i,j, F in_i,j≤ 1000 。
　　所有数据保证了至少存在一个操作方法使得星之器由初态变为终态，同时保证了初态与终态不是完全相同的。

 1 #include <cstdio>
 2 using namespace std;
 3 int N,M;
 4 void outLL(long long a,FILE *fout){
 5     if (a>=10)outLL(a/10,fout);
 6     fprintf(fout,"%d",(int)(a%10));
 7 }
 8 int main()
 9 {
10     FILE *fin=fopen("casket.in","r"),*fout=fopen("casket.out","w");
11     fscanf(fin,"%d%d",&N,&M);
12     long long ret=0;
13     for (int i=0;i<N;i++)
14         for (int j=0;j<M;j++){
15             int x;
16             fscanf(fin,"%d",&x);
17             ret+=((long long)x*(long long)i*(long long)i);
18             ret+=((long long)x*(long long)j*(long long)j);
19         }
20     for (int i=0;i<N;i++)
21         for (int j=0;j<M;j++){
22             int x;
23             fscanf(fin,"%d",&x);
24             ret-=((long long)x*(long long)i*(long long)i);
25             ret-=((long long)x*(long long)j*(long long)j);
26         }
27     outLL(ret>>1,fout);
28     fprintf(fout,"\n");
29     fclose(fin);fclose(fout);
30     return 0;
31 }

View Code

以上题解By R_64

这两天get30+30+30+20+100+100

秒客网

【HNOI模拟By lyp】Day2

相关文章