前言
看完題目大意，先思考，再看解析；覺得題目大意不清晰，點(diǎn)擊題目鏈接看原文。
A
題目鏈接
題目大意：n個(gè)點(diǎn)在一維坐標(biāo)軸上，坐標(biāo)x[i]從小到大。
每個(gè)點(diǎn)會選擇Left或者Right的方向前進(jìn)，速度v=1，求首次相遇的時(shí)間，如果所有點(diǎn)都不會相遇則輸出-1。
樣例數(shù)據(jù)：
input
4
RLRL
2 4 6 10
output
1
input
3
LLR
40 50 60
output
-1
數(shù)據(jù)范圍 (1?≤?n?≤?200?000) ， (0?≤?x[i]?≤?109)
代碼實(shí)現(xiàn)：
int right = -1;
for (int i = 0; i < n; ++i) {
if (str[i] == 'R') {
right = i;
}
else {
if (right != -1 && a[i] != a[right]) {
if (ret == -1) {
ret = (a[i] - a[right]) / 2;
}
else {
ret = min(ret, (a[i] - a[right]) / 2);
}
}
}
}
題目解析：
對于點(diǎn)i，有兩種碰撞情況：
1、方向是L，遇到左邊的點(diǎn)方向是R；
2、方向是R，遇到右邊的店方向是L；
假設(shè)點(diǎn)i和點(diǎn)j是碰撞的點(diǎn)，那么點(diǎn)i的情況1就是點(diǎn)j的情況2；
那么對于點(diǎn)i只考慮左邊的點(diǎn)即可；
題目變成：對于每個(gè)點(diǎn)，求左邊最近的方向?yàn)镽 的點(diǎn)。
B
題目鏈接
題目大意：n*m的棋盤上有若干點(diǎn)，找一個(gè)點(diǎn)橫豎能覆蓋所有點(diǎn)。
輸入數(shù)據(jù)中的*表示點(diǎn)。
n and m (1?≤?n,?m?≤?1000)
Examples
input
3 4
.*..
....
.*..
output
YES
1 2
方法1：
代碼實(shí)現(xiàn)：
// 假設(shè)符合的點(diǎn)
for (int i = 0; i < n && OK; ++i) {
for (int j = 0; j < m && OK; ++j) {
Node tmp;
tmp.x = i;
tmp.y = j;
nodes.insert(tmp);
}
}
// 檢查假設(shè)的點(diǎn)
for (int i = 0; i < n && OK; ++i) {
for (int j = 0; j < m && OK; ++j) {
if (str[i][j] == '*') {
set<Node>::iterator it = nodes.begin();
while (it != nodes.end()) {
if (it->x == i || it->y == j) {
++it;
}
else {
nodes.erase(it++);
}
}
if (nodes.size() == 0) {
OK = 0;
}
}
}
}
題目解析：
假設(shè)所有點(diǎn)符合，用set來存放所有的點(diǎn)，每遇到一個(gè)點(diǎn)，把不符合的去掉；
時(shí)間復(fù)雜度為O(NM*LogN)，復(fù)雜度的關(guān)鍵在于set的構(gòu)建。
方法2：
代碼實(shí)現(xiàn)：
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cin>>c[i][j];
if(c[i][j]=='*'){
k++;
a[i]++;
b[j]++;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++) {
s=a[i]+b[j];
if(c[i][j]=='*'){
s--;
}
if(s==k) {
cout<<"YES"<<endl<<i+1<<" "<<j+1;
return 0;
}
}
}
題目解析：
假設(shè)某一點(diǎn)符合，求這一個(gè)點(diǎn)覆蓋的點(diǎn)數(shù)是否包括其他所有需要覆蓋的點(diǎn)；
事先統(tǒng)計(jì)每行每列對應(yīng)的點(diǎn)數(shù)，求點(diǎn)覆蓋點(diǎn)數(shù)時(shí)通過每行每列的值可以較快計(jì)算出來。
時(shí)間復(fù)雜度為O(NM)。
C
題目鏈接
題目大意：
小明放了n天暑假，他非常喜歡去圖書館學(xué)習(xí)和去體育館鍛煉。
暑假里每天有4種情況：
- 0、體育館關(guān)門，圖書館關(guān)門；
- 1、體育館關(guān)門，圖書館開門；
- 2、體育館開門，圖書館關(guān)門；
- 3、體育館開門，圖書館開門；
但小明不希望連續(xù)兩天學(xué)習(xí)或者連續(xù)兩天鍛煉，如果不鍛煉也不學(xué)習(xí)那么小明會在家頹廢。
現(xiàn)在已知n天暑假里每天的圖書館、體育館開關(guān)門情況，問小明最少會在家頹廢幾天。
樣例
input
7
1 3 3 2 1 2 3
output
0
樣例解釋：小明可以在第1、3、5、7天選擇學(xué)習(xí)，2、4、6選擇運(yùn)動，故而小明最少會在家頹廢0天。
n (1?≤?n?≤?100)
代碼實(shí)現(xiàn)：
for (int i = 1; i <= n; ++i) {
int k;
cin >> k;
d[i][0] = min(min(d[i - 1][0] + 1, d[i - 1][1] + 1), d[i - 1][2] + 1);
if (k == 0) {
d[i][1] = d[i][2] = N;
}
if (k == 1) { // can to contest
d[i][1] = min(d[i - 1][2], d[i - 1][0]);
d[i][2] = N;
}
if (k == 2) { // can to gym
d[i][1] = N;
d[i][2] = min(d[i - 1][1], d[i - 1][0]);
}
if (k == 3) {
d[i][1] = min(d[i - 1][2], d[i - 1][0]);
d[i][2] = min(d[i - 1][1], d[i - 1][0]);
}
}
cout << min(min(d[n][0], d[n][1]), d[n][2]) << endl;
題目解析：
典型的動態(tài)規(guī)劃。
d[i][j]表示第i天，狀態(tài)為j時(shí)的最小休息天數(shù)。
j = 0表示都不去；
j = 1表示去contest；
j = 2表示去gym；
這樣j = 0可以由前面三種狀態(tài)轉(zhuǎn)換過來；
j = 1只能由0和2轉(zhuǎn)換；
j = 2只能由1和2轉(zhuǎn)換；
然后動態(tài)規(guī)劃一遍得最優(yōu)解。
D
題目鏈接
題目大意：有n個(gè)點(diǎn)。
有n個(gè)數(shù)字a[i]，表示第i個(gè)點(diǎn)的parent節(jié)點(diǎn)。
問使其變成一棵樹，最少需要修改多少條邊，并且把所有值輸出。
n (2?≤?n?≤?200?000)
Examples
input
4
2 3 3 4
output
1
2 3 4 4
代碼實(shí)現(xiàn)：
lld find(lld x) {
lld ret = f[x];
if (ret != x) {
ret = find(ret);
}
return f[x] = ret;
}
int main() {
for (int i = 1; i <= n; ++i) {
if (i != root) {
lld x = find(i);
lld y = find(a[i]);
if (x == y) {
++ans;
if (!root) {
root = x;
}
a[i] = root;
}
else {
f[x] = f[y];
}
}
}
}
題目解析：
n個(gè)點(diǎn)，n條邊。如果是樹必然是一條邊指向自己，其余n-1條邊沒有環(huán)。（有且僅有一個(gè)環(huán)）
那么假設(shè)有一個(gè)根節(jié)點(diǎn)root，當(dāng)出現(xiàn)環(huán)的時(shí)候，直接將環(huán)某個(gè)點(diǎn)指向root即可；
需要修改的數(shù)量=環(huán)的數(shù)量 - 1。
總結(jié)
兩個(gè)關(guān)鍵詞：動態(tài)規(guī)劃（C題）、并查集（D題）。
