比赛分析
出题人看法：由于这是场欧洲地区的比赛，在国内没找到出题人的官方消息，所以……，这一行到此结束
本博主的想法：这场比赛显然的一场多题场。现在我对多题场的认知就是时间减少的少题场。然而时间减少了多少，就看你签到题多久才出！因为同层次的队伍水平都一样，出的快慢直接决定了前期的排名！对比赛题目而言，外国场真的难读！由铁到铜需要一定的心态，有那么两道题是真的心态不好就会炸！榜上大佬7对队K，对此我表示……没有什么想说的了！接下来的卡点就在D、E、H、L这四题。D的模拟题有一定的难度，要用到字符串哈希；E感觉上是个DP，但空间上的储存也有问题；总的来说，需要用来区分的题还是有一定难度的！
比赛题目
比赛题目
A题： Environment-Friendly Travel
从一个点到另一个点，中间每条边含有两个变量，
c
o
2
co_{2}
co2?浓度和路径长度。求在可达到的情况下最小的
c
o
2
co_{2}
co2?浓度。
B题： Biodiversity
多种字符串，求字符串出现最多的的串，如果最多的串的数量大于其他串的总和则输出，否则NONE
C题：Ants
给一串数字（最长100位），求没出现的最小自然数
D题：Gnalcats
有两个操作串包含(C, D, L, P, R, S, U) 求两个操作串的出的结果是否一样
c：复制，D删除，L选择左端的带你，P合并，R选择有端点，S交换位置，U拆分
E题：Pixels
画一张图，开始给出一张图。你的图全是白色的。每一坐标点有一个开关，按下开关之后，该点和周围的几个点（上下左右）变色，求开关按下那些开关。
F题：Icebergs
给多个冰川，每个冰川给出周围的坐标，求冰川总面积
G题：S种动物，L对朋友关系（不存在朋友的朋友是朋友这种关系），N只动物，相邻的朋友之间可以换序，输出字典序最小的可能顺序。
H题：
I题：Rats
给出表达式，带公示求解
n
^
=
?
(
n
1
+
1
)
(
n
2
+
1
)
n
12
+
1
?
1
?
\hat{n} =\lfloor \frac{(n_{1} + 1)(n_{2} + 1)} {n_{12}+1} - 1 \rfloor
n^=?n12?+1(n1?+1)(n2?+1)??1?
J题：
K题：Birdwatching
给一个假图，求真图上与点T链接的所有点。真假图的关系：假图上会给出从a到b的边，表示可以从a走到b，但不一定是直接走到。这条边可以不存在，真图上是求出所有一定存在的点。
L题：River Game
部分题目思路及代码
F题：Icebergs
考点：二维面积
思路：求二维面积
代码：
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct Point
{
double x, y;
Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
Vector operator - (Point A, Point B)
{
return Vector(A.x - B.x, A.y - B.y);
}
double ans;
Point p[1000];
double cross(Vector A, Vector B) { return A.x * B.y - B.x * A.y; }
double get_area(Point *p,int n)
{
double area = 0;
for (int i = 1; i <= n - 2; ++i)
area += cross(p[i]-p[0], p[i + 1]-p[0]);
return area / 2;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int sum;
cin >> sum;
for (int j = 0; j < sum; j++)
cin >> p[j].x >> p[j].y;
ans += fabs(get_area(p, sum));
}
ans = (long long)ans;
printf("%.0lf\n", ans);
return 0;
}
K题：Birdwatching
考点：思维能力 + bfs（可以拿dfs剪枝写）
思路：反向建边，广搜几个与T相连的点，这几个点出现次数>1，则删除。
有一种特殊情况：自行成为回路，在走bfs时更新根结点，如果再次走到的点是由它本身出发的直接continue
代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5+7;
struct one_tu
{
int v,next;
}tu[N];
int head[N],top,n,m,t;
void build(int u,int v)
{
tu[top] = {v,head[u]};
head[u] = top;
top++;
}
queue<pii>q;
int vis[N],f[N];
int T[N],num;
int ans[N],cnt;
void bfs()
{
for(int it = 0; it < num; it++)
{
int s = T[it];
f[s] = s;
vis[s] = 1;
q.push({s,s});
}
while(!q.empty())
{
int u = q.front().first;
int idx = q.front().second;
q.pop();
for(int i = head[u]; ~i; i = tu[i].next)
{
int v = tu[i].v;
if(v == idx) continue;
if(vis[v] == 0)
{
vis[v] = 1;
q.push({v,idx});
f[v] = idx;
}
else if(vis[v] == 1)
{
if(f[v] != idx) vis[v]++;
q.push({v,idx});
}
}
}
}
int main()
{
memset(head, -1, sizeof head);
scanf("%d%d%d",&n,&m,&t);
for(int i = 0; i < m; i++)
{
int u,v;scanf("%d%d",&u,&v);
if(v == t)T[num++] = u;
else build(v, u);
}
bfs();
for(int i = 0; i < num; i++)
if(vis[T[i]] == 1)ans[cnt++] = T[i];
printf("%d\n",cnt);
for(int i = 0; i < cnt; i++)
printf("%d\n",ans[i]);
return 0;
}
A题：Environment-Friendly Travel
考点：建图，二维dijkstra
思路：用链式前向星建图，跑dijkstra。开二维dijkstra，第二维存剩余里程数。
dij[v][k-distance] = dij[u][k] + co_{2}
代码：
#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
const int E = 3e5+7;
const int inf = 0x3f3f3f;
pii station[1111][1111];
pii s,t;
int C[111],n,B,T;
int dco[2000][111],vis[2000][111];
struct one_tu
{
int v, next, co_2, distance;
}tu[E];
int head[E],top = 0;
void build(int u,int co_2,int distance,int v)
{
tu[top] = {v,head[u],co_2,distance};
head[u] = top;
top++;
}
int make_dist(pii a,pii b)
{
double x = fabs(a.first - b.first), y = fabs(a.second - b.second);
x = x * x; y = y * y;
double mid = sqrt(x+y);
int ans = (int)mid;
if(mid > ans) mid++;
return mid;
}
struct node
{
bool friend operator < (node a, node b)
{
return a.cost > b.cost;
}
int cost,to,k;
};
void dijkstra(int s)
{
priority_queue<node>q;
dco[s][B] = 0;
q.push({0,s,B});
while(!q.empty())
{
int u = q.top().to;
int k = q.top().k;
q.pop();
if(vis[u][k])continue;
vis[u][k] = 1;
for(int i = head[u]; i != -1; i = tu[i].next)
{
int v = tu[i].v;
int co_2 = tu[i].co_2;
int dit = tu[i].distance;
if(k >= dit)
{
if(dco[v][k-dit] > dco[u][k] + co_2)
{
dco[v][k-dit] = dco[u][k] + co_2;
if(!vis[v][k-dit])
{
q.push({dco[v][k-dit],v,k-dit});
}
}
}
}
}
}
int main()
{
memset(head, -1, sizeof head);
memset(dco, inf, sizeof dco);
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
s = {x1,y1};t = {x2,y2};
scanf("%d",&B);
scanf("%d%d",&C[0],&T);
for(int i = 1; i <= T; i++)
scanf("%d",&C[i]);
int d = make_dist(s, t);
int o = d * C[0];
scanf("%d",&n);
build(0, o, d, n+1);
for(int i = 1; i <= n; i++)
{
int x,y,l;scanf("%d%d%d",&x,&y,&l);
station[i][0] = {x,y};
for(int j = 1; j <= l; j++)
{
int to,m;scanf("%d%d",&to,&m);
station[i][j] = {to+1,m};
}
station[i][l+1] = {-1,-1};
}
for(int i = 1; i <= n; i++)
{
pii x = station[i][0];
int dist_s = make_dist(x, s), dist_t = make_dist(x, t);
int co_2_s = dist_s * C[0], co_2_t = dist_t * C[0];
build(0, co_2_s, dist_s, i);
build(i, co_2_t, dist_t, n+1);
for(int j = 1; station[i][j].first != -1 ; j++)
{
int to = station[i][j].first;
int c = station[i][j].second;
pii y = station[to][0];
int dist = make_dist(x, y);
int co_2 = dist * C[c];
build(to, co_2, dist, i);
build(i, co_2, dist, to);
}
}
dijkstra(0);
int ans = inf;
for(int i = B; i >= 0; i--)
ans = min(ans, dco[n+1][i]);
printf("%d\n",ans == inf ? -1 : ans);
return 0;
}
补一个做题心得：这道题信息量特大，建图麻烦，但不难写，细节有点多。我在写的时候出现了dijkstra上的失误，本不该出现，应该是建图时建烦了。怎一个缺德了得啊！
G题：Swapping Places
考点：拓扑排序的建图
思路：拓扑排序的思路（可惜这个方法我没用）。用的贪心的思想：一共有S种动物，N个点，求每种动物能不能到这个点就好。
代码：
#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
const int N = 1e5+7;
map<string, int>idx;
map<int, string>tran;
string animal[222];
bool vis[222][222];
int a[N],flag[N],ans[N],jud[N],loc[N];
int s,l,n;
void fid()
{
for(int j = 1; j <= s; j++)
{
while (jud[loc[j]] || (loc[j] <= n && a[loc[j]] != j && vis[a[loc[j]]][j])) loc[j] ++;
if(loc[j] <= n && a[loc[j]] == j)flag[j] = 1;
}
}
int main()
{
cin >> s >> l >> n;
for(int i = 1; i <= s; i++)
cin >> animal[i];
sort(animal + 1, animal + 1 + s);
for(int i = 1; i <= s; i++)
{
idx[animal[i]] = i;
tran[i] = animal[i];
loc[i] = 1;
}
for(int i = 1; i <= l; i++)
{
string x,y;
cin >> x >> y;
vis[idx[x]][idx[y]] = 1;
vis[idx[y]][idx[x]] = 1;
}
for(int i = 1; i <= n; i++)
{
string str; cin >> str;
a[i] = idx[str];
}
for(int i = 1; i <= n; i++)
{
fid();
int mid = 1;
for(int j = 1; j <= s; j++)
if(flag[j]){mid = j;break;}
ans[i] = mid;
jud[loc[mid]] = 1;
loc[mid] ++;
flag[mid] = 0;
}
for(int i = 1; i <= n; i++)
cout << tran[ans[i]] <<" ";
return 0;
}
|