A.养花
flower.cpp/in/out
Time Limit: 1s
Memory Limit: 512MB
Description
小 C 在家种了 n 盆花, 每盆花有一个艳丽度 a i .
在接下来的 m 天中, 每天早晨他会从一段编号连续的花中选择一盆摆
放在客厅, 并在晚上放回. 同时每天有特定的光照强度 k i , 如果这一天里摆
放在客厅的花艳丽度为 x, 则他能获得的喜悦度为 x mod k i .
他希望知道, 每一天他能获得的最大喜悦度是多少.
Input Format
数据第一行包含两个正整数 n, m.
接下来一行 n 个正整数, 第 i 个数 a i 表示第 i 盆花的艳丽度.
接下来 m 行, 每行三个正整数 l i , r i , k i , 表示选花区间和光照强度.
Output Format
输出 m 行, 每行一个整数, 表示最大喜悦度.
Sample Input
5 5
1 2 3 4 5
1 3 2
2
1 3 3
1 4 4
5 5 5
3 5 3
Sample Output
1
2
3
0
2
Constraints
对于 20% 的数据, n, m ≤ 4000.
对于 40% 的数据, n, m ≤ 50000.
对于另外 20% 的数据, a i ≤ 300.
对于 100% 的数据, n, m, a i , k i ≤ 10 5 .
20分做法
对于每次询问，直接枚举即可。复杂度O(n^2)。
40分做法
可以预处理出k=1~300时所有位置的答案，开个桶就好。复杂度O((n+m)*300)
55分做法（我的做法）
考场上想到了分块，在每个块内预处理出k=1~300时的答案，对于k>300的部分，
可以对每个块开一个1e5的数组f，f[i]记录的是<i的这个块里出现的最大数，
这样，对于给定的k,k-(i-f[i]）就有可能成为最优解。查询时，对于每个整块，
分别令i=k,2k,3k...min(nk,100000),更新答案即可；对于非整块，暴力就好。
复杂度最坏是O(n^2)。不过实际评测时竟然没有一个点TLE。。。
100分正解
只需要预处理出上述过程的答案就好，复杂度O(n*(nlogn^0.5)),利用均值不等式，
易得出块大小N=1000时复杂度最优。
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline int
typedef long long ll;
I read(int &res){
re g=1;register char ch=getchar();res=0;
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
const int N=100000,E=1000;
int n,m,L,R,W,sum,X,Y,ans,l[101000],b[101000],f[110][101000],a[101000],len;
int main(){
//freopen("flower0.in","r",stdin);
//freopen("flower.out","w",stdout);
read(n);read(m);len=E;n--;
F(i,0,n){
read(a[i]);
b[i]=(i/len)+1;
}
F(i,1,b[n]){
memset(l,0,sizeof(l));
F(j,(i-1)*len,min(i*len,n)){
l[a[j]]=a[j];
}
F(j,1,N){
l[j]=max(l[j],l[j-1]);
}
F(j,1,N){
for(re k=0;k<=N;k+=j)f[i][j]=max(f[i][j],l[min(k+j-1,N)]-k);
}
}
while(m--){
read(L);read(R);read(W);L--;R--;
X=b[L];Y=b[R];ans=0;
if(X+1<=Y-1){
F(i,X+1,Y-1){
ans=max(ans,f[i][W]);
}
}
F(i,L,min(X*len,R)){
ans=max(ans,a[i]%W);
}
F(i,max(L,(Y-1)*len),R){
ans=max(ans,a[i]%W);
}
printf("%d
",ans);
}
return 0;
}
/*
5 5
1 2 3 4 5
1 3 2
1 3 3
1 4 4
5 5 5
3 5 3
*/
这题的数据好像有点问题，N只要不是1000就WA。。。
本来我的假程序好像是可以AC的。。。
B.折射
refract.cpp/in/out
Time Limit: 1s
Memory Limit: 128MB
Description
小 Y 十分喜爱光学相关的问题, 一天他正在研究折射.
他在平面上放置了 n 个折射装置, 希望利用这些装置画出美丽的折线.
折线将从某个装置出发, 并且在经过一处装置时可以转向, 若经过的装置坐
标依次为 (x 1 ,y 1 ),(x 2 ,y 2 ),...(x k ,y k ), 则必须满足:
• ∀j ∈ (1,k], y j < y j−1
• ∀j ∈ (2,k], x j−2 < x j < x j−1 or x j−1 < x j < x j−2
现在他希望你能告诉他, 一共有多少种不同的光线能被他画出来, 两
种光线不同当且仅当经过的折射装置的集合不同. 你只需要告诉他答案对
10 9 + 7 取模后的结果.
Input Format
第一行一个正整数 n, 表示折射装置的数量.
接下来 n 行, 每行两个整数 x i ,y i 表示折射装置的坐标.
Output Format
输出一行一个整数, 表示答案对 10 9 + 7 取模后的结果.
Sample Input
4
2 2
3 1
1 4
4 3
Sample Output
14
Constraints
对于 10% 的数据: n ≤ 700,1 ≤ x i ,y i ≤ N
对于 20% 的数据: n ≤ 1000,1 ≤ x i ,y i ≤ N
对于 50% 的数据: n ≤ 4000,|x i |,|y i | ≤ 10 9
对于 100% 的数据: n ≤ 6000,|x i |,|y i | ≤ 10 9
所有数据满足 ∀i ̸= j, x i ̸= x j and y i ̸= y j .
考试时只想到n^3暴力，想着可以骗10分，结果手残开了个f[6060][6060]没算空间，直接MLE。。
直接说正解吧。。
首先，肯定不能以y坐标排序，这样复杂度只能是n^3。
我们把所有点按x坐标升序排列。枚举i节点，考虑在已有的折线中加入i。
考虑到i的横坐标是最大的，所以它只可能是折线的第一个或第二个。
因为它是折线，我们自然就想到用左或右来作为一个dp转移的状态。
设f[i][0/1]表示i号节点为y坐标最大值时，折线接下来向左或向右的方案数。
那有哪些节点可以转移呢？
考虑枚举i之前的点j。
对于y[j]<y[i]的节点，f[j][1]自然而然可以转移到f[i][0]；
对于y[j]>y[i]的节点，i可以向j进行转移。
可是这样就存在一个问题：并不是所有的f[i][0]表示的折线都能合法地转移到f[j][1]。
因此，我们不得不枚举k，当？y[i]>y[k]且x[k]>x[j]时才能转移。
粗问题了！！！这不就n^3了吗？
但当我们再仔细研究这两个条件时，发现：f[i][0]是所有满足y[k]<y[i]的f[k][1]之和。
那如何处理f[i][0],才能满足x[k]>x[j]呢？
发现x坐标是有序的，那我们倒序枚举j不就行了吗！！
很好的一道思维题。。
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
I read(int &res){
res=0;re g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
struct P{
int x,y;
friend bool operator < (P a,P b){
return a.x==b.x?a.y<b.y:a.x<b.x;
}
}p[6060];
const int E=1e9+7;
int n,m,f[6060][2],ans;
int main(){
freopen("refract5.in","r",stdin);
freopen("refract.out","w",stdout);
read(n);
F(i,1,n){
read(p[i].x);read(p[i].y);
}
sort(p+1,p+1+n);
F(i,1,n){
f[i][0]=f[i][1]=1;
FOR(j,i-1,1){
if(p[j].y>p[i].y)f[j][1]=(f[j][1]+f[i][0])%E;
else f[i][0]=(f[i][0]+f[j][1])%E;
}
}
ans=E-n;
F(i,1,n){
ans=(ans+f[i][0])%E;
ans=(ans+f[i][1])%E;
}
printf("%d",ans);
return 0;
}
C.画作
paint.cpp/in/out
Time Limit: 1s
Memory Limit: 128MB
Description
小 G 的喜欢作画, 尤其喜欢仅使用黑白两色作画.
画作可以抽象成一个 r ×c 大小的 01 矩阵. 现在小 G 构思好了了他的
画作, 准备动笔开始作画. 初始时画布是全白的, 他每一次下笔可以将一个
四联通的部分涂成黑色或白色.
你需要告诉他, 在给出的构思下, 他最少需要下笔多少次才能完成画作.
Input Format
第一行两个正整数 r, c.
接下来 r 行, 每行 c 个字符, 表示目标画作.
Output Format
输出一行一个正整数, 表示最少需要的下笔步数.
Sample Input
3 3
010
101
010
Sample Output
2
Constraints
• Subtask 1 (19pts): r × c ≤ 15.
• Subtask 2 (7pts): r = 1.
• Subtask 3 (25pts): r, c ≤ 30.
• Subtask 4 (49pts): r, c ≤ 50.
不难证明猜到一个这样的结论: 存在一种最优方案使得每次操作的区
域是上一次的子集且颜色与上一次相反.
考虑归纳证明, 记 S 为当前所有操作区域的并, T 为接下来一步的操作
区域, 我们有:
- T 与 S 有交的情况一定可以转化成 T 被 S 包含的情况.
- T 与 S 交集为空时, 可以找一个连接 S 和 T 的集合 M 并操作 S ∪
T ∪M, 并将之前的所有操作连接到更外的层以及外层的连接部分同时
操作, 特殊处理最外层和第二层的情况. - T 被 S 包含时, T 落在某个完整区域内时等价于情况二, 否则一定连
接若干个同色块, 这些块可以同时处理, 步数一定不会更劣.
知道这个结论就比较好做了, 我们可以枚举最后被修改的区域, 这时答
案就是将同色边边权当作 0, 异色边边权当作 1 后距离这个点最远的黑色点
的距离, 对所有点取最小值即可.
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
I read(int &res){
res=0;re g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
const int INF=1e9+7;
char c[60][60];
int mx[5]={0,1,0,-1,0},my[5]={0,0,1,0,-1};
int n,m,X,Y,dis[60][60],ans;
typedef pair<int,int>pii;
#define mp(x,y) make_pair(x,y)
deque<pii>q;
IN B_1(int x,int y){
re res=0;
memset(dis,-1,sizeof(dis));
dis[x][y]=0;
q.push_back(mp(x,y));
while(!q.empty()){
x=q.front().first;y=q.front().second;q.pop_front();
if(c[x][y]=='1')res=max(res,dis[x][y]);
F(i,1,4){
X=x+mx[i];Y=y+my[i];
if(X>=1&&X<=n&&Y>=1&&Y<=m&&dis[X][Y]==-1){
if(c[x][y]==c[X][Y]){
dis[X][Y]=dis[x][y];
q.push_front(mp(X,Y));
}
else{
dis[X][Y]=dis[x][y]+1;
q.push_back(mp(X,Y));
}
}
}
}
return res;
}
int main(){
read(n);read(m);
F(i,1,n){
scanf("%s",c[i]+1);
}
ans=INF;
F(i,1,n){
F(j,1,m){
ans=min(ans,B_1(i,j));
}
}
printf("%d",ans+1);
return 0;
}
总结
本次模拟赛考了55+0+0。虽然考试时前两题都想到了非常接近正解的思路，
但就是差那么一点点。还是要多多打怪做题，积攒经验。