UOJ Logo root的博客

博客

【讨论帖】剑锋OI#Ⅱ期#秩序团#模拟赛#20180114#008

2018-02-09 13:40:18 By root

倒水

分三种情况讨论。 1.max(a[i])>t>min(a[i]) 直接输出Impossible。因为不论怎么加水,温度只会无限趋近于t而达不到t,n杯水的温度不可能相等。 2.min(a[i])≥t 此时加水只会让温度降低,因此只有温度为min(a[i])时才能相等,计算所有水温度降至min(a[i])所需的水的量,然后与c比较。若大于c则为Impossible,否则最大温度为min(a[i])。 3.max(a[i])≤t 此时加水会让温度升高,先计算所有水温度到达max(a[i])所需的水的量,若c仍有剩余,就把剩下的都加进去,计算最后的温度即为答案。

注意特判max[i]=t和min[i]=t的情况,不然会RE(除以0)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100000
using namespace std;
int t,n,ma,mi=0x7fffffff;
double c;
int a[MAXN+5],b[MAXN+5];
int main(){
    scanf("%d",&n);
    scanf("%d%lf",&t,&c);
    int now=c,ss=0;
    for (int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
        ss+=b[i]; ma=max(ma,a[i]); mi=min(mi,a[i]);
    }
    if (mi<t&&ma>t){
        printf("Impossible\n");
        return 0;
    }
    if (mi>=t){
        bool flag=false;
        for (int i=1;i<=n;i++){
            double x;
            if (mi!=t) x=(a[i]-mi)*b[i]/(mi-t);
            c-=x;
            if (c<0){
                flag=true;
                break;
            }
        }
        if (flag){
            printf("Impossible\n");
            return 0;
        }
        else{
            printf("Possible\n");
            double ans=mi;
            printf("%.4lf\n",ans);
            return 0;
        }
    }
    if (ma<=t){
        bool flag=false;
        for (int i=1;i<=n;i++){
            double x;
            if (ma!=t) x=(ma-a[i])*b[i]/(t-ma);
            c-=x;
            if (c<0){
                flag=true;
                break;
            }
        }
        if (flag){
            printf("Impossible\n");
            return 0;
        }
        else{ 
            printf("Possible\n");
            double ans=ma;
            double sum=now+ss-c;
            if (c){
                ans=(ma*sum+c*t)/(sum+c);
            }
            printf("%.4lf\n",ans);
            return 0;
        }
    }
    return 0;
}

合并回文字串

题解:dp,i代表a串开始的位置,j代表b串开始的位置,da,db分别代表在a和b中的长度,dp[x][y][z][h]代表 a中选下标为x到y-1的串 和 b中选z到h-1的串是否可以组合成回文串。利用每个字符串的长度更新dp[i][i + da][j][j + db]。

初始状态 da+db≤1时必为true

更新四种状态 a或b中任意一组 首位和末位相同时 可以进行更新。 存在四种情况 a[i] == a[i + da - 1] 或b[j] == b[j + db - 1]或a[i] == b[j + db - 1]或b[j] == a[i + da - 1]。

注意:不能用memset每次对dp处理 会TLE。需要在每次更新时先设置值。

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mod 1000000007
#define mp make_pair
#define pi acos(-1)
#define eps 0.00001
#define mst(a,i) memset(a,i,sizeof(a))
#define all(n) n.begin(),n.end()
#define lson(x) ((x<<1))  
#define rson(x) ((x<<1)|1) 
#define inf 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int maxn = 55;
int dp[maxn][maxn][maxn][maxn];

int main()
{
    ios::sync_with_stdio(false);
    int i, j, k, m, n, T;
    cin >> T;
    string a, b;
    while (T--)
    {
        int ans = 0;
        cin >> a >> b;
        for (int da = 0; da <= a.size(); ++da)
            for (int db = 0; db <= b.size(); ++db)
                for (int i = 0; da + i <= a.size(); ++i)
                    for (int j = 0; db + j <= b.size(); ++j)
                    {
                        if (da + db <= 1)
                            dp[i][i + da][j][j + db] = 1;
                        else
                        {
                            dp[i][i + da][j][j + db] = 0;  //替代memset
                            if (da >= 2 && a[i] == a[i + da - 1])
                                dp[i][i + da][j][j + db] |= dp[i + 1][i + da - 1][j][j + db];
                            if (db >= 2 && b[j] == b[j + db - 1])
                                dp[i][i + da][j][j + db] |= dp[i][i + da][j + 1][j + db - 1];
                            if (db >= 1 && da >= 1 && a[i] == b[j + db - 1])
                                dp[i][i + da][j][j + db] |= dp[i + 1][i + da][j][j + db - 1];
                            if (db >= 1 && da >= 1 && b[j] == a[i + da - 1])
                                dp[i][i + da][j][j + db] |= dp[i][i + da - 1][j + 1][j + db];
                        }
                        if (dp[i][i + da][j][j + db])ans = max(ans, da + db);
                    }
        cout << ans << endl;
    }
    return 0;
}

质数

前缀和, 线性筛

【讨论帖】剑锋OI#Ⅱ期#秩序团#模拟赛#20180114#007

2018-02-08 10:37:25 By root

背包

首先按价格从大到小排一遍序。

考虑跳着跳着走,每次先二分出能买的最大价格的物品的位置,走过去、

之后二分出能买的一段物品(用前缀和记录),减钱并购买之,跳到那一段的末尾。

之后再重复第一步,不断地一段一段走即可。

这样的时间复杂度为 O(MlogNlogN) 。

因为一个人的钱数每次至少减少一半(价格从大到小,不然就还能再买),

这样就最多二分 log 次,复杂度得证。

字典序

若 A i 排在 B i 前面,就 A i 向 B i 连一条有向边,这样就构成一个 DAG 。 那么做一遍拓扑排序,用一个小根堆存着,每次取最小,再把入度为零的点加入堆中即可。使用优先队列实现即可。 时间复杂度 O(N log N)

最长树链

枚举所以质因子,然后dfs的时候只走有当前这个质因子的点。。。这样的话正面看来复杂度貌似很大,最多有10W个质因子,每次dfs复杂度上限也是10W,,貌似会超时? 这个时候要从另外一个角度计算复杂度啦。我们对一个数来考虑,他会被几次dfs遍历到?。很显然就是它的质因子的数量次,,一个数的质因子数比logn还要小很多。所以所有数只会被遍历到最多 nlogn次,复杂度也差不多nlogn级别的,就不会超时了。

【讨论帖】剑锋OI#Ⅱ期#秩序团#模拟赛#20180114#006

2018-01-14 13:47:18 By root

楼下……

【讨论帖】剑锋OI#Ⅱ期#秩序团#模拟赛#20180110#005

2018-01-14 13:39:31 By root

楼下……

解题报告:“剑锋OI”普及组多校联盟系列赛(13)By 绣湖中学 Sooke

2017-12-04 10:11:02 By root

T1 – 定向运动

本题算法: 模拟 思路概述: 统计出不去除任何打卡点的总路程,接下来用一层循环枚举去除哪个打卡点,因为去除一个打卡点只会对相邻两个打卡点间的路程造成影响,对其他打卡点的路程没有影响,所以只需要计算去掉该打卡点后新的总路程减少了多少。通过枚举,得到最大的减少量,从而使总路程减去该量得到答案。

#include <cstdio>
#define Abs(n) ((n) < 0 ? 0 - (n) : (n))
// 定义绝对值

int n , x[100001] , y[100001] , sum = 0 , dis , _max = 0;

int main(){
    scanf("%d" , &n);
    for(int i = 1 ; i <= n ; i++)
        scanf("%d%d" , &x[i] , &y[i]);
    for(int i = 2 ; i <= n ; i++)
        sum += Abs(x[i] - x[i - 1]) + Abs(y[i] - y[i - 1]); // 先统计出原总路程
for(int i = 2 ; i < n ; i++){
        // 枚举删除 2 至 n -1 的打卡点,计算得到减少量 dis
        dis  = Abs(x[i] - x[i - 1]) + Abs(y[i] - y[i - 1]);
        dis += Abs(x[i + 1] - x[i]) + Abs(y[i + 1] - y[i]);
        dis -= Abs(x[i + 1] - x[i - 1]) + Abs(y[i + 1] - y[i - 1]);
        _max = _max < dis ? dis : _max;
    }
    printf("%d\n" , sum - _max); // 将原总路程减去减少量,即为答案
    return 0;
}

T2 – 亮 灯

