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

质数

前缀和, 线性筛

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。