全国信息学奥林匹克联赛 ( NOIP2014) 复赛 模拟题 Day1 长乐一中

题目名称	正确答案	序列问题	长途旅行
英文名称	answer	sequence	travel
输入文件名	answer.in	sequence.in	travel.in
输出文件名	answer.out	sequence.out	travel.out
时间限制	1s	1s	1s
空间限制	256M	256M	256M
测试点数目	20	20	10
测试点分值	5	5	10
是否有部分分	无	无	无
题目类型	传统	传统	传统
是否有 SPJ	无	无	无

正确答案 全国信息学奥林匹克联赛( ( NOIP2014) 复 赛 模拟题 Day1 长乐一中

【题目描述】
小 H 与小 Y 刚刚参加完 UOIP 外卡组的初赛，就迫不及待的跑出考场对答案。
“吔，我的答案和你都不一样！”，小 Y 说道，”我们去找神犇们问答案吧”。
外卡组试卷*有 m 道判断题，小 H 与小 Y 一共从其他 n 个神犇那问了答案。之后又
从小 G 那里得知， 这 n 个神犇中有 p 个考了满分， q 个考了零分， 其他神犇不为满分或零分。
这可让小 Y 与小 H 犯了难。你能帮助他们还原出标准答案吗？如有多解则输出字典序最小
的那个。无解输出-1。
【 输入格式】
第一行四个整数 n, m, p, q，意义如上描述。
接下来 n 行，每一行 m 个字符’N’或’Y’，表示这题这个神犇的答案。
【 输出格式】
仅一行，一个长度为 m 的字符串或是-1。
【 样例输入】
2 2 2 0
YY
YY
【 样例输出】
YY
【 数据范围】
30% : n <= 100.
60% : n <= 5000 , m <= 100.
100% : 1 <= n <= 30000 , 1 <= m <= 500. 0 <= p , q 且 p + q <= n.

T1：
30%: O(n ^ 2 * m)暴力判断。
100%: 很显然答案的可能性最多只有 n 种，所以我们将所有人的答案按字典序排序后枚举
将每个人的答案作为正确答案来进行判断。 由于是判断题， 若当前人的答案为正确答
案则零分者的答案也就确定了， 那么只需统计出这两种答案的人数判断是否满足题意
即可。这一步使用字符串哈希即可解决。
另外要注意 p = 0 和 p = q = 0 的情况。

 #include <algorithm>
 #include <iostream>
 #include <cstring>
 #include <cstdio>
 #include <cmath>
 using namespace std;

 const int N = 3e4 + , M = 5e2 + , sed = , SED = , mod = , MOD = ;
 int n, m, p, q, ans, hash[N], HASH[N];
 int top, info[mod], nxt[N * ], fet[N * ], cnt[N * ];
 struct node {
     char s[M];
     inline bool operator < (const node &b) const {
         return strcmp(s, b.s) < ;
     }
 } a[N];

 inline void Insert(const int &x, const int &y) {
     for (int k = info[x]; k; k = nxt[k])
         if (fet[k] == y) {
             ++cnt[k]; return ;
         }
     nxt[++top] = info[x]; info[x] = top;
     fet[top] = y; cnt[top] = ;
     return ;
 }

 inline int Query(const int &x, const int &y) {
     for (int k = info[x]; k; k = nxt[k])
         if (fet[k] == y) return cnt[k];
     return ;
 }

 inline void Solve1() {
     int tmp, TMP; ans = -;
     for (int i = ; i < n; ++i) {
         tmp = TMP = ;
         for (int j = ; j < m; ++j) {
             tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;
             TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;
         }
         hash[i] = tmp, HASH[i] = TMP;
         Insert(tmp, TMP);
     }
     for (int i = ; i < n; ++i)
         if (Query(hash[i], HASH[i]) == p) {
             tmp = TMP = ;
             for (int j = ; j < m; ++j) {
                 tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;
                 TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;
             }
             if (Query(tmp, TMP) == q) {
                 ans = i; break;
             }
         }
     if (ans != -) printf("%s\n", a[ans].s);
     else     puts("-1");
     return ;
 }

 char cur[M];
 inline void Solve2() {
     int tmp, TMP; ans = -;
     for (int i = ; i < n; ++i) {
         tmp = TMP = ;
         for (int j = ; j < m; ++j) {
             tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;
             TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;
         }
         hash[i] = tmp, HASH[i] = TMP;
         Insert(tmp, TMP);
     }
     for (int i = n - ; i >= ; --i)
         if (Query(hash[i], HASH[i]) == q) {
             tmp = TMP = ;
             for (int j = ; j < m; ++j) {
                 tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;
                 TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;
             }
             if (Query(tmp, TMP) == p) {
                 ans = i; break;
             }
         }
     if (ans != -) {
         for (int i = ; i < m; ++i)
             cur[i] = a[ans].s[i] == 'N' ? 'Y' : 'N';
         printf("%s\n", cur);
     }
     else     puts("-1");
     return ;
 }

 void Solve3() {
     int tmp, TMP;
     for (int i = ; i < n; ++i) {
         tmp = TMP = ;
         for (int j = ; j < m; ++j) {
             tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;
             TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;
         }
         Insert(tmp, TMP);
         tmp = TMP = ;
         for (int j = ; j < m; ++j) {
             tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;
             TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;
         }
         Insert(tmp, TMP);
     }
     bool flag = true;
     for (int i = ; i < m; ++i) cur[i] = 'N';
     do {
         tmp = TMP = ;
         for (int j = ; j < m; ++j) {
             tmp = (tmp * sed + (cur[j] == 'N')) % mod;
             TMP = (TMP * SED + (cur[j] == 'N')) % MOD;
         }
         if (Query(tmp, TMP) == ) {
             flag = true; break;
         }
         flag = false;
         for (int j = m - ; j >= ; --j)
             if (cur[j] == 'Y') cur[j] = 'N';
             else {
                 cur[j] = 'Y'; flag = true; break;
             }
     } while (flag);
     if (flag) printf("%s\n", cur);
     else     puts("-1");
     return ;
 }

 int main() {
     freopen("answer.in", "r", stdin);
     freopen("answer.out", "w", stdout);
     scanf("%d%d%d%d", &n, &m, &p, &q);
     for (int i = ; i < n; ++i) scanf("%s", a[i].s);
     sort(a, a + n);
     if (p) Solve1();
     else if (q) Solve2();
     else     Solve3();
     fclose(stdin); fclose(stdout);
     return ;
 }

2. 序列问题
【 题目描述】
小 H 是个善于思考的学生，她正在思考一个有关序列的问题。
她的面前浮现出了一个长度为 n 的序列{ai}，她想找出两个非空的集合 S、T。
这两个集合要满足以下的条件：
1. 两个集合中的元素都为整数，且都在 [1, n] 里，即 Si，Ti ∈ [1, n]。
2. 对于集合 S 中任意一个元素 x，集合 T 中任意一个元素 y，满足 x < y。
3. 对于大小分别为 p, q 的集合 S 与 T，满足
a[s1] xor a[s2] xor a[s3] ... xor a[sp] = a[t1] and a[t2] and a[t3] ... and a[tq].
小 H 想知道一共有多少对这样的集合(S,T)，你能帮助她吗？
【输入格式】
第一行，一个整数 n
第二行，n 个整数，代表 ai。
【 输出格式】
仅一行，表示最后的答案。
【 样例输入】
4
1 2 3 3
【 样例输出】
4
【 样例解释】
S = {1,2}, T = {3}， 1 ^ 2 = 3 = 3 (^为异或)
S = {1,2}, T = {4}, 1 ^ 2 = 3 = 3
S = {1,2}， T = {3，4} 1 ^ 2 = 3 & 3 = 3 （&为与运算）
S = {3}， T = {4} 3 = 3 = 3
【 数据范围】
30%: 1 <= n <= 10
60%: 1 <= n <= 100
100%: 1 <= n <= 1000, 0 <= ai < 1024

T2:
30%：枚举每个数所在的集合或者不选，然后判定即可。复杂度 O(n*3^n)。
60%： Dp， 两个数相等就相当于两个数的 xor 为 0。 设 f[i][j][k=0..2]代表 处理到第 I 个数，
如果 k = 1 代表 and 值为 j,如果 k = 2 代表 xor 值为 j,如果 k = 0 则代表一个元素都没
取。所以很容易得到方程：
f[i][j][0] = f[i + 1][j][0]
f[i][j & ai][1] = f[i + 1][j][1] + f[i + 1][j][0] + f[i + 1][j & ai][1]
f[i][j ^ ai][2] = f[i + 1][j][1] + f[i + 1][j][2] + f[i + 1][j ^ ai][2];
最后 f[1][0][2]就是答案, 复杂度为 O(n * 1024 * 3)
DP 还可以分开用 f[i][j]和 g[i][j]表示前 i 个 xor 值为 j，后 i 个 and 值为 j 的方案数，
随后枚举分界点 k 来求总方案数。复杂度 O(n * 1024 * 3)。
100%：满分数据需要高精，答案位数较大，需要进行压位来防止 TLE，因为不知道答案的
位数究竟多大，压位后高精数组仍需要开的较大一些，所以原 DP 的数组滚动即可。

 #include <algorithm>
 #include <iostream>
 #include <cstring>
 #include <cstdio>
 #include <cmath>
 using namespace std;

 typedef long long ll;
 const int N = , M = , W = 1e9;
 int n, cur, nxt, va, vx, p[N];

 struct huge_int {
     int len, a[];
     huge_int(): len() { memset(a, , sizeof(a)); }

     inline void operator += (const huge_int &b) {
         b.len > len ? len = b.len : ;
         for (int i = ; i <= len; ++i) {
             a[i] += b.a[i];
             if (a[i] >= W) ++a[i + ], a[i] -= W;
         }
         if (a[len + ]) ++len;
         return ;
     }

     inline void print() {
         printf("%d", a[len]);
         for (int i = len - ; i; --i)
             printf("%09d", a[i]);
         puts(""); return ;
     }
 } f[][M][];

 char ch;
 int read() {
     while (ch = getchar(), ch < '' || ch > '');
     int res = ch - ;
     while (ch = getchar(), ch >= '' && ch <= '') res = res *  + ch - ;
     return res;
 }

 int main() {
     freopen("sequence.in", "r", stdin);
     freopen("sequence.out", "w", stdout);
     n = read();
     for (int i = n; i; --i) p[i] = read();
     f[][][].a[] = ;
     for (int i = ; i < n; ++i) {
         nxt = cur ^ ;
         for (int j = ; j < M; ++j)
             for (int k = ; k <= ; ++k)
                 f[nxt][j][k] = f[cur][j][k];
         for (int j = ; j < M; ++j) {
             va = p[i + ] & j, vx = p[i + ] ^ j;
             f[nxt][va][] += f[cur][j][]; f[nxt][va][] += f[cur][j][];
             f[nxt][vx][] += f[cur][j][]; f[nxt][vx][] += f[cur][j][];
         }
         cur ^= ;
     }
     f[cur][][].print();
     fclose(stdin); fclose(stdout);
     return ;
 }

3. 长途旅行
【 题目描述】
JY 是一个爱旅游的探险家，也是一名强迫症患者。现在 JY 想要在 C 国进行一次长途
旅行，C 国拥有 n 个城市(编号为 0,1,2...,n - 1)，城市之间有 m 条道路，可能某个城市到自己
有一条道路，也有可能两个城市之间有多条道路，通过每条道路都要花费一些时间。JY 从
0 号城市开始出发，目的地为 n – 1 号城市。由于 JY 想要好好参观一下 C 国，所以 JY 想要
旅行恰好 T 小时。为了让自己的旅行更有意思，JY 决定不在任何一个时刻停留(走一条到城
市自己的路并不算停留)。JY 想知道是否能够花恰好 T 小时到达 n – 1 号城市（每个城市可
经过多次） 。现在这个问题交给了你。
若可以恰好到达输出“Possible”否则输出“Impossible” 。(不含引号)。
【 输入格式】
第一行一个正整数 Case，表示数据组数。
每组数据第一行 3 个整数，分别为 n, m, T。
接下来 m 行，每行 3 个整数 x, y, z,代表城市 x 和城市 y 之间有一条耗时为 z 的双向边。
【 输出格式】
对于每组数据输出”Possible”或者”Impossible”.
【 样例输入】
2
3 3 11
0 2 7
0 1 6
1 2 5
2 1 10000
1 0 1
【 样例输出】
Possible
Impossible
【 样例解释】
第一组：0 -> 1 -> 2 :11
第二组：显然偶数时间都是不可能的。
【 数据范围】
30%: T <= 10000
另有 30%: n <= 5 , m <= 10.
100%: 2 <= n <= 50 , 1 <= m <= 100 , 1 <= z <= 10000 , 1 <= T <= 10^18 , Case <= 5.

T3：
30%：
当 T<= 10000 的时候，可以设 vis[i][j] 代表到达第 i 个点时间为 j 是否合法。 这样是
O(T*m)，可以拿到小数据。
另外的那 30%：各种奇怪的骗分方法。选手自行考虑。
100%：
当 T 很大的时候，我们考虑 如果 0 -> x -> n - 1 路径时间为 T，且 从 x 出发有一个时
间为 d 的环，则 一定存在一个 K 满足 K + p*d = T（至少 T 满足条件） ，这样我们就能绕着
环走 p 次就能构成一条时间为 T 的路径。
显然要求的路径一定经过 0，而且在合法情况下从 0 号点出发一定存在一条边，否则 0
号点和 n - 1 号就是不联通的。 随便取一条边时间为 d, 则能构成从 0 号点出发的一个时间为
2d 的环。这样原题就化为最短路问题了，dis[i][j] 代表到达 i 号点，时间为 j + p * 2d，最小
的 j+p*2d，
最后判断 dis[n -1][T % 2d] 是否小于等于 T 即可。
实际上就是在 30%的基础上缩减状态。
时间复杂度为 O(m*d)。

 #include <algorithm>
 #include <iostream>
 #include <cstring>
 #include <cstdio>
 #include <cmath>
 #include <queue>
 using namespace std;

 #define X first
 #define Y second
 #define mk make_pair
 typedef pair<int, int> DI;
 typedef long long ll;
 const int N = , M = , K = ;
 int n, m, len, u, v, c, Case;
 int tot, info[N], nxt[M], go[M], val[M];
 ll T, INF, dist[N][K];
 queue<DI> que;
 bool vis[N][K];

 inline void SetE(int x, int y, int z) {
     nxt[++tot] = info[x]; info[x] = tot; go[tot] = y; val[tot] = z;
     nxt[++tot] = info[y]; info[y] = tot; go[tot] = x; val[tot] = z;
     return ;
 }

 inline void Spfa() {
     int x, y, p, q; ll v;
     memset(dist, , sizeof(dist));
     dist[][] = ; que.push(mk(, ));
     while (!que.empty()) {
         DI top = que.front(); que.pop();
         x = top.X, p = top.Y; vis[x][p] = false;
         for (int k = info[x]; y = go[k], k; k = nxt[k]) {
             v = dist[x][p] + val[k]; q = v % len;
             if (dist[y][q] > v) {
                 dist[y][q] = v;
                 if (!vis[y][q]) {
                     vis[y][q] = true;
                     que.push(mk(y, q));
                 }
             }
         }
     }
     return ;
 }

 char ch;
 inline int read() {
     while (ch = getchar(), ch < '' || ch > '');
     int res = ch - ;
     while (ch = getchar(), ch >= '' && ch <= '') res = res *  + ch - ;
     return res;
 }
 inline ll Read() {
     while (ch = getchar(), ch < '' || ch > '');
     ll res = ch - ;
     while (ch = getchar(), ch >= '' && ch <= '') res = res *  + ch - ;
     return res;
 }

 int main() {
     freopen("travel.in", "r", stdin);
     freopen("travel.out", "w", stdout);
     Case = read();
     while (Case--) {
         n = read(), m = read(); T = Read();
         memset(info, , sizeof(info)); tot = ;
         for (int i = ; i <= m; ++i) {
             u = read(), v = read(); c = read();
             SetE(u, v, c);
         }
         if (!info[]) puts("Impossible");
         else {
             len = ;
             for (int k = info[]; k; k = nxt[k])
                 if (val[k] < len) len = val[k];
             len *= ; Spfa();
             if (dist[n - ][T % len] <= T) puts("Possible");
             else     puts("Impossible");
         }
     }
     fclose(stdin); fclose(stdout);
     return ;
 }