本题算法: 搜索,链表存储

思路概述: 首先,只有(1,1)房间有按钮打开其他房间的灯时,你才能到其他房间打开更多的灯。 也就是说,先将(1,1)房间中能打开的所有灯打开,这点是毋庸置疑的。 接下来,移动空间可能会增大,一开始在(1,1)处,如果打开了(1,2)的灯,将可以移动到房间(1,2)。但需要注意的是,并不是所有被打开了的灯都可以直接移动到那个房间,仅当那个房间有已经可以到达的相邻房间,才可以通过那个房间到达自己。因此使用两个二维数组,g[i][j]表示(i,j)的灯是否打开,vis[i][j]表示(i,j)是否可以到达。显然一开始g[1][1]=vis[1][1]=true。 所以我的思路就是广搜,运用队列,首先将(1,1)推入队列,队列里的房间一定是可以到达的。如果队首是某个房间,首先打开所有在那个房间里能打开的灯,即修改 g 数组,每修改一个,就查看那个房间是否拥有已经可以到达的相邻房间,有则推入队列,修改vis数组,无则暂时跳过。并且,队首的房间做完以上操作后,还要看看自己是否有相邻的房间,灯亮,但 vis 数组仍为 false,如果有,将其推入队列,则修改 vis 数组,无则此步骤无效。最后,统计 g 数组有多少个 1。 以上就是整个程序的思路,尽管是搜索,但仍然是很高效的,每个房间至多进队列 1 次,时间复杂度也因此在 O(n ^ 2) 左右。其实本题还有一个考点,就是链式前向星的运用,应该可以用 stl 的vector,这里不解释原理,请自行学习。

#include <cstdio>

struct List{
    int l , ls[101][101] , nx[100001] , dx[100001] , dy[100001];
    void Init(int d){
        for(int i = 1 ; i <= d ; i++)
            for(int j = 1 ; j <= d ; j++)
                ls[i][j] = -1;
        l = 0;
    }
    void Insert(int x , int y , int tx , int ty){
        nx[l] = ls[x][y] , dx[l] = tx , dy[l] = ty;
        ls[x][y] = l++;
    }
}; // 链表,可用 vector 代替之

List L;
int n , m , x , y , tx , ty , cnt = 0 , qx[100001] , qy[100001];
const int px[5] = {0 , 0 , 0 , 1 , -1}; // 偏移量数组
const int py[5] = {0 , 1 , -1 , 0 , 0}; // 偏移量数组
bool vis[102][102] , g[102][102];
int main(){
    scanf("%d%d" , &n , &m);
    L.Init(n);
    for(int i = 1 ; i <= m ; i++)
        scanf("%d%d%d%d" , &x , &y , &tx , &ty),
        L.Insert(x , y , tx , ty);
    g[1][1] = vis[1][1] = true;
    qx[1] = qy[1] = 1; // 先将 (1,1) 推入队列
    for(int l = 1 , r = 1 , ux , uy , vx , vy ; l <= r ; l++){
        ux = qx[l] , uy = qy[l]; // 取出队首
        for(int i = L.ls[ux][uy] ; i != -1 ; i = L.nx[i]){
            vx = L.dx[i] , vy = L.dy[i]; // 遍历其能打开的所有灯
            if(g[vx][vy])
                continue; // 如果已经被打开,跳过以下操作
            g[vx][vy] = true; // 打开房间的灯
            for(int j = 1 ; j <= 4 ; j++)
                if(vis[vx + px[j]][vy + py[j]]){
                    ++r , qx[r] = vx , qy[r] = vy , vis[vx][vy] = true; // 未被访问,推入队列
                    break;
                }
        }
        for(int i = 1 ; i <= 4 ; i++){
            vx = ux + px[i] , vy = uy + py[i]; // 然后是看能否到达四周房间
            if(vx < 1 || vy < 1 || vx > n || vy > n)
                continue; // 超出范围排除
            if(g[vx][vy] && !vis[vx][vy])
                ++r , qx[r] = vx , qy[r] = vy , vis[vx][vy] = true; // 能到达,推入队列
        }
    }
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
            cnt += g[i][j]; // 统计多少房间的灯能被打开
    printf("%d\n" , cnt);
    return 0;
}

T3 – 出 题

本题算法: 动态规划(背包)

思路概述: 背包问题比较容易地能看出,对某个算法出题,无非是一题都不出,或出若干道题,而题目的 n 又很小,因此可以枚举该算法出题的数量。
使用 f[i] 表示设计 i 道试题耗费的最少时间,初始化 f[0] = 0,其他为 inf。题目有一个坑点就是有些变量和数组要用 long long,正如 f 数组即其初值,其实也不难看出,因为题目中的耗时计算公式有次方。 对于每种算法,已知其 时间系数 a 和 指数 b,如果现在要设计 i 道试题,而设计本算法前只设计了 j 道试题,状态转移方程即为 f[i] = max{f[i] , a f[j] ^ b},只要按着公式就行了。 最后答案在 f[n],时间复杂度 O(m n ^ 2),n 和 m 都比较小,不用担心超时问题。

#include <cstdio>

long long pow[201][6] , f[201];
int n , m , x , y;

