Problem A
分兩種情況：
-
本身就不在
內(nèi)：直接輸出d
- 否則贬蛙，輸出第一個(gè)大于r的d的倍數(shù)窘游。也就是
d * (r / d + 1)
時(shí)間復(fù)雜度為
#include <cstdio>
using namespace std;
typedef long long LL;
int main()
{
int q;
scanf("%d", &q);
while(q--)
{
LL l, r, d;
scanf("%lld%lld%lld", &l, &r, &d);
if((d < l) || (d > r))
{
printf("%lld\n", d);
continue;
}
printf("%lld\n", d * (r / d + 1));
}
return 0;
}
Problem B
先去掉多余的字符。只保留[贡定，]，:，|這四種字符买优。
然后找最靠左的[:（兩個(gè)字符可以不用緊鄰，下同）和最靠右的:]挺举，然后再其中間找出所有的|杀赢，拼起來(lái)就是答案的字符串了。輸出長(zhǎng)度即可湘纵。
注意[:]的情況脂崔，這種情況是非法的。
時(shí)間復(fù)雜度為
#include <iostream>
#include <string>
using namespace std;
typedef long long LL;
bool CheckChr(char &c)
{
if(c == '[')return true;
if(c == ']')return true;
if(c == ':')return true;
if(c == '|')return true;
return false;
}
int FindL(string &s)
{
int pos = 0;
while(pos < s.length())
{
if(s[pos] == '[')break;
pos++;
}
while(pos < s.length())
{
if(s[pos] == ':')break;
pos++;
}
return pos;
}
int FindR(string &s)
{
int pos = s.length() - 1;
while(pos >= 0)
{
if(s[pos] == ']')break;
pos--;
}
while(pos >= 0)
{
if(s[pos] == ':')break;
pos--;
}
return pos;
}
int GetAns(string &s, int l, int r)
{
if(l >= r)return -1;
int ans = 4;
for(int i = l + 1; i < r; I++)
{
if(s[i] == '|')ans++;
}
return ans;
}
int main()
{
string s;
while(cin >> s)
{
string tmp;
for(int i = 0; i < s.length(); I++)
{
if(CheckChr(s[I]))
{
tmp += s[I];
}
}
s = tmp;
cout << GetAns(s, FindL(s), FindR(s)) << endl;
}
return 0;
}
Problem C
思路的出發(fā)點(diǎn)類(lèi)似于區(qū)間覆蓋的貪心算法梧喷。
首先砌左，對(duì)區(qū)間按左值從小到大排序。
然后將第一個(gè)區(qū)間（也就是最左邊的區(qū)間）放入集合1铺敌，從左往右遍歷：
- 若當(dāng)前區(qū)間與集合1相交汇歹，那么將其放入集合1中
- 否則說(shuō)明從當(dāng)前區(qū)間開(kāi)始往右的區(qū)間都不會(huì)跟集合1相交，將包括當(dāng)前區(qū)間在內(nèi)的剩余區(qū)間置入集合2
于是我們就可以得到一種分割方法偿凭。
當(dāng)然产弹，如果這樣掃一遍發(fā)現(xiàn)所有區(qū)間都在集合1的話，直接輸出-1弯囊。
時(shí)間復(fù)雜度為
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct node
{
int pos;
int l ,r;
int ans;
node(int _pos = 0, int _l = 0, int _r = 0, int _ans = 0)
{
pos = _pos;
l = _l;
r = _r;
ans = _ans;
}
bool operator < (const node &p)const
{
if(l != p.l)
{
return l < p.l;
}
return r < p.r;
}
};
bool cmp (const node &a, const node &b)
{
return a.pos < b.pos;
}
vector<node> v;
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
v.clear();
int n;
scanf("%d", &n);
for(int i = 0; i < n; I++)
{
int a, b;
scanf("%d%d", &a, &b);
v.push_back(node(i, a, b));
}
sort(v.begin(), v.end());
int pos = -1;
int r = v[0].r;
for(int i = 1; i < n; I++)
{
if(v[i].l > r)
{
pos = I;
break;
}
r = max(r, v[i].r);
}
if(pos == -1)
{
printf("-1\n");
continue;
}
for(int i = 0; i < n; I++)
{
if(i < pos)v[i].ans = 1;
else v[i].ans = 2;
}
sort(v.begin(), v.end(), cmp);
for(int i = 0; i < n; I++)
{
if(i)printf(" ");
printf("%d", v[i].ans);
}
printf("\n");
}
return 0;
}
Problem D
做完之后看了一下官方題解痰哨，官方題解貌似是樹(shù)分治肛過(guò)去的胶果。這里提供另外一種可以卡過(guò)去的方法。
首先顯然可以得出一個(gè)結(jié)論：最長(zhǎng)鏈上所有點(diǎn)的權(quán)值必定是同一個(gè)質(zhì)數(shù)的倍數(shù)斤斧。
那么問(wèn)題的重心便可以放在質(zhì)數(shù)上早抠。一個(gè)簡(jiǎn)單的思路是，枚舉所有在中的質(zhì)數(shù)撬讽，對(duì)于每個(gè)質(zhì)數(shù)而言蕊连，有些點(diǎn)包含這個(gè)質(zhì)數(shù)（標(biāo)記為1），有些點(diǎn)則不包含這個(gè)質(zhì)數(shù)（標(biāo)記為0）锐秦。那么問(wèn)題便可以轉(zhuǎn)化為咪奖，給定一個(gè)權(quán)值只有0和1的樹(shù)，找出最長(zhǎng)的全是1的鏈酱床。這個(gè)問(wèn)題是一個(gè)簡(jiǎn)單的樹(shù)DP羊赵，可以在
內(nèi)解決。但由于在
中的質(zhì)數(shù)過(guò)多（差不多是
個(gè)）扇谣，所以直接做肯定是超時(shí)的昧捷。
于是考慮縮減區(qū)間范圍。注意到當(dāng)質(zhì)數(shù)大于
的時(shí)候罐寨，節(jié)點(diǎn)中權(quán)值為質(zhì)數(shù)
的倍數(shù)的點(diǎn)的權(quán)值分解質(zhì)因數(shù)之后靡挥，其最大的質(zhì)因數(shù)只可能是
。
于是便可以將這個(gè)區(qū)間分成兩個(gè)區(qū)間來(lái)解決：
- 枚舉區(qū)間
中的質(zhì)數(shù)鸯绿，套用上述的方法跋破。時(shí)間復(fù)雜度為
。
- 對(duì)于另外的部分
：
- 枚舉區(qū)間
- 經(jīng)過(guò)第一步的處理之后，所有的點(diǎn)的權(quán)值要么是1男窟，要么就是區(qū)間
的時(shí)間內(nèi)找到這顆樹(shù)上除了1以外所有權(quán)值相同的鏈，取最長(zhǎng)即可歉眷。
- 枚舉區(qū)間
總的時(shí)間復(fù)雜度為牺六。
雖然基本上是卡著時(shí)間過(guò)的就是了
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
struct PrimeList
{
bool vis[200005];
vector<int> List;
int maxa;
void init(int _maxa)
{
maxa = _maxa;
memset(vis, 0, sizeof(vis));
List.clear();
for(int i = 2; i <= maxa; i++)
{
if(!vis[i])
{
List.push_back(i);
for(int j = 2; j * i <= maxa; j++)
{
vis[j * i] = true;
}
}
}
}
bool Find(int &a)
{
if(a * a <= maxa)
{
return false;
}
int l = 0, r = List.size() - 1;
while(r > l)
{
int mid = (l + r) >> 1;
if(List[mid] < a)
{
l = mid + 1;
}
else
{
r = mid;
}
}
return a == List[l];
}
}P;
struct Tree
{
int w[200005];
vector<int> e[200005];
int n;
int dp[200005];
int ans[200005];
bool vis[200005];
void init(int _n)
{
n = _n;
for(int i = 1; i <= n; i++)
{
w[i] = 0;
e[i].clear();
}
memset(vis, 0, sizeof(vis));
}
int dfs(int g, int pos = 1, int prt = -1, bool isUni = false)
{
dp[pos] = 0;
ans[pos] = 0;
if(isUni)
{
if(w[pos] != g)
{
return dp[pos];
}
vis[pos] = true;
}
for(int i = 0; i < e[pos].size(); i++)
{
if(e[pos][i] == prt)
{
continue;
}
dfs(g, e[pos][i], pos, isUni);
dp[pos] = max(dp[pos], dp[e[pos][i]]);
}
if(w[pos] % g == 0)
{
priority_queue< int, vector<int>, greater<int> > q;
for(int i = 0; i < e[pos].size(); i++)
{
if(e[pos][i] == prt)
{
continue;
}
q.push(ans[e[pos][i]]);
if(q.size() > 2)
{
q.pop();
}
}
if(q.size() > 0)
{
ans[pos] = q.top() + 1;
q.pop();
if(q.size() > 0)
{
dp[pos] = max(dp[pos], ans[pos] + q.top());
ans[pos] = q.top() + 1;
}
else
{
dp[pos] = max(dp[pos], ans[pos]);
}
}
else
{
ans[pos] = 1;
dp[pos] = max(dp[pos], 1);
}
}
//printf("dp[%d] = %d[%d]\n", pos, dp[pos], ans[pos]);
return dp[pos];
}
}T;
int main()
{
int n;
while(~scanf("%d", &n))
{
T.init(n);
int maxa = 0;
for(int i = 1; i <= n; i++)
{
int a;
scanf("%d", &a);
T.w[i] = a;
maxa = max(maxa, a);
}
for(int i = 1; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
T.e[u].push_back(v);
T.e[v].push_back(u);
}
P.init(maxa);
int ans = 0;
for(int i = 0; (i < P.List.size()) && (P.List[i] * P.List[i] <= maxa); i++)
{
//printf("%d %d\n", ans, P.List[i]);
ans = max(ans, T.dfs(P.List[i]));
//printf("*%d\n", ans);
for(int j = 1; j <= n; j++)
{
while(T.w[j] % P.List[i] == 0)
{
T.w[j] /= P.List[i];
}
}
}
for(int i = 1; i <= n; i++)
{
if(T.vis[i])
{
continue;
}
if(P.Find(T.w[i]))
{
ans = max(ans, T.dfs(T.w[i], i, -1, true));
}
}
printf("%d\n", ans);
}
return 0;
}
Problem E
首先，不管是wallet還是bill都強(qiáng)制翻轉(zhuǎn)成（
）的形式汗捡。
然后淑际，對(duì)于每個(gè)輸入，如果是bill的話就去更新和
的最大值，否則就拿輸入的
和
分別跟當(dāng)前的
和
的最大值比較得到答案庸追。
時(shí)間復(fù)雜度為。
PS：這E題活的跟道簽到題似的噗台囱。淡溯。
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int x = 0, y = 0;
int n;
scanf("%d", &n);
while(n--)
{
char s[5];
int px, py;
scanf("%s%d%d", s, &px, &py);
if(px > py)
{
swap(px, py);
}
if(s[0] == '+')
{
x = max(x, px);
y = max(y, py);
}
else
{
if((x > px) || (y > py))
{
printf("NO\n");
}
else
{
printf("YES\n");
}
}
}
return 0;
}
