Codeforces Round 849 (Div. 4)
Powered by:NEFU AB-IN
?B站直播錄像！
@TOC
Codeforces Round 849 (Div. 4)
A ? ?Codeforces Checking
題意
Given a lowercase Latin character (letter), check if it appears in the string codeforces codeforces .
思路
模擬
代碼
1#include?<bits/stdc++.h>
2using?namespace?std;
3#define?int?long?long
4#undef?int
5
6#define?SZ(X)?((int)(X).size())
7#define?ALL(X)?(X).begin(),?(X).end()
8#define?IOS????????????????????????????????????????????????????????????????????????????????????????????????????????????\
9????ios::sync_with_stdio(false);???????????????????????????????????????????????????????????????????????????????????????\
10????cin.tie(nullptr);??????????????????????????????????????????????????????????????????????????????????????????????????\
11????cout.tie(nullptr)
12#define?DEBUG(X)?cout?<<?#X?<<?":?"?<<?X?<<?'\n'
13typedef?pair<int,?int>?PII;
14
15const?int?N?=?1e5?+?10,?INF?=?0x3f3f3f3f;
16
17void?solve()
18{
19????char?a;
20????cin?>>?a;
21????string?s?=?"codeforces";
22????for?(auto?x?:?s)
23????{
24????????if?(x?==?a)
25????????{
26????????????cout?<<?"YES\n";
27????????????return;
28????????}
29????}
30????cout?<<?"NO\n";
31????return;
32}
33
34signed?main()
35{
36????IOS;
37????int?T;
38????cin?>>?T;
39????while?(T--)
40????????solve();
41????return?0;
42}B. Following Directions
題意
略
思路
模擬
代碼
1/*
2*?@Author:?NEFU?AB-IN
3*?@Date:?2023-02-03?22:35:26
4*?@FilePath:?\CF\1791\b\b.cpp
5*?@LastEditTime:?2023-02-03?22:40:58
6*/
7#include?<bits/stdc++.h>
8using?namespace?std;
9#define?int?long?long
10#undef?int
11
12#define?SZ(X)?((int)(X).size())
13#define?ALL(X)?(X).begin(),?(X).end()
14#define?IOS????????????????????????????????????????????????????????????????????????????????????????????????????????????\
15????ios::sync_with_stdio(false);???????????????????????????????????????????????????????????????????????????????????????\
16????cin.tie(nullptr);??????????????????????????????????????????????????????????????????????????????????????????????????\
17????cout.tie(nullptr)
18#define?DEBUG(X)?cout?<<?#X?<<?":?"?<<?X?<<?'\n'
19typedef?pair<int,?int>?PII;
20
21const?int?N?=?1e5?+?10,?INF?=?0x3f3f3f3f;
22
23void?solve()
24{
25????int?n;
26????cin?>>?n;
27????string?s;
28????cin?>>?s;
29????int?xs?=?0,?ys?=?0;
30????for?(auto?x?:?s)
31????{
32????????if?(x?==?'U')
33????????????ys++;
34????????if?(x?==?'D')
35????????????ys--;
36????????if?(x?==?'L')
37????????????xs--;
38????????if?(x?==?'R')
39????????????xs++;
40????????if?(ys?==?1?&&?xs?==?1)
41????????{
42????????????cout?<<?"YES\n";
43????????????return;
44????????}
45????}
46????cout?<<?"NO\n";
47????return;
48}
49
50signed?main()
51{
52????IOS;
53????int?T;
54????cin?>>?T;
55????while?(T--)
56????????solve();
57????return?0;
58}C. Prepend and Append
題意
Timur initially had a binary string? s(possibly of length 0). He performed the following operation several (possibly zero) times:
Add 0to one end of the string and 1to the other end of the string. For example, starting from the string 1011, you can obtain either 010111or 110110.
You are given Timur's final string. What is the length of the shortest possible string he could have started with??A binary string is a string (possibly the empty string) whose characters are either 0or 1.思路
模擬即可，兩種選擇，刪到不能再刪為止
代碼
1/*
2*?@Author:?NEFU?AB-IN
3*?@Date:?2023-02-03?22:35:26
4*?@FilePath:?\CF\1791\c\c.cpp
5*?@LastEditTime:?2023-02-03?22:46:12
6*/
7#include?<bits/stdc++.h>
8using?namespace?std;
9#define?int?long?long
10#undef?int
11
12#define?SZ(X)?((int)(X).size())
13#define?ALL(X)?(X).begin(),?(X).end()
14#define?IOS????????????????????????????????????????????????????????????????????????????????????????????????????????????\
15????ios::sync_with_stdio(false);???????????????????????????????????????????????????????????????????????????????????????\
16????cin.tie(nullptr);??????????????????????????????????????????????????????????????????????????????????????????????????\
17????cout.tie(nullptr)
18#define?DEBUG(X)?cout?<<?#X?<<?":?"?<<?X?<<?'\n'
19typedef?pair<int,?int>?PII;
20
21const?int?N?=?1e5?+?10,?INF?=?0x3f3f3f3f;
22
23void?solve()
24{
25????int?n;
26????cin?>>?n;
27????string?s;
28????cin?>>?s;
29????int?ans?=?n;
30????for?(int?i?=?0;?i?<?SZ(s);?++i)
31????{
32????????if?(ans?==?0)
33????????????break;
34????????if?(s[i]?==?'0'?&&?s[SZ(s)?-?i?-?1]?==?'1')
35????????????ans?-=?2;
36????????else?if?(s[i]?==?'1'?&&?s[SZ(s)?-?i?-?1]?==?'0')
37????????????ans?-=?2;
38????????else
39????????{
40????????????cout?<<?ans?<<?'\n';
41????????????return;
42????????}
43????}
44????cout?<<?ans?<<?'\n';
45????return;
46}
47
48signed?main()
49{
50????IOS;
51????int?T;
52????cin?>>?T;
53????while?(T--)
54????????solve();
55????return?0;
56}D. Distinct Split
題意
Let's denote the f(x)function for a string xas the number of distinct characters that the string contains. For example f(abc)=3, f(bbbbb)=1, and f(babacaba)=3.
Given a string s, split it into two non-empty strings aand bsuch that f(a)+f(b)is the maximum possible. In other words, find the maximum possible value of f(a)+f(b)such that a+b=s(the concatenation of string aand string bis equal to string s).思路
注意這里分字符串，是兩者必須連著，也就是兩個子串
所以可以預處理到每個點的元素種類，從前往后，從后往前，都處理一遍，最后遍歷求最值即可代碼
1#include?<bits/stdc++.h>
2using?namespace?std;
3#define?int?long?long
4#undef?int
5
6#define?SZ(X)?((int)(X).size())
7#define?ALL(X)?(X).begin(),?(X).end()
8#define?IOS????????????????????????????????????????????????????????????????????????????????????????????????????????????\
9????ios::sync_with_stdio(false);???????????????????????????????????????????????????????????????????????????????????????\
10????cin.tie(nullptr);??????????????????????????????????????????????????????????????????????????????????????????????????\
11????cout.tie(nullptr)
12#define?DEBUG(X)?cout?<<?#X?<<?":?"?<<?X?<<?'\n'
13typedef?pair<int,?int>?PII;
14
15const?int?N?=?1e5?+?10,?INF?=?0x3f3f3f3f;
16
17void?solve()
18{
19????int?n;
20????cin?>>?n;
21????string?s;
22????cin?>>?s;
23????s?=?'0'?+?s;
24????unordered_map<char,?int>?st;
25????vector<int>?a(n?+?10),?b(n?+?10);
26????for?(int?i?=?1;?i?<?SZ(s);?++i)
27????{
28????????if?(!st.count(s[i]))
29????????????a[i]++;
30????????st[s[i]]++;
31????}
32????for?(int?i?=?1;?i?<?SZ(s);?++i)
33????{
34????????a[i]?+=?a[i?-?1];
35????}
36????st.clear();
37????for?(int?i?=?SZ(s)?-?1;?i?>=?1;?--i)
38????{
39????????if?(!st.count(s[i]))
40????????????b[i]++;
41????????st[s[i]]++;
42????}
43????for?(int?i?=?SZ(s)?-?1;?i?>=?1;?--i)
44????{
45????????b[i]?+=?b[i?+?1];
46????}
47????int?mx?=?0;
48????for?(int?i?=?1;?i?+?1?<?SZ(s);?++i)
49????{
50????????int?ans?=?a[i]?+?b[i?+?1];
51????????mx?=?max(ans,?mx);
52????}
53????cout?<<?mx?<<?'\n';
54????return;
55}
56
57signed?main()
58{
59????IOS;
60????int?T;
61????cin?>>?T;
62????while?(T--)
63????????solve();
64????return?0;
65}E. Negatives and Positives
題意
翻譯：可以翻轉(zhuǎn)相鄰的兩個元素的正負，也就是index isuch that 1≤i≤n?1 and assign a[i]=?a[i] and a[i+1]=?a[i+1]
問數(shù)組最大值思路
兩種思路
思維
性質(zhì)：可以發(fā)現(xiàn)，翻轉(zhuǎn)相鄰兩元素正負，如果不限制次數(shù)，其實也就相當于，數(shù)組中兩個任意元素翻轉(zhuǎn)正負
那么就考慮非正數(shù)個數(shù)的奇偶性即可- 如果是偶數(shù)，那么內(nèi)部消化
- 如果是奇數(shù)，絕對值最小的那個負數(shù)不翻轉(zhuǎn)即可
線性dp
如果沒發(fā)現(xiàn)我上面說的性質(zhì)的話，可以采用dp直接推
我們這里規(guī)定：從下標為2開始，i和i-1同時翻轉(zhuǎn)狀態(tài)表示：
dp[i][0]代表到i處的最大值，此時i和i-1不翻轉(zhuǎn)dp[i][1]代表到i處的最大值，此時i和i-1翻轉(zhuǎn)- 此時i和i-1都必須具有可主動翻轉(zhuǎn)的能力??！，也就是i-1也可策動i-2翻轉(zhuǎn)，所以，i必須大于2
- 所以我們需要預處理
i=1和i=2的情況
狀態(tài)方程
- 第二個方程解釋一下，就是這個是a[i]翻的情況，那么由于dp[i-1][0]的情況是a[i-1]不翻的最大值，那么此時a[i]翻了，就會策動a[i-1]翻，所以要減去兩倍的a[i-1]，后面同理
最后輸出變或不變的最大值即可
代碼
思維
1/*
2*?@Author:?NEFU?AB-IN
3*?@Date:?2023-02-04?14:02:33
4*?@FilePath:?\CF\1791\e\e1.cpp
5*?@LastEditTime:?2023-02-04?14:28:27
6*/
7#include?<bits/stdc++.h>
8using?namespace?std;
9#define?int?long?long
10
11#define?SZ(X)?((int)(X).size())
12#define?ALL(X)?(X).begin(),?(X).end()
13#define?IOS????????????????????????????????????????????????????????????????????????????????????????????????????????????\
14????ios::sync_with_stdio(false);???????????????????????????????????????????????????????????????????????????????????????\
15????cin.tie(nullptr);??????????????????????????????????????????????????????????????????????????????????????????????????\
16????cout.tie(nullptr)
17#define?DEBUG(X)?cout?<<?#X?<<?":?"?<<?X?<<?'\n'
18typedef?pair<int,?int>?PII;
19
20const?int?N?=?2e5?+?10,?INF?=?0x3f3f3f3f;
21
22void?solve()
23{
24????int?n,?sum?=?0,?neg?=?0;
25????cin?>>?n;
26????vector<int>?a(n);
27????for?(int?i?=?0;?i?<?n;?++i)
28????{
29????????cin?>>?a[i];
30????????if?(a[i]?<?0)
31????????{
32????????????neg++;
33????????????a[i]?=?-a[i];
34????????}
35????????sum?+=?a[i];
36????}
37????if?(neg?%?2)
38????{
39????????int?mn?=?*min_element(ALL(a));
40????????sum?-=?2?*?mn;
41????}
42????cout?<<?sum?<<?'\n';
43????return;
44}
45
46signed?main()
47{
48????IOS;
49????int?T;
50????cin?>>?T;
51????while?(T--)
52????????solve();
53????return?0;
54}線性dp
1/*
2*?@Author:?NEFU?AB-IN
3*?@Date:?2023-02-03?22:35:26
4*?@FilePath:?\CF\1791\e\e.cpp
5*?@LastEditTime:?2023-02-04?11:07:18
6*/
7#include?<bits/stdc++.h>
8using?namespace?std;
9#define?int?long?long
10
11#define?SZ(X)?((int)(X).size())
12#define?ALL(X)?(X).begin(),?(X).end()
13#define?IOS????????????????????????????????????????????????????????????????????????????????????????????????????????????\
14????ios::sync_with_stdio(false);???????????????????????????????????????????????????????????????????????????????????????\
15????cin.tie(nullptr);??????????????????????????????????????????????????????????????????????????????????????????????????\
16????cout.tie(nullptr)
17#define?DEBUG(X)?cout?<<?#X?<<?":?"?<<?X?<<?'\n'
18typedef?pair<int,?int>?PII;
19
20const?int?N?=?2e5?+?10,?INF?=?0x3f3f3f3f;
21
22int?dp[N][2],?a[N];
23
24void?solve()
25{
26????memset(a,?0,?sizeof?a);
27????memset(dp,?0,?sizeof?dp);
28????int?n;
29????cin?>>?n;
30????for?(int?i?=?1;?i?<=?n;?++i)
31????{
32????????cin?>>?a[i];
33????}
34????dp[1][0]?=?a[1],?dp[1][1]?=?-a[1];
35????dp[2][0]?=?a[1]?+?a[2],?dp[2][1]?=?-a[1]?-?a[2];
36????for?(int?i?=?3;?i?<=?n;?++i)
37????{
38????????dp[i][0]?=?a[i]?+?max(dp[i?-?1][0],?dp[i?-?1][1]);
39????????dp[i][1]?=?-a[i]?+?max(dp[i?-?1][0]?-?2?*?a[i?-?1],?dp[i?-?1][1]?+?2?*?a[i?-?1]);
40????}
41????cout?<<?max(dp[n][0],?dp[n][1])?<<?'\n';
42????return;
43}
44
45signed?main()
46{
47????IOS;
48????int?T;
49????cin?>>?T;
50????while?(T--)
51????????solve();
52????return?0;
53}F. Range Update Point Query
題意
題意：有一個長度為n的數(shù)組a, f函數(shù)操作為將a[i] 轉(zhuǎn)換為 a[i]每一位的數(shù)的和
1 l r: 代表數(shù)組中[l, r]中的所有數(shù)都進行一次f操作
2 x ?: 代表輸出a[x]思路
此題是好題，可以好好記錄一下，和2023?？秃儆柧殸I第一場的G一樣的思路
可以采用DSU，線段樹等，這里介紹一個set做法其實可以觀察到這個f函數(shù)，梯度下降很快，由于數(shù)值最大只有1e9，最大的數(shù)就是 99999999->72->9，所以最多變兩次，之后變成定值，就不會再變了
那么思路就是- 現(xiàn)將所有不是定值的數(shù)的下標加入set
- 當出現(xiàn)1操作，即修改時，首先二分找到比l大于等于的第一個下標 (因為可能[l, r]中已經(jīng)有數(shù)是定值，被移出set了)，將其進行f操作并更新回原數(shù)組，如果它已經(jīng)是定值了，則將其移出set。繼續(xù)根據(jù)這個的下標往后找，直到下標超過r，就break
- 當出現(xiàn)2操作，直接輸出a中的值即可
代碼
1#include?<bits/stdc++.h>
2using?namespace?std;
3#define?int?long?long
4#undef?int
5
6#define?SZ(X)?((int)(X).size())
7#define?ALL(X)?(X).begin(),?(X).end()
8#define?IOS????????????????????????????????????????????????????????????????????????????????????????????????????????????\
9????ios::sync_with_stdio(false);???????????????????????????????????????????????????????????????????????????????????????\
10????cin.tie(nullptr);??????????????????????????????????????????????????????????????????????????????????????????????????\
11????cout.tie(nullptr)
12#define?DEBUG(X)?cout?<<?#X?<<?":?"?<<?X?<<?'\n'
13typedef?pair<int,?int>?PII;
14
15const?int?N?=?2e5?+?10,?INF?=?0x3f3f3f3f;
16
17int?f(int?x)
18{
19????int?ans?=?0;
20????while?(x)
21????{
22????????ans?+=?x?%?10;
23????????x?/=?10;
24????}
25????return?ans;
26}
27int?a[N];
28
29void?solve()
30{
31????int?n,?m;
32????cin?>>?n?>>?m;
33????set<int>?st;
34????for?(int?i?=?1;?i?<=?n;?i++)
35????{
36????????cin?>>?a[i];
37????????if?(f(a[i])?!=?a[i])
38????????????st.insert(i);
39????}
40????st.insert(n?+?1);
41????for?(int?i?=?1;?i?<=?m;?i++)
42????{
43????????int?op;
44????????cin?>>?op;
45????????if?(op?==?1)
46????????{
47????????????int?l,?r;
48????????????cin?>>?l?>>?r;
49????????????int?val?=?l;
50????????????while?(1)
51????????????{
52????????????????auto?t1?=?st.lower_bound(val);
53????????????????int?pos?=?*t1;
54????????????????if?(pos?>?r)
55????????????????????break;
56????????????????a[pos]?=?f(a[pos]);
57????????????????if?(f(a[pos])?==?a[pos])
58????????????????????st.erase(pos);
59????????????????val?=?pos?+?1;
60????????????}
61????????}
62????????else
63????????{
64????????????int?pos;
65????????????cin?>>?pos;
66????????????cout?<<?a[pos]?<<?'\n';
67????????}
68????}
69}
70
71signed?main()
72{
73????IOS;
74????int?T;
75????cin?>>?T;
76????while?(T--)
77????????solve();
78????return?0;
79}G1. Teleporters (Easy Version)
題意
題意：有0,1,…n個地點，其中1到n處有傳送門，現(xiàn)在有m個金幣，往左往右走會耗費一個金幣，走到第i個傳送門，如果該處的傳送門還存在的話，那么就可以做這個傳送門回0（即原點）并花費此處的金幣，這個傳送門就不可以再用了
求用傳送門的最多次數(shù)思路
其實就是個典型的貪心，類似于背包，總體積為m，物體體積為金幣+下標，價值為1
由于價值都是一樣的，所以一定是體積越小越好，所以直接貪即可之前一直想的是01背包，還寫了01背包的逆過程，結果就是浪費時間…
代碼
1#include?<bits/stdc++.h>
2using?namespace?std;
3#define?int?long?long
4
5#define?SZ(X)?((int)(X).size())
6#define?ALL(X)?(X).begin(),?(X).end()
7#define?IOS????????????????????????????????????????????????????????????????????????????????????????????????????????????\
8????ios::sync_with_stdio(false);???????????????????????????????????????????????????????????????????????????????????????\
9????cin.tie(nullptr);??????????????????????????????????????????????????????????????????????????????????????????????????\
10????cout.tie(nullptr)
11#define?DEBUG(X)?cout?<<?#X?<<?":?"?<<?X?<<?'\n'
12typedef?pair<int,?int>?PII;
13
14const?int?N?=?2e5?+?10,?INF?=?0x3f3f3f3f;
15
16int?dp[N],?v[N],?V;
17
18void?solve()
19{
20????int?n;
21????cin?>>?n?>>?V;
22????for?(int?i?=?1;?i?<=?n;?++i)
23????{
24????????cin?>>?v[i];
25????????v[i]?+=?i;
26????}
27????sort(v?+?1,?v?+?n?+?1);
28????int?ans?=?0;
29????for?(int?i?=?1;?i?<=?n;?++i)
30????{
31????????if?(V?>=?v[i])
32????????{
33????????????V?-=?v[i];
34????????????ans++;
35????????}
36????????else
37????????????break;
38????}
39????cout?<<?ans?<<?'\n';
40????return;
41}
42
43signed?main()
44{
45????IOS;
46????int?T;
47????cin?>>?T;
48????while?(T--)
49????????solve();
50????return?0;
51}
標簽：
