Codeforces Round #422 Div. 2 (A/B/C/D)

A I’m bored with life

标题真好哇。(什么
因为是阶乘,所以输出较小数的阶乘即可。

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int a,b;
scanf("%d%d",&a,&b);
ll ans=1;
for(ll i=1;i<=min(a,b);i++) ans=ans*i;
printf("%lld\n",ans);
return 0;
}

B Crossword solving

暴力即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
string a,b;
cin>>a>>b;
int ans=0x3f3f3f3f;
vector<int > gai;gai.clear();
for(int i=0;i<m-n+1;i++)
{
int cnt=0;
vector<int> buf;
for(int j=0;j<n;j++)
{
if(a[j]!=b[i+j]) {cnt++;buf.push_back(j+1);}
}
if(ans>cnt){ans=cnt;gai=buf;}
}
printf("%d\n",ans);
for(int i=0;i<(int)gai.size();i++) printf("%d ",gai[i]);puts("");
return 0;
}

C Hacker, pack your bags!

好像很多人fst了…不过我也fst了

题意是选出2个不相交的区间长度和为$x$并且权值和最小,输出最小权值和。

考试的时候还在想会不会被卡到$O(n^2)$呢,如果卡到了会不会cf的机子跑过去了呢,结果发现都是扯淡。

然后发现考试时和我互hack的那位俄罗斯神犇的代码写的非常妙,做法是$O(nlog_n)$。仔细一想,自己和别人的差距就是在这样的一些代码细节处理上。

考虑先按区间长度排序,并查找某个满足区间和为x的区间且不能相交——无非就是这样的限制条件。然后最优的就是那个vector去处理同一长度区间较小cost的那个过程——

v[i] contains the minimal cost of trip which begins at a[i].first.second or later and has length equal to a[i].first.first.
cur is not trip that you need to take with a[i] - it is the earliest trip that you can take with it, so you need to take trip which begins at a[cur].first.second or later, has length equal to a[cur].first.first and its cost is minimal.

感觉是非常优的,应该说也是比较常见的处理较小值的技巧,然而考场上并没有get到。

这题有2个hack点,一个是$inf$设小的锅,这个被那位俄罗斯神犇发现后立即提交了一个数据生成器hack我的$inf=0x3f3f3f3f$,结果我的代码居然跑过了,但如果直接给个数据的话肯定gg。另一个是$x$为偶数时,某些做法可能会选到两个长度为$\frac{x}{2}$的自己,这个也是可以hack的(不过这样的code大多数最终TLE了)。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=2*100000+5;
const int inf=0x7fffffff;
pair<pair<int ,int >,int > p[maxn];
int n,x;
int main()
{
scanf("%d%d",&n,&x);
for(int i=0;i<n;i++) scanf("%d%d%d",&p[i].first.first,&p[i].first.second,&p[i].second);
for(int i=0;i<n;i++)
{
int l=p[i].first.first,r=p[i].first.second;
p[i].first.first=r-l+1;p[i].first.second=l;
}
sort(p,p+n);
vector<int > v(n);
v[n-1]=p[n-1].second;
for(int i=n-2;i>=0;i--)
{
if(p[i].first.first==p[i+1].first.first) v[i]=min(v[i+1],p[i].second);
else v[i]=p[i].second;
}
int res=inf;
for(int i=0;i<n;i++)
{
int cur=lower_bound(p,p+n,make_pair(make_pair(x-p[i].first.first,p[i].first.first+p[i].first.second),0))-p;
if(cur==n || p[cur].first.first+p[i].first.first!=x || cur==i) continue;
res=min(res,v[cur]+p[i].second);
}
if(res!=inf)printf("%d\n",res);else printf("-1\n");
return 0;
}

D My pretty girl Noora

看错题的锅(猛然想起前几天的tc,div2第一题看成要在给定矩阵里找一行一列,结果样例很弱全过了,然后fst的悲惨经历),$x$虽然可以随便取,但是不能取很多个不同的$x$(后者对应的$f$序列是“重复的奇数序列”,和样例前几个完全符合。)

题意是有$i$个妹纸选美,要选择一个$x|i$使得恰好分为$\frac{x}{i}$组,然后把一共要进行的比较次数作为$f$数组的值,计算$t^0\times f(l)+t^1 \times f(l+1)+…+t^{r-l}\times f(r)$。

考虑先求出所有的$f$值,其余一切都好说。首先对于一个质数$x$,只能分成一组,比较次数为$\frac{x \times (x-1)}{2}$;而不是质数的话,考虑分组,在纸上列出前10个$f$就会发现,最小的比较次数一定诞生于按照该数最小的质因数分组$\rightarrow $分成最多的组。

线性筛预处理所有的质数和每个数最小的质因数,然后再预处理$t$的幂即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=5*1e6+5;
const ll mo=1e9+7;
ll pri[maxn];bool vis[maxn];
ll t,l,r,cnt;
ll minpri[maxn],f[maxn],frac[maxn];
void pre()
{
cnt=0;
for(int i=2;i<maxn;i++)
{
if(!vis[i]) pri[++cnt]=i,minpri[i]=i;
for(int j=1;j<=cnt;j++)
{
if(i*pri[j]>=maxn) break;
vis[i*pri[j]]=true;
minpri[i*pri[j]]=pri[j];
if(i%pri[j]==0) break;
}
}
}
void getf()
{
f[2]=1;
f[3]=3;f[4]=3;
for(int i=5;i<maxn;i++)
{
if(!vis[i]) f[i]=(((ll)i*(i-1))/2)%mo;
else f[i]=((ll)f[minpri[i]]*(i/minpri[i])%mo+f[i/minpri[i]])%mo;
}
}
void gett()
{
frac[0]=1;
for(int i=1;i<=r-l;i++) frac[i]=frac[i-1]*t%mo;
}
int main()
{
pre();
getf();
scanf("%lld%lld%lld",&t,&l,&r);
gett();
ll ans=0;
for(int i=0;i<r-l+1;i++)
ans=(ans+(ll)frac[i]*f[l+i]%mo)%mo;
printf("%lld\n",ans);
return 0;
}