AtCoder Beginner Contest 261 Partial Solution

本篇题解只是记录我的做题过程代码,不提供最优解
（另外这里所有的时间复杂度都只分析单个样例,不算$t$的时间复杂度）

A

点击此处查看对应的题目.
本题设计算法：差分
给出两个区间,The overlap interval can be directly calculated using the difference

时间复杂度 $O(max(b,d))$

#include <iostream>
#include <cstring> 
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const ll N = 2e5 + 10,mod = 1e9 + 7;
int s[N];

int main()
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    s[a] ++,s[b] --;s[c] ++,s[d] --;
    int maxn = max(b,d),res = 0;
    for (int i = 1;i <= maxn;i ++ ) s[i] += s[i - 1];
    for (int i = 0;i <= maxn;i ++ )
        if (s[i] == 2) res ++;

    cout << res << '\n';
    return 0;
}
  

---

B

点击此处查看对应的题目.
本题设计算法：模拟

directly simulate the meaning of the question,Whether the diagonal line is satisfied.

时间复杂度 $O(n^2)$

#include <iostream>
#include <cstring> 
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const ll N = 2010;
char g[N][N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0;i < n;i ++ ) {
        string s;
        cin >> s;
        for (int j = 0;j < n;j ++ ) {
            g[i][j] = s[j];
        }
    }
    for (int i = 0;i < n;i ++ ) {
        for (int j = 0;j < n;j ++ ) {
            if ((g[i][j] == 'W' && g[j][i] != 'L') || (g[i][j] == 'L' && g[j][i] != 'W') || (g[i][j] == 'D' && g[j][i] != 'D'))  {
                cout << "incorrect" << '\n';
                return 0;
            }
        }
    }
    cout << "correct" << '\n';
    return 0;
}

---

C

点击此处查看对应的题目.
本题设计算法：map统计

直接利用map统计字符串出现的次数即可

时间复杂度 $O(n)$

#include <iostream>
#include <cstring> 
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const ll N = 2e5 + 10;
string s[N];

int main()
{
    int n;
    cin >> n;
    unordered_map<string,int> mp;
    for (int i = 0;i < n;i ++ ) cin >> s[i];
    for (int i = 0;i < n;i ++ ) {
        if (mp.count(s[i]) == 0) cout << s[i] << '\n';
        else {
            cout << s[i] << "(" << mp[s[i]] << ")" << '\n'; 
        }
        mp[s[i]] ++;
    }
    return 0;
}

---

D

点击此处查看对应的题目.
本题设计算法：动态规划的背包问题

This question can be seen from the meaning of the question that every time a coin toss is tossed, there are two possibilities.

• 1是正面朝上
• 2 is reverse side up

Finally pass enumerationn次投掷,Various cases of counters,值得一提的是,在第 i The counter counts up to i,Because each time it is at most one is added or cleared.

State representation and state transitions are commented out in the following code,详细见以下代码

时间复杂度 $O(n^2)$

#include <iostream>
#include <cstring> 
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const ll N = 5010,INF = 1e18;
ll dp[N][N];//前icoin toss,当前计数器为j的最大收益
ll val[N];

int main()
{
    int n,m;
    cin >> n >> m;
    ll maxc = 0; 
    unordered_map<ll,ll> mp;
    for (int i = 1;i <= n;i ++ ) cin >> val[i];
    for (int i = 1;i <= m;i ++ ) {
        int a,b;
        cin >> a >> b;
        mp[a] = b;
    }
    for (int i = 1;i <= n;i ++ ) {
        for (int j = 1;j <= i;j ++ ) {//Enumerates the face-up cases
            dp[i][j] = dp[i - 1][j - 1] + val[i] + mp[j];
        }
        for (int j = 0;j <= i;j ++ ) {//Enumerations have tails up
            dp[i][0] = max(dp[i][0],dp[i - 1][j]);
        }
    }

    ll res = 0;
    for (int i = 0;i <= n;i ++ ) res = max(res,dp[n][i]);
    cout << res << '\n';
    return 0;    
}

---

E

点击此处查看对应的题目.
本题设计算法：位运算

We are considering dismantling,对于第 i Bits figured out eventually 0 还是 1.Just think about it now $X,A_i\in 0,1$ 的情形.

可以发现,These operations are not associative though,But the contribution brought by the final operation can be equivalent to the following four：

• Keep the original number the same.
• 将原数取反.
• Coerce the original number to 0.（即 x←x and 0 ）
• Coerce the original number to 1.（即 x←x or 1 ）

In other cases it will not be given X Bring change and contribution.

xor The contribution is equivalent to putting the current contribution in the section 3,4 interchange between species,或者在第 1,2 interchange between species.

We then deal with the equivalent contribution of each prefix of the sequence of operations.Finally, just combine each bit.

时间复杂度 $O(nloga)$

#include <iostream>
#include <cstring> 
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const ll N = 2e5 + 10,INF = 1e18;
int t[N],a[N],res[N],ans[N];

int main()
{
    int n,x;
    cin >> n >> x;
    for (int i = 1;i <= n;i ++ ) cin >> t[i] >> a[i];

    for (int i = 0;i < 30;i ++ ) {
        int val = x >> i & 1,now = 0;
        for (int j = 1;j <= n;j ++ ) {//Only these three things will really change
            int k = a[j] >> i & 1;
            if (k == 0 && t[j] == 1) now = 1;
            else if (k == 1 && t[j] == 2) now = 2;
            else if (k == 1 && t[j] == 3) now = 3 - now;
            res[j] = now;
        } 
        for (int j = 1;j <= n;j ++ ) {
            if (res[j] == 1) val = 0;
            else if (res[j] == 2) val = 1;
            else if (res[j] == 3) val = val ^ 1;
            ans[j] = (ans[j] | (val << i));
        } 
    }
    for (int i = 1;i <= n;i ++ ) cout << ans[i] << '\n';

    return 0;
}