心得技巧
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧

NOIP模拟57

发布时间：2022-07-05 发布网站：脚本宝典
脚本宝典收集整理的这篇文章主要介绍了NOIP模拟57，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

T1：

　　比较水的模拟，注意点：多想特殊情况即可

代码如下：

NOIP模拟57

NOIP模拟57

 1 #include <bITs/stdc++.h>
 2 using namespace std;
 3 #define I int
 4 #define C char
 5 #define B bool
 6 #define V void
 7 #define D double
 8 #define LL long long
 9 #define UL unsigned long long
10 #define P pair<I,I>
11 #define MP make_pair
12 #define fir First
13 #define sec second
14 #define lowbit(x) (x &amp; -x)
15 I len;
16 UL a[10];
17 C s[50];
18 B typ;
19 inline I read() {
20     I x(0),y(1); C z(getchar ());
21     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
22     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
23     return x * y;
24 }
25 inline V Max (I &a,I b) { a = a > b ? a : b; }
26 inline V Min (I &a,I b) { a = a < b ? a : b; }
27 inline I max (I a,I b) { return a > b ? a : b; }
28 inline I min (I a,I b) { return a < b ? a : b; }
29 inline V swap (I &a,I &b) { a ^= b, b ^= a,a ^= b; }
30 signed main () {
31     scanf ("%s",s + 1);
32     len = strlen (s + 1);
33     I cnt(1);
34     for (I i(1);i <= len; ++ i) {
35         B jud1(0),jud2(0);
36         while (!isdigit(s[i]) && i <= len) {
37             typ = 1; i ++ ; 
38         }
39         while ( isdigit(s[i]) && i <= len) {
40             if ( jud2) typ = 1;
41             if (!jud1 && (s[i] ^ 48) == 0) jud2 = 1;
42             jud1 = 1;
43             a[cnt] = a[cnt] * 10 + (s[i] ^ 48);
44             i ++ ;
45             if (i > len) break;
46             if ( isdigit(s[i])) continue;
47             else {
48                 if (cnt != 4 && s[i] == '.') break;
49                 else {
50                     typ = 1; break;
51                 }
52             }
53         }
54         cnt ++ ;
55     }
56     for (I i(1);i <= 4; ++ i)
57         if (a[i] > 255) 
58             a[i] = 255, typ = 1;
59     if (!typ) puts ("YES");
60     else {
61         puts ("NO");
62         for (I i(1);i <= 4; ++ i) {
63             PRintf ("%llu",a[i]);
64             if (i != 4) printf (".");
65         }
66     }
67 }
View Code

注意化简问题

T2：

　　考场DFs+记忆化+Hash

问题在于读题太慢，未想正解，直接打暴力，关键在于游戏的机制即只能删除AP || PP

发现关键点在于A只能由AP删除，而A又会阻碍P的删除

于是贪心的先把所有AP删除，再将所有P删除即可，具体实现采用栈模拟即可

代码如下：

NOIP模拟57

NOIP模拟57

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I int
 4 #define C char
 5 #define B bool
 6 #define V void
 7 #define D double
 8 #define LL long long
 9 #define UL unsigned long long
10 #define P pair<I,I>
11 #define MP make_pair
12 #define fir first
13 #define sec second
14 #define lowbit(x) (x & -x)
15 const I N = 1e4 + 5;
16 C s[N];
17 B q[N];
18 inline I read() {
19     I x(0),y(1); C z(getchar ());
20     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
21     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
22     return x * y;
23 }
24 inline V Max (I &a,I b) { a = a > b ? a : b; }
25 inline V Min (I &a,I b) { a = a < b ? a : b; }
26 inline I max (I a,I b) { return a > b ? a : b; }
27 inline I min (I a,I b) { return a < b ? a : b; }
28 inline V swap (I &a,I &b) { a ^= b, b ^= a,a ^= b; }
29 signed main () {
30     scanf ("%s",s + 1);
31     I len (strlen (s + 1)),h(1),t(0); 
32     for (I i(1); s[i] ; ++ i) {
33         if (s[i] == 'A') 
34             q[++t] = 1;
35         else {
36             if (h <= t && q[t])
37                 t -- ;
38             else q[++t] = 0;
39         }
40     }
41     I ans(t - h + 1);
42     for (I i(h);i <= t; ++ i) {
43         if (!q[i] && !q[i + 1]) 
44             ans -= 2, i ++ ;
45     }
46     printf ("%dn",ans);
47 }
View Code

T3：