int main(){
    scanf("%d%d" , &n , &m);
    pow[0][0] = f[0] = 0;
    for(int i = 1 ; i <= n ; i++)
        pow[i][0] = 1 , f[i] = (long long)1 << 60;
    // 预处理出 0 ~ n 的 0 ~ 5 次方,为下面的幂运算作准备
    for(int i = 0 ; i <= n ; i++)
        for(int j = 1 ; j <= 5 ; j++)
            pow[i][j] = pow[i][j - 1] * i;
    for(int i = 1 ; i <= m ; i++){
        scanf("%d%d" , &x , &y);
        for(int j = n ; j >= 1 ; j--)
            for(int k = 0 ; k < j ; k++)
                if(f[j] > f[k] + pow[j - k][y] * x)
                    f[j] = f[k] + pow[j - k][y] * x; // 状态转移,更新
    }
    printf("%lld\n" , f[n]);

T4 – 积木城堡

本题算法: 动态规划(背包)

思路概述: 会上一题的人这一题也应该不难吧。对于某个城堡的积木,要么取,要么不取,很显然的0,1背包。对于每个城堡,都作一次0,1背包,用 f[i] 表示高度为 i 的城堡是否能用那些搭,初始化 f[0] 为 true,其他为 false。对于每一块积木,高度为 j,如果要搭高度为 i 的城堡,可以得到转移方程 f[i] = f[i] | f[i - j],其中的 | 是或运算,只要 f[i] 和 f[i – j] 某一个为 true,f[i] 就为 true。 难点在于如何知道对于某个高度,所有城堡都能搭到,解决方法,就是新增数组 c,c[i] 表示能搭到高度 i 的城堡有多少个。做完每个城堡单独的背包后,如果 f[i] 为 true,则给对应的 c[i] 加上一个 1,最后倒序得出最大的 i,使 c[i] = n,为什么?因为如果 c[i] 为 n,就表示能搭到高度为 i 的城堡有 n 个,即所有城堡都能搭到高度 i(也只有 n 个城堡)。题目中提到无方案时输出 0,这个只要让 i 倒序枚举到 0 就可以解决,因为不管哪个城堡做的背包,f[0] 始终是 true,c[0] 也始终是 n 了。

#include <cstdio>
#include <cstring>
int n , m , sum , a[102] , f[10001] , c[10001];
int main(){
    scanf("%d" , &n);
    for(int i = 1 ; i <= n ; i++){
        m = 0 , sum = 0;
        while(true){
            scanf("%d" , &a[++m]);
            if(a[m] == -1)
                break; // 如果读入 -1,退出读取的循环过程
            sum += a[m]; // 统计该城堡能搭到的最高高度
        }
        m--; // 因为多读入了一个 -1,减回去
        memset(f , false , sizeof(f));
        f[0] = true; // 每次都要记得初始化,因为背包相互独立
        for(int i = 1 ; i <= m ; i++)
            for(int j = sum ; j >= a[i] ; j--)
                f[j] |= f[j - a[i]]; // 状态转移
        for(int i = 0 ; i <= sum ; i++)
            c[i] += f[i]; // 将 f[i] 的值加到 c[i] 中
    }
    for(int i = 10000 ; i >= 0 ; i--)
        if(c[i] == n){
            printf("%d\n" , i); // 倒序枚举出最大的可行高度
            break; // 注意退出
        }
    return 0;
}

#剑锋OI#Ⅱ期#任务单#最近更新20171109

2017-11-09 10:29:22 By root

解题报告:“剑锋OI”普及组多校联盟系列赛(09)#Sooke殿姥国历险记

2017-11-05 15:54:19 By root

感谢Sooke大佬为SSOI普及组多校联盟作出的伟大贡献,Sooke不仅是一个优秀的OIER,更是一个无私的分享者。

RP++

T1 – 特 训

本题算法:模拟

思路概述: 无脑做法,即每次先用变量记录三个人每两个人相邻的距离,再按照记录的距离行进。 还有一种更加优秀的思路。因为在每秒结束前,阿零已经自己想好了下一步的走法,而阿六是看阿零的位置知道下一步的走法,而阿三又是靠阿六的位置。对此,可以发现:下一步的走法与后面的人无关。因此,我们可以先让阿三按情况走,这对阿六和阿零没有任何影响。再让阿六走,这对阿零下一步的走法没有影响。最后才让阿零走。这看起来是按一定顺序来处理的,实际上这与三个人同时走是一样的结果。 事实上本题还有一种更加高深的解法,三个人在特训后的相隔开的距离只与阿零行走方式数列的后两项有关,因此,我们按数列,只让阿零行走,最后在根据最后两项处理出阿三和阿六的位置即可。 所以整道题的时间复杂度是 O(n)。


#include <iostream>
using namespace std;
int n , opt , x , y , z;
// x,y,z 分别存储阿三,阿六,阿零的当前位置 
int main(){
    cin >> n;
    x = 1 , y = 2 , z = 3; // 注意三个人的起始位置 
    for(int i = 1 ; i <= n ; i++){
        cin >> opt;
        // 输入阿零这一秒的行走方式
        // 因为阿三和阿六这一秒的行走方式只取决于前面那个人,与后面的人无关
        // 所以我们可以按 阿三,阿六,阿零 的顺序处理(其实他们本应是同时的)
        if(y - x == 1)
            x = x + 1; // 小步走
        else
            x = x + 2; // 大步走
        if(z - y == 1)
            y = y + 1;
        else
            y = y + 2;
        if(opt == 1)
            z = z + 1;
        else
            z = z + 2; 
    }
    cout << x << " " << y << " " << z << endl; // 分别输出三个人的位置 
    return 0;
}

T2 – 出 征

本题算法: 计数思想(桶),排列组合(简单数论)

思路概述: (注:以下所有士兵直接转换成边来讲,士兵的个数转换为边的长度) 三个细节务必要注意,如果有三条边,必须保证三条边中至少两条长度相等,长度之和大于等于给定的 k,而且最重要的:三条边必须满足任意两边长度之和大于第三边(构成三角形的条件)! 首先是 50 到 60 分的做法,三重循环枚举三条边,最后按上面的方式一一判断,时间复杂度为 O(n^3),毋庸置疑是特别大的。但只要拿到这个分数,说明你的数学还是稳稳的。 如何拿到 100 分呢?经过观察数据范围,我们发现边的长度不超过 3000,即使 n 已经达到了 100000,满满的计数思想。我们使用数组 a[i] 记录 n 条边中,长度为 i 的条数。因为要构成等腰三角形嘛,所以因为腰长相等,我们只需要从 1 ~ 3000 枚举腰长 i ,再枚举底边 j。 这个时候的判断需要仔细思考。和暴力做法类似,我们先判断 2 个长度为 i 的边和 1 个长度为 j 的边能否构成三角形,且 2 i + j 是否大于等于 k。接下来,分情况讨论,如果 i != j,即暂时排除了构成等边三角形的可能性。因为我们要选两条腰作为三角形的边,即从 a[i] 中选取 2 条,回忆一下,这不就是排列组合的内容吗。这个时候,我们很容易得到腰的选取方式一共有 C(a[i] , 2) 种。类似地,底边的选取方式有 C(a[j] , 1) 种。此时总共有 C(a[i] , 2) C(a[j] , 1) 种。统计入答案。 注意上面排除了等边三角形,那如果是等边三角形怎么办呢?它也是特殊的等腰三角形啊!这更加容易,枚举边长 i,判断 i * 3 是否大于等于 k,此时不用判断三角形构成的基本条件,因为任何的 i + i 一定大于另一个 i!对于满足条件的 i,方案数有 C(a[i] , 3) 种,统计入答案。 最后输出答案。时间复杂度为 O(3000 ^ 2)。(忽略常数影响,这复杂度是足够的)

#include <iostream>
#define M 1000000007

using namespace std;

long long s = 0;
int n , k , t , a[3001];
// a[i] 表示士兵数有 i 个的共有 a[i] 种 

inline int C1(int p){
    // 函数:返回 p 个中选取 1 个的组合数
    return p; 
}
inline int C2(int p){
    // 函数:返回 p 个中选取 2 个的组合数,注意 long long 
    return ((long long)p * (p - 1) / 2) % M;
}
inline int C3(int p){
    // 函数:返回 p 个中选取 3 个的组合数
    return ((long long)p * (p - 1) * (p - 2) / 6) % M; 
}

int main(){
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++)
        cin >> t , a[t]++; // 计数
    for(int i = 1 ; i <= 3000 ; i++) // 选取底边
        for(int j = 1 ; j <= 3000 ; j++) // 选取腰
            if(i != j) // 排除等边三角形
                if(j + j > i && i + j + j >= k) //构成三角形的基本条件 & 题目的条件
                    s = (s + C1(a[i]) * C2(a[j])) % M; // 底边选一个,腰选两个,统计
    for(int i = 1 ; i <= 3000 ; i++) // 特殊判断等边三角形
        if(i + i + i >= k)
            s = (s + C3(a[i])) % M; // 边选三个 
    cout << s;    
    return 0;
}

T3 – 扎 营

本题算法: 动态规划(或 单调栈)

思路概述: 这题可能稍难了一点,但骗分法正确能骗到不少分。 在看正解前,我们先来清晰一下这种题的原理。

0 1 1 1 # 1 1 0

1 1 1 1 1 1 1 1

1 1 0 1 1 0 1 1

1 1 1 1 0 1 1 1

如上面的0,1矩阵(a 和 b 当作是 1),我们想以 # 为边缘上元素,向下找最大的全 1 子矩阵。
我们先不求“大”,假设这个子矩阵只有一行,这个时候我们向左右伸展,得到这样一个子矩阵:

0 b b b a b b 0

1 1 1 1 1 1 1 1

1 1 0 1 1 0 1 1

1 1 1 1 0 1 1 1

这是向下找且只有 1 行最大的全 1 子矩阵。接下来,我们继续向下找,且让行数为 2,结果会如何呢?很显然,下面的子矩阵是向下找且只有 2 行最大的全 1 子矩阵:

0 b b b a b b 0

1 b b b b b b 1

1 1 0 1 1 0 1 1

1 1 1 1 0 1 1 1

你是否已经有思路了?别急,搜到第 3 行情况就截然不同了。如果我们像第 2 行一样,直接向下将所有元素包括进去,到第 3 行,我们就会将 0 包括进去,显然不符合条件,这个时候,我们只好缩小它的宽,如下面的全 1 子矩阵:

0 1 1 b a 1 1 0

1 1 1 b b 1 1 1

1 1 0 b b 0 1 1

1 1 1 1 0 1 1 1

思路应该已经很清晰了,我们发现向下搜子矩阵的高在增大的过程中,它的宽,只会缩小,变大却是不可能的,因此我们预处理出 sl[i][j] 和 sr[i][j],分别表示第 i 行第 j 列的元素向左和向右伸展最远的列号。以 #(询问点)所在的列为基准线,如果无法再向下找(基准线被 0 阻挡,上面的例子到了第 4 行就是此现象),停止搜索,如果还能向下,即按照 sl 和 sr 数组缩小我们当前边界,即全 1 子矩阵的宽。此时不断根据高和宽刷新面积最大值,只能得到向下搜最大的答案。
为什么是只能?因为有四个方向要搜!不辞辛苦,全部都是类似的过程。只要你上面理解了,不管是上下左右,码起来也不是这么难了。注意新添数组 su[i][j] 和 sd[i][j],是上下伸展数组。
上面是面对操作 2 的解释,操作 1 十分简单,一开始我们预处理一遍数组 sl,sr,su,sd(每行每列都要预处理),而操作 1 只需要取反,再修改目标点所在行 sl,sr 和所在列 su,sd 的值即可。两个操作的时间复杂度都是 O(nm),总复杂度是 O(qnm),最大不超过 O(1000^3)(忽略常数)

