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;
}
root Avatar