A - Subsegment Reverse
点击查看代码
#include<cstdio>
#include<numeric>
#include<algorithm>
using namespace std;
const int N=105;
int n,a[N],l,r;
int main()
{
scanf("%d%d%d",&n,&l,&r);
iota(a+1,a+n+1,1);
reverse(a+l,a+r+1);
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
return 0;
}
B - Nutrients
高桥出镜率 \(100 \%\)。
点击查看代码
#include<cstdio>
using namespace std;
const int N=105,M=105;
int n,m,a[M],x[N][M],b[M];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&x[i][j]);
b[j]+=x[i][j];
}
bool ans=true;
for(int i=1;i<=m;i++)
if(b[i]<a[i])
{
ans=false;
break;
}
printf("%s\n",ans?"Yes":"No");
return 0;
}
C - Keys
每次必有的暴力练习题。
点击查看代码
#include<cstdio>
using namespace std;
const int N=20,M=105;
int n,m,k;
int c[M],a[M][N],bt[M];
bool res[M];
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
{
scanf("%d",&c[i]);
for(int j=1;j<=c[i];j++)
{
scanf("%d",&a[i][j]);
bt[i]|=1<<(a[i][j]-1);
}
char str[5]; scanf("%s",str);
res[i]=str[0]=='o';
}
int ans=0;
for(int z=0;z<1<<n;z++)
{
bool is_ok=true;
for(int i=1;i<=m;i++)
if((__builtin_popcount(z&bt[i])>=k) != res[i])
{
is_ok=false;
break;
}
if(is_ok) ans++;
}
printf("%d\n",ans);
return 0;
}
D - Masked Popcount
找出 \([0,n]\) 中所有数二进制第 \(i\) 位上 \(1\) 的数量。
这是构成一个循环的，具体来说，例如 \(i=3\) 的时候，\([4,7],[12,15],[20,23],[28,31]\dots\) 的第 \(3\) 位上有 \(1\)，即每 \(2^i\) 个数中有 \(2^{i-1}\) 个数第 \(i\) 位是 \(1\)。
所以我们找出循环的数量，然后剩下的一截判断是否在第 \(i\) 位上有 \(1\) 的数值区间内，若有就加上剩下的一块 \(1\)。
最后若 \(m\) 在某一位上有 \(1\)，答案就要加上这一位上 \(1\) 的数量。
注意我代码里二进制最低位是第 \(0\) 位。
#include<cstdio>
using namespace std;
const int LogN=60,P=998244353;
long long n,m;
long long cnt[LogN+5];
int main()
{
scanf("%lld%lld",&n,&m);
long long ans=0;
for(int i=0;i<=LogN;i++)
{
long long t=n;
long long cycle=(t+1)>>(i+1);
cnt[i]+=cycle<<i;
t-=cycle<<(i+1);
if(t>=1ll<<i) cnt[i]+=t-(1ll<<i)+1;
if((m>>i)&1) ans=(ans+cnt[i])%P;
}
printf("%lld\n",ans);
return 0;
}
E - Max/Min
最恶心的一道，没有之一。
将 \(a\) 从小到大排序，答案转化为：
\[\sum_{i=2}^{n} \sum_{j=1}^{i-1} \left\lfloor\frac{a_i}{a_j}\right\rfloor \]然后将答案分为 \(a_i=a_j\) 和 \(a_i \neq a_j\) 两种情况。对于第一种情况，直接用公式即可算，难点在于第二种。
对于 \(\lfloor\frac{a_i}{a_j}\rfloor\)，因为除数和商不可能都大于 \(\sqrt{a_i}\)，所以将情况分为除数小于等于 \(\sqrt{a_i}\) 和被除数小于等于 \(\sqrt{a_i}\)，而对于后面一种情况，为避免重复，非常不建议枚举的时候直接判断被除数（我就是这么挂十发的），而应该采用判断“除数大于 \(\sqrt{a_i}\)”的判断方式，这样才可以保证不重不漏。
-
第一种情况：可能的商有 \(\sqrt{a_i}\) 种，当被除数、商一定时（\(\lfloor x \div y \rfloor = z\)），除数是一个确定的区间 \(\left[\lfloor\frac{x}{y+1}\rfloor+1,\lfloor\frac{x}{y}\rfloor\right]\)，预处理出值域前缀和就可以直接算。
-
第二种情况：可能的除数有 \(\sqrt{a_i}\) 种，当被除数、除数一定时，商唯一确定。直接加就行。
注意找的时候均必须找 \(a_j\) 严格小于 \(a_i\)，因为等于是在刚才单独计算的。
总的来说，我这种方法代码细节超多，不是很建议学。
时间复杂度 \(O(n \sqrt{n})\)
#include<cstdio>
#include<algorithm>
#pragma GCC optimize(2)
using namespace std;
namespace IO{
template<typename TYPE> void read(TYPE &x)
{
x=0; bool neg=false; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')neg=true;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
if(neg) {x=-x;} return;
}
template<typename TYPE> void write(TYPE x)
{
if(!x){putchar('0');return;} if(x<0){putchar('-');x=-x;}
static int sta[55]; int statop=0; while(x){sta[++statop]=x%10;x/=10;}
while(statop) {putchar('0'+sta[statop--]);} return;
}
} using namespace IO;
const int N=2e5+5,A=1e6+5;
int n,a[N],maxa;
long long ans=0;
int cnt[A];
#define qrange(l,r) (cnt[r]-cnt[(l)-1])
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
read(a[i]);
cnt[a[i]]++;
maxa=max(maxa,a[i]);
}
for(int i=1;i<=maxa;i++)
{
if(cnt[i]) ans+=1ll*cnt[i]*(cnt[i]-1)/2;
cnt[i]+=cnt[i-1];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
for(long long j=1;j*j<=a[i];j++) //枚举商
ans+=j*qrange(a[i]/(j+1)+1,min(a[i]/j,1ll*a[i]-1));
for(long long j=1;(a[i]/j)*(a[i]/j)>a[i];j++) //枚举除数
ans+=(a[i]/j)*qrange(j,min(j,1ll*a[i]-1));
}
write(ans);
return 0;
}