#include <cstdio>
#define Max(x , y) ((x) > (y) ? (x) : (y))
#define Min(x , y) ((x) < (y) ? (x) : (y))

inline int Input(){
    // 函数 : 快速读入一个 0 或 1 
    char c = getchar();
    while(c != '0' && c != '1')
        c = getchar();
    return c == '1';
}

int n , m , q , opt , x , y , resl , resr , resu , resd;
bool a[1002][1002];
int sl[1002][1002] , sr[1002][1002] , su[1002][1002] , sd[1002][1002];
// sl[i][j] 表示 第 i 行第 j 列的 1  向左最远伸展到 1 的列数
// sr[i][j] 表示 第 i 行第 j 列的 1  向右最远伸展到 1 的列数
// su[i][j] 表示 第 i 行第 j 列的 1  向上最远伸展到 1 的行数
// sr[i][j] 表示 第 i 行第 j 列的 1  向下最远伸展到 1 的行数

void UpdateLine(int p){
    // 函数:修改第 p 行的伸展信息
    for(int i = 1 ; i <= m ; i++)
        if(a[p][i])
            if(a[p][i - 1])
                sl[p][i] = sl[p][i - 1]; // 如果左边有连续的 1 ,延续 
            else
                sl[p][i] = i; // 如果左边没有连续的 1,自立 
    // 下面的处理方式类似 
    for(int i = m ; i >= 1 ; i--)
        if(a[p][i])
            if(a[p][i + 1])
                sr[p][i] = sr[p][i + 1];
            else
                sr[p][i] = i;
} 
void UpdateRow(int p){
    // 函数:修改第 p 列的伸展信息 
    for(int i = 1 ; i <= n ; i++)
        if(a[i][p])
            if(a[i - 1][p])
                su[i][p] = su[i - 1][p];
            else
                su[i][p] = i;
    for(int i = n ; i >= 1 ; i--)
        if(a[i][p])
                    if(a[i + 1][p])
                sd[i][p] = sd[i + 1][p];
            else
                sd[i][p] = i;
}
int FindUp(int p , int k){
    // 函数:以第 p 列为基准,从第 k 行向上找矩阵
    int mx , l , r; // mx 储存当前的最大答案,l 和 r 分别为选中的左右边界
    int cnt = 1; // cnt 为目标矩阵的高度 
    l = sl[k][p] , r = sr[k][p]; // 获得初始左右边界(目标矩阵的宽度) 
    mx = cnt * (r - l + 1); // 初始化目标矩阵大小,记录为可能的最大答案 
    for(int i = k - 1 ; i >= 1 ; i--)
        if(a[i][p] == 0)
            break; // 无法向上扩大了,退出寻找
        else
            cnt++, // 高度增加 
            l = Max(l , sl[i][p]) , r = Min(r , sr[i][p]), // 以选中列为基准缩小边界
            mx = Max(mx , cnt * (r - l + 1)); // 更新答案
    return mx; // 返回最终的答案
    // 下面的其他方向都是类似的过程 
}
int FindDown(int p , int k){
    // 函数:以第 p 列为基准,从第 k 行向下找矩阵
    int mx , l , r;
    int cnt = 1; 
    l = sl[k][p] , r = sr[k][p]; 
    mx = cnt * (r - l + 1);
    for(int i = k + 1 ; i <= n ; i++)
        if(a[i][p] == 0)
            break;
        else
            cnt++, 
            l = Max(l , sl[i][p]) , r = Min(r , sr[i][p]),
            mx = Max(mx , cnt * (r - l + 1));
    return mx; 
}
int FindLeft(int p , int k){
    // 函数:以第 p 行为基准,从第 k 列向左找矩阵
    int mx , u , d;
    int cnt = 1; 
    u = su[p][k] , d = sd[p][k]; 
    mx = cnt * (d - u + 1);
    for(int i = k - 1 ; i >= 1 ; i--)
        if(a[p][i] == 0)
            break;
        else
            cnt++, 
                        u = Max(u , su[p][i]) , d = Min(d , sd[p][i]),
            mx = Max(mx , cnt * (d - u + 1));
    return mx; 
}
int FindRight(int p , int k){
    // 函数:以第 p 行为基准,从第 k 列向右找矩阵
    int mx , u , d;
    int cnt = 1; 
    u = su[p][k] , d = sd[p][k]; 
    mx = cnt * (d - u + 1);
    for(int i = k + 1 ; i <= m ; i++)
        if(a[p][i] == 0)
            break;
        else
            cnt++, 
            u = Max(u , su[p][i]) , d = Min(d , sd[p][i]),
            mx = Max(mx , cnt * (d - u + 1));
    return mx; 
}

int main(){
    scanf("%d%d%d" , &n , &m , &q);
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            a[i][j] = Input();
    for(int i = 1 ; i <= n ; i++)
        UpdateLine(i);
    for(int i = 1 ; i <= m ; i++)
        UpdateRow(i);
    // 预处理先跑一遍 
    for(int i = 1 ; i <= q ; i++){
        scanf("%d%d%d" , &opt , &x , &y);
        if(opt == 1){
            a[x][y] ^= 1; // 更改操作,给自己取反 
            UpdateLine(x) , UpdateRow(y); // 修改伸展数组
            continue;
        }
        if(a[x][y] == 0){
            printf("0\n"); // 目标点都是 0,选出来不论怎样都不可能全 1,直接输出 0 
            continue;
        }
        resu = FindUp(y , x) , resd = FindDown(y , x); // 向上下找,过程需要缩小左右区间 
        resl = FindLeft(x , y) , resr = FindRight(x , y); // 向左右找,过程需要缩小上下区间 
        printf("%d\n" , Max(Max(resu , resd) , Max(resl , resr))); // 输出最大值 
    }  
    return 0;
}

T4 – 决 战

本题算法: 双向链表

思路概述: 本题相对上一题应该更简单一些,其实有一个精髓是差不多的。上一题我们以 sl 和 sr 表示元素的左右伸展,本题中,我们可以用 l[i] 和 r[i] 分别表示第 i 个部分的军队左右最近的敌对军队,如果 l[i] 或 r[i] 为 0,则表示左或右没有敌对军队。 我们可以从左向右遍历现存的军队。不难发现,如果多个友方军队紧邻,那么他们左右最近的敌对军队一定是一样的!因此,如果遍历时,前一个元素和当前元素是同一方,则复制它 l 数组中的值,否则,也就是它们互为敌人,将自己 l 数组中的值设为它。 得到 r 数组是类似的,但是我们需要从右往左遍历。 最后,再遍历一遍现有军队,此时我们已经知道任何军队左右最近的敌对军队了,所以按照题意,直接加加减减,找出受损值最大的并记录其序号。然后删除它。 如何删除?将他的士兵先分了再将他的士兵数设为 0 吗?显然是不合理的。考虑到这个部分的军队已经被打败了,也就是不复存在,这个时候它左右的军队就变成近邻了,应该不难想到用双向链表来维护。 还有一个小细节,就是士兵的叛变。根据 l[i] 和 r[i],来判断是由几个军队打败的。如果是单个敌对军队击败的,直接删除并将士兵全部转移过去。否则,平分(其实直接整除二就行了)。至于如何判断决战结束,我们可以统计每个国家所占士兵数,删除某个部分给该国家占有士兵数减一,如果某个国家的这个值为 0,即另一个国家胜利。 每次战争要 O(n) 时间复杂度遍历(或 O(3n),就算O(n) 好了),最差复杂度不超过 O(n ^ 2)。

