jy

jy

关注
发信
关注(28)粉丝(399)

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

题目名称正确答案 序列问题长途旅行
英文名称answersequencetravel
输入文件名answer.insequence.intravel.in
输出文件名answer.outsequence.outtravel.out
时间限制1s1s1s
空间限制  256M256M256M
测试点数目202010
测试点分值5510
是否有部分分无无无
题目类型传统传统传统
是否有 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 ;

 }
05-11 13:49
Powered by LMLPHP ©2024 jy 0.063268