当前位置： 首页 > news >正文

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

news 来源：原创 2024/4/28 18:00:19
题目名称正确答案 序列问题长途旅行
英文名称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 的情况。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <cmath>
  6 using namespace std;
  7 
  8 const int N = 3e4 + 2, M = 5e2 + 2, sed = 31, SED = 131, mod = 70177, MOD = 92311;
  9 int n, m, p, q, ans, hash[N], HASH[N];
 10 int top, info[mod], nxt[N * 2], fet[N * 2], cnt[N * 2];
 11 struct node {
 12     char s[M];
 13     inline bool operator < (const node &b) const {
 14         return strcmp(s, b.s) < 0;
 15     }
 16 } a[N];
 17 
 18 inline void Insert(const int &x, const int &y) {
 19     for (int k = info[x]; k; k = nxt[k])
 20         if (fet[k] == y) {
 21             ++cnt[k]; return ;
 22         }
 23     nxt[++top] = info[x]; info[x] = top;
 24     fet[top] = y; cnt[top] = 1;
 25     return ;
 26 }
 27 
 28 inline int Query(const int &x, const int &y) {
 29     for (int k = info[x]; k; k = nxt[k])
 30         if (fet[k] == y) return cnt[k];
 31     return 0;
 32 }
 33 
 34 inline void Solve1() {
 35     int tmp, TMP; ans = -1;
 36     for (int i = 0; i < n; ++i) {
 37         tmp = TMP = 0;
 38         for (int j = 0; j < m; ++j) {
 39             tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;
 40             TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;
 41         }
 42         hash[i] = tmp, HASH[i] = TMP;
 43         Insert(tmp, TMP);
 44     }
 45     for (int i = 0; i < n; ++i)
 46         if (Query(hash[i], HASH[i]) == p) {
 47             tmp = TMP = 0;
 48             for (int j = 0; j < m; ++j) {
 49                 tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;
 50                 TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;
 51             }
 52             if (Query(tmp, TMP) == q) {
 53                 ans = i; break;
 54             }
 55         }
 56     if (ans != -1) printf("%s\n", a[ans].s);
 57     else     puts("-1");
 58     return ;
 59 }
 60 
 61 char cur[M];
 62 inline void Solve2() {
 63     int tmp, TMP; ans = -1;
 64     for (int i = 0; i < n; ++i) {
 65         tmp = TMP = 0;
 66         for (int j = 0; j < m; ++j) {
 67             tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;
 68             TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;
 69         }
 70         hash[i] = tmp, HASH[i] = TMP;
 71         Insert(tmp, TMP);
 72     }
 73     for (int i = n - 1; i >= 0; --i)
 74         if (Query(hash[i], HASH[i]) == q) {
 75             tmp = TMP = 0;
 76             for (int j = 0; j < m; ++j) {
 77                 tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;
 78                 TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;
 79             }
 80             if (Query(tmp, TMP) == p) {
 81                 ans = i; break;
 82             }
 83         }
 84     if (ans != -1) {
 85         for (int i = 0; i < m; ++i)
 86             cur[i] = a[ans].s[i] == 'N' ? 'Y' : 'N';
 87         printf("%s\n", cur);
 88     }
 89     else     puts("-1");
 90     return ;
 91 }
 92 
 93 void Solve3() {
 94     int tmp, TMP;
 95     for (int i = 0; i < n; ++i) {
 96         tmp = TMP = 0;
 97         for (int j = 0; j < m; ++j) {
 98             tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;
 99             TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;
100         }
101         Insert(tmp, TMP);
102         tmp = TMP = 0;
103         for (int j = 0; j < m; ++j) {
104             tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;
105             TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;
106         }
107         Insert(tmp, TMP);
108     }
109     bool flag = true;
110     for (int i = 0; i < m; ++i) cur[i] = 'N';
111     do {
112         tmp = TMP = 0;
113         for (int j = 0; j < m; ++j) {
114             tmp = (tmp * sed + (cur[j] == 'N')) % mod;
115             TMP = (TMP * SED + (cur[j] == 'N')) % MOD;
116         }
117         if (Query(tmp, TMP) == 0) {
118             flag = true; break;
119         }
120         flag = false;
121         for (int j = m - 1; j >= 0; --j)
122             if (cur[j] == 'Y') cur[j] = 'N';
123             else {
124                 cur[j] = 'Y'; flag = true; break;
125             }
126     } while (flag);
127     if (flag) printf("%s\n", cur);
128     else     puts("-1");
129     return ;
130 }
131 
132 int main() {
133     freopen("answer.in", "r", stdin);
134     freopen("answer.out", "w", stdout);
135     scanf("%d%d%d%d", &n, &m, &p, &q);
136     for (int i = 0; i < n; ++i) scanf("%s", a[i].s);
137     sort(a, a + n);
138     if (p) Solve1();
139     else if (q) Solve2();
140     else     Solve3();
141     fclose(stdin); fclose(stdout);
142     return 0;
143 }
View Code

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 的数组滚动即可。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cmath>
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 const int N = 1001, M = 1024, W = 1e9;
10 int n, cur, nxt, va, vx, p[N];
11 
12 struct huge_int {
13     int len, a[40];
14     huge_int(): len(1) { memset(a, 0, sizeof(a)); }
15     
16     inline void operator += (const huge_int &b) {
17         b.len > len ? len = b.len : 0;
18         for (int i = 1; i <= len; ++i) {
19             a[i] += b.a[i];
20             if (a[i] >= W) ++a[i + 1], a[i] -= W;
21         }
22         if (a[len + 1]) ++len;
23         return ;
24     }
25     
26     inline void print() {
27         printf("%d", a[len]);
28         for (int i = len - 1; i; --i)
29             printf("%09d", a[i]);
30         puts(""); return ;
31     }
32 } f[2][M][3];
33 
34 char ch;
35 int read() {
36     while (ch = getchar(), ch < '0' || ch > '9');
37     int res = ch - 48;
38     while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
39     return res;
40 }
41 
42 int main() {
43     freopen("sequence.in", "r", stdin);
44     freopen("sequence.out", "w", stdout);
45     n = read();
46     for (int i = n; i; --i) p[i] = read();
47     f[0][1023][0].a[1] = 1;
48     for (int i = 0; i < n; ++i) {
49         nxt = cur ^ 1;
50         for (int j = 0; j < M; ++j)
51             for (int k = 0; k <= 2; ++k)
52                 f[nxt][j][k] = f[cur][j][k];
53         for (int j = 0; j < M; ++j) {
54             va = p[i + 1] & j, vx = p[i + 1] ^ j;
55             f[nxt][va][1] += f[cur][j][0]; f[nxt][va][1] += f[cur][j][1];
56             f[nxt][vx][2] += f[cur][j][1]; f[nxt][vx][2] += f[cur][j][2];
57         }
58         cur ^= 1;
59     }
60     f[cur][0][2].print();
61     fclose(stdin); fclose(stdout);
62     return 0;
63 }
View Code

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)。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <queue>
 7 using namespace std;
 8 
 9 #define X first
