Problem A
逐個(gè)判斷即可。
時(shí)間復(fù)雜度為。
#include <bits/stdc++.h>
using namespace std;
string s[10];
int main()
{
for(int i = 0; i < 6; I++)
cin >> s[i];
bool ans = false;
for(int i = 1; i < 6; I++)
{
if(s[0][0] == s[i][0] || s[0][1] == s[i][1])
{
ans = true;
break;
}
}
if(ans)
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
Problem B
注意到最大只有15,故可以使用暴力來解決。
直接枚舉所有可能性,逐個(gè)嘗試即可。
使用位運(yùn)算實(shí)現(xiàn)枚舉可以比較便利地枚舉完所有的情況。
當(dāng)然,DFS也是可以的。
時(shí)間復(fù)雜度為。
#include <bits/stdc++.h>
using namespace std;
bool check(int a[], int n, int bitmp)
{
int ans = 0;
for(int i = 0; i < n; i++)
{
if(bitmp & 1)
ans += a[i];
else
ans -= a[i];
bitmp >>= 1;
}
return ans % 360 == 0;
}
int main()
{
int a[20], n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
bool ans = false;
for(int bitmp = 0; bitmp < (1 << n); bitmp++)
{
ans |= check(a, n, bitmp);
if(ans)
break;
}
if(ans)
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
Problem C
檢查括號(hào)是否匹配這個(gè)使用棧便可以解決,這里假設(shè)大家已經(jīng)知道如何檢查括號(hào)匹配。
大致思想是將字符串分類,然后按類進(jìn)行匹配。
字符串大致可以分為四類:
- 自己就已經(jīng)是匹配的,例如
(),(()),()(()) - 需要在右邊再添加k個(gè)右括號(hào)才能匹配的(簡(jiǎn)稱
mpL[k]),例如((還差一個(gè)),(()(還差一個(gè)),()(()((還差兩個(gè)) - 需要在左邊再添加k個(gè)左括號(hào)才能匹配的(簡(jiǎn)稱
mpR[k]) - 無法在只拼接一個(gè)括號(hào)字符串之后就能匹配的,例如
)(
分類的話,只需要將用棧檢查括號(hào)匹配的算法稍微修改一下就可以做了(具體
參照代碼的Caclu函數(shù))
分類完畢之后,匹配的方案如下:
- 對(duì)于每個(gè)k而言,mpL[k]和mpR[k]匹配(也就是取兩者計(jì)數(shù)最小值)
- 對(duì)于自己就已經(jīng)是匹配的而言(在代碼中為
mpR[0]),在這個(gè)集合內(nèi)匹配就行了(也就是取計(jì)數(shù)除以2)
這里分類使用map實(shí)現(xiàn),故時(shí)間復(fù)雜度為
//#define TEST
#include <bits/stdc++.h>
using namespace std;
map<int, int> mpL, mpR;
void Caclu(string &s)
{
#ifdef TEST
cout << "Begin: " << s << endl;
#endif
int stk = 0;
for(int i = 0; i < s.length(); i++)
{
if(s[i] == '(')
stk++;
else
stk--;
if(stk < 0)
break;
}
if(stk > 0)
{
mpL[stk]++;
#ifdef TEST
cout << "L: " << stk << endl;
#endif
}
stk = 0;
for(int i = s.length() - 1; i >= 0; i--)
{
if(s[i] == ')')
stk++;
else
stk--;
if(stk < 0)
break;
}
if(stk >= 0)
{
mpR[stk]++;
#ifdef TEST
cout << "R: " << stk << endl;
#endif
}
}
int main()
{
mpL.clear();
mpR.clear();
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
string s;
cin >> s;
Caclu(s);
}
int ans = 0;
map<int, int>::iterator it;
for(it = mpL.begin(); it != mpL.end(); it++)
{
ans += min(it->second, mpR[it->first]);
}
ans += mpR[0] / 2;
cout << ans << endl;
return 0;
}
Problem D
首先考慮一個(gè)簡(jiǎn)化版的問題:假設(shè)n為某個(gè)質(zhì)數(shù)p的a次冪。求問題的解。
這個(gè)的話可以直接dp就行了。假設(shè)dp[a][k]為當(dāng)n為p的a次冪的時(shí)候的解。
于是就有:
這個(gè)dp的時(shí)間復(fù)雜度為,也就是
那么對(duì)于復(fù)雜版本的,n為任意正整數(shù)的情況。
首先我們假設(shè)答案為。
由于作者能力有限,無法給出一個(gè)詳細(xì)且嚴(yán)謹(jǐn)?shù)淖C明。不過可以通過小范圍數(shù)據(jù)打表發(fā)現(xiàn),當(dāng)k固定的時(shí)候,為積性函數(shù)。
于是我們可以把n分解質(zhì)因數(shù),得到
于是就有:
至于每一個(gè)分解出來的函數(shù),就是上面的簡(jiǎn)化版問題了。直接按照上面的計(jì)算即可。
至于在下的除法的話,逆元即可。
不過由于魔導(dǎo)書(Code Template)不知道被我扔哪里去了,所以只能自己手敲逆元。
分解質(zhì)因數(shù)需要的時(shí)間,故總的時(shí)間復(fù)雜度為
#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
void exgcd(LL a, LL b, LL &x, LL &y)
{
if(b == 0)
{
x = 1;
y = 1;
return;
}
LL px, py;
exgcd(b, a%b, px, py);
x = py;
y = px - (a / b) * py;
}
LL inv(LL a)
{
LL x, y;
exgcd(a, mod, x, y);
return ((x % mod) + mod) % mod;
}
map<LL, int> cnt;
void Analysis(LL n)
{
for(LL i = 2; i * i <= n; i++)
{
while(n % i == 0)
{
cnt[i]++;
n /= i;
}
}
if(n != 1)
{
cnt[n]++;
}
}
LL Solve(LL n, LL k)
{
LL ret = 1;
Analysis(n);
map<LL, int>::iterator it = cnt.begin();
for(; it != cnt.end(); it++)
{
vector<LL> v;
v.push_back(1LL);
for(int i = 0; i < it->second; i++)
{
v.push_back((v[v.size()-1] * it->first) % mod);
}
for(int i = 0; i < k; i++)
{
for(int j = 1; j < v.size(); j++)
{
v[j] = (v[j] + v[j-1]) % mod;
}
for(int j = 1; j < v.size(); j++)
{
v[j] *= inv(j + 1);
v[j] %= mod;
}
}
ret = (ret * v[v.size()-1]) % mod;
}
return ret;
}
int main()
{
LL n, k;
cin >> n >> k;
cout << Solve(n, k) << endl;
return 0;
}
Problem E
首先,這題我寫不出來的orz。。這題到最后迫不得已只能放棄思考,對(duì)著官方題解思考許久,才發(fā)現(xiàn)自己連題都讀錯(cuò)了orz
所以下面的題解基本上等于官方題解的翻譯版。如果啃過官方題解的話會(huì)發(fā)現(xiàn)下面這個(gè)基本等于把官方題解復(fù)讀一遍orz
大致的題意是,給定一個(gè)n個(gè)數(shù)的排列,將其拆分為k個(gè)單調(diào)的子序列。
這里很多人會(huì)讀錯(cuò)然后認(rèn)為求的是令k盡可能小的結(jié)果(為了下文描述方便,這里將盡可能小的問題簡(jiǎn)稱為最小拆分),然后想了賊久百思不得其解最后放棄。
但是這里的k其實(shí)并不需要盡可能小,而是只需要小于等于即可。
其中關(guān)于的定義如下:
n個(gè)數(shù)的所有排列中,每個(gè)排列可以拆分的最少的單調(diào)子序列數(shù),這些數(shù)的最大值定義為
這個(gè)事實(shí)上是一道結(jié)論題。它需要基于如下結(jié)論:
設(shè)正整數(shù)
滿足
,則有
顯然滿足條件的k是唯一的。
這個(gè)結(jié)論事實(shí)上由兩部分構(gòu)成:
- 當(dāng)
時(shí),總會(huì)有一個(gè)n的排列使其最小拆分必定大于等于k
- 當(dāng)
時(shí),所有的n的排列的最小拆分必定小于k(換言之,最大為k-1)
這里分別給出這兩個(gè)部分的不嚴(yán)謹(jǐn)證明:
結(jié)論一證明
對(duì)于存在性結(jié)論的話,只需要給出一個(gè)構(gòu)造方法即可。
這里假設(shè)n=10,k=4。那么可以給出如下序列:
注意到這個(gè)序列是有規(guī)律的。這也是當(dāng)n恰好等于時(shí)的構(gòu)造策略。此時(shí)顯然的,該序列的最小拆分是4。剛好為k。
那么當(dāng)出現(xiàn)n不恰好為的情況的話,只需要找到最大的滿足
的k,然后將前k個(gè)數(shù)按如上規(guī)律構(gòu)造,剩下的數(shù)堆到后面即可。
具體的可以自己嘗試一下。
結(jié)論二證明
首先對(duì)n的排列求LIS(最長(zhǎng)上升子序列)。于是就會(huì)有兩種情況:
- LIS的長(zhǎng)度大于等于k
- LIS的長(zhǎng)度小于k
對(duì)于第一種情況,將這個(gè)LIS中從原序列中去掉,于是原序列的數(shù)字個(gè)數(shù)變?yōu)樾∮?img class="math-inline" src="https://math.jianshu.com/math?formula=%7B%5Cfrac%20%7Bk(k-1)%7D%20%7B2%7D%7D" alt="{\frac {k(k-1)} {2}}" mathimg="1">個(gè)。這個(gè)問題其實(shí)就是原問題的版本。遞歸求證即可。
對(duì)于第二種情況,我們可以使用求LIS的方法構(gòu)造出個(gè)數(shù)等于LIS長(zhǎng)度的遞減序列。由于序列數(shù)等于LIS長(zhǎng)度,故小于k。命題得證。
這里重點(diǎn)說一下如何構(gòu)造吧。前提是需要懂得LIS的求法。
首先,類比LIS求法需要構(gòu)造一個(gè)用來存中間結(jié)果的數(shù)組一樣,這里同樣需要構(gòu)造一個(gè)二維數(shù)組
(事實(shí)上更像是兩重
vector)。
然后遍歷原序列,對(duì)于每個(gè)數(shù)而言:
- 如果二維
vector全空,或者對(duì)于二維
vector中的每個(gè)小vector的最后一個(gè)數(shù)都小于
,那么新建一個(gè)
vector,其僅存入元素,并將這個(gè)
vector尾部插入至二維vector中
- 否則,二分查找到所有尾部元素小于
的
vector的最大值,在這個(gè)vector中尾部插入
事實(shí)上這個(gè)過程就是保留歷史數(shù)據(jù)的LIS的求法。到最后每個(gè)
vector的尾部元素連起來就是原序列的LIS了。故通過這樣分割的遞減序列的個(gè)數(shù)肯定跟LIS的長(zhǎng)度一致。
運(yùn)用結(jié)論解題
事實(shí)上結(jié)論二的證明思路就是一個(gè)構(gòu)造思路了。對(duì)于任意序列,按照結(jié)論二的證明思路構(gòu)造即可得到答案。
總的時(shí)間復(fù)雜度為(我甚至不知道為啥這么爆炸的復(fù)雜度都能卡過去orz)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <ctime>
using namespace std;
typedef long long LL;
// 為了之后方便復(fù)用,把求LIS的過程抽成單獨(dú)的模塊
struct LIS
{
int w[100005];
int prt[100005];
int dp[100005];
int dp_pos[100005];
int n, top;
bool isInc;
bool check(int a, int b)
{
return (a > b) ^ isInc;
}
void Init(bool _isInc)
{
n = 0;
top = 0;
isInc = _isInc;
}
void Update(int a)
{
w[n] = a;
int l = 0, r = top - 1;
while(l < r)
{
int mid = (l + r) >> 1;
if(check(dp[mid], a))
{
l = mid + 1;
}
else
{
r = mid;
}
}
if((top == 0) || check(dp[l], a))
{
dp[top] = a;
dp_pos[top] = n;
if(top == 0)
{
prt[n] = n;
}
else
{
prt[n] = dp_pos[top - 1];
}
top++;
}
else
{
dp[l] = a;
dp_pos[l] = n;
if(l == 0)
{
prt[n] = n;
}
else
{
prt[n] = dp_pos[l - 1];
}
}
n++;
}
void Generate(vector<int> &ret)
{
int pos = dp_pos[top - 1];
ret.clear();
while(true)
{
ret.push_back(w[pos]);
if(prt[pos] == pos) break;
pos = prt[pos];
}
reverse(ret.begin(), ret.end());
}
}L;
bool vis[100005];
int a[100005];
vector< vector<int> > ans;
void Solve()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
memset(vis, 0, sizeof(vis));
ans.clear();
int cnt = 0;
while(cnt < n)
{
vector<int> ret;
L.Init(true);
for(int i = 0; i < n; i++)
{
if(vis[a[i]]) continue;
L.Update(a[i]);
}
L.Generate(ret);
int k = sqrt((n - cnt) * 2);
k -= 3;
k = max(0, k);
while((k * (k + 1)) / 2 <= (n - cnt))k++;
if(ret.size() >= k)
{
for(int i = 0; i < ret.size(); i++)
{
vis[ret[i]] = true;
}
ans.push_back(ret);
cnt += ret.size();
}
else
{
vector< vector<int> > pans;
for(int i = 0; i < n; i++)
{
if(vis[a[i]]) continue;
int l = 0, r = pans.size() - 1;
while(l < r)
{
int mid = (l + r) >> 1;
int pos = pans[mid].size() - 1;
if(pans[mid][pos] < a[i])
{
l = mid + 1;
}
else
{
r = mid;
}
}
if((pans.size() == 0) || (pans[l][pans[l].size() - 1] < a[i]))
{
vector<int> v;
v.push_back(a[i]);
pans.push_back(v);
}
else
{
pans[l].push_back(a[i]);
}
}
for(int i = 0; i < pans.size(); i++)
{
ans.push_back(pans[i]);
}
break;
}
}
printf("%d\n", (int)ans.size());
for(int i = 0; i < ans.size(); i++)
{
printf("%d", (int)ans[i].size());
for(int j = 0; j < ans[i].size(); j++)
{
printf(" %d", ans[i][j]);
}
printf("\n");
}
}
int main()
{
srand(time(NULL));
int t;
scanf("%d", &t);
while(t--)
{
Solve();
}
return 0;
}
Problem F
由于答案只需要0和1。故對(duì)于每一個(gè)多重集合而言,我們都可以表示成一個(gè)長(zhǎng)度為的
bitset。這是一個(gè)最直接的想法。
基于這個(gè)想法我們便可以直接擬出其他步驟的實(shí)現(xiàn):
- 對(duì)于步驟4而言,我們就可以直接取第x個(gè)
bitset中的第v位(這里記為)。
- 對(duì)于步驟1而言,我們只需要賦一個(gè)只有第v位為1的
bitset就行了。 - 對(duì)于步驟2而言,模2下的加法事實(shí)上就是異或(可以自己嘗試一下)
- 比較棘手的事步驟3。直接模擬的話時(shí)間復(fù)雜度是
的級(jí)別。這顯然是超時(shí)的。
對(duì)于步驟3,我們考慮能否使用更快的計(jì)算方法。
一個(gè)顯然的思路就是容斥。當(dāng)我們求新的集合的第v位的時(shí)候,事實(shí)上就是在求原來兩個(gè)集合的元素中g(shù)cd為v的數(shù)對(duì)數(shù)。這個(gè)顯然可以使用兩個(gè)集合的元素中g(shù)cd為【v的倍數(shù)】的數(shù)對(duì)數(shù)來容斥。后者就很容易計(jì)算了。
設(shè)第x個(gè)bitset中值為v的倍數(shù)的數(shù)的個(gè)數(shù)為。那么兩個(gè)集合的元素中g(shù)cd為【v的倍數(shù)】的數(shù)對(duì)數(shù)顯然就是
。也就是說,如果要使用這個(gè)方法的話還需要再維護(hù)一系列表示
的
bitset,而且這個(gè)容斥的計(jì)算時(shí)間復(fù)雜度其實(shí)也不低(其實(shí)還是)。
但是這個(gè)方法的副產(chǎn)物是可以使用的。首先,
的定義總結(jié)一下就是:
我們可以通過簡(jiǎn)單的莫比烏斯反演來得到如下式子:
也就是說,如果我們只維護(hù)的話,可以在需要某個(gè)
的時(shí)候通過莫比烏斯反演在
的時(shí)間內(nèi)計(jì)算得出。
那么四個(gè)步驟的計(jì)算方法就需要做一點(diǎn)改變:
- 對(duì)于步驟1,需要使用類似根號(hào)試除法的方法來初始化集合x。時(shí)間復(fù)雜度為
- 對(duì)于步驟2,同樣還是對(duì)應(yīng)位置的元素相加即可,在模2下的計(jì)算就是異或。時(shí)間復(fù)雜度為
- 對(duì)于步驟3,可以發(fā)現(xiàn)其實(shí)只需要將對(duì)應(yīng)位置的元素相乘就行了,在模2下的計(jì)算就是與運(yùn)算。時(shí)間復(fù)雜度為
- 對(duì)于步驟4,可以使用莫比烏斯反演來計(jì)算。時(shí)間復(fù)雜度為
總的時(shí)間復(fù)雜度為,似乎還不夠理想。
但事實(shí)上我們按照前面的存bitset的思想的話,我們可以使用bitet的整體計(jì)算來壓縮常數(shù)。例如說步驟2和步驟3其實(shí)就是兩個(gè)bitset直接進(jìn)行運(yùn)算。時(shí)間復(fù)雜度雖然還是,但是常數(shù)縮小到
的量級(jí)下。大致估算一下可以卡過去。
對(duì)于步驟4而言。我們也需要盡可能得轉(zhuǎn)換成兩個(gè)bitset直接計(jì)算。由于v的取值只有最多7000種。我們可以將莫比烏斯函數(shù)進(jìn)一步處理成7000個(gè)不同的bitset用于在不同的v值下使用。于是答案就可以變成兩個(gè)bitset相乘(與運(yùn)算),得到新的bitset,然后對(duì)新的bitset進(jìn)行count計(jì)算。這樣步驟4的常數(shù)也壓下去了。(這一部分不懂的話可以看一下代碼里的init函數(shù)和Get函數(shù))
這么做的總空間復(fù)雜度為。
#include <cstdio>
#include <cstring>
#include <bitset>
using namespace std;
bitset<7005> a[100005], mu[7005];
bool check[7005];
int prime[7005];
void init()
{
memset(check, 0, sizeof(check));
mu[1][1] = 1;
int tot = 0;
for(int i = 2; i <= 7000; i++)
{
if(!check[i])
{
prime[tot++] = i;
mu[1][i] = 1;
}
for(int j = 0; j < tot; j++)
{
if(i * prime[j] > 7000)
{
break;
}
check[i * prime[j]] = true;
if(i % prime[j] == 0)
{
mu[1][i * prime[j]] = 0;
break;
}
else
{
mu[1][i * prime[j]] = mu[1][i];
}
}
}
for(int i = 2; i <= 7000; i++)
{
for(int j = 1; j * i <= 7000; j++)
{
mu[i][j * i] = mu[1][j];
}
}
}
void Set(int x, int v)
{
a[x].reset();
for(int i = 1; i * i <=v; i++)
{
if(v % i != 0)
{
continue;
}
int j = v / i;
a[x][i] = a[x][i] ^ 1;
if(j != i)
{
a[x][j] = a[x][j] ^ 1;
}
}
}
int Get(int x, int v)
{
bitset<7005> bs = mu[v] & a[x];
int ret = bs.count();
ret = ((ret % 2) + 2) % 2;
return ret;
}
int main()
{
init();
int n, q;
scanf("%d%d", &n, &q);
while(q--)
{
int k;
scanf("%d", &k);
if(k == 1)
{
int x, v;
scanf("%d%d", &x, &v);
Set(x, v);
}
else if(k == 2)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
a[x] = a[y] ^ a[z];
}
else if(k == 3)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
a[x] = a[y] & a[z];
}
else
{
int x, v;
scanf("%d%d", &x, &v);
printf("%d", Get(x, v));
}
}
printf("\n");
return 0;
}