首页 > 代码库 > topcoder 642

topcoder 642

2024-08-08 13:25:04   218人阅读

A:直接拆开字符串写就好了。

今天的题目比较容易一些：

B：题目大意：

 求最少的翻转次数，每次翻转i是对应 y%i==0都会翻转。

球所有翻转为off状态的最小次数；

从最小idx开始，依次做就好了，因为它的状态是以后做不到的。

C：题目大意：

给出一个带权重的无向图。

求最大的height使0-n-1中权重小于Height的话花费(边值-height)^2;

先二分height;然后求出0->n-1中cost 最小的数是否大于给定的值。

 

求得时候可以用spfa ，当然有dp写法

#include<queue>#include <string>#include <vector>#include<iostream>#include<string.h>#include<algorithm>using namespace std;#define inf 203456789typedef long long ll;struct node{    int v,w;};vector<node> mp[55];ll dp[55];int boo[55];int n;long long b;class TallShoes {    public:    void bfs(int limit)    {          queue<int> q;          memset(boo,0,sizeof(boo));          for (int i=0;i<n;i++)          dp[i]=(ll) inf*inf;          dp[0]=0;          q.push(0);          while (!q.empty())          {            int u=q.front();            q.pop();            boo[u]=0;            for (int i=0;i<mp[u].size();i++)            {                int v=mp[u][i].v;                ll  k=0;                if (mp[u][i].w<limit) k=(ll) (limit-mp[u][i].w)*(limit-mp[u][i].w);                if (dp[v]>dp[u]+k)                {                    dp[v]=dp[u]+k;                    if (!boo[v])                    {                    boo[v]=1;                    q.push(v);                    }                }            }        }    }    int pan(int  x)    {       bfs(x);       if (dp[n-1]<=b) return 1;       return 0;    }    int maxHeight(int N, vector <int> X, vector <int> Y, vector <int> height, long long B) {    n=N;    b=B;    for (int i=0;i<X.size();i++){         node edge;         edge.v=Y[i];         edge.w=height[i];         mp[X[i]].push_back(edge);         edge.v=X[i];         mp[Y[i]].push_back(edge);    }    int  l=0,r=200000000;    int  ans=-1;    for (int _=1;_<=60;_++)    {        int mid=(l+r)/2;        if (pan(mid)) {                     l=mid;                     ans=l;        }        else r=mid;    }    return ans;    }};
View Code

这里初始值的设置要注意

 

div 1 A:

以为是求期望 ，比想象的简单点：

我们是求>=s的期望值，

先DP出求概率多少，再ans+=(I-S)*dp[i] I>=S;

#include<queue>#include <string>#include <vector>#include<iostream>#include<string.h>#include<algorithm>#include<cstdio>using namespace std;#define N 111111typedef long long ll;double dp[N*10];class WaitingForBus {    public:    double whenWillBusArrive(vector <int> time, vector <int> prob, int s) {    dp[0]=1;    for (int i=0;i<s;i++)    {            for (int j=0;j<time.size();j++)            dp[i+time[j]]+=dp[i]*prob[j]/100;       }       double ans=0;       for (int i=s;i<2*N;i++) //cout<<dp[i]<<" ";       ans+=dp[i]*(i-s);       return ans;    }};

 

topcoder 642


联系
我们