10 #define Y second
11 #define mk make_pair
12 typedef pair<int, int> DI;
13 typedef long long ll;
14 const int N = 51, M = 201, K = 20001;
15 int n, m, len, u, v, c, Case;
16 int tot, info[N], nxt[M], go[M], val[M];
17 ll T, INF, dist[N][K];
18 queue<DI> que;
19 bool vis[N][K];
20 
21 inline void SetE(int x, int y, int z) {
22     nxt[++tot] = info[x]; info[x] = tot; go[tot] = y; val[tot] = z;
23     nxt[++tot] = info[y]; info[y] = tot; go[tot] = x; val[tot] = z;
24     return ;
25 }
26 
27 inline void Spfa() {
28     int x, y, p, q; ll v;
29     memset(dist, 63, sizeof(dist));
30     dist[0][0] = 0; que.push(mk(0, 0));
31     while (!que.empty()) {
32         DI top = que.front(); que.pop();
33         x = top.X, p = top.Y; vis[x][p] = false;
34         for (int k = info[x]; y = go[k], k; k = nxt[k]) {
35             v = dist[x][p] + val[k]; q = v % len;
36             if (dist[y][q] > v) {
37                 dist[y][q] = v;
38                 if (!vis[y][q]) {
39                     vis[y][q] = true;
40                     que.push(mk(y, q));
41                 }
42             }
43         }
44     }
45     return ;
46 }
47 
48 char ch;
49 inline int read() {
50     while (ch = getchar(), ch < '0' || ch > '9');
51     int res = ch - 48;
52     while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
53     return res;
54 }
55 inline ll Read() {
56     while (ch = getchar(), ch < '0' || ch > '9');
57     ll res = ch - 48;
58     while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
59     return res;
60 }
61 
62 int main() {
63     freopen("travel.in", "r", stdin);
64     freopen("travel.out", "w", stdout);
65     Case = read();
66     while (Case--) {
67         n = read(), m = read(); T = Read();
68         memset(info, 0, sizeof(info)); tot = 0;
69         for (int i = 1; i <= m; ++i) {
70             u = read(), v = read(); c = read();
71             SetE(u, v, c);
72         }
73         if (!info[0]) puts("Impossible");
74         else {
75             len = 10001;
76             for (int k = info[0]; k; k = nxt[k])
77                 if (val[k] < len) len = val[k];
78             len *= 2; Spfa();
79             if (dist[n - 1][T % len] <= T) puts("Possible");
80             else     puts("Impossible");
81         }
82     }    
83     fclose(stdin); fclose(stdout);
84     return 0;
85 }
View Code

 

