zhangas

Pay more attention

0%

7.25SDKDACM

Posted on

P2362 围栏木桩

题目链接
T次询问 求序列最长上升子序列长度和个数 N^2可过
f[i]记录以a[i]结尾的序列长度
s[i]记录以a[i]结尾的序列个数
f[j]>=f[i]时 取最大个数 s[i]=s[j]
f[j]< f[i] 且 f[j]+1==f[i]时 加上a[i]使得序列长度相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<=n;i++){
    f[i]=s[i]=1;
    for(int j=1;j<i;j++){
        if(a[j]<=a[i]){//单调不减序列
            if(f[j]>=f[i]){
                f[i]=f[j]+1;
                s[i]=s[j];
            }
            else if(f[j]+1==f[i]){
                f[i]+=f[j];
            }
        }
    }
}

P2390 地标访问

题目链接
预处理出0到位置p的地标个数
四种情况1左 2右 3先左然后拐右 4先右然后拐右左
1 2 O(1)可以得到
3 4可以筛一遍地标 O(N) 注意t可能超过整个来回的可能 我就是错这里 就30pts了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int a[100005],b[100005];//预处理坐标P到原点之间的地标个数
int aa[50005],bb[50005];//存储地标
int l,r;
int lm,rm;//两端最远距离
int lc,rc;//两端地标个数
    int ans=0;
    //1 2两种情况
	if(t>=lm)
		ans=max(ans,lc);
	else
		ans=max(ans,a[t]);
	if(t>=rm)
		ans=max(ans,rc);
	else
		ans=max(ans,b[t]);
    //3 4两种情况
    for(int i=1;i<=lc;i++){
		if(t>aa[i]*2){//足够一个来回才有意义更新答案
			int g=t-aa[i]*2;
			int res=a[aa[i]];
			if(g>=rm)res+=rc;//如果返回后也超过另一方向
			else res+=b[g];	
			ans=max(ans,res);
		}
		
	}
	for(int i=1;i<=rc;i++){
		if(t>bb[i]*2){
			int g=t-bb[i]*2;
			int res=b[bb[i]];
			if(g>=lm)res+=lc;
			else res+=a[g];
			ans=max(ans,res);
		}
	}

P1388 算式

题目链接
2≤ n ≤ 15,0 ≤ k< n

预处理出区间和再 对K个乘法的位置爆搜81pts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n,m;
int a[50];
int b[50];//a数组的前缀和
int vis[50];
int ans;
//put * in position e
void dfs(int e,int d,int sum){//e是位置 d是深度 sum是局部答案
	if(d==m){
		ans=max(ans,sum*(b[n]-b[e]));
		return;
	}
	for(int i=e+1;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;
			dfs(i,d+1,sum*(b[i]-b[e]));
			vis[i]=0;
		}
	}
}
dfs(0,0,1);//是k+1个数的乘积 所以sum初始化为1

P1676 [USACO05FEB] Aggressive cows G

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sort(a+1,a+1+n);
int r=a[n]-a[1];//最大距离
int l=r;
for(int i=1;i<n;i++){
	l=min(l,a[i+1]-a[i]);//最小距离
}
//答案就在[L,R]中
while(l<r){
    int mid=(l+r+1)>>1;
    if(check(mid)){
        l=mid;
    }
    else r=mid-1;
}

check函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool check(int e){
    //检查满足最小距离为e的情况下 是否可以放置m个奶牛
    //有个贪心思想 如果从最右边的牛舍开始放都不能满足条件 那么从右侧某个牛舍开始也一定不能满足条件
    int cnt=1,res=a[1];
    for(int i=2;i<=n;i++){
        int t=a[i]-res;
        if(t>=e){
            cnt++;
            res=a[i];
        }
    }
    if(cnt>=m)return true;
    return false;
}