关键词：
洛谷月赛“月”来“月”丧了，一月更比一月丧，做得我十分不“月”……
4月的两轮月赛，都只会T1，就写一下吧，等待后续更新……
先看看Round1的T1：
【R1T1】
网址：点我
【题意简述】
给定一个长度为n的序列，其中的元素均是1~m之间的正整数。
要求从中选出k个数，交换它们的位置，其他未被选中的数保持不变，使得变换后的序列中，相等的数总是排在一段连续区间。
要求最小化k。
1<=n<=105,1<=m<=20
【思路】
①想到枚举这n个数的全排列，对每个满足条件的全排列进行计算，更新答案。dfs的中途可以把已经不满足的递归树切掉，优化一下。时间复杂度O(n!*n)，期望得分20。
②发现因为最后的序列一定是m个连续的相同段组成，考虑枚举m的全排列，这样可以保证答案合法，再统计。时间复杂度O(m!*n)，期望得分40。
③对于②算法，可以用m个桶记录下原序列的前缀和，记sum[i][j]为序列1~i位中数j的个数，则一段区间[l,r]内不是j的个数为sum[r][j]-sum[l-1][j]，把最后的统计优化到m。时间复杂度O(m!*m)，期望得分70。
④考虑对③进行优化，发现有特殊的最优子结构性质。在③中，针对两个m的全排列，如果它们的前i位的数相同，但是可以有不同的顺序。
例如：1,5,3,2,4和2,5,1,3,4，它们的前4位数相同，但是顺序不一定要相同。它们的前4位在原序列中的长度相同。对于第5位，没有必要枚举所有的前四位的全排列，只需要在数相同的全排列中寻找最小值即可。
即对于一个k最优的解，它对应的m的全排列是P，P的前i位记作Pi。必然有Pi是所有Pi的全排列中的最优解。即最优子结构性质。
考虑进行状压dp，用f[S]表示集合S的全排列对应到原序列的前面若干位中的最优解。S只可能包含1~m之间的正整数。
则f[S]=min( f[S-k] + (sum[r(S)][k]-sum[r(S-k)][k]) ) k∈S。sum数组即③中sum数组，r(S)表示集合S（表示一个m的排列）对应到原序列中的长度。
时间复杂度O(2m*m)，期望得分100。
【代码】
1 #include<cstdio> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 #define F2(i,a,b) for(int i=a;i<b;++i) 4 int n,m,num[20],sum[100001][20],f[1<<20]; 5 inline int Max(int p,int q){return p>q?p:q;} 6 void init(){ 7 int x; 8 scanf("%d%d",&n,&m); 9 F(i,1,n) scanf("%d",&x),sum[i][x-1]=1,++num[x-1]; 10 F2(j,0,m) F(i,1,n) sum[i][j]+=sum[i-1][j]; 11 } 12 int main(){ 13 init(); 14 int s; 15 F2(S,1,1<<m){ 16 s=0; 17 F2(i,0,m) 18 if((S>>i)&1)s+=num[i]; 19 F2(i,0,m) 20 if((S>>i)&1)f[S]=Max(f[S],f[S^(1<<i)]+sum[s][i]-sum[s-num[i]][i]); 21 } 22 printf("%d",n-f[(1<<m)-1]); 23 return 0; 24 }
我这里是f[S]表示最多的不动元素，会稍微好算一点点……原理不变。
R1接下来的就不会了，都是大丧题。
【R2T1】
网址：点我
【题意简述】
给定n，对于x=1~n，求出 \(\sum_{i=1}^{n}x\;mod\;n\) 。
【思路】
就直接讲吧，我先打出了这样一个表格：
第 i 行第 j 列表示 i mod j 的值。
从左往右竖着看，第1列是0，第2列重复1,0循环，第3列重复1,2,0循环……
每加入一列，就给总结果加上了若干个等差数列。
对于等差数列的加法，可以用两次差分，最后两次前缀和的方法把其变为常数时间。
总共要进行 \(\sum_{i=1}^{n}\frac{n}{i}\;=\;n\;ln(n)\) 次差分。时间复杂度O(n*lnn)。
【代码】
1 #include<cstdio> 2 long long n,a[1000002]; 3 int main(){ 4 scanf("%d",&n); 5 for(int i=2;i<=n;++i){ 6 for(int j=0;j<=n;j+=i) 7 a[j]-=i,a[j+1]+=i; 8 ++a[0]; 9 } 10 for(int i=1;i<=n;++i) a[i]=a[i-1]+a[i]; 11 a[0]=0; 12 for(int i=1;i<=n;++i) a[i]=a[i-1]+a[i]; 13 for(int i=1;i<=n;++i) printf("%lld ",a[i]); 14 return 0; 15 }
洛谷4月月赛r1
T1.题目大意：n个人站成一排，有m个团队，每个人有且属于一个团队，可以让若干个人出队，任意交换这些人的位置后再站回去，问要让所有同一团队的人连续地站在一起，至少要出队几个。（n<=10^5，m<=20）思路：求至少出... 查看详情
p3819松江1843路（洛谷月赛）
P3819松江1843路题目描述涞坊路是一条长L米的道路，道路上的坐标范围从0到L，路上有N座房子，第i座房子建在坐标为x[i]的地方，其中住了r[i]人。松江1843路公交车要在这条路上建一个公交站，市政府希望让最多的人得到方便，因... 查看详情
p3818小a和uim之大逃离ii（洛谷月赛）
P3818小A和uim之大逃离II题目背景话说上回……还是参见 https://www.luogu.org/problem/show?pid=1373 吧小a和uim再次来到雨林中探险。突然一阵南风吹来，一片乌云从南部天边急涌过来，还伴着一道道闪电，一阵阵雷声。刹那... 查看详情
求x！在k进制下后缀零的个数（洛谷月赛t1）
求x！在k进制下后缀和的个数20分： 求十进制下的x！后缀和的个数40分： 高精求阶乘，直接模拟过程(我不管反正我不打，本蒟蒻最讨厌高精了)60分（不管，反正我是70分QAQ，比赛结束后改了数据就a了...）：&... 查看详情
洛谷10月月赛r2·浴谷八连测r3-chtholly-t1
原题链接：https://www.luogu.org/problem/show?pid=3932月赛的时候只做了这一道题，而且暴力还写炸了。。。 其实，并不需要算很多的前缀和的a[i]表示i位置的物品数dis[i]表示每个储物点与一号的距离sum表示前i个储物点(物品数*距离)... 查看详情
洛谷11月月赛round.1
太感动了#2 thwfhk 240 (801ms) 100 100 40 又一张明信片，话说10月的怎么还没收到 P2246SAC#1-HelloWorld（升级版）题目背景一天，智障的pipapi正在看某辣鸡讲义学程序设计。题目描述在讲义的某一面，他... 查看详情
洛谷10月月赛round.1|p3400仓鼠窝[单调栈]
题目描述萌萌哒的Createdequal是一只小仓鼠，小仓鼠自然有仓鼠窝啦。仓鼠窝是一个由n*m个格子组成的行数为n、列数为m的矩阵。小仓鼠现在想要知道，这个矩阵中有多少个子矩阵！（实际上就是有多少个子长方形嘛。）比如说有... 查看详情
洛谷2017-2月月赛
打CF前随便打打，看了一眼只会做签到题，还挂了一次，95/400。 A.富金森林公园题目大意：给一个长度为n的数列，支持两种操作：1.修改一个数的值；2.给出一个k，问有多少段数大等于k。（N<=200,000）思路：求出大等k的数... 查看详情
洛谷10月月赛r1·普及组
SACE#1-一道不可做题Jelly这题是大水题，随便AC。就是要注意一点：初始温度与熔点的大小关系。就是因为这个。。wa了。。#include<iostream>usingnamespacestd;longlonga,b,c,d,e,f,tmp;intmain(){cin>>a>>b>>c>>d>>e>>f;if 查看详情
洛谷10月月赛round.3
Rank11:260=60+100+100 P2409Y的积木题目背景Y是个大建筑师，他总能用最简单的积木拼出最有创意的造型。题目描述Y手上有n盒积木，每个积木有个重量。现在他想从每盒积木中拿一块积木，放在一起，这一堆积木的重量为每块积木... 查看详情
洛谷9月月赛t1——预生成密码
其实这题只是一道比较简单的数学题。输入给出了a,b,c三个数的与或和由于要a尽可能小，a相同则b尽可能小，b相同则c尽可能小所以a最小一定是and，此时若要b尽可能小，c就要尽可能大，c最大就是or了，则b就等于sum-or-and。#include&... 查看详情
洛谷⑨月月赛round2官方比赛oi
自评：（完成时间3.5时）第一题模拟虽然A了，代码敲得有点慢第二题最短路第一次敲对了，又考虑数据范围和答案范围，改错了，100分改成42分。QAQ。 第三题乱搞80分还可以（因为没思路啊），不过也有A了的如果第二题不手... 查看详情
洛谷模拟城市2.0
一次洛谷月赛的T1，当时因为是信心赛，认为第一题应该不会太难，结果想了很久，直接额放弃正解选择暴力。。。简直就是巨坑的五维DP。。。mmd题目背景博弈正在机房颓一个叫做《模拟城市2.0》的游戏。2048年，经过不懈努力... 查看详情
洛谷10月月赛round.1|p3399丝绸之路[dp]
题目背景张骞于公元前138年曾历尽艰险出使过西域。加强了汉朝与西域各国的友好往来。从那以后，一队队骆驼商队在这漫长的商贸大道上行进，他们越过崇山峻岭，将中国的先进技术带向中亚、西亚和欧洲，将那里的香料、良... 查看详情
洛谷⑨月月赛round2p3392涂国旗[dp]
题目描述某国法律规定，只要一个由N*M个小方块组成的旗帜符合如下规则，就是合法的国旗。（毛熊：阿嚏——）从最上方若干行（>=1）的格子全部是白色的。接下来若干行（>=1）的格子全部是蓝色的剩下的行（>=1... 查看详情
洛谷10月月赛round.1|p3398仓鼠找sugar[lca]
题目描述小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会... 查看详情
洛谷⑨月月赛round2p3393逃离僵尸岛[最短路]
题目描述小a住的国家被僵尸侵略了！小a打算逃离到该国唯一的国际空港逃出这个国家。该国有N个城市，城市之间有道路相连。一共有M条双向道路。保证没有自环和重边。K个城市已经被僵尸控制了，如果贸然闯入就会被感染TAT.... 查看详情
洛谷洛谷p1011车站label：续命模拟qaq未知50分
题目描述火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上... 查看详情