转载于:https://www.cnblogs.com/J-william/p/6063373.html

相关文章：

  • 一套后台管理html模版
  • 关于CXF的FrontEnd和数据绑定方案
  • Android开发之计算器（一）界面设计之activity_main布局文件
  • 再谈Redirect(客户端重定向)和Dispatch(服务器端重定向)
  • 男神的补习
  • 360浏览器兼容模式 不能$.post (不是a 连接 onclick的问题!!)
  • Fluent NHibernate系列文章
  • 第八次作业
  • 计算思维导论
  • maven项目搭建
  • 图像识别技术
  • RTP协议
  • Java中Vector和ArrayList的区别
  • 如何培养数据分析的能力？
  • zabbix根据主机和端口列表自动发现监控远程MongoDB实例
  • IDEA常用插件整理
  • java小心机(3)| 浅析finalize()
  • Laravel核心解读--Facades
  • Laravel深入学习6 - 应用体系结构：解耦事件处理器
  • mongo索引构建
  • Odoo domain写法及运用
  • Python - 闭包Closure
  • React Native移动开发实战-3-实现页面间的数据传递
  • Vue2.0 实现互斥
  • Vue全家桶实现一个Web App
  • 测试开发系类之接口自动化测试
  • 对象管理器（defineProperty）学习笔记
  • 翻译 | 老司机带你秒懂内存管理 - 第一部（共三部）
  • 回顾 Swift 多平台移植进度 #2
  • 漫谈开发设计中的一些“原则”及“设计哲学”
  • 让你成为前端，后端或全栈开发程序员的进阶指南，一门学到老的技术
  • 世界上最简单的无等待算法(getAndIncrement)
  • 小李飞刀：SQL题目刷起来！
  • PostgreSQL之连接数修改
  • ​决定德拉瓦州地区版图的关键历史事件
  • ​一帧图像的Android之旅 :应用的首个绘制请求
  • （七）理解angular中的module和injector，即依赖注入
  • （十）T检验-第一部分
  • （四）搭建容器云管理平台笔记—安装ETCD(不使用证书)
  • (中等) HDU 4370 0 or 1，建模+Dijkstra。
  • (转)视频码率,帧率和分辨率的联系与区别
  • （转）微软牛津计划介绍——屌爆了的自然数据处理解决方案(人脸/语音识别，计算机视觉与语言理解)...
  • * 论文笔记 【Wide Deep Learning for Recommender Systems】
  • ..回顾17，展望18
  • ./和../以及/和~之间的区别
  • .NET Framework 的 bug？try-catch-when 中如果 when 语句抛出异常，程序将彻底崩溃
  • .NET Framework 和 .NET Core 在默认情况下垃圾回收（GC）机制的不同（局部变量部分）
  • .NET中winform传递参数至Url并获得返回值或文件
  • .net中我喜欢的两种验证码
  • /ThinkPHP/Library/Think/Storage/Driver/File.class.php 　LINE: 48
  • @ModelAttribute 注解
  • [100天算法】-二叉树剪枝（day 48）
  • [1127]图形打印 sdutOJ
  • [Android Pro] AndroidX重构和映射
  • [Android] 240204批量生成联系人，短信，通话记录的APK