LOJ刷题 / 2019寒假刷题计划
3 分钟 读完 (大约 484 个字)

10083. 「一本通 3.3 例 2」双调路径

题意

读入一个图，计算最小路径的总数。费用时间都相同的两条最小路径只算一条，输出不同种类的最小路径数。

思路

设$f[i][j]$表示在i点且已花费j时的最少时间
$$
f[i][j]=Min(f[k][i-Cost(k,i)]+Time(k,i)|For Each Edge(k,i))
$$

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define E 5010
#define eps 1e-3
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else{
		write(x/10);
		putchar(x%10+'0');
	}
}
//queue<int> q;
//set<int> s;
//priority_queue<int> q1;
//priority_queue<int,vector<int>,greater<int> > q2;
//list<int> l;
//stack<int> s;
int n,m,s,e;
int fir[E],nxt[E],son[E],w[E],cost[E],tot;
void add(int x,int y,int z,int t){++tot;w[tot]=z;son[tot]=y;nxt[tot]=fir[x];cost[tot]=t;fir[x]=tot;}
int dp[105][10005][3],Max,ans,Min=2e9;
int vis[105][10005];
struct node{int pos,dis;};
queue<node> q;
node make(int x,int y){node pp;pp.pos=x;pp.dis=y;return pp;}
void spfa(){
	while(!q.empty()) q.pop();
	for(int i=1;i<=n;i++){
		for(int j=0;j<=10005;j++){
			dp[i][j][0]=2e9;
			dp[i][j][1]=0;
		}
	}
	dp[s][0][0]=0;
	dp[s][0][1]=1;
	vis[s][0]=1;
	q.push(make(s,0));
	while(!q.empty()){
		int u=q.front().pos,dis=q.front().dis;q.pop();
		vis[u][dis]=0;
		for(int i=fir[u];i;i=nxt[i]){
			int to=son[i];
			if(dis+w[i]>Max+1) continue ;
			if(dp[u][dis][0]+cost[i]<dp[to][dis+w[i]][0]){
				dp[to][dis+w[i]][0]=dp[u][dis][0]+cost[i];
				dp[to][dis+w[i]][1]=1;
				if(vis[to][dis+w[i]]==0){
					vis[to][dis+w[i]]=1;
					q.push(make(to,dis+w[i]));
				}
			}
		}
	}
}
int main(){
//	freopen("code.in","r",stdin);freopen("code.out","w",stdout);
	n=read();m=read();s=read();e=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),z=read(),t=read();
		add(x,y,z,t);
		add(y,x,z,t);
	}
	Max=(n-1)*100+5;
	spfa();
	for(int i=0;i<=Max;i++){
		if(!dp[e][i][1]) continue ;
		if(dp[e][i][0]<Min){
			ans++;
			Min=dp[e][i][0];
		}
	}
	write(ans);putchar('\n');
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
3 分钟 读完 (大约 521 个字)

10082. 「一本通 3.3 例 1」Word Rings

题意

每组数据读入一个n和n个字符串。定义前2个与末尾2个字母相同可以连接。问使这个环串的平均长度最大。求这个最大值。不存在输出$No solution$。

思路

平均值公式：
$$
Average=(E_1+E_2+…..+E_n)/n
$$

$$
Average*n=(E_1+E_2+…+E_n)
$$

$$
(E_1-Average)+(E_2-Average)+…+(E_n-Average)=0
$$

那么可以二分答案：
$$
(E_1-Ans)+(E_2-Ans)+…+(E_n-Ans)\geq0
$$
然后瞎搞spfa。

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define E 200010
#define eps 1e-3
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else{
		write(x/10);
		putchar(x%10+'0');
	}
}
//queue<int> q;
//set<int> s;
//priority_queue<int> q1;
//priority_queue<int,vector<int>,greater<int> > q2;
//list<int> l;
//stack<int> s;
int n;
string str[100010];
int fir[E],nxt[E],son[E],tot,cnt,Max;
double w[E],dis[E],flag;
int vis[E];
int f[6666];
void add(int x,int y,double z){++tot;son[tot]=y;nxt[tot]=fir[x];fir[x]=tot;w[tot]=z;}
void spfa(int s,int v,double mid){
	if(flag==1) return ;
	vis[s]=v;
	for(int i=fir[s];i;i=nxt[i]){
		int to=son[i];
		if(dis[s]+w[i]>dis[to]+mid){
			dis[to]=dis[s]+w[i]-mid;
			if(dis[to]>Max){
				flag=1;
				return ;
			}
			if(!vis[to]) spfa(to,v,mid);
			if(flag) return ;
			else if(vis[to]==v){
				flag=1;
				return ;
			}
		}
	}
	vis[s]=0;
}
bool check(double mid){
	flag=0;
	for(int i=0;i<=cnt;i++) dis[i]=0.0;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=cnt;i++){
		spfa(i,i,mid);
		if(flag==1) break;
	}
	return flag;
}
int main(){
//	freopen("code.in","r",stdin);freopen("code.out","w",stdout);
	n=read();
	while(n!=0){
		for(int i=1;i<=n;i++) cin>>str[i];
		memset(fir,0,sizeof(fir));
		memset(f,0,sizeof(f));
		tot=0;cnt=0;Max=0;
		for(int i=1;i<=n;i++){
			int len=str[i].length();
			Max=max(Max,len);
			int a=(str[i][0]-'a')*26+str[i][1]-'a';
			int b=(str[i][len-2]-'a')*26+str[i][len-1]-'a';
			if(!f[a]) f[a]=++cnt;
			int A=f[a];
			if(!f[b]) f[b]=++cnt;
			int B=f[b];
			add(A,B,(double)len);
		}
		Max*=n;
		double l=0,r=1000,ans=-1,mid;
		while(l+eps<r){
			mid=(l+r)/2;
			if(check(mid)) l=mid,ans=mid;
			else r=mid;
		}
		if(ans!=-1) printf("%.2lf\n",ans);
		else puts("No solution");
		n=read();
	}
	return 0;
}
几秒 读完 (大约 107 个字)

我的博客

欢迎来到yzx1798106406的博客
洛谷博客地址:点击跳转
博客园博客地址:点击跳转
如果发现博客由明显问题，欢迎指出！
这是本博客的第一篇博文。
本博客搭建使用码云，Powered by Hexo & Icarus。
本博客内所有文章转载须注明出处。
谢谢！

关注我

链接

分类

标签云

Link Cut Tree RMQ Splay bfs dp fhq treap spfa 二分 博弈论 堆 差分 异或 数论 斜率优化 暴力 最长链 枚举 树状数组 树链剖分 模拟 线性筛 线段树 背包 贪心 通知

最新文章

归档

标签

Link Cut Tree 1
RMQ 5
Splay 2
bfs 1
dp 11
fhq treap 1
spfa 9
二分 3
博弈论 1
堆 1
差分 4
异或 1
数论 1
斜率优化 1
暴力 1
最长链 1
枚举 1
树状数组 6
树链剖分 1
模拟 1
线性筛 1
线段树 5
背包 1
贪心 1
通知 1

最新文章

归档

标签

Link Cut Tree 1
RMQ 5
Splay 2
bfs 1
dp 11
fhq treap 1
spfa 9
二分 3
博弈论 1
堆 1
差分 4
异或 1
数论 1
斜率优化 1
暴力 1
最长链 1
枚举 1
树状数组 6
树链剖分 1
模拟 1
线性筛 1
线段树 5
背包 1
贪心 1
通知 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×