比赛链接：Dashboard - The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jinan) - Codeforces
A
题意：有一个合法的由 $(\ ),[\ ]$ 组成的括号序列，现在括号的左右反了，如 $($ 可能写成了 $)$ ，求能不能根据现有的序列找到一个唯一的初始括号序列。
先不考虑括号的左右，对同种括号操作。
将括号分层，如 $(\ )\ [\ ]\ (\ )$ 均属于第一层，而 $(\ [\ ]\ [\ ]\ )$ 中，小括号属于第一层，中括号属于第二层；若同种符号出现在了同一层，那么可以调转两个靠内的符号使其生成两种不同的序列，如 $(\ (\ [\ ]\ )\ )$ ， $(\ [\ [\ ]\ ]\ )$ 。
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
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int len=s.length();
int p[len+5][3];
for(int i=0;i<len;i++)p[i][1]=0,p[i][2]=0;
stack<int>sta;
bool flag=0;
for(int i=0;i<len;i++)
{
if(s[i]=='(' || s[i]==')')
{
if(sta.size() && sta.top()==1)
{
if(p[sta.size()][1]==1)
{
cout<<"No\n";
flag=1;
break;
}
p[sta.size()][1]=1;
sta.pop();
}
else sta.push(1);
}
if(s[i]=='[' || s[i]==']')
{
if(sta.size() && sta.top()==2)
{
if(p[sta.size()][2]==1)
{
cout<<"No\n";
flag=1;
break;
}
p[sta.size()][2]=1;
sta.pop();
}
else sta.push(2);
}
}
if(!flag)cout<<"Yes\n";
}
return 0;
}
|
D
水题
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
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(r1-l1>=10 || r2-l2>=10)cout<<"9\n";
else
{
int ans=0;
for(int i=l1;i<=r1;i++)
{
for(int j=l2;j<=r2;j++)
{
long long x=i+j;
while(x)
{
ans=max((long long)ans,x%10);
x/=10;
}
}
}
cout<<ans<<endl;
}
}
return 0;
}
|
G
题意：给出一个 $n\times m$ 的01矩阵，可以通过选取某些行使其倒转使得每一列包含至多一个1。问有多少种选取方法。
对于每一行，将其倒置后复制在第 $i+n$ 行，相当于处理出 $2n\times m$ 的矩阵，以列为单位考虑：
同时考虑第 $i$ 列和第 $m-i+1$ 列，若一共出现超过2个1，那么直接输出答案0；若一共出现2个1，那么说明可能需要使行倒转，假设第 $i$ 行和第 $j$ 行出现了2个1，若不需要倒置就满足条件，那么分别将第 $i $ 行和第 $j$ 行与第 $i+n$ 行和第 $j+n$ 行归为一个并查集，若需要倒置，那么分别将 $i$ 行和第 $j+n$ 行，第 $j$ 行和第 $i+n$ 行归为一个并查集，若某一行在两个并查集中都出现了，那么矛盾，输出0（敌人的敌人就是朋友）；最后每个并查集有两种操作方法，答案就是 $2^k$ ，$k$ 是联通块个数。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,m,num;
string s[1000010];
int fa[2000010];
int getf(int x){
return fa[x]==x?x:fa[x]=getf(fa[x]);
}
inline int qpow(int x,int y){
int ret=1;
while(y){
if(y&1) ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
bool solve(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=2*n;++i) fa[i]=i;
num=n;
for(int i=1;i<=n;++i) cin>>s[i];
for(int i=0;i<=m/2-1;++i){
int fl=0,lst=0;
for(int j=1;j<=n;++j){
if(s[j][i]=='0'&&s[j][m-i-1]=='0') continue;
if(fl==2) return 0;
if(s[j][i]=='1'&&s[j][m-i-1]=='1') {
if(fl==1) return 0;
fl=2;
continue;
}
if(fl==0){
lst=j;
fl=1;
continue;
}
fl=2;
int x1,y1,x2,y2;
x1=getf(lst);
y1=getf(j);
x2=getf(lst+n);
y2=getf(j+n);
if(s[j][i]==s[lst][i]){
if(x1==y1||x2==y2) return 0;
if(x1==y2||x2==y1) continue;
fa[x1]=y2;
fa[y1]=x2;
}
else {
if(x1==y2||x2==y1) return 0;
if(x1==y1||x2==y2) continue;
fa[x1]=y1;
fa[x2]=y2;
}
--num;
}
}
if(m&1){
int c=0;
for(int i=1;i<=n;++i) c+=s[i][m/2]-'0';
if(c>1) return 0;
}
printf("%lld\n",qpow(2,num));
return 1;
}
signed main(){
int T;
scanf("%lld",&T);
while(T--){
if(!solve()) puts("0");
}
}
|
I
题意：给出一个长度为 $n$ 的数组，可以进行最多 $\lfloor \frac{n}{2}\rfloor$ 次操作，每次选择两个端点 $l\leq r$ 且 $a_l>a_r$ ，将这两个端点之间的元素从小到大排序，最后使得整个数组有序。求最少操作方案。$n\leq 100$
每次以第一个 $a[i]!=i$ 的数的位置为左端点，找到右边离它最远的且小于它的数的位置作为右端点进行排序。
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
| # include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N];
int id[N];
int n;
vector<pair<int,int>>path;
void solve()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
id[a[i]] = i;
}
path.clear();
int t = 1;
for(int i = 1; i <= n; i ++)
{
if(a[i] == i) continue;
int j = n;
for(j = n; j > i; j --)
{
if(a[j] < a[i])
{
path.push_back({i, j});
t = i;
i = a[i];
break;
}
}
sort(a + t, a + j + 1);
}
cout << path.size() << '\n';
for(auto c : path) cout << c.first << ' ' << c.second << endl;
}
int main()
{
int T = 1;
cin >> T;
while(T --) solve();
return 0;
}
|
K
题意：给出一个长度为 $n$ 的数组，可以操作 $k$ 次，每次使一个元素加1或者减1，最后求最长的连续递增子序列长度，满足 $a_i=a_{i+1}-1$ 。
好恶心啊
假设长度为 $t$ 的区间 $[l,r]$ 满足条件，那么一定有：
$$
|x+1-a_l|+|x+2-a_{l+1}|+…+|x+t-a_{r}|\leq k
$$
由绝对值不等式可得当 $x$ 取 $i-a_i$ 的中位数时最小，最小值为最大的 $\lfloor \frac{t}{2}\rfloor$ 个数的和减去最小的 $\lfloor \frac{t}{2}\rfloor$
个数的和。求答案时用双指针进行贪心扩展，用两个 $set$ 来实现对顶堆处理两部分和。
可以证明最优答案一定可以通过贪心扩展得到。
（不能用二分，因为 $O(nlog^2n)$会超时）
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
| # include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 500010;
int n;
int a[N];
LL k;
bool check(int n)
{
LL sum1 = 0, sum2 = 0;
multiset<int> q1,q2;
int mid = 1 - a[1];
int t = 1;
int res = 1;
int l = 1, r = 1;
for(int i = 2; i <= n; i ++)
{
if(t & 1)
{
if(i - a[i] >= mid)
{
q2.insert(i - a[i]);
sum2 += i - a[i];
q1.insert(mid);
sum1 += mid;
}
else
{
q1.insert(i - a[i]);
sum1 += i - a[i];
q2.insert(mid);
sum2 += mid;
}
}
else
{
if(i - a[i] >= *q2.begin())
{
q2.insert(i - a[i]);
sum2 += i - a[i];
mid = *q2.begin();
sum2 -= mid;
q2.erase(q2.begin());
}
else
{
q1.insert(i - a[i]);
sum1 += i - a[i];
mid = *(--q1.end());
sum1 -= mid;
q1.erase(--q1.end());
}
}
++ t;
r = i;
if(sum2 - sum1 <= k) res = max(res, t);
while(sum2 - sum1 > k && t)
{
if(t & 1)
{
if(l - a[l] == mid)
{
;
}
else if(l - a[l] > mid)
{
q2.erase(q2.lower_bound(l - a[l]));
sum2 -= l - a[l];
sum2 += mid;
q2.insert(mid);
}
else
{
q1.erase(q1.lower_bound(l - a[l]));
sum1 -= l - a[l];
q1.insert(mid);
sum1 += mid;
}
}
else
{
if(l - a[l] <= *(--q1.end()))
{
q1.erase(q1.lower_bound(l - a[l]));
sum1 -= l - a[l];
mid = *q2.begin();
q2.erase(q2.begin());
sum2 -= mid;
}
else
{
q2.erase(q2.lower_bound(l - a[l]));
sum2 -= l - a[l];
mid = *(--q1.end());
q1.erase(--q1.end());
sum1 -= mid;
}
}
++ l;
-- t;
}
}
cout << res << endl;
}
int main()
{
int T = 1;
scanf("%d",&T);
while(T --)
{
scanf("%d%lld", &n, &k);
for(int i =1; i <= n; i ++) scanf("%d",&a[i]);
check(n);
}
return 0;
}
|
微信
支付宝
