程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces #200(div.2) 模擬練習賽

Codeforces #200(div.2) 模擬練習賽

編輯：C++入門知識

Codeforces #200(div.2) 模擬練習賽

A題：

題意：一行磁鐵，同性相斥，找到這行磁鐵可以分為多少塊思路：邊讀邊計算，讀到和上一次不一樣的就加1（第一組數據特判）手速題然而我沒有把思路理清楚再寫，比隊友滿了太多=_+。

代碼：

#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long int LL;
const int M = 100009,INF = 0x3fffffff;


int main(void) {
    //problem: cf#200, address:
    int n, y, last = -1, ans = 1;
    string x;
    cin >> n;
    while(n--) {
        cin >> x;
        if(x == "10") y = 10;
        else y = 1;
        if(last != -1 && y != last) ans++;
        last = y;
    }
    cout << ans << endl;
    return 0;
}

B題：

題意：給定三個原子編號（A,B,C)，每個原子一個化學價表示要與其他原子相連接的化學鍵個數（然而圖沒有給好，誤導了大量時間）解法：只要知道A和B原子之間的化學鍵個數x，其它兩條邊的原子個數都可以用含有x的式子表示出來，再來檢驗是否滿足原子價要求即可。

代碼：

#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long int LL;
const int M = 100009,INF = 0x3fffffff;


int main(void) {
    //problem:cf#200 , address:
    int a, b, c;
    cin >> a >> b >> c;
    bool ok = false;
    for(int i = 0; i <= b; i++) {
        if(b - i == c - (a - i)) {
            ok = true;
            cout << i << " " << b - i << " "<< a - i << endl;
            break;
        }
    }
    if(!ok) cout << "Impossible" << endl;
    return 0;
}

C題：

題意：給定無限制個單位電阻，每一次操作可給當前電路並聯或者串聯一個單位電阻，求達到目標阻值（為一假分數的形式）的電阻所需要的最小操作次數。思路：開始的想法是從一個單位電阻開始，用廣度優先搜索遍歷出目標解的最小次數，然而這種正向求解空間是2的指數級別大小必定爆隊列或者超時。然後決定由答案開始倒著推到初始狀態，顯然大大減少了解空間大小。有時候從目標解出發倒著推，是非常良好的思路可以大大縮減解空間大小。下午周賽A題就用了這個思想，順利做出。注意：這個題中數據用的long long 然而我只是讀入的兩個數據用的long long 中間計算用到的數據卻還是int 一直WA，細節。

代碼：

#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long int LL;
const int M = 100009,INF = 0x3fffffff;
LL a, b, ans;


void dfs(LL x, LL y) {
    if(y == 0) return;
    ans += x / y;
    x %= y;
    swap(x, y);
    dfs(x, y);
}

int main(void) {
    //problem: cf#200, address:
    cin >> a >> b;
    dfs(a, b);
    cout << ans << endl;
    return 0;
}

D題：

題意：纏繞的繩子，問是否能夠解開？思路：只要兩個連著的覆蓋都是同樣的一根線，這兩個覆蓋就可以直接消除。這樣很容易用一個棧一邊讀取一邊模擬實現。

代碼：


#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long int LL;
const int M = 100009,INF = 0x3fffffff;


int main(void) {
    //problem: , address:
    char c;
    stack s;
    while ((c = getchar()) != '\n') {
        int x = (c == '+' ? 1 : -1);
        if(s.empty()) {s.push(x); continue;}
        if(x == s.top()) s.pop();
        else s.push(x);
    }
    cout << (s.empty() ? "Yes" : "No") << endl;
    return 0;
}