#include <iostream>
using namespace std;
int n , m[2] , cnt = 0 , resn;
int ls[3001] , nx[3001] , lsp , nxp;
// 使用双向链表,ls[i] 和 nx[i] 分别表示第 i 个部分当前的前驱和后继
// lsp 表示当时位于最左边的部分编号,nxp 表示当时位于最右边的军队编号
int l[3001] , r[3001];
// l[i] 和 r[i] 分别表示第 i 个部分左右的最近敌对军队编号 
bool f[3001]; // 每个部分的士兵国籍
long long a[3001] , res; // 每个部分的士兵数量,注意要用 long long
int main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> f[i] , m[f[i]]++; // 输入国籍,m 记录每个国家有多少个部分 
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i]; // 输入数量
    for(int i = 2 ; i <= n ; i++)
        ls[i] = i - 1;
    for(int i = 1 ; i <  n ; i++)
        nx[i] = i + 1;
    lsp = 1 , nxp = n; // 初始化双向链表
       while(m[0] != 0 && m[1] != 0){ // 只要仍有敌国军队,战争不会结束 
        cnt++; // 战争数增加
        l[lsp] = 0 , r[nxp] = 0;
        for(int i = nx[lsp] ; i != 0 ; i = nx[i])
            if(f[ls[i]] == f[i])
                l[i] = l[ls[i]]; // 如果左邻部分是我方,那么面临敌人相同
            else
                l[i] = ls[i]; // 否则,左邻部分就是自己的敌人了
        // 下面处理右边的敌人,是类似的,但是这次是逆序 
        for(int i = ls[nxp] ; i != 0 ; i = ls[i])
            if(f[nx[i]] == f[i])
                r[i] = r[nx[i]];
            else
                r[i] = nx[i];
        // 处理完左右的敌人,就可以扫一遍找最大受损值了 
        // 如果左或右没有敌人,不用担心,因为 a[0] 还是 0 
        res = 0 - ((long long)1 << 62) , resn = 0;
        for(int i = lsp ; i != 0 ; i = nx[i])
            if(res < a[l[i]] + a[r[i]] - a[i])
                res = a[l[i]] + a[r[i]] - a[i] , resn = i;
        // 士兵叛变
        if(l[resn] == 0)
            a[r[resn]] += a[resn]; // 左边没有敌人,是被右边单独打败的
        else if(r[resn] == 0)
            a[l[resn]] += a[resn]; // 右边没有敌人,是被左边单独打败的
        else
            a[l[resn]] += a[resn] / 2 , a[r[resn]] += a[resn] / 2; // 分半 
        // 最后销毁这个军队在链表中的位置 
        nx[ls[resn]] = nx[resn] , ls[nx[resn]] = ls[resn]; 
        if(lsp == resn)
            lsp = nx[resn];
        if(nxp == resn)
            nxp = ls[resn]; // 特殊处理
        m[f[resn]]--; // 不要忘了该国损失了一个军队,m 要减一 
    }
    if(m[0] == 0)
        cout << "1 " << cnt << "\n"; // 殿姥国被完全消灭,嫂稽国胜 
    else
        cout << "0 " << cnt << "\n"; // 嫂稽国被完全消灭,殿姥国胜 
    return 0;
}

#剑锋OI#Ⅱ期#任务单#线段树(一)#最近更新20171102

2017-10-29 08:23:48 By root

题目名称 Legacy

题目地址:http://codeforces.com/contest/786/problem/B

三种操作: 1 a b c,在建立权值为c的a->b的单向边 2 a b c d,建立a->[b,c]权值为d的单向边 3 a b c d,建立[b,c]->a权值为d的单向边。 给你一个起点,问你起点到其他点的最短路长度。

题目名称 Preparing for the Contest

题目地址:http://codeforces.com/contest/377/problem/B

有一个学校,有m个bug,有n个大学生,每个大学生的能力值是b[i],bug的能力值是a[i],如果b[i]>=a[j],那么第i个人能够修复j bug现在每个大学生你需要支付c[i]元,支付给他之后,他可以每天修复一个能力值小于等于他能力值的bug你需要尽量少的天数,以及在花费小于s的情况下,修复这些bug问你怎么去做?

题目名称 Day at the Beach

题目地址:http://codeforces.com/contest/599/problem/C

给你n个数,问你最多分成多少块,使得在块内单独排序之后,然后再组合起来的结果和最后排序的结果一样

题目名称 Babaei and Birthday Cake

题目地址:http://www.codeforces.com/contest/629/problem/D

有n个蛋糕,然后第i个蛋糕只能放在地上或者放在体积和编号都比他小的上面 然后问你体积最多能堆多大?

题目名称 敌兵布阵

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1166

题目名称 Just a Hook

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1698

题意:一段线段由n条小线段组成,每次操作把一个区间的小线段变成金银铜之一(金的价值为3,银为2,铜为1),最初可当做全为铜;最后求这条线段的总价值。

数位dp总结之从入门到模板

2017-10-17 14:46:08 By root

数位dp总结 之 从入门到模板 转载自:http://blog.csdn.net/wust_zzwh/article/details/52100392

基础篇 数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位......数的每一位就是数位啦! 之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式,使得新的枚举方式满足dp的性质,然后记忆化就可以了。 两种不同的枚举:对于一个求区间[le,ri]满足条件数的个数,最简单的暴力如下:

for(int i=le;i<=ri;i++)
        if(right(i)) ans++;

然而这样枚举不方便记忆化,或者说根本无状态可言。 新的枚举:控制上界枚举,从最高位开始往下枚举,例如:ri=213,那么我们从百位开始枚举:百位可能的情况有0,1,2(觉得这里枚举0有问题的继续看) 然后每一位枚举都不能让枚举的这个数超过上界213(下界就是0或者1,这个次要),当百位枚举了1,那么十位枚举就是从0到9,因为百位1已经比上界2小了,后面数位枚举什么都不可能超过上界。所以问题就在于:当高位枚举刚好达到上界是,那么紧接着的一位枚举就有上界限制了。具体的这里如果百位枚举了2,那么十位的枚举情况就是0到1,如果前两位枚举了21,最后一位之是0到3(这一点正好对于代码模板里的一个变量limit 专门用来判断枚举范围)。最后一个问题:最高位枚举0:百位枚举0,相当于此时我枚举的这个数最多是两位数,如果十位继续枚举0,那么我枚举的就是以为数咯,因为我们要枚举的是小于等于ri的所以数,当然不能少了位数比ri小的咯!(这样枚举是为了无遗漏的枚举,不过可能会带来一个问题,就是前导零的问题,模板里用lead变量表示,不过这个不是每个题目都是会有影响的,可能前导零不会影响我们计数,具体要看题目) 由于这种新的枚举只控制了上界所以我们的Main函数总是这样:

int main()
{
    long long le,ri;
    while(~scanf("%lld%lld",&le,&ri))
        printf("%lld\n",solve(ri)-solve(le-1));
}

w_w 是吧!统计[1,ri]数量和[1,le-1],然后相减就是区间[le,ri]的数量了,这里我写的下界是1,其实0也行,反正相减后就没了,注意题目中le的范围都是大于等于1的(不然le=0,再减一就G_G了) 在讲例题之前先讲个基本的动态模板(先看后面的例题也行):dp思想,枚举到当前位置pos,状态为state(这个就是根据题目来的,可能很多,毕竟dp千变万化)的数量(既然是计数,dp值显然是保存满足条件数的个数)

typedef long long ll;
int a[20];
ll dp[20][state];//不同题目状态不同
ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零
{
    //递归边界,既然是按位枚举,最低位是0,那么pos==-1说明这个数我枚举完了
    if(pos==-1) return 1;/*这里一般返回1,表示你枚举的这个数是合法的,那么这里就需要你在枚举时必须每一位都要满足题目条件,也就是说当前枚举到pos位,一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
    //第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
    if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
    /*常规写法都是在没有限制的条件记忆化,这里与下面记录状态是对应,具体为什么是有条件的记忆化后面会讲*/
    int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了
    ll ans=0;
    //开始计数
    for(int i=0;i<=up;i++)//枚举,然后把不同情况的个数加到ans就可以了
    {
        if() ...
        else if()...
        ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的
        /*这里还算比较灵活,不过做几个题就觉得这里也是套路了
        大概就是说,我当前数位枚举的数是i,然后根据题目的约束条件分类讨论
        去计算不同情况下的个数,还有要根据state变量来保证i的合法性,比如题目
        要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类,
        前一位如果是6那么这意味就不能是2,这里一定要保存枚举的这个数是合法*/
    }
    //计算完,记录状态
    if(!limit && !lead) dp[pos][state]=ans;
    /*这里对应上面的记忆化,在一定条件下时记录,保证一致性,当然如果约束条件不需要考虑lead,这里就是lead就完全不用考虑了*/
    return ans;
}
ll solve(ll x)
{
    int pos=0;
    while(x)//把数位都分解出来
    {
        a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来,反正注意数位边界就行
        x/=10;
    }
    return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的,显然比最高位还要高的一位视为0嘛
}
int main()
{
    ll le,ri;
    while(~scanf("%lld%lld",&le,&ri))
    {
        //初始化dp数组为-1,这里还有更加优美的优化,后面讲
        printf("%lld\n",solve(ri)-solve(le-1));
    }
}

