NOIP模拟 7.04

魔术球问题弱化版（ball.c/.cpp/.pas）

【题目描述】

假设有 n 根柱子，现要按下述规则在这 n 根柱子中依次放入编号为 1，2，3，…的球。

（1）每次只能在某根柱子的最上面放球。

（2）在同一根柱子中，任何 2 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 n 根柱子上最多能放多少个球。例如，在 4 根柱子上最多可放 11 个球。

对于给定的 n，计算在 n 根柱子上最多能放多少个球。

【输入描述】

第 1 行有 1 个正整数 n，表示柱子数。

【输出描述】

一行表示可以放的最大球数

样例输出。

样例输入

题目限制（为什么说弱化版就在这里）

N<=60，时限为3s

【题解】

暴力。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <cstdlib>

 #include <algorithm>

 #include <queue>

 #include <cmath> 

 const int INF = 0x3f3f3f3f;

 const int MAXN =  + ;

 inline void read(long long &x)

 {

     x = ;char ch = getchar();char c = ch;

     while(ch > '' || ch < '')c = ch, ch = getchar();

     while(ch <= '' && ch >= '')x = x *  + ch - '', ch = getchar();

     if(c == '-')x = -x;

 }

 long long ans,num[MAXN],n;

 void dfs(int step)

 {

     for(int i = ;i <= n;++ i)

     {

         if(!num[i])

         {

             num[i] = step;

             ans = step;

             dfs(step + );

             return;

         }

         int k = sqrt(num[i] + step);

         if(k * k == num[i] + step)

         {

             ans = step;

             num[i] = step;

             dfs(step + );

             break;

         }

     }

     return;

 }

 int main()

 {

     read(n);

     dfs();

     printf("%lld", ans);

     return ;

 }

2.征兵（conscription.c/.cpp/.pas）
一个国王，他拥有一个国家。最近他因为国库里钱太多了，闲着蛋疼要征集一只部队要保卫国家。他选定了N个女兵和M个男兵，但事实上每征集一个兵他就要花10000RMB，即使国库里钱再多也伤不起啊。他发现，某男兵和某女兵之间有某种关系（往正常方面想，一共R种关系），这种关系可以使KING少花一些钱就可以征集到兵，不过国王也知道，在征兵的时候，每一个兵只能使用一种关系来少花钱。这时国王向你求助，问他最少要花多少的钱。

读入（conscription.in）
第一行：T，一共T组数据。
接下来T组数据，
第一行包括N,M,R
接下来的R行包括Xi,Yi,Vi 表示如果招了第Xi个女兵，再招第Yi个男兵能省Vi元（同样表示如果招了第Yi个男兵，再招第Xi个女兵能也省Vi元）
输出（conscription.out）
共T行，表示每组数据的最终花费是多少（因为国库里的钱只有2^31-1，所以保证最终花费在maxlongint范围内）
样例输入
2

5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781

5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889
2 4 3133
样例输出
71071
54223
数据范围
数据保证
T<=5 ,m,n<=10000,r<=50000,Xi<=m,Yi<=n,Vi<=10000,结果<=2^31-1

【题解】

最大生成树。开始读错题了，以为是KM。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <cstdlib>

 #include <algorithm>

 #include <queue>

 const int INF = 0x3f3f3f3f;

 const int MAXN =  + ;

 const int MAXM =  + ;

 inline void read(int &x)

 {

     x = ;char ch = getchar();char c = ch;

     while(ch > '' || ch < '')c = ch, ch = getchar();

     while(ch <= '' && ch >= '')x = x *  + ch - '', ch = getchar();

     if(c == '-')x = -x;

 }

 int u[MAXM],v[MAXM],w[MAXM],cnt[MAXM];

 int t,n,m,r;

 int fa[MAXN];

 long long ans;

 bool cmp(int a, int b)

 {

     return w[a] >= w[b];

 }

 int find(int x)

 {

     return x == fa[x] ? x : fa[x] = find(fa[x]);

 }

 int main()

 {

     read(t);

     for(;t;--t)

     {

         ans = ;

         read(n);read(m);read(r);

         int tmp = (n + m) << ;

         for(register int i = ;i <= tmp;++ i)

             fa[i] = i;

         for(register int i = ;i <= r;++ i)

             cnt[i] = i;

         for(register int i = ; i <= r;++ i)

         {

             read(u[i]);read(v[i]);read(w[i]);

             u[i] = u[i] << ;

             v[i] = v[i] <<  | ;

         }

         std::sort(cnt + , cnt +  + r, cmp);

         for(register int i = ;i <= r;++ i)

         {

             int x = find(u[cnt[i]]);

             int y = find(v[cnt[i]]);

             if(x != y)

             {

                 ans += w[cnt[i]];

                 fa[x] = y;

             }

         }

         printf("%lld\n", (long long)(n + m) *  - ans) ;

     }

     return ;

 }

3.坑爹的GPS（gpsduel.c/.cpp/.pas）

有一天，FJ买了一辆车，但是，他一手下载了两个GPS系统。好了现在麻烦的事情来了，GPS有一个功能大概大家也知道，如果FJ没有按照GPS内置地图的最短路走，GPS就会报错来骚扰你。现在FJ准备从他的农舍（在1这个点）开车到他的谷屋（n这个点）。FJ给了你两个GPS系统内置地图的信息，他想知道，他最少会听到多少次报错（如果FJ走的路同时不满足两个GPS，报错次数+2）

