资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

SRM471-创新互联

250pt:SRM471

 题意：定义一种函数f(x),表示ｘ不断/2直到出现非素数的操作次数。现在给定N，D。求X<= N, 并且f(x) >= D的大的数

我们提供的服务有：网站设计、成都做网站、微信公众号开发、网站优化、网站认证、新罗ssl等。为上1000+企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的新罗网站制作公司

 思路：直接先弄一个1000w以内的质数表，然后直接dp。由于题目给定内存才64M。。所以没法开1000w的int数组

    所以dp时我直接对每个素数做。dp[i]表示以第i个质数结尾的f值。。

code：

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define PB push_back
#define MP make_pair

#define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)

typedef vector VI;
typedef vector VS;
typedef vector VD;
typedeflong long LL;
typedef pair PII;
bool vis[10000010];
vector P;
int dp[1000000];
class PrimeSequences
{
public:
void getPrime(int n){
              P.clear();
for (int i = 2; i <= n; ++i){
if (vis[i]) continue;
                   P.push_back(i);
for (int j = i * 2;  j <= n; j += i)
                      vis[j]= true;
              }

        }
int getLargestGenerator(int N, int D)
        {
                 getPrime(N);
int n = P.size();
int p, x;
int ans = 0;
for (int i = 0; i < n; ++i){
                       x= (P[i] >> 1);
                       p= lower_bound(P.begin(), P.end(), x) - P.begin();
if (x == P[p]) dp[i] = dp[p] + 1;
else dp[i] = 1;
                       ans= max(dp[i], ans);
                 }
if (ans < D) return -1;
for (int i = n-1; i >= 0; --i)
if (dp[i] >= D) return P[i];
return -1;
        }

};

500pt：

题意：题目给了最多n(n <= 25)个点的有向图，编号0~n-1, 现在求一条0号点到n-1点的最短路，并且该最短路上任意两点距离不为13倍数。

思路：很明显的动态规划。

    后面改成3维dp[i][j][k]，表示到达点i，从起点到点i所有路径%13的集合为j，并且此时最短路%13为k时的最短路。

    那么转移就很明显了。。

    不过此题很容易想入非非了，刚开始就是用2维写错了。少枚举了第三维。直接用最短路%13作为第三维。。

    这样的结果就可能导致当前最优而后面不一定最优。。

code：

 1 #line 7 "ThirteenHard.cpp"
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 #include 
20 #include 
21 #include 
22 #include 
23 #include 
24 #include 
25 using namespace std;
26 
27 #define PB push_back
28 #define MP make_pair
29 #define Inf 0xfffffff
30 #define REP(i,n) for(i=0;i<(n);++i)
31 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
32 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
33 #define two(i) (1 << i)
34 typedef vector VI;
35 typedef vector VS;
36 typedef vector VD;
37 typedef long long LL;
38 typedef pair PII;
39 struct oo{
40   int x, y, z;
41        oo(){}
42        oo(int _x, int _y, int _z):x(_x), y(_y), z(_z){}
43 };
44 int dp[26][1 << 14][15];
45 bool vis[26][1 << 14][15];
46 class ThirteenHard
47 {
48 public:
49 int g[30][30], n;
50 int calcTime(vector  s)
51         {
52              n = s.size();
53   for (int i = 0; i < n; ++i)
54   for (int j = 0; j < n; ++j){
55  if (s[i][j] == '#') g[i][j] = Inf;
56  if (s[i][j] >= 'A' && s[i][j] <= 'Z') g[i][j] = s[i][j] - 'A' + 1;
57  if (s[i][j] >= 'a' && s[i][j] <= 'z') g[i][j] = s[i][j] - 'a' + 27;
58                 }
59              memset(dp, -1, sizeof(dp));
60              memset(vis, 0, sizeof(vis));
61              dp[0][1][0] = 0;
62              queue q;
63              q.push(oo(0,1,0));
64   int x, y, z;
65              vis[0][1][0] = true;
66              oo cur;
67   while (!q.empty()){
68                    cur = q.front();
69   for (int i = 0; i < n; ++i) if (g[cur.x][i] < Inf){
70                             z = (cur.z + g[cur.x][i]) % 13;
71   if (two(z) & cur.y) continue;
72                             y = (cur.y | two(z));
73                             x = i;
74   if (dp[x][y][z] == -1 || dp[x][y][z] > dp[cur.x][cur.y][cur.z] + g[cur.x][x]){
75                                   dp[x][y][z] = dp[cur.x][cur.y][cur.z] + g[cur.x][x];
76   if (!vis[x][y][x]){
77                                        vis[x][y][z] = true;
78                                        q.push(oo(x, y, z));
79                                   }
80                             }
81                    }
82                    q.pop();
83                    vis[cur.x][cur.y][cur.z] = false;
84              }
85   int ans = -1;
86   for (int i = 0; i < two(13); ++i)
87 for (int j = 0; j < 13; ++j)
88 if (dp[n-1][i][j] > -1)
89 if (ans == -1 || dp[n-1][i][j] < ans) ans = dp[n-1][i][j];
90   return ans;
91         }
92 
93 };
View Code


分享文章：SRM471-创新互联
浏览路径：http://cdkjz.cn/article/dicgeg.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
四川锦华橡塑发电机组维修保养达州做网站做网站设计什邡网站建设等级保护测评成都小程序开发德昌麦琪建站成都网站代运营视频运营

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图