相信读者还对这个有不少疑问,笔者认为有必要讲一下记忆化为什么是if(!limit)才行,大致就是说有无limit会出现状态冲突,举例: 约束:数位上不能出现连续的两个1(11、112、211都是不合法的) 假设就是[1,210]这个区间的个数 状态:dp[pos][pre]:当前枚举到pos位,前面一位枚举的是pre(更加前面的位已经合法了),的个数(我的pos从0开始) 先看错误的方法计数,就是不判limit就是直接记忆化 那么假设我们第一次枚举了百位是0,显然后面的枚举limit=false,也就是数位上0到9的枚举,然后当我十位枚举了1,此时考虑dp[0][1],就是枚举到个位,前一位是1的个数,显然dp[0][1]=9;(个位只有是1的时候是不满足的),这个状态记录下来,继续dfs,一直到百位枚举了2,十位枚举了1,显然此时递归到了pos=0,pre=1的层,而dp[0][1]的状态已经有了即dp[pos][pre]!=-1;此时程序直接return dp[0][1]了,然而显然是错的,因为此时是有limit的个位只能枚举0,根本没有9个数,这就是状态冲突了。有lead的时候可能出现冲突,这只是两个最基本的不同的题目可能还要加限制,反正宗旨都是让dp状态唯一 对于这个错误说两点:一是limit为true的数并不多,一个个枚举不会很浪费时间,所以我们记录下! limit的状态解决了不少子问题重叠。第二,有人可能想到把dp状态改一下dp[pos][state][limit]就是分别记录不同limit下的个数,这种方法一般是对的,关于这个具体会讲,下面有题bzoj3209会用到这个。 数位的部分就是这些,然后就是难点,dp部分,dp大牛的艺术,弱鸡只能看看+...+ 既然从高位往低位枚举,那么状态一般都是与前面已经枚举的数位有关并且通常是根据约束条件当前枚举的这一位能使得状态完整(比如一个状态涉及到连续k位,那么就保存前k-1的状态,当前枚举的第k个是个恰好凑成成一个完整的状态,不过像那种状态是数位的和就直接保存前缀和为状态了),不过必然有一位最简单的一个状态dp[pos]当前枚举到了pos位。dp部分就要开始讲例题了,不过会介绍几种常用防tle的优化。 实战篇 例一:HDU 2089 不要62 入门题。就是数位上不能有4也不能有连续的62,没有4的话在枚举的时候判断一下,不枚举4就可以保证状态合法了,所以这个约束没有记忆化的必要,而对于62的话,涉及到两位,当前一位是6或者不是6这两种不同情况我计数是不相同的,所以要用状态来记录不同的方案数。 dp[pos][sta]表示当前第pos位,前一位是否是6的状态,这里sta只需要去0和1两种状态就可以了,不是6的情况可视为同种,不会影响计数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
int a[20];
int dp[20][2];
int dfs(int pos,int pre,int sta,bool limit)
{
    if(pos==-1) return 1;
    if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];
    int up=limit ? a[pos] : 9;
    int tmp=0;
    for(int i=0;i<=up;i++)
    {
        if(pre==6 && i==2)continue;
        if(i==4) continue;//都是保证枚举合法性
        tmp+=dfs(pos-1,i,i==6,limit && i==a[pos]);
    }
    if(!limit) dp[pos][sta]=tmp;
    return tmp;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,-1,0,true);
}
int main()
{
    int le,ri;
    //memset(dp,-1,sizeof dp);可优化
    while(~scanf("%d%d",&le,&ri) && le+ri)
    {
        memset(dp,-1,sizeof dp);
        printf("%d\n",solve(ri)-solve(le-1));
    }
    return 0;
}

入门就不多讲了,开始讲常用优化吧! 第一:memset(dp,-1,sizeof dp);放在多组数据外面。 这一点是一个数位特点,使用的条件是:约束条件是每个数自身的属性,而与输入无关。 具体的:上一题不要62和4,这个约束对每一个数都是确定的,就是说任意一个数满不满足这个约束都是确定,比如444这个数,它不满足约束条件,不管你输入的区间是多少你都无法改变这个数不满足约束这个事实,这就是数自身的属性(我们每组数据只是在区间计数而已,只能说你输入的区间不包含444的话,我们就不把它统计在内,而无法改变任何事实)。 由此,我们保存的状态就可以一直用(注意还有要limit,不同区间是会影响数位在有限制条件下的上限的) 这点优化就不给具体题目了,这个还有进一步的扩展。不过说几个我遇到的简单的约束: 1.求数位和是10的倍数的个数,这里简化为数位sum%10这个状态,即dp[pos][sum]这里10 是与多组无关的,所以可以memset优化,不过注意如果题目的模是输入的话那就不能这样了。 2.求二进制1的数量与0的数量相等的个数,这个也是数自身的属性。 3.。。。。。 还是做题积累吧。搞懂思想! 下面介绍的方法就是要行memset优化,把不满足前提的通过修改,然后优化。 介绍之前,先说一种较为笨拙的修改,那就是增加状态,前面讲limit的地方说增加一维dp[pos][state][limit],能把不同情况下状态分别记录(不过这个不能memset放外面)。基于这个思想,我们考虑:约束为数位是p的倍数的个数,其中p数输入的,这和上面sum%10类似,但是dp[pos][sum]显然已经不行了,每次p可能都不一样,为了强行把memset提到外面加状态dp[pos][sum][p],对于每个不同p分别保存对应的状态。这里前提就比较简单了,你dp数组必须合法,p太大就G_G了。所以对于与输入有关的约束都可以强行增加状态(这并不代表能ac,如果题目数据少的话就随便你乱搞了) 第二:相减。 例题:HDU 4734 题目给了个f(x)的定义:F(x) = An 2n-1 + An-1 2n-2 + ... + A2 2 + A1 1,Ai是十进制数位,然后给出a,b求区间[0,b]内满足f(i)<=f(a)的i的个数。 常规想:这个f(x)计算就和数位计算是一样的,就是加了权值,所以dp[pos][sum],这状态是基本的。a是题目给定的,f(a)是变化的不过f(a)最大好像是4600的样子。如果要memset优化就要加一维存f(a)的不同取值,那就是dp[10][4600][4600],这显然不合法。 这个时候就要用减法了,dp[pos][sum],sum不是存当前枚举的数的前缀和(加权的),而是枚举到当前pos位,后面还需要凑sum的权值和的个数, 也就是说初始的是时候sum是f(a),枚举一位就减去这一位在计算f(i)的权值,那么最后枚举完所有位 sum>=0时就是满足的,后面的位数凑足sum位就可以了。 仔细想想这个状态是与f(a)无关的(新手似乎很难理解),一个状态只有在sum>=0时才满足,如果我们按常规的思想求f(i)的话,那么最后sum>=f(a)才是满足的条件。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>

using namespace std;
const int N=1e4+5;
int dp[12][N];
int f(int x)
{
    if(x==0) return 0;
    int ans=f(x/10);
    return ans*2+(x%10);
}
int all;
int a[12];
int dfs(int pos,int sum,bool limit)
{
    if(pos==-1) {return sum<=all;}
    if(sum>all) return 0;
    if(!limit && dp[pos][all-sum]!=-1) return dp[pos][all-sum];
    int up=limit ? a[pos] : 9;
    int ans=0;
    for(int i=0;i<=up;i++)
    {
        ans+=dfs(pos-1,sum+i*(1<<pos),limit && i==a[pos]);
    }
    if(!limit) dp[pos][all-sum]=ans;
    return ans;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,true);
}
int main()
{
    int a,ri;
    int T_T;
    int kase=1;
    scanf("%d",&T_T);
    memset(dp,-1,sizeof dp);
    while(T_T--)
    {
        scanf("%d%d",&a,&ri);
        all=f(a);
        printf("Case #%d: %d\n",kase++,solve(ri));
    }
    return 0;
}

