比赛地址
Rank:26/95
[A] Environment-Friendly Travel
题意
给出一个图,求起点到终点的所有路径中,不超过距离b的花费最小的路径是多少.每条路的花费和路径长度并不相同.
题解
考虑对Dijkstra进行一下改进,用dis[i][j]表示从起点到点i的长度恰好为j的路径中,最少的花费是多少.然后堆里的元素同时维护点的编号,花费,以及起点到该点的路径长度.用改进后的Dijkstra跑一遍就行了.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
int T,n,b,i,j,lsum=1,l,p,q;
int c[N],x[N],y[N],head[N];
int dis[N][N];
typedef pair<int,int> pi;
vector <pi> a[N];
priority_queue <pair<int,pair<int,int> > > Q;
struct Edge{
int t,next,l,c;
}e[N*N*8];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Add(int s,int t,int l,int cost){
e[lsum].t=t; e[lsum].l=l; e[lsum].next=head[s]; e[lsum].c=cost; head[s]=lsum++;
}
IL int Dis(int i,int j){
return ceil(sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2)));
}
IL void Ready(){
reg int i=0,d=0;
for (i=1;i<=n;i++)
for (auto j : a[i]){
d=Dis(i,j.first)*c[j.second];
Add(i,j.first,d,Dis(i,j.first)); Add(j.first,i,d,Dis(i,j.first));
}
for (i=1;i<=n;i++){
Add(0,i,Dis(0,i)*c[0],Dis(0,i));
Add(i,0,Dis(0,i)*c[0],Dis(0,i));
Add(1001,i,Dis(1001,i)*c[0],Dis(1001,i));
Add(i,1001,Dis(1001,i)*c[0],Dis(1001,i));
}
Add(0,1001,Dis(0,1001)*c[0],Dis(1001,0));
Add(1001,0,Dis(0,1001)*c[0],Dis(1001,0));
}
IL void Work(){
reg int i=0,Ans=INF,p=0,q=0;
if (Dis(0,1001)>b){
puts("-1");
return;
}
memset(dis,INF,sizeof(dis));
dis[0][0]=0;
Q.push(make_pair(0,make_pair(0,0)));
while (!Q.empty()){
pair<int,pair<int,int>> s=Q.top();
Q.pop();
p=s.second.first; q=s.second.second;
for (i=head[p];i;i=e[i].next){
if (q+e[i].c>b) continue;
if (e[i].l-s.first<dis[e[i].t][q+e[i].c]){
dis[e[i].t][q+e[i].c]=e[i].l-s.first;
Q.push(make_pair(-dis[e[i].t][q+e[i].c],make_pair(e[i].t,q+e[i].c)));
}
}
}
for (i=0;i<=b;i++)
Ans=Min(Ans,dis[1001][i]);
cout<<Ans<<endl;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
x[0]=read(); y[0]=read();
x[1001]=read(); y[1001]=read();
b=read(); c[0]=read(); T=read();
for (i=1;i<=T;i++) c[i]=read();
n=read();
for (i=1;i<=n;i++){
x[i]=read(); y[i]=read();
l=read();
for (j=1;j<=l;j++){
p=read()+1; q=read();
a[i].push_back(make_pair(p,q));
}
}
Ready(); Work();
return 0;
}
[B] Biodiversity
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 25
#define INF 0x3f3f3f3f
using namespace std;
int i,n,Ans=0,flag=0;
string c,s;
map <string,int> M;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL void FAST_IO() {ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
FAST_IO();
cin>>n;
for (i=1;i<=n;i++){
cin>>c;
M[c]+=1;
}
for (auto j : M){
if (j.second>(n-j.second)){
Ans=j.second;
s=j.first;
flag=1;
}
}
if (!flag) cout<<"NONE";
else cout<<s<<endl;
return 0;
}
[C] Ants
题意&题解
签到题
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int u[10000005];
char s[105];
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%s", s);
int len = strlen(s);
if (len >= 7 || s[0] == '-') continue;
int a = 0;
for (int j = 0; j < len; j++)
a = a * 10 + s[j] - '0';
u[a] = 1;
}
for (int i = 0; i <= 1000000; i++) if (u[i] == 0) {
printf("%d", i);
return 0;
}
return 0;
}
[F] Icebergs
题意&题解
签到题
代码
#include <stdio.h>
#include <algorithm>
#include <vector>
#define LL long long
struct Po{LL x, y;} a[12345];
int main()
{
int n;
scanf("%d", &n);
double ans = 0;
while (n--)
{
int m;
scanf("%d", &m);
for (int i=0; i<m; ++i)
scanf("%lld%lld", &a[i].x, &a[i].y);
LL s = 0;
for (int i=0; i<m; ++i)
s += a[i].x*a[(i+1)%m].y - a[i].y*a[(i+1)%m].x;
s = s >= 0 ? s : -s;
ans += s / 2.0;
}
printf("%lld", (LL)ans);
return 0;
}
[G] Swapping Places
题意
有s种动物,每一个动物有一个名字,同时这些动物之间有l对朋友关系(没有传递性).然后给出一个长度为n的动物序列,要求通过任意次数的交换相邻两个动物位置的操作,使得这个序列的字典序最小.交换的条件是被交换的两个动物必须有朋友关系.求最后的交换结果是什么.
题解
首先将每种动物的位置单独存起来,维护一个类似于链表的东西.同时预处理一下每一种动物的表头(也就是排在最前面的那个动物),它的前面有几个动物和它有朋友关系,这个值记为s[i].之后开始枚举最终结果的每一位,按照字典序从小到大枚举动物.假如说一种动物的表头和在它之前的所有动物都有朋友关系,说明它可以通过交换操作换到最前面.记录答案,然后去维护剩下动物的表头的信息.
假如说该动物的位置是i,其他动物的表头的位置是j.如果 i
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
#define N 100010
#define NM 210
using namespace std;
int s,l,n,i,p,q,tail=0;
int L[NM][NM];
int sum[NM],a[N],Ans[N];
string c[NM],x,y;
map <int,string> M;
map <string,int> F;
priority_queue <int> Q;
IL void FAST_IO() {ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);}
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
struct Data{
int tot=0,sum=0,head=0,w=0;
vector <int> a;
}t[NM];
IL void Ready(){
reg int i=0,x=0,j=0;
for (i=1;i<=n;i++){
t[a[i]].a.push_back(i);
t[a[i]].sum++;
}
for (i=1;i<=s;i++){
if (t[i].sum==0) continue;
x=t[i].a[t[i].head];
t[i].w=x;
for (j=1;j<=x;j++)
if (L[a[j]][i]) t[i].tot++;
}
}
IL void Work(){
reg int i=0,j=0,k=0,x=0,y=0;
for (i=1;i<=n;i++){
for (j=1;j<=s;j++){
if (t[j].tot!=t[j].w) continue;
Ans[i]=j; break;
}
a[t[j].w]=INF;
for (k=1;k<=s;k++){
if (k==j) continue;
if (t[j].w<t[k].w){
if (!L[j][k]) t[k].tot++;
continue;
}
}
x=t[j].w+1; t[j].head++; t[j].w=INF;
if (t[j].head>=t[j].sum) continue;
t[j].w=y=t[j].a[t[j].head];
for (k=x;k<=y;k++){
if (a[k]==INF) t[j].tot++;
else if (L[a[k]][j]) t[j].tot++;
}
}
for (i=1;i<=n;i++)
cout<<M[Ans[i]]<<" ";
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
FAST_IO();
cin>>s>>l>>n;
for (i=1;i<=s;i++) cin>>c[i];
sort(c+1,c+1+s);
for (i=1;i<=s;i++) M[i]=c[i],F[c[i]]=i;
for (i=1;i<=l;i++){
cin>>x>>y;
p=F[x]; q=F[y];
L[p][q]=L[q][p]=1;
}
for (i=1;i<=s;i++) L[i][i]=1;
for (i=1;i<=n;i++){
cin>>x; a[i]=F[x];
}
if (!l) {
for (i=1;i<=n;i++) cout<<M[a[i]]<<" ";
return 0;
}
if (n==1){
cout<<M[a[1]]; return 0;
}
Ready(); Work();
return 0;
}
[I] Rats
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
double n1,n2,n12;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%lf%lf%lf",&n1,&n2,&n12);
printf("%lld\n",(LL)((n1+1)*(n2+1)/(n12+1)-1+0.00005));
return 0;
}
[K] Birdwatching
题意
给出一个有向图和一个点t.求t直接相连的点中有多少个满足以下条件:把t到该点的边去掉,则t无法再到达这个点.
题解
删掉所有和t相连的边,然后其他所有边反向.每一个点开一个set用来记录能被哪些和t直接相连的点访问过.然后依次从和t相邻的点开始DFS.假如说a能够从b经过一些点访问到,那么在原图中,一定有一条从t到a,再从a到b的路径,所以b就不符合题意.在DFS完成后据此就可以得到答案.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
int n,m,t,i,x,y,lsum=1;
int head[N];
vector <int> b,Ans;
set <int> f[N];
struct Edge{
int t,next;
}e[N*8];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Add(int s,int t){
e[lsum].t=t; e[lsum].next=head[s]; head[s]=lsum++;
}
IL void Dfs(int x,int pre){
reg int i=0;
if (f[x].size()>1 || f[x].count(pre)) return;
f[x].insert(pre);
for (i=head[x];i;i=e[i].next) Dfs(e[i].t,pre);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); m=read(); t=read()+1;
for (i=1;i<=m;i++){
x=read()+1; y=read()+1;
if (y==t){
b.push_back(x); continue;
}
Add(y,x);
}
for (auto j : b) Dfs(j,j);
for (auto j : b)
if (f[j].size()==1) Ans.push_back(j);
sort(Ans.begin(),Ans.end());
cout<<Ans.size()<<endl;
for (auto j : Ans)
printf("%d\n",j-1);
return 0;
}
总结
这场中第一次碰到了无榜可跟的情况,导致中间产生了一段空档期.中期多线开题感觉精力有些分散.除了硬开了一道G题之外(居然还拿了一血),后面都只写了一些残篇,尤其在打表找规律上浪费了过多的时间.然后喂题的时候一定要再确认下核心题意,最近两场比赛都栽在这上面了.
最后吐槽一下政治正确害人不浅,欧洲赛区的题目居然非要套上一个环保的题目背景,有的还套的很生硬,导致题面又臭又长.下次不拿欧洲的题来练了.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2019-2020 SWERC 部分题解
本文地址: 2019-2020 SWERC 部分题解
