原地址
讨论区
Changing
算法一
我会随机！
由于我忘了设置多组数据，期望得分0至100。
算法二
我会模拟！
复杂度(O(t^2)),期望得分60。
但是很多人忘记题目给出的是环形……
算法三
我会正解！
实际上是数学题，显然时刻tt第kk盏灯的状态为
[left(sum_{i=0}^t C_t^ia_{(k+i-1) mod n+1}
ight) mod 2
]
求和即可。复杂度O(t)，期望得分100。
Calculating
算法一
我会推公式！
将ff分解质因数得到
$$f=p_1^{k_1}p_2^{k_2}..p_j^{a_j}$$
，则题目实际上要求：
[ans=sum_{f=l}^rprod_{i=1}^j p_i^{a_i+1}
]
记f因数个数为d(f)，则由排列组合可得：
[prod_{i=1}^j p_i^{a_i+1}=d(f)
]
则原式化为：
[ans=sum_{f=l}^rd(f)
]
暴力统计答案。时间复杂度(O(r^2))，期望得分40。
算法二
我会拆询问！
实际上，我们有：
[ans=sum_{i=1}^rd(i)-sum_{j=1}^{l-1}d(j)
]
考虑如何求(sum_{i=1}^rd(i))，
对于[1,r]的整数k，k作为因数在[1,r]中出现了(leftlfloor frac rk
ight
floor)次，
显然对答案的贡献为(leftlfloor frac rk
ight
floor)。
则：
[ans=sum_{i=1}^rleftlfloor frac ri
ight
floor-sum_{j=1}^{l-1}leftlfloor frac {l-1}j
ight
floor
]
枚举k，统计答案。时间复杂度(O(2r))，期望得分60到70之间。
算法三
我会分块！
注意到(leftlfloor frac rk
ight
floor)最多有$$2sqrt r$$种取值，我们对其分类统计答案即可。
做法类似没有莫比乌斯函数的莫比乌斯反演。
时间复杂度(O(4sqrt r))，可通过全部测试点。
PS:至于为什么会有100100个测试点……这是个好问题。
Coloring
算法一
我会随机！
没试过，期望得分40以下。
算法二
我会骗分！
按从左往右，从上往下的顺序依次填颜色，期望得分60。
算法三
我会贪心！
手玩几个例子不难发现把相同颜色的放在一起更优。每次填颜色，贪心找一块在边界且尽可能大的位置，放下该颜色的所有格子。期望得分70至90。
算法四
我会搜索！
搜索时间复杂度(O(c^{nm}))，超时无疑。
嘿嘿嘿。
算法五
我会物理！
哦豁？搜索其实很靠近正解，但是时间太慢。我们考虑模拟退火。
每次操作交换两个在联通块边界的格子，计算答案是否更优，按概率更新。
算法六
等等……为啥会是90？
因为你可能会陷入局部最优解。
多随机几次就好了。
时间复杂度(O(O(跑得过)))，期望得分100。
T1
#include <cstdio>
using namespace std;
const int maxn=3000005;
int n,q,z,i,t,g[maxn];
int a[maxn],ans;
int main()
{
scanf("%d%d%d",&n,&q,&z);
z--;
for (i=0;i<n;i++)
scanf("%d",&a[i]);
for (i=1;i<=q>>1;i++)
g[i<<1]=g[i]+1;
t=0;
for (i=0;i<=q;i++)
{
t=t+g[q-i+1]-g[i];
ans+=(t==0)*a[(i+z)%n];
}
printf("%d
",ans&1);
return 0;
}
T2
#include <cstdio>
#define mod 998244353
using namespace std;
long long l,r;
long long calc(long long n)
{
long long ans=0;
for (long long i=1;i<=n;i=n/(n/i)+1)
ans=(ans+(n/(n/i)-i+1)%mod*(n/i)%mod)%mod;
return ans;
}
int main()
{
scanf("%lld%lld",&l,&r);
printf("%lld
",(calc(r)-calc(l-1)+mod)%mod);
return 0;
}
T3
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
int q,x,y,i,j,k,m[25][25],mm[25][25];
int mx,my,tx,ty;
double t,tmin,tmp,ans,delta,now;
int tot[51],cl,top[51];
bool move;
int lans,lm[25][25];
inline double search()
{
t=x*y;
delta=0.99998;
tmin=0.0001;
ans=0;
for (j=1;j<=x;j++)
for (k=1;k<y;k++)
ans+=m[j][k]!=m[j][k+1];
for (j=1;j<x;j++)
for (k=1;k<=y;k++)
ans+=m[j][k]!=m[j+1][k];
for (j=1;j<=x;j++)
for (k=1;k<=y;k++)
mm[j][k]=m[j][k];
for (i=1;i<=x;i++)
{
mm[i][0]=mm[i][1];
mm[i][y+1]=mm[i][y];
}
for (i=1;i<=y;i++)
{
mm[0][i]=mm[1][i];
mm[x+1][i]=mm[x][i];
}
tmp=now=ans;
while (tmin<t)
{
while (1)
{
mx=rand()%x+1;
my=rand()%y+1;
tx=rand()%x+1;
ty=rand()%y+1;
if (mm[mx][my]==mm[tx][ty])
continue;
if (mm[mx-1][my]==mm[mx+1][my]&&
mm[mx+1][my]==mm[mx][my-1]&&
mm[mx][my-1]==mm[mx][my+1]&&
mm[mx][my+1]==mm[mx][my])
continue;
if (mm[tx-1][ty]==mm[tx+1][ty]&&
mm[tx+1][ty]==mm[tx][ty-1]&&
mm[tx][ty-1]==mm[tx][ty+1]&&
mm[tx][ty+1]==mm[tx][ty])
continue;
move=0;
tmp-=(mm[mx-1][my]!=mm[mx][my])+(mm[mx+1][my]!=mm[mx][my])+(mm[mx][my+1]!=mm[mx][my])+(mm[mx][my-1]!=mm[mx][my]);
tmp-=(mm[tx-1][ty]!=mm[tx][ty])+(mm[tx+1][ty]!=mm[tx][ty])+(mm[tx][ty+1]!=mm[tx][ty])+(mm[tx][ty-1]!=mm[tx][ty]);
swap(mm[mx][my],mm[tx][ty]);
for (i=1;i<=x;i++)
{
mm[i][0]=mm[i][1];
mm[i][y+1]=mm[i][y];
}
for (i=1;i<=y;i++)
{
mm[0][i]=mm[1][i];
mm[x+1][i]=mm[x][i];
}
tmp+=(mm[mx-1][my]!=mm[mx][my])+(mm[mx+1][my]!=mm[mx][my])+(mm[mx][my+1]!=mm[mx][my])+(mm[mx][my-1]!=mm[mx][my]);
tmp+=(mm[tx-1][ty]!=mm[tx][ty])+(mm[tx+1][ty]!=mm[tx][ty])+(mm[tx][ty+1]!=mm[tx][ty])+(mm[tx][ty-1]!=mm[tx][ty]);
if (tmp<ans)
{
ans=tmp;
for (j=1;j<=x;j++)
for (k=1;k<=y;k++)
m[j][k]=mm[j][k];
move=1;
}
if (tmp<=now)
{
now=tmp;
move=1;
}
else
if (rand()/(double)RAND_MAX<exp((ans-tmp)/t))
{
now=tmp;
move=1;
}
if (!move)
{
tmp-=(mm[mx-1][my]!=mm[mx][my])+(mm[mx+1][my]!=mm[mx][my])+(mm[mx][my+1]!=mm[mx][my])+(mm[mx][my-1]!=mm[mx][my]);
tmp-=(mm[tx-1][ty]!=mm[tx][ty])+(mm[tx+1][ty]!=mm[tx][ty])+(mm[tx][ty+1]!=mm[tx][ty])+(mm[tx][ty-1]!=mm[tx][ty]);
swap(mm[mx][my],mm[tx][ty]);
for (i=1;i<=x;i++)
{
mm[i][0]=mm[i][1];
mm[i][y+1]=mm[i][y];
}
for (i=1;i<=y;i++)
{
mm[0][i]=mm[1][i];
mm[x+1][i]=mm[x][i];
}
tmp+=(mm[mx-1][my]!=mm[mx][my])+(mm[mx+1][my]!=mm[mx][my])+(mm[mx][my+1]!=mm[mx][my])+(mm[mx][my-1]!=mm[mx][my]);
tmp+=(mm[tx-1][ty]!=mm[tx][ty])+(mm[tx+1][ty]!=mm[tx][ty])+(mm[tx][ty+1]!=mm[tx][ty])+(mm[tx][ty-1]!=mm[tx][ty]);
for (i=1;i<=x;i++)
{
mm[i][0]=mm[i][1];
mm[i][y+1]=mm[i][y];
}
for (i=1;i<=y;i++)
{
mm[0][i]=mm[1][i];
mm[x+1][i]=mm[x][i];
}
}
break;
}
t*=delta;
}
return ans;
}
int main()
{
scanf("%d%d%d",&x,&y,&cl);
for (i=1;i<=cl;i++)
scanf("%d",&tot[i]);
lans=0x7FFFFFFF;
for (q=1;q<=3;q++)
{
memset(top,0,sizeof(top));
srand(time(0));
for (i=1;i<=x;i++)
for (j=1;j<=y;j++)
{
m[i][j]=rand()%cl+1;
while (top[m[i][j]]==tot[m[i][j]])
m[i][j]=rand()%cl+1;
top[m[i][j]]++;
}
search();
if (ans<lans)
{
for (i=1;i<=x;i++)
for (j=1;j<=y;j++)
lm[i][j]=m[i][j];
lans=ans;
}
}
for (i=1;i<=x;i++)
{
for (j=1;j<=y;j++)
printf("%d ",lm[i][j]);
printf("
");
}
return 0;
}