```cpp


####减法的艺术!!!

例题 POJ 3252
这题的约束就是一个数的二进制中0的数量要不能少于1的数量,通过上一题,这题状态就很简单了,dp[pos][num],到当前数位pos,0的数量减去1的数量为num的方案数,一个简单的问题,中间某个pos位上num可能为负数(这不一定是非法的,因为我还没枚举完嘛,只要最终的num>=0才能判合法,中途某个pos就不一定了),这里比较好处理,Hash嘛,最小就-32吧(好像),直接加上32,把32当0用。这题主要是要想讲一下lead的用法,显然我要统计0的数量,前导零是有影响的。至于!lead&&!limit才能dp,都是类似的,自己慢慢体会吧。

```cpp
#pragma comment(linker, "/STACK:10240000,10240000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
const double R=0.5772156649015328606065120900;
const int N=1e5+5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
int dp[35][66];
int a[66];
int dfs(int pos,int sta,bool lead,bool limit)
{
    if(pos==-1)
        return sta>=32;
    if(!limit && !lead && dp[pos][sta]!=-1) return dp[pos][sta];
    int up=limit?a[pos]:1;
    int ans=0;
    for(int i=0;i<=up;i++)
    {
        if(lead && i==0) ans+=dfs(pos-1,sta,lead,limit && i==a[pos]);//有前导零就不统计在内
        else ans+=dfs(pos-1,sta+(i==0?1:-1),lead && i==0,limit && i==a[pos]);
    }
    if(!limit && !lead ) dp[pos][sta]=ans;
    return ans;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x&1;
        x>>=1;
    }
    return dfs(pos-1,32,true,true);
}
int main()
{
    memset(dp,-1,sizeof dp);
    int a,b;
    while(~scanf("%d%d",&a,&b))
    {
        printf("%d\n",solve(b)-solve(a-1));
    }
    return 0;
}

然后就是一些需要自己yy的题: HDU 3709 这题就是要枚举中轴,然后数位dp UVA 1305 这题我二分然后数位dp搞(好像不是正解,我水过的) Hbzoj 1799 这题讲一下: (偷偷告诉你,这个oj是单组测试,然后memset什么的都是浮云了) 约束:一个数是它自己数位和的倍数,直接dp根本找不到状态,枚举数位和,因为总就162,然后问题就变成了一个数%mod=0,mod是枚举的,想想状态:dp[pos][sum][val],当前pos位上数位和是sum,val就是在算这个数%mod,(从高位算 *10+i),因为我们枚举的数要保证数位和等于mod,还要保证这个数是mod的倍数,很自然就能找到这些状态,显然对于每一个mod,val不能保证状态唯一,这是你要是想加一维dp[pos][sum][val][mod],记录每一个mod的状态(这里sum可以用减法,然而val不行,就只能加一维),那你就想太多了,这样是会超时的(因为状态太多,记忆化效果不好)。这里直接对每一个mod,memset一次就能ac。下面的代码还把limit的当做了状态,因为每次都要初始化,所以能这样,memset在多组外面是不能这样的,不过奇葩的,这代码,如果不把limit当状态,还是在!limit 条件下记录dp,提交一发,时间竟然更短了,可能是每次memset的关系!!!

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>

using namespace std;

typedef long long ll;

ll dp[20][163][163][2];
int a[20];
ll dfs(int pos,int sum,int val,int mod,bool limit)
{
    if(sum-9*pos-9>0) return 0;//最坏的情况,这一位及后面的全部为9都不能达到0那就直接GG,这个剪枝不会影响ac
    if(pos==-1) return sum==0 && val==0;
    if(dp[pos][sum][val][limit]!=-1) return dp[pos][sum][val][limit];
    int up=limit?a[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++)
    {
        if(sum-i<0) break;
        ans+=dfs(pos-1,sum-i,(val*10+i)%mod,mod,limit && i==a[pos]);
    }
    dp[pos][sum][val][limit]=ans;
    return ans;
}
ll solve(ll x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    ll ans=0;
    for(int i=1;i<=pos*9;i++)//上限就是每一位都是9
    {
        memset(dp,-1,sizeof dp);
        ll tmp=dfs(pos-1,i,0,i,true);
        ans+=tmp;
    }
    return ans;
}
int main()
{
//    cout<<18*9<<endl;
    ll le,ri;
//    memset(dp,-1,sizeof dp);
    while(~scanf("%lld%lld",&le,&ri))
        printf("%lld\n",solve(ri)-solve(le-1));
    return 0;
}
/*
1 1000000000000000000
*/

基本讲的差不多了。前段时间学了点新东西!!

新的领域--计数转求和 HDU 4507 这题麻烦就是要求数的平方和。 我们先考虑求和的问题,一个区间,数位dp能在一些约束下计数,现在要这些数的和。其实组合数学搞搞就可以了:如 现在枚举的某一位pos,我统计了这一位枚举i的满足条件的个数cnt,其实只要算i对总和的贡献就可以了,对于一个数而言第pos位是i,那么对求和贡献就是i10^pos,就是十进制的权值,然后有cnt个数都满足第pos位是i,最后sum=cnti10^pos.原理就是这样平方和可以看做(a10^pos+b)^2,a是你当前pos位要枚举的,b其实是个子问题,就是pos之后的位的贡献值,把这个平方展开就可以了!

#pragma comment(linker, "/STACK:10240000,10240000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
const double R=0.5772156649015328606065120900;
const int N=1e5+5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
ll fact[20];
void init()
{
    fact[0]=1;
    for(int i=1;i<20;i++)
        fact[i]=fact[i-1]*10%mod;
}
struct node
{
    ll cnt,sum,sqr;
    node(ll cnt=-1,ll sum=0,ll sqr=0):cnt(cnt),sum(sum),sqr(sqr){}
}dp[20][7][7];
int a[20];
ll fac(ll x)
{
    return x*x%mod;
}
ll dfs(int pos,ll num,ll val,ll&cnt,ll&sum,bool limit)
{
    if(pos==-1) {
        if(num==0 || val==0)
            return 0;
        cnt=1;
        return 0;
    }
    if(!limit && dp[pos][num][val].cnt!=-1) {
            cnt=dp[pos][num][val].cnt;
            sum=dp[pos][num][val].sum;
            return dp[pos][num][val].sqr;
    }
    int up=limit?a[pos]:9;
    ll sq=0;
    for(int i=0;i<=up;i++)
    if(i!=7)
    {
        ll cn=0,su=0;
        ll tmp=dfs(pos-1,(num+i)%7,(val*10+i)%7,cn,su,limit && i==a[pos]);
        ll tm=i*fact[pos]%mod;
        tmp=(tmp+fac(tm)*cn%mod+(tm*su%mod)*2%mod)%mod;//计数之后要更新sum,sqr
        sum=(sum+su+(i*fact[pos]%mod)*cn%mod)%mod;
        cnt=(cnt+cn)%mod;
        sq=(sq+tmp)%mod;
    }
    if(!limit) dp[pos][num][val]=node(cnt,sum,sq);
    return sq;
}
ll solve(ll x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    ll t1=0,t2=0;
    return dfs(pos-1,0,0,t1,t2,true);
}
bool judge(ll x)
{
    int sum=0;
    int pos=0;
    if(x%7==0) return false;
    while(x)
    {
        if(x%10==7) return false;
        sum+=x%10;
        x/=10;
    }
    sum%=7;
    return sum!=0;
}
int main()
{
    init();
    for(int i=0;i<20;i++)
        for(int j=0;j<7;j++)
        for(int k=0;k<7;k++)//memset
    {
        dp[i][j][k].cnt=-1;
        dp[i][j][k].sum=0;
        dp[i][j][k].sqr=0;
    }
    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        ll le,ri;
        scanf("%I64d%I64d",&le,&ri);
        ll ans=solve(ri)-solve(le-1);
        ans=(ans%mod+mod)%mod;
        printf("%I64d\n",ans);
    }
    return 0;
}

题解:“剑锋OI”普及组多校联盟系列赛(04)

2017-09-17 18:40:52 By root

T1 - 数字的特权

本题算法: 模拟

考察能力: 代码基础

解题思路: 使用一层 for 循环枚举每一座城市的编号,再根据题目的条件判断该城市归哪位大臣管理。因此只需要 O(n) 的时间复杂度,总用时是绰绰有余的。

代码实现:

#include <cstdio>
int n , x , y , sx = 0 , sy = 0;
int main(){
    scanf("%d%d%d" , &n , &x , &y);
    for(int i = 1 ; i <= n ; i++)
        if(x % i == y % i)
            if(x > y)
                sx++;
            else
                sy++;
            // 如果余数相同,取特权值大的一方
        else
            if(x % i > y % i)
                sx++;
            else
                sy++;
            // 否则取余数大的一方
    printf("%d %d" , sx , sy); 
    return 0;
}

T2 – 砌砖墙

本题算法: 模拟

考查能力: 观察能力,推算能力,分析能力

