7-1 懂得都懂
题目描述：
7-1 懂的都懂
众所周知，在互联网上有很多话是不好直接说出来的，不过一些模糊的图片仍然能让网友看懂你在说什么。然而对这种言论依然一定要出重拳，所以请你实现一个简单的匹配算法。
现在我们采集了原图的一些特征数据，由 N 个小于 255 的非负整数组成，假设对于给定的若干张由 Mi个同样小于 255 的非负整数组成的新图的特征数据，每个数据都可以由原图中任意四个不同数据的平均值计算而来，则称新图为原图的相似图片。对于给出的数据，请你判断是不是相似图片。
注意，不同数据指的并非是数据的值不同，而是不能取同一个数据多次。对于两个相同值的数据，如果给出两次，则可以取两次。
输入格式:
输入第一行是两个整数 N,K (1 ≤ N ≤ 50, 1 ≤ K ≤ 200)，表示采集的原图的特征数据个数和新图的张数。
接下来一行为 N 个小于 255 的非负整数，表示原图的特征数据。
最后的 K 行，每行第一个数是 M
i(1 ≤ Mi≤ 200)，表示新图的特征数据个数。然后是 Mi个小于 255 的非负整数，表示新图的特征数据。
输出格式:
对于每一张新图，如果为相似图片，则在一行中输出 Yes，否则输出 No。
输入样例:
5 3
4 8 12 20 40
3 11 16 19
3 12 16 19
10 11 11 11 11 11 11 11 11 11 11
输出样例:
Yes
No
Yes
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
代码实现：
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define int long long
const int N=1005;
int a[N],b[N];
unordered_map<int,int>mp;
signed main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
for(int l=j+1;l<n;l++){
for(int r=l+1;r<n;r++){
int t=a[i]+a[j]+a[l]+a[r];
if(t%4==0)mp[t/4]=1;
}
}
}
}
while(m--){
int k;
cin>>k;
int flag=1;
for(int i=0;i<k;i++)cin>>b[i];
for(int i=0;i<k;i++){
if(!mp[b[i]]){
flag=0;
break;
}
}
if(flag)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
7-2 芬兰木棋
题目描述：
芬兰木棋（Mölkky，又称芬兰木柱）是源自芬兰的一项运动。哲哲将这个运动改造成了赛博朋克单人版，现在场上一开始有 N 根立起的小木棋（上面分别标有一个非负整数），哲哲投掷一根大木棋去击倒这些小木棋以获得分数。分数规则如下：
- 如果仅击倒 1 根木棋，则得木棋上的分数。
- 如果击倒 2 根或以上的木棋，则只得击倒根数的分数。（例如击倒 5 根，则得 5 分。）
哲哲固定站在 (0,0) 点上，四周放着若干个小木棋 (Xi,Yi)，坐标均为整数。每次哲哲可以朝一个方向扔出大木棋，大木棋会打倒这个方向上离哲哲最近的 k 个小木棋。哲哲游戏水平很高超，所以这个 k 可以自由控制。
请问哲哲最多能拿多少分，在获得最多分数的情况下最少需要扔出多少次大木棋？
规则与真实规则有较大出入，真实游玩时请以国际莫尔基组织的规则为准
输入格式:
输入第一行是一个正整数 N (1 ≤ N ≤ 10^5)，表示场上一开始有 N 个木棋。
接下来 N 行，每行 3 个整数 Xi,Yi,Pi，分别表示木棋放置在 (Xi,Yi)，木棋上的分数是 Pi。坐标在 32 位整数范围内，分数为小于等于 1000 的正整数。
保证 (0,0) 点没有木棋，也没有木棋重叠放置。
输出格式:
输出一行两个数，表示最多分数以及获得最多分数最少需要投掷大木棋多少次。
输入样例:
11
1 2 2
2 4 3
3 6 4
-1 2 2
-2 4 3
-3 6 4
-1 -2 1
-2 -4 1
-3 -6 1
-4 -8 2
2 -1 999
输出样例:
1022 9
代码实现：
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
#define int long long
const int N=1e5+5;
typedef pair<int,int>PII;
int res,cnt;
map<PII,vector<PII> >mp1,mp2;
vector<PII>v;
int cal(int x,int y){
return x*x+y*y;
}
void func(vector<PII> v){
for(int i=0;i<v.size();i++){
if(v[i].second==1){
int j=i;
for(;j<v.size();j++){
if(v[j].second!=1)break;
}
i=j-1;
}
cnt++;
}
}
signed main(){
int n;
cin>>n;
while(n--){
int x,y,z;
cin>>x>>y>>z;
int t=__gcd(abs(x),abs(y));
mp1[{x/t,y/t}].push_back({cal(x,y),z});
res+=z;
}
for(auto t:mp1){
vector<PII> v1=t.second;
sort(v1.begin(),v1.end());
func(v1);
}
cout<<res<<" "<<cnt<<endl;
return 0;
}
7-3 打怪升级
题目描述：
很多游戏都有打怪升级的环节，玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏，游戏规则是，给定有 N 个堡垒的地图，堡垒之间有道路相连，每条道路上有一只怪兽把守。怪兽本身有能量，手里的武器有价值。打败怪兽需要的能量等于怪兽本身的能量，而怪兽一旦被打败，武器就归玩家所有 —— 当然缴获的武器价值越高，玩家就越开心。
你的任务有两件：
- 1.帮助玩家确定一个最合算的空降位置，即空降到地图中的某个堡垒，使得玩家从这个空降点出发，到攻下最难攻克（即耗费能量最多）的那个堡垒所需要的能量最小；
- 2.从这个空降点出发，帮助玩家找到攻克任意一个其想要攻克的堡垒的最省能量的路径。如果这种路径不唯一，则选择沿途缴获武器总价值最高的解，题目保证这种解是唯一的。
输入格式:
输入第一行给出两个正整数 N (≤1000) 和 M，其中 N 是堡垒总数，M 是怪兽总数。为简单起见，我们将堡垒从 1 到 N 编号。随后 M 行，第 i 行给出了第 i 只怪兽的信息，格式如下：
B1 B2 怪兽能量 武器价值
其中 B1 和 B2 是怪兽把守的道路两端的堡垒编号。题目保证每对堡垒之间只有一只怪兽把守，并且 怪兽能量 和 武器价值 都是不超过 100 的正整数。
再后面是一个正整数 K（≤N）和玩家想要攻克的 K 个目标堡垒的编号。
输出格式:
首先在一行中输出玩家空降的堡垒编号 B0。如果有多种可能，则输出编号最小的那个。
随后依次为玩家想要攻克的每个堡垒 B 推荐最省能量的攻克路径，并列出需要耗费的能量值和沿途缴获武器的总价值。注意如果最省力的路径不唯一，则选择沿途缴获武器总价值最高的解。格式为：
B0->途经堡垒1->...->B
总耗费能量 武器总价值
输入样例:
6 12
1 2 10 5
2 3 16 20
3 1 4 2
2 4 20 22
4 5 2 2
5 3 12 6
4 6 8 5
6 5 10 5
6 1 20 25
1 5 8 5
2 5 2 1
2 6 8 5
4
2 3 6 5
输出样例:
5
5->2
2 1
5->1->3
12 7
5->4->6
10 7
5
0 0
代码实现：
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
using namespace std;
#define int long long
typedef pair<int,int>PII;
const int N=1005,M=2*N;
int h[N],e[M],w[M],cnt[M],ne[M],idx;
int dist[N],vis[N],pre[N],num[N];
int d[N][N],s[N];
int n,m;
void add(int a,int b,int c,int d){
e[idx]=b,w[idx]=c,cnt[idx]=d,ne[idx]=h[a],h[a]=idx++;
}
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
void dijkstra(int start){
priority_queue<PII,vector<PII>,greater<PII> >q;
memset(dist,0x3f,sizeof dist);
memset(pre,-1,sizeof pre);
dist[start]=0;
q.push({0,start});
while(q.size()){
int dis=q.top().first;
int s=q.top().second;
q.pop();
if(vis[s])continue;
vis[s]=1;
for(int i=h[s];~i;i=ne[i]){
int j=e[i];
if(dist[j]>dist[s]+w[i]){
dist[j]=dist[s]+w[i];
pre[j]=s;
num[j]=num[s]+cnt[i];
q.push({dist[j],j});
}else if(dist[j]==dist[s]+w[i]){
if(num[j]<num[s]+cnt[i]){
num[j]=num[s]+cnt[i];
pre[j]=s;
}
}
}
}
}
void print(int x){
if(x!=-1){
print(pre[x]);
if(pre[x]==-1)cout<<x;
else cout<<"->"<<x;
}
}
signed main(){
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)d[i][j]=0;
else d[i][j]=0x3f3f3f3f;
}
}
while(m--){
int x,y,z,z1;
cin>>x>>y>>z>>z1;
add(x,y,z,z1);
add(y,x,z,z1);
d[x][y]=d[y][x]=z;
}
int k;
cin>>k;
for(int i=0;i<k;i++)cin>>s[i];
floyd();
int start=0,min1=0x3f3f3f3f;;
for(int i=1;i<=n;i++){
int max1=0;
for(int j=1;j<=n;j++)max1=max(max1,d[i][j]);
if(max1<min1)min1=max1,start=i;
}
cout<<start<<endl;
dijkstra(start);
for(int i=0;i<k;i++){
print(s[i]);
cout<<endl;
cout<<dist[s[i]]<<" "<<num[s[i]]<<endl;
}
return 0;
}