读入：第一行：n,k；n表示有FJ的谷屋在哪，同时保证GPS内置地图里的点没有超过n的点。K表示GPS内置地图里的路有多少条，如果两个点没有连接则表明这不是一条通路。

接下来k行，每行4个数X,Y,A,B分别表示从X到Y在第一个GPS地图里的距离是A，在第二个GPS地图里的是B。注意由于地形的其他因素GPS给出的边是有向边。

输出：一个值，表示FJ最少听到的报错次数。

样例输入：

5 7

3 4 7 1

1 3 2 20

1 4 17 18

4 5 25 3

1 2 10 1

3 5 4 14

2 4 6 5

样例输出：

解释

FJ选择的路线是1 2 4 5，但是GPS 1认为的最短路是1到3，所以报错一次，对于剩下的2 4 5，两个GPS都不会报错。

数据范围

N<=10000，至于路有多少条自己算吧。数据保证所有的距离都在2^31-1以内。

来源

USACO 2014年全美公开赛银组第二题（各位轻虐银组题）

【题解】

三次最短路。

先建反图，求出每个点到终点的最短路。然后求走每条边会引起的错误值的变化，再求最短路即可。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <cstdlib>

 #include <algorithm>

 #include <queue>

 const int INF = 0x3f3f3f3f;

 const int MAXN =  + ;

 const int MAXQ =  + ;

 const int MAXM =  + ;

 inline void read(int &x)

 {

     x = ;char ch = getchar();char c = ch;

     while(ch > '' || ch < '')c = ch, ch = getchar();

     while(ch <= '' && ch >= '')x = x *  + ch - '', ch = getchar();

     if(c == '-')x = -x;

 }

 struct Edge

 {

     int u,v,next,w;

 }edge1[MAXM],edge2[MAXM],edge3[MAXM];

 int head1[MAXN],head2[MAXN],head3[MAXN],cnt1,cnt2,cnt3;

 int b1[MAXN],b2[MAXN],b3[MAXN];

 long long d1[MAXN],d2[MAXN],d3[MAXN];

 int n,m;

 void insert1(int a, int b, int c){edge1[++cnt1] = Edge{a, b, head1[a], c};head1[a] = cnt1;}

 void insert2(int a, int b, int c){edge2[++cnt2] = Edge{a, b, head2[a], c};head2[a] = cnt2;}

 void insert3(int a, int b, int c){edge3[++cnt3] = Edge{a, b, head3[a], c};head3[a] = cnt3;}

 std::queue<int> q;

 void SPFA1()

 {

     memset(d1, 0x3f, sizeof(d1));

     q.push(n);

     b1[n] = ;

     d1[n] = ;

     register int pos;

     while(!q.empty())

     {

         int u = q.front();

         q.pop();

         b1[u] = ;

         for(pos = head1[u];pos;pos = edge1[pos].next)

         {

             int v = edge1[pos].v;

             if(d1[v] > d1[u] + edge1[pos].w)

             {

                 d1[v] = d1[u] + edge1[pos].w;

                 if(!b1[v])

                 {

                     q.push(v);

                     b1[v] = ;

                 }

             }

         }

     }

 }

 void SPFA2()

 {

     memset(d2, 0x3f, sizeof(d2));

     q.push(n);

     b2[n] = ;

     d2[n] = ;

     register int pos;

     while(!q.empty())

     {

         int u = q.front();

         q.pop();

         b2[u] = ;

         for(pos = head2[u];pos;pos = edge2[pos].next)

         {

             int v = edge2[pos].v;

             if(d2[v] > d2[u] + edge2[pos].w)

             {

                 d2[v] = d2[u] + edge2[pos].w;

                 if(!b2[v])

                 {

                     q.push(v);

                     b2[v] = ;

                 }

             }

         }

     }

 }

 void SPFA3()

 {

     memset(d3, 0x3f, sizeof(d3));

     q.push();

     b3[] = ;

     d3[] = ;

     register int pos;

     while(!q.empty())

     {

         int u = q.front();

         q.pop();

         b3[u] = ;

         for(pos = head3[u];pos;pos = edge3[pos].next)

         {

             int v = edge3[pos].v;

             if(d3[v] > d3[u] + edge3[pos].w)

             {

                 d3[v] = d3[u] + edge3[pos].w;

                 if(!b3[v])

                 {

                     q.push(v);

                     b3[v] = ;

                 }

             }

         }

     }

 }

 int main()

 {

     read(n);read(m);

     register int tmp1, tmp2, tmp3, tmp4,i;

     for(i = ;i <= m; ++ i)

     {

         read(tmp1);read(tmp2);read(tmp3);read(tmp4);

         insert1(tmp2, tmp1, tmp3);

         insert2(tmp2, tmp1, tmp4);

         insert3(tmp1, tmp2, );

     }

     SPFA1();

     SPFA2();

     for(int i = ;i <= cnt3;++ i)

     {

         tmp1 = edge3[i].v;tmp2 = edge3[i].u;

         if(d1[tmp1] + edge1[i].w > d1[tmp2]) ++edge3[i].w;

         if(d2[tmp1] + edge2[i].w > d2[tmp2]) ++edge3[i].w;

     }

     SPFA3();

     printf("%lld", d3[n]);

     return ;

 }

巴特西

NOIP模拟 7.04

最新文章

热门文章