解题思路: 经过研究砖块的排布规律,我们发现 第奇数层 的砖块有 m 个, 第偶数层 的砖块有 m – 1 个,我们可以视两层为一循环,即一次循环使用了 2m – 1 个砖块。 输入两个砖块编号,首先我们要看是否越界。我们设一共有 p 个砖块,不难推出 p 的通项式: p = n * m – n / 2 只有 1 ~ p 的编号是合法的,一次 if 判断输出再加上 continue 即可。 接下来,我们需要分类讨论。为了便于讨论,输入两个编号中,令较小的为 x,较大的为 y。 不难发现如果 y 在 x 右边,则有 y = x + 1;如果 y 在 x 左上角,则有 y = x + m – 1;如果 y 在 x 右上角,则有 y = x + m。接下来,我们以砖块 x 为研究对象,y 用来判断相对关系。 我们上面使两层砖块为一次循环,再次观察砖块排布,我们可以将任何砖块分成 6 类: 1.砖块位于 第奇数层,且位于该层最左边。 2.砖块位于 第奇数层,且位于该层最右边。 3.砖块位于 第奇数层,且不位于该层边缘。 4.砖块位于 第偶数层,且位于该层左侧或中间。 5.砖块位于 第偶数层,且位于该层最右边。 怎么判断砖块位于 第奇数层 还是 第偶数层 呢?上面提到一次循环有 2m – 1 个砖块,那必定和取模和判断脱不了干系,继续分析,我们设砖块 x 属于一次循环的第 t 个砖块,有: t = x % (2m - 1) 特别地,如果 t = 0,表示砖块 x 属于一次循环的 第偶数行 的末尾。如果需要一次表示,有: t = (x - 1) % (2m - 1) + 1 很显然根据性质“第奇数层 的砖块有 m 个砖块, 第偶数层 的砖块有 m – 1 个砖块”,如果 t 小于等于 m,则属于 第奇数层,否则属于 第偶数层。继续根据 t,根据若干的 if 得出砖块 x 是哪一类砖块。 例如,如果 t = 1,则是第 1 类砖块,观察排布,我们发现仅当砖块 y 在砖块 x 右上角或右边一个时,砖块 x 和 y 相邻。 同理,如果 t = m,则是第 2 类砖块,再次观察排布,我们发现仅当砖块 y 在砖块 x 左上角时,砖块 x 和 y 相邻。 对于如何求出 y 在 x 的右边一个还是左右上角,我们在之前已经介绍。接下来 3 类砖块也是使用类似的方法判断关系,在这里就不一一列出方法了。 值得注意的是数据范围,有些变量要开 long long,避免出现不必要的错误。 每组砖块编号我们只需要一些 if 判断再处理,因此时间复杂度是 O(m)

代码实现:

#include <cstdio>
bool flag;
int n , m , k;
long long x , y , p , f , t;
// 注意数据范围,有些变量不得不用 long long 存 
int main(){
    scanf("%d%d%d" , &n , &m , &k);
    p = (long long)n * m - n / 2; // 算出一共有多少砖(最大编号)
    for(int i = 1 ; i <= k ; i++){
        scanf("%lld%lld" , &x , &y);
        if(x > y)
            t = x , x = y , y = t; // 把较小的编号放入 x
        if(x <= 0 || y > p){
            printf("-1\n"); // 任意一个编号超出范围,直接结束本次循环 
            continue;
        }
        // 接下来分类讨论,代码可以长,但是思路要清晰 
        f = (x - 1) % (m + m - 1) + 1;
        // 因为砖块按 多-少-多-少 排列,所以我们以两个为一循环,先找出所在层是少还是多 
        flag = false;
        if(f <= m){
            // 属于砖块多的层,再出现新的分支,下面的条件请结合原题的图思考 
            if(f == 1)
                flag = (y == x + 1 || y == x + m);
            else if(f == m)
                flag = (y == x + m - 1);
            else
                flag = (y == x + 1 || y == x + m - 1 || y == x + m);
        }else{
            // 属于砖块少的层,同样有分支,其中最左边的砖块由于性质和中间的砖块一样,合并了 
            if(f == m + m - 1)
                flag = (y == x + m - 1 || y == x + m);
            else
                flag = (y == x + 1 || y == x + m - 1 || y == x + m);
        }
        printf("%d\n" , flag); // 最后输出问题的结果 
    }
    return 0;
}

T3 – 断肠崖

本题算法: 二分 + 递推

考查能力: 分析能力,优化能力

解题思路: 只要是做二分题做多的人,从“最大……的最小值”应该已经能判断出这题的正解是二分了。我们发现,最大跳跃距离决定着能否通关,很显然,如果最大跳跃距离越大,就越有机会通关。这其中有两个因素:首先关卡有限时,如果能跳的越远,到终点的时间也自然少了;其次悬崖的宽度也决定着关卡能否通过,如果最大跳跃距离选定为 4,而有一个宽度为 5 的悬崖,此时也只能望洋兴叹了。 因此我们只需要使用二分枚举最大跳跃距离。接下来就是看能否按要求通关且用时最小了。经过仔细分析,可以得出任何一个平台,都只能从之前的平台花 1 秒跳跃而来,很明显的递推或者说线性dp思想。我们初始化 f 数组为 inf,如果平台 x 能跳到平台 y,有以下转移方程: f[y] = min{f[y] , f[x] + 1} 至于如何判断平台 x 能跳到平台 y,之前已经用二分枚举出最大跳跃距离,判断两个平台之间的相对位置是否小于等于这个距离就行了。 最后,f[n] 即是最小的总用时。如果 f[n] 仍然是 inf(无法通关)或者 大于限时 m,则不能通关,尝试增大最大跳跃距离,否则说明可以通关,缩小最大跳跃距离。 综上所述,二分时间复杂度 O(log(a[n])),check函数时间复杂度 O(n ^ 2),因此总需时间复杂度为 O(log(a[n]) n ^ 2) 实际上,check 函数还能进行优化,用一个单调队列维护能跳到接下来平台的最小的一个 f[i],即可以直接转移。总复杂度可以将为 O(log(a[n]) n),这是一个很大的优化。但是由于本算法超纲,没有列入标程。

代码实现:

#include <cstdio>
#include <cstring>
int n , m , a[801] , v[801];
int l , r , mid , res , ansx , ansy;
int Solve(int d){
    // 测试选定最大跳跃距离为 d 能否通关且通关所需最少时间 
    memset(v , 0x7f , sizeof(v)); // 清空 dp 数组为 inf
    v[1] = 0; // 初始化起点边界 
    for(int i = 2 ; i <= n ; i++)
        for(int j = i - 1 ; j >= 1 ; j--)
            if(a[i] - a[j] <= d){
                // 先看平台 j 能否跳到平台 i,再进行状态转移 
                if(v[i] > v[j] + 1)
                    v[i] = v[j] + 1;
            }else
                break;
    return v[n];
}
int main(){
    scanf("%d%d" , &n , &m);
    for(int i = 1 ; i <= n ; i++)
        scanf("%d" , &a[i]);
    l = 1 , r = ansx = a[n] - a[1]; // 最大能直接从起点跳到终点
    while(l <= r){
        mid = (l + r) / 2; // 二分枚举最大跳跃距离
        res = Solve(mid);
        if(res > m)
            l = mid + 1; // 无法通关,向上二分
        else
            r = mid - 1 , ansx = mid , ansy = res; // 可以通关,向下二分 
    }
    printf("%d\n%d" , ansx , ansy);
    return 0;
}

T4 木块迷盒

这道题有一个很显然的性质,每一次倾斜之后,木块都是紧靠着一边一块一块叠起来的,也就是说都是连续的一行(或一列)。由于木块都是一样的,所以只要知道木块每行有几个,每列有几个,最后一次操作是哪个方向,就可以输出答案。 令h[i]表示第i行木块的个数,z[i]表示第i列木块的个数。当执行1和2操作的时候,需要修改的就是h[i]数组。下面以1操作为例: 首先清空h数组,然后对于每个z[i](除了z[n]以外,因为有一个固定块),对应的h[z[i]]++,因为当前列只能到第z[i]行,对于z[n],h[z[n]+1]++,即算上固定块的高度。到现在我们记录的h数组表示到h行结束的列的个数,显然h[i]应该是h[i]+h[i+1]+…+h[n],也就是当前结束的列和还没结束的列的个数和,所以一遍后缀和即可。要注意的是,计算的时候h[1]把固定块也算进去了,所以要-1 。 其他操作也类似。单次操作为O(n)。 输出的时候,用对应的数组,靠某一边,都由最后一次操作决定,判断一下是否在木块范围内就行了。

共 26 篇博客