Problem A: A. 谍报分析
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 3 Solved: 3
[Submit][Status][Web Board]
Description
“八一三”淞沪抗战爆发后，***几次准备去上海前线视察和指挥作战。但都因为宁沪之间的铁路和公路遭到了敌军的严密封锁，狂轰滥炸，一直未能成行。 ***特科组织，其主要任务是保卫***的安全，了解和掌握敌方的动向。经过一段时间的监听，谍报组获取了敌方若干份密报，经过分析，发现密文中频繁出现一些单词，情报人员试图从单词出现的次数中，推出敌军的行动计划。 请你编程，快速统计出频率高的前十个单词。
Input
密文是由英语单词（小写字母）组成，有若干段。单词之间由一个或多个空格分开，自然段之后可以用一个“，”或“。”表示结束。整个内容的单词数量不超过10000，不同的单词个数不超过500.
Output
输出占10行，每行一个单词及出现的次数，中间一个空格。要求按频率降序输出，出现次数相同的单词，按字典序输出。
Sample Input
shooting is at shanghai station. shooting must
be carried out. shooting shooting.
shanghai station must be surrounded, at least a team of one hundred soldiers to fight. twenty five soldiers shooting in the north, twenty five soldiers shooting in the south, twenty five soldiers shooting in the east, twenty five soldiers shooting in the west.
Sample Output
shooting 8
soldiers 5
five 4
in 4
the 4
twenty 4
at 2
be 2
must 2
shanghai 2
本来可以使用map来记录每个string出现的次数，但由于我们要先按照每个string出现的次数排序，再按照字典序排序，那么我们还是写个结构体，然后重载运算符吧，那么我们将会使用的是结构体数组，那么我们怎么实现map那种查询出这个string并增加这个string出现的次数呢？
那么可以用map来做映射啊，将map的作用改为找到这个string在数组中的位置。
#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
class A{
public:
string s;
int num;
};
bool operator < (const A &a,const A &b)
{
if(a.num==b.num)
{
return a.s<b.s;
}
return a.num>b.num;
}
A a[maxn];
map<string,int>mp;
int main()
{
string st;
int cnt=0;
while(cin>>st)
{
if(st[st.size()-1]=='.'||st[st.size()-1]==',')
{
st=st.substr(0,st.size()-1);
}
if(!mp[st])
{
a[++cnt].s=st;
mp[st]=cnt;
a[mp[st]].num++;
}
else
{
a[mp[st]].num++;
}
}
sort(a+1,a+cnt+1);
for(int i=1;i<=min(cnt,10);i++)
{
cout<<a[i].s<<' '<<a[i].num<<endl;
}
return 0;
} Problem B: B.情报传递
Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 6 Solved: 3
[Submit][Status][Web Board]
Description
抗日战争时期,在国共合作的大背景下，***不断发展壮大，其情报工作也开始由获取警报性、保卫性信息，向获取军政战略性情报转变。各系统情报组织遵循"荫蔽精干,长期埋伏,积蓄力量,以待时机"的隐蔽战线工作方针,开展了卓有成效的情报工作。 ***特科组是***情报工作的一个杰出范例,它以点为主、系统延伸、分散辐射的力量格局,异地领导、分头派遣、单线联系的组织形式。以打入、拉出、统战联络、内线为主的工作方式,形成了一个传递信息隐蔽、效用及时、形式多样的情报网络。 ***特科组的情报人员共有N人，其代号分别为0,1，……,N-1。 0号是最高领导人，特工之间有一套严格的单线联络程序，即，每个特工人员只有一个上线，他获得的情报需层层上传递到0号手里，由0号发报出去。 特工i在传递情报时，若通往到0号的通道尚未建立，则需要建立一级级单线通道;若他的上线已建立好通道，只需建立两人通道，信息发送给上线；依次类推。若特工i已建立好到0号的通道，则直接发出情报。日伪统治中心南京，既是情报来源丰富的地方，又是特工人员活动最危险的地方。因此，一旦某个特工处于不安全状态，他必须马上撤离，同时他的所有下线（处在通道上的一级级下线）也一同撤离。 已知***特科组的组织结构，你的任务是计算，当某特工i需要发送情报时，最少需要建立几个情报人员的通道；当某特工i处于不安全状态时，最少需要撤离多少人员。
Input
第一行一个整数： N （ 1≤N ≤5060 ） 接下来一行有N-1 个整数， A1 A2 ……An-1 ，其中Ai是编号i的上线。 下一行一个整数： M 表示有M个状态，（ 1≤M ≤5060 ） 接下来有M行 ：有两种形式： Send i 特工i处于要发送情报状态； Danger i 特工i处于不安全状态
Output
输出占M行 ，对于Send i，输出最少需要建立通道的情报人员数，若特工i处于通道线上，输出0；对于Danger i，输出最少需要撤离多少人员，若特工i不处于通道线上，则输出0.
Sample Input
10
0 1 2 1 3 0 0 3 2
10
Send 0
Send 3
Danger 2
Send 7
Send 5
Send 9
Danger 9
Send 4
Send 1
Send 9
Sample Output
1
3
2
1
3
1
1
1
0
1
这个就是告诉你一个树，然后一开始的时候没条路都是不可用的，我们要干的活就是维护这些路的关系。
#include<bits/stdc++.h>
using namespace std;
const int maxn=5070;
int n;
class A{
public:
//f用来储存这个节点的爹是谁
//t 用来记录这个点是否已经与他父亲建立了联系。
//ch 用来记录这个点都有那些儿子。
int f;
bool t;
vector<int> ch;
};
A aa[maxn];
int x;
int ans=0;
void fun1(int xx)
{
if(xx==-1) return ;
if(aa[xx].t==0)
{
ans++;
aa[xx].t=1;
fun1(aa[xx].f);
}
}
void fun2(int xx)
{
if(aa[xx].t==1)
{
aa[xx].t=0;
ans++;
}
for(int i=0;i<aa[xx].ch.size();i++)
{
if(aa[aa[xx].ch[i]].t)
fun2(aa[xx].ch[i]);
}
}
int main()
{
scanf("%d",&n);
aa[0].f=-1;
for(int i=1;i<n;i++)
{
scanf("%d",&aa[i].f);
aa[aa[i].f].ch.push_back(i);
aa[i].t=0;
}
int M;
scanf("%d",&M);
for(int i=0;i!=M;i++)
{
ans=0;
string s;
cin>>s>>x;
if(s=="Send")
{
fun1(x);
cout<<ans<<endl;
}
else
{
fun2(x);
cout<<ans<<endl;
}
}
return 0;
} Problem C: C.最小密钥
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 14 Solved: 7
[Submit][Status][Web Board]
Description
在中国近代史上，暂编***军绝对是一支能打硬仗，大名鼎鼎的行动部队。“一二八”上海抗战，暂编*军就曾打得小日本四易主帅。 *月号，暂编***军计划组成一个行动大队，派出N名队员潜伏在***地，发动一次大规模的巷战行动。每名队员有自己的代号Ai，为了更好的配合作战，他们需要获得一个密钥Key, 然后各自迅速移动到Ai MOD Key位置，时刻一起开战。 作战方案已经定好，你能帮*行动大队快速找个满足条件的最小密钥Key吗？ MOD表示取模运算，要求不能有多名队员待在同一个位置。
Input
第一行： T 表示以下有T组测试数据 （ 1≤T ≤5 ） 对每组数据， 第一行：N 表示行动人员数 (1<=N<=3000) 接下来一行有N个整数，分别表示每个队员的代号Ai (1<=Ai<=20000)
Output
对每组测试数据，输出占一行，一个整数 Key.
Sample Input
2
3
1 2 3
5
4 6 9 10 13
Sample Output
3
8
就是找一个符合条件的哈希key，然后没想起来什么好方法。就直接暴力枚举了。。。
#include<bits/stdc++.h>
using namespace std;
const int maxn=3010;
int T;
int n,a[maxn],vis[20010];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i!=n;i++)
{
scanf("%d",&a[i]);
}
int t=n-1;
while(t++)
{
memset(vis,0,sizeof(vis));
int i;
for(i=0;i!=n;i++)
{
int k=a[i]%t;
if(vis[k])
break;
vis[k]=1;
}
if(i==n)
{
cout<<t<<endl;
break;
}
}
}
return 0;
} Problem D: D.年终奖金
Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 1 Solved: 1
[Submit][Status][Web Board]
Description
***公司承接了N个项目需要年底完成，每个项目有一定的难度系数。由于项目太多了，需要招聘大量的技术人员。要求每个技术人员至少完成K个项目。 考虑到有些项目之间相似性以及项目的难易程度，为了避免某些员工只挑选轻松项目，CEO提出了一个奖励机制，当技术人员完成分配给他的任务后，年终可以得到一笔奖金，其得到的酬金将是C + (Tmax–Tmin)2。其中，Tmax表示所做项目的最大的难度系数，Tmin是难度系数的最小值。 你能否计算一下，为了完成所有项目，***公司年终至少需要支付多少酬金？
Input
输入有多组测试数据。对每组测试数据： 第一行： N K C (1<=N，K<=100 1<=C<=5000 ) 第二行 N个正整数分别描述N个项目的难度系数。(1<=难度系数<=10000)
Output
对每组测试数据：输出占一行，一个整数。即，***公司年终至少需要支付的酬金数。
Sample Input
2 1 1
2 4
10 2 3
1 4 10 3 10 1 8 3 8 3
Sample Output
2
13
HINT
提示：第一组测试数据，如果一个人完成，酬金为1 + (4–2)2 = 5；如果分给两个人去完成，收费为1 + 1 = 2。
看了一下估计是个DP？
你敢信？那是个平方。。。
很水的DP了一下，没有任何优化：
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=110;
int a[maxn];
int n,k,c;
int dp[maxn][maxn];
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d %d %d",&n,&k,&c))
{
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
dp[1][i]=c+(a[i]-a[1])*(a[i]-a[1]);
}
for (int i = 2; i <= n/k; i++)
{
for (int j = (i - 1) * k+1; j <= n; j++)
{
int maxp = j - (i - 1) * k;
for (int p = k; p <= maxp; p++)
{
dp[i][j] = min(dp[i][j], c + dp[i - 1][j - p] + (a[j] - a[j - p+1]) * (a[j] - a[j - p+1]));
}
}
}
int ans=inf;
for(int i=1;i<=n/k;i++)
{
ans=min(ans,dp[i][n]);
}
printf("%d\n",ans);
}
return 0;
} Problem E: G.GDP值
Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 0 Solved: 0
[Submit][Status][Web Board]
Description
***国有N个城市，这N个城市的编号从1,2，……,N 。1号城市为贸易中心。城市之间有M条高速公路，每条公路都有一个非负整数的GDP影响因子，每条公路的两端都是城市（可能两端是同一个城市），高速公路交通网保证任意两个城市都可以通过互达。 ***国正在筹划“八纵八横”的高铁建设计划，计划要修建一些高速铁路，每条高速铁路两端也都是城市（可能两端是同一个城市），每条高速铁路也都有一个非负整数的GDP影响因子。国家还计划在“八纵八横”计划建成之后，将“一带一路”扩展为“一带一路一环”，增加“内陆城市经济环”，即寻找一条从贸易中心出发沿着一系列高铁或高速公路走的路径，每条高铁或高速公路可以经过多次，每座城市也可以经过多次，最后路径又回到贸易中心结束。令“内陆城市经济环”的GDP值为依次将这条路径上所经过的高铁或高速公路的GDP影响因子经过异或运算得到(一条路经过多次则会被计算多次)。 现在***国专家正在讨论“八纵八横”的建设方案，他们会不断地修改方案，希望你能实时反馈对于当前的“八纵八横”的建设计划，“内陆城市经济环”的GDP值最大是多少。 初始时，“八纵八横”计划中不包含任何一条高铁，建设方案设有以下3 种操作计划： Add x y z 表示在城市x和城市y之间建设一条高速铁路，其GDP影响因子设为z，如果这是第k个add 操作，则将这条高铁命名为k号高铁; Cancel k 表示将第k号高铁取消掉，此时，保证k号高铁一定存在。 Change k z 表示将第k号高铁的GDP影响因子改为z，此时，保证k 号高铁一定存在。
Input
第一行三个整数： N M Q 分别表示N个城市，M条高速公路及Q个操作计划 接下来有M行， Xi Yi Zi 表示城市Xi与城市Yi有一条高速公路，GDP影响因子Zi i=1,2,….,M 接下来有Q 行，每一行一个操作计划: Add x y z 或 Cancel k 或 Change k z
Output
第一行,一个整数，表示如果不修建任何高速铁路，“内陆城市经济环”的GDP最大值； 接下来Q行，每行一个整数，表示进行了对应的每一个操作计划后，对于当前的计划，“内陆城市经济环”的GDP最大值。
Sample Input
4 4 3
1 2 1110
1 3 10
2 4 1110
2 3 100
Add 3 4 11
Change 1 101
Cancel 1
Sample Output
1000
1001
1111
1000
HINT
- 输入的所有GDP影响因子都将以二进制的形式从高位到低位给出，最多位数为1000
- 输出的答案也要以二进制的形式从高位到低位给出。
- 所有的Add操作不超过500个。 2<=n, m<=500 , 0<=Q<=1000
- 两个城市之间可能有多条高速公路或高铁，高速公路或高铁的两端可能是同一个城市(即
有重边，有自环)。
emmmm，不会做，搜了一份代码，姑且先放到这里。
解法种用到了线段树，一个我至今不会的东西。
#include<bits/stdc++.h>
typedef std::bitset<1003> bit;
const int maxn = 535;
const int maxm = 1035;
const int maxq = 1035;
const int maxOpt = 10035;
struct Opt
{
int l,r;
bit w,rin;
Opt(int a=0, int b=0, bit c=bit(), bit d=bit()):l(a),r(b),w(c),rin(d) {}
}sv[maxm];
struct Edge
{
int v;
bit w;
Edge(int a=0, bit b=bit()):v(a),w(b) {}
}edges[maxm];
struct LinearBasis
{
bit p[1003];
void insert(bit w)
{
for (int i=1000, chk=0; i>=0&&!chk; i--)
if (w[i]){
if (p[i].any()) w ^= p[i];
else p[i] = w, chk = 1;
}
}
void query()
{
bit ans = bit();
int pos = 0;
for (int i=1000; i>=0; i--)
{
if (ans[i]==0) ans ^= p[i];
if (ans[i]&&!pos) pos = i;
}
for (int i=pos; i>=0; i--) putchar(ans[i]?'1':'0');
puts("");
}
};
typedef std::vector<Opt> vec;
int n,m,T,cnt;
int fat[maxn],tag[maxq];
int edgeTot,head[maxn],nxt[maxm];
bit dis[maxn],tmp;
char str[13];
vec opt;
int read()
{
char ch = getchar();
int num = 0, fl = 1;
for (; !isdigit(ch); ch=getchar())
if (ch=='-') fl = -1;
for (; isdigit(ch); ch=getchar())
num = (num<<1)+(num<<3)+ch-48;
return num*fl;
}
void read(bit &x)
{
char str[1035];
scanf("%s",str+1), x = bit();
for (int i=strlen(str+1), j=0; i>=1; i--)
x[j] = str[i]-'0', ++j;
}
int find(int x){return x==fat[x]?x:fat[x]=find(fat[x]);}
void addedge(int u, int v, bit w)
{
edges[++edgeTot] = Edge(v, w), nxt[edgeTot] = head[u], head[u] = edgeTot;
edges[++edgeTot] = Edge(u, w), nxt[edgeTot] = head[v], head[v] = edgeTot;
}
void dfs(int x, int fa, bit c)
{
dis[x] = c;
for (int i=head[x]; i!=-1; i=nxt[i])
{
int v = edges[i].v;
if (v!=fa) dfs(v, x, c^edges[i].w);
}
}
void solve(int l, int r, vec opt, LinearBasis bas)
{
vec L,R;
int mid = (l+r)>>1;
for (int i=0, mx=opt.size(); i<mx; i++)
if (opt[i].l <= l&&r <= opt[i].r) bas.insert(opt[i].w);
else{
if (opt[i].l <= mid) L.push_back(opt[i]);
if (opt[i].r > mid) R.push_back(opt[i]);
}
if (l==r) bas.query();
else solve(l, mid, L, bas), solve(mid+1, r, R, bas);
}
int main()
{
memset(head, -1, sizeof head);
n = read(), m = read(), T = read();
for (int i=1; i<=n; i++) fat[i] = i;
for (int i=1,u,v; i<=m; i++)
{
u = read(), v = read(), read(tmp);
if (find(u)!=find(v))
fat[fat[u]] = fat[v], addedge(u, v, tmp);
else sv[++cnt] = Opt(u, v, tmp);
}
dfs(1, 0, bit());
for (int i=1; i<=cnt; i++)
opt.push_back(Opt(0, T, sv[i].w^dis[sv[i].l]^dis[sv[i].r]));
for (int i=1,cnt=0,u,v; i<=T; i++)
{
scanf("%s",str);
if (str[0]=='A'){
u = read(), v = read(), read(tmp);
opt.push_back(Opt(i, T, dis[u]^dis[v]^tmp, tmp));
tag[++cnt] = opt.size()-1;
}else if (str[1]=='h'){
u = read(), read(tmp), opt[tag[u]].r = i-1;
opt.push_back(Opt(i, T, tmp^opt[tag[u]].rin^opt[tag[u]].w, tmp));
tag[u] = opt.size()-1;
}else opt[tag[read()]].r = i-1;
}
solve(0, T, opt, LinearBasis());
return 0;
} Problem F: Binary to Prime(2)
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 4 Solved: 3
[Submit][Status][Web Board]
Description
To facilitate the analysis of a DNA sequence, a DNA sequence is represented by a binary number. The group of DNA-1 has discovered a great new way . There is a certain correlation between binary number and prime number. Instead of using the ordinary decadic numbers, they use prime base numbers. Numbers in this base are expressed as sequences of zeros and ones similarly to the binary numbers, but the weights of bits in the representation are not powers of two, but the elements of the primes ( 2, 3, 5, 7,… ). For example 01101 , ie. 2+5+7=14 Herefore, it is necessary to convert the binary number to the sum of prime numbers
Input
The input consists of several instances, each of them consisting of a single line. Each line of the input contains a 01 string, length of not more than 150. The end of input is not marked in any special way.
Output
For each test case generate a single line containing a single integer , The sum of the primes.
Sample Input
000010
0011
11001
Sample Output
3
5
20
没啥东西，打个素数表，然后按照要求求和就好。
#include<bits/stdc++.h>
using namespace std;
const int maxn=900000;
int vis[maxn];
int p[maxn];
int cnt=0;
string s;
void gerPrime()
{
for(int i=2;i<=sqrt(maxn);i++)
{
if(!vis[i])
p[cnt++]=i;
for(int j=0;j<=cnt;j++)
{
if(i*p[j]>=maxn)break;
vis[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
int main()
{
gerPrime();
while(cin>>s)
{
int ans=0;
for(int i=0;i!=s.size();i++)
{
ans+=(s[i]-'0')*p[s.size()-i-1];
}
printf("%d\n",ans);
}
return 0;
} Problem G: G. Plumbing the depth of lake
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1 Solved: 1
[Submit][Status][Web Board]
Description
There is a mysterious lake in the north of Tibet. As the sun shines, the surface of the lake is colorful and colorful. The lake was unfathomable in rainy weather. After the probe, It has an interesting bottom in that it is full of little hills and valleys. . Scientists wonders how deep the bottom of the lake is. Scientists use the most advanced radar equipment to detect the bottom of the lake. It is the discovery that the deepest part is relatively flat. Thet want to know the largest depth number only if it is verified by the fact that the same depth appears in an adjacent reading. To facilitate computing, scientists have put the lake as M * N grids . The depth reading of each grid is already known. some readings might be 0-- It’s a small island on the lake. Find the greatest depth that appears in at least two 'adjacent’readings (where ‘adjacent’ means in any of the potentially eight squares that border a square on each of its sides and its diagonals). The lake has at least one pair of positive, adjacent readings.
Input
The first line of the input contains one integers T, which is the nember of test cases (1<=T<=5). Each test case specifies: * Line 1: Two space-separated integers: M and N (1 ≤ M, N ≤ 50) * Lines 2…M+1: Line i+1 contains N space-separated integers that represent the depth of the lake across row i: Dij (0 <= Dij <=1,000,000);
Output
For each test case generate a single line: a single integer that is the depth of the lake determined.
Sample Input
1
4 3
0 1 0
1 2 0
1 5 1
2 3 4
Sample Output
1
这个就是让你找找数字最大的连续出现的数字就行。一个深搜加vis标记，就好
#include<bits/stdc++.h>
using namespace std;
const int maxn=51;
int T;
int n,m;
int map1[maxn][maxn];
bool check(int x,int y)
{
if(x<n-1&&y>0&&(map1[x+1][y-1]==map1[x][y]))
return true;
if(x<n-1&&(map1[x+1][y]==map1[x][y]))
return true;
if(x<n-1&&y<m-1&&(map1[x+1][y+1]==map1[x][y]))
return true;
if(y<m-1&&(map1[x][y+1]==map1[x][y]))
return true;
return false;
}
int main()
{
cin>>T;
for(int t=0;t!=T;t++)
{
int des=0;
scanf("%d %d",&n,&m);
for(int i=0;i!=n;i++)
{
for(int j=0;j!=m;j++)
{
scanf("%d",&map1[i][j]);
}
}
for(int i=0;i!=n;i++)
{
for(int j=0;j!=m;j++)
{
if(map1[i][j]>des)
{
if(check(i,j))
des=map1[i][j];
}
}
}
cout<<des<<endl;
}
return 0;
} Problem H: H. Intelligent Parking Building
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 2 Solved: 2
[Submit][Status][Web Board]
Description
There is a new revolution in the parking lot business: the parking building. The concept is simple: you drive your car into the elevator at the entrance of the building, and the elevator and conveyor belts drag the car to an empty parking spot, where the car remains until you pick it up. When you return, the elevator and conveyor belts move your car back to the entrance and you’re done. The layout of the building is simple. There is one central elevator that transports the cars between the different floors. On each floor there is one giant circular conveyor belt on which the cars stand. This belt can move in clockwise and counterclockwise direction. When the elevator arrives on a floor, it becomes part of the belt so that cars can move through it. At the end of the day the building is usually packed with cars and a lot of people come to pick them up. Customers are processed in a first come first serve order: the elevator is moved to the floor of the first car, the conveyor belt moves the car on the elevator, the elevator is moved down again, and so on. We like to know how long it takes before the last customer gets his car. Moving the elevator one floor up- or downwards takes 10 seconds and moving the conveyor belt one position in either direction takes 5 seconds.
Input
On the first line one positive number: the number of testcases, at most 30. Each test case specifies: • One line with two integers h and l with 1 ≤ h ≤ 50 and 2 ≤ l ≤ 50: the height of the parking tower and the length of the conveyor belts. • h lines with l integers: the initial placement of the cars. The jth number on the ith line describes the jth position on the ith floor. This number is −1 if the position is empty, and r if the position is occupied by the rth car to pick up. The positive numbers form a consecutive sequence from 1 to the number of cars. The entrance is on the first floor and the elevator (which is initially empty) is in the first position. There is at least one car in the parking tower.
Output
For each test case generate a single line containing a single integer that is the number of seconds before the last customer is served.
Sample Input
3
1 5
1 -1 -1 -1 2
1 5
2 -1 -1 -1 1
3 6
-1 5 6 -1 -1 3
-1 -1 7 -1 2 9
-1 10 4 1 8 -1
Sample Output
5
10
320
这个题目的描述写的还是比较清晰的。
就是说一个主的电梯，在不同的楼层之间跑，每次楼还有一个圆的转盘形的电梯，一开始每个圆的转盘电梯的一号停车位在楼层电梯的出口那里。
那我们就记录每个车的楼层，每个车的位置，每层楼圆形电梯的出口位置，然后模拟出去就好。
#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
map<int,int> f;
map<int,int> p;
int a[maxn];
int T,n,l,t,maxnum;
int sum;
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&T))
{
while(T--)
{
sum=0;
scanf("%d %d",&n,&l);
//init the entrance of every floor
for(int i=1;i<=n;i++)
{
a[i]=1;
}
maxnum=1;
for(int i=1;i<=n;i++)
{
int cnt=0;
for(int j=1;j<=l;j++)
{
scanf("%d",&t);
if(t>0)
{
maxnum=max(maxnum,t);
cnt++;
f[t]=i;
p[t]=j;
}
}
sum+=2*(cnt)*(i-1)*10;
}
for(int i=1;i<=maxnum;i++)
{
int len1 = a[f[i]]-1+l-p[i]+1;
int len2 = p[i]-1+l-a[f[i]]+1;
sum+=(min(abs(a[f[i]]-p[i]),min(len1,len2))*5);
a[f[i]]=p[i];
}
printf("%d\n",sum);
}
}
return 0;
} Problem I: I. Transmit information
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 0 Solved: 0
[Submit][Status][Web Board]
Description
The Chinese people threw themselves into an all-out war of resistance against Japanese aggression in 1937. The first line of resistance against aggression was formed by spies and underground workers. They lurked in every place of the city. There’s a piece of information that needs to be passed on to them. Now there is a traffic map, each road connects two different intersections Xi and Yi, each of which is the termination for at least two road. The length of each road is known LENi, no two intersections are directly connected by two different roads. N spies lurk at every intersection , some intersections mignt have more than one spy. For security, they must position themselves properly , each spy cannot accept information from local intersection , can only be transferred from elsewhere and end up at the finishing pace. At first, the information is in the hands of a spy at S intersection. After N spies transmission, and finally arrived at E intersection . Write a program to find the shortest path that connects the starting intersection(S) and the ending intersection(E) ang transmission exactly N spies.
Input
The first line of the input contains one integers T, which is the nember of test cases (1<=T<=5). Each test case specifies: * Line 1: Four space-separated integers: N M S E * Lines 2…M+1: Line i+1 describes road i with three space-separated integers: LENi Xi Yi ( 2<=N<=300,000 2<=M<=100, 1<= LENi, Xi, Yi ,S, E <=1000 i=1,…,m)
Output
For each test case generate a single line containing a single integer that is the shortest path from intersection S to intersection E that transmits exactly N spies.
Sample Input
1
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9
Sample Output
10
让求从S到E，经过点的个数为n的最短路径。
没思路，不会写，大佬门说是用floyd。
代码也没看懂。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<map>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 110;
int N,M,S,E; ///经过N个间谍传播，M道路条数，
//用来记录任意两个点之间的距离
struct matrix
{
ll a[maxn][maxn];
}dis,ans;
//传入
matrix flody(matrix A,matrix B,int n)
{
matrix tmp;
//初始化tmp地图，所有路径长度初始化为正无穷
for(int i = 1; i < n; i++)
for(int j = 1; j < n; j++)
tmp.a[i][j] = inf;
//使用floyd找到最短路径地图，并返回
for(int k = 1; k < n; k++)
for(int i = 1; i < n; i++)
for(int j = 1; j < n; j++)
if(tmp.a[i][j]>A.a[i][k]+B.a[k][j])
tmp.a[i][j] = A.a[i][k] + B.a[k][j];
return tmp;
}
void solve(int n,int s,int e)
{
//先讲距离拷贝一份到ans
for(int i = 1; i < n; i++)
for(int j = 1; j < n; j++)
ans.a[i][j] = dis.a[i][j];
//N记录了要经过的点的个数
N--;
while(N)
{
//如果是奇数，那么
if(N&1)
{
ans = flody(ans,dis,n);
}
//然后再
dis = flody(dis,dis,n);
//最后
N = N>>1;
}
//输出最后结果
if(ans.a[s][e] < inf)
printf("%lld\n",ans.a[s][e]);
}
int main()
{
int T,len,x,y;
scanf("%d",&T);
while(T--)
{
map<int,int>m; ///用map来给点进行编号。
int num = 1;
scanf("%d%d%d%d",&N,&M,&S,&E);
//先将所有距离初始化为正无穷
for(int i = 0; i < maxn; i++)
for(int j = 0; j < maxn; j++)
dis.a[i][j] = inf;
//输入数据，并为每个点编号
for(int i = 1; i <= M; i++)
{
scanf("%d%d%d",&len,&x,&y);
//如果这个点没有被编过号，那么我们为这个节点分配一个编号
if(m[x]==0)
{
m[x] = num++;
}
int xi = m[x];
if(m[y]==0)
{
m[y] = num++;
}
int yi = m[y];
//如果输入的新数据比老数据的距离小，那么覆盖老数据
if(len < dis.a[xi][yi])
dis.a[xi][yi] = dis.a[yi][xi] = len;
}
//解决num个点，从 S 到 E的问题
solve(num,m[S],m[E]);
}
return 0;
}
京公网安备 11010502036488号