你最愿意做的哪件事，才是你的天赋所在

0%

The 2019 Asia Nanchang First Round Online Programming Contest

发表于 更新于 Valine：

题目连接

The 2019 Asia Nanchang First Round Online Programming Contest

B

坑点在于，如果用前向星存图的话是会有重边的，所以再dijkstra里面不要用vis标记，用SPFA应该可以轻松跑过
初始化dis数组一定要初始化到尽量大的值，不然ui影响结果的

思路

建立一个大源点，连接消防队的点，跑一遍最短路跟消防英雄的对比。

代码实现

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>
//#include<regex>
#include<cstdio>
using namespace std;
#define ll long long 
#define maxn 1010
#define inf 0x3f3f3f3f
bool vis[maxn];
vector<int>p;
ll dis[maxn],cnt;
struct node
{
	int v,cap,next;
	node(){}
	node(int v,int cap):v(v),cap(cap){}
	bool operator < (const node &a)const
	{
		return cap>a.cap;
	}
}edge[maxn*maxn];
int head[maxn];
//vector<int>g[maxn];
void add(int u,int v,int cap)
{
	edge[cnt].v=v;
	edge[cnt].cap=cap;
	edge[cnt].next=head[u];
	head[u]=cnt;
	cnt++;
}
void dijkstra(int s,int city)
{
	for(int i=1;i<=city;i++)dis[i]=inf;
    priority_queue<node>q;
    dis[s]=0;
    q.push(node(s,0));
    while(!q.empty())
    {
    	node s=q.top();q.pop();
    	int u=s.v;
    	for(int i=head[s.v];i!=-1;i=edge[i].next)
    	{
    		int v=edge[i].v;
    		int cap=edge[i].cap;
    		if(dis[v]>dis[u]+cap)
    		{
    			dis[v]=dis[u]+cap;
    			q.push(node(v,dis[v]));
			}
		}
	}
	return ;
}
int main()
{
		int t;
	scanf("%d",&t);
	while(t--)
	{   memset(head,-1,sizeof(head));
        cnt = 0;
		int n,m,s,k,c;
		scanf("%d %d %d %d %d",&n,&m,&s,&k,&c);
		int sups = 0;
		for(int i=0;i<k;i++)
		{
			int x;
			scanf("%d",&x);
			add(sups,x,0);
			add(x,sups,0);
		}
		for(int i=1;i<=m;i++)
		{
			int u,v,w;
			scanf("%d %d %d",&u,&v,&w);
			add(u,v,w);
            add(v,u,w);
		}
		dijkstra(sups,n);
		ll maxa = -1;
		for(int i=1;i<=n;i++)
		{
			maxa = max(maxa,dis[i]);
		}
		dijkstra(s,n);
		ll maxb = -1;
		for(int i=1;i<=n;i++)
		{
			maxb= max(maxb,dis[i]);
		}
		if(maxa*c<maxb)
		printf("%lld\n",maxa);
		else printf("%lld\n",maxb);
	}
}

H

这题可以说卡常了把，用map没过，用unordered_map过了

思路

用矩阵快速幂qlog(p)的复杂度求出f(n),然后求出后记录一下，可以发现一个规律，
f(n)=f(n/md+n%md)，即可优化掉一个log然后用unordered_map优化就可以过了
这个不是正解。

代码实现

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
89
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define up(i,a,n) for(int i=a;i<=n;i++)
#define down(i,a,n) for(int i=a;i>=n;i--)
const int maxn=2;
const int md=998244353;
unordered_map<ll,ll>mp;
ll n,x,y;
struct node
{
	ll a[maxn][maxn];
	inline friend node operator * (node a,node b)
	{
	node c;
	memset(c.a,0,sizeof(c.a));
	up(i,0,1)
	up(j,0,1)
	up(k,0,1)
	c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%md;
	return c;
    }
}unit;
void init()
{
   unit.a[0][0]=3;
   unit.a[0][1]=1;
   unit.a[1][0]=2;
   unit.a[1][1]=0; 
}
long long pow_node(ll k)
{  
	node ans,a;
	a=unit;
	memset(ans.a,0,sizeof(ans.a));
	up(i,0,1)
	ans.a[i][i]=1;
	while(k)
	{
		if(k&1)ans=ans*a;
		k/=2;
		a=a*a;
	}
	return ans.a[0][0]; 
}
ll pow_num(ll a,ll k)
{
	ll ans=1;
	a%=md;
	while(k)
	{
		if(k&1)ans=(ans*a)%md;
		k/=2;
		a=(a*a)%md;
	}
	return ans;
}
int main()
{   
	scanf("%lld %lld",&n,&x);
	ll now = x;
	init();
	int cnt = 0;
	long long ans = 0;
	long long tans;
	long long pre=x;
	for(int i=0;i<n;i++)
	{
		if(now>=md)
		{
		now=(now/md+now%md);
		}
		if(mp[now]!=0)
		{   cnt++;
			ans^=mp[now];
			pre = pre^(mp[now]*mp[now]);
			now = pre;
		}
		else
		{
			tans = pow_node(now-1);
			ans^=tans;
			mp[now]=tans;
			pre = pre^(tans*tans);
			now = pre;
		}
	}
	printf("%lld\n",ans);
}
你最愿意做的哪件事，才是你的天赋所在
-------------你最愿意做的哪件事才是你的天赋所在-------------