　　O(n^4)能过，然而时间不够了，调+优化T2用的时间太长

正解是考虑问题关键在于判断菱形，根据O(n^4)暴力的思路很容易想到记录所有点的祖先

正确性在于由于问题的机制，每个点作为K只会出现一次，无后消性

考虑如何判断菱形，比较显然的思路为在记录当前结点祖先时枚举所有子节点，合并祖先信息

若a & b != 0，则说明出现菱形，判掉即可

　　然而具体实现仍然有些细节：首先需要将点按出现时间从大到小排序，因为在处理当前点父节点时，

可能父节点也是另一父节点的父节点，而从大到小排序可以解决问题，而从小到大排序却极难实现

因为菱形与父节点的判断都是由时间早向时间晚进行，同序（记录时间从小到大，并从小到大排序）难以判断

无法理解则根据时间顺序与节点关系造Hack数据即可

代码如下：

NOIP模拟57

NOIP模拟57

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I int
 4 #define C char
 5 #define B bool
 6 #define V void
 7 #define D double
 8 #define LL long long
 9 #define UL unsigned long long
10 #define P pair<I,I>
11 #define MP make_pair
12 #define fir first
13 #define sec second
14 #define lowbit(x) (x & -x)
15 const I N = 1005;
16 I n,num;
17 unordered_map <string,I> h;
18 string s,t;
19 bitset <N> jud[N];
20 inline I read() {
21     I x(0),y(1); C z(getchar ());
22     while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
23     while ( isdigit(z))  x = x * 10 + (z ^ 48), z = getchar();
24     return x * y;
25 }
26 inline V Max (I &a,I b) { a = a > b ? a : b; }
27 inline V Min (I &a,I b) { a = a < b ? a : b; }
28 inline I max (I a,I b) { return a > b ? a : b; }
29 inline I min (I a,I b) { return a < b ? a : b; }
30 inline V swap (I &a,I &b) { a ^= b, b ^= a,a ^= b; }
31 inline B com (const I &a,const I &b) { return a > b; }
32 signed main () {
33     n = read(); 
34     for (I i(1);i <= n; ++ i) {
35         I idx; B typ(0); 
36         vector <I> anc;
37         bitset <N> a;
38         cin >> s;
39         h.find (s) != h.end () ? 
40             typ = 1 : idx = ++num;
41         getchar (); getchar (); getchar ();
42         while (1) {
43             cin >> t; getchar();
44             if (t[0] == ';') break;
45             if (h.find (t) != h.end ())
46                 anc.push_back (h[t]);
47             else 
48                 typ = 1;
49         }
50         if (typ) goto flag;
51         sort (anc.begin (),anc.end (),com);
52         for (auto y : anc) if (!a[y]) {
53             if ((a & jud[y]).any ()) typ = 1;
54             a |= jud[y]; a[y] = 1;
55         }
56         if (!typ) jud[idx] = a, h[s] = idx;
57         flag :  typ ? puts ("greska") : puts ("ok");
58     }
59 
60 }
View Code

 

脚本宝典总结

以上是脚本宝典为你收集整理的NOIP模拟57全部内容，希望文章能够帮你解决NOIP模拟57所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
标签：c++javaphppythonsortStringwhilewhile优化优化排序排序程序员程序员
猜你在找的心得技巧相关文章
其他相关热搜词更多
phpjavapython程序员loadpost-format-gallerydivString参数开发ListcapMapClass工具安装SQL数据库资源this
全站导航更多
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧JavaScriptASP.NETPHP编程正则表达式AJAX相关ASP编程JSP编程编程10000问CSS/HTMLFlexvbsDOS/BAThtahtcpythonperl游戏相关VBA远程脚本ColdFusionMsSqlMysqlmariadboracleDB2mssql2008mssql2005SQLitePostgreSQLMongoDB星外虚拟主机华众虚拟主机Linuxwin服务器FTP服务器DNS服务器Tomcatnginxzabbix云和虚拟化bios系统安装系统系统进程Windows系列LINUXRedHat/CentosUbuntu/DebianFedoraSolaris红旗Linux建站经验微信营销网站优化网站策划网络赚钱网络创业站长故事alexa域名photoshop教程摄影教程Fireworks教程CorelDraw教程Illustrator教程Painter教程Freehand教程IndesignSketch笔记本主板内存CPU存储显卡显示器光存储鼠标键盘平板电脑安全教程杀毒防毒安全设置病毒查杀脚本攻防入侵防御工具使用业界动态Exploit漏洞分析
最新心得技巧教程
热门心得技巧教程