【AtCoder Beginner Contest 261 (A·B·C·D)】

$Better\; reading\; experience$

---

---

A - Intersection

---

The main idea of the topic

Originoal Link

Given the endpoints of two colored intervals $L_1,R_1,L_2,R_2$, Find the length of the interval dyed with two colors at the same time

---

thought

• Data range is small , Violence enumeration interval
• Traverse two intervals , use res[i] Record the staining
• Traverse the dyed interval , Calculate the interval length

---

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int res[N];

int main(){
    
	
	int a, b, c, d;
	
	cin >> a >> b >> c >> d;
	
	for(int i = a; i <= b; i ++) res[i]++;
	
	for(int i = c; i <= d; i ++) res[i]++;
	
	int cnt = 0;
	for(int i = 0; i <= 200; i ++) if(res[i] == 2) cnt++;
	
	if(cnt) cout << cnt - 1 << endl;
	else cout << 0 << endl;
	
	return 0;
	
}

---

B - Tournament Result

---

The main idea of the topic

Origional Link

Given $N\times N$ Table of , unit $A_{i,j}$ Recorded +$i$ And $j$ Three situations of winning or losing and drawing in the match , If there are conflicts in the records, it means that the table is incorrect

---

thought

• Traversal table , Traverse $i$ That's ok , Each line from $j=i+1$ Column start
• Judge $A_{i,j}$ and $A_{j,i}$ Is your record consistent with the facts
• Mark the inconformity and exit

---

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

char mp[N][N];

int n;

int main(){
    
	
	cin >> n;
	
	for(int i = 1; i <= n; i ++){
    
		for(int j = 1; j <= n; j++) cin >> mp[i][j];
	}
	
	bool flag = 1;
	for(int i = 1; i <= n; i ++){
    
		for(int j = i + 1; j <= n; j ++){
    
			if(mp[i][j] == 'D' && mp[j][i] != 'D'){
    
				flag = 0;
				break;
			}
			else if(mp[i][j] == 'W' && mp[j][i] != 'L'){
    
				flag = 0;
				break;
			}
			else if(mp[i][j] == 'L' && mp[j][i] != 'W'){
    
				flag = 0;
				break;
			}
		}
		if(!flag) break;
	}
	
	if(flag) cout << "correct" << endl;
	else cout << "incorrect" << endl;
	
	return 0;
	
}

---

C - NewFolder(1)

---

The main idea of the topic

Origional Link

Given $N$ individual string Type of $S$ strand , According to the given $S$ The order of , For a total of $m$ Time $S_i$, If the current $S_i$ First appearance , Output $S_i$, Otherwise output $S_i(u-1)$,$u$ Indicates the number of occurrences

---

thought

• string s[N] Store read in $S$ The order of
• map<string,int> a, Record the current $S_i$ How many times has it appeared
• Traverse s[N], bring a[s[i]]++, if a[s[i]] - 1 == 0 This is the first time

---

Code

#include <bits/stdc++.h>
using namespace std;

map<string,int> a;

int n;

const int N = 1e6 + 3;

string s[N];

int main(){
    
	
	cin >> n;
	
	for(int i = 0; i < n; i ++) cin >> s[i];
	
	for(int i = 0; i < n; i ++){
    
		
		a[s[i]]++;
		int t = a[s[i]] - 1;
		if(t != 0){
    
			cout << s[i] << '(' << t << ')' << endl;
		}
		else cout << s[i] << endl;
		
	}
	
	return 0;
	
}

---

D - Flipping and Bonus

---

The main idea of the topic

Origional Link

Flip a coin to the front , The counter increases , On the contrary, the counter is cleared , Given $N$ Coin toss is the money you get from the front $X_i$, Given $M$ Reward rules , If the value of the counter reaches $C_i$, Will get $Y_i$ Reward , Ask how to get the most money

---

thought

• a[N] Record $X_i$,b[N] Record $Y_i$
• State means ：dp[i][j] Before presentation i Second throw , The current counter value is j When you get money
• State calculation ：
  • If the throw result is positive ： be dp[i][j] = dp[i - 1][j - 1] + a[i] + b[j]
  • On the contrary, the counter is cleared , Updated results ：dp[i][0] = max(dp[i][0],dp[i - 1][j])
• Pay attention long long

---

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL n,m;

const LL N = 5010;

LL dp[N][N];

LL a[N];
LL b[N];

int main(){
    
	
	cin >> n >> m;
	
	for(int i = 1; i <= n; i ++) cin >> a[i];
	
	for(int i = 0; i < m; i ++){
    
		int x, y;
		cin >> x >> y;
		b[x] = y;
	}
	
	for(int i = 1; i <= n; i ++){
    
		for(int j = 1; j <= i; j ++){
    
			dp[i][j] = dp[i - 1][j - 1] + a[i] + b[j];
		}
		
		for(int j = 0; j < i; j ++){
    
			dp[i][0] = max(dp[i][0],dp[i - 1][j]);
		}
		
	}
	
	LL ans = 0;
	
	for(int i = 0; i <= n; i ++) ans = max(ans,dp[n][i]);
	
	cout << ans << endl;
	
	return 0;
	
}