2020hdu多校第三场比赛及补题

原创
08/25 02:40
阅读数 34

1004 Tokitsukaze and Multiple

队友半小时内A了这题,强的一匹!

给一列数,每次可以把相邻的两个数合并成一个大数(比如12,74合并成86),给一个数字p,问通过这样的操作,最多能使这数列中多少数是p的倍数

 

举例:p = 3, 数列为 2, 1, 3, 2, 1

该数列可以变成3,3,3, 答案就是3

这题我做的话半小时应该不能做出来

可以用贪心的方法线性做,从左往右扫,每当判断出能合并出符合要求的数时就合并

这个贪心和那个关于区间的贪心模板题很像

事实上,这题假设我们已知所有能合成出符合要求的数的区间,问题就变成在这些区间里找出最多的互不重合的区间,那就是把这些区间按右端点排序

队友这题写的代码并不是很美观,但还是很强的

赛后我自己也做了一遍,下面的是我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<algorithm>
#include<cstdio>
using   namespace   std;
const   int   MAXN = 1e5+7;
int   a[MAXN], last[MAXN];
int   main()
{
     int   T;
     cin >> T;
     int   n,p,x;
     while (T--){
         cin>>n>>p;
         int   su = 0, pos = 1, ans = 0;
         for ( int   i = 1;i < p;i++) last[i] = 0;
         for ( int   i = 1;i <= n;i++){
             scanf ( "%d" ,&x);
             su += x;
             su %= p;
             if (su == 0 || last[su] >= pos){
                 pos = i + 1;
                 su = 0;
                 ans ++;
             }
             last[su] = i;
         }
         cout<<ans<<endl;
     }
     return   0;
}

  

1005 Little W and Contest

这里就不叙述题意了

这题队友写的,队友写的很整齐,很美观

但是wa了很多发,很惨

比赛到后期的时候,队友叫我看这题,给了我题意和他的做法,我觉得他的做法没问题,代码也写的很好,查不出什么错,我找到一个地方可能有问题,就是一个取模的地方他是+MOD 再%MOD,我感觉+2*MOD再%MOD会更保险,然后队友改了下,还真就过了,队友气死了....

我之后才学到一个更保险的办法是先%MOD,再+MOD,再%MOD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <bits/stdc++.h>
using   namespace   std;
#define int long long
const   int   MAXN = 1e5 + 7;
const   int   MOD = 1e9 + 7;
 
int   fac[MAXN], inv[MAXN];
 
inline   void   Pre( int   n)
{
     fac[0] = 1;
     for   ( int   i = 1; i <= n; i++)
         fac[i] = fac[i - 1] * i % MOD;
     inv[1] = 1;
     for   ( int   i = 2; i <= n; i++)
         inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
     inv[0] = 1;
     for   ( int   i = 1; i <= n; i++)
         inv[i] = inv[i] * inv[i - 1] % MOD;
}
 
