碎碎念
心血来潮军训打cf打到十二点半
本来心态爆炸准备三题弃赛
最后十分钟还真过了D，离谱
不会做数学题怎么办啊呜呜呜呜呜
看完E题解，代码就是一个板子加一句话，寄
A - Madoka and Strange Thoughts
求满足lcm(a,b)/gcd(a,b)<=3且1<=a,b<=n的数对(a,b)的个数
solution
显然第一个式子的值只能为1,2,3
解一下方程就会发现a=b/3,b/2,b,b*2,b*3
那么答案就是n/3+n/2+n+n/2+n/3
#include<bits/stdc++.h>
using namespace std;
int T,n;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%d\n",n/3+n/2+n+n/2+n/3);
}
return 0;
}B - Madoka and Underground Competitions
构造一个n*n的只有‘X’和‘.’字符矩阵
使所有行上或列上连续的k个字符中至少有一个‘X’
同时要求(r,c)上必须是'X'且'X'的数量最小化
solution
显然从(r,c)对角线开始放
#include<bits/stdc++.h>
using namespace std;
int T,n,k,r,c;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&n,&k,&r,&c);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
if((i+j)%k==(r+c)%k)
putchar('X');
else putchar('.');
putchar('\n');
}
}
return 0;
}C - Madoka and Formal Statement
给你两个数组a,b，每次操作仅当a[i]<=a[i+1]时可以使a[i]+1
特别的，a[n]后面是a[1]
询问若干次操作后是否可以让a数组成为b数组
solution
显然每次跳的能跳的最大位置最优，即跳到min(a[i+1]+1,b[i])
但是会有一些阴间的情况让我们T掉
比如(1,1,1,1)变成(inf,inf,inf,inf)
所以我们需要在跳跃之前将所有数拔高到min{b}的位置
然后暴力做个几轮就好了
#include<bits/stdc++.h>
using namespace std;
int T,n,a[200010],b[200010];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int maxx=1,minn=1,cnt=0,flg=1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>a[maxx])maxx=i;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
if(b[i]<b[minn])minn=i;
}
if(a[maxx]<=b[minn])
for(int i=1;i<=n;i++)
a[i]=b[minn];
for(int i=maxx-1;cnt<=2;i--)
{
if(i==0)i=n;
if(i==maxx)cnt++;
if(i!=n)
{
if(a[i]<=a[i+1]&&a[i]<=b[i])
a[i]=min(a[i+1]+1,b[i]);
}
else
{
if(a[i]<=a[1]&&a[i]<=b[i])
a[i]=min(a[1]+1,b[i]);
}
}
for(int i=1;i<=n;i++)
if(a[i]!=b[i])flg=0;
puts(flg?"YES":"NO");
}
return 0;
}D - Madoka and The Corruption Scheme
有2^n个人编号为1..2^n，有n轮淘汰赛，你可以任意决定参赛顺序和胜利选手
你的对手可以更改你不超过k次的胜利选手，你的目的是让最终胜利的选手编号最小
solution
二进制猜结论题QAQ
反正手动模拟几个小样例就能看出是杨辉三角（
（反正我猜了一个半小时）
#include<bits/stdc++.h>
#define N 100010
using namespace std;
const int MOD=1e9+7;
int pow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=1ll*res*a%MOD;
b/=2,a=1ll*a*a%MOD;
}
return res;
}
int n,k;
int inv[N],ji[N],ni[N];
int C(int x,int y){
return 1ll*ji[x]*ni[y]%MOD*ni[x-y]%MOD;
}
int main()
{
scanf("%d%d",&n,&k);
inv[1]=1;
for(int i=2;i<N;i++)
inv[i]=MOD-1ll*MOD/i*inv[MOD%i]%MOD;
ji[0]=1,ni[0]=1;
for(int i=1;i<N;i++)
ji[i]=1ll*ji[i-1]*i%MOD,
ni[i]=1ll*ni[i-1]*inv[i]%MOD;
int ans=pow(2,n),ret=0;
while(k<n)
{
ans=(ans-C(n,ret)+MOD)%MOD;
k++,ret++;
}
printf("%d\n",ans);
return 0;
}E - Madoka and The Best University
求sum{lcm(c,gcd(a,b))}，其中a+b+c=n
solution
纯纯数学题
gcd(a,b)=gcd(a,a+b)=gcd(a,n-c)
所以这个gcd的值一定是n-c的某个因子d
而对于某个因子d对应的a的数量就是phi((n-c)/d)
所以式子就变成了sum{lcm(c,d)*phi((n-c)/d)}，其中1<=c<=n-2，(n-c) mod d = 0
直接枚举d和d的倍数，预处理phi数组，标准埃筛复杂度
（这是题解翻译）
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
int phi[100010];
int prime[100010];
bool not_prime[100010];
int tot;
void Phi()
{
for(int i=2;i<=100000;++i)
{
if(!not_prime[i])
{
prime[tot++]=i;
phi[i]=i-1;
}
for(int j=0;j<tot&&i*prime[j]<=100000;++j)
{
not_prime[i*prime[j]]=true;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
int n,ans;
long long lcm(int a,int b)
{
return 1ll*a*b/__gcd(a,b);
}
int main()
{
Phi(),scanf("%d",&n);
for(int i=1;i<=n;i++)//i->d
for(int j=i<<1;j<n;j+=i)//j->n-c
(ans+=lcm(n-j,i)*phi[j/i]%MOD)%=MOD;
printf("%d\n",ans);
return 0;
}
Comments NOTHING