A.宇宙的终结
1签
题意
在$[1,100]$中给定的某个区间内找到一个数，它是$3$个不同素数的积。
解题思路
打出$100$以内素数表，然后暴力枚举判定。
手算也行，$100$以内答案只有$30,42,66,70,78$。
参考程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<ll> phi={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
bool pend(ll x){
ll cnt=0;
for(auto &p:phi){
if(x%p==0) { cnt++; x/=p; }
if(cnt>=3) break;
}if(x==1&&cnt==3) return true;
return false;
}
void solve()
{
ll l,r;cin >> l >> r;
FORLL(i,l,r) if(pend(i)) {cout << i << endl;return;}
cout << -1 << endl;
}
|
1
2
3
4
5
6
7
| vector<ll> ans={30,42,66,70,78};
void solve()
{
ll l,r;cin >> l >> r;
for(auto &x:ans) if(x>=l&&x<=r) {cout << x << endl;return;}
cout << "-1" << endl;
}
|
B.爱恨的纠葛
思维
题意
给定$2$个长度为$n$的数组$a,b$。调整$a$数组使得$|a_i-b_i|$的最小值最小。
解题思路
在$a,b$中分别找到一个数，它们的差的绝对值最小。
对数组$a$排序，在数组$a$中二分查找$b_i$的最近邻，记录差的绝对值最小的一对的下标$i,j$，最后把$a_i$和$a_j$交换使这一对在同一位置。
参考程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| void solve()
{
ll n,t;cin >> n;
vector<ll> a(n),b(n);
FORLL(i,0,n-1) cin >> a[i];
FORLL(i,0,n-1) cin >> b[i];
SORT(a);
ll mindif=INF,idxa=-1,idxb=-1;
FORLL(i,0,n-1)
{
auto it=upper_bound(ALL(a),b[i]);
if(it!=a.end())
{
t=abs(b[i]-*it);
if(t<mindif)
{
mindif=t;
idxa=i;
idxb=it-a.begin();
}
}
if(it!=a.begin())
{
it--;
t=abs(b[i]-*it);
if(t<mindif)
{
mindif=t;
idxa=i;
idxb=it-a.begin();
}
}
}
swap(a[idxa],a[idxb]);
FORLL(i,0,n-1) cout << a[i] << Presentation(i,n-1);
}
|
C.心绪的解剖
思维
题意
给定一个数$x$，问$x$是否可以表示为$3$个斐波那契数之和。
其中，斐波那契数指的是斐波那契数列$0,1,1,2,3,5\cdots$ 中的数。
解题思路
预处理$N$以内斐波那契数列，每次二分找到恰小于等于$x$的数，然后$x$减去这个数。
三次之后，如果$x$为$0$，则可以表示。
参考程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void preFeb(){
Feb.pb(0);
Feb.pb(1);
while(Feb.back()<=1e10){
Feb.pb(Feb[Feb.size()-1]+Feb[Feb.size()-2]);
}
}
void solve()
{
ll x;cin >> x;
vector<ll> ans(3,0);
FORLL(i,0,2){
auto it = --upper_bound(ALL(Feb),x);
ans[i] = *it;
x -= *it;
}
if(x) cout << -1 << endl;
else cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
}
|
D.友谊的套路
2签
题意
在五局三胜的游戏中，一方先胜$2$场，另一方再胜$3$场逆袭，这种情况叫做“让二追三”。
已知小红的胜率为$p$，求让二追三的概率。
解题思路
分小红让二追三和小红被让二追三两种情况。
参考程序
1
2
3
4
5
6
7
| void solve()
{
ld p;cin >> p;
ld np=1-p;
ld ans=p*p*np*np*np+np*np*p*p*p;
cout << fixed << setprecision(10) << ans << endl;
}
|
E.未来的预言
思维
题意
给定一个形如“BOx”的字符串，表示进行$x$局的游戏（$x$为奇数），赢得更多场次的队伍获胜。
另给一个字符串，表示每局胜利的队伍。
问第几局已经确定了胜负，或是还未确定。
解题思路
数数
参考程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| ll getnum(string s){
ll ret=0;
FORLL(i,2,s.length()-1){
ret*=10;
ret+=s[i]-'0';
}
return ret;
}
void solve()
{
string ts;cin >> ts;
string s; cin >> s;
ll tn=getnum(ts); tn/=2;
ll cntR=0,cntP=0;
ll n=s.length();
FORLL(i,0,n-1){
char c=s[i];
if(c=='R') cntR++;
else cntP++;
if(cntR>tn){
cout << "kou!" << endl << i+1 << endl;
return;
}else if(cntP>tn){
cout << "yukari!" << endl << i+1 << endl;
return;
}
}
cout << "to be continued." << endl << n << endl;
}
|
F.命运的抉择
思维
题意
给定一个长度为$n$的数组，把它分成非空的两部分$a,b$，使得从$a,b$中分别任取一个元素$a_i,b_j$，它们互质$gcd(a_i,b_j)=1$
解题思路
先在$a$中放置一个数，开一个set记录$a$中已存在的质数因子。
在剩余的数字中多次扫描，一旦某个数$x$能被$a$中的质数因子整除，就把它放入$a$中，直到某次扫描没有加入新的数字。
剩余的数字作为$b$。
时间复杂度比较抽象//
参考程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| vector<ll> GetFac(ll x){
vector<ll> ret;
ll i=0;
while(x>1){
if(check[x]){
if(x%prime[i]==0){
ret.pb(prime[i]);
while(x%prime[i]==0) x/=prime[i];
}
}else{ ret.pb(x); return ret; }
i++;
}return ret;
}
void solve()
{
ll n,t;cin >> n;
vector<vector<ll>> vFac;
vector<ll> v;
FORLL(i,1,n){
cin >> t;
v.push_back(t);
vFac.push_back(GetFac(t));
}
set<ll> st;
vector<int> sa(n,0);
sa[0]=1; t=1;
for(auto &x:vFac[0]) st.insert(x);
while(t){
t=0;
FORLL(i,0,n-1) if(sa[i]==0){
for(auto &x:vFac[i]) if(st.count(x)){
sa[i]=1; t++;
for(auto &y:vFac[i]) st.insert(y);
break;
}
}
}
vector<ll> a,b;
FORLL(i,0,n-1) if(sa[i]) a.pb(v[i]); else b.pb(v[i]);
if(b.size()==0) {cout << "-1 -1" << endl;return;}
ll na=a.size(),nb=b.size();
cout << na << ' ' << nb << endl;
FORLL(i,0,na-1) cout << a[i] << Presentation(i,na-1);
FORLL(i,0,nb-1) cout << b[i] << Presentation(i,nb-1);
}
|
G.人生的起落
构造
题意
形如$(a,b,a),a\gt b$的三元组称为“v-三元组”。
构造一个长度为$n$，和为$S$，且恰好有$k$个“v-三元组”的正整数数组。
解题思路
限定正整数，“v-三元组”至少为$(2,1,2)$。
依此开局特判：
- $n<k*2+1$：k个“v-三元组”最少需要$2k+1$个数。
- $S<n+k+1$：k个“v-三元组”最少需要$k+1$个$2$，其余为$1$，和至少为$n+k+1$。
构造方法是，先在最前的$k+1$个奇数位上放置尽可能大的数，然后在剩余的位置上放置$1$。若还有多余的数，放在第$k+1$个奇数位（$k*2+1$）上。
若$n$恰好等于$k*2+1$，则将多余的数放置在偶数位上，但偶数位上的数不能超过奇数位上的数。
参考程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| void solve()
{
ll n,S,k;cin >> n >> S >> k;
if(n==1){
if(k==0) cout << S << endl;
else cout << "-1\n";
return ;
}
if(n==2){
if(k==0) cout << S/2 << " " << S-S/2 << endl;
else cout << "-1\n";
return ;
}
if(k==0){
FORLL(i,1,n-1) cout << "1" << ' ';
cout << S-n+1 << endl;
return ;
}
if(n<2*k+1) {cout << "-1\n";return ;}
if(k&&S<n+k+1) {cout << "-1\n";return ;}
ll t=(S-(n-(k+1)))/(k+1);
vector<ll> ans;
FORLL(i,1,k){
ans.pb(t);
ans.pb(1);
S-=t+1;
}ans.pb(t); S-=t;
if(ans.size()>=n){
t=S/(n/2);
FORLL(i,0,n/2-1){
ans[i*2+1]+=t;
S-=t;
}
t=0;
while(S){
ans[t*2+1]++;
S--;
t++;
}
if(n>1&&ans[1]>=ans[0]) {cout << "-1\n";return ;}
}else{
t=ans.size();
while(ans.size()<n){
ans.pb(1);
S--;
}
ans[t]+=S;
}
FORLL(i,0,n-1) cout << ans[i] << " \n"[i==n-1];
}
|
I.时空的交织
贪心
题意
给定$n$个数的数组$a$和$m$个数的数组$b$，表示一个$n\times m$的矩阵，矩阵中的元素$m_{i,j}=a_i*b_j$。
选择一个子矩阵，使得子矩阵中的元素之和最大，输出这个和。
解题思路
假设选定的矩阵区间为$(r_i,r_j):(c_i,c_j)$，则子矩阵的和为$\sum_{i=r_i}^{r_j}\sum_{j=c_i}^{c_j}a_ib_j=\sum_{i=r_i}^{r_j}a_i\sum_{j=c_i}^{c_j}b_j$。
问题转化为求$a$数组的一个非空连续子数组和乘上$b$数组的一个非空连续子数组和的最大值。
可为空的数组区间和的最大值可以贪心的求解：
- 用$cur$表示对当前区间和，$max$表示区间和的最大值。
- 将当前元素$a_i$加入区间，和当前最大值比较。
- 若当前区间和$cur<0$，则舍弃之前的区间，重新开始计算（$cur:=0$）。
本题中的区间要求非空，可以用最值修正。
此外，$a$数组和$b$数组的元素可以为负数，因此同时求出区间和的最大值和最小值，两两相乘取最大即可。
参考程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| void solve()
{
ll n,m;cin >> n >> m;
create_vec(a,n);
create_vec(b,m);
ll mxa,mxb,mna,mnb,curmn,curmx;
mxa=mxb=-INF; mna=mnb=INF;
curmn=curmx=0;
FORLL(i,0,n-1){
curmn+=a[i];
curmx+=a[i];
if(curmn>0) curmn=0;
if(curmx<0) curmx=0;
mna=min(mna,curmn);
mxa=max(mxa,curmx);
}
curmn=curmx=0;
FORLL(i,0,m-1){
curmn+=b[i];
curmx+=b[i];
if(curmn>0) curmn=0;
if(curmx<0) curmx=0;
mnb=min(mnb,curmn);
mxb=max(mxb,curmx);
}
curmn=INF; curmx=-INF;
FORLL(i,0,n-1){
curmn=min(curmn,a[i]);
curmx=max(curmx,a[i]);
}
if(curmx<=0) mxa=min(mxa,curmx);
if(curmn>=0) mna=max(mna,curmn);
curmn=INF; curmx=-INF;
FORLL(i,0,m-1){
curmn=min(curmn,b[i]);
curmx=max(curmx,b[i]);
}
if(curmx<=0) mxb=min(mxb,curmx);
if(curmn>=0) mnb=max(mnb,curmn);
cout << max({mna*mnb,mna*mxb,mxa*mnb,mxa*mxb}) << endl;
}
|
J.时空的交织
贪心、构造
题意
给定一棵有根树，若干个节点为红色。
为每个节点赋值$1$或$2$，使得每个以红色节点为根的子树，其节点值之和为$3$的倍数。
解题思路
对于每个红色节点，如果它没有白色子节点，则它的子树除它以外的和已经是$3$的倍数，它为$1$或$2$都不可能再使它的子树和为$3$的倍数。
如果它至少有1个白色子节点，则它和白色子节点可以配合使得它的子树和为$3$的倍数。
因此，按DFS逆序遍历，白色节点先赋值为$1$。若红色节点除其本身外，和不是$3$的倍数，则用它补上；否则将任一白色子节点改为$2$，它赋为$2$。
参考程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| vector<vector<ll>> G;
vector<ll> vDFS_rev;
void DFS(ll x)
{
for(auto &y:G[x]) DFS(y);
vDFS_rev.pb(x);
}
void solve()
{
ll n,t;cin >> n; G.resize(n+1);
string s;cin >> s;
bitset<N> red;
FORLL(i,0,n-1) red[i+1]=(s[i]=='R');
vector<ll> white(n+1,0);
FORLL(i,2,n){
cin >> t; G[t].push_back(i);
if(white[t]==0&&!red[i]) white[t]=i;
}
FORLL(i,1,n) if(white[i]==0&&red[i]) {cout << "-1\n";return ;}
DFS(1);
ll S[N]={0},ans[N]={0};
for(auto &x:vDFS_rev){
for(auto &y:G[x]) S[x]+=S[y];
if(red[x]){
if(S[x]%3==0){
ans[x]=2; S[x]+=3;
ans[white[x]]=2; S[white[x]]+=1;
}else if(S[x]%3==1){
ans[x]=2; S[x]+=2;
}else{
ans[x]=1; S[x]+=1;
}
}else{
ans[x]=1;
S[x]+=1;
}
}
FORLL(i,1,n) cout << ans[i];
cout << endl;
}
|
