CF1011A Stages
每次记下上一个选的位置，贪心能填就填。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=55;
int n,k;
char s[N];
int cnt[27];
int main()
{
scanf("%d%d",&n,&k);
scanf("%s",s+1);
for(int i=1;i<=n;i++)
cnt[s[i]-'a'+1]++;
int pre=-1,s=0;
int ans=0;
for(int i=1;i<=26;i++)
{
if(cnt[i]&&i-pre>1)
{
pre=i;
s++;
ans+=i;
}
if(s==k) break;
}
if(s==k) printf("%d",ans);
else printf("-1");
return 0;
}
CF1011B Planning The Expedition
二分答案，然后一个位置 \(i\) 的贡献为 \(\lfloor\frac{c_i}{mid}\rfloor\)。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=105;
int n,m;
int a[N];
int c[N];
bool check(int x)
{
int cnt=0;
for(int i=1;i<=100;i++)
cnt+=c[i]/x;
return cnt>=n;
}
int main()
{
scanf("%d%d",&n,&m);
int l=1,r=0;
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
c[a[i]]++;
r=max(r,c[a[i]]);
}
int ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d",ans);
return 0;
}
CF1011C Fly
对于一次降落或起飞的操作，我们设其效率为 \(k\)，则我们这次消耗的燃料 \(f\) 需要满足 \(m+f=kf\)，\(m\) 为自重加上之后需要用的燃料。
那么我们可以从后往前递推，每次求出消耗的燃料加上自重，最后减去 \(m\) 即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=105;
int n,m;
int a[N];
int c[N];
bool check(int x)
{
int cnt=0;
for(int i=1;i<=100;i++)
cnt+=c[i]/x;
return cnt>=n;
}
int main()
{
scanf("%d%d",&n,&m);
int l=1,r=0;
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
c[a[i]]++;
r=max(r,c[a[i]]);
}
int ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d",ans);
return 0;
}
CF1011D Rocket
可以询问 \(n\) 次 \(1\) 得出 \(p\)，然后再二分即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1005;
int n,m;
int a[N],b[N];
double calc(int k,double w)
{
if(k==1)
{
printf("-1");
exit(0);
}
return w+w*1.0/(k-1);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
double s=m;
s=calc(a[n],s);
for(int i=n-1;i>=1;i--)
s=calc(b[i+1],s),s=calc(a[i],s);
s=calc(b[1],s);
printf("%.10lf",s-m);
return 0;
}
CF1011E Border
问题等价于求 \(\sum\limits_{i=1}^n x_ia_i \bmod k\) 的所有取值，其中 \(x_i\) 为任意整数。
由裴蜀定理可得：
\(\sum_{i=1}^n a_ix_i=c\) 有解，当且仅当 \(\left(\gcd\limits_{i=1}^n\{a_i\}\right) | c\)。
令 \(d=\gcd\limits_{i=1}^n\{a_i\}\)，所有的取值即为 \(d\) 的倍数，还有 \(\bmod k\) 的限制的话 \(d\) 再对 \(k\) 取个 \(\gcd\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n,k;
int a[N];
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int d=k;
for(int i=1;i<=n;i++)
d=__gcd(d,a[i]);
printf("%d\n",k/d);
for(int i=0;i<k/d;i++)
printf("%d ",i*d);
return 0;
}
CF1011F Mars rover
建出整棵树，如果这个点为 AND 且有一个儿子的权值为 \(0\)，则另一个儿子子树中的叶子翻转以后不会影响到根，打个标记；如果这个点为 OR 且有一个儿子的权值为 \(1\)，则另一个儿子子树中的叶子翻转以后不会影响到根，同样打个标记。最后 DFS 扫一遍判断每个点翻转以后会不会对根产生影响就好了。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000005;
int n;
string s[N];
int v[N];
int ch[N][2];
int fa[N];
void dfs1(int u)
{
if(s[u]=="IN") return;
dfs1(ch[u][0]);
if(s[u]!="NOT") dfs1(ch[u][1]);
if(s[u]=="AND") v[u]=v[ch[u][0]]&v[ch[u][1]];
else if(s[u]=="OR") v[u]=v[ch[u][0]]|v[ch[u][1]];
else if(s[u]=="XOR") v[u]=v[ch[u][0]]^v[ch[u][1]];
else if(s[u]=="NOT") v[u]=!v[ch[u][0]];
return;
}
int tag[N];
int res[N];
void dfs2(int u)
{
if(s[u]=="AND")
{
if(v[ch[u][0]]==0) tag[ch[u][1]]=true;
if(v[ch[u][1]]==0) tag[ch[u][0]]=true;
}
else if(s[u]=="OR")
{
if(v[ch[u][0]]==1) tag[ch[u][1]]=true;
if(v[ch[u][1]]==1) tag[ch[u][0]]=true;
}
if(s[u]=="IN")
{
if(tag[u]) res[u]=v[1];
else res[u]=!v[1];
return;
}
tag[ch[u][0]]|=tag[u],dfs2(ch[u][0]);
if(s[u]!="NOT") tag[ch[u][1]]|=tag[u],dfs2(ch[u][1]);
return;
}
int main()
{
cin>>n;
s[0]="IN";
for(int i=1;i<=n;i++)
{
cin>>s[i];
if(s[i]=="AND"||s[i]=="OR"||s[i]=="XOR") cin>>ch[i][0]>>ch[i][1],fa[ch[i][0]]=fa[ch[i][1]]=i;
else if(s[i]=="NOT") cin>>ch[i][0],fa[ch[i][0]]=i;
else if(s[i]=="IN") cin>>v[i];
}
dfs1(1);
dfs2(1);
for(int i=1;i<=n;i++)
if(s[i]=="IN") printf("%d",res[i]);
return 0;
}