2019ICPC南昌网络赛部分题解

今天打得也算是不错,为学校争取到了一个名额,学校排名终于进入前100了。

A.Enju With math problem

B.Fire-fighting Hero

题目大意为:在一个无向有权图中,有一个消防英雄,有多个消防队,消防英雄要和消防队进行比赛,每个人的值为距离其他所有点的最短路的最大值(消防队到一个点有多个最短路取最小),由于消防英雄跑得比消防队快,所以消防英雄的值要除以一个系数$C$,问最后谁的值小谁赢,并输出这个值(如果消防英雄赢,输出除以$C$之前的值)。

跑两遍最短路即可。第一遍以消防英雄为源点跑最短路,第二遍建立一个超级源点,连接所有的消防队,然后在超级源点为起点跑最短路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
int n,m,S,K,C;
struct node{
int id;
ll dis;
};
bool operator<(node a,node b){
return a.dis>b.dis;
}
bool vis[N];
vector<pair<int,ll>> G[N];
ll dis[N];
void dij(int s){
priority_queue<node> q;
memset(vis,0,sizeof(vis));
rep(i,0,n) dis[i]=llINF;
dis[s]=0;
q.push({s,0});
while(!q.empty()){
node rt=q.top();q.pop();
int u=rt.id;
if(vis[u]) continue;
vis[u]=1;
for(auto V:G[u]){
int v=V.first;
ll w=V.second;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({v,dis[v]});
}
}
}
}
int id[N];
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d %d %d %d %d",&n,&m,&S,&K,&C);
rep(i,0,n) G[i].clear();
rep(i,1,K){
scanf("%d",&id[i]);
}
int u,v;
ll w;
rep(i,1,m){
scanf("%d %d %lld",&u,&v,&w);
G[u].push_back({v,w});
G[v].push_back({u,w});
}
ll ans1,ans2;
ans1=ans2=0;
dij(S);
rep(i,1,n) ans1=max(ans1,dis[i]);
rep(i,1,K){
G[0].push_back({id[i],0});
G[id[i]].push_back({0,0});
}
dij(0);
rep(i,1,n) ans2=max(ans2,dis[i]);
if(ans1<=ans2*C){
cout<<ans1<<endl;
}else{
cout<<ans2<<endl;
}
}
return 0;
}

C.Hello 2019

D.Interesting

E.Magic Master

题目大意为:你作为一个魔术师,总共有n张牌,编号为1~n,现在你要你的观众随便说一个数字,然后开始表演魔术,取出最上面的第一张牌,然后依次将此时最上面的m张牌依次放在牌的最后,然后再取最上面的一张牌,然后再依次最上面的m张牌放在最后面…持续这个过程直到取完所有的牌,且取出的牌根据取出的顺序连续递增。问刚开始扑克牌的排列是什么样的。

直接利用队列逆向模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
int ans[50000000];
int main(){
int T;scanf("%d",&T);
int n,m,Q;
while(T--){
scanf("%d %d %d", &n, &m, &Q);
queue<int> q;
rep(i, 1, n) q.push(i);
int cur = 1;
while(cur <= n){
ans[q.front()] = cur++; q.pop();
rep(i, 1, m){
q.push(q.front());
q.pop();
}
}
while(Q--){
int k;
scanf("%d", &k);
printf("%d\n", ans[k]);
}
}
return 0;
}

F.Megumi With String

G.Pangu Separates Heaven and Earth

签到题,等于1输出18000,否则输出0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
int main(){
ll T,n;
read(T);
while(T--){
read(n);
if(n==1) puts("18000");
else puts("0");
}
return 0;
}

H.The Nth Item

题目大意为:给你一个数列$F[N]$,$F[0]=0$,$F[1]=1$,$F[n]=3*F[n-1]+2*F[n-2](n\geq 2)$,现在给你两个数$Q,N$,总共Q次查询,初始$N_1=N$,$A_1=F[N_1]\space mod \space 998244353$ ,$N_i=N_{i-1}\oplus A_i^2$,问$A_1 \oplus A_2 \oplus A_3 \oplus … \oplus A_Q$ 的值。

矩阵快速幂,由于有循环节,遇到循环节直接跳过即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
const int mod = 998244353;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
ll t[100]={0,1};
struct node{
ll a[2][2];
}G;
node operator *(node a,node b){
node res;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
res.a[i][j]=0;
for(int k=0;k<2;k++){
res.a[i][j]=(res.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
}
}
}
return res;
}
node operator *(node a,ll b){
node res;
res.a[0][0]=res.a[1][1]=1;
res.a[0][1]=res.a[1][0]=0;
while(b){
if(b&1) res=res*a;
a=a*a;
b>>=1;
}
return res;
}
void init(){
G.a[0][0]=3;G.a[0][1]=2;
G.a[1][0]=1;G.a[1][1]=0;
}
map<ll,bool> mmp;
ll ans=0,now;
ll Q,NN;
ll suf;
void solve(){
cin>>Q>>NN;
rep(i,1,Q){
init();
if(i==1)
{
now=NN;
if(now==0||now==1)
{
ans^=t[now];
suf=t[now];
break;
}
else{
G=G*(now-1);
ans^=G.a[0][0];
suf=G.a[0][0];
}
}
else{
now^=(suf*suf);
if(now==0||now==1){
ans^=t[now];
suf=t[now];
break;
}
else{
G=G*(now-1);
ans^=G.a[0][0];
suf=G.a[0][0];
}
}
if(mmp[now]){
int x=(i-mmp[now])*2;
i=((Q-i)/x)*x;
}
if(!mmp[now]) mmp[now]=1;
}
cout<<ans<<endl;
}
int main(){
solve();
return 0;
}

I.Yukino With Subinterval

感谢您的支持
-------------本文结束感谢您的阅读-------------