| Solved | A | B | C | D | E |
|---|---|---|---|---|---|
| 5/5 | O | O | Ø | Ø | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A CF520B - Two Buttons
题目描述
签到$1$
解题思路
一看数据范围直接爆搜，不过似乎也可以用反向推导直接得到。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef long long ll;
using namespace std;
int vis[N],n,m;
queue<int>Q;
int main(){
int i;
memset(vis,0x3f,sizeof(vis));
scanf("%d%d",&n,&m);
Q.push(n);vis[n]=0;
int flag=0;
while(!Q.empty()&&!flag){
int x=Q.front();Q.pop();
if(x*2<N&&vis[x*2]>1e9)Q.push(x*2),vis[x*2]=vis[x]+1;
if(x-1>0&&vis[x-1]>1e9)Q.push(x-1),vis[x-1]=vis[x]+1;
if(x==m)flag=1;
}
printf("%d",vis[m]);
return 0;
}
B CF521A - DNA Alignment
题目描述
签到$2$
解题思路
首先找到出现次数最多的字母，那么整个串都为这个字母是最优选择之一。
然后找到有多少个出现次数为最多次数的字母，假设有$cnt$个。出现次数相同代表在$T$串中任意取这些字母得到的串都是最优选择，于是每一个空位有$cnt$种选择，于是答案为$cnt^n$。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef long long ll;
using namespace std;
char s[100005];
int a[10];
ll qp(int a,int p){
ll ans=1,w=1000000007;
for(;p;p>>=1,a=1LL*a*a%w)if(p&1)ans=ans*a%w;
return ans;
}
int main(){
int i,n;
scanf("%d%s",&n,s);
for(i=0;s[i];i++){
if(s[i]=='A')a[0]++;
if(s[i]=='T')a[1]++;
if(s[i]=='G')a[2]++;
if(s[i]=='C')a[3]++;
}
int ans=0,cnt=0;
for(i=0;i<4;i++)ans=max(ans,a[i]);
for(i=0;i<4;i++)if(ans==a[i])cnt++;
printf("%lld",qp(cnt,n));
return 0;
}
C CF521B - Cubes
题目描述
在保证稳定的情况下交替拿取最大值和最小值。
解题思路
一开始想用平衡树，后来才发现居然能用$set+map$（$C$党的悲哀.jpg）
注意每次找答案的时候自身也要判断就是了。（也就是说可能会从$set$中取出来）
AC代码
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
typedef long long ll;
using namespace std;
map<pair<int,int>,int>mp;
set<int>s;
int x[N],y[N];
int exist(int x,int y){return mp.count(make_pair(x,y));}
int up(int x,int y){return exist(x-1,y-1)+exist(x,y-1)+exist(x+1,y-1)<2;}
int jud(int p){
if(exist(x[p]-1,y[p]+1))&&up(x[p]-1,y[p]+1))return 0;
if(exist(x[p],y[p]+1))&&up(x[p],y[p]+1))return 0;
if(exist(x[p]+1,y[p]+1))&&up(x[p]+1,y[p]+1))return 0;
return 1;
}
void ins(int p){
int temp;
if(exist(x[p]-1,y[p]-1)&&jud(temp=mp[make_pair(x[p]-1,y[p]-1)]))s.insert(temp);
if(exist(x[p],y[p]-1)&&jud(temp=mp[make_pair(x[p],y[p]-1)]))s.insert(temp);
if(exist(x[p]+1,y[p]-1))&&jud(temp=mp[make_pair(x[p]+1,y[p]-1)]))s.insert(temp);
}
int main(){
int i,n;
ll ans=0;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d%d",&x[i],&y[i]);
mp[make_pair(x[i],y[i])]=i;
}
for(i=0;i<n;i++)if(jud(i))s.insert(i);
for(i=0;i<n;i++){
while(!s.empty()){
int now=(i&1)?(*s.begin()):(*s.rbegin());
if(jud(now)){
ans=(ans*n+now)%w;
s.erase(now);
mp.erase(make_pair(x[now],y[now]));
ins(now);
break;
}
s.erase(now);
}
}
printf("%I64d",ans);
return 0;
}
D CF521C - Pluses everywhere
题目描述
给一个大整数串$a_i$，求在里面加$k$个加号的所有计算结果之和。
解题思路
推出式子预处理。
假设每一位对答案的贡献为$ans_i$，则答案为$\sum_{i=0}^{n-1}ans_i$。
考虑计算从头开始的第$i$位对答案的贡献。
这一位数字可以放在个位、十位、百位……一直到串的末端。考虑分两类讨论：
- 直接延伸到串的末端，贡献为$a_i\times 10^{n-1-i}\times C_i^k$（在前$i$个空里面选择$k$个加号）
- 不延伸到末端，设$i$到加号右端数字的长度为$len$，则贡献为$a_i\times 10^{len-1}\times C_{n-len-1}^{k-1}$（本来有$n-1$个空，这一段都不能放置加号，一段结束放置了一个加号，故还剩$n-1-(len-1)-1=n-len-1$个空，放置$k$个加号）
故$ans_i=\sum_{len=1}^{n-1-i}a_i\times 10^{len-1}\times C_{n-len-1}^{k-1}+a_i\times 10^{n-1-i}\times C_i^k$
发现可以预处理出来这一个求和号，线性解决。
AC代码
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
typedef long long ll;
using namespace std;
int n,k;
char a[N];
ll p[N]={1},w=1000000007,fac[N]={1},inv[N]={1},s[N];
ll qp(ll x,int p){
ll ans=1;
for(;p;p>>=1,x=x*x%w)if(p&1)ans=ans*x%w;
return ans;
}
ll c(int n,int m){
if(m<0||m>n)return 0;
return fac[n]*inv[m]%w*inv[n-m]%w;
}
int main(){
int i;
scanf("%d%d",&n,&k);
scanf("%s",a);
for(i=1;i<=n;i++){
p[i]=p[i-1]*10%w;
fac[i]=fac[i-1]*i%w;
inv[i]=qp(fac[i],w-2);
}
for(i=1;i<=n;i++)s[i]=(s[i-1]+c(n-i-1,k-1)*p[i-1])%w;
ll ans=0;
for(i=0;i<n;i++)ans=(ans+(a[i]-'0')*(s[n-1-i]+p[n-i-1]*c(i,k)))%w;
printf("%lld\n",ans);
return 0;
}
E CF521D - Shop
题目描述
给一个数组$a_i$，有三种操作：$a_i$变成给定数，$a_i$加上给定数，$a_i$乘上给定数。所有有关量均为正整数。
按顺序至多采取其中$m$个操作， 问最终结果（$\prod_{i=1}^na_i$）最大时的操作顺序。
解题思路
贪心。
显然可证，乘法放到最后是最优的，操作一对于每一个数只能最多进行一次（且变到最大），且放到最前面是最优的。
于是先处理操作一，对于每一个数存储一下最大的改变量，于是转化成了操作二。
现在仅处理操作二的先后顺序。设在某一个时刻，操作二$a_i$优于$a_j$，假设操作$i$对应的数组下标是$pos_i$，改变量为$delta_i$（加或乘），当前数组（不是初始数组！）为$x_i$，则需要满足
$\prod_{p=1}^k x_p\times \frac{x_{pos_i}+delta_i}{x_{pos_i}}>\prod_{p=1}^k x_p\times \frac{x_{pos_j}+delta_j}{x_{pos_j}}$，即$\frac{delta_i}{x_{pos_i}}>\frac{delta_j}{x_{pos_j}}$。
现在考虑操作二和操作三的处理顺序。假设某一个操作二$a_i$优于操作三$a_j$，有
$\prod_{p=1}^k x_p\times \frac{x_{pos_i}+delta_i}{x_{pos_i}}>\prod_{p=1}^k x_p\times delta_j$，即$\frac{delta_i}{x_{pos_i}}>delta_j-1$。
于是对于每一个操作，记录一下$x,d$。在这里，我们对于每一个操作二以及转化过来的操作一，$x$为$x_{pos_i}$，$d$为$delta_i$，对于每一个操作三，$x$为$1$，$d$为$delta_j-1$，便可以进行排序。
排完序得到的结果中，前$ans$个中，所有的操作一与操作三必然被执行，但操作二的$x$会被操作一改变（注意上面的黑字说明的，$x$是执行这一个操作的时候的当前数组），故需要对所有的操作二进行修改。再次排序，则后面的操作一和操作三可能会上来顶替某些操作二，而这些上来的操作一又对与之对应的操作二产生了影响。重复这个过程，很快就可以到达平衡，得到答案。
非常神秘，比赛的时候我$A$掉了这个题，但是$CF$上却没有这个记录，而且再拿这个代码提交的时候会$WA$掉第$149$个点。
$upd1$：想出来原因了，等着改改。
WA-test149代码
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
struct Add{
int x,d,i;
int sign,pos;
bool operator<(const Add&p)const{return 1LL*d*p.x>1LL*p.d*x;}
}a[N];
int cnt,d[N],x[N],p[N];
int main(){
int i,k,n,m;
scanf("%d%d%d",&k,&n,&m);
for(i=1;i<=k;i++)scanf("%d",&x[i]);
for(i=1;i<=n;i++){
int opt,pos,ch;
scanf("%d%d%d",&opt,&pos,&ch);
if(opt==1){if(d[pos]<ch-x[pos])d[pos]=ch-x[pos],p[pos]=i;}
else if(opt==2)a[cnt++]=(Add){x[pos],ch,i,2,pos};
else a[cnt++]=(Add){1,ch-1,i,3,pos};
}
for(i=1;i<=k;i++)if(d[i])a[cnt++]=(Add){x[i],d[i],p[i],1,i};
std::sort(a,a+cnt);
int ans=std::min(cnt,m);
printf("%d\n",ans);
int flag=1;
while(flag){
flag=0;
for(i=0;i<ans;i++)if(a[i].sign==1)
x[a[i].pos]+=a[i].d,a[i].sign=0,flag=1;
for(i=0;i<cnt;i++)if(a[i].sign==2&&a[i].x!=x[a[i].pos])
a[i].x=x[a[i].pos];
std::sort(a,a+cnt);
}
for(i=0;i<ans;i++)if(a[i].sign<2)printf("%d ",a[i].i);
for(i=0;i<ans;i++)if(a[i].sign==2)printf("%d ",a[i].i);
for(i=0;i<ans;i++)if(a[i].sign==3)printf("%d ",a[i].i);
return 0;
}
$upd2$：错误原因在于没有考虑到操作二也可以影响操作顺序。我们很容易证明，对于某个位置，最优的一个一操作和所以二操作可以完全混合在一起进行排序。于是记录每一次进行后的$x$值进行排序即可。这样是不需要考虑爆$ll$的。
AC代码1-108ms
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
typedef long long ll;
using namespace std;
struct Add{
ll x,d;int i;
bool operator<(const Add&p)const{return d*p.x>p.d*x;}
}a[N];
int cnt,d[N],p[N],sig[N];
ll x[N];
vector<pair<int,int>>chain[N];
int main(){
int i,k,n,m;
scanf("%d%d%d",&k,&n,&m);
for(i=1;i<=k;i++)scanf("%I64d",&x[i]);
for(i=1;i<=n;i++){
int opt,pos,ch;
scanf("%d%d%d",&opt,&pos,&ch);sig[i]=opt;
if(opt==1){if(d[pos]<ch-x[pos])d[pos]=ch-x[pos],p[pos]=i;}
else if(opt==2)chain[pos].push_back(make_pair(ch,i));
else a[cnt++]=(Add){1,ch-1,i};
}
for(i=1;i<=k;i++){
if(d[i])chain[i].push_back(make_pair(d[i],p[i]));
sort(chain[i].rbegin(),chain[i].rend());
for(auto e:chain[i]){
a[cnt++]=(Add){x[i],e.first,e.second};
x[i]+=e.first;
}
}
std::sort(a,a+cnt);
int ans=std::min(cnt,m);
printf("%d\n",ans);
for(i=0;i<ans;i++)if(sig[a[i].i]==1)printf("%d ",a[i].i);
for(i=0;i<ans;i++)if(sig[a[i].i]==2)printf("%d ",a[i].i);
for(i=0;i<ans;i++)if(sig[a[i].i]==3)printf("%d ",a[i].i);
return 0;
}
然后其实也可以变成乘法去搞一搞。但是这样搞的话居然爆$ll$……必须转化成$double$才可以进行比较……
AC代码2-108ms
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
typedef long long ll;
struct Add{
ll d,x;
int i;
bool operator<(const Add&p)const{return 1.0*d*p.x>1.0*p.d*x;}
}a[N];
int cnt,d[N],p[N],sig[N],x[N];
std::vector<std::pair<int,int>>chain[N];
int main(){
int i,k,n,m;
scanf("%d%d%d",&k,&n,&m);
for(i=1;i<=k;i++)scanf("%d",&x[i]);
for(i=1;i<=n;i++){
int opt,pos,ch;
scanf("%d%d%d",&opt,&pos,&ch);
sig[i]=opt;
if(opt==1){if(d[pos]<ch-x[pos])d[pos]=ch-x[pos],p[pos]=i;}
else if(opt==2)chain[pos].push_back(std::make_pair(ch,i));
else a[cnt++]=(Add){ch,1,i};
}
for(i=1;i<=k;i++){
if(d[i])chain[i].push_back(std::make_pair(d[i],p[i]));
std::sort(chain[i].rbegin(),chain[i].rend());
ll pre=x[i],now;
for(auto e:chain[i]){
now=pre+e.first;
a[cnt++]=(Add){now,pre,e.second};
pre=now;
}
}
std::sort(a,a+cnt);
int ans=std::min(cnt,m);
printf("%d\n",ans);
for(i=0;i<ans;i++)if(sig[a[i].i]==1)printf("%d ",a[i].i);
for(i=0;i<ans;i++)if(sig[a[i].i]==2)printf("%d ",a[i].i);
for(i=0;i<ans;i++)if(sig[a[i].i]==3)printf("%d ",a[i].i);
return 0;
}