Educational Codeforces Round 153 (Rated for Div. 2)

A. Not a Substring

題目大意

給定一個只包含“（”和“）”這兩個符號的字符串s，假設長度為n，返回一個不包含字符串s、長度為2n且滿足運算規則的括號序列（意思就是“（”與“）”按順序相對應）
翻譯：

括號序列是由字符’(‘和/或’)'組成的字符串。常規括號序列是一種可以通過在序列的原始字符之間插入字符“1”和“+”來轉換成正確算術表達式的括號序列。例如:

括號序列“()()”和“(())”是正則序列(它們可以分別轉換為“(1)+(1)”和“(1+1)+1)”);括號序列“)(”、“(”和“)”不是正則序列。
給你一個括號序列s;我們定義它的長度為n。你的任務是找到一個長度為2n的正則括號序列t，使得s不作為連續子串出現在t中，或者報告不存在這樣的序列。

輸入 第一行包含一個整數t(1≤t≤1000)——測試用例的數量。

每個測試用例的唯一一行包含一個字符串s(2≤|s|≤50)，由字符“(”和/或“)”組成。

輸出
對于每個測試用例，打印它的答案。如果沒有需要的常規括號序列，則在單獨一行中打印no。否則，在第一行打印YES，在第二行打印所需的常規括號序列t。如果有多個答案-您可以打印其中的任何一個。

思路

簡單構造一下兩種情況：
第一種是類似于“（）（）（）（）”
第二種是類似于“（（（（））））”
稍微判斷一下，一種不行就輸出另外一種，還有一個特殊情況，當s為“（）”時無解
特殊判斷輸出即可

核心代碼

void solve()
{string s;cin>>s;int n;n=s.size();if(n==2&&s[0]=='('&&s[1]==')'){printf("NO\n");return ;}bool pd=1;int zhizhen=0;while(s[zhizhen]=='('&&zhizhen<n)zhizhen++;while(s[zhizhen]==')'&&zhizhen<n)zhizhen++;if(zhizhen==n)pd=1;else pd=0;if(pd){cout<<"YES\n";for(int i=0;i<n;++i)cout<<"()";cout<<endl;}else{cout<<"YES\n";for(int i=0;i<n;++i)cout<<"(";for(int i=0;i<n;++i)cout<<")";cout<<endl;}
}

B. Fancy Coins

題目大意

一共有兩種硬幣，第一種硬幣價值1，第二種硬幣價值k，現在有第一種a1個，第二種ak個，現在想要湊出價值m，問最少需要額外購買硬幣個數
翻譯：

Monocarp將以m個burles的價格進行購買。

他有兩種硬幣，數量如下:

價值1個泡泡的硬幣:a1枚普通硬幣和無限多的花哨硬幣;價值k個泡泡的硬幣:ak枚普通硬幣和無限多的花哨硬幣。
Monocarp希望以一種沒有變化的方式進行購買——提供的硬幣總價值正好是m。他可以使用普通硬幣和高級硬幣。然而，他想要花費盡可能少的花哨硬幣。

他可以用來購買物品的最小花式硬幣總數是多少?

輸入 第一行包含單個整數t(1≤t≤3?104)—測試用例的數量。

每個測試用例的唯一一行包含四個整數m、k、a1和ak(1≤m≤108;2
k≤≤108;0≤a1,ak≤108)-購買成本，第二種硬幣的價值和兩種硬幣的普通硬幣的數量。

輸出 對于每個測試用例，打印一個整數—Monocarp可以用于購買的花哨硬幣的最小總數。

思想

這道題也有O（1）的做法，但是當時懶得想了，直接二分答案，打表的過程中可以發現購買的硬幣數量是先增加后減少的，可以利用相鄰的兩個值做差尋找最小值

核心代碼

int check(int n)
{int zhi;zhi=max(n-b,0)+max((m-min(m/k,n)*k),a)-a;return zhi;
}
void solve()
{cin>>m>>k>>a>>b;if(a>m||a==m){cout<<"0\n";return;}int left=0,right=1e8+10;while(left<right){int mid=(left+right)>>1;if(check(mid)<check(mid+1))right=mid;else left=mid+1;}cout<<check(left)<<endl;return;
}

C. Game on Permutation

題目大意

兩個人 Alice 和 Bob 一起玩游戲，有一個長度為n的1~n的序列，任選一個開始的點，每一次只能選擇左邊一個比自己小的數字進行移動，兩人輪流移動，誰先無法移動或者是移動到最左邊的點為輸
翻譯：

愛麗絲和鮑勃在玩游戲。它們有一個大小為n的排列p(大小為n的排列是一個大小為n的數組其中每個元素從1到n
只發生一次)。它們還有一個芯片，可以放在排列中的任何元素上。

愛麗絲和鮑勃輪流走:愛麗絲走第一步，然后鮑勃走第二步，然后愛麗絲走第三步，以此類推。在第一步中，愛麗絲選擇排列中的任何元素并將籌碼放在該元素上。在接下來的每一次移動中，當前玩家必須將籌碼移動到任何同時在左側且嚴格小于當前元素的元素(即。如果芯片位于第i個元素上，則如果j<i且pj<pi)，則芯片可以移動到第j個元素上。如果一個玩家不能移動(根據游戲規則，移動籌碼是不可能的)，那么這個玩家就贏了游戲。

假設如果滿足以下條件，排列中的第i個元素是幸運的:

如果Alice在第一步時把籌碼放在第i個元素上，那么不管Bob怎么走，她都能贏。她有一個制勝策略)。 你必須計算這個排列中幸運元素的個數。

輸入 第一行包含一個整數t(1≤t≤104)——測試用例的數量。

每個測試用例的第一行包含單個整數n(1≤n≤3?105)，即排列中的元素個數。

第二行包含n個整數p1,p2，…，pn(1≤pi≤n)。所有的都是不同的。

n除以所有測試用例的和不超過3·105。

輸出 對于每個測試用例，打印一個整數——排列中幸運元素的數量。

思想

從左邊往右邊進行遍歷，如果當前的值是目前最小的，那么則個點肯定是不能是幸運點，如果比上一個幸運點的值要小，那么此時這個點就是幸運點。

核心代碼

void solve()
{int n,a;scanf("%d",&n);int minzhi=INT_MAX;bool win=0;int ans=0,winlose=n;for(int i=0;i<n;++i){int shuru;scanf("%d",&shuru);if(minzhi>shuru){minzhi=shuru;win=1;}else{win=(winlose<shuru);}if(!win){ans++;winlose=min(winlose,shuru);}}cout<<ans<<endl;
}