inline   int   C( int   n,  int   m)
{
     if   (m > n)
         return   0;
     return   fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
// 计算组合数
inline   int   Pow( int   a,  int   b)
{
     int   ret = 1;
     for   (; b; b >>= 1, a = a * a % MOD)
         if   (b & 1)
             ret = ret * a % MOD;
     return   ret;
}
// 快速幂
 
int   T;
int   n;
int   pts[MAXN];
int   u, v;
int   ans;
int   tmp1, tmp2;
 
struct   DSU
{
     int   parent[MAXN];
     int   n;  // Nums of Nodes
     int   cnt;  // Count Strongly Connected Components
     int   sum1[MAXN];
     int   sum2[MAXN];
     int   rank[MAXN];
 
     void   init_parent( int   n)
     {
         this   -> n = n;
         cnt = 0;
         for   ( int   i = 1; i <= n; ++i)
         {
             parent[i] = i;
             if   (pts[i] == 1)
             {
                 sum1[i] = 1;
                 sum2[i] = 0;
             }
             else
             {
                 sum1[i] = 0;
                 sum2[i] = 1;
             }
             rank[i] = 0;
         }
     }
 
     int   find_parent( int   x)
     {
         if   (parent[x] == x)
             return   x;
         else
             parent[x] = find_parent(parent[x]);
         return   parent[x];
     }
 
     bool   check_unicom( int   x,  int   y)
     {
         return   find_parent(x) == find_parent(y);
     }
 
     void   merge( int   x,  int   y)
     {
         x = find_parent(x);
         y = find_parent(y);
         if   (x != y)
         {
             parent[x] = y;
             sum1[y] += sum1[x];
             sum2[y] += sum2[x];
             cnt++;
         }
     }
 
     int   getsum1( int   i)
     {
         return   sum1[find_parent(i)];
     }
     int   getsum2( int   i)
     {
         return   sum2[find_parent(i)];
     }
}dsu;
 
int32_t main( void )
{
     ios::sync_with_stdio( false );
     cin.tie(0); cout.tie(0);
     Pre(100005);
     cin >> T;
     while   (T--)
     {
         cin >> n;
         ans = 0;
         tmp1 = tmp2 = 0;
         for   ( int   i = 1; i <= n; ++i)
         {
             cin >> pts[i];
             if   (pts[i] == 1)
             {
                 tmp1++;
             }
             if   (pts[i] == 2)
             {
                 tmp2++;
             }
         }
         dsu.init_parent(n);
         ans = (C(tmp2, 2) % MOD * tmp1 % MOD) % MOD + C(tmp2, 3) % MOD;
         ans %= MOD;
         cout << ans << endl;
         for   ( int   i = 1; i <= n - 1; ++i)
         {
             cin >> u >> v;
             if   (!dsu.check_unicom(u, v))
             {
                 int   usum1 = dsu.getsum1(u);
                 int   usum2 = dsu.getsum2(u);
                 int   vsum1 = dsu.getsum1(v);
                 int   vsum2 = dsu.getsum2(v);
                 // cout << usum1 << " " << usum2 << " " << vsum1 << " " << vsum2 << endl;
                 int   les2 = tmp2 - usum2 - vsum2;
                 int   les1 = tmp1 - usum1 - vsum1;
                 // cout << les1 << " " << les2 << endl;
                 ans = ans + 2 * MOD
                 - les2 * ((usum2 * vsum1) % MOD + (usum1 * vsum2) % MOD) % MOD
                 - ((les2 + les1) % MOD) * (usum2 * vsum2 % MOD) % MOD
                 ;
                 dsu.merge(u, v);
             }
             ans %= MOD;
             cout << ans << endl;
         }
     }
     return   0;
}

  

队友喜欢把并查集写成结构体,我通常不这样做。

 

1009 Parentheses Matching

这场的签到题,括号匹配题

括号匹配的栈模拟题我还挺怕的,所以我很早看了这题后就把这题先放了,把这题交给队友解决,自己想其他题,然而我什么也没想出来,队友也一直没做出这题,我还是得来写这题

写了几遍才知道怎么写好

因为是字典序最小,所以:

缺 ( 时,要把最左边的 * 变成 (

缺 ) 时,要把最右边的 * 变成 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<algorithm>
#include<stack>
using   namespace   std;
stack< char > st;
char   ans[100007];
int   main()
{
     int   t;
     string s,ans;
     cin>>t;
     while (t--){
         cin>>s;
         while (!st.empty()) st.pop();
         int   cnt1 = 0,cnt2 = 0;
         bool   flag =  true ;
         for ( int   i = 0;s[i];i++){
             if (s[i]== '*' ) cnt1++;
             else   if (s[i]== '(' ) st.push(s[i]);
             else {
                 if (!st.empty()) st.pop();
                 else   {
                     cnt2++;
                     if (cnt2 > cnt1) {
                         flag =  false ;
                         break ;
                     }
                 }
             }
         }
         if (!flag) {
             printf ( "No solution!\n" );
             continue ;
         }
         else {
             int   cnt = 0;
             for ( int   i = 0;s[i]&&cnt<cnt2;i++){
                 if (s[i]== '*' ) {
                     cnt++;
                     s[i] =  '(' ;
                 }
             }
             while (!st.empty()) st.pop();
             cnt = 0;
             cnt1 = 0;
             cnt2 = 0;
             int   len = s.length();
             for ( int   i = len - 1;i >= 0;i--){
                 if (s[i]== ')' ){
                     st.push(s[i]);
                 }
                 else   if (s[i]== '*' ) cnt1++;
                 else {
                     if (!st.empty()) st.pop();
                     else   {
                         cnt2++;
                         if (cnt2>cnt1){
                             flag =  false ;
                             break ;
                         }
                     }
                 }
             }
             if (!flag) {
                 printf ( "No solution!\n" );
                 continue ;
             }
             for ( int   i = len - 1;i>=0&&cnt<cnt2;i--){
                 if (s[i]== '*' ){
                     cnt++;
                     s[i] =  ')' ;
                 }
             }
             for ( int   i = 0;s[i];i++){
                 if (s[i]!= '*' )  printf ( "%c" ,s[i]);
             }
             cout<<endl;
         }
     }
     return   0;
}

留学资讯网http://www.k-a.top
留学资讯网http://www.k-d.top
留学资讯网http://www.k-z.top

第三场一题都补不来OAO,1006太难了

展开阅读全文
oao
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部